managed_linear_set.hpp

Go to the documentation of this file.

 
/*
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
 
 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 
 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 
 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include <extensions/container/linear_set.hpp>
#include <extensions/algorithm.hpp>
 
namespace ext {
 
template < class T, class Compare = std::less<T>, class Alloc = std::allocator<T> >
class managed_linear_set {
    ext::linear_set < T, Compare, Alloc > m_data;
 
    std::vector < std::function < void ( const T & ) > > insertCallbacks;
 
    std::vector < std::function < void ( const T & ) > > removeCallbacks;
 
    void fireInsert ( const T & element ) const {
        for ( const std::function < void ( const T & ) > & callback : insertCallbacks ) {
            callback ( element );
        }
    }
 
    void fireRemove ( const T & element ) const {
        for ( const std::function < void ( const T & ) > & callback : removeCallbacks ) {
            callback ( element );
        }
    }
 
    bool eq ( const T & first, const T & second ) {
        return ! m_data.value_comp ( ) ( first, second ) && ! m_data.value_comp ( ) ( second, first );
    }
 
public:
    void addInsertCallback ( const std::function < void ( const T & ) > & callback ) {
        insertCallbacks.push_back ( callback );
    }
 
    void addRemoveCallback ( const std::function < void ( const T & ) > & callback ) {
        removeCallbacks.push_back ( callback );
    }
 
    typedef T value_type;
 
    typedef typename ext::vector < T, Alloc >::const_iterator iterator;
 
    typedef typename ext::vector < T, Alloc >::const_iterator const_iterator;
 
    typedef typename ext::vector < T, Alloc >::const_reverse_iterator reverse_iterator;
 
    typedef typename ext::vector < T, Alloc >::const_reverse_iterator const_reverse_iterator;
 
    explicit managed_linear_set (const Compare& comp = Compare(), const Alloc& alloc = Alloc()) : m_data ( comp, alloc ) {
    }
 
    explicit managed_linear_set (const Alloc& alloc) : m_data ( alloc, Compare ( ) ) {
    }
 
    template <class InputIterator>
    managed_linear_set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Alloc& alloc = Alloc()) : m_data ( first, last, comp, alloc ) {
    }
 
    template < class Iterator >
    managed_linear_set ( const ext::iterator_range < Iterator > & range ) : managed_linear_set ( range.begin ( ), range.end ( ) ) {
    }
 
    managed_linear_set (const managed_linear_set& x) : m_data ( x.m_data ) {
    }
 
    managed_linear_set ( const managed_linear_set & x, const Alloc & alloc ) : m_data ( x.m_data, x.value_comp ( ), alloc ) {
    }
 
    managed_linear_set ( managed_linear_set && x ) {
        for ( const T & elem : x ) {
            x.fireRemove ( elem );
        }
 
        m_data = std::move ( x.m_data );
    }
 
    managed_linear_set (managed_linear_set&& x, const Alloc& alloc) : m_data ( x.value_comp ( ), alloc ) {
        for ( const T & elem : x ) {
            x.fireRemove ( elem );
        }
 
        m_data = std::move ( x.m_data );
    }
 
    managed_linear_set (std::initializer_list<T> il, const Compare& comp = Compare(), const Alloc& alloc = Alloc()) : m_data ( std::move ( il ), comp, alloc ) {
    }
 
    ~managed_linear_set ( ) {
    }
 
    iterator begin() & noexcept {
        return m_data.begin ( );
    }
 
    const_iterator begin() const & noexcept {
        return m_data.begin ( );
    }
 
    auto begin ( ) && noexcept {
        return std::move ( * this ).begin ( );
    }
 
    const_iterator cbegin() const noexcept {
        return m_data.cbegin ( );
    }
 
    iterator end() & noexcept {
        return m_data.end ( );
    }
 
    const_iterator end() const & noexcept {
        return m_data.end ( );
    }
 
    auto end ( ) && noexcept {
        return std::move ( * this ).end ( );
    }
 
    const_iterator cend() const noexcept {
        return m_data.cend ( );
    }
 
    auto range ( ) & {
        auto endIter = end ( );
        auto beginIter = begin ( );
        return ext::iterator_range < decltype ( endIter ) > ( beginIter, endIter );
    }
 
    auto range ( ) const & {
        auto endIter = end ( );
        auto beginIter = begin ( );
        return ext::iterator_range < decltype ( endIter ) > ( beginIter, endIter );
    }
 
    auto range ( ) && {
        auto endIter = std::move ( * this ).end ( );
        auto beginIter = std::move ( * this ).begin ( );
        return ext::iterator_range < decltype ( endIter ) > ( beginIter, endIter );
    }
 
    void clear() noexcept {
        for ( const T & elem : m_data ) {
            fireRemove ( elem );
        }
 
        m_data.clear ( );
    }
 
    size_t count ( const T& value ) const {
        return m_data.count ( value );
    }
 
    const_reverse_iterator crbegin() const noexcept {
        return m_data.crbegin ( );
    }
 
    const_reverse_iterator crend() const noexcept {
        return m_data.crend ( );
    }
 
    template <class... Args>
    std::pair < iterator, bool > emplace ( Args && ... args ) {
        return insert ( T ( std::forward ( args ) ... ) );
    }
 
    template <class... Args>
    iterator emplace_hint ( const_iterator position, Args && ... args ) {
        return insert ( position, T ( std::forward ( args ) ... ) );
    }
 
    bool empty ( ) const noexcept {
        return m_data.empty ( );
    }
 
    std::pair < const_iterator, const_iterator > equal_range ( const T & val ) const {
        return std::make_pair ( lower_bound ( val ), upper_bound ( val ) );
    }
 
    std::pair < iterator, iterator > equal_range ( const T & val ) {
        return std::make_pair ( lower_bound ( val ), upper_bound ( val ) );
    }
 
    iterator erase ( const_iterator position ) {
        fireRemove ( * position );
        return m_data.erase ( position );
    }
 
    size_t erase ( const T & val ) {
        const_iterator position = lower_bound ( val );
        if ( position != end ( ) && eq ( * position, val ) ) {
            fireRemove ( * position );
            m_data.erase ( position );
            return 1;
        } else {
            return 0;
        }
    }
 
    iterator erase (const_iterator first, const_iterator last) {
        for ( const T & elem : ext::make_iterator_range ( first, last ) )
            fireRemove ( elem );
 
        return m_data.erase ( first, last );
    }
 
    const_iterator find ( const T & val ) const {
        m_data.find ( val );
    }
 
    iterator find ( const T & val ) {
        m_data.find ( val );
    }
 
    Alloc get_allocator() const noexcept {
        return m_data.get_allocator ( );
    }
 
    std::pair < iterator, bool > insert ( const T & val ) {
        return insert ( T ( val ) );
    }
 
    std::pair < iterator, bool > insert ( T && val ) {
        const_iterator position = lower_bound ( val );
        if ( position != end ( ) && eq ( * position, val ) )
            return std::make_pair ( position, false );
        else {
            fireInsert ( val );
            return std::make_pair ( m_data.insert ( position, std::move ( val ) ), true );
        }
    }
 
    iterator insert ( const_iterator position, const T & val ) {
        return insert ( position, T ( val ) );
    }
 
    iterator insert (const_iterator position, T&& val) {
        if ( position != end ( ) && eq ( *  position, val ) )
            return position;
 
        if ( position != end ( ) && m_comp ( val, * position ) && ( position == begin ( ) || m_comp ( * std::prev ( position ), val ) ) ) {
            fireInsert ( val );
            return m_data.emplace ( position, std::move ( val ) );
        }
 
        return insert ( std::move ( val ) ).first;
    }
 
    template <class InputIterator>
    void insert (InputIterator first, InputIterator last) {
        for ( const T & elem : ext::make_iterator_range ( first, last ) )
            fireInsert ( elem );
 
        m_data.insert ( first, last );
    }
 
    void insert (std::initializer_list<T> il) {
        insert ( il.begin ( ), il.end ( ) );
    }
 
    Compare key_comp() const {
        return m_data.key_comp();
    }
 
    iterator lower_bound ( const T & val ) {
        return m_data.lower_bound ( val );
    }
 
    const_iterator lower_bound (const T& val) const {
        return m_data.lower_bound ( val );
    }
 
    size_t max_size() const noexcept {
        return m_data.max_size ( );
    }
 
    managed_linear_set & operator= ( const managed_linear_set & data ) {
        ext::set_symmetric_difference ( m_data.begin ( ), m_data.end ( ), data.begin ( ), data.end ( ), ext::make_callback_iterator ( std::bind ( & managed_linear_set::fireRemove, this, std::placeholders::_1 ) ), ext::make_callback_iterator ( std::bind ( & managed_linear_set::fireInsert, this, std::placeholders::_1 ) ) );
 
        m_data = data.m_data;
        return *this;
    }
 
    managed_linear_set & operator= ( managed_linear_set && data ) {
        ext::set_symmetric_difference ( m_data.begin ( ), m_data.end ( ), data.begin ( ), data.end ( ), ext::make_callback_iterator ( std::bind ( & managed_linear_set::fireRemove, this, std::placeholders::_1 ) ), ext::make_callback_iterator ( std::bind ( & managed_linear_set::fireInsert, this, std::placeholders::_1 ) ) );
 
        for ( const T & elem : data ) {
            data.fireRemove ( elem );
        }
 
        m_data = std::move ( data.m_data );
        return *this;
    }
 
    managed_linear_set & operator= ( std::initializer_list < T > il ) {
        linear_set < T > data ( il );
        ext::set_symmetric_difference ( m_data.begin ( ), m_data.end ( ), data.begin ( ), data.end ( ), ext::make_callback_iterator ( std::bind ( & managed_linear_set::fireRemove, this, std::placeholders::_1 ) ), ext::make_callback_iterator ( std::bind ( & managed_linear_set::fireInsert, this, std::placeholders::_1 ) ) );
 
        m_data = std::move ( data );
        return *this;
    }
 
    reverse_iterator rbegin() noexcept {
        return m_data.rbegin ( );
    }
 
    const_reverse_iterator rbegin() const noexcept {
        return m_data.rbegin ( );
    }
 
    reverse_iterator rend() noexcept {
        return m_data.rend ( );
    }
 
    const_reverse_iterator rend() const noexcept {
        return m_data.rend ( );
    }
 
    size_t size() const noexcept {
        return m_data.size ( );
    }
 
    void swap ( managed_linear_set & data ) {
        auto thisToOther = ext::make_callback_iterator ( [ this, & data ] ( const T & element ) { this->fireRemove ( element ); data.fireInsert ( element ); } );
        auto otherToThis = ext::make_callback_iterator ( [ this, & data ] ( const T & element ) { data.fireRemove ( element ); this->fireInsert ( element ); } );
        ext::set_symmetric_difference ( m_data.begin ( ), m_data.end ( ), data.begin ( ), data.end ( ), thisToOther, otherToThis );
 
        m_data.swap ( data.m_data );
    }
 
    iterator upper_bound ( const T & val) {
        return m_data.upper_bound ( val );
    }
 
    const_iterator upper_bound (const T& val) const {
        return m_data.upper_bound ( val );
    }
 
    Compare value_comp() const {
        return m_data.value_comp ( );
    }
 
    auto operator <=> ( const managed_linear_set < T, Compare, Alloc > & other ) const = default;
 
};
 
template< class T, class ... Ts >
std::ostream& operator<<(std::ostream& out, const ext::managed_linear_set<T, Ts ...>& value) {
    out << "{";
 
    bool first = true;
    for(const T& item : value) {
        if(!first) out << ", ";
        first = false;
        out << item;
    }
 
    out << "}";
    return out;
}
 
} /* namespace ext */
 
namespace std {
 
template <class T, class Compare, class Alloc>
void swap ( ext::managed_linear_set < T, Compare, Alloc > & x, ext::managed_linear_set < T, Compare, Alloc > & y ) {
    x.swap ( y );
}
 
} /* namespace std */