acav::IntervalTree Class Reference

Sorted array for interval queries. More...

#include <SourceLocationIndex.h>

Public Member Functions
	IntervalTree (const IntervalTree &)=delete
IntervalTree &	operator= (const IntervalTree &)=delete
void	insert (Interval interval)
	Add interval to collection (not sorted yet).
void	finalize ()
	Sort intervals by start position (call once after all inserts).
std::vector< AstViewNode * >	query (unsigned line, unsigned column) const
	Find all intervals containing a point.
AstViewNode *	queryFirstContained (unsigned beginLine, unsigned beginColumn, unsigned endLine, unsigned endColumn) const
	Find first interval fully contained within a range.
std::size_t	size () const
	Get total number of intervals.

Detailed Description

Sorted array for interval queries.

Stores source ranges in a sorted vector for efficient point queries. Uses binary search for lookup.

Complexity:

• Insert: O(1) amortized (vector push_back)
• Finalize: O(n log n) (one-time sort)
• Query: O(log n + k) where k = number of matches

Definition at line 63 of file SourceLocationIndex.h.

Member Function Documentation

finalize()

void acav::IntervalTree::finalize

(

)

Sort intervals by start position (call once after all inserts).

Definition at line 59 of file SourceLocationIndex.cpp.

insert()

void acav::IntervalTree::insert

(

Interval

interval

)

Add interval to collection (not sorted yet).

Parameters

interval

The source range and associated node

Definition at line 55 of file SourceLocationIndex.cpp.

query()

std::vector< AstViewNode * > acav::IntervalTree::query	(	unsigned	line,
		unsigned	column ) const

Find all intervals containing a point.

Parameters

line	Source line number (1-based)
column	Source column number (1-based)

Returns

Vector of nodes sorted by depth (deepest first)

Definition at line 69 of file SourceLocationIndex.cpp.

queryFirstContained()

AstViewNode * acav::IntervalTree::queryFirstContained	(	unsigned	beginLine,
		unsigned	beginColumn,
		unsigned	endLine,
		unsigned	endColumn ) const

Find first interval fully contained within a range.

Parameters

beginLine	Range start line (1-based)
beginColumn	Range start column (1-based)
endLine	Range end line (1-based)
endColumn	Range end column (1-based)

Returns

First node whose interval is inside the range, or nullptr

Definition at line 98 of file SourceLocationIndex.cpp.

size()

std::size_t acav::IntervalTree::size ( ) const

inline

Get total number of intervals.

Definition at line 95 of file SourceLocationIndex.h.

---

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

• app/include/core/SourceLocationIndex.h
• app/core/SourceLocationIndex.cpp