[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15148762#comment-15148762 ] Rodion Efremov commented on COLLECTIONS-479: I am more or less done with a Set-implementation that provides methods get(int index) and indexOf(T element); both run in O(log N). See here: https://github.com/coderodde/OrderStatisticTree However, if a Map is required, please tell me, should not take much time to refactor. Best, rodde > An Order Statistic Tree > --- > > Key: COLLECTIONS-479 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 > Project: Commons Collections > Issue Type: New Feature >Reporter: Ajo Fod >Priority: Minor > Fix For: 4.x > > Attachments: COLLECTIONS-479.patch, NodeExistsException.java, > RedBlackBST.java > > > An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree > provides two useful properties. The ability to rank arbitrary keys relative > to keys existing in the tree AND the ability to retrieve elements from the > tree with the given rank. > This can be used to find the percentile rank of a key for example. > This functionality is not yet provided yet by any of the major libraries > AFAIK. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15143246#comment-15143246 ] Rodion Efremov commented on COLLECTIONS-479: Hello everybody! I wasn't able to work on this one after all. However, I started today from scratch and have a progress on counted AVL-tree: insert, lookup and deletion implemented. Just lacks the actual counts needed for making it an order statistic tree. Question: what interfaces should I implement? java.util.Set seems like natural choice, but there might be more. What would be your opinion on this one? > An Order Statistic Tree > --- > > Key: COLLECTIONS-479 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 > Project: Commons Collections > Issue Type: New Feature >Reporter: Ajo Fod >Priority: Minor > Fix For: 4.x > > Attachments: COLLECTIONS-479.patch, NodeExistsException.java, > RedBlackBST.java > > > An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree > provides two useful properties. The ability to rank arbitrary keys relative > to keys existing in the tree AND the ability to retrieve elements from the > tree with the given rank. > This can be used to find the percentile rank of a key for example. > This functionality is not yet provided yet by any of the major libraries > AFAIK. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14577892#comment-14577892 ] Thomas Neidhart commented on COLLECTIONS-479: - Looking through some old issue, COLLECTIONS-181 talks about the same problem but proposes another solution. From the referenced issue, I like the proposed interface: IndexedSortedMap. In total there are 4 approaches proposed: * create a concrete class with a sorted array as backing data structure * create a decorator with a sorted list as backing data structure * create a concrete class with a counted red-black tree * create a concrete class with an counted AVL tree An Order Statistic Tree --- Key: COLLECTIONS-479 URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 Project: Commons Collections Issue Type: New Feature Reporter: Ajo Fod Priority: Minor Fix For: 4.x Attachments: COLLECTIONS-479.patch, NodeExistsException.java, RedBlackBST.java An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree provides two useful properties. The ability to rank arbitrary keys relative to keys existing in the tree AND the ability to retrieve elements from the tree with the given rank. This can be used to find the percentile rank of a key for example. This functionality is not yet provided yet by any of the major libraries AFAIK. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13854155#comment-13854155 ] Rodion Efremov commented on COLLECTIONS-479: Hello, y'all! Might the ordered statistic tree look anything like [this|https://github.com/coderodde/cskit/blob/master/src/main/java/net/coderodde/cskit/ds/tree/OrderStatisticTree.java]? Rodde An Order Statistic Tree --- Key: COLLECTIONS-479 URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 Project: Commons Collections Issue Type: New Feature Reporter: Ajo Fod Priority: Minor Attachments: NodeExistsException.java, RedBlackBST.java An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree provides two useful properties. The ability to rank arbitrary keys relative to keys existing in the tree AND the ability to retrieve elements from the tree with the given rank. This can be used to find the percentile rank of a key for example. This functionality is not yet provided yet by any of the major libraries AFAIK. -- This message was sent by Atlassian JIRA (v6.1.4#6159)
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13854200#comment-13854200 ] Ajo Fod commented on COLLECTIONS-479: - Yes, that looks right. -Ajo An Order Statistic Tree --- Key: COLLECTIONS-479 URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 Project: Commons Collections Issue Type: New Feature Reporter: Ajo Fod Priority: Minor Attachments: NodeExistsException.java, RedBlackBST.java An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree provides two useful properties. The ability to rank arbitrary keys relative to keys existing in the tree AND the ability to retrieve elements from the tree with the given rank. This can be used to find the percentile rank of a key for example. This functionality is not yet provided yet by any of the major libraries AFAIK. -- This message was sent by Atlassian JIRA (v6.1.4#6159)
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[
https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13854440#comment-13854440
]
Rodion Efremov commented on COLLECTIONS-479:
What package should I put it in? Might
'{{org.apache.commons.collections4.map}}' be the right place?
An Order Statistic Tree
---
Key: COLLECTIONS-479
URL: https://issues.apache.org/jira/browse/COLLECTIONS-479
Project: Commons Collections
Issue Type: New Feature
Reporter: Ajo Fod
Priority: Minor
Attachments: NodeExistsException.java, RedBlackBST.java
An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree
provides two useful properties. The ability to rank arbitrary keys relative
to keys existing in the tree AND the ability to retrieve elements from the
tree with the given rank.
This can be used to find the percentile rank of a key for example.
This functionality is not yet provided yet by any of the major libraries
AFAIK.
--
This message was sent by Atlassian JIRA
(v6.1.4#6159)
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13761740#comment-13761740 ] Rodion Efremov commented on COLLECTIONS-479: Hello, Thomas. Could you assign me to this issue? I just might come up with the implementation in a week or so. An Order Statistic Tree --- Key: COLLECTIONS-479 URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 Project: Commons Collections Issue Type: New Feature Reporter: Ajo Fod Priority: Minor Attachments: NodeExistsException.java, RedBlackBST.java An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree provides two useful properties. The ability to rank arbitrary keys relative to keys existing in the tree AND the ability to retrieve elements from the tree with the given rank. This can be used to find the percentile rank of a key for example. This functionality is not yet provided yet by any of the major libraries AFAIK. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13762153#comment-13762153 ] Thomas Neidhart commented on COLLECTIONS-479: - Hi Rodion, thanks for your interest. There is no need to assign issues to somebody in general, but it would be great if you are interesting in working on it and provide a patch! Thomas An Order Statistic Tree --- Key: COLLECTIONS-479 URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 Project: Commons Collections Issue Type: New Feature Reporter: Ajo Fod Priority: Minor Attachments: NodeExistsException.java, RedBlackBST.java An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree provides two useful properties. The ability to rank arbitrary keys relative to keys existing in the tree AND the ability to retrieve elements from the tree with the given rank. This can be used to find the percentile rank of a key for example. This functionality is not yet provided yet by any of the major libraries AFAIK. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13708980#comment-13708980 ] Thomas Neidhart commented on COLLECTIONS-479: - Thanks for the suggestion and the patch. Ideally, the new class should be embedded into an existing collection type and in this case I guess a Set would be appropriate. To include a new feature into collections we would also need unit tests that fit into the test framework. Looking at the proposed feature itself, I think it could be solved by using the already existing TreeList. We just need a method to find the insertion point by traversing the tree in sort order. The corresponding index is stored in the AVLTree nodes, which is then used to provide the select / rank functionality: * select(index) = get(index) * rank(obj) = indexOf(obj) An Order Statistic Tree --- Key: COLLECTIONS-479 URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 Project: Commons Collections Issue Type: New Feature Reporter: Ajo Fod Priority: Minor Attachments: NodeExistsException.java, RedBlackBST.java An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree provides two useful properties. The ability to rank arbitrary keys relative to keys existing in the tree AND the ability to retrieve elements from the tree with the given rank. This can be used to find the percentile rank of a key for example. This functionality is not yet provided yet by any of the major libraries AFAIK. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
