Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
spatial_overlap_region.hpp
1 // -*- C++ -*-
2 //
3 // Copyright Sylvain Bougerel 2009 - 2013.
4 // Distributed under the Boost Software License, Version 1.0.
5 // (See accompanying file COPYING or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 
16 #ifndef SPATIAL_OVERLAP_REGION_HPP
17 #define SPATIAL_OVERLAP_REGION_HPP
18 
19 #include "spatial_region.hpp"
20 
21 namespace spatial
22 {
59  template <typename Key, typename Compare,
60  typename Layout = llhh_layout_tag>
61  class overlap_bounds
62  : private Compare
63  {
64  public:
68  overlap_bounds() : Compare(), _target() { }
69 
73  overlap_bounds(const Compare& compare, const Key& target)
74  : Compare(compare), _target(target)
75  { }
76 
80  relative_order
81  operator()(dimension_type dim, dimension_type rank, const Key& key) const
82  {
83  return overlap_bounds_impl(dim, rank, key, Layout());
84  }
85 
86  private:
90  Key _target;
91 
92  relative_order overlap_bounds_impl
93  (dimension_type dim, dimension_type rank, const Key& key, llhh_layout_tag)
94  const
95  {
96  return (dim < (rank >> 1))
97  ? (Compare::operator()(dim, key, dim + (rank >> 1), _target)
98  ? matching : above)
99  : (Compare::operator()(dim - (rank >> 1), _target, dim, key)
100  ? matching : below);
101  }
102 
103  relative_order overlap_bounds_impl
104  (dimension_type dim, dimension_type, const Key& key, lhlh_layout_tag)
105  const
106  {
107  return ((dim % 2) == 0)
108  ? (Compare::operator()(dim, key, dim + 1, _target) ? matching : above)
109  : (Compare::operator()(dim - 1, _target, dim, key) ? matching : below);
110  }
111 
112  relative_order overlap_bounds_impl
113  (dimension_type dim, dimension_type rank, const Key& key, hhll_layout_tag)
114  const
115  {
116  return (dim < (rank >> 1))
117  ? (Compare::operator()(dim + (rank >> 1), _target, dim, key)
118  ? matching : below)
119  : (Compare::operator()(dim, key, dim - (rank >> 1), _target)
120  ? matching : above);
121  }
122 
123  relative_order overlap_bounds_impl
124  (dimension_type dim, dimension_type, const Key& key, hlhl_layout_tag)
125  const
126  {
127  return ((dim % 2) == 0)
128  ? (Compare::operator()(dim + 1, _target, dim, key) ? matching : below)
129  : (Compare::operator()(dim, key, dim - 1, _target) ? matching : above);
130  }
131  };
132 
140  template <typename Tp, typename Layout>
142  overlap_bounds<typename container_traits<Tp>::key_type,
143  typename container_traits<Tp>::key_compare,
144  Layout>
145  make_overlap_bounds
146  (const Tp& container,
147  const typename container_traits<Tp>::key_type& target,
148  Layout tag)
149  {
150  ::spatial::except::check_box(container, target, tag);
151  return overlap_bounds
152  <typename container_traits<Tp>::key_type,
153  typename container_traits<Tp>::key_compare, Layout>
154  (container.key_comp(), target);
155  }
156 
157  template <typename Tp>
158  overlap_bounds<typename container_traits<Tp>::key_type,
159  typename container_traits<Tp>::key_compare>
160  make_overlap_bounds
161  (const Tp& container,
162  const typename container_traits<Tp>::key_type& target)
163  { return make_overlap_bounds(container, target, llhh_layout_tag()); }
165 
166  template<typename Ct, typename Layout = llhh_layout_tag>
167  struct overlap_region_iterator
168  : region_iterator
169  <Ct, overlap_bounds<typename container_traits<Ct>::key_type,
170  typename container_traits<Ct>::key_compare,
171  Layout> >
172  {
174  overlap_region_iterator() { }
175 
176  overlap_region_iterator
177  (const region_iterator
178  <Ct, overlap_bounds<typename container_traits<Ct>::key_type,
179  typename container_traits<Ct>::key_compare,
180  Layout> >& other)
181  : region_iterator
182  <Ct, overlap_bounds<typename container_traits<Ct>::key_type,
183  typename container_traits<Ct>::key_compare,
184  Layout> >(other) { }
185  };
186 
187  template<typename Ct, typename Layout>
188  struct overlap_region_iterator<const Ct, Layout>
189  : region_iterator
190  <const Ct, overlap_bounds<typename container_traits<Ct>::key_type,
191  typename container_traits<Ct>::key_compare,
192  Layout> >
193  {
195  overlap_region_iterator() { }
196 
197  overlap_region_iterator
198  (const region_iterator
199  <const Ct, overlap_bounds<typename container_traits<Ct>::key_type,
200  typename container_traits<Ct>::key_compare,
201  Layout> >& other)
202  : region_iterator
203  <const Ct, overlap_bounds<typename container_traits<Ct>::key_type,
204  typename container_traits<Ct>::key_compare,
205  Layout> >
206  (other) { }
207 
208  overlap_region_iterator
209  (const region_iterator
210  <Ct, overlap_bounds<typename container_traits<Ct>::key_type,
211  typename container_traits<Ct>::key_compare,
212  Layout> >& other)
213  : region_iterator
214  <const Ct, overlap_bounds<typename container_traits<Ct>::key_type,
215  typename container_traits<Ct>::key_compare,
216  Layout> >
217  (other) { }
218  };
219 
220  template<typename Ct, typename Layout = llhh_layout_tag>
221  struct overlap_region_iterator_pair
222  : region_iterator_pair
223  <Ct, overlap_bounds<typename container_traits<Ct>::key_type,
224  typename container_traits<Ct>::key_compare,
225  Layout> >
226  {
228  overlap_region_iterator_pair() { }
229 
230  overlap_region_iterator_pair
231  (const region_iterator
232  <Ct, overlap_bounds<typename container_traits<Ct>::key_type,
233  typename container_traits<Ct>::key_compare,
234  Layout> >& a,
235  const region_iterator
236  <Ct, overlap_bounds<typename container_traits<Ct>::key_type,
237  typename container_traits<Ct>::key_compare,
238  Layout> >& b)
239  : region_iterator_pair
240  <Ct, overlap_bounds<typename container_traits<Ct>::key_type,
241  typename container_traits<Ct>::key_compare,
242  Layout> >
243  (a, b) { }
244  };
245 
246  template<typename Ct, typename Layout>
247  struct overlap_region_iterator_pair<const Ct, Layout>
248  : region_iterator_pair
249  <const Ct, overlap_bounds<typename container_traits<Ct>::key_type,
250  typename container_traits<Ct>::key_compare,
251  Layout> >
252  {
254  overlap_region_iterator_pair() { }
255 
256  overlap_region_iterator_pair
257  (const region_iterator
258  <const Ct, overlap_bounds<typename container_traits<Ct>::key_type,
259  typename container_traits<Ct>::key_compare,
260  Layout> >& a,
261  const region_iterator
262  <const Ct, overlap_bounds<typename container_traits<Ct>::key_type,
263  typename container_traits<Ct>::key_compare,
264  Layout> >& b)
265  : region_iterator_pair
266  <const Ct, overlap_bounds<typename container_traits<Ct>::key_type,
267  typename container_traits<Ct>::key_compare,
268  Layout> >
269  (a, b) { }
270 
271  overlap_region_iterator_pair
272  (const overlap_region_iterator_pair<Ct>& other)
273  : region_iterator_pair
274  <const Ct, overlap_bounds<typename container_traits<Ct>::key_type,
275  typename container_traits<Ct>::key_compare,
276  Layout> >
277  (other) { }
278  };
279 
280  template <typename Ct>
281  inline overlap_region_iterator<Ct>
282  overlap_region_end(Ct& container,
283  const typename container_traits<Ct>::key_type& target)
284  {
285  return region_end
286  (container, make_overlap_bounds(container, target, llhh_layout_tag()));
287  }
288 
289  template <typename Ct, typename Layout>
290  inline overlap_region_iterator<Ct, Layout>
291  overlap_region_end(Ct& container,
292  const typename container_traits<Ct>::key_type& target,
293  const Layout& layout)
294  {
295  return region_end
296  (container, make_overlap_bounds(container, target, layout));
297  }
298 
299  template <typename Ct>
300  inline overlap_region_iterator<const Ct>
301  overlap_region_end(const Ct& container,
302  const typename container_traits<Ct>::key_type& target)
303  {
304  return _regionend
305  (container, make_overlap_bounds(container, target, llhh_layout_tag()));
306  }
307 
308  template <typename Ct, typename Layout>
309  inline overlap_region_iterator<const Ct, Layout>
310  overlap_region_end(const Ct& container,
311  const typename container_traits<Ct>::key_type& target,
312  const Layout& layout)
313  {
314  return region_end
315  (container, make_overlap_bounds(container, target, layout));
316  }
317 
318  template <typename Ct>
319  inline overlap_region_iterator<const Ct>
320  overlap_region_cend(const Ct& container,
321  const typename container_traits<Ct>::key_type& target)
322  {
323  return region_cend
324  (container, make_overlap_bounds(container, target, llhh_layout_tag()));
325  }
326 
327  template <typename Ct, typename Layout>
328  inline overlap_region_iterator<const Ct, Layout>
329  overlap_region_cend(const Ct& container,
330  const typename container_traits<Ct>::key_type& target,
331  const Layout& layout)
332  {
333  return region_cend
334  (container, make_overlap_bounds(container, target, layout));
335  }
336 
337  template <typename Ct>
338  inline overlap_region_iterator<Ct>
339  overlap_region_begin(Ct& container,
340  const typename container_traits<Ct>::key_type& target)
341  {
342  return region_begin
343  (container, make_overlap_bounds(container, target, llhh_layout_tag()));
344  }
345 
346  template <typename Ct, typename Layout>
347  inline overlap_region_iterator<Ct, Layout>
348  overlap_region_begin(Ct& container,
349  const typename container_traits<Ct>::key_type& target,
350  const Layout& layout)
351  {
352  return region_begin
353  (container, make_overlap_bounds(container, target, layout));
354  }
355 
356  template <typename Ct>
357  inline overlap_region_iterator<const Ct>
358  overlap_region_begin(const Ct& container,
359  const typename container_traits<Ct>::key_type& target)
360  {
361  return _regionbegin
362  (container, make_overlap_bounds(container, target, llhh_layout_tag()));
363  }
364 
365  template <typename Ct, typename Layout>
366  inline overlap_region_iterator<const Ct, Layout>
367  overlap_region_begin(const Ct& container,
368  const typename container_traits<Ct>::key_type& target,
369  const Layout& layout)
370  {
371  return region_begin
372  (container, make_overlap_bounds(container, target, layout));
373  }
374 
375  template <typename Ct>
376  inline overlap_region_iterator<const Ct>
377  overlap_region_cbegin(const Ct& container,
378  const typename container_traits<Ct>::key_type& target)
379  {
380  return region_cbegin
381  (container, make_overlap_bounds(container, target, llhh_layout_tag()));
382  }
383 
384  template <typename Ct, typename Layout>
385  inline overlap_region_iterator<const Ct, Layout>
386  overlap_region_cbegin(const Ct& container,
387  const typename container_traits<Ct>::key_type& target,
388  const Layout& layout)
389  {
390  return region_cbegin
391  (container, make_overlap_bounds(container, target, layout));
392  }
393 
394  template <typename Ct>
395  inline overlap_region_iterator_pair<Ct>
396  overlap_region_range(Ct& container,
397  const typename container_traits<Ct>::key_type& target)
398  {
399  return region_range
400  (container, make_overlap_bounds(container, target, llhh_layout_tag()));
401  }
402 
403  template <typename Ct, typename Layout>
404  inline overlap_region_iterator_pair<Ct, Layout>
405  overlap_region_range(Ct& container,
406  const typename container_traits<Ct>::key_type& target,
407  const Layout& layout)
408  {
409  return region_range
410  (container, make_overlap_bounds(container, target, layout));
411  }
412 
413  template <typename Ct>
414  inline overlap_region_iterator_pair<const Ct>
415  overlap_region_range(const Ct& container,
416  const typename container_traits<Ct>::key_type& target)
417  {
418  return region_range
419  (container, make_overlap_bounds(container, target, llhh_layout_tag()));
420  }
421 
422  template <typename Ct, typename Layout>
423  inline overlap_region_iterator_pair<const Ct, Layout>
424  overlap_region_range(const Ct& container,
425  const typename container_traits<Ct>::key_type& target,
426  const Layout& layout)
427  {
428  return region_range
429  (container, make_overlap_bounds(container, target, layout));
430  }
431 
432  template <typename Ct>
433  inline overlap_region_iterator_pair<const Ct>
434  overlap_region_crange(const Ct& container,
435  const typename container_traits<Ct>::key_type& target)
436  {
437  return region_crange
438  (container, make_overlap_bounds(container, target, llhh_layout_tag()));
439  }
440 
441  template <typename Ct, typename Layout>
442  inline overlap_region_iterator_pair<const Ct, Layout>
443  overlap_region_crange(const Ct& container,
444  const typename container_traits<Ct>::key_type& target,
445  const Layout& layout)
446  {
447  return region_crange
448  (container, make_overlap_bounds(container, target, layout));
449  }
450 
451 } // namespace spatial
452 
453 #endif // SPATIAL_OVERLAP_REGION_HPP
spatial::overlap_region_begin
overlap_region_iterator< Ct > overlap_region_begin(Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_overlap_region.hpp:339
spatial::region_iterator
This type provides both an iterator and a constant iterator to iterate through all elements of a tree...
Definition: spatial_region.hpp:140
spatial::overlap_region_end
overlap_region_iterator< Ct > overlap_region_end(Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_overlap_region.hpp:282
spatial::overlap_region_crange
overlap_region_iterator_pair< const Ct > overlap_region_crange(const Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_overlap_region.hpp:434
spatial::hhll_layout_tag
Represents a coordinate layout for the box.
Definition: spatial.hpp:126
spatial::llhh_layout_tag
Represents a coordinate layout for the box.
Definition: spatial.hpp:97
spatial::overlap_region_iterator_pair< const Ct, Layout >::overlap_region_iterator_pair
overlap_region_iterator_pair()
defctor
Definition: spatial_overlap_region.hpp:254
spatial::region_cend
region_iterator< const Ct, Predicate > region_cend(const Ct &container, const Predicate &pred)
Definition: spatial_region.hpp:423
spatial::region_iterator_pair
This structure defines a pair of mutable region iterator.
Definition: spatial_region.hpp:502
spatial::overlap_bounds::overlap_bounds_impl
relative_order overlap_bounds_impl(dimension_type dim, dimension_type rank, const Key &key, llhh_layout_tag) const
Definition: spatial_overlap_region.hpp:93
spatial::overlap_region_iterator_pair::overlap_region_iterator_pair
overlap_region_iterator_pair()
defctor
Definition: spatial_overlap_region.hpp:228
spatial::container_traits::key_type
Tp::key_type key_type
The type representing the key managed by the container.
Definition: traits.hpp:48
spatial::overlap_bounds::overlap_bounds
overlap_bounds()
The default constructor leaves everything un-initialized.
Definition: spatial_overlap_region.hpp:68
spatial::overlap_bounds
This class is a model of Region Predicate that matches any keys that is overlapping with a given test...
Definition: spatial_overlap_region.hpp:61
spatial::region_begin
region_iterator< Ct, Predicate > region_begin(Ct &container, const Predicate &pred)
Definition: spatial_region.hpp:449
spatial::region_range
region_iterator_pair< Ct, Predicate > region_range(Ct &container, const Predicate &pred)
Returns a spatial::region_iterator_pair where first points to the first element matching the predicat...
Definition: spatial_region.hpp:570
spatial::container_traits
The traits type for all containers in the spatial namespace.
Definition: traits.hpp:42
spatial::region_cbegin
region_iterator< const Ct, Predicate > region_cbegin(const Ct &container, const Predicate &pred)
Definition: spatial_region.hpp:469
spatial::relative_order
relative_order
Defines values for relative ordering.
Definition: spatial.hpp:81
spatial::dimension_type
std::size_t dimension_type
Defines the type for the dimension as being a size.
Definition: spatial.hpp:71
spatial::region_end
region_iterator< Ct, Predicate > region_end(Ct &container, const Predicate &pred)
Definition: spatial_region.hpp:405
spatial::overlap_region_iterator< const Ct, Layout >::overlap_region_iterator
overlap_region_iterator()
defctor
Definition: spatial_overlap_region.hpp:195
spatial::overlap_bounds::overlap_bounds
overlap_bounds(const Compare &compare, const Key &target)
Set the target box and the comparator to the appropriate value.
Definition: spatial_overlap_region.hpp:73
spatial::overlap_bounds::operator()
relative_order operator()(dimension_type dim, dimension_type rank, const Key &key) const
The operator that tells wheather the point is in region or not.
Definition: spatial_overlap_region.hpp:81
spatial::lhlh_layout_tag
Represents a coordinate layout for the box.
Definition: spatial.hpp:112
spatial::overlap_region_range
overlap_region_iterator_pair< Ct > overlap_region_range(Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_overlap_region.hpp:396
spatial
The main namespace used in the library.
Definition: algorithm.hpp:23
spatial::region_crange
region_iterator_pair< const Ct, Predicate > region_crange(const Ct &container, const Predicate &pred)
This overload works only on constant containers and will return a set of constant iterators...
Definition: spatial_region.hpp:592
spatial::overlap_bounds::_target
Key _target
The box value that will be used for overlaping comparison.
Definition: spatial_overlap_region.hpp:90
spatial::overlap_region_cend
overlap_region_iterator< const Ct > overlap_region_cend(const Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_overlap_region.hpp:320
spatial::hlhl_layout_tag
Represents a coordinate layout for the box.
Definition: spatial.hpp:141
spatial::overlap_region_iterator
Definition: spatial_overlap_region.hpp:167
spatial::overlap_region_iterator::overlap_region_iterator
overlap_region_iterator()
defctor
Definition: spatial_overlap_region.hpp:174
spatial::overlap_region_cbegin
overlap_region_iterator< const Ct > overlap_region_cbegin(const Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_overlap_region.hpp:377
spatial::make_overlap_bounds
overlap_bounds< typename container_traits< Tp >::key_type, typename container_traits< Tp >::key_compare, Layout > make_overlap_bounds(const Tp &container, const typename container_traits< Tp >::key_type &target, Layout tag)
Overlap bounds factory that takes in a container, a key and returns an overlap_bounds type...
Definition: spatial_overlap_region.hpp:146
spatial::overlap_region_iterator_pair
Definition: spatial_overlap_region.hpp:221