Hello everybody. I think I have found a gap in the...

# stdlib

[David Gracia]

Hello everybody. I think I have found a gap in the koltin stlib and I would like to make a contribution to it. But first I would like to discuss it with you to be sure it is worthwhile. A few days ago, a student asked me for help to find an efficient algorithm in kotlin to solve this exercise https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem . After analyzing it, I realized that it is necessary to use a collection such that:
- it is mutable
- it has random/direct access (read-only)
- it keeps the elements sorted at all times (invariant)
- it can have duplicate elements

I started looking for data structures in the kotlin and java stlib and did not find any that met the requirements.

I searched stackoverflow and found this thread https://stackoverflow.com/questions/8725387/why-is-there-no-sortedlist-in-java. None of the alternatives work to solve the exercise efficiently.

So I implemented the data structure myself and solved the exercise.

Personally I think it is worthwile because the hackerrank problem seems to me to be a likely scenario in the fintech domain.

What do you think?

[elizarov]

We don’t even have SortedSet/Map in Kotlin common stdlib yet. SortedList would be the next to consider after we add them.

[elizarov]

It is not easy to cram into the design of Collections API but it is definitely useful in some narrow domains. From my experience, though, in those domains where it is needed you often need a domain-specific implementation anyway, so the value of having a generic one in stdlib is questionable.

[mcpiroman]

I needed such a collection too, but ended up just using `MutableList`with `binarySearch`and `add`with index. You can wrap it into `addToSorted`function. The only problem is you have to only ever use this function to keep the invariant.

[Astronaut4449]

I agree with not polluting stdlib. How about a kotlinx.collections library? Once implemented it is pretty low maintenance.

[elizarov]

I can also suggest you to make your own open source implementation. It does not all have to come from us.

[Astronaut4449]

Especially beginners feel more comfortable using official libraries. That's the reason a lot of CS students like Python so much. Since Kotlin is pushing to become an educational language it might be worth considering. The implementation could come from the community. The trusted kotlinx namespace is owned by Jetbrains though.

I love that Kotlin has so many official libraries (e.g. serialization and datetime).

[elizarov]

I’m sure students will appreciate learning how to write their own SortedList, not having it there out-of-the-box. As for solving hacker rank problems, it is not something that we consider a bonus during language and library design. Having said that, we’ll definitely consider it after we have infrastructure for pure-Kotlin implementations of SortedSet/Map.

[Astronaut4449]

👍

[David Gracia]

Do you consider the possibility of the community contributing to the advancement of this part of the stdlib, or do you prefer the JB team to take care of it? If it is the first case, maybe I will start to make an opensource implementation as you propose and maybe one day you will consider to include it in the stdlib.

[elizarov]

That’s the way to go. Open source library with implementation is a great way to contribute.

[jimn]

iinm there is groupby which is more or less ranked iterators, no? it has everything a non-library needs to get the job done and possibly add some job security along the way