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 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 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

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()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

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 than 1<lt;k * Math.pow(overflowThreshold, TAG_SIZE-k) elements can share the same k-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 after v.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

delete

public DynamicOrderedList.DOLNode<K> delete(DynamicOrderedList.DOLNode<K> node)

Deletes a node. The deleted node is returned.

Parameters:

node - the node to be deleted. It must not be head or tail.

Returns:

the deleted node.

moveAfter

public DynamicOrderedList.DOLNode<K> moveAfter(DynamicOrderedList.DOLNode<K> node,
                                               DynamicOrderedList.DOLNode<K> previous)

Moves a node immediately after a given one.

Parameters:

node - a node of the list. It must not be head or tail.

previous - the node immediately after which node should be moved. It cannot be tail.

Returns:

the node after being moved.

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 be tail.

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)