IndexSet.h

/* Copyright (C) 2012-2020 IBM Corp.
 * This program is Licensed under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at
 *   http://www.apache.org/licenses/LICENSE-2.0
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License. See accompanying LICENSE file.
 */
#ifndef HELIB_INDEXSET_H
#define HELIB_INDEXSET_H
 
#include <helib/NumbTh.h>
 
namespace helib {
 
class IndexSet
{
 
  std::vector<bool> rep;
  // NOTE: modern versions of C++ are supposed
  // to implement this efficiently as a "specialized template class".
  // Older versions of C++ define the equivalent class bit_std::vector.
 
  long _first, _last, _card;
 
  // Invariant: if _card == 0, then _first = 0, _last = -1;
  // otherwise, _first (resp. _last) is the lowest (resp. highest)
  // index in the set.
  // In any case, the std::vector rep always defines the characteristic
  // function of the set.
 
  // private helper function
  void intervalConstructor(long low, long high);
 
public:
  /*** constructors ***/
 
  // @brief No-argument constructor, creates empty set
  IndexSet() : _first(0), _last(-1), _card(0) {}
 
  // @brief Constructs an interval, low to high
  IndexSet(long low, long high) { intervalConstructor(low, high); }
 
  // @brief Constructs a singleton set
  explicit IndexSet(long j) { intervalConstructor(j, j); }
 
  // copy constructor: use the built-in copy constructor
 
  /*** assignment ***/
 
  // assignment: use the built-in assignment operator
 
  long first() const { return _first; }
 
  long last() const { return _last; }
 
  long next(long j) const;
 
  // @brief Returns the previous element before j, if any; otherwise j-1
  long prev(long j) const;
 
  long card() const { return _card; }
 
  bool contains(long j) const;
 
  bool contains(const IndexSet& s) const;
 
  bool disjointFrom(const IndexSet& s) const;
 
  /*** comparison ***/
 
  bool operator==(const IndexSet& s) const;
 
  bool operator!=(const IndexSet& s) const { return !(*this == s); }
 
  /*** update methods ***/
 
  void clear();
 
  void insert(long j);
 
  void remove(long j);
 
  void insert(const IndexSet& s);
 
  void remove(const IndexSet& s);
 
  void retain(const IndexSet& s);
 
  static const IndexSet& emptySet();
 
  bool isInterval() const { return (_card == (1 + _last - _first)); }
 
  /*** raw IO ***/
  void read(std::istream& str);
  void write(std::ostream& str) const;
 
  /*** code to allow one to write "for (long i: set)" ***/
 
  class iterator
  {
    friend class IndexSet;
 
  public:
    long operator*() const { return i_; }
    iterator& operator++()
    {
      i_ = s_.next(i_);
      return *this;
    }
 
    bool operator==(const iterator& other) const
    {
      return &s_ == &other.s_ && i_ == other.i_;
    }
 
    bool operator!=(const iterator& other) const { return !(*this == other); }
 
  protected:
    iterator(const IndexSet& s, long i) : s_(s), i_(i) {}
 
  private:
    const IndexSet& s_;
    long i_;
  };
 
  iterator begin() const { return iterator(*this, this->first()); }
  iterator end() const { return iterator(*this, this->last() + 1); }
};
 
// some high-level convenience methods...not very efficient...
// not sure if we really need these
 
IndexSet operator|(const IndexSet& s, const IndexSet& t);
 
IndexSet operator&(const IndexSet& s, const IndexSet& t);
 
IndexSet operator^(const IndexSet& s, const IndexSet& t);
 
IndexSet operator/(const IndexSet& s, const IndexSet& t);
 
// I/O operator
std::ostream& operator<<(std::ostream& str, const IndexSet& set);
std::istream& operator>>(std::istream& str, IndexSet& set);
 
long card(const IndexSet& s);
 
inline bool empty(const IndexSet& s) { return s.card() == 0; }
 
bool operator<=(const IndexSet& s1, const IndexSet& s2);
 
bool operator<(const IndexSet& s1, const IndexSet& s2);
 
bool operator>=(const IndexSet& s1, const IndexSet& s2);
 
bool operator>(const IndexSet& s1, const IndexSet& s2);
 
inline bool disjoint(const IndexSet& s1, const IndexSet& s2)
{
  return s1.disjointFrom(s2);
}
 
} // namespace helib
 
#endif // ifndef HELIB_INDEXSET_H