vtf-logo

IntSetSparse.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00008 #if !defined(__ads_IntSetSparse_h__)
00009 #define __ads_IntSetSparse_h__
00010 
00011 #if defined(DEBUG_ads) && !defined(DEBUG_IntSetSparse)
00012 #define DEBUG_IntSetSparse
00013 #endif
00014 
00015 #include "../defs.h"
00016 
00017 #include "../algorithm/is_sorted.h"
00018 
00019 #include <algorithm>
00020 #include <iosfwd>
00021 #include <iterator>
00022 #include <set>
00023 
00024 #include <cassert>
00025 
00026 BEGIN_NAMESPACE_ADS
00027 
00029 template <typename T = int>
00030 class IntSetSparse :
00031   public std::set<T> {
00032   //
00033   // Private types.
00034   //
00035 
00036 private:
00037 
00039   typedef std::set<T> base_type;
00040 
00041   //
00042   // Public types.
00043   //
00044 
00045 public:
00046 
00048   typedef typename base_type::iterator iterator;
00050   typedef typename base_type::const_iterator const_iterator;
00052   typedef typename base_type::value_type value_type;
00054   typedef int size_type;
00055 
00056   //
00057   // Data
00058   //
00059 
00060 private:
00061 
00062   // Upper bound on the elements.
00063   size_type _ub;
00064 
00065 public:
00066 
00067   //--------------------------------------------------------------------------
00069   // @{
00070 
00072   IntSetSparse() :
00073     base_type(),
00074     _ub(0)
00075   {}
00076 
00078   IntSetSparse(const value_type upper_bound) :
00079     base_type(),
00080     _ub(upper_bound)
00081   {}
00082 
00084   template <typename IntInIter>
00085   IntSetSparse(IntInIter start, IntInIter finish, 
00086                 const value_type upper_bound) :
00087     base_type(start, finish),
00088     _ub(upper_bound)
00089   {}
00090 
00092   IntSetSparse(const IntSetSparse& x) :
00093     base_type(x),
00094     _ub(x._ub)
00095   {}
00096 
00098   IntSetSparse& 
00099   operator=(const IntSetSparse& x) {
00100     if (this != &x) {
00101       base_type::operator=(x);
00102       _ub = x._ub;
00103     }
00104     return *this;
00105   }
00106   
00108   ~IntSetSparse()
00109   {}
00110 
00111   // @}
00112   //--------------------------------------------------------------------------
00114   // @{
00115 
00117   value_type
00118   upper_bound() const {
00119     return _ub;
00120   }
00121 
00123   size_type
00124   size() const {
00125     return base_type::size();
00126   }
00127 
00129   bool 
00130   empty() const { 
00131     return base_type::empty();
00132   }
00133 
00135   const_iterator 
00136   begin() const { 
00137     return base_type::begin();
00138   }
00139 
00141   const_iterator 
00142   end() const { 
00143     return base_type::end();
00144   }
00145 
00147   bool
00148   is_in(const value_type x) const {
00149     return base_type::count(x);
00150   }
00151 
00153   bool
00154   subset(const IntSetSparse& x) const {
00155     return std::includes(begin(), end(), x.begin(), x.end());
00156   }
00157 
00159 
00162   bool
00163   is_valid() const {
00164     // Check that the elements are in the proper range.
00165     for (const_iterator i = begin(); i != end(); ++i) {
00166       if (*i < 0 || *i >= upper_bound()) {
00167         return false;
00168       }
00169     }
00170     return true;
00171   }
00172 
00173   // @}
00174   //--------------------------------------------------------------------------
00176   // @{
00177 
00179   iterator 
00180   begin() { 
00181     return base_type::begin();
00182   }
00183 
00185   iterator 
00186   end() { 
00187     return base_type::end();
00188   }
00189 
00191   void
00192   set_upper_bound(const value_type upper_bound) {
00193     _ub = upper_bound;
00194   }
00195 
00197   std::pair<iterator,bool>
00198   insert(const value_type x) {
00199 #ifdef DEBUG_IntSetSparse
00200     assert(0 <= x && x < upper_bound());
00201 #endif
00202     return base_type::insert(x);
00203   }
00204 
00206   iterator
00207   insert(const iterator position, const value_type x) {
00208 #ifdef DEBUG_IntSetSparse
00209     assert(0 <= x && x < upper_bound());
00210 #endif
00211     return base_type::insert(position, x);
00212   }
00213 
00215 
00218   template <typename IntInIter>
00219   void
00220   insert(IntInIter start, IntInIter finish) {
00221     base_type::insert(start, finish);
00222   }
00223 
00225   std::insert_iterator<IntSetSparse>
00226   inserter() {
00227     return std::inserter(*this, end());
00228   }
00229 
00231   void
00232   erase(const iterator i) {
00233     base_type::erase(i);
00234   }
00235 
00237   /* 
00238      Return true if the element was in the set.
00239   */
00240   bool
00241   erase(const value_type x) {
00242     return base_type::erase(x);
00243   }
00244 
00246   void
00247   clear() {
00248     base_type::clear();
00249   }
00250 
00252   void
00253   swap(IntSetSparse& x) {
00254     base_type::swap(x);
00255     std::swap(_ub, x._ub);
00256   }
00257 
00258   // @}
00259   //--------------------------------------------------------------------------
00261 
00262 
00264   bool
00265   operator==(const IntSetSparse<T>& x) const {
00266     return (upper_bound() == x.upper_bound() && 
00267              static_cast<const base_type&>(*this) == 
00268              static_cast<const base_type&>(x));
00269   }
00270 
00272   bool
00273   operator!=(const IntSetSparse& x) const {
00274     return ! operator==(x);
00275   }
00276 
00277   // @}
00278   //--------------------------------------------------------------------------
00280 
00281 
00283   void
00284   put(std::ostream& out) const {
00285     out << _ub;
00286     for (const iterator i = begin(); i != end(); ++i) {
00287       out << *i << "\n";
00288     }
00289   }
00290 
00292 };
00293 
00294 //
00295 // File output.
00296 //
00297 
00299 
00302 template <typename T>
00303 inline
00304 std::ostream&
00305 operator<<(std::ostream& out, const IntSetSparse<T>& x) {
00306   x.put(out);
00307   return out;
00308 }
00309 
00310 //
00311 // Set operations.
00312 //
00313 
00315 
00318 template <typename T>
00319 inline
00320 void
00321 set_union(const IntSetSparse<T>& a, const IntSetSparse<T>& b, 
00322            IntSetSparse<T>& c) {
00323   assert(a.upper_bound() <= c.upper_bound() && 
00324           b.upper_bound() <= c.upper_bound());
00325   c.clear();
00326   std::set_union(a.begin(), a.end(), b.begin(), b.end(), 
00327                   std::inserter(c, c.end()));
00328 }
00329 
00331 
00334 template <typename T>
00335 inline
00336 void
00337 set_intersection(const IntSetSparse<T>& a, const IntSetSparse<T>& b, 
00338                   IntSetSparse<T>& c) {
00339   assert(a.upper_bound() <= c.upper_bound() && 
00340           b.upper_bound() <= c.upper_bound());
00341   c.clear();
00342   std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), 
00343                          std::inserter(c, c.end()));
00344 }
00345 
00347 
00350 template <typename T>
00351 inline
00352 void
00353 set_difference(const IntSetSparse<T>& a, const IntSetSparse<T>& b, 
00354                 IntSetSparse<T>& c) {
00355   assert(a.upper_bound() <= c.upper_bound());
00356   c.clear();
00357   std::set_difference(a.begin(), a.end(), b.begin(), b.end(), 
00358                        std::inserter(c, c.end()));
00359 }
00360 
00362 
00365 template <typename T>
00366 inline
00367 void
00368 set_complement(const IntSetSparse<T>& a, IntSetSparse<T>& b) {
00369   assert(a.upper_bound() == b.upper_bound());
00370 #ifdef DEBUG_IntSetSparse
00371   assert(a.is_valid());
00372 #endif
00373     
00374   b.clear();
00375   typename IntSetSparse<T>::const_iterator i = a.begin();
00376   // Loop over all integers in the range.
00377   for (int n = 0; n != a.upper_bound(); ++n) {
00378     // If the element is in the set.
00379     if (i != a.end() && *i == n) {
00380       // Skip the element.
00381       ++i;
00382     }
00383     // If the element is not in the set.
00384     else {
00385       // Add it to b.
00386       b.insert(b.end(), n);
00387     }
00388   }
00389   assert(i == a.end());
00390 }
00391 
00392 END_NAMESPACE_ADS
00393 
00394 #endif

Generated on Fri Aug 24 12:55:26 2007 for Algorithms and Data Structures Package by  doxygen 1.4.7