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

4.22. SkipList.__searchCutItem

The logic here is basically the same as in .__searchCutList(), but the caller only needs to know the level-0 element of the search cut list. So, to avoid a lot of extra storage allocator calls, we don't build the entire search cut list. For more detailed commentary, see Section 4.18, “SkipList.__searchCutList().

pyskip.py
# - - -   S k i p L i s t . _ _ s e a r c h C u t I t e m   - - -

    def __searchCutItem ( self, key ):
        """Find the level-0 predecessor of the given key.

          [ key is in self's key domain ->
              return search-point(0, key).link[0] ]
        """

        #-- 1 --
        # [ searchItem  :=  self.__heads ]
        searchItem  =  self.__heads

        #-- 2 --
        # [ if search-precedes ( searchItem, key ) ->
        #     searchItem  :=  search-point ( 0, key ) ]
        for i in xrange ( self.__nLevels-1, -1, -1 ):
            #-- 2 body --
            # [ if search-precedes ( searchItem, key ) ->
            #     searchItem  :=  search-point-after(i, key, searchItem) ]
            searchItem  =  self.__searchPoint ( searchItem, i, key )

        #-- 3 --
        self.nSearches  =  self.nSearches + 1
        return searchItem