00001 #ifndef theplu_yat_utility_segment_tree
00002 #define theplu_yat_utility_segment_tree
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include "Segment.h"
00026
00027 #include "yat_assert.h"
00028
00029 #include <algorithm>
00030 #include <functional>
00031
00032 namespace theplu {
00033 namespace yat {
00034 namespace utility {
00035
00044 template<class Container, class Compare, class Value2Key>
00045 class SegmentTree
00046 {
00047 public:
00049 typedef typename Container::key_type key_type;
00051 typedef typename Container::value_type value_type;
00053 typedef typename key_type::value_type element_type;
00054
00056 typedef typename Container::key_compare key_compare;
00058 typedef typename Container::value_compare value_compare;
00060 typedef Compare element_compare;
00061
00063 typedef typename Container::pointer pointer;
00065 typedef typename Container::reference reference;
00067 typedef typename Container::const_reference const_reference;
00069 typedef typename Container::size_type size_type;
00071 typedef typename Container::difference_type difference_type;
00073 typedef typename Container::iterator iterator;
00075 typedef typename Container::const_iterator const_iterator;
00076
00080 SegmentTree(void) {}
00081
00085 virtual ~SegmentTree(void) {}
00086
00090 const_iterator begin(void) const { return container_.begin(); }
00091
00095 iterator begin(void) { return container_.begin(); }
00096
00100 void clear(void) { container_.clear(); }
00101
00105 size_type count(const element_type& element) const;
00106
00110 bool empty(void) const { return container_.empty(); }
00111
00115 const_iterator end(void) const { return container_.end(); }
00116
00120 iterator end(void) { return container_.end(); }
00121
00126 const_iterator find(const element_type& vt) const;
00127
00139 std::pair<iterator, bool> insert(const value_type& segment);
00140
00144 key_compare key_comp(void) const
00145 {
00146 return key_compare(compare);
00147 }
00148
00153 iterator lower_bound(const element_type& element);
00154
00159 const_iterator lower_bound(const element_type& element) const;
00160
00164 size_type size(void) const { return container_.size(); }
00165
00170 iterator upper_bound(const element_type& element);
00171
00176 const_iterator upper_bound(const element_type& element) const;
00177
00181 value_compare value_comp(void) const { return key_comp(); }
00182
00183 protected:
00185 Container container_;
00186
00192 std::pair<iterator, iterator> overlap_range(const key_type& segment)
00193 {
00194 iterator first = container_.lower_bound(segment);
00195 if (first!=begin()) {
00196 --first;
00197 if (compare(*first, segment))
00198 ++first;
00199 }
00200 iterator last = first;
00201 while (last!=end() && !compare(segment, *last))
00202 ++last;
00203 YAT_ASSERT(last==end() || compare(segment, *last));
00204 return std::make_pair(first, last);
00205 }
00206
00207
00208
00209
00210 };
00211
00212 template<class Container, class Compare, class Value2Key>
00213 typename SegmentTree<Container, Compare, Value2Key>::size_type
00214 SegmentTree<Container,Compare,Value2Key>::count(const element_type& element) const
00215 {
00216 if (find(element)==end())
00217 return 0;
00218 return 1;
00219 }
00220
00221
00222 template<class Container, class Compare, class Value2Key>
00223 typename SegmentTree<Container, Compare, Value2Key>::const_iterator
00224 SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt) const
00225 {
00226 const_iterator iter = lower_bound(vt);
00227 element_compare comp;
00228
00229 if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
00230 return end();
00231 return iter;
00232 }
00233
00234
00235 template<typename T, class Compare, class Value2Key>
00236 std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator, bool>
00237 SegmentTree<T, Compare,Value2Key>::insert(const value_type& segment)
00238 {
00239 return container_.insert(segment);
00240 }
00241
00242
00243 template<typename T, class Compare, class Value2Key>
00244 typename SegmentTree<T, Compare, Value2Key>::iterator
00245 SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element)
00246 {
00247 key_type segment(element, element);
00248 iterator result = container_.lower_bound(segment);
00249
00250 YAT_ASSERT(result==end()
00251 || !compare(Value2Key()(*result),segment));
00252 return result;
00253 }
00254
00255
00256 template<typename T, class Compare, class Value2Key>
00257 typename SegmentTree<T, Compare, Value2Key>::const_iterator
00258 SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element) const
00259 {
00260 key_type segment(element, element);
00261 const_iterator result = container_.lower_bound(segment);
00262
00263 YAT_ASSERT(result==end()
00264 || !compare(Value2Key()(*result),segment));
00265 return result;
00266 }
00267
00268
00269 template<typename T, class Compare, class Value2Key>
00270 typename SegmentTree<T, Compare, Value2Key>::iterator
00271 SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element)
00272 {
00273 key_type segment(element, element);
00274 iterator result = container_.upper_bound(segment);
00275 Compare comp;
00276 Value2Key value2key;
00277 if (result==end() || comp(element, value2key(*result).begin()))
00278 return result;
00279 ++result;
00280
00281 YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
00282 return result;
00283 }
00284
00285
00286 template<typename T, class Compare, class Value2Key>
00287 typename SegmentTree<T, Compare, Value2Key>::const_iterator
00288 SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element) const
00289 {
00290 Segment<element_type, Compare> segment(element, element);
00291 const_iterator result = container_.upper_bound(segment);
00292 Compare comp;
00293 Value2Key value2key;
00294 if (result==end() || comp(element, value2key(*result).begin()))
00295 return result;
00296 ++result;
00297
00298 YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
00299 return result;
00300 }
00301
00302 }}}
00303 #endif