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 ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Entries ¶
type Entries []Entry
Entries is a typed list of Entry that can be reused if Dispose is called.
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)
// Get returns any entries that exist at the addresses provided by the
// given entries. Entries are returned in the order in which they are
// received. If an entry cannot be found, a nil is returned in its
// place.
Get(entries ...Entry) Entries
// 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.
Source Files
Directories