toolbox/multiArray.hh

Go to the documentation of this file.

/* multidimensional arrays based on std::map
 */

#ifndef multiarray_hh
#define multiarray_hh

#include <map>
#include "basics/outputOperator.hh"
#include "basics/exceptions.hh"
#include "basics/typedefs.hh"
#include "basics/vectorsMatrices.hh"
#include "toolbox/stiffArray.hh"
#include "toolbox/scannerConnectors.hh"
#include "basics/debug.hh"

// debugging
#define MultiIndexDestr_D 0
#define MultiArrayCommute_D 0
#define MultiArrayErase_D 0
#define MultiArrayScanner_D 0
#define MultiArrayIndex_D 0
#define MultiArrayIndexShort_D 0
// simple info
#define MultiArrayInfo 1

namespace concepts {

  // Forward Declaration
  template <uint dim, typename T>
  class MultiArray;

  // ******************************************************* MultiIndex<dim> **

  /* Class for a multidimensional index

     @author Kersten Schmidt, 2005
  */

  template<uint dim>
  class MultiIndex : public StiffArray<dim, uint> {
  public:
    MultiIndex() : StiffArray<dim, uint>() {}
    MultiIndex(const uint& dft) : StiffArray<dim, uint>(dft) {}
    MultiIndex(const uint dft[]); 

    MultiIndex(const MultiIndex<dim>& a) : StiffArray<dim, uint>(a) {}
    virtual ~MultiIndex() {
      DEBUGL(MultiIndexDestr_D, "done.");
    }

//     bool operator<(const MultiIndex<dim>& a) const;
    bool operator==(const MultiIndex<dim>& a) const;
    bool operator!=(const MultiIndex<dim>& a) const;
  protected:
    virtual std::ostream& info(std::ostream& os) const;
  };

  template<uint dim>
  MultiIndex<dim>::MultiIndex(const uint dft[]) :
    StiffArray<dim, uint>() {
    memorycpy((uint*)(*this), dft, dim);
  }

//   template<uint dim>
//   bool MultiIndex<dim>::operator<(const MultiIndex<dim>& a) const {
//     uint i = 0;
//     while(i < dim && (*this)[i] == a[i]) ++i;
//     return (i < dim && (*this)[i] < a[i]);
//   }

  template<uint dim>
  bool MultiIndex<dim>::operator==(const MultiIndex<dim>& a) const {
    uint i = 0;
    while(i < dim && (*this)[i] == a[i]) ++i;
    return (i == dim);
  }

  template<uint dim>
  bool MultiIndex<dim>::operator!=(const MultiIndex<dim>& a) const {
    return !(*this == a);
  }

  template<uint dim>
  std::ostream& MultiIndex<dim>::info(std::ostream& os) const {
    os << "MultiIndex<" << dim << ">([";
    for (uint i = 0; i < dim; ++i)
      os << (*this)[i] << ((i == dim-1) ? "" : ", ");
    return os << "])";
  }

  // ************************************************** MultiEntrance<dim,T> **

  /* Class for Entrance of multidimensional Array

     @author Kersten Schmidt, 2004
   */

  template <uint dim, typename T>
  class MultiEntrance : public OutputOperator {
  public:
    MultiEntrance(const uint i, const MultiEntrance<dim-1,T> ent) : 
      i_(i), ent_(ent) {}
    inline uint operator()(const uint j) const {
      conceptsAssert(j < dim, Assertion());
      if (j==0) return i_;
      return ent_(j-1);
    }
    inline const T& value() const { return ent_.value(); }
  protected:
    virtual std::ostream& info(std::ostream& os) const {
      os << "(" << i_;
      for(uint j=0;j < dim-1;++j)
  os << ", " << ent_(j);
      return os << ", " << ent_.value() << ")";
    }
  private:
    const uint i_;
    MultiEntrance<dim-1,T> ent_;
  };

  // **************************************************** MultiEntrance<1,T> **

  template <typename T>
  class MultiEntrance<1,T> : public OutputOperator {
  public:
    MultiEntrance(const uint i, const T& value) : i_(i), value_(value) {}
    inline uint operator()(const uint j = 0) const {
      conceptsAssert(j < 1, Assertion());
      return i_;
    }
    inline const T& value() const { return value_; }
  protected:
    virtual std::ostream& info(std::ostream& os) const {
      return os << "(" << i_ << ", " << value_ << ")";
    }
  private:
    const uint i_;
    const T value_;
  };
  
  // ***************************************************** MultiArray<dim,T> **

  template <uint dim, typename T>
  class MultiArray : public OutputOperator {
  public:
    class Scanner {
    public:
      Scanner(const MultiArray<dim,T> array) : 
        i_(array.data_.begin()), end_(array.data_.end()), j_(0) {
        DEBUGL(MultiArrayScanner_D, i_->first << ", " << i_->second);
        if (!eos()) 
          //    j_.reset(i_->second.scan());
          j_ = i_->second.scan();
        DEBUGL(MultiArrayScanner_D, i_->first << ", " << i_->second);
      }
      Scanner(const Scanner& scan) 
        : i_(scan.i_), end_(scan.end_), j_(scan.j_) {}
      virtual ~Scanner() { if (j_!=0) delete j_; }
      bool eos() const {
        DEBUGL(MultiArrayScanner_D, i_->first << ", " << i_->second);
        return i_ == end_; 
      }
      const MultiEntrance<dim,T> operator()() const {
        DEBUGL(MultiArrayScanner_D, i_->first << ", " << i_->second);
        return MultiEntrance<dim,T>(i_->first, (*j_)());
      }
      const MultiEntrance<dim,T> operator++(int) {
        DEBUGL(MultiArrayScanner_D, i_->first << ", " << i_->second);
        // avoid taking the next entrance if you are at the end
        conceptsAssert(!eos(), Assertion());
  // take first the current entrance
//  const MultiEntrance<dim,T> tmp(i_->first, (*j_)++);
//  // if the scanner of the next dimension came to the end,
//  // take next in this dimension
//  if (j_->eos()) {
//    i_++;
//    j_.reset(i_->second.scan());
//    delete j_;
//    j_ = new typename MultiArray<dim-1,T>::Scanner(i_->second);
//    typename MultiArray<dim-1, T>::Scanner* j2= i_->second.scan();
//    DEBUGL(MultiArrayScanner_D, i_->first << ", " << (*j2)() << ", " << j2 << ", " << j2->eos());
//    j_ = j2;
//    DEBUGL(MultiArrayScanner_D, i_->first << ", " << (*j_)() << ", " << j_ << ", " << j_->eos());
//  }
        const MultiEntrance<dim,T> tmp(i_++->first, (*j_)());
        DEBUGL(MultiArrayScanner_D, i_->first << ", " << i_->second << ", " << j_ << ", " << j_->eos());  
        return tmp;
      }
      Scanner* clone() const { return new Scanner(*this); }
    private:
      typename std::map<uint, MultiArray<dim-1, T> >::const_iterator i_;
      typename std::map<uint, MultiArray<dim-1, T> >::const_iterator end_;
      typename MultiArray<dim-1, T>::Scanner* j_;
//       std::auto_ptr<typename MultiArray<dim-1, T>::Scanner> j_;
    };
    MultiArray(bool commutable = false) : commutable_(commutable) {}
    ~MultiArray() { clear(); }
    T& operator [](const uint i[dim]);
    T& operator [](uint i[dim]);

    const T& operator [](const uint i[dim]) const;
    const T& operator [](uint i[dim]) const;
    Scanner* scan() const { return new Scanner(*this); }
    bool isElm(const uint i[dim]) const;
    bool isElm(uint i[dim]) const;
    void commute(uint i[dim]) const;
    void erase(const uint i[dim]);
    void erase(uint i[dim]);
    uint size() const;
    void clear();
  protected:
    virtual std::ostream& info(std::ostream& os) const;
  private:
    std::map<uint, MultiArray<dim-1, T> > data_;
    const bool commutable_;
  };

  template <uint dim, typename T>
  T& MultiArray<dim, T>::operator[](const uint i[dim]) {
    DEBUGL(MultiArrayIndex_D, *this << ", i = " << MultiIndex<dim>(i));
    DEBUGL(!MultiArrayIndex_D && MultiArrayIndexShort_D,
     "i = " << MultiIndex<dim>(i));
    uint I[dim];
    memorycpy(I, i, dim);
    return (*this)[I];
  }

  template <uint dim, typename T>
  T& MultiArray<dim, T>::operator[](uint i[dim]) {
    DEBUGL(MultiArrayIndex_D, *this << ", i = " << MultiIndex<dim>(i));
    DEBUGL(!MultiArrayIndex_D && MultiArrayIndexShort_D,
     "i = " << MultiIndex<dim>(i));
    commute(i);
    typename std::map<uint, MultiArray<dim-1, T> >::iterator j = 
      data_.find(i[0]);
    if (j == data_.end()) {
      // creating of new entrance, but no data
      std::pair
  <typename std::map<uint, MultiArray<dim-1, T> >::iterator, bool> k =
  data_.insert(std::pair<uint, MultiArray<dim-1, T> >
         (i[0], MultiArray<dim-1, T>(commutable_)));
      j = k.first;
    }
    DEBUGL(MultiArrayIndex_D, *this);
    // if new entrance was created, here the data is created
    return j->second[i+1];
  }

  template <uint dim, typename T>
  const T& MultiArray<dim, T>::operator[](const uint i[dim]) const {
    DEBUGL(MultiArrayIndex_D, *this << ", i = " << MultiIndex<dim>(i));
    DEBUGL(!MultiArrayIndex_D && MultiArrayIndexShort_D,
     "i = " << MultiIndex<dim>(i));
    uint I[dim];
    memorycpy(I, i, dim);
    return (*this)[I];
  }

  template <uint dim, typename T>
  const T& MultiArray<dim, T>::operator[](uint i[dim]) const {
    DEBUGL(MultiArrayIndex_D, *this << ", i = " << MultiIndex<dim>(i));
    DEBUGL(!MultiArrayIndex_D && MultiArrayIndexShort_D,
     "i = " << MultiIndex<dim>(i));
    commute(i);
    typename std::map<uint, MultiArray<dim-1, T> >::const_iterator j =
      data_.find(i[0]);
    if (j == data_.end()) {
      DEBUGL(MultiArrayIndex_D || MultiArrayIndexShort_D,
       "i = " << MultiIndex<dim>(i));
      throw conceptsException(IndexNotExisting());
    }
    return j->second[i+1];
  }

  template <uint dim, typename T>
  bool MultiArray<dim, T>::isElm(const uint i[dim]) const {
    uint I[dim];
    memorycpy(I, i, dim);
    return isElm(I);
  }

  template <uint dim, typename T>
  bool MultiArray<dim, T>::isElm(uint i[dim]) const {
    commute(i);
    typename std::map<uint, MultiArray<dim-1, T> >::const_iterator j = 
      data_.find(i[0]);
    if (j == data_.end())
      return false;
    else return j->second.isElm(i+1);
  }

  template <uint dim, typename T>
  void MultiArray<dim, T>::commute(uint i[dim]) const {
    if (commutable_) {
      for(uint j=1; j < dim; ++j) {
  if (i[j] < i[0]) std::swap(i[0],i[j]);
      }
      DEBUGL(MultiArrayCommute_D, MultiIndex<dim>(i));
    }
  }

  template <uint dim, typename T>
  void MultiArray<dim, T>::erase(const uint i[dim]) {
    uint I[dim];
    memorycpy(I, i, dim);
    erase(I);
  }

  template <uint dim, typename T>
  void MultiArray<dim, T>::erase(uint i[dim]) {
    commute(i);
    DEBUGL(MultiArrayErase_D, "Erase (" << Array<uint>(i,dim) << ")");
    typename std::map<uint, MultiArray<dim-1, T> >::iterator j = 
      data_.find(i[0]);
    if (j == data_.end())
      throw conceptsException(IndexNotExisting());
    DEBUGL(MultiArrayErase_D, j->second);    
    j->second.erase(i+1);
    DEBUGL(MultiArrayErase_D, j->second);
    if (j->second.size()==0)
      data_.erase(i[0]);
  }

  template <uint dim, typename T>
  uint MultiArray<dim, T>::size() const {
    uint size = 0;
    typename std::map<uint, MultiArray<dim-1, T> >::const_iterator j = 
      data_.begin();
    for(;j != data_.end();++j)
      size += j->second.size();
    return size;
  }

  template <uint dim, typename T>
  void MultiArray<dim, T>::clear() {
    typename std::map<uint, MultiArray<dim-1, T> >::iterator j = data_.begin();
    for(;j != data_.end();++j)
      j->second.clear();
    data_.clear();
  }

  template <uint dim, typename T>
  std::ostream& MultiArray<dim, T>::info(std::ostream& os) const {
    uint size = this->size();
    os << "MultiArray<" << dim << ",T>(" << size << ", ";
    if (commutable_) os << "yes";
    else os << "no";
    if (size > 0) {
      os << ",[";
      typename std::map<uint, MultiArray<dim-1, T> >::const_iterator j0 = data_.begin();
      for(;j0 != data_.end();) {
#if MultiArrayInfo
  DEBUGL(MultiArrayScanner_D,j0->first << ", " << j0->second);
  os << "(" << j0->first << ", " << j0->second << ")";
#else
  // does not function, ++-Operator doesn't work
  std::auto_ptr<Scanner> sc(scan());
  while (!sc->eos()) {
    os << (*sc)++;
    if (!sc->eos()) os << ", ";
  }
#endif
  if (++j0 != data_.end()) os << ", ";
      }
      os << "]";
    }
    return os << ")";
  }

  // ******************************************************* MultiArray<1,T> **

  template <typename T>
  class MultiArray<1,T> : public OutputOperator {
  public:
    class Scanner  {
    public:
      Scanner(const MultiArray<1,T> array) : i_(array.data_.begin()), 
               end_(array.data_.end()) {}
      Scanner(const Scanner& scan) : i_(scan.i_), end_(scan.end_) {}
      bool eos() const { return i_ == end_; }
      const MultiEntrance<1,T> operator()() const {
  return MultiEntrance<1,T>(i_->first, i_->second);
      }
      const MultiEntrance<1,T> operator++(int) {
  // avoid taking the next entrance if you are at the end
  conceptsAssert(!eos(), Assertion());
  // take the current entrance
  const MultiEntrance<1,T> tmp(i_->first, i_->second);
  i_++;
  return tmp;
      }
      Scanner* clone() const { return new Scanner(*this); }
    private:
      typename std::map<uint, T>::const_iterator i_;
      typename std::map<uint, T>::const_iterator end_;
    };
    
    MultiArray(bool commutable = false) {}
    ~MultiArray() { clear(); }
    T& operator [](const uint i[1]) { return data_[i[0]]; }
    const T& operator [](const uint i[1]) const { return (*this)[i[0]];}
    T& operator [](const uint i) { return data_[i]; }
    const T& operator [](const uint i) const;
    Scanner* scan() const { return new Scanner(*this); }
    bool isElm(const uint i[1]) const { return isElm(i[0]); }
    bool isElm(const uint i) const;
    inline void erase(const uint i[1]) { erase(i[0]); }
    inline void erase(uint i) { 
      DEBUGL(MultiArrayErase_D, "Erase (" << i << ")");
      data_.erase(i);
    }
    uint size() const { return data_.size(); }

    inline void clear() { data_.clear(); }
  protected:
    virtual std::ostream& info(std::ostream& os) const;
  private:
    std::map<uint, T> data_;
  };

  template <typename T>
  const T& MultiArray<1, T>::operator[](const uint i) const {
    typename std::map<uint, T>::const_iterator j = data_.find(i);
    if (j == data_.end())
      throw conceptsException(IndexNotExisting());
    return j->second;
  }

  template <typename T>
  bool MultiArray<1, T>::isElm(const uint i) const {
    typename std::map<uint, T>::const_iterator j = data_.find(i);
    return (j != data_.end());
  }

  template <typename T>
  std::ostream& MultiArray<1,T>::info(std::ostream& os) const {
    uint size = this->size();
    os << "MultiArray<1,T>(" << size;
    if (size > 0) {
      os << ",[";
      std::auto_ptr<Scanner> sc(scan());
      while (!sc->eos()) {
        os << (*sc)++;
        if (!sc->eos()) os << ", ";
      }
      os << "]";
    }
    return os << ")";
  }

} // namespace concepts

#endif // multiarray_hh