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

Last change on this file since 3064 was 3064, checked in by Peter, 8 years ago

improve variable name for clearer doc

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 10.0 KB
Line 
1#ifndef theplu_yat_utility_segment_tree
2#define theplu_yat_utility_segment_tree
3
4// $Id: SegmentTree.h 3064 2013-07-09 07:44:26Z 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& element) 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       \return the \c value_compare object used by the class to sort
226       \c values
227     */
228    value_compare value_comp(void) const { return key_comp(); }
229
230  protected:
231    /// underlying container
232    Container container_;
233
234    /**
235       pair.first first (smallest) segment that overlaps with \a
236       segment and pair.second first (smallest) segment that does not
237       overlap with \a segment.
238     */
239    std::pair<iterator, iterator> overlap_range(const key_type& segment)
240    {
241      iterator first = container_.lower_bound(segment);
242      if (first!=begin()) {
243        --first;
244        if (compare(*first, segment))
245          ++first;
246      }
247      iterator last = first;
248      while (last!=end() && !compare(segment, *last))
249        ++last;
250      YAT_ASSERT(last==end() || compare(segment, *last));
251      return std::make_pair(first, last);
252    }
253
254    // using compiler generated copying
255    //SegmentTree(const SegmentTree&);
256    //SegmentTree& operator=(const SegmentTree&);
257  };
258
259  template<class Container, class Compare, class Value2Key>
260  typename SegmentTree<Container, Compare, Value2Key>::size_type
261  SegmentTree<Container,Compare,Value2Key>::count(const element_type& element) const
262  {
263    if (find(element)==end())
264      return 0;
265    return 1;
266  }
267
268
269  template<class Container, class Compare, class Value2Key>
270  typename SegmentTree<Container, Compare, Value2Key>::const_iterator
271  SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt) const
272  {
273    const_iterator iter = lower_bound(vt);
274    element_compare comp;
275    //    if (iter==end() || comp(vt, iter->begin()))
276    if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
277      return end();
278    return iter;
279  }
280
281
282  template<class Container, class Compare, class Value2Key>
283  typename SegmentTree<Container, Compare, Value2Key>::iterator
284  SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt)
285  {
286    iterator iter = lower_bound(vt);
287    element_compare comp;
288    if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
289      return end();
290    return iter;
291  }
292
293
294  template<typename T, class Compare, class Value2Key>
295  std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator, bool>
296  SegmentTree<T, Compare,Value2Key>::insert(const value_type& segment)
297  {
298    return container_.insert(segment);
299  }
300
301
302  template<typename T, class Compare, class Value2Key>
303  typename SegmentTree<T, Compare, Value2Key>::iterator
304  SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element)
305  {
306    key_type segment(element, element);
307    iterator result = container_.lower_bound(segment);
308    // result is larger or overlapping with segment (i.e.! result<segment)
309    YAT_ASSERT(result==end()
310               || !compare(Value2Key()(*result),segment));
311    return result;
312  }
313
314
315  template<typename T, class Compare, class Value2Key>
316  typename SegmentTree<T, Compare, Value2Key>::const_iterator
317  SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element) const
318  {
319    key_type segment(element, element);
320    const_iterator result = container_.lower_bound(segment);
321    // result is larger or overlapping with segment (i.e.! result<segment)
322    YAT_ASSERT(result==end()
323               || !compare(Value2Key()(*result),segment));
324    return result;
325  }
326
327
328  template<typename T, class Compare, class Value2Key>
329  typename SegmentTree<T, Compare, Value2Key>::iterator
330  SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element)
331  {
332    key_type segment(element, element);
333    iterator result = container_.upper_bound(segment);
334    Compare comp;
335    Value2Key value2key;
336    if (result==end() || comp(element, value2key(*result).begin()))
337      return result;
338    ++result;
339    // result is larger than segment
340    YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
341    return result;
342  }
343
344
345  template<typename T, class Compare, class Value2Key>
346  typename SegmentTree<T, Compare, Value2Key>::const_iterator
347  SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element) const
348  {
349    Segment<element_type, Compare> segment(element, element);
350    const_iterator result = container_.upper_bound(segment);
351    Compare comp;
352    Value2Key value2key;
353    if (result==end() || comp(element, value2key(*result).begin()))
354      return result;
355    ++result;
356    // result is larger than segment
357    YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
358    return result;
359  }
360
361}}}
362#endif
Note: See TracBrowser for help on using the repository browser.