glib 1.4 : skip list

[Daniele Cruciani <cruciani cli di unipi it>]

Hi,

I know it could be too late ...

I would like to have skip list implementation on glib 1.4 .

At this time, I don't known what the plan for glib 1.4, but if I've
some time (at late september - begin of october) I can work on that,
but i need support from a glib developer, now I'm too busy.

I need Skip List for a university project, and probably I'll provide
test too.

>From Communication of the ACM (June 1990 Volume 33 Number 6):

"Skip List: a Probabilistic Alternetive to Balanced Tree"

abstract: Skip lists are data structures that use probabilistic
	  balancing rather than strictly enforced balancing. As a
	  reusult, the algorithms for insertion and deletion in skip
	  lists are much simpler and significantly faster than
	  equivalent algorithms for balanced trees.

Author: William Pugh

Actually, it's really simpler to implement (one day hack)
Also, it could be implemented simple procedures for previous and next
element (of a given one): let try to make a previous and next with
btree ...

I'll don't take offence if someone stole me this job ;)

ciao.

P.S. : I've just installed a new mail server, and actually i'm busy
now, so I hope that From field in the mail is right ... please reply
me directly at cruciani cli di unipi it

-- 
Daniele Cruciani <cruciani cli di unipi it>
Universita` di Pisa - Informatica -
http://www.cli.di.unipi.it/~cruciani/