Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
spatial_enclosed_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_ENCLOSED_REGION_HPP
17 #define SPATIAL_ENCLOSED_REGION_HPP
18 
19 #include "spatial_region.hpp"
20 
21 namespace spatial
22 {
56  template <typename Key, typename Compare,
57  typename Layout = llhh_layout_tag>
58  class enclosed_bounds
59  : private Compare
60  {
61  public:
65  enclosed_bounds() : Compare(), _target() { }
66 
70  enclosed_bounds(const Compare& compare, const Key& target)
71  : Compare(compare), _target(target)
72  { }
73 
77  relative_order
78  operator()(dimension_type dim, dimension_type rank, const Key& key) const
79  {
80  return enclose_bounds_impl(dim, rank, key, Layout());
81  }
82 
83  private:
87  Key _target;
88 
89  relative_order enclose_bounds_impl
90  (dimension_type dim, dimension_type rank, const Key& key, llhh_layout_tag)
91  const
92  {
93  return (dim < (rank >> 1))
94  ? (Compare::operator()(dim , key, _target)
95  ? below : (Compare::operator()(dim + (rank >> 1), _target, dim, key)
96  ? above : matching))
97  : (Compare::operator()(dim, key, dim - (rank >> 1), _target)
98  ? below : (Compare::operator()(dim, _target, key)
99  ? above : matching));
100  }
101 
102  relative_order enclose_bounds_impl
103  (dimension_type dim, dimension_type, const Key& key, lhlh_layout_tag)
104  const
105  {
106  return ((dim % 2) == 0)
107  ? (Compare::operator()(dim , key, _target)
108  ? below : (Compare::operator()(dim + 1, _target, dim, key)
109  ? above : matching))
110  : (Compare::operator()(dim, key, dim - 1, _target)
111  ? below : (Compare::operator()(dim, _target, key)
112  ? above : matching));
113  }
114 
115  relative_order enclose_bounds_impl
116  (dimension_type dim, dimension_type rank, const Key& key, hhll_layout_tag)
117  const
118  {
119  return (dim < (rank >> 1))
120  ? (Compare::operator()(dim , _target, key)
121  ? above : (Compare::operator()(dim, key, dim + (rank >> 1), _target)
122  ? below : matching))
123  : (Compare::operator()(dim - (rank >> 1), _target, dim, key)
124  ? above : (Compare::operator()(dim, key, _target)
125  ? below : matching));
126  }
127 
128  relative_order enclose_bounds_impl
129  (dimension_type dim, dimension_type, const Key& key, hlhl_layout_tag)
130  const
131  {
132  return ((dim % 2) == 0)
133  ? (Compare::operator()(dim , _target, key)
134  ? above : (Compare::operator()(dim, key, dim + 1, _target)
135  ? below : matching))
136  : (Compare::operator()(dim - 1, _target, dim, key)
137  ? above : (Compare::operator()(dim, key, _target)
138  ? below : matching));
139  }
140  };
141 
149  template <typename Tp, typename Layout>
151  enclosed_bounds<typename container_traits<Tp>::key_type,
152  typename container_traits<Tp>::key_compare,
153  Layout>
154  make_enclosed_bounds
155  (const Tp& container,
156  const typename container_traits<Tp>::key_type& target,
157  Layout tag)
158  {
159  except::check_box(container, target, tag);
160  return enclosed_bounds
161  <typename container_traits<Tp>::key_type,
162  typename container_traits<Tp>::key_compare, Layout>
163  (container.key_comp(), target);
164  }
165 
166  template <typename Tp>
167  enclosed_bounds<typename container_traits<Tp>::key_type,
168  typename container_traits<Tp>::key_compare>
169  make_enclosed_bounds
170  (const Tp& container,
171  const typename container_traits<Tp>::key_type& target)
172  { return make_enclosed_bounds(container, target, llhh_layout_tag()); }
174 
175  template<typename Ct, typename Layout = llhh_layout_tag>
176  struct enclosed_region_iterator
177  : region_iterator
178  <Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
179  typename container_traits<Ct>::key_compare,
180  Layout> >
181  {
182  enclosed_region_iterator() { }
183 
184  enclosed_region_iterator
185  (const region_iterator
186  <Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
187  typename container_traits<Ct>::key_compare,
188  Layout> >& other)
189  : region_iterator
190  <Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
191  typename container_traits<Ct>::key_compare,
192  Layout> >(other) { }
193  };
194 
195  template<typename Ct, typename Layout>
196  struct enclosed_region_iterator<const Ct, Layout>
197  : region_iterator
198  <const Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
199  typename container_traits<Ct>::key_compare,
200  Layout> >
201  {
202  enclosed_region_iterator() { }
203 
204  enclosed_region_iterator
205  (const region_iterator
206  <const Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
207  typename container_traits<Ct>::key_compare,
208  Layout> >& other)
209  : region_iterator
210  <const Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
211  typename container_traits<Ct>::key_compare,
212  Layout> >
213  (other) { }
214 
215  enclosed_region_iterator
216  (const region_iterator
217  <Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
218  typename container_traits<Ct>::key_compare,
219  Layout> >& other)
220  : region_iterator
221  <const Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
222  typename container_traits<Ct>::key_compare,
223  Layout> >
224  (other) { }
225  };
226 
227  template<typename Ct, typename Layout = llhh_layout_tag>
228  struct enclosed_region_iterator_pair
229  : region_iterator_pair
230  <Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
231  typename container_traits<Ct>::key_compare,
232  Layout> >
233  {
234  enclosed_region_iterator_pair() { }
235 
236  enclosed_region_iterator_pair
237  (const region_iterator
238  <Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
239  typename container_traits<Ct>::key_compare,
240  Layout> >& a,
241  const region_iterator
242  <Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
243  typename container_traits<Ct>::key_compare,
244  Layout> >& b)
245  : region_iterator_pair
246  <Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
247  typename container_traits<Ct>::key_compare,
248  Layout> >
249  (a, b) { }
250  };
251 
252  template<typename Ct, typename Layout>
253  struct enclosed_region_iterator_pair<const Ct, Layout>
254  : region_iterator_pair
255  <const Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
256  typename container_traits<Ct>::key_compare,
257  Layout> >
258  {
259  enclosed_region_iterator_pair() { }
260 
261  enclosed_region_iterator_pair
262  (const region_iterator
263  <const Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
264  typename container_traits<Ct>::key_compare,
265  Layout> >& a,
266  const region_iterator
267  <const Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
268  typename container_traits<Ct>::key_compare,
269  Layout> >& b)
270  : region_iterator_pair
271  <const Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
272  typename container_traits<Ct>::key_compare,
273  Layout> >
274  (a, b) { }
275 
276  enclosed_region_iterator_pair
277  (const enclosed_region_iterator_pair<Ct>& other)
278  : region_iterator_pair
279  <const Ct, enclosed_bounds<typename container_traits<Ct>::key_type,
280  typename container_traits<Ct>::key_compare,
281  Layout> >
282  (other) { }
283  };
284 
285  template <typename Ct>
286  inline enclosed_region_iterator<Ct>
287  enclosed_region_end(Ct& container,
288  const typename container_traits<Ct>::key_type& target)
289  {
290  return region_end
291  (container, make_enclosed_bounds(container, target, llhh_layout_tag()));
292  }
293 
294  template <typename Ct, typename Layout>
295  inline enclosed_region_iterator<Ct, Layout>
296  enclosed_region_end(Ct& container,
297  const typename container_traits<Ct>::key_type& target,
298  const Layout& layout)
299  {
300  return region_end
301  (container, make_enclosed_bounds(container, target, layout));
302  }
303 
304  template <typename Ct>
305  inline enclosed_region_iterator<const Ct>
306  enclosed_region_end(const Ct& container,
307  const typename container_traits<Ct>::key_type& target)
308  {
309  return _regionend
310  (container, make_enclosed_bounds(container, target, llhh_layout_tag()));
311  }
312 
313  template <typename Ct, typename Layout>
314  inline enclosed_region_iterator<const Ct, Layout>
315  enclosed_region_end(const Ct& container,
316  const typename container_traits<Ct>::key_type& target,
317  const Layout& layout)
318  {
319  return region_end
320  (container, make_enclosed_bounds(container, target, layout));
321  }
322 
323  template <typename Ct>
324  inline enclosed_region_iterator<const Ct>
325  enclosed_region_cend(const Ct& container,
326  const typename container_traits<Ct>::key_type& target)
327  {
328  return region_cend
329  (container, make_enclosed_bounds(container, target, llhh_layout_tag()));
330  }
331 
332  template <typename Ct, typename Layout>
333  inline enclosed_region_iterator<const Ct, Layout>
334  enclosed_region_cend(const Ct& container,
335  const typename container_traits<Ct>::key_type& target,
336  const Layout& layout)
337  {
338  return region_cend
339  (container, make_enclosed_bounds(container, target, layout));
340  }
341 
342  template <typename Ct>
343  inline enclosed_region_iterator<Ct>
344  enclosed_region_begin(Ct& container,
345  const typename container_traits<Ct>::key_type& target)
346  {
347  return region_begin
348  (container, make_enclosed_bounds(container, target, llhh_layout_tag()));
349  }
350 
351  template <typename Ct, typename Layout>
352  inline enclosed_region_iterator<Ct, Layout>
353  enclosed_region_begin(Ct& container,
354  const typename container_traits<Ct>::key_type& target,
355  const Layout& layout)
356  {
357  return region_begin
358  (container, make_enclosed_bounds(container, target, layout));
359  }
360 
361  template <typename Ct>
362  inline enclosed_region_iterator<const Ct>
363  enclosed_region_begin(const Ct& container,
364  const typename container_traits<Ct>::key_type& target)
365  {
366  return _regionbegin
367  (container, make_enclosed_bounds(container, target, llhh_layout_tag()));
368  }
369 
370  template <typename Ct, typename Layout>
371  inline enclosed_region_iterator<const Ct, Layout>
372  enclosed_region_begin(const Ct& container,
373  const typename container_traits<Ct>::key_type& target,
374  const Layout& layout)
375  {
376  return region_begin
377  (container, make_enclosed_bounds(container, target, layout));
378  }
379 
380  template <typename Ct>
381  inline enclosed_region_iterator<const Ct>
382  enclosed_region_cbegin(const Ct& container,
383  const typename container_traits<Ct>::key_type& target)
384  {
385  return region_cbegin
386  (container, make_enclosed_bounds(container, target, llhh_layout_tag()));
387  }
388 
389  template <typename Ct, typename Layout>
390  inline enclosed_region_iterator<const Ct, Layout>
391  enclosed_region_cbegin(const Ct& container,
392  const typename container_traits<Ct>::key_type& target,
393  const Layout& layout)
394  {
395  return region_cbegin
396  (container, make_enclosed_bounds(container, target, layout));
397  }
398 
399  template <typename Ct>
400  inline enclosed_region_iterator_pair<Ct>
401  enclosed_region_range(Ct& container,
402  const typename container_traits<Ct>::key_type& target)
403  {
404  return region_range
405  (container, make_enclosed_bounds(container, target, llhh_layout_tag()));
406  }
407 
408  template <typename Ct, typename Layout>
409  inline enclosed_region_iterator_pair<Ct, Layout>
410  enclosed_region_range(Ct& container,
411  const typename container_traits<Ct>::key_type& target,
412  const Layout& layout)
413  {
414  return region_range
415  (container, make_enclosed_bounds(container, target, layout));
416  }
417 
418  template <typename Ct>
419  inline enclosed_region_iterator_pair<const Ct>
420  enclosed_region_range(const Ct& container,
421  const typename container_traits<Ct>::key_type& target)
422  {
423  return region_range
424  (container, make_enclosed_bounds(container, target, llhh_layout_tag()));
425  }
426 
427  template <typename Ct, typename Layout>
428  inline enclosed_region_iterator_pair<const Ct, Layout>
429  enclosed_region_range(const Ct& container,
430  const typename container_traits<Ct>::key_type& target,
431  const Layout& layout)
432  {
433  return region_range
434  (container, make_enclosed_bounds(container, target, layout));
435  }
436 
437  template <typename Ct>
438  inline enclosed_region_iterator_pair<const Ct>
439  enclosed_region_crange(const Ct& container,
440  const typename container_traits<Ct>::key_type& target)
441  {
442  return region_crange
443  (container, make_enclosed_bounds(container, target, llhh_layout_tag()));
444  }
445 
446  template <typename Ct, typename Layout>
447  inline enclosed_region_iterator_pair<const Ct, Layout>
448  enclosed_region_crange(const Ct& container,
449  const typename container_traits<Ct>::key_type& target,
450  const Layout& layout)
451  {
452  return region_crange
453  (container, make_enclosed_bounds(container, target, layout));
454  }
455 
456 } // namespace spatial
457 
458 #endif // SPATIAL_ENCLOSED_REGION_HPP
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::enclosed_region_iterator
Definition: spatial_enclosed_region.hpp:176
spatial::enclosed_region_cbegin
enclosed_region_iterator< const Ct > enclosed_region_cbegin(const Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_enclosed_region.hpp:382
spatial::hhll_layout_tag
Represents a coordinate layout for the box.
Definition: spatial.hpp:126
spatial::enclosed_region_iterator_pair< const Ct, Layout >::enclosed_region_iterator_pair
enclosed_region_iterator_pair()
Definition: spatial_enclosed_region.hpp:259
spatial::enclosed_region_iterator_pair
Definition: spatial_enclosed_region.hpp:228
spatial::enclosed_bounds::_target
Key _target
The box value that will be used for the enclosing comparison.
Definition: spatial_enclosed_region.hpp:87
spatial::enclosed_region_end
enclosed_region_iterator< Ct > enclosed_region_end(Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_enclosed_region.hpp:287
spatial::make_enclosed_bounds
enclosed_bounds< typename container_traits< Tp >::key_type, typename container_traits< Tp >::key_compare, Layout > make_enclosed_bounds(const Tp &container, const typename container_traits< Tp >::key_type &target, Layout tag)
Enclosed bounds factory that takes in a container, a key and returns an enclosed_bounds type...
Definition: spatial_enclosed_region.hpp:155
spatial::llhh_layout_tag
Represents a coordinate layout for the box.
Definition: spatial.hpp:97
spatial::enclosed_region_begin
enclosed_region_iterator< Ct > enclosed_region_begin(Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_enclosed_region.hpp:344
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::container_traits::key_type
Tp::key_type key_type
The type representing the key managed by the container.
Definition: traits.hpp:48
spatial::enclosed_bounds
This region predicate matches keys that are enclosed or equal to a target box.
Definition: spatial_enclosed_region.hpp:58
spatial::enclosed_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_enclosed_region.hpp:78
spatial::except::check_box
void check_box(const Tp &container, const typename container_traits< Tp >::key_type &box, llhh_layout_tag)
Checks that all coordinates of a box are matching with the layout specified or else, raise an invalid_box exception.
Definition: spatial_except.hpp:190
spatial::region_begin
region_iterator< Ct, Predicate > region_begin(Ct &container, const Predicate &pred)
Definition: spatial_region.hpp:449
spatial::enclosed_region_iterator_pair::enclosed_region_iterator_pair
enclosed_region_iterator_pair()
Definition: spatial_enclosed_region.hpp:234
spatial::enclosed_region_iterator< const Ct, Layout >::enclosed_region_iterator
enclosed_region_iterator()
Definition: spatial_enclosed_region.hpp:202
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::enclosed_bounds::enclosed_bounds
enclosed_bounds(const Compare &compare, const Key &target)
Set the target box and the comparator to the appropriate value.
Definition: spatial_enclosed_region.hpp:70
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::lhlh_layout_tag
Represents a coordinate layout for the box.
Definition: spatial.hpp:112
spatial::enclosed_region_cend
enclosed_region_iterator< const Ct > enclosed_region_cend(const Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_enclosed_region.hpp:325
spatial::enclosed_bounds::enclosed_bounds
enclosed_bounds()
The default constructor leaves everything un-initialized.
Definition: spatial_enclosed_region.hpp:65
spatial
The main namespace used in the library.
Definition: algorithm.hpp:23
spatial::enclosed_region_range
enclosed_region_iterator_pair< Ct > enclosed_region_range(Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_enclosed_region.hpp:401
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::enclosed_region_crange
enclosed_region_iterator_pair< const Ct > enclosed_region_crange(const Ct &container, const typename container_traits< Ct >::key_type &target)
Definition: spatial_enclosed_region.hpp:439
spatial::hlhl_layout_tag
Represents a coordinate layout for the box.
Definition: spatial.hpp:141
spatial::enclosed_bounds::enclose_bounds_impl
relative_order enclose_bounds_impl(dimension_type dim, dimension_type rank, const Key &key, llhh_layout_tag) const
Definition: spatial_enclosed_region.hpp:90
spatial::enclosed_region_iterator::enclosed_region_iterator
enclosed_region_iterator()
Definition: spatial_enclosed_region.hpp:182