This section is empty.


This section is empty.


This section is empty.


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