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

Last change on this file since 2703 was 2703, checked in by Peter, 11 years ago

merge release 0.8.1 into trunk

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