package data
- Alphabetic
- Public
- Protected
Type Members
- sealed trait DetSkipOctree[T <: Exec[T], P, H, A] extends SkipOctree[T, P, H, A]
- trait HASkipList[T <: Exec[T], A, E] extends SkipList[T, A, E]
- trait SkipList[T <: Exec[T], A, E] extends Mutable[T]
- trait SkipOctree[T <: Exec[T], P, H, A] extends Mutable[T]
A
SkipOctree
is a multi-dimensional data structure that maps coordinates to values.A
SkipOctree
is a multi-dimensional data structure that maps coordinates to values. It extends the interface of Scala's mutableMap
and adds further operations such as range requires and nearest neighbour search. - sealed trait TotalOrder[T <: Exec[T]] extends Mutable[T]
Value Members
- object Ancestor
- object DetSkipOctree
A transactional deterministic skip octree as outlined in the paper by Eppstein et al.
A transactional deterministic skip octree as outlined in the paper by Eppstein et al. It is constructed from a given space (dimensions) and a skip-gap parameter which determines the kind of skip list which is used to govern the level decimation.
The tree is a mutable data structure which supports lookup, insertion and removal in O(log n), as well as efficient range queries and nearest neighbour search.
The current implementation, backed by
impl.SkipOctreeImpl
, uses the types of thegeom
package, assuming that coordinates are integers, with the maximum root hyper-cube given by a span from0
to0x7FFFFFFF
(e.g. inSpace.IntTwoDim
, this isIntSquare( 0x40000000, 0x40000000, 0x40000000 )
. - object HASkipList
A transactional version of the deterministic k-(2k+1) top-down operated skip list as described in T.
A transactional version of the deterministic k-(2k+1) top-down operated skip list as described in T. Papadakis, Skip Lists and Probabilistic Analysis of Algorithms. Ch. 4 (Deterministic Skip Lists), pp. 55--78. Waterloo (CA) 1993
It uses the horizontal array technique with a parameter for k (minimum gap size). It uses a modified top-down removal algorithm that avoids the need for a second pass as in the original algorithm, and is careful about object creations, so that it will be able to persist the data structure without any unnecessary reads or writes to the store.
Three implementation notes: (1) We treat the nodes as immutable at the moment, storing them directly in the S#Val child pointers of their parents. While this currently seems to have a performance advantage (?), we could try to avoid this by using S#Refs for the child pointers, making the nodes become mutable. We could avoid copying the arrays for each insertion or deletion, at the cost of more space, but maybe better performance.
(2) The special treatment of
isRight
kind of sucks. Since now that information is also persisted, we might just have two types of branches and leaves, and avoid passing around this flag.(3) Since there is a bug with the top-down one-pass removal, we might end up removing the creation of instances of virtual branches altogether again when replacing the current algorithm by a two-pass one.
TODO: nodes or at least leaves should be horizontally connected for a faster iterator and fast pair (interval) search
- object SkipList
- object SkipOctree
- object TotalOrder
A transactional data structure to maintain an ordered sequence of elements such that two random elements can be compared in O(1).
A transactional data structure to maintain an ordered sequence of elements such that two random elements can be compared in O(1).
This uses an algorithm from the paper Bender, M. and Cole, R. and Demaine, E. and Farach-Colton, M. and Zito, J., Two simplified algorithms for maintaining order in a list, Algorithms—ESA 2002, pp. 219--223, 2002.
The
relabel
method is based on the Python implementation by David Eppstein, as published at http://www.ics.uci.edu/~eppstein/PADS/OrderedSequence.py however a bug resulting in a relabel size of 1 was fixed.Original note: "Due to rebalancing on the integer tags used to maintain order, the amortized time per insertion in an n-item list is O(log n)."