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

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

adding more types required to conform to 'Unique Sorted Associated Container'

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