A skip list container class in Python

The .match() method is used to search for a specific, matching item. If there are multiple matching items, by definition it returns the first. This means we use the search cut list to locate the matching item, rather than the insert cut list. See Section 3.2.2, “The search algorithm”.

# - - -   S k i p L i s t . m a t c h   - - -

    def match ( self, key ): 
        """Return the first or only child with the given key.
        """

If there is a matching item, the level-0 element of the search cut list will precede it; see Section 4.2.9, “search-cut-list”. So we could call the .__searchCutList() method and use element [0] of the returned list.

However, for efficiency reasons, there is a simplified version of .__searchCutList() that doesn't build up the entire cut list, but instead just finds the level-0 predecessor: see Section 4.22, “SkipList.__searchCutItem”.

        #-- 1 --
        # [ searchItem  :=  successor of search-point ( 0, key ) ]
        prevItem    =  self.__searchCutItem(key)
        searchItem  =  prevItem.links[0]

If the user is looking for a child that isn't there, searchItem will point either at the terminator, or at a _SkipItem with a different key. In either of those cases, raise the KeyError exception. Otherwise, return the child item. See Section 4.13, “SkipList.__compareItemKey()”.

        #-- 2 --
        # [ (searchItem is a _SkipItem in self) ->
        #     if (searchItem is not self.__terminator) and
        #     ( cmp ( key-of (searchItem's child), key ) ) == 0 )  ->
        #       return searchItem's child
        #     else ->
        #       raise KeyError ]
        if ( ( searchItem is not self.__terminator ) and
             ( self.__compareItemKey ( searchItem, key ) == 0 ) ):
            return searchItem.child
        else:
            raise KeyError, "Key not found: %s" % key