A skip list container class in Python

This routine builds a list of the predecessors of the cut point for insertion. As Pugh's paper describes, we start searching at the highest-numbered list and proceed down to the level-0 list.

# - - -   S k i p L i s t . _ _ i n s e r t C u t L i s t   - - -

    def __insertCutList ( self, key ):
        """Form the insertion cut list.

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

The first step is to build a list of pointers to self.__heads, one for each possible level.

        #-- 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

Next, we search all the levels currently in use from the top down. We find the cut point at each level, then for the next level we start at the predecessor of that cut point. The routine to find each cut point is Section 4.11, “SkipList.__insertPoint()”.

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

Finally, we maintain the invariant on .nSearches, since every call to this routine counts as a search.

        #-- 3 --
        self.nSearches  =  self.nSearches + 1       # Count as a search
        return result