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 <ostream>
#include <algorithm>
 
#include <extensions/iterator.hpp>
#include <extensions/range.hpp>
 
#include "vector.hpp"
 
namespace ext {
 
template < class T, class Compare = std::less<T>, class Alloc = std::allocator<T> >
class linear_set {
    ext::vector < T, Alloc > m_data;
 
    Compare m_comp;
 
    bool eq ( const T & first, const T & second ) {
        return ! m_comp ( first, second ) && ! m_comp ( second, first );
    }
 
    void sort_unique ( ) {
        std::sort ( m_data.begin ( ), m_data.end ( ), m_comp );
        m_data.erase ( std::unique ( m_data.begin ( ), m_data.end ( ), std::bind ( &linear_set < T >::eq, this, std::placeholders::_1, std::placeholders::_2 ) ), m_data.end ( ) );
    }
 
public:
    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 linear_set (const Compare& comp = Compare(), const Alloc& alloc = Alloc()) : m_data ( alloc ), m_comp ( comp ) {
    }
 
    explicit linear_set (const Alloc& alloc) : m_data ( alloc ), m_comp ( Compare ( ) ) {
    }
 
    template <class InputIterator>
    linear_set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Alloc& alloc = Alloc()) : m_data ( first, last, alloc ), m_comp ( comp ) {
        sort_unique ( );
    }
 
    template < class Iterator >
    linear_set ( const ext::iterator_range < Iterator > & range ) : linear_set ( range.begin ( ), range.end ( ) ) {
    }
 
    linear_set (const linear_set& x) : m_data ( x.m_data ), m_comp ( x.m_comp ) {
    }
 
    linear_set (const linear_set& x, const Alloc& alloc) : m_data ( x.m_data, alloc ), m_comp ( x.m_comp ) {
    }
 
    linear_set (linear_set&& x) : m_data ( std::move ( x.m_data ) ), m_comp ( x.m_comp ) {
    }
 
    linear_set (linear_set&& x, const Alloc& alloc) : m_data ( std::move ( x.m_data ), alloc ), m_comp ( x.m_comp ) {
    }
 
    linear_set (std::initializer_list<T> il, const Compare& comp = Compare(), const Alloc& alloc = Alloc()) : m_data ( std::move ( il ), alloc ), m_comp ( comp ) {
        sort_unique ( );
    }
 
    ~linear_set ( ) {
    }
 
    iterator begin() & noexcept {
        return m_data.begin ( );
    }
 
    const_iterator begin() const & noexcept {
        return m_data.begin ( );
    }
 
    auto begin ( ) && noexcept {
        return make_set_move_iterator ( 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 make_set_move_iterator ( 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 {
        m_data.clear ( );
    }
 
    size_t count ( const T& value ) const {
        return std::binary_search ( m_data.begin ( ), m_data.end ( ), 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) {
        return m_data.erase ( position );
    }
 
    size_t erase (const T& val) {
        const_iterator position = lower_bound ( val );
        if ( position != end ( ) && eq ( * position, val ) )
            return m_data.erase ( position ), 1;
        else
            return 0;
    }
 
    iterator erase (const_iterator first, const_iterator last) {
        return m_data.erase ( first, last );
    }
 
    const_iterator find (const T& val) const {
        const_iterator position = lower_bound ( begin ( ), end ( ), val, m_comp );
        if ( eq ( * position, val ) )
            return position;
        else
            return end ( );
    }
 
    iterator find (const T& val) {
        iterator position = lower_bound ( val );
        if ( eq ( * position, val ) )
            return position;
        else
            return end ( );
    }
 
    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
            return std::make_pair ( m_data.emplace ( 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 ) ) )
            return m_data.emplace ( position, std::move ( val ) );
 
        return insert ( std::move ( val ) ).first;
    }
 
    template <class InputIterator>
    void insert (InputIterator first, InputIterator last) {
        m_data.insert ( m_data.end ( ), first, last );
        sort_unique ( );
    }
 
    void insert (std::initializer_list<T> il) {
        insert ( il.begin ( ), il.end ( ) );
    }
 
    Compare key_comp() const {
        return m_comp;
    }
 
    iterator lower_bound (const T& val) {
        return std::lower_bound ( begin ( ), end ( ), val, m_comp );
    }
 
    const_iterator lower_bound (const T& val) const {
        return std::lower_bound ( begin ( ), end ( ), val, m_comp );
    }
 
    size_t max_size() const noexcept {
        return m_data.max_size ( );
    }
 
    linear_set& operator= (const linear_set& x) {
        m_data = x.m_data;
        m_comp = x.m_comp;
        return *this;
    }
 
    linear_set& operator= (linear_set&& x) {
        m_data = std::move ( x.m_data );
        m_comp = std::move ( x.m_comp );
        return *this;
    }
 
    linear_set& operator= (std::initializer_list<T> il) {
        m_data = std::move ( il );
        std::sort ( m_data.begin ( ), m_data.end ( ), m_comp );
        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 (linear_set& x) {
        using std::swap;
        swap ( m_data, x.m_data );
        swap ( m_comp, x.m_comp );
    }
 
    iterator upper_bound (const T& val) {
        return std::upper_bound ( begin ( ), end ( ), val, m_comp );
    }
 
    const_iterator upper_bound (const T& val) const {
        return std::upper_bound ( begin ( ), end ( ), val, m_comp );
    }
 
    Compare value_comp() const {
        return m_comp;
    }
 
    bool contains ( const T & key ) const {
        return this->count ( key ) != 0U;
    }
 
    template < class K >
    bool contains ( const K & key ) const {
        return this->count ( key ) != 0U;
    }
 
    bool operator == ( const linear_set<T,Compare,Alloc>& rhs ) const {
        const linear_set<T,Compare,Alloc>& lhs = * this;
        return lhs.m_data == rhs.m_data;
    }
 
    auto operator <=>  ( const linear_set<T,Compare,Alloc>& rhs ) const {
        const linear_set<T,Compare,Alloc>& lhs = * this;
        return lhs.m_data <=> rhs.m_data;
    }
 
};
 
template <class T, class Compare, class Alloc>
void swap ( ext::linear_set < T, Compare, Alloc > & x, ext::linear_set < T, Compare, Alloc > & y) {
    x.swap ( y );
}
 
template< class T, class ... Ts >
std::ostream& operator<<(std::ostream& out, const ext::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 */