A skip list container class in Python

This argument is a function that takes a child argument and returns the corresponding key value. The default value, None, causes SkipList to treat the child elements themselves as keys.

Suppose, for example, that you are building a skip list full of HockeyTeam objects, and each object has an attribute .teamName that contains the team's name as a string. You could write that key function as:

    def teamKey(hockeyTeam):
        return hockeyTeam.teamName

Then to create the skip list you'd say something like:

    skip = SkipList ( keyFun=teamKey )

and the objects would be ordered alphabetically by team name.

To make the ordering case-insensitive, you could write the key function like this, uppercasing the keys for comparison:

    def teamKey(hockeyTeam):
        return hockeyTeam.teamName.upper()

A function that defines the ordering relation on values in the list. The default value, None, means to use the usual Python cmp() function to compare values. You may supply your own function, adhering to the usual convention for this function: when called to compare two elements a and b, cmp(a, b) should return:

If you use allowDups=1, you will be allowed to store multiple objects in the skip list even though they compare equal to each other. If, however, you set allowDups=0, the skip list object will raise an exception if you attempt to insert an element into the list that is equal to an existing element, according to the cmpFun function (or its default).

The purpose of this argument is to tune performance with very large skip lists. With the default value for count equal to a million, the skip list should provide access in logarithmic time for up to about a million elements. If you plan to store more than that, set count to an estimated number of elements.

If the number of elements in the skip list greatly exceeds the count value, it will still function correctly, but the performance may suffer.