« back to all changes in this revision
Viewing changes to inc/mdds/rectangle_set.hpp
- browse files at revision 4
- compare with another revision
- download diff
- download tarball
- view history from revision 4
- Committer: Bazaar Package Importer
- Author(s): Rene Engelhard
- Date: 2010-12-21 02:02:35 UTC
- mfrom: (1.1.1 upstream)
- Revision ID: james.westby@ubuntu.com-20101221020235-zck8jzrtz3odo6fi
Tags: 0.3.1-1
New upstream release
added
removed
inc/mdds/rectangle_set.hpp
1
/*************************************************************************
2
*
3
* Copyright (c) 2010 Kohei Yoshida
4
*
5
* Permission is hereby granted, free of charge, to any person
6
* obtaining a copy of this software and associated documentation
7
* files (the "Software"), to deal in the Software without
8
* restriction, including without limitation the rights to use,
9
* copy, modify, merge, publish, distribute, sublicense, and/or sell
10
* copies of the Software, and to permit persons to whom the
11
* Software is furnished to do so, subject to the following
12
* conditions:
13
*
14
* The above copyright notice and this permission notice shall be
15
* included in all copies or substantial portions of the Software.
16
*
17
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24
* OTHER DEALINGS IN THE SOFTWARE.
25
*
26
************************************************************************/
27
28
#ifndef __MDDS_RECTANGLE_SET_HPP__
29
#define __MDDS_RECTANGLE_SET_HPP__
30
31
#include "segment_tree.hpp"
32
#include "global.hpp"
33
34
#include <vector>
35
#include <unordered_map>
36
#include <boost/ptr_container/ptr_map.hpp>
37
38
namespace mdds {
39
40
template<typename _Key, typename _Data>
41
class rectangle_set
42
{
43
public:
44
typedef _Key key_type;
45
typedef _Data data_type;
46
47
#ifdef UNIT_TEST
48
public:
49
#else
50
private:
51
#endif
52
struct rectangle
53
{
54
key_type x1;
55
key_type y1;
56
key_type x2;
57
key_type y2;
58
59
rectangle(key_type _x1, key_type _y1, key_type _x2, key_type _y2) :
60
x1(_x1), y1(_y1), x2(_x2), y2(_y2) {}
61
62
rectangle(const rectangle& r) :
63
x1(r.x1), y1(r.y1), x2(r.x2), y2(r.y2) {}
64
65
rectangle& operator= (const rectangle& r)
66
{
67
x1 = r.x1;
68
y1 = r.y1;
69
x2 = r.x2;
70
y2 = r.y2;
71
return *this;
72
}
73
74
bool operator== (const rectangle& r) const
75
{
76
return x1 == r.x1 && y1 == r.y1 && x2 == r.x2 && y2 == r.y2;
77
}
78
79
bool operator!= (const rectangle& r) const
80
{
81
return !operator==(r);
82
}
83
};
84
typedef ::std::unordered_map<data_type*, rectangle> dataset_type;
85
private:
86
typedef segment_tree<key_type, data_type> inner_type;
87
typedef segment_tree<key_type, inner_type> outer_type;
88
89
typedef ::std::pair<key_type, key_type> interval_type;
90
typedef ::boost::ptr_map<interval_type, inner_type> inner_segment_map_type;
91
92
public:
93
typedef typename inner_type::search_result_type search_result_type;
94
95
/**
96
* Most of the implementation of search_result and its iterator is in
97
* segment_tree since the iteration logic is identical & depends on the
98
* segment_tree internals.
99
*/
100
class search_result : public inner_type::search_result_base
101
{
102
public:
103
typedef typename inner_type::search_result_base::res_chains_type res_chains_type;
104
typedef typename inner_type::search_result_base::res_chains_ptr res_chains_ptr;
105
typedef typename inner_type::data_chain_type data_chain_type;
106
107
public:
108
109
class iterator : public inner_type::iterator_base
110
{
111
friend class rectangle_set<_Key,_Data>::search_result;
112
private:
113
iterator(const res_chains_ptr& p) : inner_type::iterator_base(p) {}
114
public:
115
iterator() : inner_type::iterator_base() {}
116
};
117
118
search_result() : inner_type::search_result_base() {}
119
search_result(const search_result& r) : inner_type::search_result_base(r) {}
120
121
typename search_result::iterator begin()
122
{
123
typename search_result::iterator itr(
124
inner_type::search_result_base::get_res_chains());
125
itr.move_to_front();
126
return itr;
127
}
128
129
typename search_result::iterator end()
130
{
131
typename search_result::iterator itr(
132
inner_type::search_result_base::get_res_chains());
133
itr.move_to_end();
134
return itr;
135
}
136
};
137
138
rectangle_set();
139
rectangle_set(const rectangle_set& r);
140
~rectangle_set();
141
142
rectangle_set& operator= (const rectangle_set& r);
143
144
/**
145
* Equality between two instances of rectangle_set is evaluated based on
146
* the stored rectangle instances; their pointer values and geometries.
147
*/
148
bool operator== (const rectangle_set& r) const;
149
150
bool operator!= (const rectangle_set& r) const { return !operator==(r); }
151
152
/**
153
* Insert a new rectangle (and data associated with it) into the set.
154
* Note that insertion of duplicate data instance is not allowed. A data
155
* is considered a duplicate if its pointer value is identical to one of
156
* the data instances already stored within. Also note that <i>the end
157
* point of a rectangle is non-inclusive; a rectangle of (x1,y1) - (x2,y2)
158
* means that the rectangle spans x1 <= x < x2 and y1 <= y < y2.</i>
159
*
160
* @param x1 lower x coordinate of the rectangle. Inclusive.
161
* @param y1 lower y coordinate of the rectangle. Inclusive.
162
* @param x2 upper x coordinate of the rectangle. Non-inclusive.
163
* @param y2 upper y coordinate of the rectangle. Non-inclusive.
164
* @param data pointer to data instance associated with this rectangle.
165
* <i>Note that the caller is responsible for managing the
166
* life cycle of the data instance</i>.
167
*
168
* @return true if a rectangle successfully inserted, false otherwise.
169
*/
170
bool insert(key_type x1, key_type y1, key_type x2, key_type y2, data_type* data);
171
172
/**
173
* Search and collect all rectangles that contains a given point.
174
*
175
* @param x x coordinate of a query point.
176
* @param y y coordinate of a query point.
177
* @param result array of pointers to rectangle instances.
178
*
179
* @return true if the search is successful, false otherwise.
180
*/
181
bool search(key_type x, key_type y, search_result_type& result);
182
183
/**
184
* Search and collect all rectangles containing a given point.
185
*
186
* @param x x coordinate of a query point.
187
* @param y y coordinate of a query point.
188
*
189
* @return object containing the result of the search, which can be
190
* accessed via iterator.
191
*/
192
search_result search(key_type x, key_type y);
193
194
/**
195
* Remove a rectangle instance pointed to by a given pointer.
196
*
197
* @param data pointer that points to the rectangle instance you wish to
198
* remove from the set.
199
*/
200
void remove(data_type* data);
201
202
/**
203
* Clear all rectangles stored in the set.
204
*/
205
void clear();
206
207
/**
208
* Return the number of rectangles currently stored in the set.
209
*
210
* @return number of stored rectangles.
211
*/
212
size_t size() const;
213
214
/**
215
* Check whether or not the set is empty.
216
*
217
* @return true if the set is empty, false otherwise.
218
*/
219
bool empty() const;
220
221
private:
222
void build_outer_segment_tree();
223
224
#ifdef UNIT_TEST
225
public:
226
void dump_rectangles() const;
227
bool verify_rectangles(const dataset_type& expected) const;
228
#endif
229
230
private:
231
232
/**
233
* This data member stores pointers to the inner segment tree instances
234
* associated with outer intervals. Used to speed up searches.
235
*/
236
outer_type m_outer_segments;
237
238
/**
239
* This data member owns the inner segment_tree instances.
240
*/
241
inner_segment_map_type m_inner_map;
242
243
/**
244
* Used to keep track of currently stored data instances, to prevent
245
* insertion of duplicates. Duplicates are defined as data objects having
246
* identical pointer value.
247
*/
248
dataset_type m_dataset;
249
};
250
251
template<typename _Key, typename _Data>
252
rectangle_set<_Key,_Data>::rectangle_set()
253
{
254
}
255
256
template<typename _Key, typename _Data>
257
rectangle_set<_Key,_Data>::rectangle_set(const rectangle_set& r) :
258
m_inner_map(r.m_inner_map),
259
m_dataset(r.m_dataset)
260
{
261
build_outer_segment_tree();
262
}
263
264
template<typename _Key, typename _Data>
265
rectangle_set<_Key,_Data>::~rectangle_set()
266
{
267
}
268
269
template<typename _Key, typename _Data>
270
rectangle_set<_Key,_Data>& rectangle_set<_Key,_Data>::operator= (const rectangle_set& r)
271
{
272
clear(); // Don't forget to clear the internal state beforehands.
273
274
m_inner_map = r.m_inner_map;
275
m_dataset = r.m_dataset;
276
build_outer_segment_tree();
277
return *this;
278
}
279
280
template<typename _Key, typename _Data>
281
bool rectangle_set<_Key,_Data>::operator== (const rectangle_set& r) const
282
{
283
if (m_dataset.size() != r.m_dataset.size())
284
return false;
285
286
typename dataset_type::const_iterator itr = m_dataset.begin(), itr_end = m_dataset.end();
287
for (; itr != itr_end; ++itr)
288
{
289
typename dataset_type::const_iterator itr_rhs = r.m_dataset.find(itr->first);
290
if (itr_rhs == r.m_dataset.end())
291
return false;
292
293
if (itr->second != itr_rhs->second)
294
return false;
295
}
296
297
return true;
298
}
299
300
template<typename _Key, typename _Data>
301
bool rectangle_set<_Key,_Data>::insert(key_type x1, key_type y1, key_type x2, key_type y2, data_type* data)
302
{
303
// Make sure this is not a duplicate.
304
if (m_dataset.find(data) != m_dataset.end())
305
return false;
306
307
// Check if interval x1 - x2 is already stored.
308
interval_type outer_interval = interval_type(x1, x2);
309
typename inner_segment_map_type::iterator itr = m_inner_map.find(outer_interval);
310
if (itr == m_inner_map.end())
311
{
312
// this interval has not yet been stored. Create a new inner segment
313
// tree instance for this interval.
314
::std::pair<typename inner_segment_map_type::iterator, bool> r =
315
m_inner_map.insert(outer_interval, new inner_type);
316
if (!r.second)
317
throw general_error("inner segment tree insertion failed.");
318
319
itr = r.first;
320
321
// Register the pointer to this inner segment tree instance with the
322
// outer segment tree.
323
if (!m_outer_segments.insert(x1, x2, itr->second))
324
// This should never fail if my logic is correct.
325
throw general_error("failed to insert an inner segment tree pointer into the outer segment tree.");
326
}
327
328
inner_type* inner_tree = itr->second;
329
inner_tree->insert(y1, y2, data);
330
m_dataset.insert(typename dataset_type::value_type(data, rectangle(x1, y1, x2, y2)));
331
332
return true;
333
}
334
335
template<typename _Key, typename _Data>
336
bool rectangle_set<_Key,_Data>::search(key_type x, key_type y, search_result_type& result)
337
{
338
typename outer_type::search_result_type inner_trees;
339
if (!m_outer_segments.is_tree_valid())
340
m_outer_segments.build_tree();
341
342
if (!m_outer_segments.search(x, inner_trees))
343
return false;
344
345
typename outer_type::search_result_type::iterator itr_tree = inner_trees.begin(), itr_tree_end = inner_trees.end();
346
for (; itr_tree != itr_tree_end; ++itr_tree)
347
{
348
inner_type* inner_tree = *itr_tree;
349
if (!inner_tree->is_tree_valid())
350
inner_tree->build_tree();
351
352
// Search all relevant inner trees and aggregate results.
353
if (!inner_tree->search(y, result))
354
return false;
355
}
356
return true;
357
}
358
359
template<typename _Key, typename _Data>
360
typename rectangle_set<_Key,_Data>::search_result
361
rectangle_set<_Key,_Data>::search(key_type x, key_type y)
362
{
363
search_result result;
364
typename outer_type::search_result_type inner_trees;
365
if (!m_outer_segments.is_tree_valid())
366
m_outer_segments.build_tree();
367
368
if (!m_outer_segments.search(x, inner_trees))
369
return result;
370
371
typename outer_type::search_result_type::iterator itr_tree = inner_trees.begin(), itr_tree_end = inner_trees.end();
372
for (; itr_tree != itr_tree_end; ++itr_tree)
373
{
374
inner_type* inner_tree = *itr_tree;
375
if (!inner_tree->is_tree_valid())
376
inner_tree->build_tree();
377
378
// Search all relevant inner trees and aggregate results.
379
inner_tree->search(y, result);
380
}
381
return result;
382
}
383
384
template<typename _Key, typename _Data>
385
void rectangle_set<_Key,_Data>::remove(data_type* data)
386
{
387
typename dataset_type::iterator itr_data = m_dataset.find(data);
388
if (itr_data == m_dataset.end())
389
// The data is not stored in this data structure.
390
return;
391
392
const rectangle& rect = itr_data->second;
393
394
// Find the corresponding inner segment tree for this outer interval.
395
interval_type outer(rect.x1, rect.x2);
396
typename inner_segment_map_type::iterator itr_seg = m_inner_map.find(outer);
397
if (itr_seg == m_inner_map.end())
398
throw general_error("inconsistent internal state: failed to find an internal segment tree for an existing interval.");
399
400
// Remove data from the inner segment tree.
401
inner_type* inner_tree = itr_seg->second;
402
inner_tree->remove(data);
403
if (inner_tree->empty())
404
{
405
// This inner tree is now empty. Erase it.
406
m_outer_segments.remove(inner_tree);
407
m_inner_map.erase(itr_seg);
408
}
409
410
// Remove it from the data set as well.
411
m_dataset.erase(data);
412
}
413
414
template<typename _Key, typename _Data>
415
void rectangle_set<_Key,_Data>::clear()
416
{
417
m_outer_segments.clear();
418
m_inner_map.clear();
419
m_dataset.clear();
420
}
421
422
template<typename _Key, typename _Data>
423
size_t rectangle_set<_Key,_Data>::size() const
424
{
425
return m_dataset.size();
426
}
427
428
template<typename _Key, typename _Data>
429
bool rectangle_set<_Key,_Data>::empty() const
430
{
431
return m_dataset.empty();
432
}
433
434
template<typename _Key, typename _Data>
435
void rectangle_set<_Key,_Data>::build_outer_segment_tree()
436
{
437
// Re-construct the outer segment tree from the authoritative inner tree
438
// map.
439
typename inner_segment_map_type::iterator itr = m_inner_map.begin(), itr_end = m_inner_map.end();
440
for (; itr != itr_end; ++itr)
441
{
442
const interval_type& interval = itr->first;
443
inner_type* tree = itr->second;
444
m_outer_segments.insert(interval.first, interval.second, tree);
445
}
446
}
447
448
#ifdef UNIT_TEST
449
template<typename _Key, typename _Data>
450
void rectangle_set<_Key,_Data>::dump_rectangles() const
451
{
452
using namespace std;
453
cout << "dump rectangles ------------------------------------------------" << endl;
454
if (m_dataset.empty())
455
{
456
cout << "No rectangles in the data set." << endl;
457
return;
458
}
459
460
typename dataset_type::const_iterator itr = m_dataset.begin(), itr_end = m_dataset.end();
461
for (; itr != itr_end; ++itr)
462
{
463
const rectangle& rect = itr->second;
464
cout << itr->first->name << ": (x1,y1,x2,y2) = "
465
<< "(" << rect.x1 << "," << rect.y1 << "," << rect.x2 << "," << rect.y2 << ")"
466
<< endl;
467
}
468
}
469
470
template<typename _Key, typename _Data>
471
bool rectangle_set<_Key,_Data>::verify_rectangles(const dataset_type& expected) const
472
{
473
if (m_dataset.size() != expected.size())
474
// Data sizes differ.
475
return false;
476
477
typename dataset_type::const_iterator itr_data = m_dataset.begin(), itr_data_end = m_dataset.end();
478
for (; itr_data != itr_data_end; ++itr_data)
479
{
480
const data_type* data = itr_data->first;
481
typename dataset_type::const_iterator itr_test = expected.find(data);
482
if (itr_test == expected.end())
483
// Pointer in one container but not in the other.
484
return false;
485
486
if (itr_data->second != itr_test->second)
487
// Rectangle positions and/or sizes differ.
488
return false;
489
}
490
491
return true;
492
}
493
#endif
494
495
}
496
497
#endif
Loggerhead is a web-based interface for Breezy
Version: 2.0.1