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

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

added some more types to SegmentSet?'s public interface

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