interval

package
v1.1.9 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Oct 1, 2018 License: Apache-2.0 Imports: 6 Imported by: 0

Documentation

Overview

Package interval provides two implementations for an interval tree. One is based on an augmented Left-Leaning Red Black tree. The other is based on an augmented BTree.

Index

Constants

View Source
const (
	TD234 = iota
	BU23
)

Operation LLRBMode of the underlying LLRB tree.

View Source
const (
	// DefaultBTreeMinimumDegree is the default B-tree minimum degree. Benchmarks
	// show that the interval tree performs best with this minimum degree.
	DefaultBTreeMinimumDegree = 32
)
View Source
const LLRBMode = BU23

LLRBMode .

Variables

View Source
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.

View Source
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.

View Source
var ExclusiveOverlapper = exclusiveOverlapper{}

ExclusiveOverlapper defines overlapping as a pair of ranges that share a segment of the keyspace in the exclusive. "exclusive" means that the start keys are treated as inclusive and the end keys are treated as exclusive.

View Source
var InclusiveOverlapper = inclusiveOverlapper{}

InclusiveOverlapper defines overlapping as a pair of ranges that share a segment of the keyspace in the inclusive way. "inclusive" means that both start and end keys treated as inclusive values.

Functions

func Compare

func Compare(a, b Interface) int

Compare returns a value indicating the sort order relationship between a and b. The comparison is performed lexicographically on (a.Range().Start, a.ID()) and (b.Range().Start, b.ID()) tuples where Range().Start is more significant that ID().

Given c = Compare(a, b):

c == -1  if (a.Range().Start, a.ID()) < (b.Range().Start, b.ID());
c == 0 if (a.Range().Start, a.ID()) == (b.Range().Start, b.ID()); and
c == 1 if (a.Range().Start, a.ID()) > (b.Range().Start, b.ID()).

"c == 0" is equivalent to "Equal(a, b) == true".

func Equal

func Equal(a, b Interface) bool

Equal returns a boolean indicating whethter the given Interfaces are equal to each other. If "Equal(a, b) == true", "a.Range().End == b.Range().End" must hold. Otherwise, the interval tree behavior is undefined. "Equal(a, b) == true" is equivalent to "Compare(a, b) == 0". But the former has measurably better performance than the latter. So Equal should be used when only equality state is needed.

func RangeGroupsOverlap

func RangeGroupsOverlap(rg1, rg2 RangeGroup) bool

RangeGroupsOverlap determines if two RangeGroups contain any overlapping Ranges or if they are fully disjoint. It does so by iterating over the RangeGroups together and comparing subsequent ranges.

Types

type Comparable

type Comparable []byte

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

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 == -1 if a < b;
c == 0 if a == b; and
c == 1 if a > b.

func (Comparable) Equal

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

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 an interval 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 DoMatching function should traverse no further.

type Overlapper

type Overlapper interface {
	// Overlap checks whether two ranges overlap.
	Overlap(Range, Range) bool
}

Overlapper specifies the overlapping relationship.

type Range

type Range struct {
	Start, End Comparable
}

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

func (Range) Equal

func (r Range) Equal(other Range) bool

Equal returns whether the two ranges are equal.

func (Range) String

func (r Range) String() string

String implements the Stringer interface.

type RangeGroup

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
	// Iterator returns an iterator to visit each Range stored in the
	// group, in-order. It is not safe to mutate the RangeGroup while
	// iteration is being performed.
	Iterator() RangeGroupIterator
	// 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

func NewRangeList() RangeGroup

NewRangeList constructs a linked-list backed RangeGroup.

func NewRangeTree

func NewRangeTree() RangeGroup

NewRangeTree constructs an interval tree backed RangeGroup.

type RangeGroupIterator

type RangeGroupIterator interface {
	// Next returns the next Range in the RangeGroup. It returns false
	// if there are no more Ranges.
	Next() (Range, bool)
}

RangeGroupIterator is an iterator that walks in-order over a RangeGroup.

type Tree

type Tree interface {
	// AdjustRanges fixes range fields for all nodes in the tree. This must be
	// called before Get, Do or DoMatching* is used if fast insertion or deletion
	// has been performed.
	AdjustRanges()
	// Len returns the number of intervals stored in the Tree.
	Len() int
	// Get returns a slice of Interfaces that overlap r in the tree. The slice is
	// sorted nondecreasingly by interval start.
	Get(r Range) []Interface
	// GetWithOverlapper returns a slice of Interfaces that overlap r in the tree
	// using the provided overlapper function. The slice is sorted nondecreasingly
	// by interval start.
	GetWithOverlapper(r Range, overlapper Overlapper) []Interface
	// Insert inserts the Interface e into the tree. Insertions may replace an
	// existing Interface which is equal to the Interface e.
	Insert(e Interface, fast bool) error
	// Delete deletes the Interface e if it exists in the tree. The deleted
	// Interface is equal to the Interface e.
	Delete(e Interface, fast bool) error
	// Do performs fn on all intervals stored in the tree. The traversal is done
	// in the nondecreasing order of interval start. A boolean is returned
	// indicating whether the traversal was interrupted by an Operation returning
	// true. If fn alters stored intervals' sort relationships, future tree
	// operation behaviors are undefined.
	Do(fn Operation) bool
	// DoMatching performs fn on all intervals stored in the tree that overlaps r.
	// The traversal is done in the nondecreasing order of interval start. A
	// boolean is returned indicating whether the traversal was interrupted by an
	// Operation returning true. If fn alters stored intervals' sort
	// relationships, future tree operation behaviors are undefined.
	DoMatching(fn Operation, r Range) bool
	// Iterator creates an iterator to iterate over all intervals stored in the
	// tree, in-order.
	Iterator() TreeIterator
}

Tree is an interval tree. For all the functions which have a fast argment, fast being true means a fast operation which does not adjust node ranges. If fast is false, node ranges are adjusted.

func NewTree

func NewTree(overlapper Overlapper) Tree

NewTree creates a new interval tree with the given overlapper function. It uses the augmented Left-Leaning Red Black tree implementation.

type TreeIterator

type TreeIterator interface {
	// Next returns the current interval stored in the interval tree	and moves
	// the iterator to the next interval. The method returns false if no intervals
	// remain in the interval tree.
	Next() (Interface, bool)
}

TreeIterator iterates over all intervals stored in the interval tree, in-order.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL