Version: v0.0.0-...-59788d5 Latest Latest

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

Go to latest
Published: Feb 11, 2015 License: Apache-2.0 Imports: 4 Imported by: 0



Package rangetree is designed to store n-dimensional data in an easy-to-query way. Given this package's primary use as representing cartesian data, this information is represented by int64s at n-dimensions. This implementation is not actually a tree but a sparse n-dimensional list. This package also includes two implementations of this sparse list, one mutable (and not threadsafe) and another that is immutable copy-on-write which is threadsafe. The mutable version is obviously faster but will likely have write contention for any consumer that needs a threadsafe rangetree.

TODO: unify both implementations with the same interface.



This section is empty.


This section is empty.


This section is empty.


type Entries

type Entries []Entry

Entries is a typed list of Entry that can be reused if Dispose is called.

func NewEntries

func NewEntries() Entries

NewEntries will return a reused list of entries.

func (*Entries) Dispose

func (entries *Entries) Dispose()

Dispose will free the resources consumed by this list and allow the list to be reused.

type Entry

type Entry interface {
	// ValueAtDimension returns the value of this entry
	// at the specified dimension.
	ValueAtDimension(dimension uint64) int64

Entry defines items that can be added to the rangetree.

type Interval

type Interval interface {
	// LowAtDimension returns an integer representing the lower bound
	// at the requested dimension.
	LowAtDimension(dimension uint64) int64
	// HighAtDimension returns an integer representing the higher bound
	// at the request dimension.
	HighAtDimension(dimension uint64) int64

Interval describes the methods required to query the rangetree.

type NoEntriesError

type NoEntriesError struct{}

NoEntriesError is returned from an operation that requires existing entries when none are found.

func (NoEntriesError) Error

func (nee NoEntriesError) Error() string

type OutOfDimensionError

type OutOfDimensionError struct {
	// contains filtered or unexported fields

OutOfDimensionError is returned when a requested operation doesn't meet dimensional requirements.

func (OutOfDimensionError) Error

func (oode OutOfDimensionError) Error() string

type RangeTree

type RangeTree interface {
	// Add will add the provided entries to the tree.  Any entries that
	// were overwritten will be returned in the order in which they
	// were overwritten.  If a cell's addition does not overwrite, a nil
	// is returned for that cell for its index in the provided cells.
	Add(entries ...Entry) Entries
	// Len returns the number of entries in the tree.
	Len() uint64
	// Delete will remove the provided entries from the tree.
	Delete(entries ...Entry)
	// Query will return a list of entries that fall within
	// the provided interval.
	Query(interval Interval) Entries
	// Apply will call the provided function with each entry that exists
	// within the provided range, in order.  Return false at any time to
	// cancel iteration.  Altering the entry in such a way that its location
	// changes will result in undefined behavior.
	Apply(interval Interval, fn func(Entry) bool)
	// InsertAtDimension will increment items at and above the given index
	// by the number provided.  Provide a negative number to to decrement.
	// Returned are two lists.  The first list is a list of entries that
	// were moved.  The second is a list entries that were deleted.  These
	// lists are exclusive.
	InsertAtDimension(dimension uint64, index, number int64) (Entries, Entries)

RangeTree describes the methods available to the rangetree.

func New

func New(dimensions uint64) RangeTree

New is the constructor to create a new rangetree with the provided number of dimensions.


Path Synopsis
Package skiplist implements an n-dimensional rangetree based on a skip list.
Package skiplist implements an n-dimensional rangetree based on a skip list.

Jump to

Keyboard shortcuts

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