A skip list container class in Python

This method returns the "search cut list", a list of the predecessors of a given key at each level of the skip list.

# - - -   S k i p L i s t . _ _ s e a r c h C u t L i s t   - - -

    def __searchCutList ( self, key ):
        """Find predecessors of the item with a given key.

          [ key is in self's key domain ->
              return search-cut-list ( key ) ]
        """

We start by building a list called result containing pointers to the head element, and also point searchItem at the head element.

        #-- 1 --
        # [ result      :=  a list of size self.__maxLevels such that
        #                   each element is self.__heads
        #   searchItem  :=  self.__heads ]
        result      =  [self.__heads] * self.__maxLevels
        searchItem  =  self.__heads

This loop is similar to the one in Section 4.10, “SkipList.__insertCutList()”. It starts at the highest level currently in use and searches forward to find the predecessor at that level. Then it backs up and goes down a level until it reaches level 0. See Section 4.19, “SkipList.__searchPoint()”.

        #-- 2 --
        # [ if search-precedes ( searchItem, key ) ->
        #     result      :=  result modified so that for I in
        #                     [0,self.__nLevels),
        #                     result[I]  := search-point(I, key)
        #     searchItem  :=  <anything> ]
        for i in xrange ( self.__nLevels-1, -1, -1 ):
            #-- 2 body --
            # [ if search-precedes ( searchItem, key ) ->
            #     result[i]   :=  search-point-after(i, key, searchItem)
            #     searchItem  :=  <same as previous line> ]
            searchItem  =  self.__searchPoint ( searchItem, i, key )
            result[i]   =  searchItem

Finally, we increment the total count of searches and return the resulting cut-list.

        #-- 3 --
        self.nSearches  =  self.nSearches + 1
        return result