A skip list container class in Python

Inserts a new child element c into the skip list.

If you created the skip list with allowDups=0 and the new element has the same key as an existing member of the list, this method will raise a KeyError exception.

If duplicates are allowed (the allowDups=1 option to the constructor), and the new element's key duplicates one or more already in the list, the new child will be added in sequence after the other duplicates. This makes the ordering stable; see Section 2.1.3, “Stability”.

Deletes the first or only element whose key is equal to k, and returns the deleted child element (or None if there are no matching elements).

If duplicates are allowed and there are multiple elements equal to e, only the first one will be deleted.

Returns the first or only object whose key equals k. If there are no such objects, this method raises a KeyError exception.

Searches for the first element whose key is equal to or greater than k, and returns an iterator that iterates over all those elements.

If there are any elements in the skip list, this method returns the first element. If the skip list is empty, it raises KeyError.

This special method defines the meaning of the ordinary len() function when applied to a SkipList. It returns the number of child elements in the list.

Returns an iterator object that can be used to iterate over the elements of the skip list. You can have multiple independent iterators pointing at the same skip list, and each will move independently of the others. This allows constructs like:

    for i in s: ...

where s is a SkipList object. Such a loop will set i to each child value from s in turn.

Defines the meaning of the Python “in” and “not in” operators in the usual way for container classes.

If s is a SkipList, the expression k in s returns true if and only if k is equal to at least one member of s. Similarly, the expression k not in s returns true iff k is not equal to any member of s.

Same as .delete(k).

This method defines the usual meaning of s[k], where s is a SkipList. It has the same semantics as s.match[k].

This syntax is useful mainly for skip lists that don't allow duplicates. If you need to retrieve multiple members that all compare equal, use the .find() method.

Read-only; equal to the number of times the list has been searched. Each call to the .match(), .find(), or .delete() method is counted as one search.

Read-only; equal to the number of times two elements have been compared with the cmpFun function (or its default).

Statistically, the ratio of .nCompares to .nSearches should be proportional to the log of the number of elements. For analysis, see Pugh's original article.