Am 19.09.2005 um 09:26 schrieb Andreas Raab:


>
> Besides, I'd be much more interested in a hashtable/dictionary  
> implementation that preserves ordering (e.g., if an element is  
> added before another it will be enumerated before the other) to  
> preserve consistency in a replicated computation. I'll definitely  
> need to look into this so if anyone has an implementation I'm all  
> ears...
>

Skiplists are a kind of blend between OrderedCollection and  
Dictionary: You have a defined ordering (like in OrderedCollection,  
that is, your objects
would need to implement #<, or you can provide a sortBlock), and are  
free-access like dictionaries. And the best, they are quite efficient.

There is an enhanced implementation on Mantis:

   http://bugs.impara.de/view.php?id=1555

"
A skiplist is a sorted data structure that allows one to search for  
any element in o(log n) time.

It also allows one to enumerate forward to the next element.  
Basically, its a tree-like algorithm, except it doesn't use trees.

The implementation here is similar to a Dictionary, in that it  
indexes (a subclass of) Associations. Thus, you can do    foo at: key  
put: value
You can also search for a key, if the key does not exist, it will  
report the first key greater than the search, or nil.
"

So if your events have an ordering (a timestamp), then this should be  
worth a look.

             Marcus