source: trunk/yat/utility/SegmentSet.h @ 2296

Last change on this file since 2296 was 2296, checked in by Peter, 12 years ago

class SegmentSet?: added function clear and fixed bug in insert. Divided test into subtests. refs #635

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 7.2 KB
Line 
1#ifndef theplu_yat_utility_segment_set
2#define theplu_yat_utility_segment_set
3
4// $Id: SegmentSet.h 2296 2010-07-08 19:39:42Z peter $
5
6/*
7  Copyright (C) 2010 Peter Johansson
8
9  This file is part of the yat library, http://dev.thep.lu.se/yat
10
11  The yat library is free software; you can redistribute it and/or
12  modify it under the terms of the GNU General Public License as
13  published by the Free Software Foundation; either version 3 of the
14  License, or (at your option) any later version.
15
16  The yat library is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  General Public License for more details.
20
21  You should have received a copy of the GNU General Public License
22  along with yat. If not, see <http://www.gnu.org/licenses/>.
23*/
24
25#include "Segment.h"
26#include "yat_assert.h"
27
28#include <algorithm>
29#include <functional>
30#include <set>
31
32namespace theplu {
33namespace yat {
34namespace utility {
35
36  /**
37     \brief a set of Segments
38
39     A container that holds a set of Segment. The Segments can not overlap.
40
41     \since new in yat 0.7
42   */
43  template<typename T, class Compare = std::less<T> >
44  class SegmentSet
45  {
46  public:
47    /// value_type
48    typedef Segment<T, Compare> value_type;
49  private:
50    /// \cond
51    struct Compare_
52    {
53      bool operator()(const value_type& lhs, const value_type& rhs) const
54      { return lhs.begin() < rhs.begin(); }
55    };
56    /// \endcond
57
58    typedef std::set<value_type, Compare_> Set_;
59
60  public:
61    /// \brief iterator
62    typedef typename Set_::iterator iterator;
63    /// \brief const_iterator
64    typedef typename Set_::const_iterator const_iterator;
65
66    /**
67       \brief default constructor
68     */
69    SegmentSet(void) {}
70
71    /**
72       \return iterator to first Segment
73     */
74    const_iterator begin(void) const { return set_.begin(); }
75
76    /**
77       \return iterator to first Segment
78     */
79    iterator begin(void) { return set_.begin(); }
80
81    /**
82       \brief erases all the segments
83     */
84    void clear(void) { set_.clear(); }
85
86    /**
87       \return 1 if there is a set that overlaps with \a vt
88     */
89    size_t count(const typename value_type::value_type& vt) const;
90
91    /**
92       \return end of set
93     */
94    const_iterator end(void) const { return set_.end(); }
95
96    /**
97       \return end of set
98     */
99    iterator end(void) { return set_.end(); }
100
101    /**
102       \return an iterator pointing to the Segment that contains \a
103       vt. If no Segment contains \a vt, end() is returned.
104     */
105    const_iterator find(const typename value_type::value_type& vt) const;
106
107    /**
108       \brief insert set
109
110       if \a segment does not overlap with any segment in set, insert
111       segment; otherwise do nothing.
112
113       \return a pair where pair.first points to the added \a segment
114       or if \a segment was not added it points to a Segment in set
115       that overlaps with \a segment; pair.second is true if \a
116       segment was added.
117     */
118    std::pair<iterator, bool> insert(const value_type& segment);
119
120    /**
121       insert \a segment into set. If there is no gap between \a
122       segment and neighboring segments the segments are merged. Note
123       that this might also happen for non-overlapping segments, e.g.,
124       [0,1) and [1,2) would be merged into [0,2).
125     */
126    const_iterator insert_merge(const value_type& segment);
127
128    /**
129       \return iterator pointing to first segment that overlaps with
130       \a segment or is greater than \a segment.
131     */
132    const_iterator lower_bound(const value_type& segment) const;
133
134    /**
135       \return number of segments in set
136     */
137    size_t size(void) const { return set_.size(); }
138
139    /**
140       \return iterator pointing to first segment that is greater than
141       \a segment.
142     */
143    const_iterator upper_bound(const value_type& segment) const;
144
145  private:
146    std::set<value_type, Compare_> set_;
147   
148    /**
149       pair.first first (smallest) segment that overlaps with \a
150       segment and pair.second first (smallest) segment that does not
151       overlap with \a segment.
152     */
153    std::pair<iterator, iterator> overlap_range(const value_type& segment) 
154    {
155      iterator first = set_.lower_bound(segment);
156      if (first!=begin()) {
157        --first;
158        if (compare(*first, segment))
159          ++first;
160      }
161      iterator last = first;
162      while (last!=end() && !compare(segment, *last))
163        ++last;
164      YAT_ASSERT(last==end() || compare(segment, *last));
165      return std::make_pair(first, last);
166    }
167
168
169    /**
170       pair.first first (smallest) segment that overlaps with \a
171       segment and pair.second first (smallest) segment that does not
172       overlap with \a segment.
173     */
174    std::pair<const_iterator, const_iterator> 
175    overlap_range(const value_type& segment) const
176    {
177      const_iterator first = set_.lower_bound(segment);
178      if (first!=begin()) {
179        --first;
180        if (compare(*first, segment))
181          ++first;
182      }
183      const_iterator last = first;
184      while (last!=end() && !compare(segment, *last))
185        ++last;
186      return std::make_pair(first, last);
187    }
188
189    // using compiler generated copying
190    //SegmentSet(const SegmentSet&);
191    //SegmentSet& operator=(const SegmentSet&);
192  };
193
194  template<typename T, class Compare>
195  size_t 
196  SegmentSet<T, Compare>::count(const typename value_type::value_type& vt) const
197  {
198    if (find(vt)==end())
199      return 0;
200    return 1;
201  }
202
203
204  template<typename T, class Compare>
205  typename SegmentSet<T, Compare>::const_iterator
206  SegmentSet<T, Compare>::find(const typename value_type::value_type& vt) const
207  {
208    Segment<T, Compare> segment(vt, vt);
209    std::pair<const_iterator, const_iterator> p = overlap_range(segment);
210    if (p.first == end())
211      return end();
212    Compare comp;
213    if (comp(vt, p.first->begin()))
214        return end();
215    return p.first;
216  }
217
218
219  template<typename T, class Compare>
220  std::pair<typename SegmentSet<T, Compare>::iterator, bool> 
221  SegmentSet<T, Compare>::insert(const value_type& segment)
222  {
223    std::pair<iterator, iterator> p = overlap_range(segment);
224    std::pair<typename SegmentSet<T, Compare>::iterator, bool> result;
225    if (p.first==p.second) {
226      result.first = set_.insert(p.first, segment);
227      result.second = true;
228      return result;
229    }
230    result.first = p.first;
231    result.second = false;
232    return result;
233  }
234
235
236  template<typename T, class Compare>
237  typename SegmentSet<T, Compare>::const_iterator
238  SegmentSet<T, Compare>::insert_merge(const value_type& segment)
239  {
240    std::pair<iterator, iterator> p = overlap_range(segment);
241    if (p.first==p.second) {
242      return set_.insert(p.first, segment);
243    }
244    Compare comp;
245    if (comp(segment.begin(), p.first->begin()))
246      const_cast<value_type&>(*p.first).begin() = segment.begin();
247
248    --p.second;
249    const_cast<value_type&>(*p.first).end() = 
250      std::max(p.second->end(), segment.end(), comp);
251    ++p.second;
252    iterator begin(p.first);
253    ++begin;
254    set_.erase(begin, p.second); 
255    return p.first;
256  }
257
258
259  template<typename T, class Compare>
260  typename SegmentSet<T, Compare>::const_iterator
261  SegmentSet<T, Compare>::lower_bound(const value_type& segment) const
262  {
263    const_iterator result = set_.lower_bound(segment);
264    if (result!=begin()) {
265      --result;
266      if (compare(*result, segment))
267        ++result;
268    }
269    return result;
270  }
271
272
273  template<typename T, class Compare>
274  typename SegmentSet<T, Compare>::const_iterator
275  SegmentSet<T, Compare>::upper_bound(const value_type& segment) const
276  {
277    const_iterator result = set_.lower_bound(segment);
278    while (result!=end() && !compare(segment, *result))
279      ++result;
280    return result;
281  }
282
283}}}
284#endif
Note: See TracBrowser for help on using the repository browser.