include/dai/smallset.h

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  libDAI is licensed under the terms of the GNU General Public License version
   4  *  2, or (at your option) any later version. libDAI is distributed without any
   5  *  warranty. See the file COPYING for more details.
   6  *
   7  *  Copyright (C) 2002       Martijn Leisink  [martijn@mbfys.kun.nl]
   8  *  Copyright (C) 2006-2009  Joris Mooij      [joris dot mooij at libdai dot org]
   9  *  Copyright (C) 2002-2007  Radboud University Nijmegen, The Netherlands
  10  */
  11
  12
  13 /// \file
  14 /// \brief Defines SmallSet<T> class
  15
  16
  17 #ifndef __defined_libdai_smallset_h
  18 #define __defined_libdai_smallset_h
  19
  20
  21 #include <vector>
  22 #include <algorithm>
  23
  24
  25 namespace dai {
  26
  27
  28 /// Represents a set; the implementation is optimized for a small number of elements.
  29 /** SmallSet uses an ordered std::vector<T> to represent a set; this is faster than
  30  *  using a std::set<T> if the number of elements is small.
  31  *  \tparam T Should be less-than-comparable.
  32  */
  33 template <typename T>
  34 class SmallSet {
  35     private:
  36         /// The elements in this set
  37         std::vector<T> _elements;
  38
  39     public:
  40         /// Default constructor (construct an empty set)
  41         SmallSet() : _elements() {}
  42
  43         /// Construct a set with one element
  44         SmallSet( const T &t ) : _elements() {
  45             _elements.push_back( t );
  46         }
  47
  48         /// Construct a set with two elements
  49         SmallSet( const T &t1, const T &t2 ) {
  50             if( t1 < t2 ) {
  51                 _elements.push_back( t1 );
  52                 _elements.push_back( t2 );
  53             } else if( t2 < t1 ) {
  54                 _elements.push_back( t2 );
  55                 _elements.push_back( t1 );
  56             } else
  57                 _elements.push_back( t1 );
  58         }
  59
  60         /// Construct a SmallSet from a range of elements.
  61         /** \tparam TIterator Iterates over instances of type T.
  62          *  \param begin Points to first element to be added.
  63          *  \param end Points just beyond last element to be added.
  64          *  \param sizeHint For efficiency, the number of elements can be speficied by sizeHint.
  65          */
  66         template <typename TIterator>
  67         SmallSet( TIterator begin, TIterator end, size_t sizeHint=0 ) {
  68             _elements.reserve( sizeHint );
  69             _elements.insert( _elements.begin(), begin, end );
  70             std::sort( _elements.begin(), _elements.end() );
  71             typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
  72             _elements.erase( new_end, _elements.end() );
  73         }
  74
  75         /// Set-minus operator: returns all elements in *this, except those in x
  76         SmallSet operator/ ( const SmallSet& x ) const {
  77             SmallSet res;
  78             std::set_difference( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
  79             return res;
  80         }
  81
  82         /// Set-union operator: returns all elements in *this, plus those in x
  83         SmallSet operator| ( const SmallSet& x ) const {
  84             SmallSet res;
  85             std::set_union( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
  86             return res;
  87         }
  88
  89         /// Set-intersection operator: returns all elements in *this that are also contained in x
  90         SmallSet operator& ( const SmallSet& x ) const {
  91             SmallSet res;
  92             std::set_intersection( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
  93             return res;
  94         }
  95
  96         /// Erases from *this all elements in x
  97         SmallSet& operator/= ( const SmallSet& x ) {
  98             return (*this = (*this / x));
  99         }
 100
 101         /// Erases one element
 102         SmallSet& operator/= ( const T &t ) {
 103             typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
 104             if( pos != _elements.end() )
 105                 if( *pos == t ) // found element, delete it
 106                     _elements.erase( pos );
 107             return *this;
 108         }
 109
 110         /// Adds to *this all elements in x
 111         SmallSet& operator|= ( const SmallSet& x ) {
 112             return( *this = (*this | x) );
 113         }
 114
 115         /// Adds one element
 116         SmallSet& operator|= ( const T& t ) {
 117             typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
 118             if( pos == _elements.end() || *pos != t ) // insert it
 119                 _elements.insert( pos, t );
 120             return *this;
 121         }
 122
 123         /// Erases from *this all elements not in x
 124         SmallSet& operator&= ( const SmallSet& x ) {
 125             return (*this = (*this & x));
 126         }
 127
 128         /// Returns true if *this is a subset of x
 129         bool operator<< ( const SmallSet& x ) const {
 130             return std::includes( x._elements.begin(), x._elements.end(), _elements.begin(), _elements.end() );
 131         }
 132
 133         /// Returns true if x is a subset of *this
 134         bool operator>> ( const SmallSet& x ) const {
 135             return std::includes( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end() );
 136         }
 137
 138         /// Returns true if *this and x have elements in common
 139         bool intersects( const SmallSet& x ) const {
 140             return( (*this & x).size() > 0 );
 141         }
 142
 143         /// Returns true if *this contains the element t
 144         bool contains( const T &t ) const {
 145             return std::binary_search( _elements.begin(), _elements.end(), t );
 146         }
 147
 148         /// Constant iterator over the elements
 149         typedef typename std::vector<T>::const_iterator const_iterator;
 150         /// Iterator over the elements
 151         typedef typename std::vector<T>::iterator iterator;
 152         /// Constant reverse iterator over the elements
 153         typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
 154         /// Reverse iterator over the elements
 155         typedef typename std::vector<T>::reverse_iterator reverse_iterator;
 156
 157         /// Returns iterator that points to the first element
 158         iterator begin() { return _elements.begin(); }
 159         /// Returns constant iterator that points to the first element
 160         const_iterator begin() const { return _elements.begin(); }
 161
 162         /// Returns iterator that points beyond the last element
 163         iterator end() { return _elements.end(); }
 164         /// Returns constant iterator that points beyond the last element
 165         const_iterator end() const { return _elements.end(); }
 166
 167         /// Returns reverse iterator that points to the last element
 168         reverse_iterator rbegin() { return _elements.rbegin(); }
 169         /// Returns constant reverse iterator that points to the last element
 170         const_reverse_iterator rbegin() const { return _elements.rbegin(); }
 171
 172         /// Returns reverse iterator that points beyond the first element
 173         reverse_iterator rend() { return _elements.rend(); }
 174         /// Returns constant reverse iterator that points beyond the first element
 175         const_reverse_iterator rend() const { return _elements.rend(); }
 176
 177         /// Returns number of elements
 178         typename std::vector<T>::size_type size() const { return _elements.size(); }
 179
 180         /// Returns whether the SmallSet is empty
 181         bool empty() const { return _elements.size() == 0; }
 182
 183         /// Returns true if a and b are identical
 184         friend bool operator==( const SmallSet &a, const SmallSet &b ) {
 185             return (a._elements == b._elements);
 186         }
 187
 188         /// Returns true if a and b are not identical
 189         friend bool operator!=( const SmallSet &a, const SmallSet &b ) {
 190             return !(a._elements == b._elements);
 191         }
 192
 193         /// Lexicographical comparison of elements
 194         friend bool operator<( const SmallSet &a, const SmallSet &b ) {
 195             return a._elements < b._elements;
 196         }
 197 };
 198
 199
 200 } // end of namespace dai
 201
 202
 203 #endif