This routine builds a list of the predecessors of the cut point for insertion. As Pugh's paper describes, we start searching at the highest-numbered list and proceed down to the level-0 list.
# - - - S k i p L i s t . _ _ i n s e r t C u t L i s t - - - def __insertCutList ( self, key ): """Form the insertion cut list. [ key is in self's key domain -> return insertion-cut-list(key) ] """
The first step is to build a list of pointers to
self.__heads, one for each
#-- 1 -- # [ result := a list of size self.__maxLevels such that # each element is self.__heads # searchItem := self.__heads ] result = [self.__heads] * self.__maxLevels searchItem = self.__heads
Next, we search all the levels currently in use from the
top down. We find the cut point at each level, then for
the next level we start at the predecessor of that cut
point. The routine to find each cut point is Section 4.11, “
#-- 2 -- # [ if insertion-precedes ( searchItem, key ) -> # result := result modified so that for I in # [0,self.nLevels), result[I] is # insertion-point(I, key) # searchItem := <anything> ] for level in xrange ( self.__nLevels - 1, -1, -1 ): #-- 2 body -- # [ if insertion-precedes(searchItem, key) -> # searchItem := insertion-point-after(level, # key, searchItem) # result[level] := <same as previous line> ] searchItem = self.__insertPoint ( searchItem, level, key ) result[level] = searchItem
Finally, we maintain the invariant on
.nSearches, since every call to
this routine counts as a search.
#-- 3 -- self.nSearches = self.nSearches + 1 # Count as a search return result