Basic Image AlgorithmS Library 2.8.0

SparseArray2D.hh

00001 /* This file is part of the BIAS library (Basic ImageAlgorithmS).
00002 
00003    Copyright (C) 2003-2009    (see file CONTACT for details)
00004    Multimediale Systeme der Informationsverarbeitung
00005    Institut fuer Informatik
00006    Christian-Albrechts-Universitaet Kiel
00007    
00008    
00009    BIAS is free software; you can redistribute it and/or modify
00010    it under the terms of the GNU Lesser General Public License as published by
00011    the Free Software Foundation; either version 2.1 of the License, or
00012    (at your option) any later version.
00013    
00014    BIAS is distributed in the hope that it will be useful,
00015    but WITHOUT ANY WARRANTY; without even the implied warranty of
00016    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00017    GNU Lesser General Public License for more details.
00018    
00019    You should have received a copy of the GNU Lesser General Public License
00020    along with BIAS; if not, write to the Free Software
00021    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA*/
00022 #ifndef __SparseArray2D_hh__
00023 #define __SparseArray2D_hh__
00024 
00025 #include <bias_config.h>
00026 
00027 #include <Base/Debug/Exception.hh>
00028 #include <Base/Debug/Error.hh>
00029 
00030 #include <map>
00031 
00032 namespace BIAS {
00033   
00034   template <class T> class SparseArray2D;
00035 
00036   template <class T>
00037   std::ostream& operator<<(std::ostream& os, const SparseArray2D<T> &t);
00038 
00039   /** @class SparseArray2D
00040    *  @test tested with TestSparseArray2D.cpp
00041       @brief generic two dimensional psarsly populated rectangular array 
00042       holding arbitrary data types
00043 
00044       The syntax of the access functions is kept similar to the stl::classes
00045       
00046       @author woelk 11/2007 (c) www.vision-n.de */
00047   template <class T>  
00048   class SparseArray2D
00049   {
00050   public:
00051     SparseArray2D();
00052 
00053     SparseArray2D(const unsigned nrows, const unsigned ncols);
00054 
00055     // copy constructor
00056     SparseArray2D(const SparseArray2D<T>& m);
00057 
00058     ~SparseArray2D();
00059 
00060     /// copy operator
00061     SparseArray2D<T>& operator=(const SparseArray2D<T>& m);
00062 
00063     /// frees the memory
00064     void clear();
00065 
00066     /// preserves the content
00067     void resize(const unsigned  nrows, const unsigned ncols);
00068 
00069     bool empty() const 
00070     { return (Data_.empty() && Nrows_==0 && Ncols_==0); }
00071 
00072     unsigned ncols() const { return Ncols_; }
00073 
00074     unsigned nrows() const { return Nrows_; }
00075 
00076     unsigned size() const { return Nrows_ * Ncols_; }
00077 
00078     unsigned num_entries() const { return Data_.size(); }
00079 
00080     bool is_valid(const unsigned row, const unsigned col) const;
00081 
00082     void erase(const unsigned row, const unsigned col);
00083 
00084     /// checked element access
00085     T&       operator()(const unsigned row, const unsigned col);
00086     const T& operator()(const unsigned row, const unsigned col) const;
00087 
00088     class const_iterator;
00089 
00090     /// for iterator access
00091     /// todo: derive from std::iterator class(es)
00092     class iterator  
00093     {
00094     public:
00095       inline iterator() : Val_() {}
00096       inline iterator(const iterator& it) : Val_(it.Val_) {}
00097       inline ~iterator() {}
00098       inline T& operator*() { return Val_->second; }
00099       inline T* operator->() { return &Val_->second; }
00100       inline long long unsigned first() const 
00101       { return Val_->first; }
00102       inline iterator operator++(int) { Val_++; return *this; }
00103       inline bool operator==(const iterator& it) { return (Val_ == it.Val_); }
00104       inline bool operator!=(const iterator& it) { return (Val_ != it.Val_); }
00105       inline iterator& operator=(const iterator& it) 
00106       { Val_ = it.Val_; return *this; }
00107 
00108       friend class SparseArray2D;
00109       friend class const_iterator;
00110     private:
00111       typename std::map<long long unsigned, T>::iterator Val_;
00112       inline iterator(const typename std::map<long long unsigned, T>::iterator it) : Val_(it) {}
00113     };
00114 
00115 
00116     /// for const_iterator access
00117     /// todo: derive from std::iterator class(es)
00118     class const_iterator
00119     {
00120     public:
00121       inline const_iterator() : Val_() {}
00122       inline const_iterator(const const_iterator& it) : Val_(it.Val_) {}
00123       inline const_iterator(const iterator& it) : Val_(it.Val_) {}
00124       inline ~const_iterator() {}
00125       inline const T& operator*() { return Val_->second; }
00126       inline const T* operator->() { return &Val_->second; }
00127       inline long long unsigned first() const 
00128       { return Val_->first; }
00129       inline const_iterator operator++(int) { Val_++; return *this; }
00130       inline bool operator==(const const_iterator& it) 
00131       { return (Val_ == it.Val_); }
00132       inline bool operator!=(const const_iterator& it) 
00133       { return (Val_ != it.Val_); }
00134       inline const_iterator& operator=(const const_iterator& it) 
00135       { Val_ = it.Val_; return *this; }
00136 
00137       friend class SparseArray2D;
00138     private:
00139       typename std::map<long long unsigned, T>::const_iterator Val_;
00140     };
00141 
00142     const_iterator begin() const { 
00143       const_iterator it;
00144       it.Val_ = Data_.begin();
00145       return it;
00146     }
00147     const_iterator end() const { 
00148       const_iterator it;
00149       it.Val_ = Data_.end();
00150       return it;
00151     }
00152     iterator begin() { return (iterator) Data_.begin(); }
00153     iterator end() { return (iterator) Data_.end(); }
00154      
00155     inline void position(const const_iterator &it, unsigned &row, 
00156                          unsigned &col) const
00157     { Map2Indices_(it.first(), row, col); } 
00158     inline void position(const iterator &it, unsigned &row, unsigned &col) const
00159     { Map2Indices_(it.first(), row, col); } 
00160 
00161     friend std::ostream& operator<<<T>(std::ostream& os,
00162                                        const SparseArray2D<T> &t);
00163 
00164   protected:
00165     std::map<long long unsigned, T> Data_;
00166     unsigned Nrows_, Ncols_;
00167 
00168     inline long long unsigned Indices2Map_(const unsigned row, 
00169                                           const unsigned col) const
00170     { return (long long unsigned)row * (long long unsigned)Ncols_ + 
00171         (long long unsigned)col; }
00172 
00173     inline void Map2Indices_(const long long unsigned& map,
00174                             unsigned& row, unsigned & col) const
00175     { row = (unsigned)(map / (long long unsigned)Ncols_); 
00176       col = (unsigned)(map % (long long unsigned)Ncols_); }
00177 
00178 
00179   };
00180 
00181   /////////////////////////////////////////////////////////////////
00182   // implementation
00183   /////////////////////////////////////////////////////////////////
00184 
00185   template <class T>
00186   SparseArray2D<T>::SparseArray2D()
00187     : Data_(), Nrows_(0), Ncols_(0)
00188   {}
00189 
00190 
00191   template <class T>
00192   SparseArray2D<T>::SparseArray2D(const unsigned nrows, const unsigned ncols)
00193     : Data_(), Nrows_(nrows), Ncols_(ncols)
00194   {
00195     if (nrows == 0 || ncols == 0)
00196       BEXCEPTION("invalid size in Arra2D "<<nrows<<"x"<<ncols);
00197   }
00198 
00199 
00200   template <class T>
00201   SparseArray2D<T>::SparseArray2D(const SparseArray2D<T>& m)
00202     : Data_(), Nrows_(0), Ncols_(0)
00203   { *this = m; }
00204 
00205 
00206   template <class T>
00207   SparseArray2D<T>::~SparseArray2D()
00208   { /*std::cout <<"destructor ~SparseArray2D()\n"; */ clear(); }
00209 
00210 
00211   template<class T>
00212   SparseArray2D<T>& SparseArray2D<T>::operator=(const SparseArray2D<T>& m)
00213   {
00214     // this indirection is necessary to be able to cope with self assignement
00215     std::map<long long unsigned, T> tmp = m.Data_;
00216     Data_ = tmp;
00217     Nrows_ = m.Nrows_;
00218     Ncols_ = m.Ncols_;
00219     return *this;
00220   }
00221 
00222 
00223   template<class T>
00224   void SparseArray2D<T>::clear()
00225   { Data_.clear(); Ncols_ = Nrows_ = 0; }
00226 
00227 
00228   template<class T>
00229   void SparseArray2D<T>::resize(const unsigned nrows, const unsigned ncols)
00230   { 
00231     std::map<long long unsigned, T> tmp;
00232     unsigned col, row;
00233     typename std::map<long long unsigned, T>::const_iterator it;
00234     for (it = Data_.begin(); it!=Data_.end(); it++){
00235       Map2Indices_(it->first, row, col);
00236       tmp[(long long unsigned)row * (long long unsigned)ncols + 
00237           (long long unsigned)col] = it->second;
00238     }
00239     Data_ = tmp;
00240     Nrows_ = nrows;
00241     Ncols_ = ncols;
00242   }
00243 
00244 
00245   template<class T>
00246   bool SparseArray2D<T>::is_valid(const unsigned row, const unsigned col) const
00247   {
00248     if (row >= Nrows_ || col >= Ncols_) return false;
00249     if (Data_.find(Indices2Map_(row, col)) == Data_.end()) return false;
00250     return true;
00251   }
00252 
00253 
00254   template<class T>
00255   void SparseArray2D<T>::erase(const unsigned row, const unsigned col)
00256   {
00257     BIASASSERT(row < Nrows_ && col < Ncols_);
00258     typename std::map<long long unsigned, T>::iterator it;
00259     it = Data_.find(Indices2Map_(row, col));
00260     if (it == Data_.end()) return;
00261     Data_.erase(it);
00262   }
00263 
00264 
00265   template<class T>
00266   T& SparseArray2D<T>::operator()(const unsigned row, const unsigned col)
00267   {
00268     if (row >= Nrows_ || col >= Ncols_) 
00269       BEXCEPTION("index out of bounds: array2D size = "<<Ncols_<<"x"<<Nrows_
00270                  <<"  and index access at ["<<row<<"]["<<col<<"]");
00271     return Data_[Indices2Map_(row, col)];
00272   }
00273 
00274 
00275   template<class T>
00276   const T& SparseArray2D<T>::operator()(const unsigned row, const unsigned col) const
00277   {
00278     if (row >= Nrows_ || col >= Ncols_) 
00279       BEXCEPTION("index out of bounds: array2D size = "<<Ncols_<<"x"<<Nrows_
00280                  <<"  and index access at ["<<row<<"]["<<col<<"]");
00281     typename std::map<long long unsigned, T>::const_iterator it;
00282     if ((it=Data_.find(Indices2Map_(row, col)))==Data_.end())
00283       BEXCEPTION("matrix is empty at ["<<row<<"]["<<col<<"]");
00284     return it->second;
00285   }
00286 
00287 
00288   template <class T>
00289   std::ostream& operator<<(std::ostream& os, const SparseArray2D<T> &a)
00290   {
00291     typename SparseArray2D<T>::const_iterator it;
00292     unsigned col, row, last_row=0 ;
00293     for (it=a.begin(); it!=a.end(); it++){
00294       a.position(it, row, col);
00295       if (row!=last_row){
00296         last_row = row; 
00297         os << std::endl;
00298       }
00299       os << "a["<<row<<"]["<<col<<"]="<<*it<<" ";
00300     }
00301     //os << std::endl;
00302     return os;
00303   }
00304 
00305 
00306 } // namespace
00307 
00308 #endif
 All Classes Functions Variables Typedefs Enumerations Enumerator Friends