| OpenMS 2.5.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-2020.
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>
44 #include <OpenMS/DATASTRUCTURES/DPosition.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
69 typedef DPosition<2, double> ClusterCenter;
70
74 typedef DPosition<2, Int64> CellIndex;
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
103 Grid & grid_;
104 grid_iterator grid_it_;
105 cell_iterator cell_it_;
106
107 // Search for next non-empty cell
108 void searchNextCell_()
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 {
117 cell_it_ = cell_iterator();
118 return;
119 }
120
121 cell_it_ = grid_it_->second.begin();
122 }
123 }
124
125 public:
126 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
136 Iterator & operator++()
137 {
138 ++cell_it_;
139 searchNextCell_();
140 return *this;
141 }
142
143 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
156 value_type & operator*() const
157 { return *cell_it_; }
158
159 value_type * operator->() const
160 { return &*cell_it_; }
161
162 const CellIndex index() const
163 {
164 return grid_it_->first;
165 }
166
167 };
168
172 class ConstIterator :
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_;
182 grid_iterator grid_it_;
183 cell_iterator cell_it_;
184
185 // Search for next non-empty cell
186 void searchNextCell_()
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 {
195 cell_it_ = cell_iterator();
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) :
215 grid_(it.grid_), grid_it_(it.grid_it_), cell_it_(it.cell_it_)
216 {}
217
218 ConstIterator & operator++()
219 {
220 ++cell_it_;
221 searchNextCell_();
222 return *this;
223 }
224
225 ConstIterator operator++(int)
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:
252 typedef ConstIterator const_iterator;
253 typedef Iterator iterator;
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:
261 Grid cells_;
262 CellIndex grid_dimension_;
263
264 public:
265
269 const ClusterCenter cell_dimension;
270
274 const CellIndex & grid_dimension;
275
276 public:
277 HashGrid(const ClusterCenter & c_dimension) :
278 cells_(),
279 grid_dimension_(),
280 cell_dimension(c_dimension),
281 grid_dimension(grid_dimension_)
282 {}
283
289 cell_iterator insert(const value_type & v)
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 try
315 {
316 CellContent & cell = cells_.at(cellkey);
317 return cell.erase(key);
318 }
319 catch (std::out_of_range &) {}
320 return 0;
321 }
322
326 void clear() { cells_.clear(); }
327
331 iterator begin()
332 {
333 grid_iterator grid_it = cells_.begin();
334 if (grid_it == cells_.end()) return end();
335
336 cell_iterator cell_it = grid_it->second.begin();
337 return iterator(cells_, grid_it, cell_it);
338 }
339
343 const_iterator begin() const
344 {
345 const_grid_iterator grid_it = cells_.begin();
346 if (grid_it == cells_.end()) return end();
347
348 const_cell_iterator cell_it = grid_it->second.begin();
349 return const_iterator(cells_, grid_it, cell_it);
350 }
351
355 iterator end()
356 {
357 return iterator(cells_);
358 }
359
363 const_iterator end() const
364 {
365 return const_iterator(cells_);
366 }
367
371 bool empty() const
372 {
373 return size() == 0;
374 }
375
379 size_type size() const
380 {
381 size_type ret = 0;
382
383 for (const_grid_iterator it = grid_begin(); it != grid_end(); ++it)
384 {
385 ret += it->second.size();
386 }
387
388 return ret;
389 }
390
394 const_grid_iterator grid_begin() const { return cells_.begin(); }
395
399 const_grid_iterator grid_end() const { return cells_.end(); }
400
404 const typename Grid::mapped_type & grid_at(const CellIndex & x) const { return cells_.at(x); }
405
409 grid_iterator grid_begin() { return cells_.begin(); }
413 grid_iterator grid_end() { return cells_.end(); }
417 typename Grid::mapped_type & grid_at(const CellIndex & x) { return cells_.at(x); }
418
419 private:
420 // XXX: Replace with proper operator
421 CellIndex cellindexAtClustercenter_(const ClusterCenter & key)
422 {
423 CellIndex ret;
424 typename CellIndex::iterator it = ret.begin();
425 typename ClusterCenter::const_iterator lit = key.begin(), rit = cell_dimension.begin();
426 for (; it != ret.end(); ++it, ++lit, ++rit)
427 {
428 double t = std::floor(*lit / *rit);
429 if (t < std::numeric_limits<Int64>::min() || t > std::numeric_limits<Int64>::max()) throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
430 *it = static_cast<Int64>(t);
431 }
432 return ret;
433 }
434
435 void updateGridDimension_(const CellIndex & d)
436 {
437 typename CellIndex::const_iterator it_new = d.begin();
438 typename CellIndex::iterator it_cur = grid_dimension_.begin();
439 for (; it_new != d.end(); ++it_new, ++it_cur)
440 {
441 if (*it_cur < *it_new)
442 *it_cur = *it_new;
443 }
444 }
445
446 };
447
449 template <UInt N, typename T>
450 std::size_t hash_value(const DPosition<N, T> & b)
451 {
452 boost::hash<T> hasher;
453 std::size_t hash = 0;
454 for (typename DPosition<N, T>::const_iterator it = b.begin(); it != b.end(); ++it)
455 hash ^= hasher(*it);
456 return hash;
457 }
458
459 }
460
461 #endif /* OPENMS_COMPARISON_CLUSTERING_HASHGRID_H */
OpenMS::HashGrid::ConstIterator::grid_
const Grid & grid_
Definition: HashGrid.h:181
OpenMS::HashGrid::ConstIterator::ConstIterator
ConstIterator(const Grid &grid, grid_iterator grid_it, cell_iterator cell_it)
Definition: HashGrid.h:208
OpenMS::HashGrid::clear
void clear()
Clears the map.
Definition: HashGrid.h:326
OpenMS::HashGrid::ConstIterator::operator==
bool operator==(const ConstIterator &rhs) const
Definition: HashGrid.h:232
OpenMS::HashGrid::Iterator::cell_it_
cell_iterator cell_it_
Definition: HashGrid.h:105
OpenMS::HashGrid::Iterator::operator++
Iterator & operator++()
Definition: HashGrid.h:136
OpenMS::HashGrid::empty
bool empty() const
Return true if HashGrid is empty.
Definition: HashGrid.h:371
OpenMS::HashGrid::begin
const_iterator begin() const
Returns iterator to first element.
Definition: HashGrid.h:343
OpenMS::DPosition::begin
ConstIterator begin() const
Non-mutable begin iterator.
Definition: DPosition.h:395
OpenMS::HashGrid::Iterator::Iterator
Iterator(Grid &grid, grid_iterator grid_it, cell_iterator cell_it)
Definition: HashGrid.h:130
OpenMS::HashGrid::value_type
CellContent::value_type value_type
Definition: HashGrid.h:88
OpenMS::HashGrid::end
iterator end()
Returns iterator to first element.
Definition: HashGrid.h:355
OpenMS::Exception::OutOfRange
Out of range exception.
Definition: Exception.h:319
OpenMS::HashGrid::Iterator::operator==
bool operator==(const Iterator &rhs) const
Definition: HashGrid.h:150
OpenMS::HashGrid::Iterator::operator!=
bool operator!=(const Iterator &rhs) const
Definition: HashGrid.h:153
OpenMS::HashGrid::ConstIterator::cell_iterator
CellContent::const_iterator cell_iterator
Definition: HashGrid.h:179
OpenMS::HashGrid::iterator
Iterator iterator
Definition: HashGrid.h:253
OpenMS::HashGrid::ConstIterator::grid_it_
grid_iterator grid_it_
Definition: HashGrid.h:182
OpenMS::HashGrid::size_type
CellContent::size_type size_type
Definition: HashGrid.h:258
OpenMS::HashGrid::cellindexAtClustercenter_
CellIndex cellindexAtClustercenter_(const ClusterCenter &key)
Definition: HashGrid.h:421
OpenMS::HashGrid::const_grid_iterator
Grid::const_iterator const_grid_iterator
Definition: HashGrid.h:254
OpenMS::HashGrid::ConstIterator::operator*
const value_type & operator*() const
Definition: HashGrid.h:238
OpenMS::HashGrid::Iterator::Iterator
Iterator(Grid &grid)
Definition: HashGrid.h:126
OpenMS::HashGrid::Iterator::grid_iterator
Grid::iterator grid_iterator
Definition: HashGrid.h:100
Types.h
OpenMS::HashGrid::Iterator::cell_iterator
CellContent::iterator cell_iterator
Definition: HashGrid.h:101
OpenMS::HashGrid::ConstIterator::ConstIterator
ConstIterator(const Grid &grid)
Definition: HashGrid.h:204
OpenMS::HashGrid::ConstIterator::searchNextCell_
void searchNextCell_()
Definition: HashGrid.h:186
OpenMS::HashGrid::grid_at
Grid::mapped_type & grid_at(const CellIndex &x)
Definition: HashGrid.h:417
OpenMS::HashGrid::ConstIterator::cell_it_
cell_iterator cell_it_
Definition: HashGrid.h:183
OpenMS::HashGrid::end
const_iterator end() const
Returns iterator to first element.
Definition: HashGrid.h:363
OpenMS::HashGrid
Container for (2-dimensional coordinate, value) pairs.
Definition: HashGrid.h:62
OpenMS::HashGrid::const_iterator
ConstIterator const_iterator
Definition: HashGrid.h:252
OpenMS::HashGrid::mapped_type
CellContent::mapped_type mapped_type
Definition: HashGrid.h:87
OpenMS::HashGrid::CellIndex
DPosition< 2, Int64 > CellIndex
Index for cells.
Definition: HashGrid.h:74
OpenMS::HashGrid::Iterator::operator->
value_type * operator->() const
Definition: HashGrid.h:159
OpenMS::HashGrid::updateGridDimension_
void updateGridDimension_(const CellIndex &d)
Definition: HashGrid.h:435
OpenMS::HashGrid::erase
size_type erase(const key_type &key)
Erases elements matching the 2-dimensional coordinate.
Definition: HashGrid.h:311
OpenMS::DPosition::const_iterator
const CoordinateType * const_iterator
Definition: DPosition.h:76
OpenMS::HashGrid::ConstIterator::index
const CellIndex index() const
Definition: HashGrid.h:244
OpenMS::HashGrid::insert
cell_iterator insert(const value_type &v)
Inserts a (2-dimensional coordinate, value) pair.
Definition: HashGrid.h:289
OpenMS::HashGrid::grid_end
grid_iterator grid_end()
Definition: HashGrid.h:413
OpenMS::HashGrid::Iterator::grid_
Grid & grid_
Definition: HashGrid.h:103
DPosition.h
OpenMS::HashGrid::cell_iterator
CellContent::iterator cell_iterator
Definition: HashGrid.h:257
OpenMS::HashGrid::ClusterCenter
DPosition< 2, double > ClusterCenter
Coordinate for stored pairs.
Definition: HashGrid.h:69
OpenMS::HashGrid::grid_dimension
const CellIndex & grid_dimension
Upper-right corner of key space for cells.
Definition: HashGrid.h:274
OpenMS::HashGrid::ConstIterator
Constant element iterator for the hash grid.
Definition: HashGrid.h:172
OpenMS::HashGrid::ConstIterator::operator!=
bool operator!=(const ConstIterator &rhs) const
Definition: HashGrid.h:235
OpenMS
Main OpenMS namespace.
Definition: FeatureDeconvolution.h:46
OpenMS::HashGrid::ConstIterator::operator++
ConstIterator operator++(int)
Definition: HashGrid.h:225
OpenMS::HashGrid::grid_begin
const_grid_iterator grid_begin() const
Returns iterator to first grid cell.
Definition: HashGrid.h:394
OpenMS::HashGrid::const_cell_iterator
CellContent::const_iterator const_cell_iterator
Definition: HashGrid.h:256
OpenMS::HashGrid::begin
iterator begin()
Returns iterator to first element.
Definition: HashGrid.h:331
OpenMS::HashGrid::grid_at
const Grid::mapped_type & grid_at(const CellIndex &x) const
Returns the grid cell at given index.
Definition: HashGrid.h:404
OpenMS::HashGrid::Iterator
Element iterator for the hash grid.
Definition: HashGrid.h:94
OpenMS::HashGrid::grid_end
const_grid_iterator grid_end() const
Returns iterator to on after last grid cell.
Definition: HashGrid.h:399
OpenMS::DPosition
Representation of a coordinate in D-dimensional space.
Definition: DPosition.h:53
OpenMS::HashGrid::HashGrid
HashGrid(const ClusterCenter &c_dimension)
Definition: HashGrid.h:277
OpenMS::HashGrid::cell_dimension
const ClusterCenter cell_dimension
Dimension of cells.
Definition: HashGrid.h:269
OpenMS::HashGrid::CellContent
boost::unordered_multimap< ClusterCenter, Cluster > CellContent
Contents of a cell.
Definition: HashGrid.h:79
OpenMS::HashGrid::ConstIterator::operator->
const value_type * operator->() const
Definition: HashGrid.h:241
OpenMS::HashGrid::ConstIterator::grid_iterator
Grid::const_iterator grid_iterator
Definition: HashGrid.h:178
OpenMS::HashGrid::Iterator::operator*
value_type & operator*() const
Definition: HashGrid.h:156
OpenMS::HashGrid::key_type
CellContent::key_type key_type
Definition: HashGrid.h:86
OpenMS::HashGrid::Iterator::operator++
Iterator operator++(int)
Definition: HashGrid.h:143
OpenMS::HashGrid::grid_iterator
Grid::iterator grid_iterator
Definition: HashGrid.h:255
OpenMS::HashGrid::Grid
boost::unordered_map< CellIndex, CellContent > Grid
Map of (cell-index, cell-content).
Definition: HashGrid.h:84
OpenMS::HashGrid::cells_
Grid cells_
Definition: HashGrid.h:261
OpenMS::HashGrid::erase
void erase(iterator pos)
Erases element on given iterator.
Definition: HashGrid.h:300
OpenMS::Int64
OPENMS_INT64_TYPE Int64
Signed integer type (64bit)
Definition: Types.h:70
OpenMS::DPosition< 2, Int64 >::iterator
CoordinateType * iterator
Definition: DPosition.h:75
OpenMS::HashGrid::Iterator::index
const CellIndex index() const
Definition: HashGrid.h:162
OpenMS::HashGrid::Iterator::grid_it_
grid_iterator grid_it_
Definition: HashGrid.h:104
OpenMS::HashGrid::ConstIterator::operator++
ConstIterator & operator++()
Definition: HashGrid.h:218
OpenMS::hash_value
std::size_t hash_value(const DPosition< N, T > &b)
Definition: HashGrid.h:450
OpenMS::HashGrid::size
size_type size() const
Return number of elements.
Definition: HashGrid.h:379
OpenMS::HashGrid::grid_begin
grid_iterator grid_begin()
Definition: HashGrid.h:409
OpenMS::DPosition::end
ConstIterator end() const
Non-mutable end iterator.
Definition: DPosition.h:401
OpenMS::HashGrid::Iterator::searchNextCell_
void searchNextCell_()
Definition: HashGrid.h:108
OpenMS::HashGrid::ConstIterator::ConstIterator
ConstIterator(const Iterator &it)
Definition: HashGrid.h:214
OpenMS::HashGrid::grid_dimension_
CellIndex grid_dimension_
Definition: HashGrid.h:262