[
https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
