SparseArray2D.hh

/* This file is part of the BIAS library (Basic ImageAlgorithmS).

   Copyright (C) 2003-2009    (see file CONTACT for details)
   Multimediale Systeme der Informationsverarbeitung
   Institut fuer Informatik
   Christian-Albrechts-Universitaet Kiel
   
   
   BIAS is free software; you can redistribute it and/or modify
   it under the terms of the GNU Lesser General Public License as published by
   the Free Software Foundation; either version 2.1 of the License, or
   (at your option) any later version.
   
   BIAS is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU Lesser General Public License for more details.
   
   You should have received a copy of the GNU Lesser General Public License
   along with BIAS; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA*/
#ifndef __SparseArray2D_hh__
#define __SparseArray2D_hh__

#include <bias_config.h>

#include <Base/Debug/Exception.hh>
#include <Base/Debug/Error.hh>

#include <map>

namespace BIAS {
  
  template <class T> class SparseArray2D;

  template <class T>
  std::ostream& operator<<(std::ostream& os, const SparseArray2D<T> &t);

  /** @class SparseArray2D
   *  @test tested with TestSparseArray2D.cpp
      @brief generic two dimensional psarsly populated rectangular array 
      holding arbitrary data types

      The syntax of the access functions is kept similar to the stl::classes
      
      @author woelk 11/2007 (c) www.vision-n.de */
  template <class T>  
  class SparseArray2D
  {
  public:
    SparseArray2D();

    SparseArray2D(const unsigned nrows, const unsigned ncols);

    // copy constructor
    SparseArray2D(const SparseArray2D<T>& m);

    ~SparseArray2D();

    /// copy operator
    SparseArray2D<T>& operator=(const SparseArray2D<T>& m);

    /// frees the memory
    void clear();

    /// preserves the content
    void resize(const unsigned  nrows, const unsigned ncols);

    bool empty() const 
    { return (Data_.empty() && Nrows_==0 && Ncols_==0); }

    unsigned ncols() const { return Ncols_; }

    unsigned nrows() const { return Nrows_; }

    unsigned size() const { return Nrows_ * Ncols_; }

    unsigned num_entries() const { return Data_.size(); }

    bool is_valid(const unsigned row, const unsigned col) const;

    void erase(const unsigned row, const unsigned col);

    /// checked element access
    T&       operator()(const unsigned row, const unsigned col);
    const T& operator()(const unsigned row, const unsigned col) const;

    class const_iterator;

    /// for iterator access
    /// todo: derive from std::iterator class(es)
    class iterator  
    {
    public:
      inline iterator() : Val_() {}
      inline iterator(const iterator& it) : Val_(it.Val_) {}
      inline ~iterator() {}
      inline T& operator*() { return Val_->second; }
      inline T* operator->() { return &Val_->second; }
      inline long long unsigned first() const 
      { return Val_->first; }
      inline iterator operator++(int) { Val_++; return *this; }
      inline bool operator==(const iterator& it) { return (Val_ == it.Val_); }
      inline bool operator!=(const iterator& it) { return (Val_ != it.Val_); }
      inline iterator& operator=(const iterator& it) 
      { Val_ = it.Val_; return *this; }

      friend class SparseArray2D;
      friend class const_iterator;
    private:
      typename std::map<long long unsigned, T>::iterator Val_;
      inline iterator(const typename std::map<long long unsigned, T>::iterator it) : Val_(it) {}
    };


    /// for const_iterator access
    /// todo: derive from std::iterator class(es)
    class const_iterator
    {
    public:
      inline const_iterator() : Val_() {}
      inline const_iterator(const const_iterator& it) : Val_(it.Val_) {}
      inline const_iterator(const iterator& it) : Val_(it.Val_) {}
      inline ~const_iterator() {}
      inline const T& operator*() { return Val_->second; }
      inline const T* operator->() { return &Val_->second; }
      inline long long unsigned first() const 
      { return Val_->first; }
      inline const_iterator operator++(int) { Val_++; return *this; }
      inline bool operator==(const const_iterator& it) 
      { return (Val_ == it.Val_); }
      inline bool operator!=(const const_iterator& it) 
      { return (Val_ != it.Val_); }
      inline const_iterator& operator=(const const_iterator& it) 
      { Val_ = it.Val_; return *this; }

      friend class SparseArray2D;
    private:
      typename std::map<long long unsigned, T>::const_iterator Val_;
    };

    const_iterator begin() const { 
      const_iterator it;
      it.Val_ = Data_.begin();
      return it;
    }
    const_iterator end() const { 
      const_iterator it;
      it.Val_ = Data_.end();
      return it;
    }
    iterator begin() { return (iterator) Data_.begin(); }
    iterator end() { return (iterator) Data_.end(); }
     
    inline void position(const const_iterator &it, unsigned &row, 
                         unsigned &col) const
    { Map2Indices_(it.first(), row, col); } 
    inline void position(const iterator &it, unsigned &row, unsigned &col) const
    { Map2Indices_(it.first(), row, col); } 

    friend std::ostream& operator<<<T>(std::ostream& os,
                                       const SparseArray2D<T> &t);

  protected:
    std::map<long long unsigned, T> Data_;
    unsigned Nrows_, Ncols_;

    inline long long unsigned Indices2Map_(const unsigned row, 
                                          const unsigned col) const
    { return (long long unsigned)row * (long long unsigned)Ncols_ + 
        (long long unsigned)col; }

    inline void Map2Indices_(const long long unsigned& map,
                            unsigned& row, unsigned & col) const
    { row = (unsigned)(map / (long long unsigned)Ncols_); 
      col = (unsigned)(map % (long long unsigned)Ncols_); }


  };

  /////////////////////////////////////////////////////////////////
  // implementation
  /////////////////////////////////////////////////////////////////

  template <class T>
  SparseArray2D<T>::SparseArray2D()
    : Data_(), Nrows_(0), Ncols_(0)
  {}


  template <class T>
  SparseArray2D<T>::SparseArray2D(const unsigned nrows, const unsigned ncols)
    : Data_(), Nrows_(nrows), Ncols_(ncols)
  {
    if (nrows == 0 || ncols == 0)
      BEXCEPTION("invalid size in Arra2D "<<nrows<<"x"<<ncols);
  }


  template <class T>
  SparseArray2D<T>::SparseArray2D(const SparseArray2D<T>& m)
    : Data_(), Nrows_(0), Ncols_(0)
  { *this = m; }


  template <class T>
  SparseArray2D<T>::~SparseArray2D()
  { /*std::cout <<"destructor ~SparseArray2D()\n"; */ clear(); }


  template<class T>
  SparseArray2D<T>& SparseArray2D<T>::operator=(const SparseArray2D<T>& m)
  {
    // this indirection is necessary to be able to cope with self assignement
    std::map<long long unsigned, T> tmp = m.Data_;
    Data_ = tmp;
    Nrows_ = m.Nrows_;
    Ncols_ = m.Ncols_;
    return *this;
  }


  template<class T>
  void SparseArray2D<T>::clear()
  { Data_.clear(); Ncols_ = Nrows_ = 0; }


  template<class T>
  void SparseArray2D<T>::resize(const unsigned nrows, const unsigned ncols)
  { 
    std::map<long long unsigned, T> tmp;
    unsigned col, row;
    typename std::map<long long unsigned, T>::const_iterator it;
    for (it = Data_.begin(); it!=Data_.end(); it++){
      Map2Indices_(it->first, row, col);
      tmp[(long long unsigned)row * (long long unsigned)ncols + 
          (long long unsigned)col] = it->second;
    }
    Data_ = tmp;
    Nrows_ = nrows;
    Ncols_ = ncols;
  }


  template<class T>
  bool SparseArray2D<T>::is_valid(const unsigned row, const unsigned col) const
  {
    if (row >= Nrows_ || col >= Ncols_) return false;
    if (Data_.find(Indices2Map_(row, col)) == Data_.end()) return false;
    return true;
  }


  template<class T>
  void SparseArray2D<T>::erase(const unsigned row, const unsigned col)
  {
    BIASASSERT(row < Nrows_ && col < Ncols_);
    typename std::map<long long unsigned, T>::iterator it;
    it = Data_.find(Indices2Map_(row, col));
    if (it == Data_.end()) return;
    Data_.erase(it);
  }


  template<class T>
  T& SparseArray2D<T>::operator()(const unsigned row, const unsigned col)
  {
    if (row >= Nrows_ || col >= Ncols_) 
      BEXCEPTION("index out of bounds: array2D size = "<<Ncols_<<"x"<<Nrows_
                 <<"  and index access at ["<<row<<"]["<<col<<"]");
    return Data_[Indices2Map_(row, col)];
  }


  template<class T>
  const T& SparseArray2D<T>::operator()(const unsigned row, const unsigned col) const
  {
    if (row >= Nrows_ || col >= Ncols_) 
      BEXCEPTION("index out of bounds: array2D size = "<<Ncols_<<"x"<<Nrows_
                 <<"  and index access at ["<<row<<"]["<<col<<"]");
    typename std::map<long long unsigned, T>::const_iterator it;
    if ((it=Data_.find(Indices2Map_(row, col)))==Data_.end())
      BEXCEPTION("matrix is empty at ["<<row<<"]["<<col<<"]");
    return it->second;
  }


  template <class T>
  std::ostream& operator<<(std::ostream& os, const SparseArray2D<T> &a)
  {
    typename SparseArray2D<T>::const_iterator it;
    unsigned col, row, last_row=0 ;
    for (it=a.begin(); it!=a.end(); it++){
      a.position(it, row, col);
      if (row!=last_row){
        last_row = row; 
        os << std::endl;
      }
      os << "a["<<row<<"]["<<col<<"]="<<*it<<" ";
    }
    //os << std::endl;
    return os;
  }


} // namespace

#endif