IntervalTree.h 9.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258
  1. #ifndef __INTERVAL_TREE_H
  2. #define __INTERVAL_TREE_H
  3. //------------------------------------------------------------------------------------------------------------------------
  4. /// \class IntervalTree
  5. ///
  6. /// \brief
  7. /// \author Sergei Lobastov (LHE, JINR, Dubna)
  8. //------------------------------------------------------------------------------------------------------------------------
  9. #include <assert.h>
  10. #include <vector>
  11. #include <algorithm>
  12. #include <iostream>
  13. //------------------------------------------------------------------------------------------------------------------------
  14. //------------------------------------------------------------------------------------------------------------------------
  15. // class Interval
  16. //------------------------------------------------------------------------------------------------------------------------
  17. //------------------------------------------------------------------------------------------------------------------------
  18. template <class T, typename K = double>
  19. class Interval
  20. {
  21. public:
  22. K start;
  23. K stop;
  24. T value;
  25. Interval(K s, K e, const T& v)
  26. : start(s), stop(e), value(v)
  27. {
  28. }
  29. };
  30. //------------------------------------------------------------------------------------------------------------------------
  31. template <class T, typename K>
  32. K intervalStart(const Interval<T,K>& i)
  33. {
  34. return i.start;
  35. }
  36. //------------------------------------------------------------------------------------------------------------------------
  37. template <class T, typename K>
  38. K intervalStop(const Interval<T,K>& i)
  39. {
  40. return i.stop;
  41. }
  42. //------------------------------------------------------------------------------------------------------------------------
  43. template <class T, typename K>
  44. std::ostream& operator<<(std::ostream& out, const Interval<T,K>& i)
  45. {
  46. out<<"Interval("<<i.start<<", "<<i.stop<<"): "<<i.value;
  47. return out;
  48. }
  49. //------------------------------------------------------------------------------------------------------------------------
  50. template <class T, typename K = double>
  51. class IntervalStartSorter
  52. {
  53. public:
  54. bool operator() (const Interval<T,K>& a, const Interval<T,K>& b)
  55. {
  56. return a.start < b.start;
  57. }
  58. };
  59. //------------------------------------------------------------------------------------------------------------------------
  60. template <class T, typename K = double>
  61. class IntervalValueSorter
  62. {
  63. public:
  64. bool operator() (const Interval<T,K>& a, const Interval<T,K>& b)
  65. {
  66. return a.value < b.value;
  67. }
  68. };
  69. //------------------------------------------------------------------------------------------------------------------------
  70. //------------------------------------------------------------------------------------------------------------------------
  71. // class IntervalTree
  72. //------------------------------------------------------------------------------------------------------------------------
  73. //------------------------------------------------------------------------------------------------------------------------
  74. template <class T, typename K = double>
  75. class IntervalTree
  76. {
  77. public:
  78. typedef Interval<T,K> interval;
  79. typedef std::vector<interval> intervalVector;
  80. typedef IntervalTree<T,K> intervalTree;
  81. intervalVector intervals;
  82. intervalTree* left;
  83. intervalTree* right;
  84. K center;
  85. //------------------------------------------------------------------------------------------------------------------------
  86. IntervalTree<T,K>(void)
  87. : left(nullptr), right(nullptr), center(0.)
  88. {
  89. }
  90. //------------------------------------------------------------------------------------------------------------------------
  91. IntervalTree<T,K>(const intervalTree& other)
  92. : left(nullptr), right(nullptr)
  93. {
  94. center = other.center;
  95. intervals = other.intervals;
  96. if(other.left) left = new intervalTree(*other.left);
  97. if(other.right) right = new intervalTree(*other.right);
  98. }
  99. //------------------------------------------------------------------------------------------------------------------------
  100. ~IntervalTree(void)
  101. {
  102. delete left;
  103. delete right;
  104. }
  105. //------------------------------------------------------------------------------------------------------------------------
  106. IntervalTree<T,K>& operator=(const intervalTree& other)
  107. {
  108. center = other.center;
  109. intervals = other.intervals;
  110. if(other.left) left = new intervalTree(*other.left);
  111. else
  112. {
  113. if(left) delete left;
  114. left = nullptr;
  115. }
  116. if(other.right) right = new intervalTree(*other.right);
  117. else
  118. {
  119. if(right) delete right;
  120. right = nullptr;
  121. }
  122. return *this;
  123. }
  124. //------------------------------------------------------------------------------------------------------------------------
  125. IntervalTree<T,K>( intervalVector& ivals, std::size_t depth = 16, std::size_t minbucket = 64, K leftextent = 0, K rightextent = 0, std::size_t maxbucket = 512)
  126. : left(nullptr), right(nullptr)
  127. {
  128. --depth;
  129. IntervalStartSorter<T,K> intervalStartSorter;
  130. if(depth == 0 || (ivals.size() < minbucket && ivals.size() < maxbucket))
  131. {
  132. std::sort(ivals.begin(), ivals.end(), intervalStartSorter);
  133. intervals = ivals;
  134. }
  135. else
  136. {
  137. if(leftextent == 0 && rightextent == 0)
  138. {
  139. // sort intervals by start
  140. std::sort(ivals.begin(), ivals.end(), intervalStartSorter);
  141. }
  142. K leftp = 0.;
  143. K rightp = 0.;
  144. K centerp = 0.;
  145. if(leftextent || rightextent)
  146. {
  147. leftp = leftextent;
  148. rightp = rightextent;
  149. }
  150. else
  151. {
  152. leftp = ivals.front().start;
  153. std::vector<K> stops;
  154. stops.resize(ivals.size());
  155. transform(ivals.begin(), ivals.end(), stops.begin(), intervalStop<T,K>);
  156. rightp = *max_element(stops.begin(), stops.end());
  157. }
  158. //centerp = ( leftp + rightp ) / 2;
  159. centerp = ivals.at(ivals.size() / 2).start;
  160. center = centerp;
  161. intervalVector lefts;
  162. intervalVector rights;
  163. for(typename intervalVector::iterator it = ivals.begin(); it != ivals.end(); ++it)
  164. {
  165. interval& range = *it;
  166. if(range.stop < center) lefts.push_back(range);
  167. else if(range.start > center) rights.push_back(range);
  168. else intervals.push_back(range);
  169. }
  170. if(!lefts.empty()) left = new intervalTree(lefts, depth, minbucket, leftp, centerp);
  171. if(!rights.empty()) right = new intervalTree(rights, depth, minbucket, centerp, rightp);
  172. }
  173. }
  174. //------------------------------------------------------------------------------------------------------------------------
  175. void findOverlapping(K start, K stop, intervalVector& overlapping) const
  176. {
  177. if(!intervals.empty() && ! (stop < intervals.front().start))
  178. {
  179. for(typename intervalVector::const_iterator it = intervals.begin(); it != intervals.end(); ++it)
  180. {
  181. const interval& range = *it;
  182. if(range.stop >= start && range.start <= stop) overlapping.push_back(range);
  183. }
  184. }
  185. if(left && start <= center) left->findOverlapping(start, stop, overlapping);
  186. if(right && stop >= center) right->findOverlapping(start, stop, overlapping);
  187. }
  188. //------------------------------------------------------------------------------------------------------------------------
  189. void findContained(K start, K stop, intervalVector& contained) const
  190. {
  191. if(!intervals.empty() && ! (stop < intervals.front().start))
  192. {
  193. for(typename intervalVector::const_iterator it = intervals.begin(); it != intervals.end(); ++it)
  194. {
  195. const interval& range = *it;
  196. if(range.start >= start && range.stop <= stop) contained.push_back(range);
  197. }
  198. }
  199. if(left && start <= center) left->findContained(start, stop, contained);
  200. if(right && stop >= center) right->findContained(start, stop, contained);
  201. }
  202. //------------------------------------------------------------------------------------------------------------------------
  203. void dump(const char* comment = nullptr, std::ostream& out = std::cout, int treeLevel = 0) const
  204. {
  205. treeLevel++;
  206. if(comment) out<<comment;
  207. out<<" left= "<<left<<" right= "<<right<<" size= "<<intervals.size();
  208. for(typename intervalVector::const_iterator it = intervals.begin(), itEnd = intervals.end(); it != itEnd; it++) out<<std::endl<<(*it);
  209. if(left != nullptr)
  210. {
  211. out<<"\n Left_"<<treeLevel;
  212. left->dump(comment, out);
  213. }
  214. if(right != nullptr)
  215. {
  216. out<<"\n Right_"<<treeLevel;
  217. right->dump(comment, out);
  218. }
  219. }
  220. //------------------------------------------------------------------------------------------------------------------------
  221. static void dumpIntervals(const intervalVector* pVector, const char* comment = nullptr, std::ostream& out = std::cout)
  222. {
  223. assert(pVector != nullptr);
  224. if(comment) out<<comment;
  225. out<<" size= "<<pVector->size();
  226. for(typename intervalVector::const_iterator it = pVector->begin(), itEnd = pVector->end(); it != itEnd; it++) out<<std::endl<<(*it);
  227. }
  228. //------------------------------------------------------------------------------------------------------------------------
  229. };
  230. //------------------------------------------------------------------------------------------------------------------------
  231. #endif