rangetree

Documentation

Overview

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.

Index

• type Entries
  • func NewEntries() Entries
  • func (entries *Entries) Dispose()
• type Entry
• type Interval
• type NoEntriesError
  • func (nee NoEntriesError) Error() string
• type OutOfDimensionError
  • func (oode OutOfDimensionError) Error() string
• type RangeTree
  • func New(dimensions uint64) RangeTree

Types

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 an entry's addition does not overwrite, a nil
	// is returned for that entry's 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.
	// Any entries that were deleted will be returned in the order in
	// which they were deleted.  If an entry does not exist to be deleted,
	// a nil is returned for that entry's index in the provided cells.
	Delete(entries ...Entry) Entries
	// 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.