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

    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.



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


                      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.