smallset.h

Go to the documentation of this file.

/*  This file is part of libDAI - http://www.libdai.org/
 *
 *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
 *
 *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
 */




#ifndef __defined_libdai_smallset_h
#define __defined_libdai_smallset_h


#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>


namespace dai {



template <typename T>
class SmallSet {
    private:
        std::vector<T> _elements;

    public:

        SmallSet() : _elements() {}

        SmallSet( const T &t ) : _elements() {
            _elements.push_back( t );
        }

        SmallSet( const T &t1, const T &t2 ) {
            if( t1 < t2 ) {
                _elements.push_back( t1 );
                _elements.push_back( t2 );
            } else if( t2 < t1 ) {
                _elements.push_back( t2 );
                _elements.push_back( t1 );
            } else
                _elements.push_back( t1 );
        }


        template <typename TIterator>
        SmallSet( TIterator begin, TIterator end, size_t sizeHint ) {
            _elements.reserve( sizeHint );
            _elements.insert( _elements.begin(), begin, end );
            std::sort( _elements.begin(), _elements.end() );
            typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
            _elements.erase( new_end, _elements.end() );
        }


        SmallSet& insert( const T& t ) {
            typename SmallSet<T>::iterator it = std::lower_bound( _elements.begin(), _elements.end(), t );
            if( (it == _elements.end()) || (*it != t) )
                _elements.insert( it, t );
            return *this;
        }

        SmallSet& erase( const T& t ) {
            return (*this /= t);
        }

        SmallSet operator/ ( const SmallSet& x ) const {
            SmallSet res;
            std::set_difference( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
            return res;
        }

        SmallSet operator| ( const SmallSet& x ) const {
            SmallSet res;
            std::set_union( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
            return res;
        }

        SmallSet operator& ( const SmallSet& x ) const {
            SmallSet res;
            std::set_intersection( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
            return res;
        }

        SmallSet& operator/= ( const SmallSet& x ) {
            return (*this = (*this / x));
        }

        SmallSet& operator/= ( const T &t ) {
            typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
            if( pos != _elements.end() )
                if( *pos == t ) // found element, delete it
                    _elements.erase( pos );
            return *this;
        }

        SmallSet& operator|= ( const SmallSet& x ) {
            return( *this = (*this | x) );
        }

        SmallSet& operator|= ( const T& t ) {
            typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
            if( pos == _elements.end() || *pos != t ) // insert it
                _elements.insert( pos, t );
            return *this;
        }

        SmallSet& operator&= ( const SmallSet& x ) {
            return (*this = (*this & x));
        }

        bool operator<< ( const SmallSet& x ) const {
            return std::includes( x._elements.begin(), x._elements.end(), _elements.begin(), _elements.end() );
        }

        bool operator>> ( const SmallSet& x ) const {
            return std::includes( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end() );
        }


        bool intersects( const SmallSet& x ) const {
            return( (*this & x).size() > 0 );
        }

        bool contains( const T &t ) const {
            return std::binary_search( _elements.begin(), _elements.end(), t );
        }

        typename std::vector<T>::size_type size() const { return _elements.size(); }

        bool empty() const { return _elements.size() == 0; }

        std::vector<T>& elements() { return _elements; }

        const std::vector<T>& elements() const { return _elements; }

        typedef typename std::vector<T>::const_iterator const_iterator;
        typedef typename std::vector<T>::iterator iterator;
        typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
        typedef typename std::vector<T>::reverse_iterator reverse_iterator;


        iterator begin() { return _elements.begin(); }
        const_iterator begin() const { return _elements.begin(); }

        iterator end() { return _elements.end(); }
        const_iterator end() const { return _elements.end(); }

        reverse_iterator rbegin() { return _elements.rbegin(); }
        const_reverse_iterator rbegin() const { return _elements.rbegin(); }

        reverse_iterator rend() { return _elements.rend(); }
        const_reverse_iterator rend() const { return _elements.rend(); }

        T& front() { return _elements.front(); }
        const T& front() const { return _elements.front(); }

        T& back() { return _elements.back(); }
        const T& back() const { return _elements.back(); }


        friend bool operator==( const SmallSet &a, const SmallSet &b ) {
            return (a._elements == b._elements);
        }

        friend bool operator!=( const SmallSet &a, const SmallSet &b ) {
            return !(a._elements == b._elements);
        }

        friend bool operator<( const SmallSet &a, const SmallSet &b ) {
            return a._elements < b._elements;
        }


        friend std::ostream& operator << ( std::ostream& os, const SmallSet& x ) {
            os << "{";
            for( typename std::vector<T>::const_iterator it = x.begin(); it != x.end(); it++ )
                os << (it != x.begin() ? ", " : "") << *it;
            os << "}";
            return os;
        }

        std::string toString() const {
            std::stringstream ss;
            ss << *this;
            return ss.str();
        }
};


} // end of namespace dai


#endif