SegmentTree¶

Overview¶

An accelerated data structure of items where it supports fast queries of "what items overlap wth x values", so we don't have to iterate through all items.

This effectively combines an interval/segment tree with red-black tree balancing for insertion.

For proper red-black constraints, we handle ranges from -infinity to infinity.

@author Jonathan Olson <jonathan.olson@colorado.edu>

Class SegmentTree¶

import { SegmentTree } from 'scenerystack/kite';

Constructor¶

new SegmentTree( epsilon )¶

Instance Methods¶

getMinX( item : T, epsilon : number ) : number¶

getMaxX( item : T, epsilon : number ) : number¶

query( item : T, interruptableCallback : ( item: T ) => boolean ) : boolean¶

Calls interruptableCallback in turn for every "possibly overlapping" item stored in this tree.

@param item - The item to use for the bounds range. @param interruptableCallback - When this returns true, the search will be aborted

addItem( item : T )¶

removeItem( item : T )¶

audit()¶

For assertion purposes

toString() : string¶

Instance Properties¶

rootNode : SegmentNode<T>¶

Source Code¶

See the source for SegmentTree.ts in the kite repository.