FlatIntervalTree< T > Class Template Reference

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

#include <IntervalTree.h>

Classes
struct	Interval

Public Member Functions
void	insert (uint64_t low, uint64_t high, T payload)
T	find_innermost_overlap (uint64_t point)
	Find the innermost interval that overlaps a given point.

Private Member Functions
void	ensure_sorted ()

Private Attributes
std::vector< Interval >	intervals
bool	sorted = false

Detailed Description

template<class T>
class FlatIntervalTree< T >

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

Copyright (C) 2025 Andrew S. Rightenburg Bash++: Bash with classes

This implementation is designed to efficiently store and query intervals representing code entities in Bash++ source files. It supports insertion of intervals and querying for the innermost overlapping interval at a given point.

It's possible to design this as a "flat" structure because of our invariants:

1. Intervals are only inserted and never removed.
2. Queries are only made after all insertions are complete.
3. Intervals do not partially overlap; they are either entirely nested or entirely disjoint.

These invariants allow us to use a sorted vector and binary search for efficient querying, avoiding the complexity of a traditional tree structure.

Template Parameters

T	The type of the payload associated with each interval.

Member Function Documentation

ensure_sorted()

template<class T >

void FlatIntervalTree< T >::ensure_sorted ( )

inlineprivate

find_innermost_overlap()

template<class T >

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

inline

Find the innermost interval that overlaps a given point.

This function performs a binary search to efficiently locate the innermost interval that contains the specified point. If no such interval exists, it returns a default-constructed T.

Parameters

point

The point to query.

Returns

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

insert()

template<class T >

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

inline

Member Data Documentation

intervals

template<class T >

std::vector<Interval> FlatIntervalTree< T >::intervals

private

sorted

template<class T >

bool FlatIntervalTree< T >::sorted = false

private

---

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

• src/include/IntervalTree.h