source: trunk/yat/utility/SegmentTree.h @ 2611

Last change on this file since 2611 was 2611, checked in by Peter, 10 years ago

fixes #680 and #679

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 9.3 KB
Line 
1#ifndef theplu_yat_utility_segment_tree
2#define theplu_yat_utility_segment_tree
3
4// $Id: SegmentTree.h 2611 2011-11-04 23:03:50Z 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
27#include "yat_assert.h"
28
29#include <algorithm>
30#include <functional>
31
32namespace theplu {
33namespace yat {
34namespace utility {
35
36  /**
37     \brief Base Class for SegmentSet and SegmentMap
38
39     - Container: underlying container (set or map)
40     - Compare: functor comparing elements (same as in Segment)
41     - Value2Key: functor translating a \c const_reference to \c
42       key_type (or \c const&)
43   */
44  template<class Container, class Compare, class Value2Key>
45  class SegmentTree
46  {
47  public:
48    /// \brief key type
49    typedef typename Container::key_type key_type;
50    /// \brief value type
51    typedef typename Container::value_type value_type;
52    /// \brief element type
53    typedef typename key_type::value_type element_type;
54
55    /// \brief key compare
56    typedef typename Container::key_compare key_compare;
57    /// \brief value compare
58    typedef typename Container::value_compare value_compare;
59    /// \brief element compare
60    typedef Compare element_compare;
61
62    /// \brief pointer
63    typedef typename Container::pointer pointer;
64    /// \brief reference
65    typedef typename Container::reference reference;
66    /// \brief const reference
67    typedef typename Container::const_reference const_reference;
68    /// \brief size_type
69    typedef typename Container::size_type size_type;
70    /// \brief difference_type
71    typedef typename Container::difference_type difference_type;
72    /// \brief iterator
73    typedef typename Container::iterator iterator;
74    /// \brief const_iterator
75    typedef typename Container::const_iterator const_iterator;
76
77    /**
78       \brief creates a container with no segments
79     */
80    SegmentTree(void) {}
81
82    /**
83       \brief Destructor
84    */
85    virtual ~SegmentTree(void) {}
86
87    /**
88       \return const iterator to first Segment
89     */
90    const_iterator begin(void) const { return container_.begin(); }
91
92    /**
93       \return iterator to first Segment
94     */
95    iterator begin(void) { return container_.begin(); }
96
97    /**
98       \brief erases all segments
99     */
100    void clear(void) { container_.clear(); }
101
102    /**
103       \return 1 if there is a set that overlaps with \a element
104     */
105    size_type count(const element_type& element) const;
106
107    /**
108       \return \c true if size is zero
109    */
110    bool empty(void) const { return container_.empty(); }
111
112    /**
113       \return end of set
114     */
115    const_iterator end(void) const { return container_.end(); }
116
117    /**
118       \return end of set
119     */
120    iterator end(void) { return container_.end(); }
121
122    /**
123       erase segments in range [first, last)
124
125       \since New in yat 0.8
126     */
127    void erase(iterator first, iterator last) { container_.erase(first, last);}
128
129    /**
130       erase segment pointed to by \a pos
131
132       \since New in yat 0.8
133     */
134    void erase(iterator pos) { container_.erase(pos); }
135
136    /**
137       \return an iterator pointing to the Segment that contains \a
138       vt. If no Segment contains \a vt, end() is returned.
139
140       \since New in yat 0.8
141     */
142    iterator find(const element_type& vt);
143
144    /**
145       \return an iterator pointing to the Segment that contains \a
146       vt. If no Segment contains \a vt, end() is returned.
147     */
148    const_iterator find(const element_type& vt) const;
149
150    /**
151       \brief insert value
152
153       if \a segment does not overlap with any segment in set, insert
154       segment; otherwise do nothing.
155
156       \return a pair where pair.first points to the added \a segment
157       or if \a segment was not added it points to a Segment in set
158       that overlaps with \a segment; pair.second is true if \a
159       segment was added.
160     */
161    std::pair<iterator, bool> insert(const value_type& segment);
162
163    /**
164       \return Comparison functor to compare to segments
165     */
166    key_compare key_comp(void) const 
167    { 
168      return key_compare(compare);
169    }
170
171    /**
172       \return iterator pointing to first segment that overlaps with
173       \a element or is greater than \a element.
174     */
175    iterator lower_bound(const element_type& element);
176
177    /**
178       \return iterator pointing to first segment that overlaps with
179       \a element or is greater than \a element.
180     */
181    const_iterator lower_bound(const element_type& element) const;
182
183    /**
184       \return number of segments in set
185     */
186    size_type size(void) const { return container_.size(); }
187
188    /**
189       \return iterator pointing to first segment that is greater than
190       \a segment.
191     */
192    iterator upper_bound(const element_type& element);
193
194    /**
195       \return iterator pointing to first segment that is greater than
196       \a segment.
197     */
198    const_iterator upper_bound(const element_type& element) const;
199
200    /**
201       \return Comparison functor to compare to segments
202     */
203    value_compare value_comp(void) const { return key_comp(); }
204
205  protected:
206    /// underlying container
207    Container container_;
208
209    /**
210       pair.first first (smallest) segment that overlaps with \a
211       segment and pair.second first (smallest) segment that does not
212       overlap with \a segment.
213     */
214    std::pair<iterator, iterator> overlap_range(const key_type& segment) 
215    {
216      iterator first = container_.lower_bound(segment);
217      if (first!=begin()) {
218        --first;
219        if (compare(*first, segment))
220          ++first;
221      }
222      iterator last = first;
223      while (last!=end() && !compare(segment, *last))
224        ++last;
225      YAT_ASSERT(last==end() || compare(segment, *last));
226      return std::make_pair(first, last);
227    }
228
229    // using compiler generated copying
230    //SegmentTree(const SegmentTree&);
231    //SegmentTree& operator=(const SegmentTree&);
232  };
233
234  template<class Container, class Compare, class Value2Key>
235  typename SegmentTree<Container, Compare, Value2Key>::size_type
236  SegmentTree<Container,Compare,Value2Key>::count(const element_type& element) const
237  {
238    if (find(element)==end())
239      return 0;
240    return 1;
241  }
242
243
244  template<class Container, class Compare, class Value2Key>
245  typename SegmentTree<Container, Compare, Value2Key>::const_iterator
246  SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt) const
247  {
248    const_iterator iter = lower_bound(vt);
249    element_compare comp;
250    //    if (iter==end() || comp(vt, iter->begin()))
251    if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
252      return end();
253    return iter;
254  }
255
256
257  template<class Container, class Compare, class Value2Key>
258  typename SegmentTree<Container, Compare, Value2Key>::iterator
259  SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt)
260  {
261    iterator iter = lower_bound(vt);
262    element_compare comp;
263    if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
264      return end();
265    return iter;
266  }
267
268
269  template<typename T, class Compare, class Value2Key>
270  std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator, bool> 
271  SegmentTree<T, Compare,Value2Key>::insert(const value_type& segment)
272  {
273    return container_.insert(segment);
274  }
275
276
277  template<typename T, class Compare, class Value2Key>
278  typename SegmentTree<T, Compare, Value2Key>::iterator
279  SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element)
280  {
281    key_type segment(element, element);
282    iterator result = container_.lower_bound(segment);
283    // result is larger or overlapping with segment (i.e.! result<segment)
284    YAT_ASSERT(result==end() 
285               || !compare(Value2Key()(*result),segment));
286    return result;
287  }
288
289
290  template<typename T, class Compare, class Value2Key>
291  typename SegmentTree<T, Compare, Value2Key>::const_iterator
292  SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element) const
293  {
294    key_type segment(element, element);
295    const_iterator result = container_.lower_bound(segment);
296    // result is larger or overlapping with segment (i.e.! result<segment)
297    YAT_ASSERT(result==end() 
298               || !compare(Value2Key()(*result),segment));
299    return result;
300  }
301
302
303  template<typename T, class Compare, class Value2Key>
304  typename SegmentTree<T, Compare, Value2Key>::iterator
305  SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element)
306  {
307    key_type segment(element, element);
308    iterator result = container_.upper_bound(segment);
309    Compare comp;
310    Value2Key value2key;
311    if (result==end() || comp(element, value2key(*result).begin()))
312      return result;
313    ++result;
314    // result is larger than segment
315    YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
316    return result;
317  }
318
319
320  template<typename T, class Compare, class Value2Key>
321  typename SegmentTree<T, Compare, Value2Key>::const_iterator
322  SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element) const
323  {
324    Segment<element_type, Compare> segment(element, element);
325    const_iterator result = container_.upper_bound(segment);
326    Compare comp;
327    Value2Key value2key;
328    if (result==end() || comp(element, value2key(*result).begin()))
329      return result;
330    ++result;
331    // result is larger than segment
332    YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
333    return result;
334  }
335
336}}}
337#endif
Note: See TracBrowser for help on using the repository browser.