A skip list container class in Python

This routine tests whether a given _SkipItem is before a given key, assuming that we're performing an insertion of a child with that key value.

# - - -   S k i p L i s t . _ _ i n s e r t i o n P r e c e d e s   - - -


    def __insertionPrecedes ( self, skipItem, key ):
        """Does this _SkipItem precede this key for insertion?

          [ skipItem is not self.__heads ->
              return keys-are-ordered ( key-of ( skipItem's child ),
                                        key ) ]
        """

The terminator never precedes anything:

        #-- 1 --
        if skipItem is self.__terminator:
            return 0

Next, we compare the key of the _SkipItem to the new key. See Section 4.13, “SkipList.__compareItemKey()”.

        #-- 2 --
        # [ comparison  :=  cmp ( key-of ( skipItem's child ), key ) ]
        comparison  =  self.__compareItemKey ( skipItem, key )

Whether we want to place the new key before or after duplicates depends on whether the skip list allows duplicates.

        #-- 3 --
        #
        # Note: if duplicates are disallowed, and there is an item that
        # duplicates (target), we want to point before the duplicate
        # item so that the .insert() method will see it and fail.
        # If duplicates are allowed, though, we want to point after
        # all matching items so that the list order will reflect
        # the insertion order.
        #
        # [ if self.allowDups ->
        #     if comparison <= 0  ->  return 1
        #     else ->  return 0
        #   else ->
        #     if comparison < 0 ->  return 1
        #     else ->  return 0 ]
        if self.allowDups:
            return ( comparison <= 0 )
        else:
            return ( comparison < 0 )