IntSetSparse.h

Go to the documentation of this file.

// -*- C++ -*-

#if !defined(__ads_IntSetSparse_h__)
#define __ads_IntSetSparse_h__

#if defined(DEBUG_ads) && !defined(DEBUG_IntSetSparse)
#define DEBUG_IntSetSparse
#endif

#include "../defs.h"

#include "../algorithm/is_sorted.h"

#include <algorithm>
#include <iosfwd>
#include <iterator>
#include <set>

#include <cassert>

BEGIN_NAMESPACE_ADS

template <typename T = int>
class IntSetSparse :
  public std::set<T> {
  //
  // Private types.
  //

private:

  typedef std::set<T> base_type;

  //
  // Public types.
  //

public:

  typedef typename base_type::iterator iterator;
  typedef typename base_type::const_iterator const_iterator;
  typedef typename base_type::value_type value_type;
  typedef int size_type;

  //
  // Data
  //

private:

  // Upper bound on the elements.
  size_type _ub;

public:

  //--------------------------------------------------------------------------
  // @{

  IntSetSparse() :
    base_type(),
    _ub(0)
  {}

  IntSetSparse(const value_type upper_bound) :
    base_type(),
    _ub(upper_bound)
  {}

  template <typename IntInIter>
  IntSetSparse(IntInIter start, IntInIter finish, 
                const value_type upper_bound) :
    base_type(start, finish),
    _ub(upper_bound)
  {}

  IntSetSparse(const IntSetSparse& x) :
    base_type(x),
    _ub(x._ub)
  {}

  IntSetSparse& 
  operator=(const IntSetSparse& x) {
    if (this != &x) {
      base_type::operator=(x);
      _ub = x._ub;
    }
    return *this;
  }
  
  ~IntSetSparse()
  {}

  // @}
  //--------------------------------------------------------------------------
  // @{

  value_type
  upper_bound() const {
    return _ub;
  }

  size_type
  size() const {
    return base_type::size();
  }

  bool 
  empty() const { 
    return base_type::empty();
  }

  const_iterator 
  begin() const { 
    return base_type::begin();
  }

  const_iterator 
  end() const { 
    return base_type::end();
  }

  bool
  is_in(const value_type x) const {
    return base_type::count(x);
  }

  bool
  subset(const IntSetSparse& x) const {
    return std::includes(begin(), end(), x.begin(), x.end());
  }


  bool
  is_valid() const {
    // Check that the elements are in the proper range.
    for (const_iterator i = begin(); i != end(); ++i) {
      if (*i < 0 || *i >= upper_bound()) {
        return false;
      }
    }
    return true;
  }

  // @}
  //--------------------------------------------------------------------------
  // @{

  iterator 
  begin() { 
    return base_type::begin();
  }

  iterator 
  end() { 
    return base_type::end();
  }

  void
  set_upper_bound(const value_type upper_bound) {
    _ub = upper_bound;
  }

  std::pair<iterator,bool>
  insert(const value_type x) {
#ifdef DEBUG_IntSetSparse
    assert(0 <= x && x < upper_bound());
#endif
    return base_type::insert(x);
  }

  iterator
  insert(const iterator position, const value_type x) {
#ifdef DEBUG_IntSetSparse
    assert(0 <= x && x < upper_bound());
#endif
    return base_type::insert(position, x);
  }


  template <typename IntInIter>
  void
  insert(IntInIter start, IntInIter finish) {
    base_type::insert(start, finish);
  }

  std::insert_iterator<IntSetSparse>
  inserter() {
    return std::inserter(*this, end());
  }

  void
  erase(const iterator i) {
    base_type::erase(i);
  }

  /* 
     Return true if the element was in the set.
  */
  bool
  erase(const value_type x) {
    return base_type::erase(x);
  }

  void
  clear() {
    base_type::clear();
  }

  void
  swap(IntSetSparse& x) {
    base_type::swap(x);
    std::swap(_ub, x._ub);
  }

  // @}
  //--------------------------------------------------------------------------


  bool
  operator==(const IntSetSparse<T>& x) const {
    return (upper_bound() == x.upper_bound() && 
             static_cast<const base_type&>(*this) == 
             static_cast<const base_type&>(x));
  }

  bool
  operator!=(const IntSetSparse& x) const {
    return ! operator==(x);
  }

  // @}
  //--------------------------------------------------------------------------


  void
  put(std::ostream& out) const {
    out << _ub;
    for (const iterator i = begin(); i != end(); ++i) {
      out << *i << "\n";
    }
  }

};

//
// File output.
//


template <typename T>
inline
std::ostream&
operator<<(std::ostream& out, const IntSetSparse<T>& x) {
  x.put(out);
  return out;
}

//
// Set operations.
//


template <typename T>
inline
void
set_union(const IntSetSparse<T>& a, const IntSetSparse<T>& b, 
           IntSetSparse<T>& c) {
  assert(a.upper_bound() <= c.upper_bound() && 
          b.upper_bound() <= c.upper_bound());
  c.clear();
  std::set_union(a.begin(), a.end(), b.begin(), b.end(), 
                  std::inserter(c, c.end()));
}


template <typename T>
inline
void
set_intersection(const IntSetSparse<T>& a, const IntSetSparse<T>& b, 
                  IntSetSparse<T>& c) {
  assert(a.upper_bound() <= c.upper_bound() && 
          b.upper_bound() <= c.upper_bound());
  c.clear();
  std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), 
                         std::inserter(c, c.end()));
}


template <typename T>
inline
void
set_difference(const IntSetSparse<T>& a, const IntSetSparse<T>& b, 
                IntSetSparse<T>& c) {
  assert(a.upper_bound() <= c.upper_bound());
  c.clear();
  std::set_difference(a.begin(), a.end(), b.begin(), b.end(), 
                       std::inserter(c, c.end()));
}


template <typename T>
inline
void
set_complement(const IntSetSparse<T>& a, IntSetSparse<T>& b) {
  assert(a.upper_bound() == b.upper_bound());
#ifdef DEBUG_IntSetSparse
  assert(a.is_valid());
#endif
    
  b.clear();
  typename IntSetSparse<T>::const_iterator i = a.begin();
  // Loop over all integers in the range.
  for (int n = 0; n != a.upper_bound(); ++n) {
    // If the element is in the set.
    if (i != a.end() && *i == n) {
      // Skip the element.
      ++i;
    }
    // If the element is not in the set.
    else {
      // Add it to b.
      b.insert(b.end(), n);
    }
  }
  assert(i == a.end());
}

END_NAMESPACE_ADS

#endif

---