First try:a skiplist implementation

[Brian Rice]

I have made the said corrections and checked these into CVS as files 
src/lib/skiplist.slate and tests/skiplist.slate. One test failed, the 
#newPointerLength test. I haven't investigated it. Let me know if there 
are any issues. :)

On Jan 11, 2005, at 10:08 AM, Brian Rice wrote:

> 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/