1 #ifndef theplu_yat_utility_segment_tree 2 #define theplu_yat_utility_segment_tree 27 #include "yat_assert.h" 45 template<
class Container,
class Compare,
class Value2Key>
79 typedef typename Container::pointer
pointer;
250 if (first!=
begin()) {
252 if (compare(*first, segment))
256 while (last!=
end() && !compare(segment, *last))
258 YAT_ASSERT(last==
end() || compare(segment, *last));
259 return std::make_pair(first, last);
267 template<
class Container,
class Compare,
class Value2Key>
271 if (find(element)==end())
277 template<
class Container,
class Compare,
class Value2Key>
284 if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
290 template<
class Container,
class Compare,
class Value2Key>
296 if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
302 template<
typename T,
class Compare,
class Value2Key>
303 std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator,
bool>
306 return container_.insert(segment);
310 template<
typename T,
class Compare,
class Value2Key>
311 std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator,
bool>
314 return container_.insert(std::move(segment));
318 template<
typename T,
class Compare,
class Value2Key>
323 iterator result = container_.lower_bound(segment);
325 YAT_ASSERT(result==end()
326 || !compare(Value2Key()(*result),segment));
331 template<
typename T,
class Compare,
class Value2Key>
338 YAT_ASSERT(result==end()
339 || !compare(Value2Key()(*result),segment));
344 template<
typename T,
class Compare,
class Value2Key>
349 iterator result = container_.upper_bound(segment);
352 if (result==end() || comp(element, value2key(*result).begin()))
356 YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
361 template<
typename T,
class Compare,
class Value2Key>
369 if (result==end() || comp(element, value2key(*result).begin()))
373 YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
iterator upper_bound(const element_type &element)
Definition: SegmentTree.h:346
iterator begin(void)
Definition: SegmentTree.h:111
Container::iterator iterator
iterator
Definition: SegmentTree.h:89
const_iterator end(void) const
Definition: SegmentTree.h:131
iterator find(const element_type &element)
Definition: SegmentTree.h:292
void erase(iterator first, iterator last)
erase values in range [first, last)
Definition: SegmentTree.h:143
Container::value_type value_type
value type is same as Container 's value_type.
Definition: SegmentTree.h:62
Container::key_compare key_compare
key compare
Definition: SegmentTree.h:72
key_type::value_type element_type
element type is same as key_type 's value_type.
Definition: SegmentTree.h:69
iterator end(void)
Definition: SegmentTree.h:136
The Department of Theoretical Physics namespace as we define it.
Container::pointer pointer
pointer
Definition: SegmentTree.h:79
std::pair< iterator, bool > insert(const value_type &value)
insert value
Definition: SegmentTree.h:304
void erase(iterator pos)
Definition: SegmentTree.h:150
Container::const_reference const_reference
const reference
Definition: SegmentTree.h:83
Container::difference_type difference_type
difference_type
Definition: SegmentTree.h:87
void clear(void)
erases all values
Definition: SegmentTree.h:116
iterator lower_bound(const element_type &element)
similar to lower_bound in std::set and std::map
Definition: SegmentTree.h:320
Container::const_iterator const_iterator
const_iterator
Definition: SegmentTree.h:91
Container::reference reference
reference
Definition: SegmentTree.h:81
bool empty(void) const
Definition: SegmentTree.h:126
SegmentTree(void)
creates a SegmentTree with no segments
Definition: SegmentTree.h:96
key_compare key_comp(void) const
Definition: SegmentTree.h:192
a class for a Segment or Interval
Definition: Segment.h:49
virtual ~SegmentTree(void)
Destructor.
Definition: SegmentTree.h:101
Container::key_type key_type
key type is same as Container 's key_type.
Definition: SegmentTree.h:54
Container::value_compare value_compare
value compare
Definition: SegmentTree.h:74
Base Class for SegmentSet and SegmentMap.
Definition: SegmentTree.h:46
Container::size_type size_type
size_type
Definition: SegmentTree.h:85
std::pair< iterator, iterator > overlap_range(const key_type &segment)
Definition: SegmentTree.h:247
Compare element_compare
element compare
Definition: SegmentTree.h:76
size_type count(const element_type &element) const
Definition: SegmentTree.h:269
value_compare value_comp(void) const
Definition: SegmentTree.h:236
size_type size(void) const
Definition: SegmentTree.h:216
const_iterator begin(void) const
Definition: SegmentTree.h:106
Container container_
underlying container
Definition: SegmentTree.h:240