## Documentation ¶

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

This section is empty.

### Types ¶

#### type Comparable ¶

```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
}```

Comparable is an interface for trichotomic comparisons.

#### type Int64Comparable ¶

`type Int64Comparable int64`

#### func (Int64Comparable) Compare ¶

`func (v Int64Comparable) Compare(c Comparable) int`

#### type Interval ¶

```type Interval struct {
Begin Comparable
End   Comparable
}```

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

#### 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 ¶

```type IntervalTree struct {
// contains filtered or unexported fields
}```

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".

#### func (*IntervalTree) Contains ¶

`func (ivt *IntervalTree) Contains(iv Interval) bool`

Contains returns true if there is some tree node intersecting the 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) 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.

#### type IntervalValue ¶

```type IntervalValue struct {
Ivl Interval
Val interface{}
}```

#### type IntervalVisitor ¶

`type IntervalVisitor func(n *IntervalValue) bool`

InternalVisitor is used on tree searchs; return false to stop searching.

#### type StringAffineComparable ¶

`type StringAffineComparable string`

StringAffineComparable treats "" as > all other strings

#### 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`