2

I am trying to search for a collection type that have the following properties:

  • Maintain insertion order
  • Don't allow duplicates
  • Add one or more elements after another

I could create my own data collection but I wish not to.

After taking a look at all collections available in kotlin I think LinkedHashSet have almost all of my requirements, however it can't add elements after another or at nth position.

Is there any way to accomplish this with an extension method or any another trick?

Exprove
  • 1,301
  • 2
  • 18
  • 32
  • Seems like you'd have better luck with a `List` where you check if it `contains` an element before adding it. A `LinkedHashSet` maintains insertion order but, since it's a `Set`, it doesn't support positional insertions. – Slaw May 10 '19 at 10:47
  • @Slaw Calling `contains` O(n) on each added element seems expensive, that's why a `HashSet` its a better idea. – Exprove May 10 '19 at 11:29
  • 1
    Yes, it will be more expensive, but I don't believe there's any `Set` implementations in the JDK that do what you want. Another option is to use both a `Set` and a `List` at the same time, as mentioned in [this answer](https://stackoverflow.com/a/8185105/6395627). There's also [`ListOrderedSet`](https://commons.apache.org/proper/commons-collections/javadocs/api-4.3/org/apache/commons/collections4/set/ListOrderedSet.html) from Apache Common Collections. – Slaw May 10 '19 at 11:40
  • Related question: [Is there an insertion order preserving `Set` that also implements `List`](https://stackoverflow.com/questions/8185090/is-there-an-insertion-order-preserving-set-that-also-implements-list) – Roland May 10 '19 at 11:41
  • @Roland `LinkedHashSet` in Kotlin has some extensions methods which aren't present in Java. I though those extensions or even some Kotlin caveats could resolve any of those issues. – Exprove May 10 '19 at 11:47
  • @Exprove I know... you mean the `Iterable`-extension functions? It seems clear that this will not work with `LinkedHashSet` alone... `LinkedHashSet` retains the order of insertion... so it would be against its nature to add an element before any other... (i.e. violating the "order of insertion") – Roland May 10 '19 at 11:57
  • @Roland `ArrayList` also retains the order of insertion and it lets me to add in some arbitrary position. At least this is the behavior I am expecting in this question. – Exprove May 10 '19 at 12:04
  • 1
    Think of extension functions as a better way to create so-called "utility" classes. They don't usually have any access to the internals of a class, they simply add _behavior_. `LinkedHashSet` does not expose any way to insert an element at an arbitrary point; an extension function can't help you here. – Slaw May 10 '19 at 12:05
  • @Exprove [`ArrayList`](https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/util/ArrayList.html) however doesn't state anything in the documentation regarding the insertion order (actually I only see *"in proper sequence"* regarding order)... [`LinkedHashSet`](https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/util/LinkedHashSet.html) on the contrary states it explicitly: *"the order in which elements were inserted into the set"* – Roland May 10 '19 at 15:56
  • if `ArrayList` is suitable for you, that's fine... I just wanted to say that `LinkedHashSet` will not going to help due to how it is implemented and also described in the documentation... – Roland May 10 '19 at 15:59
  • could you tell what you want to accomplish with the following: "Add one or more elements after another"... I mean: `LinkedHashSet` supports the first 2 requirements... and `ArrayList` supports the first and the last... and you could surely implement your own collection type supporting all 3... but I wonder what the use case is to insert things somewhere in between for a `Set`. Maybe I have an idea then ;-) – Roland May 10 '19 at 16:22

3 Answers3

0

You can just use List<> or any of its implementations. Its maintain insertion order, you can add one or more elements after another, and you can accomplish the "avoid duplicates" requirement by calling .distinct() when returning your list. i.e:

private fun fillData(): MutableList<String> {
    var dataSet: MutableList<String> = ArrayList()
    for (i in 0..10) dataSet.add("Product $i")
    dataSet.add("aaa")
    dataSet.add("aaa")
    dataSet.add("aaa")
    dataSet.add("aaa")
    dataSet.add("aaa")
    return dataSet.distinct().toMutableList()
}

The result of this function returns an array with 11 elements, "Product 1".. "Product 10" and just 1 "aaa" element at the end.

you can see the doc of List.distinct() here

Jonathan Aste
  • 1,764
  • 1
  • 13
  • 20
  • 1
    While that may give the results you require, it doesn't reflect the collection type that doesn't allow duplicates... – Roland May 10 '19 at 16:19
  • The real solution is to implement a custom List overriding add methods but as @Exprove stated, "I could create my own data collection but I wish not to.". So this is a functional workarround, – Jonathan Aste May 10 '19 at 17:09
  • If that's the real solution, why don't you state it that way? And actually there do exist such collection types.. but not in the standard library* as it seems.. – Roland May 10 '19 at 19:25
0

In the standard library (& Java collection API) there isn't such a collection type as far as I know.

Apache commons collections however contains what you are looking for: ListOrderedSet

Roland
  • 22,259
  • 4
  • 57
  • 84
0

Why not implement a custom data structure that exactly serve your requirements?

class OrderedHashSet<E> : MutableSet<E>{

    private val set = HashSet<E>()
    private val list = LinkedList<E>()

    override val size: Int
        get() = list.size

    override fun contains(element: E) = set.contains(element)

    override fun containsAll(elements: Collection<E>) = set.containsAll(elements)

    override fun isEmpty() = list.isEmpty()

    override fun iterator() = list.iterator()

    override fun add(element: E): Boolean {
        if(set.add(element)){
            list.add(element)
            return true
        }
        return false
    }

    fun add(index: Int, element: E) : Boolean {
        if(set.add(element)){
            list.add(index, element)
            return true
        }
        return false
    }

    override fun addAll(elements: Collection<E>): Boolean {
        var modified = false
        for(element in elements){
            if(add(element)){
                modified = true
            }
        }
        return modified
    }

    override fun clear() {
        set.clear()
        list.clear()
    }

    override fun remove(element: E): Boolean {
        set.remove(element)
        return list.remove(element)
    }

    override fun removeAll(elements: Collection<E>): Boolean {
        var modified = false
        for(element in elements){
            if(remove(element)){
                modified = true
            }
        }
        return modified
    }

    override fun retainAll(elements: Collection<E>): Boolean {
        set.retainAll(elements)
        return list.retainAll(elements)
    }

}
birneee
  • 623
  • 4
  • 10