include/dai/smallset.h

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