00001 #ifndef theplu_yat_utility_segment_set
00002 #define theplu_yat_utility_segment_set
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 #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) {
00068 return this->container_.insert(p.first, segment);
00069 }
00070
00071
00072
00073
00074
00075
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());
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
00089 return this->container_.insert(this->end(), segment2);
00090 }
00091
00092 private:
00093
00094
00095
00096 };
00097
00098 }}}
00099 #endif