First try:a skiplist implementation

[Brian Rice]

Welcome. :)

On Jan 11, 2005, at 6:29 AM, Márton Sasvári (IJ/ETH) wrote:

> Hi,
>
> I was starting to study Slate recently. As an exercise I've 
> implemented a skiplist as there wasn't one in the collection library. 
> Naming (SkipListNode) came from the Squeak implementation but as I 
> developped it test-first there should not be too much resemblance with 
> it.

Cool!

> Unit test are at the end of the file.

Doubly so!

> I would appreciate any comments on style, language use, etc.
> Tested on Slate-0.3.1 but if I followed the list thoroughly there was 
> no language spec change in the basic features besides delegation what 
> I did not use in that depth.

That's right - this program should work fine in current-CVS Slate.

There's one issue that could expose a bug later, that you are using 
RandomStream itself instead of calling newSeed: to get a fresh one. 
That could cause contention in the presence of concurrency.

As for style, mostly I would say that you can now take advantage of the 
`>> macro (cascade syntax) to change:

sl@(SkipList traits) newEmpty
[| newSL |
   newSL: sl clone.
   newSL pointers: (Array newSize: 5).
   newSL maxLevel: 5.
   newSL numElements: 0.
   newSL
].

into:

sl@(SkipList traits) newEmpty
[sl clone `>> [pointers: (sl pointers newSize: 5). maxLevel: 5. 
numElements: 0. ]].

I also changed the #pointers initialization to refer to the existing 
slot, which requires that it be set up in the named-prototype, but it 
also means that the code is less brittle, since the underlying 
implementation isn't hardcoded so much (which allows for dynamically 
changing it and getting forward-propagation of it, although in 
SkipList's case it may not matter).

Furthermore, you can make SkipListNode an "attribute type" of SkipList, 
like so:

(SkipList traits addPrototype: #Node derivedFrom: {Cloneable})
   `>> [addSlot: #pointers. addSlot: #object. ].

And then you can refer to the named prototype as "SkipList Node" or 
"<myList> Node".

Everything else looks pretty good, although I may spend some time 
cleaning up the control-flow of the larger methods to make them a 
little more clear before checking this into CVS (you don't mind, do 
you?).

Thanks!

--
Brian T. Rice
LOGOS Research and Development
http://tunes.org/~water/