tpl_interval_tree.H File Reference

Interval tree: augmented BST for overlap/stabbing queries. More...

#include <gsl/gsl_rng.h>
#include <cassert>
#include <ctime>
#include <type_traits>
#include <ahFunction.H>
#include <tpl_binNodeUtils.H>
#include <treapNode.H>
#include <tpl_binTreeOps.H>
#include <ah-errors.H>
#include <ah-concepts.H>
#include <ah-dry.H>
#include <ahDry.H>
#include <htlist.H>
#include <utility>
#include <memory>

Include dependency graph for tpl_interval_tree.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Interval< T >
	Closed interval [low, high]. More...
struct	Aleph::Interval_Less< T, Compare >
	BST comparator for intervals: order by (low, then high). More...
struct	Aleph::interval_endpoint< Interval< T > >
	Specialization for Interval<T>. More...
class	Aleph::Interval_Tree_Node_Data< T >
	Data portion of an interval tree node. More...
class	Aleph::Interval_Tree_Node< Key >
	Interval tree node with sentinel support. More...
class	Aleph::Interval_Tree_NodeVtl< Key >
	Interval tree node with virtual destructor. More...
class	Aleph::Gen_Interval_Tree< NodeType, T, Compare >
	Augmented treap storing intervals with overlap/stabbing queries. More...
struct	Aleph::Gen_Interval_Tree< NodeType, T, Compare >::Iterator
	Inorder iterator over nodes. More...
struct	Aleph::Interval_Tree< T, Compare >
	Interval tree using nodes without virtual destructor. More...
struct	Aleph::Interval_Tree_Vtl< T, Compare >
	Interval tree using nodes with virtual destructor. More...
class	Aleph::DynIntervalTree< T, Compare >
	High-level interval tree with automatic memory management. More...
class	Aleph::DynIntervalTree< T, Compare >::Iterator
	Inorder iterator yielding Interval<T> keys. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Typedefs
template<typename Key >
using	Aleph::interval_endpoint_t = typename interval_endpoint< Key >::type

Functions
template<class Node >
auto &	Aleph::MAX_EP (Node *p) noexcept
	Access max_endpoint of an interval tree node.
template<class Node >
const auto &	Aleph::MAX_EP (const Node *p) noexcept

Detailed Description

Interval tree: augmented BST for overlap/stabbing queries.

An interval tree stores closed intervals [low, high] and efficiently answers overlap and stabbing queries in O(log n) expected time.

The implementation is an augmented treap where each node stores the maximum endpoint in its subtree. This allows pruning entire subtrees during overlap searches.

Features

• Insert/remove intervals: O(log n) expected
• Overlap search (find one): O(log n) expected
• Find all overlaps: O(k log n) where k = number of results
• Stabbing query: O(k log n)

Applications

• Sweep-line segment intersection
• Temporal scheduling conflict detection
• Windowing queries in computational geometry

See also

tpl_treap.H Base treap

Author

Leandro Rabindranath Leon

Definition in file tpl_interval_tree.H.