From: Brian Hurt <bhurt@sp...>  20040602 20:37:24

On Wed, 2 Jun 2004, Bardur Arantsson wrote: > I suppose it would require slightly more than strictly > necessary, but I can't think of any nontreelike > implementation of a nondestructive maptype structure > which can achieve the same low complexity for all the > needed operations. (But I'm not _that_ familiar with more > advanced data structures, so you should take that with a > grain of salt...) The more I think about it, the more I like basically requiring a tree structure. For the core operations (find, add, remove), a tree structure is already O(log N). The next step faster than that is O(1) which I don't think we'll get. Well, we get them with a hash, but I don't think you could implement a functional hash, and we already have an imperitive hash. Note that when I say "tree", this also includes "treelike" structures, like 2,3,4trees and btrees. All I need is that the nodes be kept in some sort of sorted order. Allowing you to traverse them in a forward or backwards order in O(N). I notice that I specified that the enumerations come out in sorted order I wanted to do this so that I could do efficient (O(N)) maps using enums, so long as the map maintained the sorted property. So this may already be a requirement in the new interface. > I don't think it would necessarily bloat the code since > you can implement one (two, perhaps?) generic traversal > algorithm which can support all of the above, and then > just call it with appropriate closures. True. I'd be inclined to declare the directionless comprehensions to be deprecated, and that new code should specify a direction (left or right). > Well, technically it's quite possible to maintain the key > values separately in a Set, and get a "sorted map" that > way. Insertion/deletion/etc. costs about twice as much as > just using the Map. But if we want to iterate through the > (key,value) pairs in that Map in sorted order, there are > basically two approaches: > > 1) Use Set to get sorted list of keys; iterate through > keys, using ExtMap.find to retrieve the corresponding > value. O(n*log n), n lookups and O(log n) lookup time. > > 2) Use ExtMap.elements to get a list of (key,value) pairs, > sort that and iterate. O(n*log n) from the sort. > > Neither of which is as fast as just direct traversal of > the Map tree would be. Yep, they'd qualify. Although I suppose you could use the sorted gaurentee of enums to your advantage but it'd still be more efficient to do it directly.  "Usenet is like a herd of performing elephants with diarrhea  massive, difficult to redirect, aweinspiring, entertaining, and a source of mindboggling amounts of excrement when you least expect it."  Gene Spafford Brian 