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 class
A node of the doubly-linked list underlying this data structure. -
Field Summary
FieldsModifier and TypeFieldDescriptionFictitious element at the beginning of the list.long
Number 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 TypeMethodDescriptionboolean
Asserts that all tags are in order.static <K> int
Compares 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 void
moveAfter
(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
u
comes 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
-