cockroach: github.com/abhinavdahiya/cockroach/util/interval Index | Files

package interval

import "github.com/abhinavdahiya/cockroach/util/interval"

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

Index

Package Files

bu23.go interval.go range_group.go

Constants

const (
    TD234 = iota
    BU23
)

Operation mode of the underlying LLRB tree.

const Mode = BU23

Mode .

Variables

var ErrEmptyRange = errors.New("interval: empty range")

ErrEmptyRange is returned if an interval is used where the start value is equal to the end value.

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.

type Comparable Uses

type Comparable []byte

A Comparable is a type that describes the ends of a Range.

func (Comparable) Compare Uses

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.

func (Comparable) Equal Uses

func (c Comparable) Equal(o Comparable) bool

Equal returns a boolean indicating if the given comparables are equal to each other. Note that this has measurably better performance than Compare() == 0, so it should be used when only equality state is needed.

type Interface Uses

type Interface interface {
    Range() Range
    // Returns a unique ID for the element.
    // TODO(nvanbenschoten) Should this be changed to an int64?
    ID() uintptr
}

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

type Node Uses

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

A Node represents a node in a Tree.

type Operation Uses

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 Range Uses

type Range struct {
    Start, End Comparable
}

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

func (Range) Equal Uses

func (r Range) Equal(other Range) bool

Equal returns whether the two ranges are equal.

func (Range) OverlapExclusive Uses

func (r Range) OverlapExclusive(other Range) bool

OverlapExclusive returns whether the two provided ranges overlap. It defines overlapping as a pair of ranges that share a segment of the keyspace, with the start keys treated as inclusive and the end keys treated as exclusive.

func (Range) OverlapInclusive Uses

func (r Range) OverlapInclusive(other Range) bool

OverlapInclusive returns whether the two provided ranges overlap. It defines overlapping as a pair of ranges that share a segment, with both start and end keys treated as inclusive values.

func (Range) String Uses

func (r Range) String() string

String implements the Stringer interface.

type RangeGroup Uses

type RangeGroup interface {
    // Add will attempt to add the provided Range to the RangeGroup,
    // returning whether the addition increased the range of the group
    // or not.
    Add(Range) bool
    // Sub will attempt to remove the provided Range from the RangeGroup,
    // returning whether the subtraction reduced the range of the group
    // or not.
    Sub(Range) bool
    // Clear clears all ranges from the RangeGroup, resetting it to be
    // used again.
    Clear()
    // Overlaps returns whether the provided Range is partially contained
    // within the group of Ranges in the RangeGroup.
    Overlaps(Range) bool
    // Encloses returns whether the provided Range is fully contained
    // within the group of Ranges in the RangeGroup.
    Encloses(Range) bool
    // ForEach calls the provided function with each Range stored in
    // the group. An error is returned indicating whether the callback
    // function saw an error, whereupon the Range iteration will halt
    // (potentially prematurely) and the error will be returned from ForEach
    // itself. If no error is returned from the callback, the method
    // will visit all Ranges in the group before returning a nil error.
    ForEach(func(Range) error) error
    // Len returns the number of Ranges currently within the RangeGroup.
    // This will always be equal to or less than the number of ranges added,
    // as ranges that overlap will merge to produce a single larger range.
    Len() int
    fmt.Stringer
}

RangeGroup represents a set of possibly disjointed Ranges. The interface exposes methods to manipulate the group by adding and subtracting Ranges. All methods requiring a Range will panic if the provided range is inverted or empty.

One use case of the interface is to add ranges to the group and observe whether the addition increases the size of the group or not, indicating whether the new range's interval is redundant, or if it is needed for the full composition of the group. Because the RangeGroup builds as more ranges are added, insertion order of the ranges is critical. For instance, if two identical ranges are added, only the first to be added with Add will return true, as it will be the only one to expand the group.

Another use case of the interface is to add and subtract ranges as needed to the group, allowing the internals of the implementation to coalesce and split ranges when needed to factor the group to its minimum number of disjoint ranges.

func NewRangeList Uses

func NewRangeList() RangeGroup

NewRangeList constructs a linked-list backed RangeGroup.

func NewRangeTree Uses

func NewRangeTree() RangeGroup

NewRangeTree constructs an interval tree backed RangeGroup.

type Tree Uses

type Tree struct {
    Root       *Node                   // root node of the tree.
    Count      int                     // number of elements stored.
    Overlapper func(Range, Range) bool // determines how to define Range overlap.
}

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

func (*Tree) AdjustRanges Uses

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 Uses

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 Uses

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

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

func (*Tree) DeleteMax Uses

func (t *Tree) DeleteMax(fast bool)

DeleteMax deletes the right-most interval.

func (*Tree) DeleteMin Uses

func (t *Tree) DeleteMin(fast bool)

DeleteMin deletes the left-most interval.

func (*Tree) Do Uses

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 Uses

func (t *Tree) DoMatching(fn Operation, r Range) bool

DoMatching performs fn on all intervals stored in the tree that match r according to t.Overlapper, with Overlapper() used to guide tree traversal, so DoMatching() will outperform 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 Uses

func (t *Tree) DoMatchingReverse(fn Operation, r Range) bool

DoMatchingReverse performs fn on all intervals stored in the tree that match r according to t.Overlapper, with Overlapper() used to guide tree traversal, so DoMatching() will outperform 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 Uses

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 Uses

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 Uses

func (t *Tree) Get(r Range) (o []Interface)

Get returns a slice of Interfaces that overlap r in the Tree.

func (*Tree) GetWithOverlapper Uses

func (t *Tree) GetWithOverlapper(r Range, overlapper func(Range, Range) bool) (o []Interface)

GetWithOverlapper returns a slice of Interfaces that overlap r in the Tree using the provided overlapper function.

func (*Tree) Insert Uses

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 Uses

func (t *Tree) Len() int

Len returns the number of intervals stored in the Tree.

func (*Tree) Max Uses

func (t *Tree) Max() Interface

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

func (*Tree) Min Uses

func (t *Tree) Min() Interface

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

Package interval imports 5 packages (graph). Updated 2017-03-13. Refresh now. Tools for package owners. This is a dead-end fork (no commits since the fork).