OpenMS  2.8.0
HashGrid.h
Go to the documentation of this file.
1 // --------------------------------------------------------------------------
2 // OpenMS -- Open-Source Mass Spectrometry
3 // --------------------------------------------------------------------------
4 // Copyright The OpenMS Team -- Eberhard Karls University Tuebingen,
5 // ETH Zurich, and Freie Universitaet Berlin 2002-2021.
6 //
7 // This software is released under a three-clause BSD license:
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
12 // documentation and/or other materials provided with the distribution.
13 // * Neither the name of any author or any participating institution
14 // may be used to endorse or promote products derived from this software
15 // without specific prior written permission.
16 // For a full list of authors, refer to the file AUTHORS.
17 // --------------------------------------------------------------------------
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 // ARE DISCLAIMED. IN NO EVENT SHALL ANY OF THE AUTHORS OR THE CONTRIBUTING
22 // INSTITUTIONS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
25 // OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
26 // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
27 // OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
28 // ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // --------------------------------------------------------------------------
31 // $Maintainer: Lars Nilse $
32 // $Authors: Bastian Blank $
33 // --------------------------------------------------------------------------
34 
35 #include <cmath>
36 #include <iterator>
37 #include <limits>
38 
39 #include <boost/array.hpp>
40 #include <boost/functional/hash.hpp>
41 #include <boost/unordered/unordered_map.hpp>
42 
43 #include <OpenMS/CONCEPT/Types.h>
45 
46 #ifndef OPENMS_COMPARISON_CLUSTERING_HASHGRID_H
47 #define OPENMS_COMPARISON_CLUSTERING_HASHGRID_H
48 
49 namespace OpenMS
50 {
61  template <typename Cluster>
62  class HashGrid
63  {
64 public:
68  // XXX: Check is there is another type handy in OpenMS already
70 
75 
79  typedef typename boost::unordered_multimap<ClusterCenter, Cluster> CellContent;
80 
84  typedef boost::unordered_map<CellIndex, CellContent> Grid;
85 
86  typedef typename CellContent::key_type key_type;
87  typedef typename CellContent::mapped_type mapped_type;
88  typedef typename CellContent::value_type value_type;
89 
90 private:
94  class Iterator :
95  public std::iterator<std::input_iterator_tag, value_type>
96  {
97 private:
98  friend class HashGrid;
99 
100  typedef typename Grid::iterator grid_iterator;
101  typedef typename CellContent::iterator cell_iterator;
102 
106 
107  // Search for next non-empty cell
109  {
110  while (cell_it_ == grid_it_->second.end())
111  {
112  grid_it_++;
113 
114  // If we are at the last cell, set cell iterator to something well-known
115  if (grid_it_ == grid_.end())
116  {
118  return;
119  }
120 
121  cell_it_ = grid_it_->second.begin();
122  }
123  }
124 
125 public:
126  explicit Iterator(Grid & grid) :
127  grid_(grid), grid_it_(grid.end())
128  {}
129 
130  Iterator(Grid & grid, grid_iterator grid_it, cell_iterator cell_it) :
131  grid_(grid), grid_it_(grid_it), cell_it_(cell_it)
132  {
133  searchNextCell_();
134  }
135 
137  {
138  ++cell_it_;
139  searchNextCell_();
140  return *this;
141  }
142 
143  const Iterator operator++(int)
144  {
145  Iterator ret(*this);
146  operator++();
147  return ret;
148  }
149 
150  bool operator==(const Iterator & rhs) const
151  { return grid_it_ == rhs.grid_it_ && cell_it_ == rhs.cell_it_; }
152 
153  bool operator!=(const Iterator & rhs) const
154  { return !(*this == rhs); }
155 
157  { return *cell_it_; }
158 
160  { return &*cell_it_; }
161 
162  const CellIndex index() const
163  {
164  return grid_it_->first;
165  }
166 
167  };
168 
173  public std::iterator<std::input_iterator_tag, const value_type>
174  {
175 private:
176  friend class HashGrid;
177 
178  typedef typename Grid::const_iterator grid_iterator;
179  typedef typename CellContent::const_iterator cell_iterator;
180 
181  const Grid & grid_;
184 
185  // Search for next non-empty cell
187  {
188  while (cell_it_ == grid_it_->second.end())
189  {
190  grid_it_++;
191 
192  // If we are at the last cell, set cell iterator to something well-known
193  if (grid_it_ == grid_.end())
194  {
196  return;
197  }
198 
199  cell_it_ = grid_it_->second.begin();
200  }
201  }
202 
203 public:
204  ConstIterator(const Grid & grid) :
205  grid_(grid), grid_it_(grid.end())
206  {}
207 
208  ConstIterator(const Grid & grid, grid_iterator grid_it, cell_iterator cell_it) :
209  grid_(grid), grid_it_(grid_it), cell_it_(cell_it)
210  {
211  searchNextCell_();
212  }
213 
214  ConstIterator(const Iterator & it) :
216  {}
217 
219  {
220  ++cell_it_;
221  searchNextCell_();
222  return *this;
223  }
224 
226  {
227  ConstIterator ret(*this);
228  operator++();
229  return ret;
230  }
231 
232  bool operator==(const ConstIterator & rhs) const
233  { return grid_it_ == rhs.grid_it_ && cell_it_ == rhs.cell_it_; }
234 
235  bool operator!=(const ConstIterator & rhs) const
236  { return !(*this == rhs); }
237 
238  const value_type & operator*() const
239  { return *cell_it_; }
240 
241  const value_type * operator->() const
242  { return &*cell_it_; }
243 
244  const CellIndex index() const
245  {
246  return grid_it_->first;
247  }
248 
249  };
250 
251 public:
254  typedef typename Grid::const_iterator const_grid_iterator;
255  typedef typename Grid::iterator grid_iterator;
256  typedef typename CellContent::const_iterator const_cell_iterator;
257  typedef typename CellContent::iterator cell_iterator;
258  typedef typename CellContent::size_type size_type;
259 
260 private:
263 
264 public:
265 
270 
275 
276 public:
277  explicit HashGrid(const ClusterCenter & c_dimension) :
278  cells_(),
279  grid_dimension_(),
280  cell_dimension(c_dimension),
282  {}
283 
290  {
291  const CellIndex cellkey = cellindexAtClustercenter_(v.first);
292  CellContent & cell = cells_[cellkey];
293  updateGridDimension_(cellkey);
294  return cell.insert(v);
295  }
296 
300  void erase(iterator pos)
301  {
302  CellContent & cell = pos.grid_it_->second;
303  cell.erase(pos.cell_it_);
304  }
305 
311  size_type erase(const key_type & key)
312  {
313  const CellIndex cellkey = cellindexAtClustercenter_(key);
314  auto cell = cells_.find(cellkey);
315  if (cell == cells_.end()) return 0;
316  return cell->second.erase(key);
317  }
318 
322  void clear() { cells_.clear(); }
323 
328  {
329  grid_iterator grid_it = cells_.begin();
330  if (grid_it == cells_.end()) return end();
331 
332  cell_iterator cell_it = grid_it->second.begin();
333  return iterator(cells_, grid_it, cell_it);
334  }
335 
340  {
341  const_grid_iterator grid_it = cells_.begin();
342  if (grid_it == cells_.end()) return end();
343 
344  const_cell_iterator cell_it = grid_it->second.begin();
345  return const_iterator(cells_, grid_it, cell_it);
346  }
347 
352  {
353  return iterator(cells_);
354  }
355 
360  {
361  return const_iterator(cells_);
362  }
363 
367  bool empty() const
368  {
369  return size() == 0;
370  }
371 
375  size_type size() const
376  {
377  size_type ret = 0;
378 
379  for (const_grid_iterator it = grid_begin(); it != grid_end(); ++it)
380  {
381  ret += it->second.size();
382  }
383 
384  return ret;
385  }
386 
390  const_grid_iterator grid_begin() const { return cells_.begin(); }
391 
395  const_grid_iterator grid_end() const { return cells_.end(); }
396 
400  const typename Grid::mapped_type & grid_at(const CellIndex & x) const { return cells_.at(x); }
401 
405  typename Grid::mapped_type & grid_at(const CellIndex & x) { return cells_.at(x); }
406 
410  const_grid_iterator grid_find(const CellIndex & x) const { return cells_.find(x); }
411 
415  grid_iterator grid_find(const CellIndex & x) { return cells_.find(x); }
416 
417 
421  grid_iterator grid_begin() { return cells_.begin(); }
425  grid_iterator grid_end() { return cells_.end(); }
426 
427 private:
428  // XXX: Replace with proper operator
430  {
431  CellIndex ret;
432  typename CellIndex::iterator it = ret.begin();
433  typename ClusterCenter::const_iterator lit = key.begin(), rit = cell_dimension.begin();
434  for (; it != ret.end(); ++it, ++lit, ++rit)
435  {
436  double t = std::floor(*lit / *rit);
437  if (t < std::numeric_limits<Int64>::min() || t > std::numeric_limits<Int64>::max()) throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
438  *it = static_cast<Int64>(t);
439  }
440  return ret;
441  }
442 
444  {
445  typename CellIndex::const_iterator it_new = d.begin();
446  typename CellIndex::iterator it_cur = grid_dimension_.begin();
447  for (; it_new != d.end(); ++it_new, ++it_cur)
448  {
449  if (*it_cur < *it_new)
450  *it_cur = *it_new;
451  }
452  }
453 
454  };
455 
457  template <UInt N, typename T>
458  std::size_t hash_value(const DPosition<N, T> & b)
459  {
460  boost::hash<T> hasher;
461  std::size_t hash = 0;
462  for (typename DPosition<N, T>::const_iterator it = b.begin(); it != b.end(); ++it)
463  hash ^= hasher(*it);
464  return hash;
465  }
466 
467 }
468 
469 #endif /* OPENMS_COMPARISON_CLUSTERING_HASHGRID_H */
Representation of a coordinate in D-dimensional space.
Definition: DPosition.h:54
ConstIterator end() const
Non-mutable end iterator.
Definition: DPosition.h:401
CoordinateType * iterator
Definition: DPosition.h:75
const CoordinateType * const_iterator
Definition: DPosition.h:76
ConstIterator begin() const
Non-mutable begin iterator.
Definition: DPosition.h:395
Out of range exception.
Definition: Exception.h:313
Constant element iterator for the hash grid.
Definition: HashGrid.h:174
ConstIterator(const Grid &grid, grid_iterator grid_it, cell_iterator cell_it)
Definition: HashGrid.h:208
const ConstIterator operator++(int)
Definition: HashGrid.h:225
bool operator!=(const ConstIterator &rhs) const
Definition: HashGrid.h:235
const Grid & grid_
Definition: HashGrid.h:181
const CellIndex index() const
Definition: HashGrid.h:244
grid_iterator grid_it_
Definition: HashGrid.h:182
bool operator==(const ConstIterator &rhs) const
Definition: HashGrid.h:232
Grid::const_iterator grid_iterator
Definition: HashGrid.h:178
ConstIterator & operator++()
Definition: HashGrid.h:218
const value_type * operator->() const
Definition: HashGrid.h:241
cell_iterator cell_it_
Definition: HashGrid.h:183
ConstIterator(const Iterator &it)
Definition: HashGrid.h:214
const value_type & operator*() const
Definition: HashGrid.h:238
ConstIterator(const Grid &grid)
Definition: HashGrid.h:204
CellContent::const_iterator cell_iterator
Definition: HashGrid.h:179
void searchNextCell_()
Definition: HashGrid.h:186
Element iterator for the hash grid.
Definition: HashGrid.h:96
value_type & operator*() const
Definition: HashGrid.h:156
CellContent::iterator cell_iterator
Definition: HashGrid.h:101
const CellIndex index() const
Definition: HashGrid.h:162
grid_iterator grid_it_
Definition: HashGrid.h:104
Grid::iterator grid_iterator
Definition: HashGrid.h:100
bool operator==(const Iterator &rhs) const
Definition: HashGrid.h:150
cell_iterator cell_it_
Definition: HashGrid.h:105
Iterator(Grid &grid, grid_iterator grid_it, cell_iterator cell_it)
Definition: HashGrid.h:130
Grid & grid_
Definition: HashGrid.h:103
Iterator(Grid &grid)
Definition: HashGrid.h:126
bool operator!=(const Iterator &rhs) const
Definition: HashGrid.h:153
void searchNextCell_()
Definition: HashGrid.h:108
const Iterator operator++(int)
Definition: HashGrid.h:143
Iterator & operator++()
Definition: HashGrid.h:136
value_type * operator->() const
Definition: HashGrid.h:159
Container for (2-dimensional coordinate, value) pairs.
Definition: HashGrid.h:63
CellContent::const_iterator const_cell_iterator
Definition: HashGrid.h:256
grid_iterator grid_end()
Definition: HashGrid.h:425
CellIndex cellindexAtClustercenter_(const ClusterCenter &key)
Definition: HashGrid.h:429
boost::unordered_multimap< ClusterCenter, Cluster > CellContent
Contents of a cell.
Definition: HashGrid.h:79
const CellIndex & grid_dimension
Upper-right corner of key space for cells.
Definition: HashGrid.h:274
Grid::const_iterator const_grid_iterator
Definition: HashGrid.h:254
CellIndex grid_dimension_
Definition: HashGrid.h:262
Iterator iterator
Definition: HashGrid.h:253
const_iterator begin() const
Returns iterator to first element.
Definition: HashGrid.h:339
CellContent::iterator cell_iterator
Definition: HashGrid.h:257
const_grid_iterator grid_find(const CellIndex &x) const
Returns the grid cell at given index if present, otherwise the grid_end iterator.
Definition: HashGrid.h:410
const_grid_iterator grid_end() const
Returns iterator to on after last grid cell.
Definition: HashGrid.h:395
DPosition< 2, Int64 > CellIndex
Index for cells.
Definition: HashGrid.h:74
DPosition< 2, double > ClusterCenter
Coordinate for stored pairs.
Definition: HashGrid.h:69
boost::unordered_map< CellIndex, CellContent > Grid
Map of (cell-index, cell-content).
Definition: HashGrid.h:84
cell_iterator insert(const value_type &v)
Inserts a (2-dimensional coordinate, value) pair.
Definition: HashGrid.h:289
ConstIterator const_iterator
Definition: HashGrid.h:252
size_type size() const
Return number of elements.
Definition: HashGrid.h:375
CellContent::value_type value_type
Definition: HashGrid.h:88
bool empty() const
Return true if HashGrid is empty.
Definition: HashGrid.h:367
Grid cells_
Definition: HashGrid.h:261
CellContent::size_type size_type
Definition: HashGrid.h:258
Grid::iterator grid_iterator
Definition: HashGrid.h:255
HashGrid(const ClusterCenter &c_dimension)
Definition: HashGrid.h:277
grid_iterator grid_find(const CellIndex &x)
Returns the grid cell at given index if present, otherwise the grid_end iterator.
Definition: HashGrid.h:415
CellContent::key_type key_type
Definition: HashGrid.h:86
void updateGridDimension_(const CellIndex &d)
Definition: HashGrid.h:443
grid_iterator grid_begin()
Definition: HashGrid.h:421
void clear()
Clears the map.
Definition: HashGrid.h:322
const Grid::mapped_type & grid_at(const CellIndex &x) const
Returns the grid cell at given index.
Definition: HashGrid.h:400
iterator end()
Returns iterator to first element.
Definition: HashGrid.h:351
const_iterator end() const
Returns iterator to first element.
Definition: HashGrid.h:359
void erase(iterator pos)
Erases element on given iterator.
Definition: HashGrid.h:300
const ClusterCenter cell_dimension
Dimension of cells.
Definition: HashGrid.h:269
Grid::mapped_type & grid_at(const CellIndex &x)
Definition: HashGrid.h:405
iterator begin()
Returns iterator to first element.
Definition: HashGrid.h:327
const_grid_iterator grid_begin() const
Returns iterator to first grid cell.
Definition: HashGrid.h:390
size_type erase(const key_type &key)
Erases elements matching the 2-dimensional coordinate.
Definition: HashGrid.h:311
CellContent::mapped_type mapped_type
Definition: HashGrid.h:87
OPENMS_INT64_TYPE Int64
Signed integer type (64bit)
Definition: Types.h:70
Main OpenMS namespace.
Definition: FeatureDeconvolution.h:47
std::size_t hash_value(const DPosition< N, T > &b)
Definition: HashGrid.h:458