A skip list container class in Python

The responsibility of this method is to build a new _SkipItem to hold the newly inserted child, and then link it into one or more of the linked lists.

# - - -   S k i p L i s t . _ _ i n s e r t I t e m   - - -


    def __insertItem ( self, child, cutList ):
        """
          [ cutList is insertion-cut-list(key-of(child)) ->
              self  :=  self with a new _SkipItem, with child=(child),
                        inserted after the items pointed at by the
                        first n levels of cutList, where n is in the
                        range [1,self.__maxLevels] ]
        """

First, using the random number generator, we decide into how many levels we should link the new item. If number of levels picked exceeds the current number of levels, we must adjust the value of self.__nLevels to maintain the invariant that this variable tracks the maximum number of levels actually in use so far. See Section 4.15, “SkipList.__pickLevel()”.

        #-- 1 --
        # [ levels          :=  a random integer in [1,self.__maxLevels]
        #   self.__nLevels  :=  max ( self.__nLevels,
        #                             that random integer ) ]
        levels  =  self.__pickLevel ( )

Then we construct the actual _SkipItem containing the new child. See Section 4.3, “The _SkipItem internal class”.

        #-- 2 --
        # [ newItem  :=  a new _SkipItem with child=(child) and
        #                (levels) forward links all set to None ]
        newItem  =  _SkipItem ( child, levels )

Finally, the .__insertRelink() method takes care of linking the item into the correct number of linked lists; see Section 4.16, “SkipList.__insertRelink()”.

        #-- 3 --
        # [ (cutList is insertion-cut-list(key-of(child))) and
        #   (newItem is a _SkipItem with at least (levels) links) ->
        #     self  :=  self with newItem linked into the first (levels)
        #               lists, just after the element pointed at by the
        #               corresponding element of cutList ]
        self.__insertRelink ( levels, cutList, newItem )