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