rtree

type ArithmeticError ¶

type ArithmeticError struct{ Message string }

ArithmeticError is Java's ArithmeticException.

func (e *ArithmeticError) Error() string

type ChildSlot ¶

type ChildSlot struct {
	SmallestHV  *big.Int
	SmallestKey tuple.Tuple
	LargestHV   *big.Int
	LargestKey  tuple.Tuple
	ChildID     []byte
	ChildMBR    MBR
}

ChildSlot is an intermediate node slot referencing a child node.

func (s ChildSlot) GetMBR() MBR

type IndexOutOfBoundsError ¶

type IndexOutOfBoundsError struct{ Index, Length int }

IndexOutOfBoundsError is Java's IndexOutOfBoundsException.

func (e *IndexOutOfBoundsError) Error() string

type ItemSlot ¶

type ItemSlot struct {
	HilbertValue *big.Int
	Point        Point
	KeySuffix    tuple.Tuple
	Value        tuple.Tuple
}

ItemSlot is a leaf node slot containing a data item.

func (s ItemSlot) GetMBR() MBR

func (s ItemSlot) ItemKey() tuple.Tuple

type MBR ¶

type MBR struct {
	Low  []int64
	High []int64
}

MBR is a minimum bounding rectangle for N dimensions. Stored as [low0, low1, ..., lowN-1, high0, high1, ..., highN-1].

func MBRFromPoint(p Point) MBR

func MBRFromTuple(t tuple.Tuple, numDimensions int) (MBR, error)

func (m MBR) ContainsPoint(p Point) bool

func (m MBR) NumDimensions() int

func (m MBR) Overlaps(other MBR) bool

func (m MBR) Union(other MBR) MBR

type NegativeArraySizeError ¶

type NegativeArraySizeError struct{ Size int }

NegativeArraySizeError is Java's NegativeArraySizeException.

func (e *NegativeArraySizeError) Error() string

type NodeKind ¶

type NodeKind byte

NodeKind identifies a node as leaf or intermediate.

const (
	NodeKindLeaf         NodeKind = 0x00
	NodeKindIntermediate NodeKind = 0x01
)

type NullPointerError ¶

type NullPointerError struct{}

NullPointerError is Java's NullPointerException, from Objects.requireNonNull with no message.

func (*NullPointerError) Error() string

type Point ¶

type Point struct {
	Coordinates tuple.Tuple
}

Point represents an N-dimensional point with int64 coordinates. Null coordinates are represented as nil in the tuple.

func (p Point) Coordinate(dim int) int64

func (p Point) NumDimensions() int

type RTree ¶

type RTree struct {
	// contains filtered or unexported fields
}

RTree is a Hilbert R-tree backed by FDB. Matches Java's com.apple.foundationdb.async.rtree.RTree.

func NewRTree(storage *StorageAdapter, config RTreeConfig) (*RTree, error)

func (rt *RTree) Clear(tx fdb.WritableTransaction) error

func (rt *RTree) Delete(tx fdb.WritableTransaction, point Point, keySuffix tuple.Tuple) error

func (rt *RTree) InsertOrUpdate(tx fdb.WritableTransaction, point Point, keySuffix tuple.Tuple, value tuple.Tuple) error

func (rt *RTree) Scan(tx fdb.ReadTransaction, lastHV *big.Int, lastKey tuple.Tuple, mbrPredicate func(MBR) bool) ([]ItemSlot, error)

func (rt *RTree) ScanIterator(tx fdb.ReadTransaction, lastHV *big.Int, lastKey tuple.Tuple, mbrPredicate func(MBR) bool) *RTreeIterator

type RTreeConfig ¶

type RTreeConfig struct {
	MinM               int          // Min slots per non-root node (default 16)
	MaxM               int          // Max slots per node (default 32)
	SplitS             int          // Siblings involved in split/fuse (default 2)
	Storage            RTreeStorage // Node layout (default BY_NODE)
	StoreHilbertValues bool         // Store HV in leaf slots (default true)
	UseNodeSlotIndex   bool         // Maintain the node slot index (default false)
	NumDimensions      int          // Number of spatial dimensions
}

RTreeConfig configures the R-tree behavior. Matches Java's RTree.Config.

func DefaultRTreeConfig(numDimensions int) RTreeConfig

type RTreeIterator ¶

type RTreeIterator struct {
	// contains filtered or unexported fields
}

RTreeIterator lazily walks the R-tree depth-first in Hilbert order, fetching one leaf node at a time from FDB.

func (it *RTreeIterator) Next() (ItemSlot, bool, error)

type RTreeStorage ¶

type RTreeStorage string

RTreeStorage is Java's RTree.Storage: how a node's slots are laid out.

const (
	// RTreeStorageByNode stores a node as one key/value pair, its slots a
	// nested tuple in the value (Java's ByNodeStorageAdapter). The default.
	RTreeStorageByNode RTreeStorage = "BY_NODE"
	// RTreeStorageBySlot stores each slot of a node as its own key/value pair
	// under the node's key (Java's BySlotStorageAdapter).
	RTreeStorageBySlot RTreeStorage = "BY_SLOT"
)

type StorageAdapter ¶

type StorageAdapter struct {
	// contains filtered or unexported fields
}

StorageAdapter serializes R-tree nodes in FDB in the layout the index's StorageAdapter option names (RTreeConfig.Storage):

• BY_NODE (Java's ByNodeStorageAdapter): each node is one key-value pair, subspace.pack(nodeId) → tuple(nodeKind, slotList), slotList a nested tuple holding each slot as a sub-tuple (its key items, then its value items).
• BY_SLOT (Java's BySlotStorageAdapter): each slot is its own pair under the node, subspace.pack(nodeId, nodeKind, slotKey...) → tuple(slotValue...).

With the rtreeUseNodeSlotIndex option it also maintains Java's node slot index (NodeSlotIndexAdapter): an empty-valued key (level, largestHilbertValue, largestKey items..., childId) in the index's secondary subspace for every child slot of every intermediate node, level being the child's (a leaf is level 0). The index is a function of the tree alone, so Go maintains it as the difference the operation made to the intermediate nodes it touched (flushNodeSlotIndex) rather than per slot change as Java's change sets do; the stored entries are the same.

func NewStorageAdapter(ss subspace.Subspace, config RTreeConfig) *StorageAdapter

func (s *StorageAdapter) WithEnv(env *dst.Env) *StorageAdapter

func (s *StorageAdapter) WithNodeSlotIndex(sub subspace.Subspace) *StorageAdapter

type VerifyError ¶

type VerifyError struct{}

VerifyError is Guava's VerifyException from one of RTree's Verify.verify checks, which carry no message.

func (*VerifyError) Error() string