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

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