augmentedtree

Documentation

Overview

Package augmentedtree is designed to be useful when checking for intersection of ranges in n-dimensions. For instance, if you imagine an xy plane then the augmented tree is for telling you if plane defined by the points (0, 0) and (10, 10). The augmented tree can tell you if that plane overlaps with a plane defined by (-5, -5) and (5, 5) (true in this case). You can also check intersections against a point by constructing a range of encompassed solely if a single point.

The current tree is a simple top-down red-black binary search tree.

TODO: Add a bottom-up implementation to assist with duplicate range handling.

Index

• type Interval
• type Intervals
  • func (ivs *Intervals) Dispose()
• type Tree
  • func New(dimensions uint64) Tree

Types

type Interval

type Interval interface {
	// LowAtDimension returns an integer representing the lower bound
	// at the requested dimension.
	LowAtDimension(uint64) int64
	// HighAtDimension returns an integer representing the higher bound
	// at the requested dimension.
	HighAtDimension(uint64) int64
	// OverlapsAtDimension should return a bool indicating if the provided
	// interval overlaps this interval at the dimension requested.
	OverlapsAtDimension(Interval, uint64) bool
	// ID should be a unique ID representing this interval.  This
	// is used to identify which interval to delete from the tree if
	// there are duplicates.
	ID() uint64
}

Interval is the interface that must be implemented by any item added to the interval tree. This interface is similar to the interval found in the rangetree package and it should be possible for the same struct to implement both interfaces. Note that ranges here are inclusive. It is also expected that the provided interval is immutable and that the returned values never change. Doing so results in undefined behavior.

type Intervals

type Intervals []Interval

Intervals represents a list of Intervals.

func (*Intervals) Dispose

func (ivs *Intervals) Dispose()

Dispose will free any consumed resources and allow this list to be re-allocated.

type Tree

type Tree interface {
	// Add will add the provided intervals to the tree.
	Add(intervals ...Interval)
	// Len returns the number of intervals in the tree.
	Len() uint64
	// Delete will remove the provided intervals from the tree.
	Delete(intervals ...Interval)
	// Query will return a list of intervals that intersect the provided
	// interval.  The provided interval's ID method is ignored so the
	// provided ID is irrelevant.
	Query(interval Interval) Intervals
}

Tree defines the object that is returned from the tree constructor. We use a Tree interface here because the returned tree could be a single dimension or many dimensions.

func New

func New(dimensions uint64) Tree

New constructs and returns a new interval tree with the max dimensions provided.