toolbox/dynArray.hh

Go to the documentation of this file.

/* dynamic array
 */

#ifndef dynarray_hh
#define dynarray_hh

#include "basics/outputOperator.hh"
#include "basics/exceptions.hh"
#include "basics/typedefs.hh"
#include "basics/debug.hh"

// debugging
#define DynArrayPageConstr_D 0
#define DynArrayDestr_D 0
#define DynArrayIndex_D 0

namespace concepts {

  // ********************************************************** DynArrayBase **

  class DynArrayBase : public OutputOperator {
  public:
    DynArrayBase(const uint htblsz, const uint htblmsk,
     const uint pgsz, const uint pgmsk,
     const bool init = false);
    DynArrayBase(const DynArrayBase& base);
    virtual ~DynArrayBase();

    uint max() const { return max_; }

    uint min() const { return min_; }
  protected:
    bool init_;
    bool empty_;
    uint max_;
    uint min_;
    uint npg_;
 
    const uint htblsz_;

    const uint htblmsk_;

    const uint pgsz_;
    const uint pgmsk_;

    void operator=(DynArrayBase&) {
      throw conceptsException(ExceptionBase());
    }

    virtual std::ostream& info(std::ostream& os) const;
  };

  // ********************************************************** DynArrayPage **

  template <class T>
  class DynArrayPage {
    DynArrayPage* lnk_;
    uint idx_;
    uint sz_;
    T* mem_;
  public:
    DynArrayPage(uint idx, uint sz, DynArrayPage* lnk = 0) :
      lnk_(lnk), idx_(idx), sz_(sz), mem_(new T[sz]) {
      DEBUGL(DynArrayPageConstr_D, "done.");
    }
    DynArrayPage(const DynArrayPage& pg) :
      lnk_(0), idx_(pg.idx_), sz_(pg.sz_), mem_(new T[sz_]) {
      std::memcpy(mem_, pg.mem_, sz_*sizeof(T));
      if (pg.lnk_)
  lnk_ = new DynArrayPage<T>(*pg.lnk_);
    }
    ~DynArrayPage() { delete[] mem_; }

    T& operator[](uint i) { return mem_[i]; }

    uint index() const { return idx_; }
    DynArrayPage* link() const { return lnk_; }
  };

  // ************************************************************** DynArray **

  template <class T>
  class DynArray : public DynArrayBase {
  public:
    inline DynArray(uint htblsz = 2, uint pgsz = 2);
    inline DynArray(uint htblsz, uint pgsz, const T& dflt);
    inline DynArray(const DynArray& d);
    inline ~DynArray();

    T& operator [](uint i);

    const T& operator [](uint i) const;

    bool isElm(uint i);
    const bool isElm(uint i) const;

    inline float memory() const; 

    void reset();                
  protected:
    virtual std::ostream& info(std::ostream& os) const;
  private:
    DynArrayPage<T>** htbl_;
    DynArrayPage<T>*  lru_;
    T dflt_;
  };

  template<class T> 
  DynArray<T>::DynArray(uint htblsz, uint pgsz) :
    DynArrayBase(htblsz, (1 << htblsz) - 1, pgsz, (1 << pgsz) - 1, false),
    htbl_(new DynArrayPage<T>*[htblmsk_ + 1]), lru_(0) {
    for(uint i = htblmsk_ + 1; i--;)
      htbl_[i] = 0;
  }

  template<class T> 
  DynArray<T>::DynArray(uint htblsz, uint pgsz, const T& dflt) : 
    DynArrayBase(htblsz, (1 << htblsz) - 1, pgsz, (1 << pgsz) - 1, true),
    htbl_(new DynArrayPage<T>*[htblmsk_ + 1]), lru_(0), dflt_(dflt) {
    for(uint i = htblmsk_ + 1; i--;)
      htbl_[i] = 0; 
  }

  template <class T>
  DynArray<T>::DynArray(const DynArray<T>& d)
    : DynArrayBase(d), htbl_(new DynArrayPage<T>*[htblmsk_ + 1]),
      lru_(0), dflt_(d.dflt_) {
    for(uint i = d.htblmsk_ + 1; i--;)
      if (d.htbl_[i])
  htbl_[i] = new DynArrayPage<T>(*d.htbl_[i]);
  }

  template <class T> 
  DynArray<T>::~DynArray() {
    DEBUGL(DynArrayDestr_D, "start.");
    for(uint i = htblmsk_ + 1; i--;) {
      DynArrayPage<T>* pg = htbl_[i];
      while (pg != NULL) {
  DynArrayPage<T>* foo = pg; pg = pg->link();
  delete foo;
      }
    }
    delete[] htbl_;
    DEBUGL(DynArrayDestr_D, "done.");
  }

  template <class T> 
  T& DynArray<T>::operator[](uint i) {
    DEBUGL(DynArrayIndex_D, "i = " << i);

    if (!(i < max_))
      max_ = i + 1;
    if (lru_ == NULL || i < min_)
      min_ = i;

    uint pgidx = i >> pgsz_;

    if (lru_ != NULL && lru_->index() == pgidx)
      return (*lru_)[i & pgmsk_];

    DynArrayPage<T>** htbl = htbl_ + (pgidx & htblmsk_);

    DynArrayPage<T>* pg = *htbl;
    while(pg != 0) {
      if (pg->index() == pgidx) 
  return (*(lru_ = pg))[i & pgmsk_];
      pg = pg->link();
    }

    *htbl = pg = new DynArrayPage<T>(pgidx, pgmsk_ + 1, *htbl);
    npg_++;
    if (init_)
      for(uint j = pgmsk_ + 1; j--;)
  (*pg)[j] = dflt_;

    return (*(lru_ = pg))[i & pgmsk_];
  }

  template <class T> 
  const T& DynArray<T>::operator[](uint i) const {

    if (!(i < max_)) {
      DEBUGL(DynArrayIndex_D, *this);
      DEBUGL(DynArrayIndex_D, "i = " << i);
      throw conceptsException(IndexNotExisting());
    }
    if (lru_ == NULL || i < min_) {
      DEBUGL(DynArrayIndex_D, *this);
      DEBUGL(DynArrayIndex_D, "i = " << i);
      throw conceptsException(IndexNotExisting());
    }

    uint pgidx = i >> pgsz_;

    if (lru_ != NULL && lru_->index() == pgidx)
      return (*lru_)[i & pgmsk_];

    DynArrayPage<T>** htbl = htbl_ + (pgidx & htblmsk_);

    DynArrayPage<T>* pg = *htbl;
    while(pg != 0) {
      if (pg->index() == pgidx) 
  return (*pg)[i & pgmsk_];
      pg = pg->link();
    }
    DEBUGL(DynArrayIndex_D, *this);
    DEBUGL(DynArrayIndex_D, "i = " << i);
    throw conceptsException(IndexNotExisting());
  }

  template <class T> 
  bool DynArray<T>::isElm(uint i) {

    if (!(i < max_))  return 0;
    if (lru_ == 0 || i < min_)  return 0;

    uint pgidx = i >> pgsz_;

    if (lru_ != 0 && lru_->index() == pgidx)
      return (init_) ? ((*lru_)[i & pgmsk_] != dflt_) : 1;

    DynArrayPage<T>** htbl = htbl_ + (pgidx & htblmsk_);

    DynArrayPage<T>* pg = *htbl;
    while(pg != 0) {
      if (pg->index() == pgidx) {
        lru_ = pg;
  return (init_) ? ((*lru_)[i & pgmsk_] != dflt_) : 1;
      }
      pg = pg->link();
    }
    return 0;
  }

  template <class T> 
  const bool DynArray<T>::isElm(uint i) const {

    if (!(i < max_))  return 0;
    if (lru_ == 0 || i < min_)  return 0;

    uint pgidx = i >> pgsz_;

    DynArrayPage<T>* lru = lru_;

    if (lru != 0 && lru->index() == pgidx)
      return (init_) ? (&(*lru)[i & pgmsk_] != &dflt_) : 1;

    DynArrayPage<T>** htbl = htbl_ + (pgidx & htblmsk_);

    DynArrayPage<T>* pg = *htbl;
    while(pg != 0) {
      if (pg->index() == pgidx) {
        lru = pg;
  return (init_) ? ((*lru)[i & pgmsk_] != dflt_) : 1;
      }
      pg = pg->link();
    }
    return 0;
  }

  template <class T> 
  inline float DynArray<T>::memory() const {
    return sizeof(DynArray) + (float)(1 << htblsz_) * 
      sizeof(DynArrayPage<T>*) + (float)npg_ *
      (sizeof(DynArrayPage<T>) + (float)(1 << pgsz_) * sizeof(T));
  }

  template <class T>
  void DynArray<T>::reset() {
    for(uint i = htblmsk_ + 1; i--;) {
      DynArrayPage<T>* pg = htbl_[i]; 
      while (pg != NULL) {
  DynArrayPage<T>* foo = pg;
  pg = pg->link();
  delete foo;
      }
      htbl_[i] = NULL;
    }
    lru_ = NULL; max_ = min_ = 0; npg_ = 0;
  }

  template <class T>
  std::ostream& DynArray<T>::info(std::ostream& os) const {
    os << "DynArray(init = " << init_ << ", emtpy = " << empty_
       << ", min = " << min_ << ", max = " << max_ << ", npg = "
       << npg_ << ", htblsz = " << htblsz_ << ", htblmsk = "
       << htblmsk_ << ", pgsz = " << pgsz_ << ", pgmsk = " << pgmsk_
       << ", [" << std::endl;
    for(uint i = htblmsk_ + 1; i--;) {
      DynArrayPage<T>* pg = htbl_[i]; 
      while (pg != NULL) {
  uint pgidx = pg->index();
  os << pgidx << " | ";
  for (uint j = 0; j <= pgmsk_; ++j)
    os << '(' << (pgidx << pgsz_) + j << ", " << (*pg)[j] << "), ";
  pg = pg->link();
  os << std::endl;
      }
    }
    os << "])";
    return os;
  }

} // namespace concepts

#endif // dynarray_hh