# skiplist.icn: An object to store ordered sets, using an algorithm # introduced in ``Skip lists: a probabilistic alternative to # balanced trees'' by William Pugh, Comm. ACM 33(6)668-676, # June 1990. #-- $define SKIP_LIST_REVISION "$Revision: 1.22 $" $define SKIP_LIST_DATE "$Date: 1996/12/01 00:54:16 $" #================================================================ # Class SkipList: Each instance represents an ordered set of # elements of the same type. # Ordinarily when I need to generate things in some sequence, # I'll put them into an Icon table whose key sorts in the # correct order, and use sort() to pull them out. # There are several reasons why this won't work for some # applications: # (1) Sometimes you want to dive into a certain point # in the sequence, and pull out elements in # sequence after that point. It's silly to sort # the entire array every time you want one or two # elements. # (2) It requires that the key be materialized as a # single, comparable string. This makes it impossible # to have, for example, a mixture of ascending and # descending fields. For flexibility, it is nice # to be able to define the ordering of elements # by providing a procedure that can be applied to # any pair of elements to say what order they should # come in. # Skip lists fit these requirements nicely. You can quickly # jump to any point in the sequence, and then use the lowest- # level list to access further elements in sequence. #---------------------------------------------------------------- # METHODS #---------------------------------------------------------------- # Skip_List_New ( comparator, allowDups, maxLevels ) # [ if the arguments satisfy the invariants of the corresponding # fields (maxLevels defaulting to MAX_LEVELS_DEFAULT) -> # return a new SkipList object with those fields, and # containing no elements # ] #-- # Skip_List_Insert ( self, value ) # [ if value is an object in the domain of self.comparator -> # if self.allowDups is false and there is an element x # in self such that self.comparator ( x, value ) returns 0 -> # fail # else -> # self := self with value added, after any other values # that self.comparator calls equal # return &null # ] #-- # Skip_List_Delete ( self, value ) # [ if value is an object in the domain of self.comparator -> # if self contains any elements x such that # self.comparator ( x, value ) returns 0 -> # self := self with the first such element deleted # return &null # else -> # fail # ] #-- # Skip_List_Search ( self, value ) # [ if value is an object in the domain of self.comparator -> # generate the objects x in self such that # self.comparator ( x, value ) returns 0, in the order # in which they were inserted # ] #-- # Skip_List_Search_Range ( self, value, stopValue ) # [ if value is &null or in the domain of self.comparator and # stopValue is &null or in the domain of self.comparator -> # generates the objects x in self such that # self.comparator ( x, value ) returns >= 0 (or from the # beginning if value is &null), and # self.comparator ( x, stopValue ) returns < 0 (or to the end # if stopValue is &null), as ordered by self.comparator, with # equal values generated in the order in which they were inserted # ] #-- # Skip_List_N_Searches ( self ) # [ returns the number of times we've searched the list for an item # ] #-- # Skip_List_N_Compares ( self ) # [ returns the number of times we've compared two elements # with the .comparator function # ] #---------------------------------------------------------------- record skipListTag ( # State for a SkipList object comparator, # Ordering function allowDups, # True if we're allowed to store two objects # that are equal according to .comparator maxLevels, # Maximum number of levels nLevels, # Number of levels currently in use heads, # A SkipItem containing the heads of the lists terminator, # A SkipItem, a pointer to which denotes end-of-list nItems, # Number of items stored in the list nSearches, # Number of times we've searched the list nCompares ) # Number of times we've called .comparator #---------------------------------------------------------------- # INVARIANTS #---------------------------------------------------------------- # .comparator == # a function with calling sequence # .comparator(x,y) # that takes two objects x and y of the type of object stored # in this list and returns: # if x comes before y -> a negative integer # if x comes after y -> a positive integer # if x and y are ranked equal -> the integer 0 #-- # .allowDups == # if self is allowed to contain items ranked equal by .comparator -> # a non-null value # else -> &null #-- # .maxLevels == an integer >= 1 limiting the size of the skip # list #-- # .nLevels == an integer in the interval [0, .maxLevels] indicating # how many skip list levels are currently in use #-- # .heads == # a SkipItem object having .maxLevels forward pointers such that: # (1) The first list rooted in .heads is a linked list # ordering all elements in the set according to .comparator, # with equal-ranked elements ordered so that later-inserted # elements follow earlier-inserted elements. # (2) For every (i)th list rooted in .heads, i in [2, .nLevels], # that list is a subset of the elements in the next # lower-numbered list. # (3) Each list is terminated by a pointer to .terminator. #-- # .terminator == # a SkipItem object having .maxLevels forward pointers, all &null #-- # .nItems == the number of items currently stored in the list #-- # .nSearches == the number of times we've searched the whole # list for some item #-- # .nCompares == the number of times we've called .comparator #---------------------------------------------------------------- # DEFINITIONS #---------------------------------------------------------------- # insertion-cut-list ( skipList, target ) == # a list L of size skipList.maxLevels such that for all # i in [1, skipList.maxLevels] -> # L[i] := insertion-point ( skipList, i, target ) #-- # Translation: insertion-cut-list ( skipList, target ) is # the list of predecessors whose forward links must be # updated at the site when (target) is inserted into (skipList) #---------------------------------------------------------------- # insertion-point ( skipList, level, target ) == # the last element E in nth-list ( skipList, skipList.heads, level ) # such that insertion-precedes ( skipList, E, target ) is true #-- # Translation: insertion-point ( skipList, level, target ) == # the predecessor whose forward link must be updated when # (target) is inserted into list (level) of (skipList) #---------------------------------------------------------------- # insertion-point-after ( skipList, level, target, searchItem ) == # the last element E in nth-list ( skipList, searchitem, level ) # such that insertion-precedes ( skipList, E, target ) is true #-- # Translation: This define is like insertion-point, except that, # assuming searchItem precedes target, we can start searching # at searchItem instead of having to go all the way back to .heads. # When using this define, it is recommended that you have a # precondition that (searchItem) precedes (target). #---------------------------------------------------------------- # insertion-precedes ( skipList, skipItem, target ) == # if skipList.allowDups is true -> # if skip-compare ( skipList, skipitem, target ) <= 0 -> true # else -> false # else -> # search-precedes ( skipList, skipItem, target ) #-- # Translation: a predicate that is true if (skipItem) goes before # (target) in skipList, false otherwise #---------------------------------------------------------------- # nth-list ( skipList, skipItem, n ) == # the linked list of SkipItem objects rooted at skipItem # and using Skip_Item_Nth_Link ( skipItem, n ) as a forward link #---------------------------------------------------------------- # search-cut-list ( skipList, target ) == # a list L of size skipList.maxLevels such that for all # i in [1, skipList.maxLevels] -> # L[i] := search-point ( skipList, i, target ) #-- # Translation: the list of predecessors whose forward links must # be updated when element (target) is deleted from (skipList) #---------------------------------------------------------------- # search-point ( skipList, level, target ) == # the last block E in nth-list ( skipList, skipList.heads, level ) # such that search-precedes ( skipList, E, target ) is true #-- # Translation: the predecessor whose forward link must be updated # when element (target) is deleted from list (level) of (skipList) #---------------------------------------------------------------- # search-point-after ( skipList, level, target, searchItem ) == # the last element E in nth-list ( skipList, searchitem, level ) # such that search-precedes ( skipList, E, target ) is true #-- # Translation: This define is like search-point, except that, # assuming searchItem precedes target, we can start searching # at searchItem instead of having to go all the way back to .heads. # When using this define, it is recommended that you have a # precondition that (searchItem) precedes (target). #---------------------------------------------------------------- # search-precedes ( skipList, skipItem, target ) == # if skip-compare ( skipList, skipItem, target ) < 0 -> true # else -> false #-- # Translation: a predicate that is true if (skipItem) precedes # (target) in (skipList), false otherwise #---------------------------------------------------------------- # skip-compare ( skipList, skipItem, target ) == # if skipItem is skipList.terminator -> 1 # else -> skipList.comparator ( value of skipItem, target ) #---------------------------------------------------------------- # DEFINES #---------------------------------------------------------------- # The NEW_LEVEL_PROBABILITY is the `p' of Pugh's article, and # is used to determine into how many levels of the skip list # a new item is linked upon its creation. See Skip_List_Pick_Level() # for details, but in general a new node will have a probability # (1-p) of being in only one level; probability (1-p)*p of # being in two; and in general propability (1-p)*(p^(k-1)) of # being in k lists. For example, if p is 0.25, 3/4 of the # nodes will live only in the first list; 1/4 will be in two # or more lists; 1/16 will be in three or more lists; and so on. #-- $define NEW_LEVEL_PROBABILITY 0.25 # p of the article #-- # The MAX_LEVELS_DEFAULT is the default limit on the number of # levels in the skip list. According to the analysis done in # Pugh's article, a skip list should be able to deliver O(log n) # search times so long as the number of elements does not exceed # (1 / NEW_LEVEL_PROBABILITY ) ^ (number of levels) #-- $define MAX_LEVELS_DEFAULT 10 # Should handle (1/p)^n objects # - - - S k i p _ L i s t _ N e w - - - #-- 1996-07-01: Verified by trace table, JS #-- 1996-07-19: Verified with Stavely # [ if the arguments satisfy the invariants of the corresponding # fields (maxLevels defaulting to MAX_LEVELS_DEFAULT) -> # return a new SkipList object with those fields, and # containing no elements # ] procedure Skip_List_New ( comparator, allowDups, maxLevels ) local self # New SkipList object to be returned #-- 1 -- #-[ self := a new SkipList object with fields: # .comparator := comparator # .allowDups := allowDups # .maxLevels := maxLevels, defaulting to MAX_LEVELS_DEFAULT # .nLevels := 0 # .heads := &null # .terminator := &null # .nSearches := 0 # .nCompares := 0 #-] self := skipListTag ( ); self.comparator := comparator; self.allowDups := allowDups; self.maxLevels := ( \ maxLevels ) | MAX_LEVELS_DEFAULT; self.nLevels := 0; self.nItems := 0; self.nSearches := 0; self.nCompares := 0; #-- 2 -- #-[ self.terminator := a new SkipItem with a value of &null, and links # a list of self.maxLevels &null values #-] self.terminator := Skip_Item_New ( &null, self.maxLevels ); #-- 3 -- #-[ self.heads := a new SkipItem with a value of &null, and links a # list of self.maxLevels pointers to self.terminator #-] self.heads := Skip_Item_New ( &null, self.maxLevels ); every Skip_Item_Set_Nth_Link ( self.heads, 1 to self.maxLevels, self.terminator ); #-- 4 -- return self; end # --- Skip_List_New --- # - - - S k i p _ L i s t _ N _ I t e m s - - - procedure Skip_List_N_Items ( self ) return self.nItems; end # --- Skip_List_N_Items --- # - - - S k i p _ L i s t _ N _ S e a r c h e s - - - #-- 1996-07-01: Verified by trace table, JS #-- 1996-07-19: Verified with Stavely # [ returns the number of times we've searched the list for an item # ] procedure Skip_List_N_Searches ( self ) return self.nSearches; end # - - - S k i p _ L i s t _ N _ C o m p a r e s - - - #-- 1996-07-01: Verified by trace table, JS #-- 1996-07-19: Verified with Stavely # [ returns the number of times we've compared two elements # with the .comparator function # ] procedure Skip_List_N_Compares ( self ) return self.nCompares; end # - - - S k i p _ L i s t _ I n s e r t - - - #-- 1996-08-08: Verified with Stavely # [ if value is an object in the domain of self.comparator -> # if self.allowDups is false and there is an element x # in self that self.comparator calls equal -> # fail # else -> # self := self with value added, after any other values # that self.comparator calls equal # return &null # ] procedure Skip_List_Insert ( self, value ) local cutList # List of predecessors at each level local prevItem # Predecessor of insertion point local nextItem # Successor of prevItem #-- 1 -- #-[ cutList := insertion-cut-list ( self, value ) #-] cutList := Skip_List_Insert_Cut_List ( self, value ); #-- 2 -- #-[ prevItem := first item from cutList # nextItem := successor of first item from cutList #-] prevItem := cutList[1]; nextItem := Skip_Item_Nth_Link ( prevItem, 1 ); #-- 3 -- #-[ if self.allowDups is &null and self.comparator compares # nextItem's value equal to (value) -> # fail # | else -> I #-] if ( / self.allowDups ) & ( nextItem ~=== self.terminator ) & ( Skip_List_Compare_Item_Value ( self, nextItem, value ) = 0 ) then fail; #-- 4 -- #-[ if cutList is insertion-cut-list(self, value) -> # self := self with a new SkipItem containing (value) # inserted after the items pointed at by the first n # elements of cutList, where n is in [1, self.maxLevels] #-] Skip_List_Insert_Item ( self, value, cutList ); #-- 5 -- self.nItems +:= 1; # Keep a running count of items return; end # --- Skip_List_Insert --- # - - - S k i p _ L i s t _ I n s e r t _ C u t _ L i s t - - - #-- 1996-07-02: Verified by trace table, JS #-- 1996-07-31: Verified with Stavely # [ if target is in the domain of self.comparator -> # returns insertion-cut-list ( self, target ) # ] procedure Skip_List_Insert_Cut_List ( self, target ) local result # List to be returned local level # Walks the levels of the skip list local searchItem # Current search location, a SkipItem #-- 1 -- #-[ result := a list of size (self.maxLevels) with each # element pointing to (self.heads) # searchItem := self.heads #-] result := list ( self.maxLevels, self.heads ); searchItem := self.heads; #-- 2 -- #-[ if insertion-precedes ( self, searchItem, target ) -> # result := result modified so that for I in [1, self.nLevels], # result[I] := insertion-point ( self, I, target ) # searchItem := #-] every level := self.nLevels to 1 by -1 do { #-- 2 body -- #-[ if insertion-precedes ( self, searchItem, target ) -> # (result[level], searchItem) := # insertion-point-after ( self, level, target, searchItem ) #-] searchItem := Skip_List_Insert_Point ( self, searchItem, level, target ); result [ level ] := searchItem; } #-- 2 body -- #-- 3 -- self.nSearches +:= 1; return result; end # --- Skip_List_Insert_Cut_List --- # - - - S k i p _ L i s t _ I n s e r t _ P o i n t - - - #-- 1996-07-03: Verified by trace table, JS #-- 1996-07-31: Verified with Stavely # [ if insertion-precedes ( self, searchItem, target ) -> # return insertion-point-after ( self, level, target, searchItem ) # ] procedure Skip_List_Insert_Point ( self, searchItem, level, target ) local prevItem # Walks the (level)th list local nextItem # Successor to prevItem #-- 1 -- #-[ prevItem := searchItem # nextItem := successor of searchItem in (level)th list #-] prevItem := searchItem; nextItem := Skip_Item_Nth_Link ( searchItem, level ); #-- 2 -- #-[ if not insertion-precedes ( self, nextItem, target ) -> I # | else -> # prevItem := last item E at or after nextItem in the # (level)th list such that # insertion-precedes ( self, E, target ) is true # nextItem := first item F at or after nextItem in the # (level)th list such that # insertion-precedes ( self, F, target ) is false #-] while Skip_List_Insertion_Precedes ( self, nextItem, target ) do { #-- 2 body -- #-[ previItem := nextItem # nextItem := the successor of nextItem in the (level)th list #-] prevItem := nextItem; nextItem := Skip_Item_Nth_Link ( nextItem, level ); } #-- 2 body -- #-- 3 -- return prevItem; end # --- Skip_List_Insert_Point --- # - - - 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 - - - #-- 1996-07-03: Verified by trace table, JS #-- 1996-07-21: Verified with Stavely # [ if target is in the domain of self.comparator and # skipItem is a SkipItem -> # if insertion-precedes ( self, skipItem, target ) -> # return &null # | else -> fail # ] procedure Skip_List_Insertion_Precedes ( self, skipItem, target ) local comparison # Result from self.comparator #-- 1 -- #-[ if skipItem is self.terminator -> fail # | else -> I #-] if skipItem === self.terminator then fail; #-- 2 -- #-[ comparison := self.comparator ( value of skipItem, target ) #-] comparison := Skip_List_Compare_Item_Value ( self, skipItem, target ); #-- 3 -- #-[ if self.allowDups is &null -> # if comparison < 0 -> return &null # else -> fail # | else -> # if comparison <= 0 -> return &null # else -> fail #-] if / self.allowDups then { if comparison < 0 then return &null else fail; } else { if comparison <= 0 then return &null else fail; } end # --- Skip_List_Insertion_Precedes --- # - - - S k i p _ L i s t _ P i c k _ L e v e l - - - #-- 1996-07-03: Verified by trace table, JS #-- 1996-07-21: Verified with Stavely # [ self.nLevels := max of self.nLevels and a randomly chosen # integer in [1, self.maxLevels] # returns that randomly chosen integer # ] procedure Skip_List_Pick_Level ( self ) #-- # Note: this logic implements what the inventor of skip lists calls # a `dirty hack', that is, the new level will never exceed the # existing number of levels (self.nLevels) by more than one. #-- local result # Result to be returned local maxNewLevel # Maximum possible new level #-- 1 -- #-[ result := 1 # maxNewLevel := smaller of (self.nLevels+1) and self.maxLevels #-] result := 1; maxNewLevel := self.nLevels + 1; maxNewLevel >:= self.maxLevels; # a >:= b means a := min(a,b) #-- 2 -- #-[ result := result possibly increased randomly, but not > maxNewLevel #-] #-- # Note: (?0) returns a random float in [0.0, 1.0) #-- while ( (?0) <= NEW_LEVEL_PROBABILITY ) & ( result < maxNewLevel ) do result +:= 1; #-- 3 -- #-[ self.nLevels := max of self.nLevels and result #-] self.nLevels <:= result; # a <:= b means a := max(a,b) #-- 4 -- return result; end # --- Skip_List_Pick_Level --- # - - - S k i p _ L i s t _ I n s e r t _ I t e m - - - #-- 1996-08-08: Verified with Stavely # [ if cutList is insertion-cut-list(self, value) -> # self := self with a new SkipItem containing (value) # inserted after the items pointed at by the first n # elements of cutList, where n is in [1, self.maxLevels] # ] procedure Skip_List_Insert_Item ( self, value, cutList ) local levels # How many levels the new item will have local newItem # The new SkipItem to be inserted #-- 1 -- #-[ levels := a random integer in [1, self.maxLevels] # self.nLevels := max ( self.nLevels, that random integer) #-] levels := Skip_List_Pick_Level ( self ); #-- 2 -- #-[ newItem := a new SkipItem with value (value) and (levels) # forward links, all &null #-] newItem := Skip_Item_New ( value, levels ); #-- 3 -- #-[ if cutList is insertion-cut-list(self, value) and # newItem is a SkipItem with at least (levels) forward links -> # self := self with newItem linked into the first (levels) # lists, just after the element pointed at by # the corresponding element of cutList #-] Skip_List_Insert_Relink ( self, levels, cutList, newItem ); end # --- Skip_List_Insert_Item --- # - - - S k i p _ L i s t _ I n s e r t _ R e l i n k - - - #-- 1996-08-08: Verified with Stavely # [ if cutList is insertion-cut-list(self, value) 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 # ] procedure Skip_List_Insert_Relink ( self, levels, cutList, newItem ) local lx # Walks from 1 to levels local prevItem # The SkipItem that precedes newItem local succItem # The SkipItem that follows newItem #-- 1 -- every lx := 1 to levels do { #-- 1 body -- #-[ if lx is an integer in [1, levels] -> # let P be the item pointed at by cutList[lx] in: # newItem := newItem with link (lx) pointing where link (lx) # of item P points # P := P with link (lx) pointing at newItem #-] #-- 1.1 -- #-[ if lx is an integer in [1, levels] -> # prevItem := the item pointed at by cutList[lx] # succItem := link (lx) of the item pointed at by cutList[lx] #-] prevItem := cutList[lx]; succItem := Skip_Item_Nth_Link ( prevItem, lx ); #-- 1.2 -- #-[ if lx is an integer in [1, levels] -> # newItem := newItem with link (lx) pointing to succItem # prevItem := prevItem with link (lx) pointing to newItem #-] Skip_Item_Set_Nth_Link ( newItem, lx, succItem ); Skip_Item_Set_Nth_Link ( prevItem, lx, newItem ); } #-- 1 body -- end # --- Skip_List_Insert_Relink --- # - - - S k i p _ L i s t _ D e l e t e - - - #-- 1996-07-05: Verified by trace table, JS #-- 1996-07-31: Verified with Stavely # [ if value is an object in the domain of self.comparator -> # if self contains any elements x such that # self.comparator ( x, value ) returns 0 -> # self := self with the first such element deleted # else -> # fail # ] procedure Skip_List_Delete ( self, value ) local cutList # search-cut-list ( self, value ) local prevItem # The first element of search-cut-list ( self, value ) local nextItem # The immediate successor to prevItem local level # Walks levels needing relinking #-- 1 -- #-[ cutList := search-cut-list ( self, value ) # prevItem := first element of search-cut-list ( self, value ) # nextItem := successor to first element of # search-cut-list ( self, value ) #-] cutList := Skip_List_Search_Cut_List ( self, value ); prevItem := cutList[1]; nextItem := Skip_Item_Nth_Link ( prevItem, 1 ); #-- 2 -- #-[ if nextItem is self.terminator or # self.comparator ( value of nextItem, value ) > 0 -> # fail # | else -> I #-] if ( nextItem === self.terminator ) | ( Skip_List_Compare_Item_Value ( self, nextItem, value ) > 0 ) then fail; # Attempt to delete nonexistent element #-- 3 -- #-[ self := self modified so that for all I in [1, self.nLevels], # 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 #-] every level := 1 to self.nLevels do { #-- 3 body -- #-[ if the SkipItem pointed to by cutList[level] has a (level)th # link that points to nextItem -> # that link is made to point where nextItem's (level)th # link points #-] prevItem := cutList[level]; if Skip_Item_Nth_Link ( prevItem, level ) === nextItem then Skip_Item_Set_Nth_Link ( prevItem, level, Skip_Item_Nth_Link ( nextItem, level ) ); } #-- 3 body -- #-- 4 -- self.nItems -:= 1; # Keep a running count of items return &null; end # --- Skip_List_Delete --- # - - - S k i p _ L i s t _ S e a r c h _ C u t _ L i s t - - - #-- 1996-07-05: Verified by trace table, JS #-- 1996-08-08: Verified with Stavely # [ if target is in the domain of self.comparator -> # returns search-cut-list ( self, target ) # ] procedure Skip_List_Search_Cut_List ( self, target ) local result # List to be returned local level # Walks the levels of the skip list local searchItem # Current search location, a SkipItem #-- 1 -- #-[ result := a list of size (self.maxLevels) with each # element pointing to (self.heads) # searchItem := self.heads #-] result := list ( self.maxLevels, self.heads ); searchItem := self.heads; #-- 2 -- #-[ if target is in the domain of self.comparator -> # if search-precedes ( self, searchItem, target ) -> # result := result modified so that for I in [1, self.maxLevels], # result[I] := search-point ( self, I, target ) # searchItem := #-] every level := self.nLevels to 1 by -1 do { #-- 2 body -- #-[ if target is in the domain of self.comparator -> # if search-precedes ( self, searchItem, target ) -> # ( result[level], searchItem ) := # search-point-after ( self, level, target, searchItem ) #-] searchItem := Skip_List_Search_Point ( self, searchItem, level, target ); result [ level ] := searchItem; } #-- 2 body -- #-- 3 -- self.nSearches +:= 1; return result; end # --- Skip_List_Search_Cut_List --- # - - - S k i p _ L i s t _ S e a r c h _ P o i n t - - - #-- 1996-07-05: Verified by trace table and inspection, JS #-- 1996-07-31: Verified with Stavely # [ if search-precedes ( self, searchItem, target ) -> # return search-point-after ( self, level, target, searchItem ) # ] procedure Skip_List_Search_Point ( self, searchItem, level, target ) local prevItem # Walks the (level)th list local nextItem # Successor to prevItem #-- 1 -- #-[ prevItem := searchItem # nextItem := successor of searchItem in (level)th list #-] prevItem := searchItem; nextItem := Skip_Item_Nth_Link ( searchItem, level ); #-- 2 -- #-[ if not search-precedes ( self, nextItem, target ) -> I # | else -> # prevItem := last item E at or after nextItem in the # (level)th list such that # search-precedes ( self, E, target ) is true # nextItem := first item F at or after nextItem in the # (level)th list such that # search-precedes ( self, F, target ) is false #-] while Skip_List_Search_Precedes ( self, nextItem, target ) do { prevItem := nextItem; nextItem := Skip_Item_Nth_Link ( nextItem, level ); } #-- 3 -- return prevItem; end # --- Skip_List_Search_Point --- # - - - S k i p _ L i s t _ S e a r c h _ P r e c e d e s - - - #-- 1996-07-05: Verified by trace table, JS #-- 1996-07-31: Verified with Stavely # [ if skipItem is a SkipItem and target is in the domain # of self.comparator -> # if search-precedes ( self, skipItem, target ) -> # return &null # else -> fail # ] procedure Skip_List_Search_Precedes ( self, skipItem, target ) local comparison # Result from self.comparator #-- 1 -- #-[ if skipItem is self.terminator -> fail # | else -> I #-] if skipItem === self.terminator then fail; #-- 2 -- #-[ if self.comparator ( skipItem's value, target ) < 0 -> # return &null # | else -> fail #-] if Skip_List_Compare_Item_Value ( self, skipItem, target ) < 0 then return else fail; end # --- Skip_List_Search_Precedes --- # - - - S k i p _ L i s t _ S e a r c h - - - #-- 1996-07-05: Verified by trace table and inspection, JS #-- 1996-08-08: Verified with Stavely # [ if target is an object in the domain of self.comparator -> # generate the objects x in self such that # self.comparator ( x, target ) returns 0, in the order # in which they were inserted # ] procedure Skip_List_Search ( self, target ) local searchItem # Walks down one list #-- 1 -- self.nSearches +:= 1; #-- 2 -- #-[ if target is an object in the domain of self.comparator -> # searchItem := search-point ( self, 1, target ) #-] searchItem := Skip_List_Search_Cut_Item ( self, target ); #-- 3 -- #-[ if searchItem is a SkipItem in self but not equal to self.terminator # and target is in the domain of self.comparator -> # searchItem := # generate all initial values from elements E from the first-level # list rooted at searchItem such that # self.comparator ( value of E, target ) returns 0 #-] while ( searchItem := Skip_List_Search_Equal ( self, searchItem, target ) ) do suspend Skip_Item_Value ( searchItem ); #-- 4 -- fail; end # --- Skip_List_Search --- # - - - S k i p _ L i s t _ S e a r c h _ C u t _ I t e m - - - #-- 1996-08-08: Verified with Stavely # [ if target is in the domain of self.comparator -> # returns search-point ( self, 1, target ) # ] procedure Skip_List_Search_Cut_Item ( self, target ) #-- # Note: This routine is pretty much the same as Skip_List_Search_Cut_List() # except that it returns only the first element of the cut list. The # caller could use that routine instead and then take out the first # element, but that approach would cause more storage allocator calls. #-- local level # Walks the levels of the skip list local searchItem # Current search location, a SkipItem #-- 1 -- #-[ searchItem := self.heads #-] searchItem := self.heads; #-- 2 -- #-[ if search-precedes ( self, searchItem, target ) -> # searchItem := search-point ( self, 1, target ) #-] every level := self.nLevels to 1 by -1 do { #-- 2 body -- #-[ if search-precedes ( self, searchItem, target ) -> # searchItem := search-point-after ( self, level, # target, searchItem ) #-] searchItem := Skip_List_Search_Point ( self, searchItem, level, target ); } #-- 2 body -- #-- 3 -- self.nSearches +:= 1; return searchItem; end # --- Skip_List_Search_Cut_Item --- # - - - S k i p _ L i s t _ S e a r c h _ E q u a l - - - #-- 1996-07-05: Verified by trace table, JS #-- 1996-08-08: Verified with Stavely # [ if searchItem is a SkipItem in self but not equal to self.terminator # and target is in the domain of self.comparator -> # if self.comparator returns 0 when comparing target with the # value of the immediate successor of searchItem -> # return that successor # else -> fail # ] procedure Skip_List_Search_Equal ( self, searchItem, target ) local nextItem # Immediate successor of searchItem #-- 1 -- #-[ nextItem := immediate successor of searchItem #-] nextItem := Skip_Item_Nth_Link ( searchItem, 1 ); #-- 2 -- #-[ if nextItem is the terminator -> fail # | else -> I #-] if nextItem === self.terminator then fail; #-- 3 -- #-[ if self.comparator returns 0 when comparing target with the # value from nextItem -> # return nextItem # | else -> fail #-] if Skip_List_Compare_Item_Value ( self, nextItem, target ) = 0 then return nextItem else fail; end # --- Skip_List_Search_Equal --- # - - - S k i p _ L i s t _ S e a r c h _ R a n g e - - - #-- 1996-08-18: Verified with Stavely # [ if target is &null or in the domain of self.comparator and # stopTarget is &null or in the domain of self.comparator -> # generates the objects x in self such that # self.comparator ( x, value ) returns >= 0 (or from the # beginning if value is &null), and # self.comparator ( x, stopValue ) returns < 0 (or to the end # if stopValue is &null), as ordered by self.comparator, with # equal values generated in the order in which they were inserted # ] procedure Skip_List_Search_Range ( self, target, stopTarget ) local level # Walks the levels local searchItem # Walks down one list #-- 1 -- self.nSearches +:= 1; #-- 2 -- #-[ if target is &null -> # searchItem := self.heads # | else -> # searchItem := search-point ( self, 1, target ) #-] if / target then searchItem := self.heads else searchItem := Skip_List_Search_Cut_Item ( self, target ); #-- 3 -- #-[ if searchItem is not self.terminator -> # if stopTarget is &null -> # generate all items starting with first-level successor of # searchItem up to self.terminator # else -> # generate all items starting with first-level successor of # searchItem, through the last element F such that # search-precedes(self, F, stopTarget) is true #-] if / stopTarget then { #-- 3.1 -- while ( ( searchItem := Skip_Item_Nth_Link ( searchItem, 1 ) ) ~=== self.terminator ) do suspend Skip_Item_Value ( searchItem ); } #-- 3.1 -- else { #-- 3.2 -- while ( searchItem := Skip_List_Search_Less ( self, searchItem, stopTarget ) ) do suspend Skip_Item_Value ( searchItem ); } #-- 3.2 -- #-- 4 -- fail; end # --- Skip_List_Search_Range --- # - - - S k i p _ L i s t _ S e a r c h _ L e s s - - - #-- 1996-07-31: Verified with Stavely # [ if searchItem is a SkipItem in self but not equal to self.terminator # and target is in the domain of self.comparator -> # if search-precedes ( self, (successor of searchItem), target) -> # return that successor # else -> fail # ] procedure Skip_List_Search_Less ( self, searchItem, target ) local nextItem # Immediate successor of searchItem #-- 1 -- #-[ nextItem := immediate successor of searchItem #-] nextItem := Skip_Item_Nth_Link ( searchItem, 1 ); #-- 2 -- #-[ if nextItem is the terminator -> fail # | else -> I #-] if nextItem === self.terminator then fail; #-- 3 -- #-[ if self.comparator returns a value < 0 when comparing the # value from nextItem with target -> # return nextItem # | else -> fail #-] if Skip_List_Compare_Item_Value ( self, nextItem, target ) < 0 then return nextItem else fail; end # --- Skip_List_Search_Less --- # - - - S k i p _ L i s t _ C o m p a r e _ I t e m _ V a l u e - - - #-- 1996-07-31: Verified with Stavely # [ if item is a SkipItem and value is in the domain of # self.comparator -> # return self.comparator ( value from item, value ) # ] procedure Skip_List_Compare_Item_Value ( self, item, value ) self.nCompares +:= 1; return self.comparator ( Skip_Item_Value ( item ), value ); end # --- Skip_List_Compare_Item_Value ---