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

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

always use Compare functor in Segment (not std::less)

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 6.9 KB
Line 
1#ifndef theplu_yat_utility_segment_set
2#define theplu_yat_utility_segment_set
3
4// $Id: SegmentSet.h 2292 2010-07-07 16:32:54Z 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       \return 1 if there is a set that overlaps with \a vt
83     */
84    size_t count(const typename value_type::value_type& vt) const;
85
86    /**
87       \return end of set
88     */
89    const_iterator end(void) const { return set_.end(); }
90
91    /**
92       \return end of set
93     */
94    iterator end(void) { return set_.end(); }
95
96    /**
97       \return an iterator pointing to the Segment that contains \a
98       vt. If no Segment contains \a vt, end() is returned.
99     */
100    const_iterator find(const typename value_type::value_type& vt) const;
101
102    /**
103       \brief insert set
104
105       if \a segment does not overlap with any segment in set, insert
106       segment; otherwise do nothing.
107
108       \return a pair where pair.first points to the added \a segment
109       or if \a segment was not added it points to a Segment in set
110       that overlaps with \a segment; pair.second is true if \a
111       segment was added.
112     */
113    std::pair<iterator, bool> insert(const value_type& segment);
114
115    /**
116       insert \a segment into set. If there is no gap between \a
117       segment and neighboring segments the segments are merged. Note
118       that this might also happen for non-overlapping segments, e.g.,
119       [0,1) and [1,2) would be merged into [0,2).
120     */
121    const_iterator insert_merge(const value_type& segment);
122
123    /**
124       \return iterator pointing to first segment that overlaps with
125       \a segment or is greater than \a segment.
126     */
127    const_iterator lower_bound(const value_type& segment) const;
128
129    /**
130       \return number of segments in set
131     */
132    size_t size(void) const { return set_.size(); }
133
134    /**
135       \return iterator pointing to first segment that is greater than
136       \a segment.
137     */
138    const_iterator upper_bound(const value_type& segment) const;
139
140  private:
141    std::set<value_type, Compare_> set_;
142   
143    /**
144       pair.first first (smallest) segment that overlaps with \a
145       segment and pair.second first (smallest) segment that does not
146       overlap with \a segment.
147     */
148    std::pair<iterator, iterator> overlap_range(const value_type& segment) 
149    {
150      iterator first = set_.lower_bound(segment);
151      if (first!=begin()) {
152        --first;
153        if (compare(*first, segment))
154          ++first;
155      }
156      iterator last = first;
157      while (last!=end() && !compare(segment, *last))
158        ++last;
159      YAT_ASSERT(last==end() || compare(segment, *last));
160      return std::make_pair(first, last);
161    }
162
163
164    /**
165       pair.first first (smallest) segment that overlaps with \a
166       segment and pair.second first (smallest) segment that does not
167       overlap with \a segment.
168     */
169    std::pair<const_iterator, const_iterator> 
170    overlap_range(const value_type& segment) const
171    {
172      const_iterator first = set_.lower_bound(segment);
173      if (first!=begin()) {
174        --first;
175        if (compare(*first, segment))
176          ++first;
177      }
178      const_iterator last = first;
179      while (last!=end() && !compare(segment, *last))
180        ++last;
181      return std::make_pair(first, last);
182    }
183
184    // using compiler generated copying
185    //SegmentSet(const SegmentSet&);
186    //SegmentSet& operator=(const SegmentSet&);
187  };
188
189  template<typename T, class Compare>
190  size_t 
191  SegmentSet<T, Compare>::count(const typename value_type::value_type& vt) const
192  {
193    if (find(vt)==end())
194      return 0;
195    return 1;
196  }
197
198
199  template<typename T, class Compare>
200  typename SegmentSet<T, Compare>::const_iterator
201  SegmentSet<T, Compare>::find(const typename value_type::value_type& vt) const
202  {
203    Segment<T, Compare> segment(vt, vt);
204    std::pair<const_iterator, const_iterator> p = overlap_range(segment);
205    if (p.first == end())
206      return end();
207    Compare comp;
208    if (comp(vt, p.first->begin()))
209        return end();
210    return p.first;
211  }
212
213
214  template<typename T, class Compare>
215  std::pair<typename SegmentSet<T, Compare>::iterator, bool> 
216  SegmentSet<T, Compare>::insert(const value_type& segment)
217  {
218    iterator iter = set_.lower_bound(segment);
219    return set_.insert(segment);
220  }
221
222
223  template<typename T, class Compare>
224  typename SegmentSet<T, Compare>::const_iterator
225  SegmentSet<T, Compare>::insert_merge(const value_type& segment)
226  {
227    std::pair<iterator, iterator> p = overlap_range(segment);
228    if (p.first==p.second) {
229      return set_.insert(p.first, segment);
230    }
231    Compare comp;
232    if (comp(segment.begin(), p.first->begin()))
233      const_cast<value_type&>(*p.first).begin() = segment.begin();
234
235    --p.second;
236    const_cast<value_type&>(*p.first).end() = 
237      std::max(p.second->end(), segment.end(), comp);
238    ++p.second;
239    iterator begin(p.first);
240    ++begin;
241    set_.erase(begin, p.second); 
242    return p.first;
243  }
244
245
246  template<typename T, class Compare>
247  typename SegmentSet<T, Compare>::const_iterator
248  SegmentSet<T, Compare>::lower_bound(const value_type& segment) const
249  {
250    const_iterator result = set_.lower_bound(segment);
251    if (result!=begin()) {
252      --result;
253      if (compare(*result, segment))
254        ++result;
255    }
256    return result;
257  }
258
259
260  template<typename T, class Compare>
261  typename SegmentSet<T, Compare>::const_iterator
262  SegmentSet<T, Compare>::upper_bound(const value_type& segment) const
263  {
264    const_iterator result = set_.lower_bound(segment);
265    while (result!=end() && !compare(segment, *result))
266      ++result;
267    return result;
268  }
269
270}}}
271#endif
Note: See TracBrowser for help on using the repository browser.