A skip list container class in Python

This routine takes care of repairing all the linked lists that must contain the newly created _SkipItem. In general, insertion into a linked lists has this form, where P is the predecessor, S is the successor, and N is the new block:

    N.link = S
    P.link = N

So all we need to do is execute this relinking operation once for each level that contains the new _SkipItem. See also the diagram of this relinking in Section 3.1, “The skip list data structure”.

# - - -   S k i p L i s t . _ _ i n s e r t R e l i n k   - - -

    def __insertRelink ( self, levels, cutList, newItem ):
        """Insert the new _SkipItem into all its linked lists.

          [ (cutList is insertion-cut-list(key-of(child))) and
            (newItem is a _SkipItem with child=(child) and
            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 ]
        """

        #-- 1 --
        for i in xrange(levels):

            #-- 1 loop --
            # [ i is an integer in [0,levels) ->
            #     newItem.links[i]     :=  cutList[i].links[i]
            #     cutList[i].links[i]  :=  newItem ]

            #-- 1.1 --
            # [ i is an integer in [0,levels) ->
            #     prevItem  :=  the item pointed at by cutList[i]
            #     succItem  :=  the (i)th link from the item
            #                   pointed at by cutList[i] ]
            prevItem  =  cutList[i]
            succItem  =  prevItem.links[i]

            #-- 1.2 --
            # [ i is an integer in [0,levels) ->
            #     newItem   :=  newItem with its (i)th link
            #                   pointing to succItem
            #     prevItem  :=  prevItem with its (i)th link
            #                   pointing to newItem ]
            newItem.links[i]   =  succItem
            prevItem.links[i]  =  newItem