You don't need left and right, you can literally use a sorted map / PTM
that looks like {0 :a 3 :a …} as your representation and build a wrapper to
query it appropriately using functions like avl/nearest, but implemented
using first/(r)(sub)seq.Here's a prototype: https://github.com/michalmarczyk/ticktickticktock (require '[ticktickticktock.core :as tttt]) (tttt/tttt-map 0 :a 1 :a 2 :a 3 :a 4 :b 5 :b 6 :c 7 :c 8 :c 9 :c) ;= {0 :a, 3 :a, 4 :b, 5 :b, 6 :c, 9 :c} ;; the above is a wrapper around a sorted map Some interactions: user=> (get (tttt/tttt-map 0 :a 1 :a 2 :a 3 :a 4 :b 5 :b 6 :c 7 :c 8 :c 9 :c) -1) nil user=> (get (tttt/tttt-map 0 :a 1 :a 2 :a 3 :a 4 :b 5 :b 6 :c 7 :c 8 :c 9 :c) 0) :a user=> (get (tttt/tttt-map 0 :a 1 :a 2 :a 3 :a 4 :b 5 :b 6 :c 7 :c 8 :c 9 :c) 1) :a user=> (get (tttt/tttt-map 0 :a 1 :a 2 :a 3 :a 4 :b 5 :b 6 :c 7 :c 8 :c 9 :c) 8) :c NB. this really is a prototype – it supports only the what's strictly necessary for the above demo to work – but it should be fairly straightforward to extend it to support other desirable features. (For example assoc elsewhere than beyond the rightmost key etc. dissoc of single values doesn't really make sense here, but I suppose "inserting a gap" would.) Also, I don't think it handles lookups "in between intervals" very well… That's fixable as well. I guess the first thing to fix would be the lack of a clear target API design. :-) Cheers, Michał On 20 February 2015 at 20:09, David James <davidcja...@gmail.com> wrote: > Yes, exactly, you read my mind. > > (I'd also like to do this a sorted-map / PersistentTreeMap (nudge, nudge) > -- all that is missing would be public 'left' and 'right' accessors. I > don't necessarily need rank functionality.) > > On Friday, February 20, 2015 at 10:39:26 AM UTC-5, Michał Marczyk wrote: >> >> Do you mean you'd like to compress >> >> {0 :a 1 :a 2 :a 3 :a 4 :b 5 :b 6 :c 7 :c 8 :c 9 :c} >> >> to something like >> >> {[0 1 2] :a [4 5] :b [6 7 8 9] :c} >> >> while maintaining the ability to ask for the value at 0, 1, …, 9? >> >> If so, you could represent the above as >> >> {0 :a 2 :a 4 :b 5 :b 6 :c 9 :c} >> >> (notice no explicit entries for 1, 7, 8) and query for the value at 7, >> say, using >> >> (val (avl/nearest the-map <= 7)) >> ;= :c >> >> (avl/nearest can be implemented for built-in sorted maps using subseq and >> first, in fact the test suite for data.avl has an implementation like that >> that it compares avl/nearest against). >> >> If you need more operations – say, data.avl-style slice-{at,key} and >> subrange – those could be supported with some care (mostly around the >> possibility that a slice, say, removes an endpoint of an interval – you may >> need to add the slice boundary as a replacement in that case). >> >> Cheers, >> Michał >> >> >> On 20 February 2015 at 16:15, David James <david...@gmail.com> wrote: >> >>> Thanks for your comments. I see now that I should clarify: all I really >>> need is public access to the left and right Java methods in PTM. (So, >>> perhaps CLJ-1008 is asking for more than I really need.) >>> >>> It seems to me that since Clojure's RB-Tree implementation (i.e. >>> sorted-map = PTM), it might as well expose a Java API for root node (which >>> it does) and branches (which is does not, currently). Is there any downside >>> to exposing the 'right' and 'left' Java methods as public? >>> >>> In the near term, I'll be using data.avl. I'm glad it exists! My use >>> case involves a non-overlapping interval map to store time series data that >>> doesn't change very often. >>> >> -- > 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 > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
