Sorted Invariants

Much of the next chapter covers different ways to maintain a sorted invariant. Most of the rest of the of the structures discussed are implemented as either a sorted set or sorted map. This page covers the basic operations and introduces the module’s only probabalistic structure with the skip list.

Sorted Map & Set ADTs

Sorted maps and sets extend the basic map and set ADTs on the previous page, but maintain a comparative ordering of keys and may include any number of the following operations:

• first() / smallest() Returns a reference to the first/smallest member contained in the structure by key or null/None if the structure is empty
• last() / largest() Returns a reference to the last/largest member contained in the structure by key or null/None if the structure is empty
• ceiling(k) Returns the next smallest key that is >= k, or null/None if the structure is either empty or does not contain key k
• floor(k) Returns the next largest key that is <= k, or null/None if the structure is either empty or does not contain key k
• upper(k) Returns the next largest key that is > k, or null/None if the structure is either empty or does not contain key k
• lower(k) Returns the next smallest key that is < k, or null/None if the structure is either empty or does not contain key k
• sub_iter(k1, k2) Returns an iterable range of all entries with keys >= k1 and < k2
• poll_first()/pop_first() Returns (and removes) the smallest key
• poll_last()/pop_last() Returns (and removes) the largest key

Sorted maps are good for search operations where comparative ordering is important, such as the next largest or smallest member. For example, sorted maps using timestamps as keys could easily identify elements before, after, or within a range of timestamps. Sorted structures are also useful in maintaining maxima sets. Take for example a map of entries where the keys represent a cost and values represent some performance metric. Using a sorted map it is possible to write a function like best(cost) that returns the best performance for the value.

Sorted Invariant Representations

There are no hard asymptotic bounds on sorted structures, so their representations and implementations have a wide berth for creative solutioning. For example, it is possible to represent a sorted set with a basic dynamic array structure and periodically run some O(n * log(n)) sorting operation, such as before a lookup or after an insertion. This design would technically count as a sorted structure, but its performance requires expensive sort operations and may not always maintain a sorted structural invariant.

Using a list with some sorting algorithm for add, remove, and resize operations requires O(n) time. The first and last operations require O(1), and get/ceiling/floor/higher/lower operations take O(log n) when using a binary search algorithm. The submap operation requires O(s + log n) where s represents the number of items included. On the other hand, you can implement sorted maps with skip lists that result in O(log n) queries and O((1 + r) log n) adds/updates where r is the number of removed entries.

Rust-Specific Design

Rust provides the RangeBounds trait which makes it possible to replace ceiling(k), floor(k), lower(k), upper(k), and sub_iter() with a single range(R: RangeBounds) operation. Using RangeBounds is likely more performant than manually implementing a predicate with a closure as it allows the collection to use its backing structure to directly identify the lower bound, then iterate until it reaches the upper bound. The bound checks are monomorphized and often zero-cost after inlining.

For example, consider the following range operation ipmlemented with a closure:

impl<T: Ord> SortedSet<T> {
    fn range_where<F>(&self, pred: F) -> impl Iterator<Item = &T>
    where
        F: Fn(&T) -> bool,
    {
        self.data.iter().filter(move |x| pred(x))
    }
}

...

for x in s.range_where(|&x| x >= 3 && x < 8) {
    ...
}

Using the closure necessarily checks every element in the collection, resulting in O(n) running time, even if an an early return exists at the upper bound. Using RangeBounds makes it possible to use the underlying structure’s fast lookup operations to identify elements. Assuming that the structure promises O(log(n)) lookups, properly implementing the RangeBounds trait as a requirement for the structure’s keys provides O(log(n) + k) operations where k is the number of elements returned.

Skip Lists

You can make a sorted table with a regular old index-based list, but it still may require O(n) time for update operations due to shifts, and linked lists dont allow for fast searches. To get around this you can use either a binary search tree (BST) or a skip list. Both BSTs and skip lists provide O(long n) expected (on average) time bounds for search, insert, update, and delete operations. The choice between a skip list and a BST comes down to two trade-offs. BSTs have better cache locality but are difficult to implement for concurrent operations. If you need a safe, concurrent map with

Skip lists are a collection of lists S0 to Sh. List S0 contains all entries in the skip list with keys sorted by some logical methodology as well as two sentinel entries representing keys lower and higher than all possible keys. Visually you can imagine the sentinel entries as -∞ and +∞. The magic of a skip list relies on the fact that each subsequent list contains some random number of elements of the base list S0, also between two sentinel entries -∞ and +∞. Each subsequent list contains roughly half the number of entries as the feeder list, with the specific entries (indexes) chosen at random. If list S0 for map M contains 10 entries (plus two sentinel entries), list S1 might contain 5 entries, S2 might contain 3 entries, S3 might contain 1 entry, and S4 would contain just the sentinel entries.

To visualize skip list operations you can start by layering each list S0 through Sh as sorted lists from left to right with S0 on the bottom under S1 through Sh at the top where h represents the height of the skip list. The result is a kind of grid where each horizontal row is a list Si that represents a level and each column of randomly chosen entries forms a tower.

The heart of the skip list is the skip_search(k) operation which finds the first key that is less than or equal to key k. The skip search operation starts at the “top left” position of the imaginary grid of layered lists S0 up to Sh, which is the sentinel node of Sh represented by key -∞. The operation first checks if key k is <= -∞. If the operation returns null/None, the operation terminates. Otherwise, the operation drops down a level with in the same tower to Sh-1. Next the operation advances to the right-most position p occupied by an entry at position p where key(p) <= k, which is called scanning forward. The operation repreats these steps until it finds the largest key at position p that is <= k. Algorithm:

    skip_search(k):
        p = head of highest list
        while lower_list(p) != null    // Drop to lower list
            p = lower_list(p)
            while k >= key(next(p)) do // Scan forward
                p = next(p)
    return p