Object

de.sciss.lucre.data

HASkipList

Related Doc: package data

Permalink

object HASkipList

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

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

Type Members

  1. final class Branch[S <: Sys[S], A, B] extends HeadOrBranch[S, A, B] with Node[S, A, B]

    Permalink
  2. sealed trait HeadOrBranch[S <: Sys[S], A, E] extends AnyRef

    Permalink
  3. sealed trait Leaf[S <: Sys[S], A, E] extends Node[S, A, E]

    Permalink
  4. sealed trait Map[S <: Sys[S], A, B] extends SkipList.Map[S, A, B]

    Permalink
  5. sealed trait Node[S <: Sys[S], A, E] extends AnyRef

    Permalink
  6. sealed trait Set[S <: Sys[S], A] extends SkipList.Set[S, 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 Branch

    Permalink
  5. object Map

    Permalink
  6. object Set

    Permalink
  7. final def asInstanceOf[T0]: T0

    Permalink
    Definition Classes
    Any
  8. def clone(): AnyRef

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  9. def debugFindLevel[S <: Sys[S], A](list: SkipList[S, A, _], key: A)(implicit tx: HASkipList.debugFindLevel.S.Tx): Int

    Permalink
  10. final def eq(arg0: AnyRef): Boolean

    Permalink
    Definition Classes
    AnyRef
  11. def equals(arg0: Any): Boolean

    Permalink
    Definition Classes
    AnyRef → Any
  12. def finalize(): Unit

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  13. final def getClass(): Class[_]

    Permalink
    Definition Classes
    AnyRef → Any
  14. def hashCode(): Int

    Permalink
    Definition Classes
    AnyRef → Any
  15. final def isInstanceOf[T0]: Boolean

    Permalink
    Definition Classes
    Any
  16. final def ne(arg0: AnyRef): Boolean

    Permalink
    Definition Classes
    AnyRef
  17. final def notify(): Unit

    Permalink
    Definition Classes
    AnyRef
  18. final def notifyAll(): Unit

    Permalink
    Definition Classes
    AnyRef
  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