On Jan 30, 6:59 pm, Rowdy Rednose <rowdy.redn...@gmx.net> wrote: >> > The goal is to narrow down a map to include only keys with a given >> > prefix.
> I want to have it in O(1). That's why I use a tree map in the first > place. You can get at the subtree of sorted-map in O(log(n)) but only as a sequence, not as another sorted-map: (subseq (sorted-map "abe" 1 "bob" 2 "bruce" 3 "charlie" 4) >= "b" < "c") => (["bob" 2] ["bruce" 3]) Looking at the source of PersistentTreeMap there appears to be no way to get at a subtree. It seems PersistentTreeMaps have constant-time 'count', but only the root stores this count. Unless I'm missing something to make subtrees available you'd thus have to either: * add a count field to all the nodes (yuck, though maybe java's object overhead is enough that the extra overhead would negligible); or * add a new type of TreeMap that doesn't have constant-time count (like PersistentList vs Cons). -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
