Class: SkipList

• Inheritance
• Description
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • adding
  • element comparison
  • enumerating
  • initialization
  • node enumeration
  • private
  • removing
  • testing

Inheritance:

   Object
   |
   +--Collection
      |
      +--SkipList
         |
         +--IdentitySkipList

Package:

stx:libbasic2

Category:

Collections-Ordered-Trees

Version:

rev: 1.1 date: 2017/06/18 15:49:18

user: cg

file: SkipList.st directory: libbasic2

module: stx stc-classLibrary: libbasic2

Description:

From 'Skip Lists: A Probabilistic Alternative to Balanced Trees' by William Pugh 
( http://epaperpress.com/sortsearch/download/skiplist.pdf ):

Skip lists are a data structure that can be used in place of balanced trees.  
Skip lists use probabilistic balancing rather than strictly enforcing balancing 
and as a result the algorithms for insertion and deletion in skip lists are much simpler 
and significantly faster than equivalent algorithms for balanced trees.

Notes:

The elements of the skip list must implement #< or you must provide a sort block.

Class protocol:

 maxLevel: maxLevel

SkipList maxLevel: 5

 maxLevel: anInteger sortBlock: aBlock

 new

SkipList new

 new: anInteger

(comment from inherited method)
return an instance of myself with anInteger indexed variables

 new: anInteger sortBlock: aBlock

 sortBlock: aBlock

Instance protocol:

 level

 maxLevel

 maxLevel: n

Modified (format): / 18-06-2017 / 17:42:51 / cg

 size

 sortBlock

 sortBlock: aBlock

Modified (format): / 18-06-2017 / 17:44:44 / cg

 add: element

(comment from inherited method)
add the argument, anObject to the receiver.
If the receiver is ordered, the position of the new element is undefined
(i.e. don't depend on where it will be put).
An error is raised here - it is to be implemented by a concrete subclass.

 add: element ifPresent: aBlock

 is: element1 equalTo: element2

 do: aBlock

(comment from inherited method)
evaluate the argument, aBlock for each element.
Return the receiver
(subclasses should care to also return the receiver,
in case do: is used in a chain of messages.)

 initialize: maxLevel

 nodesDo: aBlock

Modified (format): / 18-06-2017 / 17:31:41 / cg

 atForward: i put: node

Modified (format): / 18-06-2017 / 17:32:30 / cg

 forward: i

 is: node before: element

 is: node theNodeFor: element

 next

 randomLevel

Modified (format): / 18-06-2017 / 17:42:59 / cg

 search: element updating: array

At this point: node < element <= forward

 remove: element ifAbsent: aBlock

Modified (format): / 18-06-2017 / 17:43:30 / cg

 removeAll

Modified (format): / 18-06-2017 / 17:43:39 / cg

 includes: element

(comment from inherited method)
return true, if an element equal to the argument, searchedElement is in the collection.
This compares using #= (i.e. it does not look for the object itself,
instead, one that compares equal).
See #includesIdentical: when identity is asked for.
This is a *very* slow fallback - many subclasses redefine this for performance.

 isEmpty

(comment from inherited method)
return true, if the receiver is empty