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         /// Set-minus operator: returns all elements in *this, except those in x
  89         SmallSet operator/ ( const SmallSet& x ) const {
  90             SmallSet res;
  91             std::set_difference( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
  92             return res;
  93         }
  94
  95         /// Set-union operator: returns all elements in *this, plus those in x
  96         SmallSet operator| ( const SmallSet& x ) const {
  97             SmallSet res;
  98             std::set_union( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
  99             return res;
 100         }
 101
 102         /// Set-intersection operator: returns all elements in *this that are also contained in x
 103         SmallSet operator& ( const SmallSet& x ) const {
 104             SmallSet res;
 105             std::set_intersection( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
 106             return res;
 107         }
 108
 109         /// Erases from *this all elements in x
 110         SmallSet& operator/= ( const SmallSet& x ) {
 111             return (*this = (*this / x));
 112         }
 113
 114         /// Erases one element
 115         SmallSet& operator/= ( const T &t ) {
 116             typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
 117             if( pos != _elements.end() )
 118                 if( *pos == t ) // found element, delete it
 119                     _elements.erase( pos );
 120             return *this;
 121         }
 122
 123         /// Adds to *this all elements in x
 124         SmallSet& operator|= ( const SmallSet& x ) {
 125             return( *this = (*this | x) );
 126         }
 127
 128         /// Adds one element
 129         SmallSet& operator|= ( const T& t ) {
 130             typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
 131             if( pos == _elements.end() || *pos != t ) // insert it
 132                 _elements.insert( pos, t );
 133             return *this;
 134         }
 135
 136         /// Erases from *this all elements not in x
 137         SmallSet& operator&= ( const SmallSet& x ) {
 138             return (*this = (*this & x));
 139         }
 140
 141         /// Returns true if *this is a subset of x
 142         bool operator<< ( const SmallSet& x ) const {
 143             return std::includes( x._elements.begin(), x._elements.end(), _elements.begin(), _elements.end() );
 144         }
 145
 146         /// Returns true if x is a subset of *this
 147         bool operator>> ( const SmallSet& x ) const {
 148             return std::includes( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end() );
 149         }
 150
 151         /// Returns true if *this and x have elements in common
 152         bool intersects( const SmallSet& x ) const {
 153             return( (*this & x).size() > 0 );
 154         }
 155
 156         /// Returns true if *this contains the element t
 157         bool contains( const T &t ) const {
 158             return std::binary_search( _elements.begin(), _elements.end(), t );
 159         }
 160
 161         /// Constant iterator over the elements
 162         typedef typename std::vector<T>::const_iterator const_iterator;
 163         /// Iterator over the elements
 164         typedef typename std::vector<T>::iterator iterator;
 165         /// Constant reverse iterator over the elements
 166         typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
 167         /// Reverse iterator over the elements
 168         typedef typename std::vector<T>::reverse_iterator reverse_iterator;
 169
 170         /// Returns iterator that points to the first element
 171         iterator begin() { return _elements.begin(); }
 172         /// Returns constant iterator that points to the first element
 173         const_iterator begin() const { return _elements.begin(); }
 174
 175         /// Returns iterator that points beyond the last element
 176         iterator end() { return _elements.end(); }
 177         /// Returns constant iterator that points beyond the last element
 178         const_iterator end() const { return _elements.end(); }
 179
 180         /// Returns reverse iterator that points to the last element
 181         reverse_iterator rbegin() { return _elements.rbegin(); }
 182         /// Returns constant reverse iterator that points to the last element
 183         const_reverse_iterator rbegin() const { return _elements.rbegin(); }
 184
 185         /// Returns reverse iterator that points beyond the first element
 186         reverse_iterator rend() { return _elements.rend(); }
 187         /// Returns constant reverse iterator that points beyond the first element
 188         const_reverse_iterator rend() const { return _elements.rend(); }
 189
 190         /// Returns number of elements
 191         typename std::vector<T>::size_type size() const { return _elements.size(); }
 192
 193         /// Returns whether the SmallSet is empty
 194         bool empty() const { return _elements.size() == 0; }
 195
 196         /// Returns true if a and b are identical
 197         friend bool operator==( const SmallSet &a, const SmallSet &b ) {
 198             return (a._elements == b._elements);
 199         }
 200
 201         /// Returns true if a and b are not identical
 202         friend bool operator!=( const SmallSet &a, const SmallSet &b ) {
 203             return !(a._elements == b._elements);
 204         }
 205
 206         /// Lexicographical comparison of elements
 207         friend bool operator<( const SmallSet &a, const SmallSet &b ) {
 208             return a._elements < b._elements;
 209         }
 210 };
 211
 212
 213 } // end of namespace dai
 214
 215
 216 #endif