template <typename Range>

class IntervalTree

Defined at line 23 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

An associative container which holds ranges of values.

IntervalTree is capable of holding these ranges of values, but indexing by individual

values, instead of by range.

This class is thread-compatible.

Public Methods

void IntervalTree<Range> ()

Defined at line 31 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

template <typename RangeType>

bool try_insert (RangeType && range)

Inserts a range of values into the tree. If they overlap with existing ranges, they

are combined with those existing ranges. If this range cannot be combined with

existing ranges, an error is returned.

Returns true if the range is inserted successfully.

Returns false if the insertion was unsuccessful (This is only possible with an error

propagated from |Range::Container::Update|).

Runtime: O(log(number of ranges))

Defined at line 43 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

template <typename RangeType>

void insert (RangeType && range)

Inserts |range| of values into the tree.

Precondition: |range| must be either mergeable with overlapping intervals in the tree, or must

not overlap. Callers which cannot satisfy these preconditions should consider |try_insert|

instead.

Defined at line 99 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

void erase (const KeyType & value)

Erases a single value from the tree. If this value is only part of a range, that

range is split into multiple parts.

Runtime: O(log(number of ranges))

Defined at line 107 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

void erase (const RangeType & value)

Erases a range from the tree. If this range partially overlaps with ranges present in the

tree, those ranges are split into multiple parts.

Defined at line 141 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

IterType find (const KeyType & value)

Returns an iterator to the range which contains the value.

If no such range exists, returns |end()|.

Runtime: O(log(number of ranges))

Defined at line 172 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

IterType find (const RangeType & range)

Returns an iterator to the first range which overlaps with a provided range.

If no such range exists, returns |end()|.

Defined at line 194 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

void clear ()

Defined at line 217 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

bool empty ()

Defined at line 219 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

size_t size ()

Defined at line 221 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

IterType begin ()

Defined at line 223 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

ConstIterType begin ()

Defined at line 225 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

IterType end ()

Defined at line 227 of file ../../zircon/system/ulib/range/include/range/interval-tree.h

ConstIterType end ()

Defined at line 229 of file ../../zircon/system/ulib/range/include/range/interval-tree.h