Packages

  • package root
    Definition Classes
    root
  • package de
    Definition Classes
    root
  • package sciss
    Definition Classes
    de
  • package lucre
    Definition Classes
    sciss
  • package data
    Definition Classes
    lucre
  • 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

    Definition Classes
    data
  • Branch
  • HeadOrBranch
  • Leaf
  • Map
  • Node
  • Set

object Set

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

Type Members

  1. type Branch[S <: Base[S], A] = HASkipList.Branch[S, A, A]
  2. type Leaf[S <: Base[S], A] = HASkipList.Leaf[S, A, A]
  3. type Node[S <: Base[S], A] = HASkipList.Node[S, A, A]

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def clone(): AnyRef
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @native() @throws(classOf[java.lang.CloneNotSupportedException])
  6. def empty[S <: Base[S], A](minGap: Int = 2, keyObserver: KeyObserver[Set.empty.S.Tx, A] = SkipList.NoKeyObserver)(implicit tx: Set.empty.S.Tx, ord: Ordering[Set.empty.S.Tx, A], keySerializer: Serializer[Set.empty.S.Tx, Set.empty.S.Acc, A]): Set[S, A]

    Creates a new empty skip list.

    Creates a new empty skip list. Type parameter S specifies the STM system to use. Type parameter A specifies the type of the keys stored in the list.

    minGap

    the minimum gap-size used for the skip list. This value must be between 1 and 126 inclusive.

    keyObserver

    an object which observes key promotions and demotions. Use NoKeyObserver (default) if key motions do not need to be monitored. The monitoring allows the use of the skip list for synchronized decimation of related data structures, such as the deterministic skip quadtree.

    tx

    the transaction in which to initialize the structure

    ord

    the ordering of the keys. This is an instance of txn.Ordering to allow for specialized versions and transactional restrictions.

    keySerializer

    the serializer for the elements, in case a persistent STM is used.

  7. def empty[S <: Base[S], A](implicit tx: Set.empty.S.Tx, ord: Ordering[Set.empty.S.Tx, A], keySerializer: Serializer[Set.empty.S.Tx, Set.empty.S.Acc, A]): Set[S, A]

    Creates a new empty skip list with default minimum gap parameter of 2 and no key observer.

    Creates a new empty skip list with default minimum gap parameter of 2 and no key observer. Type parameter S specifies the STM system to use. Type parameter A specifies the type of the keys stored in the list.

    tx

    the transaction in which to initialize the structure

    ord

    the ordering of the keys. This is an instance of txn.Ordering to allow for specialized versions and transactional restrictions.

    keySerializer

    the serializer for the elements, in case a persistent STM is used.

  8. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  9. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  10. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.Throwable])
  11. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  12. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  13. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  14. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  15. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  16. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  17. def read[S <: Base[S], A](in: DataInput, access: Set.read.S.Acc, keyObserver: KeyObserver[Set.read.S.Tx, A] = SkipList.NoKeyObserver)(implicit tx: Set.read.S.Tx, ordering: Ordering[Set.read.S.Tx, A], keySerializer: Serializer[Set.read.S.Tx, Set.read.S.Acc, A]): Set[S, A]
  18. def serializer[S <: Base[S], A](keyObserver: KeyObserver[Set.serializer.S.Tx, A] = SkipList.NoKeyObserver)(implicit ordering: Ordering[Set.serializer.S.Tx, A], keySerializer: Serializer[Set.serializer.S.Tx, Set.serializer.S.Acc, A]): Serializer[Set.serializer.S.Tx, Set.serializer.S.Acc, Set[S, A]]
  19. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  20. def toString(): String
    Definition Classes
    AnyRef → Any
  21. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  22. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  23. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @throws(classOf[java.lang.InterruptedException])

Inherited from AnyRef

Inherited from Any

Ungrouped