The responsibility of this method is to build a new
to hold the newly inserted child, and then link it into
one or more of the linked lists.
# - - - S k i p L i s t . _ _ i n s e r t I t e m - - - def __insertItem ( self, child, cutList ): """ [ cutList is insertion-cut-list(key-of(child)) -> self := self with a new _SkipItem, with child=(child), inserted after the items pointed at by the first n levels of cutList, where n is in the range [1,self.__maxLevels] ] """
First, using the random number generator, we decide into
how many levels we should link the new item. If number
of levels picked exceeds the current number of levels, we
must adjust the value of
self.__nLevels to maintain the
invariant that this variable tracks the maximum number of
levels actually in use so far. See Section 4.15, “
#-- 1 -- # [ levels := a random integer in [1,self.__maxLevels] # self.__nLevels := max ( self.__nLevels, # that random integer ) ] levels = self.__pickLevel ( )
Then we construct the actual
_SkipItem containing the new child.
See Section 4.3, “The
_SkipItem internal class”.
#-- 2 -- # [ newItem := a new _SkipItem with child=(child) and # (levels) forward links all set to None ] newItem = _SkipItem ( child, levels )
method takes care of linking the item into the correct
number of linked lists; see Section 4.16, “
#-- 3 -- # [ (cutList is insertion-cut-list(key-of(child))) and # (newItem is a _SkipItem with at least (levels) links) -> # self := self with newItem linked into the first (levels) # lists, just after the element pointed at by the # corresponding element of cutList ] self.__insertRelink ( levels, cutList, newItem )