Interval tree that stores closed intervals and answers point queries.

Synopsis

Declared in <llvm/ADT/IntervalTree.h>

template<
    typename PointT,
    typename ValueT,
    typename DataT = IntervalData<PointT, ValueT>>
class IntervalTree;

Description

Intervals are inserted offline and then built into a tree. Queries return all intervals that contain a given point, optionally sorted by endpoint.

Types

Name

Description

find_iterator

Forward iterator over intervals that contain a query point.

Type Aliases

Name

Description

Allocator

Allocator used for tree nodes.

DataType

Interval record type stored in the tree.

IntervalReferences

Collection of pointers to intervals that contain a query point.

PointType

Type of interval endpoints.

ValueType

Type of values stored with intervals.

Enums

Name

Description

Sorting

Ordering used when sorting overlapping interval results.

Member Functions

Name

Description

IntervalTree [constructor]

Construct an empty interval tree that allocates nodes from NodeAllocator.

~IntervalTree [destructor]

Destroy the tree and release allocated nodes.

clear

Remove all entries.

create

Create the interval tree.

empty

Return true when no intervals are mapped.

find

Iterator to start a find operation; it returns find_end() if the tree has not been built. There is no support to iterate over all the elements of the tree.

find_end

Iterator to end find operation.

getContaining

Return all the intervals in their natural tree location, that contain the given point.

insert

Add a mapping of [Left;Right]to Value.

print

Print the interval tree. When HexFormat is true, the interval tree interval ranges and associated values are printed in hexadecimal format.

Static Member Functions

Name

Description

sortIntervals

Sort the given intervals using the following sort options: Ascending: return the intervals with the smallest at the front. Descending: return the intervals with the biggest at the front.

Specializations

Name

Description

IntervalTree<unsigned long, LVScope*>

Interval tree that stores closed intervals and answers point queries.

Template Parameters

Name

Description

PointT

Fundamental type used for interval endpoints.

ValueT

Fundamental or pointer type stored with each interval.

DataT

Interval record type (defaults to IntervalData).

Created with MrDocs