Implement Insertion Ordered Set implementing MutableSet API.

[donraab]

Today a LinkedHashSet can be used by wrapping a JDK LinkedHashSet with a SetAdapter as follows.

Sets.adapt(new LinkedHashSet());

This works fine for most cases but it would be nicer if we provided an Ordered Set implementation that returned more specific values out of certain methods.

[oehme]

I think the title should be "implement insertion ordered set". Using a linked structure is the reason for the huge memory overhead of LinkedHashSet. Using a long[] to maintain the iteration order would be much more efficient. But maybe I'm missing a different reason why a linked structure might be useful?

[donraab]

Makes sense. Updated. I'll leave implementation detail up to the developer who contributes.

[motlin]

A removal from the middle of an IntList would turn Set.remove() into a linear time operation, at least with the naive/obvious implementation. In fact, any removal is complicated.

…

On Sat, Dec 9, 2017 at 4:09 PM Stefan Oehme ***@***.***> wrote: I think the title should be "implement insertion ordered set". Using a linked structure is the reason for the huge memory overhead of LinkedHashSet. Using an IntList to maintain the iteration order would be much more efficient. But maybe I'm missing a different reason why a linked structure might be useful? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#339 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAO6IsoTTxbm1ShQDdira-tkCoUVHsVAks5s-vcJgaJpZM4PKxdO> .

[oehme]

I corrected my comment above - I meant keeping the links in a long[], storing the previous pointer in the lower half and the next pointer in the upper half of each long and indexing it with the same indexes as the main table. That gives you a compact link representation and constant time removals.

[arvidvillen]

Any updates in this?
Surely ImmutableOrderedSet would be one of the most used collections in a regular project as the ordering should/could be done in DB query.

[nikhilnanivadekar]

@arvidvillen what updates would you like? If you need this functionality, please feel free to contribute.

[mohrezaei]

@arvidvillen The most used collection for representing results coming from a database is a simple list. It's naturally ordered, random access and has a superior interface compared to a set.

[arvidvillen]

Thanks for super fast replies.
Interesting, I guess I'm not really thinking of it from a performance point of view, but rather the semantic meaning (what the interface tells the user about the collection). ImmutableOrderedSet would tell me more as a consumer of an API than ImmutableSet or ImmutableList.

But I understand not many people see it that way as there are very few collection libraries that support OrderedSet or UniqueList.