yat  0.14.5pre
SegmentTree.h
1 #ifndef theplu_yat_utility_segment_tree
2 #define theplu_yat_utility_segment_tree
3 
4 // $Id: SegmentTree.h 3114 2013-11-10 23:51:47Z peter $
5 
6 /*
7  Copyright (C) 2010, 2011, 2012, 2013 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 
32 namespace theplu {
33 namespace yat {
34 namespace utility {
35 
44  template<class Container, class Compare, class Value2Key>
46  {
47  public:
53  typedef typename Container::key_type key_type;
54 
61  typedef typename Container::value_type value_type;
62 
68  typedef typename key_type::value_type element_type;
69 
71  typedef typename Container::key_compare key_compare;
73  typedef typename Container::value_compare value_compare;
75  typedef Compare element_compare;
76 
78  typedef typename Container::pointer pointer;
80  typedef typename Container::reference reference;
82  typedef typename Container::const_reference const_reference;
84  typedef typename Container::size_type size_type;
86  typedef typename Container::difference_type difference_type;
88  typedef typename Container::iterator iterator;
90  typedef typename Container::const_iterator const_iterator;
91 
95  SegmentTree(void) {}
96 
100  virtual ~SegmentTree(void) {}
101 
105  const_iterator begin(void) const { return container_.begin(); }
106 
110  iterator begin(void) { return container_.begin(); }
111 
115  void clear(void) { container_.clear(); }
116 
120  size_type count(const element_type& element) const;
121 
125  bool empty(void) const { return container_.empty(); }
126 
130  const_iterator end(void) const { return container_.end(); }
131 
135  iterator end(void) { return container_.end(); }
136 
142  void erase(iterator first, iterator last) { container_.erase(first, last);}
143 
149  void erase(iterator pos) { container_.erase(pos); }
150 
156  iterator find(const element_type& element);
157 
166  const_iterator find(const element_type& element) const;
167 
179  std::pair<iterator, bool> insert(const value_type& value);
180 
184  key_compare key_comp(void) const
185  {
186  return key_compare(compare);
187  }
188 
195  iterator lower_bound(const element_type& element);
196 
203  const_iterator lower_bound(const element_type& element) const;
204 
208  size_type size(void) const { return container_.size(); }
209 
214  iterator upper_bound(const element_type& element);
215 
222  const_iterator upper_bound(const element_type& element) const;
223 
228  value_compare value_comp(void) const { return key_comp(); }
229 
230  protected:
232  Container container_;
233 
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
262  {
263  if (find(element)==end())
264  return 0;
265  return 1;
266  }
267 
268 
269  template<class Container, class Compare, class Value2Key>
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>
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>
297  {
298  return container_.insert(segment);
299  }
300 
301 
302  template<typename T, class Compare, class Value2Key>
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>
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>
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>
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
iterator upper_bound(const element_type &element)
Definition: SegmentTree.h:330
iterator begin(void)
Definition: SegmentTree.h:110
Container::iterator iterator
iterator
Definition: SegmentTree.h:88
iterator find(const element_type &element)
Definition: SegmentTree.h:284
void erase(iterator first, iterator last)
erase values in range [first, last)
Definition: SegmentTree.h:142
Container::value_type value_type
value type is same as Container &#39;s value_type.
Definition: SegmentTree.h:61
Container::key_compare key_compare
key compare
Definition: SegmentTree.h:71
key_type::value_type element_type
element type is same as key_type &#39;s value_type.
Definition: SegmentTree.h:68
size_type count(const element_type &element) const
Definition: SegmentTree.h:261
iterator end(void)
Definition: SegmentTree.h:135
value_compare value_comp(void) const
Definition: SegmentTree.h:228
Container::pointer pointer
pointer
Definition: SegmentTree.h:78
std::pair< iterator, bool > insert(const value_type &value)
insert value
Definition: SegmentTree.h:296
void erase(iterator pos)
Definition: SegmentTree.h:149
Container::const_reference const_reference
const reference
Definition: SegmentTree.h:82
Container::difference_type difference_type
difference_type
Definition: SegmentTree.h:86
void clear(void)
erases all values
Definition: SegmentTree.h:115
iterator lower_bound(const element_type &element)
similar to lower_bound in std::set and std::map
Definition: SegmentTree.h:304
Container::const_iterator const_iterator
const_iterator
Definition: SegmentTree.h:90
Container::reference reference
reference
Definition: SegmentTree.h:80
const_iterator begin(void) const
Definition: SegmentTree.h:105
SegmentTree(void)
creates a SegmentTree with no segments
Definition: SegmentTree.h:95
bool empty(void) const
Definition: SegmentTree.h:125
a class for a Segment or Interval
Definition: Segment.h:47
virtual ~SegmentTree(void)
Destructor.
Definition: SegmentTree.h:100
Container::key_type key_type
key type is same as Container &#39;s key_type.
Definition: SegmentTree.h:53
size_type size(void) const
Definition: SegmentTree.h:208
Container::value_compare value_compare
value compare
Definition: SegmentTree.h:73
Base Class for SegmentSet and SegmentMap.
Definition: SegmentTree.h:45
Container::size_type size_type
size_type
Definition: SegmentTree.h:84
std::pair< iterator, iterator > overlap_range(const key_type &segment)
Definition: SegmentTree.h:239
Compare element_compare
element compare
Definition: SegmentTree.h:75
key_compare key_comp(void) const
Definition: SegmentTree.h:184
Container container_
underlying container
Definition: SegmentTree.h:232
const_iterator end(void) const
Definition: SegmentTree.h:130

Generated on Tue Sep 26 2017 02:33:29 for yat by  doxygen 1.8.5