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.

Copyright 2014 Workiva, LLC

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

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. Note that all ranges are inclusive.

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.  The values at dimensions are inclusive.
	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.

func New

func New(dimensions uint64) RangeTree

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