This routine searches down one level's linked list until it reaches the point where a new key is to be inserted.
# - - - 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.
#-- 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.
#-- 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.
#-- 3 -- return prevItem