Class TreeMap<K,V> | Lower and Upper Count Support

[mayank bansal]

Hi Remi,

I raised a PR for improving the complexity of size() method of HeadMap/
TailMap https://github.com/openjdk/jdk/pull/1255 .
I am getting jcheck failed exception because of wrong commit message as it
is not yet assigned to any issue id. Could you please help here ?
Thanks.

On Sun, Nov 8, 2020 at 5:38 PM <forax at univ-mlv.fr> wrote:

>
>
> ------------------------------
>
> *De: *"mayank bansal" <mayankbansal933 at gmail.com>
> *À: *"Remi Forax" <forax at univ-mlv.fr>
> *Cc: *"core-libs-dev" <core-libs-dev at openjdk.java.net>
> *Envoyé: *Dimanche 8 Novembre 2020 12:55:09
> *Objet: *Re: Class TreeMap<K,V> | Lower and Upper Count Support
>
> Hi Remi,
> Thank you for pointing that out. This is providing the same feature but it
> is not the optimal approach for calculating the size.
>
> AscendingSubMap().size() is actually iterating each and every element
> using Iterator to calculate the size resulting in the O(N) time complexity
> which can be reduced to O(logN) and this will be a huge improvement. Code
> snippet for the reference -
> https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/TreeMap.java#L1937-L1950
>
> I am coming from the fact that I was trying to solve one coding problem, I
> tried using own Balanced BST
> <https://leetcode.com/submissions/detail/418028305/> (AVL tree) and it
> executed in ~180ms and when I tried using TreeSet headSet().size()
> <https://leetcode.com/submissions/detail/418070375/>, it resulted in a
> TLE - Time Limit Exceeded.
>
>
> Interesting, I've always though that all collections of java.util had a
> size() implementation in O(1).
> It may be worth fixing this if there is a simple fix.
>
> One issue with TreeMap is that unlike most of the other implementations,
> TreeMap is not used a lot so we are still discovering issues.
>
> Rémi
>
>
>
>
> On Sun, Nov 8, 2020 at 4:09 PM Remi Forax <forax at univ-mlv.fr> wrote:
>
>> Is it different from
>>  headMap(key, true).size() / tailMap(key, true).size() ?
>>
>>
>> https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/NavigableMap.html#headMap(K,boolean)
>>
>> https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/NavigableMap.html#tailMap(K,boolean)
>>
>> cheers,
>> Rémi
>>
>> ----- Mail original -----
>> > De: "mayank bansal" <mayankbansal933 at gmail.com>
>> > À: "core-libs-dev" <core-libs-dev at openjdk.java.net>
>> > Envoyé: Dimanche 8 Novembre 2020 11:22:01
>> > Objet: Class TreeMap<K,V> | Lower and Upper Count Support
>>
>> > Hi Everyone,
>> >
>> > I would like to propose and work on a feature request of supporting the
>> > lower and higher count in java class TreeMap.
>> > "lower count" is the number of elements that are strictly less than the
>> > given value.
>> > "upper count" is the number of elements that are strictly greater than
>> the
>> > given value.
>> >
>> > *Method definitions-*
>> > int getLowerCount(K key);
>> > int getHigherCount(K key);
>> >
>> > *Follow-up feature -*
>> > Class TreeSet<E> constructor initializes the TreeMap<K,V> in the TreeSet
>> > constructor.
>> > It puts the dummy value as *new Object()* whenever we add the entry in
>> > TreeSet.
>> > I would like to work on the feature to provide the *Duplicate count* in
>> > case of the same Key and the same Value.
>> >
>> > I will be happy to work on both and raise a PR. I need some guidance if
>> the
>> > proposed feature looks good and I can start working on it and also would
>> > like to know about the process whether I can directly raise the PR.
>> >
>> > Thanks
>> > --
>> > Regards,
>> > Mayank Bansal
>>
>
>
> --
> Regards,
> Mayank Bansal
>
>

-- 
Regards,
Mayank Bansal