yat
0.8.3pre
|
00001 #ifndef theplu_yat_utility_segment_set 00002 #define theplu_yat_utility_segment_set 00003 00004 // $Id: SegmentSet.h 2360 2010-12-04 01:04:45Z peter $ 00005 00006 /* 00007 Copyright (C) 2010 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 #include "SegmentTree.h" 00027 #include "stl_utility.h" 00028 #include "yat_assert.h" 00029 00030 #include <set> 00031 #include <utility> 00032 00033 namespace theplu { 00034 namespace yat { 00035 namespace utility { 00036 00044 template<typename T, class Compare = std::less<T> > 00045 class SegmentSet 00046 : public SegmentTree<std::set<Segment<T, Compare>, 00047 SegmentCompare<T, Compare> >, 00048 Compare, 00049 Identity<const Segment<T, Compare>&> > 00050 { 00051 typedef SegmentSet<T, Compare> me; 00052 public: 00056 SegmentSet(void) {} 00057 00062 typename me::const_iterator 00063 insert_merge(const typename me::value_type& segment) 00064 { 00065 std::pair<typename me::iterator, typename me::iterator> p = 00066 overlap_range(segment); 00067 if (p.first==p.second) { // no overlap between set and segment 00068 return this->container_.insert(p.first, segment); 00069 } 00070 /* 00071 p.first last p.second 00072 ---> ---> ---> ---> 00073 00074 -----------------------> 00075 segment 00076 */ 00077 Compare comp; 00078 typename me::iterator last=p.second; 00079 YAT_ASSERT(last==this->end() || compare(segment, *last)); 00080 YAT_ASSERT(last!=this->begin()); // last!=p.first 00081 --last; 00082 YAT_ASSERT(compare_3way(segment, *last)==0); 00083 00084 Segment<T, Compare> segment2(std::min(p.first->begin(), 00085 segment.begin(), comp), 00086 std::max(last->end(), segment.end(), comp)); 00087 this->container_.erase(p.first, p.second); 00088 // FIXME: use a better hint than end() 00089 return this->container_.insert(this->end(), segment2); 00090 } 00091 00092 private: 00093 // using compiler generated copying 00094 //SegmentSet(const SegmentSet&); 00095 //SegmentSet& operator=(const SegmentSet&); 00096 }; 00097 00098 }}} 00099 #endif