fei_ctg_set.hpp

#ifndef _fei_ctg_set_hpp_
#define _fei_ctg_set_hpp_

/*--------------------------------------------------------------------*/
/*    Copyright 2006 Sandia Corporation.                              */
/*    Under the terms of Contract DE-AC04-94AL85000, there is a       */
/*    non-exclusive license for use of this work by or on behalf      */
/*    of the U.S. Government.  Export of this program may require     */
/*    a license from the United States Government.                    */
/*--------------------------------------------------------------------*/

#include <fei_macros.hpp>
#include <fei_iostream.hpp>

#include <cstring>
#include <vector>
#include <fei_ArrayUtils.hpp>

namespace fei {

const int Set_end_val = -99999999;

template<typename T>
class ctg_set {
  public:
  ctg_set(int alloc_incr=32)
    : dataptr_(0), len_(0), highwatermark_(0), alloc_incr_(alloc_incr) {}

  ctg_set(const ctg_set<T>& src)
    : dataptr_(0), len_(0),
      highwatermark_(src.highwatermark_), alloc_incr_(src.alloc_incr_)
    {
      if (highwatermark_>0) {
        expand_dataptr(highwatermark_);
        len_ = src.len_;
        for(int i=0; i<len_; ++i) dataptr_[i] = src.dataptr_[i];
      }
    }

  virtual ~ctg_set(){clear();}

  typedef T key_type;

  class const_iterator {
  public:
    const_iterator() : set_(0),
      val_(Set_end_val), limit_(Set_end_val), i_(0) {}

    const_iterator(const ctg_set<T>* _set,
       const T& val,
       int i)
      : set_(_set),
      val_(val), limit_(Set_end_val), i_(i)
      {
  if (set_ != 0) {
    if (set_->len_ > 0) {
      limit_ = set_->dataptr_[i+1]-1;
    }
  }
      }

    const_iterator(const const_iterator& src)
      : set_(src.set_),
       val_(src.val_), limit_(src.limit_), i_(src.i_) {}

    virtual ~const_iterator(){}

    const T& operator*() const { return(val_); }

    const_iterator& operator++()
      {
  if (val_ < limit_) {
    ++val_;
  }
  else {
    if (i_ < set_->len_-2) {
      i_ += 2;
      val_ = set_->dataptr_[i_];
      limit_ = set_->dataptr_[i_+1]-1;
    }
    else {
      val_ = Set_end_val;
      limit_ = Set_end_val;
    }
  }
  return(*this);
      }

    const_iterator& operator=(const const_iterator& src)
      {
  set_ = src.set_;
  i_ = src.i_;
  val_ = src.val_;
  limit_ = src.limit_;
  return(*this);
      }

    bool operator==(const const_iterator& rhs)
      {
  return(val_ == rhs.val_);
      }

    bool operator!=(const const_iterator& rhs)
      {
  return(val_ != rhs.val_);
      }

  private:
    const ctg_set<T>* set_;
    T val_;
    T limit_;
    int i_;
  };

  const_iterator begin() const
    {
      T val = Set_end_val;
      if (len_>0) {
  val = dataptr_[0];
      }
      return(const_iterator(this, val, 0));
    }

  static const_iterator end() { return(const_iterator(0, Set_end_val, 0)); }

  ctg_set<T>& operator=(const ctg_set<T>& src)
    {
      highwatermark_ = src.highwatermark_;
      expand_dataptr(highwatermark_);
      len_ = src.len_;

      return(*this);
    }

  bool operator!=(const ctg_set<T>& rhs)
  {
    if (len_ != rhs.len_) {
      return(true);
    }

    for(int i=0; i<len_; ++i) {
      if (dataptr_[i] != rhs.dataptr_[i]) {
        return(true);
      }
    }

    return(false);
  }

  int clear()
  {
    delete [] dataptr_;
    dataptr_ = 0;
    len_ = 0;
    highwatermark_ = 0;
    return(0);
  }

  std::pair<const_iterator,bool> insert(const T& item)
  {
    if (len_ > highwatermark_) {
      FEI_COUT << "error"<<FEI_ENDL;
    }
    if (len_ < 1) {
      highwatermark_ = alloc_incr_;
      expand_dataptr(highwatermark_);
      dataptr_[0] = item;
      dataptr_[1] = item+1;
      len_ = 2;
      return(std::pair<const_iterator,bool>(const_iterator(this, item, 0),true));
    }

    int insertPoint = fei::lowerBound(item, dataptr_, len_);

    if (insertPoint < len_) {

      //dataptr_[insertPoint] is the first entry in dataptr_ that is not
      //less than item.
      //The possibilities are:
      //
      //1. dataptr_[insertPoint] equals item, so:
      //
      //     if (insertPoint is an even number) {
      //       return since item is present
      //     }
      //     else {
      //       expand the range below item to include item
      //       (by incrementing dataptr_[insertPoint])
      //       check whether dataptr_[insertPoint] == dataptr_[insertPoint+1]
      //       if so, merge the range at insertPoint-1 with the
      //       range at insertPoint+1
      //       return
      //     }
      //
      //2. dataptr_[insertPoint] is greater than item, so:
      //
      //     if (insertPoint is an even number) {
      //       if (item == dataptr_[insertPoint]-1) {
      //         expand the range at insertPoint to include item, by
      //         simply decrementing dataptr_[insertPoint]
      //       }
      //       else {
      //         insert a new range at insertPoint
      //       }
      //     }
      //     else {
      //       return since item is already present in the range at
      //       dataptr_[insertPoint-1]
      //     }
      //

      if (dataptr_[insertPoint] == item) {
  if (insertPoint%2 == 0) {
    //insertPoint is an even number, so return since item is present
    return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),false));
  }

  //Since insertPoint is an odd number, item lies just outside an existing
  //range so we simply need to add item to the range by incrementing
  //dataptr_[insertPoint].
  ++dataptr_[insertPoint];

  //now check whether this newly expanded range should be merged
  //with the range above it
  if (insertPoint < len_-1) {
    if (dataptr_[insertPoint] == dataptr_[insertPoint+1]) {
      dataptr_[insertPoint] = dataptr_[insertPoint+2];
      len_ -= 2;
      int nmove=len_-insertPoint-1;
      if (nmove > 0) {
        T* dest = dataptr_+insertPoint+1;
        T* src =  dest+2;
        std::memmove(dest, src, nmove*sizeof(T));
      }
    }
  }

  return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint-1),true));
      }
      else {
  //dataptr_[insertPoint] is greater than item.

  if (insertPoint%2 == 0) {
    if (item == dataptr_[insertPoint]-1) {
      --dataptr_[insertPoint];
      return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
    }
    else {
      //insert a new range at insertPoint
      int nmove = len_-insertPoint;
      if (len_+2 > highwatermark_) {
        highwatermark_ += alloc_incr_;
        expand_dataptr(highwatermark_);
      }
      len_ += 2;
      if (nmove > 0) {
        T* dest = dataptr_+insertPoint+2;
        T* src = dest - 2;
        std::memmove(dest, src, nmove*sizeof(T));
      }
      dataptr_[insertPoint] = item;
      dataptr_[insertPoint+1] = item+1;

      return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
    }
  }
  else {
    return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint-1),false));
  }
      }
    }

    //If we get to here, insertPoint >= len_, meaning we need to append
    //a new range.
    if (len_+2 > highwatermark_) {
      highwatermark_ += alloc_incr_;
      expand_dataptr(highwatermark_);
    }
    len_ += 2;
    dataptr_[insertPoint] = item;
    dataptr_[insertPoint+1] = item+1;

    return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
  }

  void insert2(const T& item)
  {
    if (len_ < 1) {
      highwatermark_ = alloc_incr_;
      expand_dataptr(highwatermark_);
      dataptr_[0] = item;
      dataptr_[1] = item+1;
      len_ = 2;
      return;
    }

    int insertPoint = fei::lowerBound(item, dataptr_, len_);

    if (insertPoint < len_) {

      //dataptr_[insertPoint] is the first entry in dataptr_ that is not
      //less than item.
      //The possibilities are:
      //
      //1. insertPoint is an even number:
      //   dataptr_[insertPoint] is the start of an existing range.
      //   diff = dataptr_[insertPoint] - item;
      //   switch(diff) {
      //    case 0 : //  item in range, so return
      //    case 1 : //  item just below range, so expand range and return
      //    default: //  insert new range for item
      //   }
      //
      //2. insertPoint is an odd number:
      //   dataptr_[insertPoint] is the end of an existing range
      //   diff = dataptr_[insertPoint] - item;
      //   switch(diff) {
      //    case 0 : {
      //      // item just above range, so expand range
      //      // check whether range should be merged with range above
      //    }
      //    default: // item in range, so return
      //   }
      //

      if (insertPoint%2==0) {
        switch(dataptr_[insertPoint]-item) {
          case 0: break; //item in range
          case 1: {//expand range downwards
            --dataptr_[insertPoint];
            break;
          }
          default: {// insert new range for item
            //insert a new range at insertPoint
            int nmove = len_-insertPoint;
            if (len_+2 > highwatermark_) {
              highwatermark_ += alloc_incr_;
              expand_dataptr(highwatermark_);
            }
            len_ += 2;

            T* dest = dataptr_+insertPoint+2;
            T* src = dest - 2;
            std::memmove(dest, src, nmove*sizeof(T));

            dataptr_[insertPoint] = item;
            dataptr_[insertPoint+1] = item+1;
          }
        }
      }
      else {//insertPoint is odd number
        if (dataptr_[insertPoint] == item) {
          // item just above range, so expand range
          ++dataptr_[insertPoint];

          // check whether range should be merged with range above
          if (insertPoint < len_-1 &&
              dataptr_[insertPoint] == dataptr_[insertPoint+1]) {
            dataptr_[insertPoint] = dataptr_[insertPoint+2];
            len_ -= 2;
            int nmove=len_-insertPoint-1;
            if (nmove > 0) {
              T* dest = dataptr_+insertPoint+1;
              T* src =  dest+2;
              std::memmove(dest, src, nmove*sizeof(T));
            }
          }
        }//end if (dataptr_[insertPoint]==item)...
        //     else do nothing, item is already in existing range
      }

      return;
    } // end if (insertPoint < len_)...

    //If we get to here, insertPoint >= len_, meaning we need to append
    //a new range.
    if (len_+2 > highwatermark_) {
      highwatermark_ += alloc_incr_;
      expand_dataptr(highwatermark_);
    }
    dataptr_[insertPoint] = item;
    dataptr_[insertPoint+1] = item+1;
    len_ += 2;
  }

  int insert2_dense_group(const T& starting_index, int group_size)
    {
      for(int i=0; i<group_size; ++i) {
  insert2(starting_index+i);
      }

      return(0);
    }

  const_iterator find(const T& item)
    {
      if (len_ < 1) {
  return(const_iterator(0, Set_end_val, 0));
      }

      int insertPoint = -1;
      int index = fei::binarySearch(item, dataptr_, len_, insertPoint);

      if (index < 0) {
  if (insertPoint%2==0) {
    return(end());
  }
  else {
    return(const_iterator(this, item, insertPoint-1));
  }
      }

      if (index%2==0) {
  return( const_iterator(this, item, index) );
      }

      return(const_iterator(0, Set_end_val, 0));
    }

  int copy_to_array(int len, T* items) const
    {
      const_iterator iter = begin(), iter_end = end();
      int offset = 0;
      for(; iter != iter_end; ++iter) {
  if (offset >= len) {
    break;
  }

  items[offset++] = *iter;
      }

      return(0);
    }

  int copy_to_vector(std::vector<T>& items) const
    {
      int sz = size();
      items.resize(sz);
      T* itemsPtr = &(items[0]);
      return(copy_to_array(sz, itemsPtr));
    }

  int size() const
    {
      int setsize = 0;
      int offset = 0;
      while(offset<(len_-1)) {
  setsize += dataptr_[offset+1]-dataptr_[offset];
  offset += 2;
      }

      return(setsize);
    }

 private:
  void expand_dataptr(int newlen)
  {
    //on entry to this function, dataptr_ has length 'len_'.
    //we assume newlen is greater than len_.
    //after we create newptr with length 'newlen', we copy
    //len_ positions from dataptr_ to newptr.

    T* newptr = new T[newlen];
    for(int i=0; i<len_; ++i) newptr[i] = dataptr_[i];
    delete [] dataptr_;
    dataptr_ = newptr;
  }

  friend class const_iterator;
  T* dataptr_;
  int len_;
  int highwatermark_;
  int alloc_incr_;
};//class ctg_set

}//namespace fei

#endif