The insertion of a new child element is depicted above; see Section 3.1, “The skip list data structure”.
# - - - S k i p L i s t . i n s e r t - - - def insert ( self, child ): """Insert a new child element into the skip list."""
To link in a new child element, once we have decided how many levels of links it will use, we must insert it into each of those linked lists. So we define the idea of an insertion cut list: a list of all the predecessors whose forward links must be updated.
The main complication here is that we must implement stability, that is, objects with equal keys must be ordered by insertion time. For example, if we have five objects all with a key value of 5, the first one must be the first inserted, and the last one must be the last inserted.
So, when computing the insertion cut list, we must find
the point in the child sequence after the last child with
the same key. Refer to Section 4.2, “Verification functions”
for the verification functions used here, and also
see Section 4.9, “
The next step is to build the insertion cut list. If there any elements with the same key as the new element, the insertion cut list depends on whether duplicates are allowed or not. We call the point of insertion the cut point, and the cut list is the list of links that cross the cut point.
If duplicates aren't allowed, the cut point is positioned before any duplicate elements, so that when we check for duplicates, we check the new key against the successor of the cut point.
But if duplicates are allowed, due to the stability
constraint, the cut point should be
after any duplicates. See Section 4.8, “
SkipList.insert()” for a discussion of stability.
#-- 2 -- # [ cutList := insertion-cut-list ( key ) ] cutList = self.__insertCutList ( key ) #-- 3 - # [ prevItem := first item from cutList # nextItem := successor at level 0 of first item from # cutList ] prevItem = cutList nextItem = prevItem.links
Now that we have
just after the cut point, we can check for duplicates
when they're not allowed. See Section 4.13, “
#-- 4 -- # [ if (not self.allowDups) and # (nextItem is not self.terminator) and # (cmp(key-of(nextItem.child, key)) == 0 ) -> # raise ValueError # else -> I ] if ( ( not self.allowDups ) and ( nextItem is not self.__terminator ) and ( self.__compareItemKey ( nextItem, key ) == 0 ) ): raise ValueError
Having eliminated the only error case, now we can proceed
with the actual insertion of the new element. See
Section 4.14, “
#-- 5 -- # [ if cutList is insertion-cut-list ( key ) -> # self := self with a new _SkipItem containing (child) # inserted after the items pointed at by the # the first n elements of cutList, where # n is in [1,self.__maxLevels] ] self.__insertItem ( child, cutList )
The next step maintains the invariant on
.__nItems, that is, we keep track of
the number of items in the list.
#-- 6 -- self.__nItems = self.__nItems + 1