1 | #ifndef theplu_yat_utility_segment_set |
---|
2 | #define theplu_yat_utility_segment_set |
---|
3 | |
---|
4 | // $Id: SegmentSet.h 3344 2014-11-06 12:09:32Z peter $ |
---|
5 | |
---|
6 | /* |
---|
7 | Copyright (C) 2010 Peter Johansson |
---|
8 | Copyright (C) 2012 Jari Häkkinen |
---|
9 | |
---|
10 | This file is part of the yat library, http://dev.thep.lu.se/yat |
---|
11 | |
---|
12 | The yat library is free software; you can redistribute it and/or |
---|
13 | modify it under the terms of the GNU General Public License as |
---|
14 | published by the Free Software Foundation; either version 3 of the |
---|
15 | License, or (at your option) any later version. |
---|
16 | |
---|
17 | The yat library is distributed in the hope that it will be useful, |
---|
18 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
19 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
---|
20 | General Public License for more details. |
---|
21 | |
---|
22 | You should have received a copy of the GNU General Public License |
---|
23 | along with yat. If not, see <http://www.gnu.org/licenses/>. |
---|
24 | */ |
---|
25 | |
---|
26 | #include "Segment.h" |
---|
27 | #include "SegmentTree.h" |
---|
28 | #include "stl_utility.h" |
---|
29 | #include "yat_assert.h" |
---|
30 | |
---|
31 | #include <set> |
---|
32 | #include <utility> |
---|
33 | |
---|
34 | namespace theplu { |
---|
35 | namespace yat { |
---|
36 | namespace utility { |
---|
37 | |
---|
38 | /** |
---|
39 | \brief a set of Segments |
---|
40 | |
---|
41 | A container that holds a set of Segment. The Segments cannot overlap. |
---|
42 | |
---|
43 | \since new in yat 0.7 |
---|
44 | */ |
---|
45 | template<typename T, class Compare = std::less<T> > |
---|
46 | class SegmentSet |
---|
47 | : public SegmentTree<std::set<Segment<T, Compare>, |
---|
48 | SegmentCompare<T, Compare> >, |
---|
49 | Compare, |
---|
50 | Identity<const Segment<T, Compare>&> > |
---|
51 | { |
---|
52 | typedef SegmentSet<T, Compare> me; |
---|
53 | public: |
---|
54 | /** |
---|
55 | \brief creates a set with no segments |
---|
56 | */ |
---|
57 | SegmentSet(void) {} |
---|
58 | |
---|
59 | /** |
---|
60 | insert \a segment into set. If there is no gap between \a |
---|
61 | segment and neighboring segments the segments are merged. |
---|
62 | */ |
---|
63 | typename me::const_iterator |
---|
64 | insert_merge(const typename me::value_type& segment) |
---|
65 | { |
---|
66 | std::pair<typename me::iterator, typename me::iterator> p = |
---|
67 | this->overlap_range(segment); |
---|
68 | return insert_merge(p, segment); |
---|
69 | } |
---|
70 | |
---|
71 | /** |
---|
72 | \brief insert with a hint |
---|
73 | |
---|
74 | Similar to insert_merge(1) but \a hint help to find where to |
---|
75 | insert \a segment. For the \a hint to be useful, \a segment |
---|
76 | should not be greater than element hint points to and not |
---|
77 | smaller than element --hint points to. |
---|
78 | |
---|
79 | \since New in yat 0.13 |
---|
80 | */ |
---|
81 | typename me::iterator insert_merge(typename me::iterator hint, |
---|
82 | const typename me::value_type& segment) |
---|
83 | { |
---|
84 | std::pair<typename me::iterator, typename me::iterator> p(hint, hint); |
---|
85 | if (this->container_.empty()) |
---|
86 | return insert_merge(p, segment); |
---|
87 | |
---|
88 | //.If hint points to an element that is less than segment, hint |
---|
89 | //is no good and we ignore the hint. |
---|
90 | if (hint!=this->end() && compare(*hint, segment)) |
---|
91 | return insert_merge(segment); |
---|
92 | |
---|
93 | if (p.first!=this->begin()) { |
---|
94 | --p.first; |
---|
95 | // If --hint point to an element greater than segment, hint is |
---|
96 | // no good. |
---|
97 | if (compare(segment, *p.first)) |
---|
98 | return insert_merge(segment); |
---|
99 | // find first element that is smaller than segment |
---|
100 | while (p.first!=this->begin() && !compare(*p.first, segment)) |
---|
101 | --p.first; |
---|
102 | YAT_ASSERT(p.first==this->begin() || compare(*p.first, segment)); |
---|
103 | YAT_ASSERT(p.first!=this->end()); |
---|
104 | if (compare(*p.first, segment)) |
---|
105 | ++p.first; |
---|
106 | } |
---|
107 | |
---|
108 | // find first element greater than segment |
---|
109 | while (p.second!=this->end() && !compare(segment, *p.second)) |
---|
110 | ++p.second; |
---|
111 | |
---|
112 | return insert_merge(p, segment); |
---|
113 | } |
---|
114 | |
---|
115 | private: |
---|
116 | // used by public functions insert_merge. |
---|
117 | // |
---|
118 | // p.first points to the first segment that overlaps with \a segment or |
---|
119 | // is greater than segment. |
---|
120 | // p.second points to the first segment that is greater than \a segment |
---|
121 | typename me::const_iterator |
---|
122 | insert_merge(const std::pair<typename me::iterator, |
---|
123 | typename me::iterator>& p, |
---|
124 | const typename me::value_type& segment) |
---|
125 | { |
---|
126 | YAT_ASSERT(p.first==this->end() || !compare(*p.first, segment)); |
---|
127 | YAT_ASSERT(p.second==this->end() || compare(segment, *p.second)); |
---|
128 | if (p.first==p.second) { // no overlap between set and segment |
---|
129 | return this->container_.insert(p.first, segment); |
---|
130 | } |
---|
131 | /* |
---|
132 | p.first last p.second |
---|
133 | ---> ---> ---> ---> |
---|
134 | |
---|
135 | -----------------------> |
---|
136 | segment |
---|
137 | */ |
---|
138 | Compare comp; |
---|
139 | typename me::iterator last=p.second; |
---|
140 | YAT_ASSERT(last==this->end() || compare(segment, *last)); |
---|
141 | YAT_ASSERT(last!=this->begin()); // last!=p.first |
---|
142 | --last; |
---|
143 | YAT_ASSERT(compare_3way(segment, *last)==0); |
---|
144 | |
---|
145 | Segment<T, Compare> |
---|
146 | segment2(std::min(p.first->begin(), segment.begin(), comp), |
---|
147 | std::max(last->end(), segment.end(), comp)); |
---|
148 | |
---|
149 | this->container_.erase(p.first, p.second); |
---|
150 | return this->container_.insert(p.second, segment2); |
---|
151 | } |
---|
152 | |
---|
153 | // using compiler generated copying |
---|
154 | //SegmentSet(const SegmentSet&); |
---|
155 | //SegmentSet& operator=(const SegmentSet&); |
---|
156 | }; |
---|
157 | |
---|
158 | }}} |
---|
159 | #endif |
---|