1 #ifndef theplu_yat_utility_segment_tree
2 #define theplu_yat_utility_segment_tree
27 #include "yat_assert.h"
44 template<
class Container,
class Compare,
class Value2Key>
78 typedef typename Container::pointer
pointer;
242 if (first!=
begin()) {
244 if (compare(*first, segment))
248 while (last!=
end() && !compare(segment, *last))
250 YAT_ASSERT(last==
end() || compare(segment, *last));
251 return std::make_pair(first, last);
259 template<
class Container,
class Compare,
class Value2Key>
260 typename SegmentTree<Container, Compare, Value2Key>::size_type
263 if (find(element)==end())
269 template<
class Container,
class Compare,
class Value2Key>
276 if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
282 template<
class Container,
class Compare,
class Value2Key>
288 if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
294 template<
typename T,
class Compare,
class Value2Key>
295 std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator,
bool>
298 return container_.insert(segment);
302 template<
typename T,
class Compare,
class Value2Key>
307 iterator result = container_.lower_bound(segment);
309 YAT_ASSERT(result==end()
310 || !compare(Value2Key()(*result),segment));
315 template<
typename T,
class Compare,
class Value2Key>
322 YAT_ASSERT(result==end()
323 || !compare(Value2Key()(*result),segment));
328 template<
typename T,
class Compare,
class Value2Key>
333 iterator result = container_.upper_bound(segment);
336 if (result==end() || comp(element, value2key(*result).begin()))
340 YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
345 template<
typename T,
class Compare,
class Value2Key>
353 if (result==end() || comp(element, value2key(*result).begin()))
357 YAT_ASSERT(result==end() || compare(segment, value2key(*result)));