IntervalTree< T > Class Template Reference

A specialized implementation of an Interval Tree for Bash++'s particular use case. More...

#include <IntervalTree.h>

Public Member Functions
	IntervalTree ()
void	insert (uint64_t low, uint64_t high, T payload)
std::vector< T >	find_overlaps (uint64_t point)
T	find_innermost_overlap (uint64_t point)
	Find the innermost interval that contains the given point.

Private Member Functions
uint64_t	find_max (std::unique_ptr< IntervalNode< T > > &node)
void	insert_node (std::unique_ptr< IntervalNode< T > > &node, uint64_t low, uint64_t high, T payload)
void	find_overlaps (std::unique_ptr< IntervalNode< T > > &node, uint64_t point, std::vector< T > &overlaps)

Private Attributes
std::unique_ptr< IntervalNode< T > >	_root

Detailed Description

template<class T>
class IntervalTree< T >

A specialized implementation of an Interval Tree for Bash++'s particular use case.

This implementation is designed to efficiently manage and query intervals, allowing for fast insertion, deletion, and overlap detection.

Some particularities about our implementation:

1. Partial overlaps are not possible in the Bash++ compiler All intervals are either entirely contained within wider intervals (e.g., [0 [50, 75] 100]) Or entirely disjoint (e.g., [0, 100] [101, 110]) Partial overlaps can never happen
2. This implementation guarantees that wider (parent) intervals are always placed above narrower (children) intervals in the tree. If [50, 75] is inserted, and then [0, 100] is inserted afterwards, The tree will re-order itself such that [0, 100] becomes the new root, with [50, 75] as its child.

These invariants are crucial for the tree's primary function in the compiler: find_innermost_overlap

Template Parameters

T	The type of the payload stored in each interval node.

Constructor & Destructor Documentation

IntervalTree()

template<class T >

IntervalTree< T >::IntervalTree ( )

inline

Member Function Documentation

find_innermost_overlap()

template<class T >

T IntervalTree< T >::find_innermost_overlap ( uint64_t  point )

inline

Find the innermost interval that contains the given point.

This function traverses the interval tree to find the innermost interval that contains the specified point.

Given our tree's invariants, this task is equivalent to either of:

1. Finding the overlapping interval with the highest start position.
2. Finding the deepest interval in the tree that contains the point.

So, this implementation simply traverses the tree, and returns the last overlapping node that it finds, which is guaranteed to be the innermost one due to the tree's structure.

Parameters

point

The point to check for overlaps.

Returns

T The payload of the innermost overlapping interval, or a default-constructed T if none is found.

find_max()

template<class T >

uint64_t IntervalTree< T >::find_max ( std::unique_ptr< IntervalNode< T > > &  node )

inlineprivate

find_overlaps() [1/2]

template<class T >

void IntervalTree< T >::find_overlaps ( std::unique_ptr< IntervalNode< T > > &  node, uint64_t  point, std::vector< T > &  overlaps  )

inlineprivate

find_overlaps() [2/2]

template<class T >

std::vector< T > IntervalTree< T >::find_overlaps ( uint64_t  point )

inline

insert()

template<class T >

void IntervalTree< T >::insert ( uint64_t  low, uint64_t  high, T  payload  )

inline

insert_node()

template<class T >

void IntervalTree< T >::insert_node ( std::unique_ptr< IntervalNode< T > > &  node, uint64_t  low, uint64_t  high, T  payload  )

inlineprivate

Member Data Documentation

_root

template<class T >

std::unique_ptr<IntervalNode<T> > IntervalTree< T >::_root

private

---

The documentation for this class was generated from the following file:

• src/include/IntervalTree.h