A skip list container class in Python

This method implements the algorithm for probabilistically deciding how many levels to use for linking in a new skip list entry. For a discussion of this algorithm, see Section 3.1, “The skip list data structure”.

# - - -   S k i p L i s t . _ _ p i c k L e v e l   - - -

    def __pickLevel ( self ):
        """Into how many levels should an insertion be linked?

          [ self.__nLevels  :=  max ( self.__nLevels,
                a randomly chosen integer in [1,self.__maxLevels] )
            return that same integer ]
        """

Here is what Pugh calls the “dirty hack:” we will never add more than one level to a skip list per insertion. For the details, see Section 3.1, “The skip list data structure”.

        #-- 1 --
        result  =  1
        maxNewLevel  =  min ( self.__nLevels + 1, self.__maxLevels )

Roll the dice, figuratively. The random.random() function returns a real in the interval [0,1), and NEW_LEVEL_PROBABILITY is what Pugh calls p. The process is limited by the previously computed maxNewLevel. For details on the random module, see the Python library reference under “Miscellaneous Services.”

        #-- 2 --
        # [ maxNewLevel >= result  ->
        #     result  :=  a randomly chosen integer in the range
        #                 [result,maxNewLevel] ]
        while ( ( random.random() <= self.NEW_LEVEL_PROBABILITY ) and
                ( result < maxNewLevel ) ):
            result  =  result + 1

Maintain the invariant on self.__nLevels (a running max of the number of levels ever used in the skip list), and return the generated result.

        #-- 3 --
        self.__nLevels  =  max ( self.__nLevels, result )

        #-- 4 --
        return result