Ordered Sets


#1

Hey folks,

The Java collections frameworks, frustratingly, lacks any interface that indicates “an ordered collection of unique elements”, and Kotlin doesn’t step in and provide an interface/class either. So…I’m curious what people in the Kotlin community have been doing instead, when it’s important to convey to the consumers of an API that the returned collection contains only distinct values, in a deliberate iteration order, and those properties are of equal importance.

Some possibilities I can think of:

  1. Return a list and document the distinct values property.
  2. Return a set and document the iteration order. (this is what Kotlin does with .toSet())
  3. Return a LinkedHashSet, even though it’s a concrete class and mutable (and not the Set interface that .toSet() returns)
  4. Implement a custom wrapper class, like class OrderedSet<T>(inner: Set<T>) : Set<T> by inner.

What do you recommend and why?

Thanks!
Max


#3

He means the interface equivalent of a LinkedHashSet, not of a TreeSet…


#4

Ah, yes, ordered != sorted, at least in this case. Sorry for the confusion.


#5

For now we’re going to experiment with this:

/**
 * Identical to [Set], but indicates that the iteration order is meaningful.
 */
typealias OrderedSet<E> = Set<E>

/**
 * Identical to [MutableSet], but indicates that the iteration order is meaningful.
 */
typealias OrderedMutableSet<E> = MutableSet<E> // Usually LinkedHashSet

It doesn’t confer type safety, but it does convey intent.


#6

As for the implements right now, all the toSet, setOf and mutableSetOf are all implemented with LinkedHashSet.
Kotlin provides the function of linkedSetOf to explicitly create a LinkedHashSet.

/**
 * Returns a new [LinkedHashSet] with the given elements.
 * Elements of the set are iterated in the order they were specified.
 */
public fun <T> linkedSetOf(vararg elements: T): LinkedHashSet<T> = elements.toCollection(LinkedHashSet(mapCapacity(elements.size)))