yat
0.8.3pre
|
00001 #ifndef theplu_yat_utility_segment_tree 00002 #define theplu_yat_utility_segment_tree 00003 00004 // $Id: SegmentTree.h 2681 2012-01-12 21:41:15Z peter $ 00005 00006 /* 00007 Copyright (C) 2010, 2011, 2012 Peter Johansson 00008 00009 This file is part of the yat library, http://dev.thep.lu.se/yat 00010 00011 The yat library is free software; you can redistribute it and/or 00012 modify it under the terms of the GNU General Public License as 00013 published by the Free Software Foundation; either version 3 of the 00014 License, or (at your option) any later version. 00015 00016 The yat library is distributed in the hope that it will be useful, 00017 but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00019 General Public License for more details. 00020 00021 You should have received a copy of the GNU General Public License 00022 along with yat. If not, see <http://www.gnu.org/licenses/>. 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: 00053 typedef typename Container::key_type key_type; 00054 00061 typedef typename Container::value_type value_type; 00062 00068 typedef typename key_type::value_type element_type; 00069 00071 typedef typename Container::key_compare key_compare; 00073 typedef typename Container::value_compare value_compare; 00075 typedef Compare element_compare; 00076 00078 typedef typename Container::pointer pointer; 00080 typedef typename Container::reference reference; 00082 typedef typename Container::const_reference const_reference; 00084 typedef typename Container::size_type size_type; 00086 typedef typename Container::difference_type difference_type; 00088 typedef typename Container::iterator iterator; 00090 typedef typename Container::const_iterator const_iterator; 00091 00095 SegmentTree(void) {} 00096 00100 virtual ~SegmentTree(void) {} 00101 00105 const_iterator begin(void) const { return container_.begin(); } 00106 00110 iterator begin(void) { return container_.begin(); } 00111 00115 void clear(void) { container_.clear(); } 00116 00120 size_type count(const element_type& element) const; 00121 00125 bool empty(void) const { return container_.empty(); } 00126 00130 const_iterator end(void) const { return container_.end(); } 00131 00135 iterator end(void) { return container_.end(); } 00136 00142 void erase(iterator first, iterator last) { container_.erase(first, last);} 00143 00149 void erase(iterator pos) { container_.erase(pos); } 00150 00156 iterator find(const element_type& element); 00157 00166 const_iterator find(const element_type& vt) const; 00167 00179 std::pair<iterator, bool> insert(const value_type& value); 00180 00184 key_compare key_comp(void) const 00185 { 00186 return key_compare(compare); 00187 } 00188 00195 iterator lower_bound(const element_type& element); 00196 00203 const_iterator lower_bound(const element_type& element) const; 00204 00208 size_type size(void) const { return container_.size(); } 00209 00214 iterator upper_bound(const element_type& element); 00215 00222 const_iterator upper_bound(const element_type& element) const; 00223 00230 value_compare value_comp(void) const { return key_comp(); } 00231 00232 protected: 00234 Container container_; 00235 00241 std::pair<iterator, iterator> overlap_range(const key_type& segment) 00242 { 00243 iterator first = container_.lower_bound(segment); 00244 if (first!=begin()) { 00245 --first; 00246 if (compare(*first, segment)) 00247 ++first; 00248 } 00249 iterator last = first; 00250 while (last!=end() && !compare(segment, *last)) 00251 ++last; 00252 YAT_ASSERT(last==end() || compare(segment, *last)); 00253 return std::make_pair(first, last); 00254 } 00255 00256 // using compiler generated copying 00257 //SegmentTree(const SegmentTree&); 00258 //SegmentTree& operator=(const SegmentTree&); 00259 }; 00260 00261 template<class Container, class Compare, class Value2Key> 00262 typename SegmentTree<Container, Compare, Value2Key>::size_type 00263 SegmentTree<Container,Compare,Value2Key>::count(const element_type& element) const 00264 { 00265 if (find(element)==end()) 00266 return 0; 00267 return 1; 00268 } 00269 00270 00271 template<class Container, class Compare, class Value2Key> 00272 typename SegmentTree<Container, Compare, Value2Key>::const_iterator 00273 SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt) const 00274 { 00275 const_iterator iter = lower_bound(vt); 00276 element_compare comp; 00277 // if (iter==end() || comp(vt, iter->begin())) 00278 if (iter==end() || comp(vt, Value2Key()(*iter).begin())) 00279 return end(); 00280 return iter; 00281 } 00282 00283 00284 template<class Container, class Compare, class Value2Key> 00285 typename SegmentTree<Container, Compare, Value2Key>::iterator 00286 SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt) 00287 { 00288 iterator iter = lower_bound(vt); 00289 element_compare comp; 00290 if (iter==end() || comp(vt, Value2Key()(*iter).begin())) 00291 return end(); 00292 return iter; 00293 } 00294 00295 00296 template<typename T, class Compare, class Value2Key> 00297 std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator, bool> 00298 SegmentTree<T, Compare,Value2Key>::insert(const value_type& segment) 00299 { 00300 return container_.insert(segment); 00301 } 00302 00303 00304 template<typename T, class Compare, class Value2Key> 00305 typename SegmentTree<T, Compare, Value2Key>::iterator 00306 SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element) 00307 { 00308 key_type segment(element, element); 00309 iterator result = container_.lower_bound(segment); 00310 // result is larger or overlapping with segment (i.e.! result<segment) 00311 YAT_ASSERT(result==end() 00312 || !compare(Value2Key()(*result),segment)); 00313 return result; 00314 } 00315 00316 00317 template<typename T, class Compare, class Value2Key> 00318 typename SegmentTree<T, Compare, Value2Key>::const_iterator 00319 SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element) const 00320 { 00321 key_type segment(element, element); 00322 const_iterator result = container_.lower_bound(segment); 00323 // result is larger or overlapping with segment (i.e.! result<segment) 00324 YAT_ASSERT(result==end() 00325 || !compare(Value2Key()(*result),segment)); 00326 return result; 00327 } 00328 00329 00330 template<typename T, class Compare, class Value2Key> 00331 typename SegmentTree<T, Compare, Value2Key>::iterator 00332 SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element) 00333 { 00334 key_type segment(element, element); 00335 iterator result = container_.upper_bound(segment); 00336 Compare comp; 00337 Value2Key value2key; 00338 if (result==end() || comp(element, value2key(*result).begin())) 00339 return result; 00340 ++result; 00341 // result is larger than segment 00342 YAT_ASSERT(result==end() || compare(segment, value2key(*result))); 00343 return result; 00344 } 00345 00346 00347 template<typename T, class Compare, class Value2Key> 00348 typename SegmentTree<T, Compare, Value2Key>::const_iterator 00349 SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element) const 00350 { 00351 Segment<element_type, Compare> segment(element, element); 00352 const_iterator result = container_.upper_bound(segment); 00353 Compare comp; 00354 Value2Key value2key; 00355 if (result==end() || comp(element, value2key(*result).begin())) 00356 return result; 00357 ++result; 00358 // result is larger than segment 00359 YAT_ASSERT(result==end() || compare(segment, value2key(*result))); 00360 return result; 00361 } 00362 00363 }}} 00364 #endif