interval

Documentation

Overview

Package interval implements an interval tree based on an augmented Left-Leaning Red Black tree.

Index

• Constants
• Variables
• type Comparable
  • func (c Comparable) Compare(o Comparable) int
• type Interface
• type Node
• type Operation
• type Overlapper
• type Range
• type Tree
  • func (t *Tree) AdjustRanges()
  • func (t *Tree) Ceil(q Interface) (o Interface, err error)
  • func (t *Tree) Delete(e Interface, fast bool) (err error)
  • func (t *Tree) DeleteMax(fast bool)
  • func (t *Tree) DeleteMin(fast bool)
  • func (t *Tree) Do(fn Operation) bool
  • func (t *Tree) DoMatching(fn Operation, q Overlapper) bool
  • func (t *Tree) DoMatchingReverse(fn Operation, q Overlapper) bool
  • func (t *Tree) DoReverse(fn Operation) bool
  • func (t *Tree) Floor(q Interface) (o Interface, err error)
  • func (t *Tree) Get(q Overlapper) (o []Interface)
  • func (t *Tree) Insert(e Interface, fast bool) (err error)
  • func (t *Tree) Len() int
  • func (t *Tree) Max() Interface
  • func (t *Tree) Min() Interface

Constants

const (
	TD234 = iota
	BU23
)

Operation mode of the underlying LLRB tree.

const Mode = BU23

Mode .

Variables

var ErrInvertedRange = errors.New("interval: inverted range")

ErrInvertedRange is returned if an interval is used where the start value is greater than the end value.

Types

type Comparable

type Comparable []byte

A Comparable is a type that describes the ends of an Overlapper.

func (Comparable) Compare

func (c Comparable) Compare(o Comparable) int

Compare returns a value indicating the sort order relationship between the receiver and the parameter.

Given c = a.Compare(b):

c < 0 if a < b;
c == 0 if a == b; and
c > 0 if a > b.

type Interface

type Interface interface {
	Overlapper
	Range() Range
	ID() uintptr // Returns a unique ID for the element.
}

An Interface is a type that can be inserted into a Tree.

type Node

type Node struct {
	Elem        Interface
	Range       Range
	Left, Right *Node
	Color       llrb.Color
}

A Node represents a node in a Tree.

type Operation

type Operation func(Interface) (done bool)

An Operation is a function that operates on an Interface. If done is returned true, the Operation is indicating that no further work needs to be done and so the Do function should traverse no further.

type Overlapper

type Overlapper interface {
	// Overlap returns a boolean indicating whether the receiver overlaps the parameter.
	Overlap(Range) bool
}

An Overlapper can determine whether it overlaps a range.

type Range

type Range struct {
	Start, End Comparable
}

A Range is a type that describes the basic characteristics of an interval.

type Tree

type Tree struct {
	Root  *Node // Root node of the tree.
	Count int   // Number of elements stored.
}

A Tree manages the root node of an interval tree. Public methods are exposed through this type.

func (*Tree) AdjustRanges

func (t *Tree) AdjustRanges()

AdjustRanges fixes range fields for all Nodes in the Tree. This must be called before Get or DoMatching* is used if fast insertion or deletion has been performed.

func (*Tree) Ceil

func (t *Tree) Ceil(q Interface) (o Interface, err error)

Ceil returns the smallest value equal to or greater than the query q according to q.Start.Compare(), with ties broken by comparison of ID() values.

func (*Tree) Delete

func (t *Tree) Delete(e Interface, fast bool) (err error)

Delete deletes the element e if it exists in the Tree.

func (*Tree) DeleteMax

func (t *Tree) DeleteMax(fast bool)

DeleteMax deletes the right-most interval.

func (*Tree) DeleteMin

func (t *Tree) DeleteMin(fast bool)

DeleteMin deletes the left-most interval.

func (*Tree) Do

func (t *Tree) Do(fn Operation) bool

Do performs fn on all intervals stored in the tree. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.

func (*Tree) DoMatching

func (t *Tree) DoMatching(fn Operation, q Overlapper) bool

DoMatching performs fn on all intervals stored in the tree that match q according to Overlap, with q.Overlap() used to guide tree traversal, so DoMatching() will out perform Do() with a called conditional function if the condition is based on sort order, but can not be reliably used if the condition is independent of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.

func (*Tree) DoMatchingReverse

func (t *Tree) DoMatchingReverse(fn Operation, q Overlapper) bool

DoMatchingReverse performs fn on all intervals stored in the tree that match q according to Overlap, with q.Overlap() used to guide tree traversal, so DoMatching() will out perform Do() with a called conditional function if the condition is based on sort order, but can not be reliably used if the condition is independent of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.

func (*Tree) DoReverse

func (t *Tree) DoReverse(fn Operation) bool

DoReverse performs fn on all intervals stored in the tree, but in reverse of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored intervals' sort relationships, future tree operation behaviors are undefined.

func (*Tree) Floor

func (t *Tree) Floor(q Interface) (o Interface, err error)

Floor returns the largest value equal to or less than the query q according to q.Start.Compare(), with ties broken by comparison of ID() values.

func (*Tree) Get

func (t *Tree) Get(q Overlapper) (o []Interface)

Get returns a slice of Interfaces that overlap q in the Tree according to q.Overlap().

func (*Tree) Insert

func (t *Tree) Insert(e Interface, fast bool) (err error)

Insert inserts the Interface e into the Tree. Insertions may replace existing stored intervals.

func (*Tree) Len

func (t *Tree) Len() int

Len returns the number of intervals stored in the Tree.

func (*Tree) Max

func (t *Tree) Max() Interface

Max returns the right-most interval stored in the tree.

func (*Tree) Min

func (t *Tree) Min() Interface

Min returns the left-most interval stored in the tree.