object
TotalOrder
Value Members
-
final
def
!=(arg0: Any): Boolean
-
final
def
##(): Int
-
final
def
==(arg0: Any): Boolean
-
object
Map
-
object
Set
-
final
def
asInstanceOf[T0]: T0
-
def
clone(): AnyRef
-
final
def
eq(arg0: AnyRef): Boolean
-
def
equals(arg0: Any): Boolean
-
def
finalize(): Unit
-
final
def
getClass(): Class[_]
-
def
hashCode(): Int
-
final
def
isInstanceOf[T0]: Boolean
-
final
def
ne(arg0: AnyRef): Boolean
-
final
def
notify(): Unit
-
final
def
notifyAll(): Unit
-
final
def
synchronized[T0](arg0: ⇒ T0): T0
-
def
toString(): String
-
final
def
wait(): Unit
-
final
def
wait(arg0: Long, arg1: Int): Unit
-
final
def
wait(arg0: Long): Unit
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
relabelmethod 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)."