Package it.unimi.dsi.webgraph.scratch
Class DynamicOrderedList<K>
- java.lang.Object
-
- it.unimi.dsi.webgraph.scratch.DynamicOrderedList<K>
-
- Type Parameters:
K
- the type of the elements contained in this list.
public class DynamicOrderedList<K> extends java.lang.Object
This class implements a simplified one-level version of the data structure described in Bender, Michael A., et al. " Two simplified algorithms for maintaining order in a list." European Symposium on Algorithms. Springer, Berlin, Heidelberg, 2002. All elements (of typeK
) after insertions are dealt with through suitable handles, that are themselves nodes of a doubly-linked list, contain a refence to the actual element and have an additional long tag that serves the purpose of comparison.The total order is initially empty, a new element can be inserted or moved just after a given element, or it can be deleted. At any time one can test in which order two given elements are. Insertions/moves take O(log n) amortized time, whereas deletions and queries take O(1) time.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
DynamicOrderedList.DOLNode<K>
A node of the doubly-linked list underlying this data structure.
-
Field Summary
Fields Modifier and Type Field Description DynamicOrderedList.DOLNode<K>
head
Fictitious element at the beginning of the list.long
size
Number of elements currently in the list.DynamicOrderedList.DOLNode<K>
tail
Fictitious element at the endof the list.
-
Constructor Summary
Constructors Constructor Description DynamicOrderedList()
Creates an empty list with 3/2-overflow threshold.DynamicOrderedList(double overflowThreshold)
Creates an empty list with given overflow threshold.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
assertList()
Asserts that all tags are in order.static <K> int
compare(DynamicOrderedList.DOLNode<K> u, DynamicOrderedList.DOLNode<K> v)
Compares two nodes (through their tags).DynamicOrderedList.DOLNode<K>
delete(DynamicOrderedList.DOLNode<K> node)
Deletes a node.DynamicOrderedList.DOLNode<K>
insertAfter(DynamicOrderedList.DOLNode<K> previous, K y)
Inserts a new node immediately after a given one.static void
main(java.lang.String[] arg)
DynamicOrderedList.DOLNode<K>
moveAfter(DynamicOrderedList.DOLNode<K> node, DynamicOrderedList.DOLNode<K> previous)
Moves a node immediately after a given one.java.lang.String
toString()
-
-
-
Field Detail
-
head
public DynamicOrderedList.DOLNode<K> head
Fictitious element at the beginning of the list.
-
tail
public DynamicOrderedList.DOLNode<K> tail
Fictitious element at the endof the list.
-
size
public long size
Number of elements currently in the list.
-
-
Constructor Detail
-
DynamicOrderedList
public DynamicOrderedList(double overflowThreshold)
Creates an empty list with given overflow threshold. No more than1<lt;k * Math.pow(overflowThreshold, TAG_SIZE-k)
elements can share the samek
-bit prefix.- Parameters:
overflowThreshold
- the overflow threshold of this list: it must be a number between 1 and 2.
-
DynamicOrderedList
public DynamicOrderedList()
Creates an empty list with 3/2-overflow threshold.
-
-
Method Detail
-
compare
public static <K> int compare(DynamicOrderedList.DOLNode<K> u, DynamicOrderedList.DOLNode<K> v)
Compares two nodes (through their tags).- Parameters:
u
- the first node.v
- the second node.- Returns:
- a negative, null, positive value depending on whether
u
comes before, coincides or comes afterv
.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
delete
public DynamicOrderedList.DOLNode<K> delete(DynamicOrderedList.DOLNode<K> node)
Deletes a node. The deleted node is returned.
-
moveAfter
public DynamicOrderedList.DOLNode<K> moveAfter(DynamicOrderedList.DOLNode<K> node, DynamicOrderedList.DOLNode<K> previous)
Moves a node immediately after a given one.
-
insertAfter
public DynamicOrderedList.DOLNode<K> insertAfter(DynamicOrderedList.DOLNode<K> previous, K y)
Inserts a new node immediately after a given one.- Parameters:
previous
- the node immediately after which the new node should be inserted. It cannot betail
.y
- the content of the node to be inserted.- Returns:
- the inserted node.
-
assertList
public boolean assertList()
Asserts that all tags are in order.- Returns:
- true if all tags are in order.
-
main
public static void main(java.lang.String[] arg)
-
-