Re: Accessing branches in PersistentTreeMap / sorted-map / CLJ-1008
PS. Well, I suppose you'd want to make sure that you're not getting a key
that lies past the right endpoint of the map when using the nearest-based
approach.
On 20 February 2015 at 16:39, Michał Marczyk michal.marc...@gmail.com
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 davidcja...@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.
Re: Accessing branches in PersistentTreeMap / sorted-map / CLJ-1008
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.
Re: Accessing branches in PersistentTreeMap / sorted-map / CLJ-1008
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 davidcja...@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.
Re: Accessing branches in PersistentTreeMap / sorted-map / CLJ-1008
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
javascript: 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.
Re: Accessing branches in PersistentTreeMap / sorted-map / CLJ-1008
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 ])
(/-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 (/-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 (/-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 (/-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 (/-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.
Re: Accessing branches in PersistentTreeMap / sorted-map / CLJ-1008
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 javascript: 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 javascript: 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 javascript: 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 javascript:. 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.
Re: Accessing branches in PersistentTreeMap / sorted-map / CLJ-1008
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 davidcja...@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 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.
Re: Accessing branches in PersistentTreeMap / sorted-map / CLJ-1008
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 javascript: 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 javascript: 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 javascript: 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 javascript:. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are
Re: Accessing branches in PersistentTreeMap / sorted-map / CLJ-1008
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
Re: Accessing branches in PersistentTreeMap / sorted-map / CLJ-1008
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 davidcja...@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 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.
