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.
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 type
K) 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 ClassesModifier and TypeClassDescriptionstatic classA node of the doubly-linked list underlying this data structure. -
Field Summary
FieldsModifier and TypeFieldDescriptionFictitious element at the beginning of the list.longNumber of elements currently in the list.Fictitious element at the endof the list. -
Constructor Summary
ConstructorsConstructorDescriptionCreates an empty list with 3/2-overflow threshold.DynamicOrderedList(double overflowThreshold) Creates an empty list with given overflow threshold. -
Method Summary
Modifier and TypeMethodDescriptionbooleanAsserts that all tags are in order.static <K> intCompares two nodes (through their tags).delete(DynamicOrderedList.DOLNode<K> node) Deletes a node.insertAfter(DynamicOrderedList.DOLNode<K> previous, K y) Inserts a new node immediately after a given one.static voidmoveAfter(DynamicOrderedList.DOLNode<K> node, DynamicOrderedList.DOLNode<K> previous) Moves a node immediately after a given one.toString()
-
Field Details
-
head
Fictitious element at the beginning of the list. -
tail
Fictitious element at the endof the list. -
size
public long sizeNumber of elements currently in the list.
-
-
Constructor Details
-
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 Details
-
compare
Compares two nodes (through their tags).- Parameters:
u- the first node.v- the second node.- Returns:
- a negative, null, positive value depending on whether
ucomes before, coincides or comes afterv.
-
toString
-
delete
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
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
-