SHORE API
•All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
d2tree.hpp
Go to the documentation of this file.
1 
2 /*
3  * Copyright 2008,2009,2010,2011,2012 Stephan Ossowski, Korbinian Schneeberger,
4  * Felix Ott, Joerg Hagmann, Alf Scotland, Sebastian Bender
5  *
6  * This file is part of SHORE.
7  *
8  * SHORE is free software: you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation, either version 3 of the License, or
11  * (at your option) any later version.
12  *
13  * SHORE is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with SHORE. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
25 
26 
27 #ifndef SHORE_ALGO_D2TREE_HPP__
28 #define SHORE_ALGO_D2TREE_HPP__
29 
30 #include <algorithm>
31 #include <iterator>
32 #include <vector>
33 
34 #include "shore/base/util.hpp"
35 #include "shore/base/mathops.hpp"
36 
37 namespace shore {
38 
40 template<typename XCompare,typename YCompare=XCompare,typename XYCompare=XCompare>
41 class d2tree
42 {
43  private:
44 
45  XCompare m_xcmp;
46  YCompare m_ycmp;
47  XYCompare m_xycmp;
48 
49  bool m_hasxy;
50 
51  template<typename Iterator>
52  void build_recursive(const Iterator i,const Iterator j,const bool d2)
53  {
54  const size_t size=j-i;
55 
56  if(size<=1)
57  return;
58 
59  const Iterator med=i+(size>>1);
60 
61  if(d2)
62  std::nth_element(i,med,j,m_ycmp);
63  else
64  std::nth_element(i,med,j,m_xcmp);
65 
66  build_recursive(i,med,!d2);
67  build_recursive(med+1,j,!d2);
68  }
69 
71  template<typename Iterator,typename Key_t>
72  void search_including_recursive(std::vector<Iterator>& ret,
73  const Key_t& key,
74  const Iterator i,const Iterator j,
75  const bool d2) const
76  {
77  const size_t size=j-i;
78 
79  if(size==0)
80  return;
81 
82  const Iterator med_it=i+(size>>1);
83  const typename std::iterator_traits<Iterator>::value_type& med_elem=*med_it;
84 
85  if(!d2)
86  {
87  if(!m_xcmp(key,med_elem))
88  {
89  if(!m_ycmp(med_elem,key))
90  ret.push_back(med_it);
91 
92  search_including_recursive(ret,key,med_it+1,j,!d2);
93  }
94  search_including_recursive(ret,key,i,med_it,!d2);
95  }
96  else
97  {
98  if(!m_ycmp(med_elem,key))
99  {
100  if(!m_xcmp(key,med_elem))
101  ret.push_back(med_it);
102 
103  search_including_recursive(ret,key,i,med_it,!d2);
104  }
105  search_including_recursive(ret,key,med_it+1,j,!d2);
106  }
107  }
108 
110  template<typename Iterator,typename Key_t>
111  void search_included_recursive(std::vector<Iterator>& ret,
112  const Key_t& key,
113  const Iterator i,const Iterator j,
114  const bool d2) const
115  {
116  const size_t size=j-i;
117 
118  if(size==0)
119  return;
120 
121  const Iterator med_it=i+(size>>1);
122  const typename std::iterator_traits<Iterator>::value_type& med_elem=*med_it;
123 
124  if(!d2)
125  {
126  if(!m_xcmp(med_elem,key))
127  {
128  if(!m_ycmp(key,med_elem))
129  ret.push_back(med_it);
130 
131  search_included_recursive(ret,key,i,med_it,!d2);
132  }
133  search_included_recursive(ret,key,med_it+1,j,!d2);
134  }
135  else
136  {
137  if(!m_ycmp(key,med_elem))
138  {
139  if(!m_xcmp(med_elem,key))
140  ret.push_back(med_it);
141 
142  search_included_recursive(ret,key,med_it+1,j,!d2);
143  }
144  search_included_recursive(ret,key,i,med_it,!d2);
145  }
146  }
147 
149  template<typename Iterator,typename Key_t>
150  void search_overlapping_recursive(std::vector<Iterator>& ret,
151  const Key_t& key,
152  const Iterator i,const Iterator j,
153  const bool d2) const
154  {
155  const size_t size=j-i;
156 
157  if(size==0)
158  return;
159 
160  const Iterator med_it=i+(size>>1);
161  const typename std::iterator_traits<Iterator>::value_type& med_elem=*med_it;
162 
163  if(!d2)
164  {
165  if(m_xycmp(med_elem,key))
166  {
167  if(m_xycmp(key,med_elem))
168  ret.push_back(med_it);
169 
170  // if the start of the middle elem. is small enough,
171  // we have to search to the right
172  search_overlapping_recursive(ret,key,med_it+1,j,!d2);
173  }
174  // always search to the left
175  search_overlapping_recursive(ret,key,i,med_it,!d2);
176  }
177  else
178  {
179  if(m_xycmp(key,med_elem))
180  {
181  if(m_xycmp(med_elem,key))
182  ret.push_back(med_it);
183 
184  search_overlapping_recursive(ret,key,i,med_it,!d2);
185  }
186  // always search to the right
187  search_overlapping_recursive(ret,key,med_it+1,j,!d2);
188  }
189  }
190 
193  template<typename Iterator,typename Key_t>
194  void search_nearest_downstream_recursive(std::vector<Iterator>& ret,
195  const Key_t& key,
196  const Iterator i,const Iterator j,
197  const bool d2) const
198  {
199  const size_t size=j-i;
200 
201  if(size==0)
202  return;
203 
204  const Iterator med_it=i+(size>>1);
205 
206  const typename std::iterator_traits<Iterator>::value_type& med_elem=*med_it;
207 
208  // if it's equal or larger than key
209  if(!m_xycmp(med_elem,key))
210  {
211  // if nothing has been found up to now,
212  // then its the best hit for now
213  if(ret.empty())
214  {
215  ret.push_back(med_it);
216 
217  search_nearest_downstream_recursive(ret,key,i,med_it,!d2);
218  search_nearest_downstream_recursive(ret,key,med_it+1,j,!d2);
219  }
220  // something else has been found, compare
221  else
222  {
223  // better than previous hits
224  if(m_xcmp(med_elem,*ret.front()))
225  {
226  ret.clear();
227  ret.push_back(med_it);
228 
229  search_nearest_downstream_recursive(ret,key,i,med_it,!d2);
230  search_nearest_downstream_recursive(ret,key,med_it+1,j,!d2);
231  }
232  // worse than previous hits
233  else if(m_xcmp(*ret.front(),med_elem))
234  {
235  search_nearest_downstream_recursive(ret,key,i,med_it,!d2);
236  // if we're in the correct dimension,
237  // we can discard a branch of the tree
238  if(d2)
239  search_nearest_downstream_recursive(ret,key,med_it+1,j,!d2);
240  }
241  // equal to previous hits
242  else
243  {
244  ret.push_back(med_it);
245 
246  search_nearest_downstream_recursive(ret,key,i,med_it,!d2);
247  search_nearest_downstream_recursive(ret,key,med_it+1,j,!d2);
248  }
249  }
250  }
251  // it's not larger than pos, discard this now
252  else
253  {
254  // if we're in the correct dimension,
255  // we can discard a branch of the tree
256  if(d2)
257  search_nearest_downstream_recursive(ret,key,i,med_it,!d2);
258  search_nearest_downstream_recursive(ret,key,med_it+1,j,!d2);
259  }
260  }
261 
264  template<typename Iterator,typename Key_t>
265  void search_nearest_upstream_recursive(std::vector<Iterator>& ret,
266  const Key_t& key,
267  const Iterator i,const Iterator j,
268  const bool d2) const
269  {
270  const size_t size=j-i;
271 
272  if(size==0)
273  return;
274 
275  const Iterator med_it=i+(size>>1);
276  const typename std::iterator_traits<Iterator>::value_type& med_elem=*med_it;
277 
278  if(m_xycmp(key,med_elem))
279  {
280  search_nearest_upstream_recursive(ret,key,i,med_it,!d2);
281  if(!d2)
282  search_nearest_upstream_recursive(ret,key,med_it+1,j,!d2);
283  }
284  else
285  {
286  if(ret.empty())
287  {
288  ret.push_back(med_it);
289 
290  search_nearest_upstream_recursive(ret,key,i,med_it,!d2);
291  search_nearest_upstream_recursive(ret,key,med_it+1,j,!d2);
292  }
293  else
294  {
295  if(m_ycmp(*ret.front(),med_elem))
296  {
297  ret.clear();
298  ret.push_back(med_it);
299 
300  search_nearest_upstream_recursive(ret,key,i,med_it,!d2);
301  search_nearest_upstream_recursive(ret,key,med_it+1,j,!d2);
302  }
303  else if(m_ycmp(med_elem,*ret.front()))
304  {
305  if(!d2)
306  search_nearest_upstream_recursive(ret,key,i,med_it,!d2);
307  search_nearest_upstream_recursive(ret,key,med_it+1,j,!d2);
308  }
309  else
310  {
311  ret.push_back(med_it);
312 
313  search_nearest_upstream_recursive(ret,key,i,med_it,!d2);
314  search_nearest_upstream_recursive(ret,key,med_it+1,j,!d2);
315  }
316  }
317  }
318  }
319 
320  public:
321 
323  d2tree(XCompare cx,YCompare cy,XYCompare cxy)
324  :m_xcmp(cx),m_ycmp(cy),m_xycmp(cxy),m_hasxy(true)
325  {}
326 
331  d2tree(XCompare cx,YCompare cy)
332  :m_xcmp(cx),m_ycmp(cy),m_xycmp(cx),m_hasxy(false)
333  {}
334 
338  template<typename Iterator>
339  void build(Iterator beg,Iterator end)
340  {
341  build_recursive(beg,end,false);
342  }
343 
345  // Query functions:
346  // all assume that build() was already executed on the vector
348 
353  template<typename Iterator,typename Key_t>
354  std::vector<Iterator> search_including(
355  Iterator beg,Iterator end,const Key_t& key) const
356  {
357  std::vector<Iterator> ret;
358 
359  search_including_recursive(ret,key,beg,end,false);
360 
361  return ret;
362  }
363 
368  template<typename Iterator,typename Key_t>
369  std::vector<Iterator> search_included(
370  Iterator beg,Iterator end,const Key_t& key) const
371  {
372  std::vector<Iterator> ret;
373 
374  search_included_recursive(ret,key,beg,end,false);
375 
376  return ret;
377  }
378 
383  template<typename Iterator,typename Key_t>
384  std::vector<Iterator> search_overlapping(
385  Iterator beg,Iterator end,const Key_t& key) const
386  {
387  if(!m_hasxy)
388  throw_exception(std::logic_error("d2tree: no xy comparator provided"));
389 
390  std::vector<Iterator> ret;
391 
392  search_overlapping_recursive(ret,key,beg,end,false);
393 
394  return ret;
395  }
396 
401  template<typename Iterator,typename Key_t>
402  std::vector<Iterator> search_nearest_upstream(
403  Iterator beg,Iterator end,const Key_t& key) const
404  {
405  if(!m_hasxy)
406  throw_exception(std::logic_error("d2tree: no xy comparator provided"));
407 
408  std::vector<Iterator> ret;
409 
410  search_nearest_upstream_recursive(ret,key,beg,end,false);
411 
412  return ret;
413  }
414 
419  template<typename Iterator,typename Key_t>
420  std::vector<Iterator> search_nearest_downstream(
421  Iterator beg,Iterator end,const Key_t& key) const
422  {
423  if(!m_hasxy)
424  throw_exception(std::logic_error("d2tree: no xy comparator provided"));
425 
426  std::vector<Iterator> ret;
427 
428  search_nearest_downstream_recursive(ret,key,beg,end,false);
429 
430  return ret;
431  }
432 };
433 
435 
437 template<typename first_t,typename second_t>
438 bool paircmpx(const std::pair<first_t,second_t>& p1,
439  const std::pair<first_t,second_t>& p2)
440 {
441  return p1.first<p2.first;
442 }
443 
445 template<typename first_t,typename second_t>
446 bool paircmpy(const std::pair<first_t,second_t>& p1,
447  const std::pair<first_t,second_t>& p2)
448 {
449  return p1.second<p2.second;
450 }
451 
453 template<typename first_t,typename second_t>
454 bool paircmpxy(const std::pair<first_t,second_t>& p1,
455  const std::pair<first_t,second_t>& p2)
456 {
457  return p1.first<p2.second;
458 }
459 
460 } // namespace shore
461 
462 #endif // SHORE_ALGO_D2TREE_HPP__
463