Object/Trait

de.sciss.lucre.data

DeterministicSkipOctree

Related Docs: trait DeterministicSkipOctree | package data

Permalink

object DeterministicSkipOctree

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 the geom package, assuming that coordinates are integers, with the maximum root hyper-cube given by a span from 0 to 0x7FFFFFFF (e.g. in Space.IntTwoDim, this is IntSquare( 0x40000000, 0x40000000, 0x40000000 ).

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. DeterministicSkipOctree
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Type Members

  1. sealed trait Branch[S <: Base[S], D <: Space[D], A] extends Child[S, D, A] with NonEmpty[S, D]

    Permalink

  2. sealed trait Child[+S, +D, +A] extends Writable

    Permalink

  3. sealed trait ChildBranch[S <: Base[S], D <: Space[D], A] extends Branch[S, D, A] with NonEmptyChild[S, D, A]

    Permalink

     Utility trait which elements the rightward search findPN.

  4. sealed trait Leaf[S <: Base[S], D <: Space[D], A] extends Child[S, D, A] with LeftNonEmptyChild[S, D, A] with RightNonEmptyChild[S, D, A] with LeafOrEmpty[S, D, A]

    Permalink

  5. sealed trait LeafOrEmpty[+S, +D, +A] extends LeftChild[S, D, A]

    Permalink
    Attributes
    protected

  6. sealed trait Left extends AnyRef

    Permalink

  7. sealed trait LeftBranch[S <: Base[S], D <: Space[D], A] extends Branch[S, D, A] with LeftNonEmpty[S, D]

    Permalink

    A left tree node implementation provides more specialized child nodes of type LeftChild.

    A left tree node implementation provides more specialized child nodes of type LeftChild. It furthermore defines a resolution method findImmediateLeaf which is typically called after arriving here from a findP0 call.

  8. sealed trait LeftChild[+S, +D, +A] extends Left with Child[S, D, A]

    Permalink

  9. sealed trait LeftChildBranch[S <: Base[S], D <: Space[D], A] extends LeftBranch[S, D, A] with ChildBranch[S, D, A] with LeftNonEmptyChild[S, D, A]

    Permalink

  10. sealed trait LeftNonEmpty[S <: Base[S], D <: Space[D]] extends Left with NonEmpty[S, D]

    Permalink

  11. sealed trait LeftNonEmptyChild[S <: Base[S], D <: Space[D], A] extends LeftNonEmpty[S, D] with NonEmptyChild[S, D, A] with LeftChild[S, D, A] with Writable

    Permalink

    A common trait used in pattern matching, comprised of Leaf and LeftChildBranch.

  12. sealed trait LeftTopBranch[S <: Base[S], D <: Space[D], A] extends LeftBranch[S, D, A] with TopBranch[S, D, A] with Disposable[DeterministicSkipOctree.LeftTopBranch.S.Tx]

    Permalink

  13. sealed trait Next[+S, +D, +A] extends Child[S, D, A]

    Permalink

  14. sealed trait NonEmpty[S <: Base[S], D <: Space[D]] extends Identifiable[DeterministicSkipOctree.NonEmpty.S.Id]

    Permalink

    A node is an object that can be stored in a orthant of a branch.

  15. sealed trait NonEmptyChild[S <: Base[S], D <: Space[D], A] extends NonEmpty[S, D] with Child[S, D, A]

    Permalink

    An inner non empty tree element has a mutable parent node.

  16. sealed trait RightBranch[S <: Base[S], D <: Space[D], A] extends Next[S, D, A] with Branch[S, D, A]

    Permalink

    A right tree node implementation provides more specialized child nodes of type RightChild.

    A right tree node implementation provides more specialized child nodes of type RightChild. It furthermore defines the node in Qi-1 via the prev method.

  17. sealed trait RightChild[+S, +D, +A] extends Child[S, D, A]

    Permalink

  18. sealed trait RightChildBranch[S <: Base[S], D <: Space[D], A] extends RightBranch[S, D, A] with ChildBranch[S, D, A] with RightNonEmptyChild[S, D, A]

    Permalink

  19. sealed trait RightNonEmptyChild[S <: Base[S], D <: Space[D], A] extends RightChild[S, D, A] with NonEmptyChild[S, D, A] with Writable

    Permalink

    A common trait used in pattern matching, comprised of Leaf and RightChildBranch.

  20. sealed trait RightTopBranch[S <: Base[S], D <: Space[D], A] extends RightBranch[S, D, A] with TopBranch[S, D, A]

    Permalink

  21. sealed trait TopBranch[S <: Base[S], D <: Space[D], A] extends Branch[S, D, A]

    Permalink

Value Members

  1. final def !=(arg0: Any): Boolean

    Permalink
    Definition Classes
    AnyRef → Any

  2. final def ##(): Int

    Permalink
    Definition Classes
    AnyRef → Any

  3. final def ==(arg0: Any): Boolean

    Permalink
    Definition Classes
    AnyRef → Any

  4. object Empty extends LeftChild[Nothing, Nothing, Nothing] with RightChild[Nothing, Nothing, Nothing] with Next[Nothing, Nothing, Nothing] with LeafOrEmpty[Nothing, Nothing, Nothing] with Product with Serializable

    Permalink

  5. final def asInstanceOf[T0]: T0

    Permalink
    Definition Classes
    Any

  6. def clone(): AnyRef

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

  7. def empty[S <: Base[S], D <: Space[D], A](hyperCube: DeterministicSkipOctree.empty.D.HyperCube, skipGap: Int = 2)(implicit view: (A, DeterministicSkipOctree.empty.S.Tx) ⇒ DeterministicSkipOctree.empty.D.PointLike, tx: DeterministicSkipOctree.empty.S.Tx, space: D, keySerializer: Serializer[DeterministicSkipOctree.empty.S.Tx, DeterministicSkipOctree.empty.S.Acc, A]): DeterministicSkipOctree[S, D, A]

    Permalink

  8. final def eq(arg0: AnyRef): Boolean

    Permalink
    Definition Classes
    AnyRef

  9. def equals(arg0: Any): Boolean

    Permalink
    Definition Classes
    AnyRef → Any

  10. def finalize(): Unit

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )

  11. final def getClass(): Class[_]

    Permalink
    Definition Classes
    AnyRef → Any

  12. def hashCode(): Int

    Permalink
    Definition Classes
    AnyRef → Any

  13. final def isInstanceOf[T0]: Boolean

    Permalink
    Definition Classes
    Any

  14. final def ne(arg0: AnyRef): Boolean

    Permalink
    Definition Classes
    AnyRef

  15. final def notify(): Unit

    Permalink
    Definition Classes
    AnyRef

  16. final def notifyAll(): Unit

    Permalink
    Definition Classes
    AnyRef

  17. def read[S <: Base[S], D <: Space[D], A](in: DataInput, access: DeterministicSkipOctree.read.S.Acc)(implicit tx: DeterministicSkipOctree.read.S.Tx, view: (A, DeterministicSkipOctree.read.S.Tx) ⇒ DeterministicSkipOctree.read.D.PointLike, space: D, keySerializer: Serializer[DeterministicSkipOctree.read.S.Tx, DeterministicSkipOctree.read.S.Acc, A]): DeterministicSkipOctree[S, D, A]

    Permalink

  18. implicit def serializer[S <: Base[S], D <: Space[D], A](implicit view: (A, DeterministicSkipOctree.serializer.S.Tx) ⇒ DeterministicSkipOctree.serializer.D.PointLike, space: D, keySerializer: Serializer[DeterministicSkipOctree.serializer.S.Tx, DeterministicSkipOctree.serializer.S.Acc, A]): Serializer[DeterministicSkipOctree.serializer.S.Tx, DeterministicSkipOctree.serializer.S.Acc, DeterministicSkipOctree[S, D, A]]

    Permalink

  19. final def synchronized[T0](arg0: ⇒ T0): T0

    Permalink
    Definition Classes
    AnyRef

  20. def toString(): String

    Permalink
    Definition Classes
    AnyRef → Any

  21. final def wait(): Unit

    Permalink
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

  22. final def wait(arg0: Long, arg1: Int): Unit

    Permalink
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

  23. final def wait(arg0: Long): Unit

    Permalink
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Inherited from AnyRef

Inherited from Any

Ungrouped