adt - ActiveState ActiveGo 1.8

Package adt

import ""

Overview ▾

Package adt implements useful abstract data types.



ivt := &adt.IntervalTree{}

ivt.Insert(adt.NewInt64Interval(1, 3), 123)
ivt.Insert(adt.NewInt64Interval(9, 13), 456)
ivt.Insert(adt.NewInt64Interval(7, 20), 789)

rs := ivt.Stab(adt.NewInt64Point(10))
for _, v := range rs {
    fmt.Printf("Overlapping range: %+v\n", v)


Overlapping range: &{Ivl:{Begin:7 End:20} Val:789}
Overlapping range: &{Ivl:{Begin:9 End:13} Val:456}

Index ▾



Package files

doc.go interval_tree.go

type BytesAffineComparable

BytesAffineComparable treats empty byte arrays as > all other byte arrays

type BytesAffineComparable []byte

func (BytesAffineComparable) Compare

func (b BytesAffineComparable) Compare(c Comparable) int

type Comparable

Comparable is an interface for trichotomic comparisons.

type Comparable interface {
    // Compare gives the result of a 3-way comparison
    // a.Compare(b) = 1 => a > b
    // a.Compare(b) = 0 => a == b
    // a.Compare(b) = -1 => a < b
    Compare(c Comparable) int

type Int64Comparable

type Int64Comparable int64

func (Int64Comparable) Compare

func (v Int64Comparable) Compare(c Comparable) int

type Interval

Interval implements a Comparable interval [begin, end) TODO: support different sorts of intervals: (a,b), [a,b], (a, b]

type Interval struct {
    Begin Comparable
    End   Comparable

func NewBytesAffineInterval

func NewBytesAffineInterval(begin, end []byte) Interval

func NewBytesAffinePoint

func NewBytesAffinePoint(b []byte) Interval

func NewInt64Interval

func NewInt64Interval(a int64, b int64) Interval

func NewInt64Point

func NewInt64Point(a int64) Interval

func NewStringAffineInterval

func NewStringAffineInterval(begin, end string) Interval

func NewStringAffinePoint

func NewStringAffinePoint(s string) Interval

func NewStringInterval

func NewStringInterval(begin, end string) Interval

func NewStringPoint

func NewStringPoint(s string) Interval

func (*Interval) Compare

func (ivl *Interval) Compare(c Comparable) int

Compare on an interval gives == if the interval overlaps.

type IntervalTree

IntervalTree represents a (mostly) textbook implementation of the "Introduction to Algorithms" (Cormen et al, 2nd ed.) chapter 13 red-black tree and chapter 14.3 interval tree with search supporting "stabbing queries".

type IntervalTree struct {
    // contains filtered or unexported fields

func (*IntervalTree) Contains

func (ivt *IntervalTree) Contains(ivl Interval) bool

Contains returns true if the interval tree's keys cover the entire given interval.

func (*IntervalTree) Delete

func (ivt *IntervalTree) Delete(ivl Interval) bool

Delete removes the node with the given interval from the tree, returning true if a node is in fact removed.

func (*IntervalTree) Find

func (ivt *IntervalTree) Find(ivl Interval) (ret *IntervalValue)

Find gets the IntervalValue for the node matching the given interval

func (*IntervalTree) Height

func (ivt *IntervalTree) Height() int

Height is the number of levels in the tree; one node has height 1.

func (*IntervalTree) Insert

func (ivt *IntervalTree) Insert(ivl Interval, val interface{})

Insert adds a node with the given interval into the tree.

func (*IntervalTree) Intersects

func (ivt *IntervalTree) Intersects(iv Interval) bool

Intersects returns true if there is some tree node intersecting the given interval.

func (*IntervalTree) Len

func (ivt *IntervalTree) Len() int

Len gives the number of elements in the tree

func (*IntervalTree) MaxHeight

func (ivt *IntervalTree) MaxHeight() int

MaxHeight is the expected maximum tree height given the number of nodes

func (*IntervalTree) Stab

func (ivt *IntervalTree) Stab(iv Interval) (ivs []*IntervalValue)

Stab returns a slice with all elements in the tree intersecting the interval.

func (*IntervalTree) Visit

func (ivt *IntervalTree) Visit(ivl Interval, ivv IntervalVisitor)

Visit calls a visitor function on every tree node intersecting the given interval. It will visit each interval [x, y) in ascending order sorted on x.

type IntervalValue

type IntervalValue struct {
    Ivl Interval
    Val interface{}

type IntervalVisitor

IntervalVisitor is used on tree searches; return false to stop searching.

type IntervalVisitor func(n *IntervalValue) bool

type StringAffineComparable

StringAffineComparable treats "" as > all other strings

type StringAffineComparable string

func (StringAffineComparable) Compare

func (s StringAffineComparable) Compare(c Comparable) int

type StringComparable

type StringComparable string

func (StringComparable) Compare

func (s StringComparable) Compare(c Comparable) int