Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
spatial_open_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_OPEN_REGION_HPP
17 #define SPATIAL_OPEN_REGION_HPP
18 
19 #include "spatial_region.hpp"
20 
21 namespace spatial
22 {
40  template <typename Key, typename Compare>
41  class open_bounds
42  : private Compare // empty member optimization
43  {
44  public:
48  open_bounds()
49  : Compare(), _lower(), _upper() { }
50 
64  open_bounds(const Compare& compare, const Key& lower,
65  const Key& upper)
66  : Compare(compare), _lower(lower), _upper(upper)
67  { }
68 
81  relative_order
82  operator()(dimension_type dim, dimension_type, const Key& key) const
83  {
84  return (!Compare::operator()(dim, _lower, key)
85  ? below
86  : (Compare::operator()(dim, key, _upper)
87  ? matching
88  : above));
89  }
90 
91  private:
95  Key _lower;
96 
100  Key _upper;
101  };
102 
121  template <typename Tp>
122  open_bounds<typename container_traits<Tp>::key_type,
123  typename container_traits<Tp>::key_compare>
124  make_open_bounds
125  (const Tp& container,
126  const typename container_traits<Tp>::key_type& lower,
127  const typename container_traits<Tp>::key_type& upper)
128  {
129  except::check_open_bounds(container, lower, upper);
130  return open_bounds
131  <typename container_traits<Tp>::key_type,
132  typename container_traits<Tp>::key_compare>
133  (container.key_comp(), lower, upper);
134  }
135 
136  template<typename Ct>
137  struct open_region_iterator
138  : region_iterator
139  <Ct, open_bounds<typename container_traits<Ct>::key_type,
140  typename container_traits<Ct>::key_compare> >
141  {
142  open_region_iterator() { }
143 
144  open_region_iterator
145  (const region_iterator
146  <Ct, open_bounds<typename container_traits<Ct>::key_type,
147  typename container_traits<Ct>::key_compare> >& other)
148  : region_iterator
149  <Ct, open_bounds<typename container_traits<Ct>::key_type,
150  typename container_traits<Ct>::key_compare> >
151  (other) { }
152  };
153 
154  template<typename Ct>
155  struct open_region_iterator<const Ct>
156  : region_iterator
157  <const Ct, open_bounds<typename container_traits<Ct>::key_type,
158  typename container_traits<Ct>::key_compare> >
159  {
160  open_region_iterator() { }
161 
162  open_region_iterator
163  (const region_iterator
164  <const Ct, open_bounds<typename container_traits<Ct>::key_type,
165  typename container_traits<Ct>::key_compare> >&
166  other)
167  : region_iterator
168  <const Ct, open_bounds<typename container_traits<Ct>::key_type,
169  typename container_traits<Ct>::key_compare> >
170  (other) { }
171 
172  open_region_iterator
173  (const region_iterator
174  <Ct, open_bounds<typename container_traits<Ct>::key_type,
175  typename container_traits<Ct>::key_compare> >& other)
176  : region_iterator
177  <const Ct, open_bounds<typename container_traits<Ct>::key_type,
178  typename container_traits<Ct>::key_compare> >
179  (other) { }
180  };
181 
182  template<typename Ct>
183  struct open_region_iterator_pair
184  : region_iterator_pair
185  <Ct, open_bounds<typename container_traits<Ct>::key_type,
186  typename container_traits<Ct>::key_compare> >
187  {
188  open_region_iterator_pair() { }
189 
190  open_region_iterator_pair
191  (const region_iterator
192  <Ct, open_bounds<typename container_traits<Ct>::key_type,
193  typename container_traits<Ct>::key_compare> >& a,
194  const region_iterator
195  <Ct, open_bounds<typename container_traits<Ct>::key_type,
196  typename container_traits<Ct>::key_compare> >& b)
197  : region_iterator_pair
198  <Ct, open_bounds<typename container_traits<Ct>::key_type,
199  typename container_traits<Ct>::key_compare> >
200  (a, b) { }
201  };
202 
203  template<typename Ct>
204  struct open_region_iterator_pair<const Ct>
205  : region_iterator_pair
206  <const Ct, open_bounds<typename container_traits<Ct>::key_type,
207  typename container_traits<Ct>::key_compare> >
208  {
209  open_region_iterator_pair() { }
210 
211  open_region_iterator_pair
212  (const region_iterator
213  <const Ct, open_bounds<typename container_traits<Ct>::key_type,
214  typename container_traits<Ct>::key_compare> >& a,
215  const region_iterator
216  <const Ct, open_bounds<typename container_traits<Ct>::key_type,
217  typename container_traits<Ct>::key_compare> >& b)
218  : region_iterator_pair
219  <const Ct, open_bounds<typename container_traits<Ct>::key_type,
220  typename container_traits<Ct>::key_compare> >
221  (a, b) { }
222 
223  open_region_iterator_pair
224  (const region_iterator_pair
225  <Ct, open_bounds<typename container_traits<Ct>::key_type,
226  typename container_traits<Ct>::key_compare> >& other)
227  : region_iterator_pair
228  <const Ct, open_bounds<typename container_traits<Ct>::key_type,
229  typename container_traits<Ct>::key_compare> >
230  (other) { }
231  };
232 
233  template <typename Ct>
234  inline open_region_iterator<Ct>
235  open_region_end(Ct& container,
236  const typename container_traits<Ct>::key_type& lower,
237  const typename container_traits<Ct>::key_type& upper)
238  { return region_end(container, make_open_bounds(container, lower, upper)); }
239 
240  template <typename Ct>
241  inline open_region_iterator<const Ct>
242  open_region_end(const Ct& container,
243  const typename container_traits<Ct>::key_type& lower,
244  const typename container_traits<Ct>::key_type& upper)
245  { return region_end(container, make_open_bounds(container, lower, upper)); }
246 
247  template <typename Ct>
248  inline open_region_iterator<const Ct>
249  open_region_cend(const Ct& container,
250  const typename container_traits<Ct>::key_type& lower,
251  const typename container_traits<Ct>::key_type& upper)
252  { return region_cend(container, make_open_bounds(container, lower, upper)); }
253 
254  template <typename Ct>
255  inline open_region_iterator<Ct>
256  open_region_begin(Ct& container,
257  const typename container_traits<Ct>::key_type& lower,
258  const typename container_traits<Ct>::key_type& upper)
259  { return region_begin(container, make_open_bounds(container, lower, upper)); }
260 
261  template <typename Ct>
262  inline open_region_iterator<const Ct>
263  open_region_begin(const Ct& container,
264  const typename container_traits<Ct>::key_type& lower,
265  const typename container_traits<Ct>::key_type& upper)
266  { return region_begin(container, make_open_bounds(container, lower, upper)); }
267 
268  template <typename Ct>
269  inline open_region_iterator<const Ct>
270  open_region_cbegin(const Ct& container,
271  const typename container_traits<Ct>::key_type& lower,
272  const typename container_traits<Ct>::key_type& upper)
273  {
274  return region_cbegin(container, make_open_bounds(container, lower, upper));
275  }
276 
277  template <typename Ct>
278  inline open_region_iterator_pair<Ct>
279  open_region_range(Ct& container,
280  const typename container_traits<Ct>::key_type& lower,
281  const typename container_traits<Ct>::key_type& upper)
282  { return region_range(container, make_open_bounds(container, lower, upper)); }
283 
284  template <typename Ct>
285  inline open_region_iterator_pair<const Ct>
286  open_region_range(const Ct& container,
287  const typename container_traits<Ct>::key_type& lower,
288  const typename container_traits<Ct>::key_type& upper)
289  { return region_range(container, make_open_bounds(container, lower, upper)); }
290 
291  template <typename Ct>
292  inline open_region_iterator_pair<const Ct>
293  open_region_crange(const Ct& container,
294  const typename container_traits<Ct>::key_type& lower,
295  const typename container_traits<Ct>::key_type& upper)
296  {
297  return region_crange(container, make_open_bounds(container, lower, upper));
298  }
299 
300 } // namespace spatial
301 
302 #endif // SPATIAL_OPEN_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::open_region_iterator::open_region_iterator
open_region_iterator()
Definition: spatial_open_region.hpp:142
spatial::open_bounds
A model of Region Predicate that checks if a value of type Key is contained within the open boundarie...
Definition: spatial_open_region.hpp:41
spatial::except::check_open_bounds
void check_open_bounds(const Tp &container, const typename container_traits< Tp >::key_type &lower, const typename container_traits< Tp >::key_type &upper)
Checks if all coordinates of lower are strictly less than these of higher along the same dimensions...
Definition: spatial_except.hpp:129
spatial::container_traits::key_compare
Tp::key_compare key_compare
Comparison functor used to compare two instances of key_type.
Definition: traits.hpp:98
spatial::open_region_cend
open_region_iterator< const Ct > open_region_cend(const Ct &container, const typename container_traits< Ct >::key_type &lower, const typename container_traits< Ct >::key_type &upper)
Definition: spatial_open_region.hpp:249
spatial::open_region_end
open_region_iterator< Ct > open_region_end(Ct &container, const typename container_traits< Ct >::key_type &lower, const typename container_traits< Ct >::key_type &upper)
Definition: spatial_open_region.hpp:235
spatial::open_region_iterator_pair< const Ct >::open_region_iterator_pair
open_region_iterator_pair()
Definition: spatial_open_region.hpp:209
spatial::open_region_iterator_pair
Definition: spatial_open_region.hpp:183
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::open_region_iterator< const Ct >::open_region_iterator
open_region_iterator()
Definition: spatial_open_region.hpp:160
spatial::open_region_cbegin
open_region_iterator< const Ct > open_region_cbegin(const Ct &container, const typename container_traits< Ct >::key_type &lower, const typename container_traits< Ct >::key_type &upper)
Definition: spatial_open_region.hpp:270
spatial::open_region_range
open_region_iterator_pair< Ct > open_region_range(Ct &container, const typename container_traits< Ct >::key_type &lower, const typename container_traits< Ct >::key_type &upper)
Definition: spatial_open_region.hpp:279
spatial::open_bounds::_upper
Key _upper
The upper bound for the orthogonal region iterator.
Definition: spatial_open_region.hpp:100
spatial::region_begin
region_iterator< Ct, Predicate > region_begin(Ct &container, const Predicate &pred)
Definition: spatial_region.hpp:449
spatial::open_bounds::open_bounds
open_bounds()
The default constructor leaves everything un-initialized.
Definition: spatial_open_region.hpp:48
spatial::open_region_iterator
Definition: spatial_open_region.hpp:137
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::open_region_begin
open_region_iterator< Ct > open_region_begin(Ct &container, const typename container_traits< Ct >::key_type &lower, const typename container_traits< Ct >::key_type &upper)
Definition: spatial_open_region.hpp:256
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::open_bounds::_lower
Key _lower
The lower bound for the orthogonal region iterator.
Definition: spatial_open_region.hpp:95
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::open_region_crange
open_region_iterator_pair< const Ct > open_region_crange(const Ct &container, const typename container_traits< Ct >::key_type &lower, const typename container_traits< Ct >::key_type &upper)
Definition: spatial_open_region.hpp:293
spatial::open_bounds::open_bounds
open_bounds(const Compare &compare, const Key &lower, const Key &upper)
Set the lower and upper boundary for the orthogonal range search in the region.
Definition: spatial_open_region.hpp:64
spatial::open_region_iterator_pair::open_region_iterator_pair
open_region_iterator_pair()
Definition: spatial_open_region.hpp:188
spatial::make_open_bounds
open_bounds< typename container_traits< Tp >::key_type, typename container_traits< Tp >::key_compare > make_open_bounds(const Tp &container, const typename container_traits< Tp >::key_type &lower, const typename container_traits< Tp >::key_type &upper)
A open_bounds factory that takes in a container, a region defined by lower and upper, and returns a constructed open_bounds object.
Definition: spatial_open_region.hpp:125
spatial::open_bounds::operator()
relative_order operator()(dimension_type dim, dimension_type, const Key &key) const
The operator that returns wheather the point is in region or not.
Definition: spatial_open_region.hpp:82