"""skiplist.py: A container class for ordered sets in Python. Written by John W. Shipman (john@nmt.edu), New Mexico Tech Computer Center, Socorro, NM 87801, in March 1997. Freely available under the terms of the GNU General Public License. This class orders a set of arbitrary objects using their cmp() relation. Some definitions: * The CHILD DOMAIN refers to the type of the objects stored in the list. * The KEY DOMAIN is the type of objects that are to compared with the cmp() function. This may be an object derived from the child object, or the child object itself, if the user prefers. This object supports allows both random search and sequential access. It should give O(log(n)) performance on searches and is stable under arbitrary insertion and deletion. The caller may specify whether duplicate keys are allowed. A SkipList object contains an object called a CURSOR which allows sequential access. It may be undefined. It is described in the intended functions as self._cursor, but the caller ought not to refer to it---that would be a violation of encapsulation. This module was developed using the Cleanroom software development methodology. A description of the author's method and conventions are available at: http://www.nmt.edu/~shipman/soft/clean/ For the theory behind the ``skip list'' data structure used in this implementation, see: Pugh, William. Skip lists: a probabilistic alternative to balanced trees. In: Communications of the ACM, June 1990, 33(6)668-676. """ #================================================================ # Exported methods and variables #---------------------------------------------------------------- # SkipList ( keyFunction, allowDups, maxLevels ) # [ if keyFunction is either None or a method with calling # sequence: # keyFunction(v) # and intended function: # [ if v is an object in the child domain -> # return the key of v, in the key domain # ] # and allowDups is true iff duplicates are allowed # and maxLevels is None or a positive integer -> # return a new SkipList object with the specified # properties and no contained objects # ] #-- # .insert ( child ) # [ if child is an object in child-domain ( self ) -> # if (self does not allow duplicates) and # (there is a child object X in self such that # cmp ( key-of(child), key-of(X) ) = 0) -> # raise ValueError # else -> # self := self with child inserted in order, # following all other equal keys if any # ] #-- # .match ( key ) # [ if key is an object in key-domain ( self ) -> # if there are one or more objects that were inserted # in the order X0, X1, ... and for which # cmp ( Xi, key ) == 0 -> # self._cursor := at X0 in this sequence # return X0 # else -> # self._cursor := None # raise ValueError # ] #-- # .find ( key ) # [ if key is an object in key-domain ( self ) -> # if there are no objects X in self for which # cmp ( key-of ( X ), key ) >= 0 -> # self._cursor := None # raise ValueError # else -> # self._cursor := at the first X such that # cmp ( key-of ( X ), key ) >= 0 # return that X # ] #-- # .next ( ) # [ if not self._cursor -> # raise IndexError # else if self._cursor is the last object -> # self._cursor := None # return None # else -> # self._cursor := the object after self._cursor # return the child from that object # ] #-- # .first ( ) # [ if self is empty -> # self._cursor := None # return None # else -> # self._cursor := the first _SkipItem in self # return the child from the first _SkipItem in self # ] #-- # .delete ( key ) # [ if key is an object in key-domain ( self ) -> # if there are one or more objects that were inserted # in the order X0, X1, ... and for which # cmp ( Xi, key ) == 0 and self._cursor is X0 -> # self._cursor := None # self := self with X0 deleted # return X0 # else if there are one or more objects that were inserted # in the order X0, X1, ... and for which # cmp ( Xi, key ) == 0 and self._cursor is not X0 -> # self := self with X0 deleted # return X0 # else -> # return None # ] #-- # .nItems # [ returns the number of contained objects # ] #-- # .nSearches # [ returns the number of searches carried out on this object; # does not include sequential access via the .next() method # ] #-- # .nCompares # [ returns the number of times we have called cmp() to compare # two keys # ] #-- # - - - Definitions - - - #---------------------------------------------------------------- # child-domain ( self ) == self's child domain #---------------------------------------------------------------- # children-are-ordered ( x, y ) == # if self.allowDups -> # cmp ( key-of ( x ), key-of ( y ) ) <= 0 # else -> # cmp ( key-of ( x ), key-of ( y ) ) < 0 #-- # Similar to the keys-are-ordered predicate, but operates on # child objects. #---------------------------------------------------------------- # insertion-cut-list ( key ) == # a list L of size self.maxLevels, such that each element # L[i] equals insertion-point ( i, key ) #-- # An ``insertion cut list'' is a list of the _SkipItem objects # that must be updated when a new elements is inserted. Element # [i] of the cut list points to the element whose forward # pointer has to be repaired in the (i)th list. #---------------------------------------------------------------- # insertion-point ( level, key ) == # the last element E in nth-list ( self.heads, level ) such # that insertion-precedes ( E, key ) is true #-- # This describes the predecessor _SkipItem whose forward link # must be updated when a new item with key (key) is inserted. #---------------------------------------------------------------- # insertion-point-after ( level, key, searchItem ) == # the last element E in nth-list(searchItem,level) such that # insertion-precedes(E, key) is true #-- # Just like insertion-point(), except that it starts at an # arbitrary _SkipItem instead of self.heads. #---------------------------------------------------------------- # insertion-precedes ( skipItem, key ) == # if skipItem is self.terminator -> F # else if skipItem is self.heads -> T # else -> # keys-are-ordered ( key-of ( skipItem's child ), key ) #-- # This predicate is true when (skipItem) should be before # an item with key (key) in the level-0 list. #---------------------------------------------------------------- # key-domain ( self ) == # if not self.keyFunction -> self's child domain # else -> apply ( self.keyFunction, self's child domain ) #-- # That is, if the user specifies that the key domain and the # child domain are not the same, then we apply the user's # keyFunction() to a child object to obtain its keys. #---------------------------------------------------------------- # key-of ( child ) == # if not self.keyFunction -> # child # else -> # self.keyFunction ( child ) #---------------------------------------------------------------- # keys-are-ordered ( x, y ) == # if self.allowDups -> # cmp ( x, y ) <= 0 # else -> # cmp ( x, y ) < 0 #-- # This is the ordering relation used in the key domain. # - If we don't allow duplicates, then each key must be # strictly less than its successor. # - If we allow duplicates, then two successive keys can # be equal. #---------------------------------------------------------------- # nth-list ( root, n ) == # the linked list of _SkipItem objects rooted at (root) and # using _SkipItem.link() as the next-item method #-- # This define is used to describe positions in the linked list # of objects at one level of the structure. In particular, # nth-list ( self.head, n ) # describes the entire skip list at level (n). #---------------------------------------------------------------- # search-cut-list ( key ) == # a list L of size self.maxLevels such that # L[i] := search-point ( i, key ) #-- # Like insert-cut-list(), but used for .delete() and .find() # operations. #---------------------------------------------------------------- # search-point ( level, key ) == # the last _SkipItem E in nth-list(self.heads, level) such that # search-precedes(E, key) is true #-- # The predecessor whose forward link must be updated when # the item with key (key) is deleted. Also used in # .find(). #---------------------------------------------------------------- # search-point-after ( level, key, searchItem ) == # the last element E in nth-list(searchItem, level) such that # search-precedes(E, key) is true #-- # Like search-point except that the search starts at some # given item rather than at self.heads. #---------------------------------------------------------------- # search-precedes ( skipItem, key ) == # if skip-compare ( skipitem, key ) < 0 -> true # else -> false #-- # A predicate, true when the child in skipItem is before the # key (key). #---------------------------------------------------------------- # skip-compare ( skipItem, key ) == # if skipItem is self.terminator -> 1 # else -> cmp ( key-of ( skipItem's child ), key ) #-- # Like cmp(), but we want to avoid trying to extract a key # from self.terminator, because it doesn't have one. If # skipItem is the terminator, we return 1 because the terminator # goes after all other elements. #---------------------------------------------------------------- # - - - State and invariants - - - #-- # .keyFunction: Key-extractor function. # INV: As specified in the constructor's `keyFunction' argument, # defaulting to None. #-- # .allowDups: Duplicates-allowed flag. # INV: As specified in the constructor's `allowDups' argument, # defaulting to ALLOW_DUPS_DEFAULT. #-- # .maxLevels: Maximum number of levels in the skip list. # INV: As specified in the constructor's `maxLevels' argument, # defaulting to MAX_LEVELS_DEFAULT. #-- # .nLevels: Current number of levels in the skip list. # INV: 0 <= self.nLevels < self.maxLevels #-- # .heads: List head pointers. # INV: heads[0] is the head of a linked list of _SkipItem objects, # terminated by a link to self.terminator, and whose members contain # all the child objects currently in the list, such that for any two # adjacent objects (Xi, Xj), children-are-ordered ( Xi, Xj ) is true. # # INV: For i in [1,self.maxLevels), the list rooted in heads[i] # is a linked list of _SkipItem objects, terminated by a link to # self.terminator, and containing a subset of the linked list in # heads[i-1] in the same order. #-- # .terminator: List head terminator element. # INV: self.terminator is a _SkipItem object with self.maxLevels # forward links all set to None. #-- # .nItems: Number of contained objects # INV: self.nItems is an integer equal to the number of objects # contained in self. #-- # .nSearches: Number of searches # INV: self.nSearches is an integer equal to the number of calls # to methods requiring a random search in the list. #-- # .nCompares: Number of compares # INV: self.nCompares is an integer equal to the number of times # we have called cmp() to compare two keys. #-- # ._cursor: Current position for sequential access. # INV: if the cursor position is undefined -> None # else -> # points to the _SkipItem containing the child last returned # by a call to .match(), .find(), .first(), or .next(), but # never points to self.terminator #-- import whrandom # whrandom.random() is our random number generator class SkipList: """Container class for ordered sets. """ #-- # Manifest constants #-- ALLOW_DUPS_DEFAULT = 0 # Default value of allowDups MAX_LEVELS_DEFAULT = 10 # Default value of maxLevels NEW_LEVEL_PROBABILITY = 0.25 # The `p' of Pugh's article # - - - S k i p L i s t - - - #-- Verified 1997-4-4, Stavely def __init__ ( self, keyFunction = None, allowDups = ALLOW_DUPS_DEFAULT, maxLevels = MAX_LEVELS_DEFAULT ): #-- 1 -- self.keyFunction = keyFunction self.allowDups = allowDups self.maxLevels = maxLevels self.nLevels = 0 self.nItems = 0 self.nSearches = 0 self.nCompares = 0 self._cursor = None #-- 2 -- #-[ self.terminator := a new _SkipItem with child=None and # nLevels=self.maxLevels and # all links set to None #-] self.terminator = _SkipItem ( child = None, nLevels = self.maxLevels ) #-- 3 -- #-[ self.heads := a new _SkipItem with child=None and # nLevels=self.maxLevels and # all links set to self.terminator #-] self.heads = _SkipItem ( child = None, nLevels = self.maxLevels ) for i in xrange ( self.maxLevels ): self.heads.setLink ( i, self.terminator ) # - - - . i n s e r t - - - #-- Verified 1997-4-4, Stavely def insert ( self, child ): #-- 1 -- #-[ key := key-of ( child ) #-] key = self._keyOf ( child ) #-- 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.link(0) #-- 4 -- #-[ if (not self.allowDups) and # (nextItem is not self.terminator) and # (cmp(key-of(prevItem.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 #-- 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 ) #-- 6 -- self.nItems = self.nItems + 1 # - - - . _ k e y O f - - - # [ if child is in child-domain ( self ) -> # return key-of ( child ) # ] def _keyOf ( self, child ): if self.keyFunction: return self.keyFunction ( child ) else: return child # - - - . _ i n s e r t C u t L i s t - - - #-- Verified, 1997-4-4, Stavely # [ if key is in key-domain(self) -> # return insertion-cut-list(key) # ] def _insertCutList ( self, key ): #-- 1 -- #-[ result := a list of size self.maxLevels such that # each element is self.heads # searchItem := self.heads #-] result = [self.heads] * self.maxLevels searchItem = self.heads #-- 2 -- #-[ if insertion-precedes ( searchItem, key ) -> # result := result modified so that for I in # [0,self.nLevels), result[I] is # insertion-point(I, key) # searchItem := #-] for level in xrange ( self.nLevels - 1, -1, -1 ): #-- 2 body -- #-[ if insertion-precedes(searchItem, key) -> # searchItem := insertion-point-after(level, # key, searchItem) # result[level] := #-] searchItem = self._insertPoint ( searchItem, level, key ) result[level] = searchItem #-- 3 -- self.nSearches = self.nSearches + 1 # Count as a search return result # - - - _ i n s e r t P o i n t - - - #-- Verified, 1997-4-4, Stavely # [ if insertion-precedes(searchItem, key) -> # return insertion-point-after ( level, key, searchItem) # ] def _insertPoint ( self, searchItem, level, key ): #-- 1 -- #-[ prevItem := searchItem # nextItem := successor of searchItem in (level)th list #-] prevItem = searchItem nextItem = searchItem.link(level) #-- 2 -- #-[ if nextItem is not self.heads -> # if not insertion-precedes(nextItem, key) -> I # else -> # prevItem := last item E at or after nextItem # in the (level)th list such that # insertion-precedes(E, key) is true # nextItem := #-] while self._insertionPrecedes ( nextItem, key ): #-- 2 body -- #-[ prevItem := nextItem # nextItem := the succesor of nextItem in the # (level)th list #-] prevItem = nextItem nextItem = nextItem.link(level) #-- 3 -- return prevItem # - - - _ i n s e r t i o n P r e c e d e s - - - #-- Verified, 1997-4-4, Stavely # [ if skipItem is not self.heads -> # return keys-are-ordered ( key-of ( skipItem's child ), key ) # ] def _insertionPrecedes ( self, skipItem, key ): #-- 1 -- if skipItem is self.terminator: return 0 #-- 2 -- #-[ comparison := cmp ( key-of ( skipItem's child ), key ) #-] comparison = self._compareItemKey ( skipItem, key ) #-- 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 ) # - - - _ c o m p a r e I t e m K e y - - - #-- Verified, 1997-4-4, Stavely # [ return cmp ( key-of ( skipItem's child ), keyB ) # ] def _compareItemKey ( self, skipItem, keyB ): #-- 1 -- #-[ keyA := key-of ( skipItem's child ) #-] keyA = self._keyOf ( skipItem.child() ) #-- 2 -- self.nCompares = self.nCompares + 1 return cmp ( keyA, keyB ) # - - - _ i n s e r t I t e m - - - #-- Verified, 1997-4-4, Stavely # [ if 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] # ] def _insertItem ( self, child, cutList ): #-- 1 -- #-[ levels := a random integer in [1,self.maxLevels] # self.nLevels := max ( self.nLevels, that random integer ) #-] levels = self._pickLevel ( ) #-- 2 -- #-[ newItem := a new _SkipItem with child=(child) and # (levels) forward links all set to None #-] newItem = _SkipItem ( child, levels ) #-- 3 -- #-[ if (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 ) # - - - _ p i c k L e v e l - - - #-- Verified, 1997-4-4, Stavely # [ let L be a randomly chosen integer in [1,self.maxLevels] in: # self.nLevels := max ( self.nLevels, L ) # return L # ] def _pickLevel ( self ): #-- # Note: This routine implements what the inventor of skip lists # calls the ``dirty hack:'' We will never add more than one # level to a skip list per insertion. This is a Good Thing, in # my opinion, because it avoids the case where a fluke of random # number generation can suddenly increase the number of levels # in the list by a large amount. #-- #-- 1 -- result = 1 maxNewLevel = min ( self.nLevels + 1, self.maxLevels ) #-- 2 -- # # This is the probabilistic part of the algorithm. We # want to select a number of levels L for the new element # in such a way that higher levels are less and less likely. # The NEW_LEVEL_PROBABILITY is a probability P between 0 and 1 # so that there is a (1-P) chance that L will be 1, # a (1-P^2) chance that L will be 2, and so forth. For # example, for P==0.25, 1/4 of blocks will be level 2, # 1/16 will be level 3, and so forth. The # whrand.random() method returns a real in [0,1). # #-[ if maxNewLevel >= result -> # result := a randomly chosen integer in [result,maxNewLevel] #-] while ( whrandom.random() <= self.NEW_LEVEL_PROBABILITY ) and \ ( result < maxNewLevel ): result = result + 1 #-- 3 -- self.nLevels = max ( self.nLevels, result ) #-- 4 -- return result # - - - _ i n s e r t R e l i n k - - - #-- Verified, 1997-4-4, Stavely # [ if (cutList is insertion-cut-list(key-of(child))) and # (newItem is a _SkipItem with child=(child) and # 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 # ] def _insertRelink ( self, levels, cutList, newItem ): #-- 1 -- for i in xrange(levels): #-- 1 loop -- #-[ if i is an integer in [0,levels) -> # let P be the item pointed at by cutList[i] in: # newItem := newItem with its (i)th link # pointing where the (i)th link of # item P points # P := P with its (i)th link pointing # at newItem #-] #-- 1.1 -- #-[ if i is an integer in [0,levels) -> # prevItem := the item pointed at by cutList[i] # succItem := the (i)th link from the item # pointed at by cutList[i] #-] prevItem = cutList[i] succItem = prevItem.link(i) #-- 1.2 -- #-[ if i is an integer in [0,levels) -> # newItem := newItem with its (i)th link # pointing to succItem # prevItem := prevItem with its (i)th link # pointing to newItem #-] newItem.setLink ( i, succItem ) prevItem.setLink ( i, newItem ) # - - - d e l e t e - - - #-- Verified, 1997-4-4, Stavely def delete ( self, key ): #-- 1 -- #-[ cutList := search-cut-list ( key ) # prevItem := first element of search-cut-list ( key ) # nextItem := successor to first element of # search-cut-list ( key ) #-] cutList = self._searchCutList ( key ) prevItem = cutList[0] nextItem = prevItem.link(0) #-- 2 -- #-[ if (nextItem is self.terminator) or # ( cmp ( key-of ( nextItem's child ), key ) ) > 0 ) -> # return None # else -> I #-] if ( ( nextItem is self.terminator ) or ( self._compareItemKey ( nextItem, key ) > 0 ) ): return None #-- 3 -- Note: nextItem is to be deleted #-[ self := self modified so that for all I in # [0,self.nLevels), if the skipItem pointed to by # cutList[I] has an (I)th link that points to # nextItem, make that link point where nextItem's # (I)th link points #-] # # NB: Possible optimization---break from the loop when # we find a level not needing repair # for i in xrange(self.nLevels): #-- 3 body -- #-[ if the _SkipItem pointed to by cutList[i] has an # (i)th link that points to nextItem -> # that link is made to point where nextItem's (i)th # link points #-] prevItem = cutList[i] if prevItem.link(i) is nextItem: prevItem.setLink(i, nextItem.link(i)) #-- 4 -- if nextItem is self._cursor: self._cursor = None #-- 5 -- self.nItems = self.nItems - 1 return nextItem.child() # - - - _ s e a r c h C u t L i s t - - - #-- Verified, 1997-4-4, Stavely # [ if key is in key-domain(self) -> # return search-cut-list ( key ) # ] def _searchCutList ( self, key ): #-- 1 -- #-[ result := a list of size self.maxLevels such that # each element is self.heads # searchItem := self.heads #-] result = [self.heads] * self.maxLevels searchItem = self.heads #-- 2 -- #-[ if search-precedes ( searchItem, key ) -> # result := result modified so that for I in # [0,self.nLevels), # result[I] := search-point(I, key) # searchItem := #-] for i in xrange ( self.nLevels-1, -1, -1 ): #-- 2 body -- #-[ if search-precedes ( searchItem, key ) -> # result[i] := search-point-after(i, key, searchItem) # searchItem := #-] searchItem = self._searchPoint ( searchItem, i, key ) result[i] = searchItem #-- 3 -- self.nSearches = self.nSearches + 1 return result # - - - _ s e a r c h P o i n t - - - #-- Verified, 1997-4-4, Stavely # [ if ( level is in [0,self.maxLevels ) ) and # ( search-precedes ( searchItem, key ) ) -> # return search-point-after ( level, key, searchItem ) # ] def _searchPoint ( self, searchItem, level, key ): #-- 1 -- #-[ prevItem := searchItem # nextItem := successor of searchItem in (level)th list #-] prevItem = searchItem nextItem = searchItem.link(level) #-- 2 -- #-[ if nextItem is not self.heads -> # if search-precedes ( nextItem, key ) -> # prevItem := last item E in nth-list(nextItem, level) # such that search-predeces(E, key) is true # nextItem := # else -> I #-] while self._searchPrecedes ( nextItem, key ): prevItem = nextItem nextItem = nextItem.link(level) #-- 3 -- return prevItem # - - - _ s e a r c h P r e c e d e s - - - #-- Verified, 1997-4-4, Stavely # [ if ( skipItem is a _SkipItem ) and # ( key is in key-domain(self) ) -> # if search-precedes ( skipItem, key ) -> # return 1 # else -> # return 0 # ] def _searchPrecedes ( self, skipItem, key ): #-- 1 -- if skipItem is self.terminator: return 0 # Terminator never precedes anything #-- 2 -- #-[ if cmp ( key-of(skipItem's child), key ) < 0 -> # return 1 # else -> # return 0 #-] if self._compareItemKey ( skipItem, key ) < 0: return 1 else: return 0 # - - - m a t c h - - - Exact search #-- Verified, 1997-4-4, Stavely def match ( self, key ): #-- 1 -- #-[ searchItem := search-point ( 0, key ) . link(0) #-] searchItem = self._searchCutItem ( key ) #-- 2 -- #-[ if (searchItem is a _SkipItem in self) -> # if (searchItem is not self.terminator) and # ( cmp ( key-of (searchItem's child), key ) ) == 0 ) -> # self._cursor := searchItem # return searchItem's child # else -> # self._cursor := None # raise ValueError #-] if ( searchItem is not self.terminator ) and \ ( self._compareItemKey ( searchItem, key ) == 0 ): self._cursor = searchItem return searchItem.child() else: self._cursor = None raise ValueError # - - - f i n d - - - Approximate search #-- Verified, 1997-4-4, Stavely def find ( self, key ): #-- 1 -- #-[ searchItem := search-point ( 0, key ).link(0) #-] searchItem = self._searchCutItem ( key ) #-- 2 -- if searchItem is self.terminator: self._cursor = None raise ValueError else: self._cursor = searchItem return searchItem.child() # - - - _ s e a r c h C u t I t e m - - - #-- Verified, 1997-4-4, Stavely # [ if key is in key-domain(self) -> # return search-point(0, key).link(0) # ] def _searchCutItem ( self, key ): #-- # This is basically the same logic as _searchCutList, but # the caller is interested only in the level-0 element, so # we avoid building up the entire cut list so as to reduce # storage allocator calls. # NB: As originally verified, this routine returned # search-point(0, key); thanks to David Taylor, e-mail # , for pointing out that this # returned the wrong element. #-- #-- 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.link(0) # - - - f i r s t - - - #-- Verified, 1997-4-8, Stavely def first ( self ): #-- 1 -- #-[ firstItem := successor of self.heads in list 0 #-] firstItem = self.heads.link(0) #-- 2 -- if firstItem is self.terminator: self._cursor = None return None else: self._cursor = firstItem return firstItem.child() # - - - n e x t - - - #-- Verified, 1997-4-8, Stavely def next ( self ): #-- 1 -- if not self._cursor: raise IndexError #-- 2 -- #-[ nextItem := successor of self._cursor at level 0 #-] nextItem = self._cursor.link(0) #-- 3 -- if nextItem is self.terminator: self._cursor = None return None else: self._cursor = nextItem return nextItem.child() # - - - - - Private class _SkipItem - - - - - #================================================================ # Each instance holds one stored object in the child-domain of a # SkipList along with its associated links. #---------------------------------------------------------------- # Exported methods: #---------------------------------------------------------------- # _SkipItem ( child, nLevels) # [ if nLevels is an integer >= 1 -> # return a new SkipItem with child=(child) and # (nLevels) forward links, each set to None # ] #-- # .child(): # [ return self's child # ] #-- # .link(i): # [ if i is an integer in [0,len(self.links)) -> # return self's (i)th forward link # else -> # raise IndexError # ] #-- # .setLink(i, child): # [ if i is an integer in [0,len(self.links)) -> # set self's (i)th link to child # else -> # raise IndexError # ] #---------------------------------------------------------------- # - - - State and invariants - - - #-- # .value: Stored value. # INV: Can be any object including None. #-- # .links: Forward links. # INV: A list of one or more links, each of which can be either # None or a reference to a _SkipItem. #-- class _SkipItem: # - - - _ S k i p I t e m - - - #-- Verified, 1997-4-8, Stavely def __init__ ( self, child, nLevels ): self.value = child self.links = [None]*nLevels # - - - c h i l d - - - #-- Verified, 1997-4-8, Stavely def child ( self ): return self.value # - - - l i n k - - - #-- Verified, 1997-4-8, Stavely def link ( self, n ): return self.links[n] # - - - s e t L i n k - - - #-- Verified, 1997-4-8, Stavely def setLink ( self, i, child ): self.links [ i ] = child