Next / Previous / Contents / TCC Help System / NM Tech homepage

4.11. SkipList.__insertPoint()

This routine searches down one level's linked list until it reaches the point where a new key is to be inserted.

pyskip.py
# - - -   S k i p L i s t . _ _ i n s e r t P o i n t   - - -

    def __insertPoint ( self, searchItem, level, key ):
        """Find the insertion point at a given level.

          [ insertion-precedes(searchItem, key) ->
              return insertion-point-after ( level, key, searchItem) ]
        """

First we find the predecessor and successor of the starting point.

pyskip.py
        #-- 1 --
        # [ prevItem  :=  searchItem
        #   nextItem  :=  successor of searchItem in (level)th list ]
        prevItem  =  searchItem
        nextItem  =  searchItem.links[level]

Next, we move down the nth-level list until we reach the point where the insertion will go.

pyskip.py
        #-- 2 --
        # [ if nextItem is not self.__heads ->
        #     if not insertion-precedes(nextItem, key) -> I
        #     else ->
        #       prevItem  :=  last item E at or after nextItem
        #                     in the (level)th list such that
        #                     insertion-precedes(E, key) is true
        #       nextItem  :=  <anything> ]
        while self.__insertionPrecedes ( nextItem, key ):
            #-- 2 body --
            # [ prevItem  :=  nextItem
            #   nextItem  :=  the succesor of nextItem in the
            #                 (level)th list ]
            prevItem  =  nextItem
            nextItem  =  nextItem.links[level]

Finally, we return the predecessor to that location.

pyskip.py
        #-- 3 --
        return prevItem