This method returns the "search cut list", a list of the predecessors of a given key at each level of the skip list.
# - - - S k i p L i s t . _ _ s e a r c h C u t L i s t - - - def __searchCutList ( self, key ): """Find predecessors of the item with a given key. [ key is in self's key domain -> return search-cut-list ( key ) ] """
We start by building a list called
result containing pointers to the
head element, and also point
at the head element.
#-- 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
This loop is similar to the one in Section 4.10, “
SkipList.__insertCutList()”. It starts at the highest
level currently in use and searches forward to find the
predecessor at that level. Then it backs up and goes
down a level until it reaches level 0. See Section 4.19, “
#-- 2 -- # [ if search-precedes ( searchItem, key ) -> # result := result modified so that for I in # [0,self.__nLevels), # result[I] := search-point(I, key) # searchItem := <anything> ] for i in xrange ( self.__nLevels-1, -1, -1 ): #-- 2 body -- # [ if search-precedes ( searchItem, key ) -> # result[i] := search-point-after(i, key, searchItem) # searchItem := <same as previous line> ] searchItem = self.__searchPoint ( searchItem, i, key ) result[i] = searchItem
Finally, we increment the total count of searches and return the resulting cut-list.
#-- 3 -- self.nSearches = self.nSearches + 1 return result