include/dai/smallset.h

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
   4  *
   5  *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
   6  */
   7
   8
   9 /// \file
  10 /// \brief Defines the SmallSet<> class, which represents a set (optimized for a small number of elements).
  11
  12
  13 #ifndef __defined_libdai_smallset_h
  14 #define __defined_libdai_smallset_h
  15
  16
  17 #include <vector>
  18 #include <algorithm>
  19 #include <iostream>
  20
  21
  22 namespace dai {
  23
  24
  25 /// Represents a set; the implementation is optimized for a small number of elements.
  26 /** SmallSet uses an ordered <tt>std::vector<</tt><em>T</em><tt>></tt> to represent a set; this is faster than
  27  *  using a <tt>std::set<</tt><em>T</em><tt>></tt> if the number of elements is small.
  28  *  \tparam T Should be less-than-comparable.
  29  */
  30 template <typename T>
  31 class SmallSet {
  32     private:
  33         /// The elements in this set
  34         std::vector<T> _elements;
  35
  36     public:
  37     /// \name Constructors and destructors
  38     //@{
  39         /// Default constructor (constructs an empty set)
  40         SmallSet() : _elements() {}
  41
  42         /// Construct a set consisting of one element
  43         SmallSet( const T &t ) : _elements() {
  44             _elements.push_back( t );
  45         }
  46
  47         /// Construct a set consisting of two elements
  48         SmallSet( const T &t1, const T &t2 ) {
  49             if( t1 < t2 ) {
  50                 _elements.push_back( t1 );
  51                 _elements.push_back( t2 );
  52             } else if( t2 < t1 ) {
  53                 _elements.push_back( t2 );
  54                 _elements.push_back( t1 );
  55             } else
  56                 _elements.push_back( t1 );
  57         }
  58
  59         /// Construct a SmallSet from a range of elements.
  60         /** \tparam TIterator Iterates over instances of type \a T.
  61          *  \param begin Points to first element to be added.
  62          *  \param end Points just beyond last element to be added.
  63          *  \param sizeHint For efficiency, the number of elements can be speficied by \a sizeHint.
  64          *  \note The \a sizeHint parameter used to be optional in libDAI versions 0.2.4 and earlier.
  65          */
  66         template <typename TIterator>
  67         SmallSet( TIterator begin, TIterator end, size_t sizeHint ) {
  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
  76     /// \name Operators for set-theoretic operations
  77     //@{
  78         /// Inserts \a t into \c *this
  79         SmallSet& insert( const T& t ) {
  80             typename SmallSet<T>::iterator it = std::lower_bound( _elements.begin(), _elements.end(), t );
  81             if( (it == _elements.end()) || (*it != t) )
  82                 _elements.insert( it, t );
  83             return *this;
  84         }
  85
  86         /// Erases \a t from \c *this
  87         SmallSet& erase( const T& t ) {
  88             return (*this /= t);
  89         }
  90
  91         /// Set-minus operator: returns all elements in \c *this, except those in \a x
  92         SmallSet operator/ ( const SmallSet& x ) const {
  93             SmallSet res;
  94             std::set_difference( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
  95             return res;
  96         }
  97
  98         /// Set-union operator: returns all elements in \c *this, plus those in \a x
  99         SmallSet operator| ( const SmallSet& x ) const {
 100             SmallSet res;
 101             std::set_union( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
 102             return res;
 103         }
 104
 105         /// Set-intersection operator: returns all elements in \c *this that are also contained in \a x
 106         SmallSet operator& ( const SmallSet& x ) const {
 107             SmallSet res;
 108             std::set_intersection( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
 109             return res;
 110         }
 111
 112         /// Erases from \c *this all elements in \a x
 113         SmallSet& operator/= ( const SmallSet& x ) {
 114             return (*this = (*this / x));
 115         }
 116
 117         /// Erases one element
 118         SmallSet& operator/= ( const T &t ) {
 119             typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
 120             if( pos != _elements.end() )
 121                 if( *pos == t ) // found element, delete it
 122                     _elements.erase( pos );
 123             return *this;
 124         }
 125
 126         /// Adds to \c *this all elements in \a x
 127         SmallSet& operator|= ( const SmallSet& x ) {
 128             return( *this = (*this | x) );
 129         }
 130
 131         /// Adds one element
 132         SmallSet& operator|= ( const T& t ) {
 133             typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
 134             if( pos == _elements.end() || *pos != t ) // insert it
 135                 _elements.insert( pos, t );
 136             return *this;
 137         }
 138
 139         /// Erases from \c *this all elements not in \a x
 140         SmallSet& operator&= ( const SmallSet& x ) {
 141             return (*this = (*this & x));
 142         }
 143
 144         /// Returns \c true if \c *this is a subset of \a x
 145         bool operator<< ( const SmallSet& x ) const {
 146             return std::includes( x._elements.begin(), x._elements.end(), _elements.begin(), _elements.end() );
 147         }
 148
 149         /// Returns \c true if \a x is a subset of \c *this
 150         bool operator>> ( const SmallSet& x ) const {
 151             return std::includes( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end() );
 152         }
 153     //@}
 154
 155     /// \name Queries
 156     //@{
 157         /// Returns \c true if \c *this and \a x have elements in common
 158         bool intersects( const SmallSet& x ) const {
 159             return( (*this & x).size() > 0 );
 160         }
 161
 162         /// Returns \c true if \c *this contains the element \a t
 163         bool contains( const T &t ) const {
 164             return std::binary_search( _elements.begin(), _elements.end(), t );
 165         }
 166
 167         /// Returns number of elements
 168         typename std::vector<T>::size_type size() const { return _elements.size(); }
 169
 170         /// Returns whether \c *this is empty
 171         bool empty() const { return _elements.size() == 0; }
 172
 173         /// Returns reference to the elements
 174         std::vector<T>& elements() { return _elements; }
 175
 176         /// Returns constant reference to the elements
 177         const std::vector<T>& elements() const { return _elements; }
 178     //@}
 179
 180         /// Constant iterator over the elements
 181         typedef typename std::vector<T>::const_iterator const_iterator;
 182         /// Iterator over the elements
 183         typedef typename std::vector<T>::iterator iterator;
 184         /// Constant reverse iterator over the elements
 185         typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
 186         /// Reverse iterator over the elements
 187         typedef typename std::vector<T>::reverse_iterator reverse_iterator;
 188
 189     /// \name Iterator interface
 190     //@{
 191         /// Returns iterator that points to the first element
 192         iterator begin() { return _elements.begin(); }
 193         /// Returns constant iterator that points to the first element
 194         const_iterator begin() const { return _elements.begin(); }
 195
 196         /// Returns iterator that points beyond the last element
 197         iterator end() { return _elements.end(); }
 198         /// Returns constant iterator that points beyond the last element
 199         const_iterator end() const { return _elements.end(); }
 200
 201         /// Returns reverse iterator that points to the last element
 202         reverse_iterator rbegin() { return _elements.rbegin(); }
 203         /// Returns constant reverse iterator that points to the last element
 204         const_reverse_iterator rbegin() const { return _elements.rbegin(); }
 205
 206         /// Returns reverse iterator that points beyond the first element
 207         reverse_iterator rend() { return _elements.rend(); }
 208         /// Returns constant reverse iterator that points beyond the first element
 209         const_reverse_iterator rend() const { return _elements.rend(); }
 210
 211         /// Returns reference to first element
 212         T& front() { return _elements.front(); }
 213         /// Returns constant reference to first element
 214         const T& front() const { return _elements.front(); }
 215
 216         /// Returns reference to last element
 217         T& back() { return _elements.back(); }
 218         /// Returns constant reference to last element
 219         const T& back() const { return _elements.back(); }
 220     //@}
 221
 222     /// \name Comparison operators
 223     //@{
 224         /// Returns \c true if \a a and \a b are identical
 225         friend bool operator==( const SmallSet &a, const SmallSet &b ) {
 226             return (a._elements == b._elements);
 227         }
 228
 229         /// Returns \c true if \a a and \a b are not identical
 230         friend bool operator!=( const SmallSet &a, const SmallSet &b ) {
 231             return !(a._elements == b._elements);
 232         }
 233
 234         /// Lexicographical comparison of elements
 235         friend bool operator<( const SmallSet &a, const SmallSet &b ) {
 236             return a._elements < b._elements;
 237         }
 238     //@}
 239
 240     /// \name Streaming input/output
 241     //@{
 242         /// Writes a SmallSet to an output stream
 243         friend std::ostream& operator << ( std::ostream& os, const SmallSet& x ) {
 244             os << "{";
 245             for( typename std::vector<T>::const_iterator it = x.begin(); it != x.end(); it++ )
 246                 os << (it != x.begin() ? ", " : "") << *it;
 247             os << "}";
 248             return os;
 249         }
 250     //@}
 251 };
 252
 253
 254 } // end of namespace dai
 255
 256
 257 #endif