[jira] [Created] (COLLECTIONS-672) There are no List collestion with optimized indexOf method.

["Aleksandr Maksymenko (JIRA)" <ji...@apache.org>]

Aleksandr Maksymenko created COLLECTIONS-672:
------------------------------------------------

             Summary: There are no List collestion with optimized indexOf method.
                 Key: COLLECTIONS-672
                 URL: https://issues.apache.org/jira/browse/COLLECTIONS-672
             Project: Commons Collections
          Issue Type: Improvement
          Components: Collection
            Reporter: Aleksandr Maksymenko


All known implementations of List are all have O(n) for indexOf() operation.

Here is my implementation of such List on github which has O(log n) for indexOf() and contains():
[https://github.com/masyamandev/indexable-set]

There are two modifications: one implements both List and Set, so it can contains unique elements, second modification can contains any amount of unique objects, but it's a bit slower.

It's based on TreeList and provide complexity:
 * get by index is O(log n)
 * insertion, removing (both by index or by value) are O((log n) * (1 + log m)) where is amount of elements equals to inserted/removed element.
 * insertion, removing are O(log n) if all elements are unique.
 * indexOf and lastIndexOf are O(log n).
 * contains is O(1) or (log n) depending on Map implementation.

As those collections have complexity similar to TreeSet (at least in cases of unique elements), overall performance is 20-30% slower due to element indexing and eliminating some optimizations. However it provides fast indexOf and contains.

Can I help in porting my code to Apache common Collections library?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)