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

  • Field Details

  • Constructor Details

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

    • 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 String toString()
      Overrides:
      toString in class Object
    • delete

      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

      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(String[] arg)