Basic Image AlgorithmS Library  2.8.0
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
SparseArray2D.hh
1 /* This file is part of the BIAS library (Basic ImageAlgorithmS).
2 
3  Copyright (C) 2003-2009 (see file CONTACT for details)
4  Multimediale Systeme der Informationsverarbeitung
5  Institut fuer Informatik
6  Christian-Albrechts-Universitaet Kiel
7 
8 
9  BIAS is free software; you can redistribute it and/or modify
10  it under the terms of the GNU Lesser General Public License as published by
11  the Free Software Foundation; either version 2.1 of the License, or
12  (at your option) any later version.
13 
14  BIAS is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  GNU Lesser General Public License for more details.
18 
19  You should have received a copy of the GNU Lesser General Public License
20  along with BIAS; if not, write to the Free Software
21  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA*/
22 #ifndef __SparseArray2D_hh__
23 #define __SparseArray2D_hh__
24 
25 #include <bias_config.h>
26 
27 #include <Base/Debug/Exception.hh>
28 #include <Base/Debug/Error.hh>
29 
30 #include <map>
31 
32 namespace BIAS {
33 
34  template <class T> class SparseArray2D;
35 
36  template <class T>
37  std::ostream& operator<<(std::ostream& os, const SparseArray2D<T> &t);
38 
39  /** @class SparseArray2D
40  * @test tested with TestSparseArray2D.cpp
41  @brief generic two dimensional psarsly populated rectangular array
42  holding arbitrary data types
43 
44  The syntax of the access functions is kept similar to the stl::classes
45 
46  @author woelk 11/2007 (c) www.vision-n.de */
47  template <class T>
48  class SparseArray2D
49  {
50  public:
51  SparseArray2D();
52 
53  SparseArray2D(const unsigned nrows, const unsigned ncols);
54 
55  // copy constructor
57 
59 
60  /// copy operator
62 
63  /// frees the memory
64  void clear();
65 
66  /// preserves the content
67  void resize(const unsigned nrows, const unsigned ncols);
68 
69  bool empty() const
70  { return (Data_.empty() && Nrows_==0 && Ncols_==0); }
71 
72  unsigned ncols() const { return Ncols_; }
73 
74  unsigned nrows() const { return Nrows_; }
75 
76  unsigned size() const { return Nrows_ * Ncols_; }
77 
78  unsigned num_entries() const { return Data_.size(); }
79 
80  bool is_valid(const unsigned row, const unsigned col) const;
81 
82  void erase(const unsigned row, const unsigned col);
83 
84  /// checked element access
85  T& operator()(const unsigned row, const unsigned col);
86  const T& operator()(const unsigned row, const unsigned col) const;
87 
88  class const_iterator;
89 
90  /// for iterator access
91  /// todo: derive from std::iterator class(es)
92  class iterator
93  {
94  public:
95  inline iterator() : Val_() {}
96  inline iterator(const iterator& it) : Val_(it.Val_) {}
97  inline ~iterator() {}
98  inline T& operator*() { return Val_->second; }
99  inline T* operator->() { return &Val_->second; }
100  inline long long unsigned first() const
101  { return Val_->first; }
102  inline iterator operator++(int) { Val_++; return *this; }
103  inline bool operator==(const iterator& it) { return (Val_ == it.Val_); }
104  inline bool operator!=(const iterator& it) { return (Val_ != it.Val_); }
105  inline iterator& operator=(const iterator& it)
106  { Val_ = it.Val_; return *this; }
107 
108  friend class SparseArray2D;
109  friend class const_iterator;
110  private:
111  typename std::map<long long unsigned, T>::iterator Val_;
112  inline iterator(const typename std::map<long long unsigned, T>::iterator it) : Val_(it) {}
113  };
114 
115 
116  /// for const_iterator access
117  /// todo: derive from std::iterator class(es)
119  {
120  public:
121  inline const_iterator() : Val_() {}
122  inline const_iterator(const const_iterator& it) : Val_(it.Val_) {}
123  inline const_iterator(const iterator& it) : Val_(it.Val_) {}
124  inline ~const_iterator() {}
125  inline const T& operator*() { return Val_->second; }
126  inline const T* operator->() { return &Val_->second; }
127  inline long long unsigned first() const
128  { return Val_->first; }
129  inline const_iterator operator++(int) { Val_++; return *this; }
130  inline bool operator==(const const_iterator& it)
131  { return (Val_ == it.Val_); }
132  inline bool operator!=(const const_iterator& it)
133  { return (Val_ != it.Val_); }
135  { Val_ = it.Val_; return *this; }
136 
137  friend class SparseArray2D;
138  private:
139  typename std::map<long long unsigned, T>::const_iterator Val_;
140  };
141 
143  const_iterator it;
144  it.Val_ = Data_.begin();
145  return it;
146  }
147  const_iterator end() const {
148  const_iterator it;
149  it.Val_ = Data_.end();
150  return it;
151  }
152  iterator begin() { return (iterator) Data_.begin(); }
153  iterator end() { return (iterator) Data_.end(); }
154 
155  inline void position(const const_iterator &it, unsigned &row,
156  unsigned &col) const
157  { Map2Indices_(it.first(), row, col); }
158  inline void position(const iterator &it, unsigned &row, unsigned &col) const
159  { Map2Indices_(it.first(), row, col); }
160 
161  friend std::ostream& operator<<<T>(std::ostream& os,
162  const SparseArray2D<T> &t);
163 
164  protected:
165  std::map<long long unsigned, T> Data_;
166  unsigned Nrows_, Ncols_;
167 
168  inline long long unsigned Indices2Map_(const unsigned row,
169  const unsigned col) const
170  { return (long long unsigned)row * (long long unsigned)Ncols_ +
171  (long long unsigned)col; }
172 
173  inline void Map2Indices_(const long long unsigned& map,
174  unsigned& row, unsigned & col) const
175  { row = (unsigned)(map / (long long unsigned)Ncols_);
176  col = (unsigned)(map % (long long unsigned)Ncols_); }
177 
178 
179  };
180 
181  /////////////////////////////////////////////////////////////////
182  // implementation
183  /////////////////////////////////////////////////////////////////
184 
185  template <class T>
187  : Data_(), Nrows_(0), Ncols_(0)
188  {}
189 
190 
191  template <class T>
192  SparseArray2D<T>::SparseArray2D(const unsigned nrows, const unsigned ncols)
193  : Data_(), Nrows_(nrows), Ncols_(ncols)
194  {
195  if (nrows == 0 || ncols == 0)
196  BEXCEPTION("invalid size in Arra2D "<<nrows<<"x"<<ncols);
197  }
198 
199 
200  template <class T>
202  : Data_(), Nrows_(0), Ncols_(0)
203  { *this = m; }
204 
205 
206  template <class T>
208  { /*std::cout <<"destructor ~SparseArray2D()\n"; */ clear(); }
209 
210 
211  template<class T>
213  {
214  // this indirection is necessary to be able to cope with self assignement
215  std::map<long long unsigned, T> tmp = m.Data_;
216  Data_ = tmp;
217  Nrows_ = m.Nrows_;
218  Ncols_ = m.Ncols_;
219  return *this;
220  }
221 
222 
223  template<class T>
225  { Data_.clear(); Ncols_ = Nrows_ = 0; }
226 
227 
228  template<class T>
229  void SparseArray2D<T>::resize(const unsigned nrows, const unsigned ncols)
230  {
231  std::map<long long unsigned, T> tmp;
232  unsigned col, row;
233  typename std::map<long long unsigned, T>::const_iterator it;
234  for (it = Data_.begin(); it!=Data_.end(); it++){
235  Map2Indices_(it->first, row, col);
236  tmp[(long long unsigned)row * (long long unsigned)ncols +
237  (long long unsigned)col] = it->second;
238  }
239  Data_ = tmp;
240  Nrows_ = nrows;
241  Ncols_ = ncols;
242  }
243 
244 
245  template<class T>
246  bool SparseArray2D<T>::is_valid(const unsigned row, const unsigned col) const
247  {
248  if (row >= Nrows_ || col >= Ncols_) return false;
249  if (Data_.find(Indices2Map_(row, col)) == Data_.end()) return false;
250  return true;
251  }
252 
253 
254  template<class T>
255  void SparseArray2D<T>::erase(const unsigned row, const unsigned col)
256  {
257  BIASASSERT(row < Nrows_ && col < Ncols_);
258  typename std::map<long long unsigned, T>::iterator it;
259  it = Data_.find(Indices2Map_(row, col));
260  if (it == Data_.end()) return;
261  Data_.erase(it);
262  }
263 
264 
265  template<class T>
266  T& SparseArray2D<T>::operator()(const unsigned row, const unsigned col)
267  {
268  if (row >= Nrows_ || col >= Ncols_)
269  BEXCEPTION("index out of bounds: array2D size = "<<Ncols_<<"x"<<Nrows_
270  <<" and index access at ["<<row<<"]["<<col<<"]");
271  return Data_[Indices2Map_(row, col)];
272  }
273 
274 
275  template<class T>
276  const T& SparseArray2D<T>::operator()(const unsigned row, const unsigned col) const
277  {
278  if (row >= Nrows_ || col >= Ncols_)
279  BEXCEPTION("index out of bounds: array2D size = "<<Ncols_<<"x"<<Nrows_
280  <<" and index access at ["<<row<<"]["<<col<<"]");
281  typename std::map<long long unsigned, T>::const_iterator it;
282  if ((it=Data_.find(Indices2Map_(row, col)))==Data_.end())
283  BEXCEPTION("matrix is empty at ["<<row<<"]["<<col<<"]");
284  return it->second;
285  }
286 
287 
288  template <class T>
289  std::ostream& operator<<(std::ostream& os, const SparseArray2D<T> &a)
290  {
292  unsigned col, row, last_row=0 ;
293  for (it=a.begin(); it!=a.end(); it++){
294  a.position(it, row, col);
295  if (row!=last_row){
296  last_row = row;
297  os << std::endl;
298  }
299  os << "a["<<row<<"]["<<col<<"]="<<*it<<" ";
300  }
301  //os << std::endl;
302  return os;
303  }
304 
305 
306 } // namespace
307 
308 #endif
void Map2Indices_(const long long unsigned &map, unsigned &row, unsigned &col) const
bool operator!=(const const_iterator &it)
const_iterator begin() const
std::map< long long unsigned, T > Data_
for iterator access todo: derive from std::iterator class(es)
void resize(const unsigned nrows, const unsigned ncols)
preserves the content
bool operator==(const iterator &it)
bool operator!=(const iterator &it)
std::map< long long unsigned, T >::iterator Val_
bool is_valid(const unsigned row, const unsigned col) const
std::map< long long unsigned, T >::const_iterator Val_
long long unsigned Indices2Map_(const unsigned row, const unsigned col) const
bool empty() const
const_iterator(const const_iterator &it)
iterator(const typename std::map< long long unsigned, T >::iterator it)
generic two dimensional psarsly populated rectangular array holding arbitrary data types ...
unsigned size() const
for const_iterator access todo: derive from std::iterator class(es)
bool operator==(const const_iterator &it)
SparseArray2D< T > & operator=(const SparseArray2D< T > &m)
copy operator
iterator(const iterator &it)
void position(const iterator &it, unsigned &row, unsigned &col) const
T & operator()(const unsigned row, const unsigned col)
checked element access
void position(const const_iterator &it, unsigned &row, unsigned &col) const
long long unsigned first() const
const_iterator & operator=(const const_iterator &it)
const_iterator end() const
long long unsigned first() const
void erase(const unsigned row, const unsigned col)
void clear()
frees the memory
unsigned num_entries() const
unsigned ncols() const
iterator & operator=(const iterator &it)
unsigned nrows() const