Next / Previous / Contents / Shipman's homepage

4.8. SkipList.insert()

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, “SkipList.__keyOf().
        #-- 1 --
        # [ key  :=  key-of ( child ) ]
        key  =  self.__keyOf ( child )

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[0]
        nextItem  =  prevItem.links[0]

Now that we have nextItem pointing just after the cut point, we can check for duplicates when they're not allowed. See Section 4.13, “SkipList.__compareItemKey().
        #-- 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, “SkipList.__insertItem().
        #-- 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