Hi David,
data.avl trees and maps offer navigable map / set functionality out of the
box (with a Clojure API – as mentioned in my comment on CLJ-1008,
implementing the "reverse" methods would be straightforward in itself, but
problematic due to interactions with other functionality I'd like to have
the option to implement; I might eventually come up with a clean way of
making it all work together, but for now I'd like to keep my options open):
(avl/subrange (avl/sorted-set 0 1 2 3 4 5) >= 2 < 5)
;= #{2 3 4}
Adding them to PTM would be quite a bit trickier, because PTM doesn't store
rank metadata in nodes, and so after extracting a subrange from a PTM
instance we have no good answer to c.c/count, unless of course we're
willing to walk the entire subrange (but at this point it's simpler to just
combine (r)subseq with into to produce a new map; in fact there is a
function like this in data.avl's test suite for use as a sanity check on
the fast implementation – as you'd expect, it's *very* slow, whereas
data.avl/subrange is fast – O(log n) – and gives you first-class results
with O(1) count).
As I said in CLJ-1008, I'm not convinced we should change that – as of
right now, we have in Clojure a lean sorted map (c.l.PTM with basic sorted
map / set functionality) and a more feature-rich sorted map (data.avl –
extra features, fatter nodes). Making c.l.PTM nodes fatter would remove the
lean & basic option, so we should only do it if there's a compelling
reason. Given data.avl's performance – totally on a par with c.l.PTM
(sometimes faster, largely due to AVL trees being shallower, sometimes
slower where they do a measurable amount of extra work) – I'm not sure
there really is a compelling reason. Do you feel otherwise?
(I can see other "feature packages" being useful for various use cases…
I've been thinking about how best to support them without reimplementing
too much of the basic stuff.)
Going back to the original question, data.avl trees and maps make no
attempt to hide the internal structure of their nodes (although you'll have
to access the fields through clojure.data.avl.IAVLNode method calls and not
direct field access; the fields need to be mutable for data.avl to support
transients, and deftype-introduced mutable fields are always private):
;; reflection removable with appropriate hints
(.. (avl/sorted-set 0 0 1 1 2 2 3 3 4 4) (getTree) (getLeft))
;= #<AVLNode clojure.data.avl.AVLNode@25c3b70f>
As for interval trees, that's one data structure that I've been meaning to
add to data.avl for a long time, and I'm fairly close to releasing a first
cut. Currently I'm aiming at sets of intervals with some overlap queries
("find intervals overlapping this one", "find intervals which include this
point"). I'm not planning to support all data.avl features for interval
sets in the initial alpha – the purpose of that will be to hash out a good
API for the new stuff – but I'll be happy to add in whatever makes sense in
a future release. (In particular, map-like interval trees in which you
could associate values with the stored intervals are a possibility.)
In any case, whatever your use case is, I'd be very interested to learn
more about it and see if data.avl could provide a useful solution.
Cheers,
Michał
On 19 February 2015 at 23:12, David James <davidcja...@gmail.com> wrote:
> Yes, we're on the same page here. I'm very glad Michał has done great work
> in this Clojure data structure space.
>
> Of course, I wouldn't mind if dozens of people agreed, but I'm more
> interested in the pros/cons before I try to mobilize support. So, to those
> reading this, I'd be interested to hear if:
>
> (a) you agree with CLJ-1008 (or some friendly amendment to it)
> (b) you disagree with CLJ-1008 for some principled or philosophical reason
> (not just because you think other things are more pressing or you wouldn't
> personally use a a RB-Tree API right away)
> (c) you think more exploration is needed
>
> Some observations and context:
>
> * I find it curious that `tree` is public but `left` and `right` are not.
> Perhaps this was just historical accident?
>
> * Exposing the API for PersistentTreeMaps opens up a lot of useful
> possibilities for derivative data structures. (This is what led me to this
> question.) See, for example, interval trees, in particular ones with
> non-overlapping intervals: http://en.wikipedia.org/wiki/Interval_tree,
> which could be naively implemented with a PersistentTreeMap if it had
> public API access.
>
> On Thursday, February 19, 2015 at 3:37:46 PM UTC-5, Andy Fingerhut wrote:
>>
>> David:
>>
>> I see why you would want that.
>>
>> If you want this soon, I would recommend using data.avl as suggested by
>> Michał,
>> or copy the parts of the sorted-set/map implementation from Clojure and
>> implement it yourself.
>>
>> If you don't want it soon, you could try persuading a few dozen people to
>> vote on CLJ-1008, and hope the Clojure developers also want this change.
>> No guarantees there.
>>
>> Andy
>>
>> On Thu, Feb 19, 2015 at 12:18 PM, David James <david...@gmail.com> wrote:
>>
>>> Andy, to take advantage of the Red-Black Tree, I'm looking for public
>>> API access to the branches. (I'm not looking for a work-around.)
>>>
>>> More discussion on this at SO: http://stackoverflow.com/
>>> questions/1981859/finding-keys-closest-to-a-given-value-
>>> for-clojure-sorted-maps
>>>
>>> Thanks to both Michał Marczyk and Andy for commenting on CLJ-1008 (
>>> http://dev.clojure.org/jira/browse/CLJ-1008).
>>>
>>> On Thursday, February 19, 2015 at 1:02:53 PM UTC-5, Andy Fingerhut wrote:
>>>>
>>>> I haven't checked carefully, but from at least a quick look it appears
>>>> that implementing the NavigableMap and NavigableSet interfaces could be
>>>> done by using the existing subseq and rsubseq functions in clojure.core?
>>>>
>>>> It doesn't give you access to subtree nodes directly, but perhaps it is
>>>> sufficient for your purposes?
>>>>
>>>> Andy
>>>>
>>>> On Wed, Feb 18, 2015 at 6:04 PM, David James <david...@gmail.com>
>>>> wrote:
>>>>
>>>>> Summary: I'd like to find a public API to work with the underlying
>>>>> tree of a sorted-map.
>>>>>
>>>>> For example:
>>>>>
>>>>> (def t (sorted-map 1 :a 2 :b 3 :c 4 :d 5 :e 6 :f))
>>>>>
>>>>> The underlying implementation of sorted-map uses a PersistentTreeMap,
>>>>> which can be accessed with `tree`:
>>>>>
>>>>> (.tree t) ;=> [2 :b]
>>>>>
>>>>> I have not found a way to access the left and right branches, since
>>>>> calling `left` fails:
>>>>>
>>>>> (.left (.tree t))
>>>>>
>>>>> IllegalArgumentException Can't call public method of non-public class:
>>>>> public clojure.lang.PersistentTreeMap$Node clojure.lang.
>>>>> PersistentTreeMap$BlackBranch.left()
>>>>> clojure.lang.Reflector.invokeMatchingMethod
>>>>> (Reflector.java:88)
>>>>>
>>>>> Perhaps it would be reasonable to make such calls possible, at least
>>>>> from the Java API (without reflection)?
>>>>>
>>>>> CLJ-1008 (http://dev.clojure.org/jira/browse/CLJ-1008) offers one
>>>>> possible way to support a public API. It was created in 2012. Perhaps it
>>>>> could use another look. Thoughts?
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Clojure" group.
>>>>> To post to this group, send email to clo...@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+u...@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+u...@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 clo...@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+u...@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+u...@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.
>
--
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.
