From: Nicolas Cannasse <warplayer@fr...>  20040910 21:52:56

>  Changed name > >  Everything from Funarr still supported > >  I stuck with a weight balanced tree. Chris Okasaki's Random Access > Lists are interesting, but they're geared towards list replacement, not > array replacement. For example, I can't figure out how to delete elements > in the middle of a random access list I can with a weight balanced tree. > >  added append, to append two indexed trees in O(log N) time. The > returned tree is balanced. > >  added splice, return a subset of an indexed tree. This takes either > O(log N) where N is the length of the source tree, or O((log M)^2) where > M is the length of the returned tree. I can't think of a better way of > doing this suggestions welcomed. > >  Added list, array, and enum conversions. > >  Added rev function to reverse an indexed tree > >  I realized that I could do a binary search on the indexed tree in the > same amount of time it takes me to get a single element. So I added two > binary search functions search, which returns the found element, and > find_index, which returns the index of the found element. Note that with > these functions it now becomes possible to implement a threaded map > structure, by combining an index tree with a map. I would rename Idxtree to IdxTree , using a maj T for case. search_index instead of find_index would be more consistent. I would also drop the O(N) notations were it's obvious that all elements are browsed : of_list / to_array / iter / fold for example. I would also remove rev_enum and of_rev_enum which are a little bit particular and can be acheived using to_enum + rev or of_enum + rev. And I would add iteri + mapi functions. It has my approval for inclusion into ExtLib. You can commit it on CVS right now or wait for more people insights. Thanks, Nicolas 