[#llvm-IntervalTree-08]
= xref:llvm.adoc[llvm]::IntervalTree
:relfileprefix: ../
:mrdocs:

Interval tree that stores closed intervals and answers point queries.

== Synopsis

Declared in `<llvm/ADT/IntervalTree.h>`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
template<
    typename PointT,
    typename ValueT,
    typename DataT = xref:llvm/IntervalData.adoc[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

[cols="1,4"]
|===
| Name| Description
| xref:llvm/IntervalTree-08/find_iterator.adoc[`find_iterator`] 
| Forward iterator over intervals that contain a query point.
|===


== Type Aliases

[cols="1,4"]
|===
| Name| Description
| xref:llvm/IntervalTree-08/Allocator.adoc[`Allocator`] 
| Allocator used for tree nodes.
| xref:llvm/IntervalTree-08/DataType.adoc[`DataType`] 
| Interval record type stored in the tree.
| xref:llvm/IntervalTree-08/IntervalReferences.adoc[`IntervalReferences`] 
| Collection of pointers to intervals that contain a query point.
| xref:llvm/IntervalTree-08/PointType.adoc[`PointType`] 
| Type of interval endpoints.
| xref:llvm/IntervalTree-08/ValueType.adoc[`ValueType`] 
| Type of values stored with intervals.
|===


== Enums

[cols="1,4"]
|===
| Name| Description
| xref:llvm/IntervalTree-08/Sorting.adoc[`Sorting`] 
| Ordering used when sorting overlapping interval results.
|===


== Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:llvm/IntervalTree-08/2constructor.adoc[`IntervalTree`]         [.small]#[constructor]#
| Construct an empty interval tree that allocates nodes from `NodeAllocator.`
| xref:llvm/IntervalTree-08/2destructor.adoc[`~IntervalTree`] [.small]#[destructor]#
| Destroy the tree and release allocated nodes.
| xref:llvm/IntervalTree-08/clear.adoc[`clear`] 
| Remove all entries.
| xref:llvm/IntervalTree-08/create.adoc[`create`] 
| Create the interval tree.
| xref:llvm/IntervalTree-08/empty.adoc[`empty`] 
| Return true when no intervals are mapped.
| xref:llvm/IntervalTree-08/find.adoc[`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.
| xref:llvm/IntervalTree-08/find_end.adoc[`find_end`] 
| Iterator to end find operation.
| xref:llvm/IntervalTree-08/getContaining.adoc[`getContaining`] 
| Return all the intervals in their natural tree location, that contain the given point.
| xref:llvm/IntervalTree-08/insert.adoc[`insert`] 
| Add a mapping of [Left;Right]to _Value._
| xref:llvm/IntervalTree-08/print.adoc[`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

[cols="1,4"]
|===
| Name| Description
| xref:llvm/IntervalTree-08/sortIntervals.adoc[`sortIntervals`] 
| Sort overlapping intervals in ascending or descending order by span.
|===


== Template Parameters

[cols="1,4"]
|===
| 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).
|===


[.small]#Created with https://www.mrdocs.com[MrDocs]#