OpenMS
HashGrid.h
Go to the documentation of this file.
1 // Copyright (c) 2002-2023, The OpenMS Team -- EKU Tuebingen, ETH Zurich, and FU Berlin
2 // SPDX-License-Identifier: BSD-3-Clause
3 //
4 // --------------------------------------------------------------------------
5 // $Maintainer: Lars Nilse $
6 // $Authors: Bastian Blank $
7 // --------------------------------------------------------------------------
8 
9 #include <OpenMS/CONCEPT/Types.h>
11 #include <boost/array.hpp>
12 #include <boost/functional/hash.hpp>
13 #include <boost/unordered/unordered_map.hpp>
14 #include <cmath>
15 #include <iterator>
16 #include <limits>
17 
18 #ifndef OPENMS_COMPARISON_CLUSTERING_HASHGRID_H
19  #define OPENMS_COMPARISON_CLUSTERING_HASHGRID_H
20 
21 namespace OpenMS
22 {
33  template<typename Cluster>
34  class HashGrid
35  {
36  public:
40  // XXX: Check is there is another type handy in OpenMS already
42 
47 
51  typedef typename boost::unordered_multimap<ClusterCenter, Cluster> CellContent;
52 
56  typedef boost::unordered_map<CellIndex, CellContent> Grid;
57 
58  typedef typename CellContent::key_type key_type;
59  typedef typename CellContent::mapped_type mapped_type;
60  typedef typename CellContent::value_type value_type;
61 
62  private:
66  class Iterator
67  {
68  private:
69  friend class HashGrid;
70 
71  typedef typename Grid::iterator grid_iterator;
72  typedef typename CellContent::iterator cell_iterator;
73 
78  using iterator_category = std::input_iterator_tag;
84  using pointer = value_type*;
86  using difference_type = std::ptrdiff_t;
88 
89 
93 
94  // Search for next non-empty cell
96  {
97  while (cell_it_ == grid_it_->second.end())
98  {
99  grid_it_++;
100 
101  // If we are at the last cell, set cell iterator to something well-known
102  if (grid_it_ == grid_.end())
103  {
105  return;
106  }
107 
108  cell_it_ = grid_it_->second.begin();
109  }
110  }
111 
112  public:
113  explicit Iterator(Grid& grid) : grid_(grid), grid_it_(grid.end())
114  {
115  }
116 
117  Iterator(Grid& grid, grid_iterator grid_it, cell_iterator cell_it) : grid_(grid), grid_it_(grid_it), cell_it_(cell_it)
118  {
119  searchNextCell_();
120  }
121 
123  {
124  ++cell_it_;
125  searchNextCell_();
126  return *this;
127  }
128 
129  const Iterator operator++(int)
130  {
131  Iterator ret(*this);
132  operator++();
133  return ret;
134  }
135 
136  bool operator==(const Iterator& rhs) const
137  {
138  return grid_it_ == rhs.grid_it_ && cell_it_ == rhs.cell_it_;
139  }
140 
141  bool operator!=(const Iterator& rhs) const
142  {
143  return !(*this == rhs);
144  }
145 
147  {
148  return *cell_it_;
149  }
150 
152  {
153  return &*cell_it_;
154  }
155 
156  const CellIndex index() const
157  {
158  return grid_it_->first;
159  }
160  };
161 
166  {
167  private:
168  friend class HashGrid;
169 
170  typedef typename Grid::const_iterator grid_iterator;
171  typedef typename CellContent::const_iterator cell_iterator;
172 
177  using iterator_category = std::input_iterator_tag;
183  using pointer = value_type*;
185  using difference_type = std::ptrdiff_t;
187 
188  const Grid& grid_;
191 
192  // Search for next non-empty cell
194  {
195  while (cell_it_ == grid_it_->second.end())
196  {
197  grid_it_++;
198 
199  // If we are at the last cell, set cell iterator to something well-known
200  if (grid_it_ == grid_.end())
201  {
203  return;
204  }
205 
206  cell_it_ = grid_it_->second.begin();
207  }
208  }
209 
210  public:
211  ConstIterator(const Grid& grid) : grid_(grid), grid_it_(grid.end())
212  {
213  }
214 
215  ConstIterator(const Grid& grid, grid_iterator grid_it, cell_iterator cell_it) : grid_(grid), grid_it_(grid_it), cell_it_(cell_it)
216  {
217  searchNextCell_();
218  }
219 
221  {
222  }
223 
225  {
226  ++cell_it_;
227  searchNextCell_();
228  return *this;
229  }
230 
232  {
233  ConstIterator ret(*this);
234  operator++();
235  return ret;
236  }
237 
238  bool operator==(const ConstIterator& rhs) const
239  {
240  return grid_it_ == rhs.grid_it_ && cell_it_ == rhs.cell_it_;
241  }
242 
243  bool operator!=(const ConstIterator& rhs) const
244  {
245  return !(*this == rhs);
246  }
247 
248  const value_type& operator*() const
249  {
250  return *cell_it_;
251  }
252 
253  const value_type* operator->() const
254  {
255  return &*cell_it_;
256  }
257 
258  const CellIndex index() const
259  {
260  return grid_it_->first;
261  }
262  };
263 
264  public:
267  typedef typename Grid::const_iterator const_grid_iterator;
268  typedef typename Grid::iterator grid_iterator;
269  typedef typename CellContent::const_iterator const_cell_iterator;
270  typedef typename CellContent::iterator cell_iterator;
271  typedef typename CellContent::size_type size_type;
272 
273  private:
276 
277  public:
282 
287 
288  public:
289  explicit HashGrid(const ClusterCenter& c_dimension) : cells_(), grid_dimension_(), cell_dimension(c_dimension), grid_dimension(grid_dimension_)
290  {
291  }
292 
299  {
300  const CellIndex cellkey = cellindexAtClustercenter_(v.first);
301  CellContent& cell = cells_[cellkey];
302  updateGridDimension_(cellkey);
303  return cell.insert(v);
304  }
305 
309  void erase(iterator pos)
310  {
311  CellContent& cell = pos.grid_it_->second;
312  cell.erase(pos.cell_it_);
313  }
314 
321  {
322  const CellIndex cellkey = cellindexAtClustercenter_(key);
323  auto cell = cells_.find(cellkey);
324  if (cell == cells_.end())
325  return 0;
326  return cell->second.erase(key);
327  }
328 
332  void clear()
333  {
334  cells_.clear();
335  }
336 
341  {
342  grid_iterator grid_it = cells_.begin();
343  if (grid_it == cells_.end())
344  return end();
345 
346  cell_iterator cell_it = grid_it->second.begin();
347  return iterator(cells_, grid_it, cell_it);
348  }
349 
354  {
355  const_grid_iterator grid_it = cells_.begin();
356  if (grid_it == cells_.end())
357  return end();
358 
359  const_cell_iterator cell_it = grid_it->second.begin();
360  return const_iterator(cells_, grid_it, cell_it);
361  }
362 
367  {
368  return iterator(cells_);
369  }
370 
375  {
376  return const_iterator(cells_);
377  }
378 
382  bool empty() const
383  {
384  return size() == 0;
385  }
386 
390  size_type size() const
391  {
392  size_type ret = 0;
393 
394  for (const_grid_iterator it = grid_begin(); it != grid_end(); ++it)
395  {
396  ret += it->second.size();
397  }
398 
399  return ret;
400  }
401 
406  {
407  return cells_.begin();
408  }
409 
414  {
415  return cells_.end();
416  }
417 
421  const typename Grid::mapped_type& grid_at(const CellIndex& x) const
422  {
423  return cells_.at(x);
424  }
425 
429  typename Grid::mapped_type& grid_at(const CellIndex& x)
430  {
431  return cells_.at(x);
432  }
433 
438  {
439  return cells_.find(x);
440  }
441 
446  {
447  return cells_.find(x);
448  }
449 
450 
455  {
456  return cells_.begin();
457  }
462  {
463  return cells_.end();
464  }
465 
466  private:
467  // XXX: Replace with proper operator
469  {
470  CellIndex ret;
471  typename CellIndex::iterator it = ret.begin();
472  typename ClusterCenter::const_iterator lit = key.begin(), rit = cell_dimension.begin();
473  for (; it != ret.end(); ++it, ++lit, ++rit)
474  {
475  double t = std::floor(*lit / *rit);
476  if (t < std::numeric_limits<Int64>::min() || t > std::numeric_limits<Int64>::max())
477  throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
478  *it = static_cast<Int64>(t);
479  }
480  return ret;
481  }
482 
484  {
485  typename CellIndex::const_iterator it_new = d.begin();
486  typename CellIndex::iterator it_cur = grid_dimension_.begin();
487  for (; it_new != d.end(); ++it_new, ++it_cur)
488  {
489  if (*it_cur < *it_new)
490  *it_cur = *it_new;
491  }
492  }
493  };
494 
496  template<UInt N, typename T>
497  std::size_t hash_value(const DPosition<N, T>& b)
498  {
499  boost::hash<T> hasher;
500  std::size_t hash = 0;
501  for (typename DPosition<N, T>::const_iterator it = b.begin(); it != b.end(); ++it)
502  hash ^= hasher(*it);
503  return hash;
504  }
505 
506 } // namespace OpenMS
507 
508 #endif /* OPENMS_COMPARISON_CLUSTERING_HASHGRID_H */
Representation of a coordinate in D-dimensional space.
Definition: DPosition.h:29
ConstIterator end() const
Non-mutable end iterator.
Definition: DPosition.h:386
CoordinateType * iterator
Definition: DPosition.h:50
const CoordinateType * const_iterator
Definition: DPosition.h:51
ConstIterator begin() const
Non-mutable begin iterator.
Definition: DPosition.h:380
Out of range exception.
Definition: Exception.h:287
Constant element iterator for the hash grid.
Definition: HashGrid.h:166
ConstIterator(const Grid &grid, grid_iterator grid_it, cell_iterator cell_it)
Definition: HashGrid.h:215
const ConstIterator operator++(int)
Definition: HashGrid.h:231
bool operator!=(const ConstIterator &rhs) const
Definition: HashGrid.h:243
value_type * pointer
The pointer type as returned by operator->()
Definition: HashGrid.h:183
const Grid & grid_
Definition: HashGrid.h:188
const CellIndex index() const
Definition: HashGrid.h:258
grid_iterator grid_it_
Definition: HashGrid.h:189
HashGrid::value_type value_type
The iterator's value type.
Definition: HashGrid.h:179
bool operator==(const ConstIterator &rhs) const
Definition: HashGrid.h:238
value_type & reference
The reference type as returned by operator*()
Definition: HashGrid.h:181
Grid::const_iterator grid_iterator
Definition: HashGrid.h:170
ConstIterator & operator++()
Definition: HashGrid.h:224
const value_type * operator->() const
Definition: HashGrid.h:253
cell_iterator cell_it_
Definition: HashGrid.h:190
ConstIterator(const Iterator &it)
Definition: HashGrid.h:220
const value_type & operator*() const
Definition: HashGrid.h:248
ConstIterator(const Grid &grid)
Definition: HashGrid.h:211
std::input_iterator_tag iterator_category
The iterator's category type.
Definition: HashGrid.h:177
CellContent::const_iterator cell_iterator
Definition: HashGrid.h:171
std::ptrdiff_t difference_type
The difference type.
Definition: HashGrid.h:185
void searchNextCell_()
Definition: HashGrid.h:193
Element iterator for the hash grid.
Definition: HashGrid.h:67
value_type & operator*() const
Definition: HashGrid.h:146
CellContent::iterator cell_iterator
Definition: HashGrid.h:72
value_type * pointer
The pointer type as returned by operator->()
Definition: HashGrid.h:84
const CellIndex index() const
Definition: HashGrid.h:156
grid_iterator grid_it_
Definition: HashGrid.h:91
HashGrid::value_type value_type
The iterator's value type.
Definition: HashGrid.h:80
value_type & reference
The reference type as returned by operator*()
Definition: HashGrid.h:82
Grid::iterator grid_iterator
Definition: HashGrid.h:71
bool operator==(const Iterator &rhs) const
Definition: HashGrid.h:136
cell_iterator cell_it_
Definition: HashGrid.h:92
Iterator(Grid &grid, grid_iterator grid_it, cell_iterator cell_it)
Definition: HashGrid.h:117
Grid & grid_
Definition: HashGrid.h:90
std::input_iterator_tag iterator_category
The iterator's category type.
Definition: HashGrid.h:78
Iterator(Grid &grid)
Definition: HashGrid.h:113
std::ptrdiff_t difference_type
The difference type.
Definition: HashGrid.h:86
bool operator!=(const Iterator &rhs) const
Definition: HashGrid.h:141
void searchNextCell_()
Definition: HashGrid.h:95
const Iterator operator++(int)
Definition: HashGrid.h:129
Iterator & operator++()
Definition: HashGrid.h:122
value_type * operator->() const
Definition: HashGrid.h:151
Container for (2-dimensional coordinate, value) pairs.
Definition: HashGrid.h:35
CellContent::const_iterator const_cell_iterator
Definition: HashGrid.h:269
grid_iterator grid_end()
Definition: HashGrid.h:461
CellIndex cellindexAtClustercenter_(const ClusterCenter &key)
Definition: HashGrid.h:468
boost::unordered_multimap< ClusterCenter, Cluster > CellContent
Contents of a cell.
Definition: HashGrid.h:51
const CellIndex & grid_dimension
Upper-right corner of key space for cells.
Definition: HashGrid.h:286
Grid::const_iterator const_grid_iterator
Definition: HashGrid.h:267
CellIndex grid_dimension_
Definition: HashGrid.h:275
Iterator iterator
Definition: HashGrid.h:266
const_iterator begin() const
Returns iterator to first element.
Definition: HashGrid.h:353
CellContent::iterator cell_iterator
Definition: HashGrid.h:270
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:437
const_grid_iterator grid_end() const
Returns iterator to on after last grid cell.
Definition: HashGrid.h:413
DPosition< 2, Int64 > CellIndex
Index for cells.
Definition: HashGrid.h:46
DPosition< 2, double > ClusterCenter
Coordinate for stored pairs.
Definition: HashGrid.h:41
boost::unordered_map< CellIndex, CellContent > Grid
Map of (cell-index, cell-content).
Definition: HashGrid.h:56
cell_iterator insert(const value_type &v)
Inserts a (2-dimensional coordinate, value) pair.
Definition: HashGrid.h:298
ConstIterator const_iterator
Definition: HashGrid.h:265
size_type size() const
Return number of elements.
Definition: HashGrid.h:390
CellContent::value_type value_type
Definition: HashGrid.h:60
bool empty() const
Return true if HashGrid is empty.
Definition: HashGrid.h:382
Grid cells_
Definition: HashGrid.h:274
CellContent::size_type size_type
Definition: HashGrid.h:271
Grid::iterator grid_iterator
Definition: HashGrid.h:268
HashGrid(const ClusterCenter &c_dimension)
Definition: HashGrid.h:289
grid_iterator grid_find(const CellIndex &x)
Returns the grid cell at given index if present, otherwise the grid_end iterator.
Definition: HashGrid.h:445
CellContent::key_type key_type
Definition: HashGrid.h:58
void updateGridDimension_(const CellIndex &d)
Definition: HashGrid.h:483
grid_iterator grid_begin()
Definition: HashGrid.h:454
void clear()
Clears the map.
Definition: HashGrid.h:332
const Grid::mapped_type & grid_at(const CellIndex &x) const
Returns the grid cell at given index.
Definition: HashGrid.h:421
iterator end()
Returns iterator to first element.
Definition: HashGrid.h:366
const_iterator end() const
Returns iterator to first element.
Definition: HashGrid.h:374
void erase(iterator pos)
Erases element on given iterator.
Definition: HashGrid.h:309
const ClusterCenter cell_dimension
Dimension of cells.
Definition: HashGrid.h:281
Grid::mapped_type & grid_at(const CellIndex &x)
Definition: HashGrid.h:429
iterator begin()
Returns iterator to first element.
Definition: HashGrid.h:340
const_grid_iterator grid_begin() const
Returns iterator to first grid cell.
Definition: HashGrid.h:405
size_type erase(const key_type &key)
Erases elements matching the 2-dimensional coordinate.
Definition: HashGrid.h:320
CellContent::mapped_type mapped_type
Definition: HashGrid.h:59
OPENMS_INT64_TYPE Int64
Signed integer type (64bit)
Definition: Types.h:44
Main OpenMS namespace.
Definition: FeatureDeconvolution.h:22
std::size_t hash_value(const DPosition< N, T > &b)
Definition: HashGrid.h:497