Any implementation of Ordered Set in Java

Question

If anybody is familiar with Objective-C there is a collection called NSOrderedSet that acts as Set and its items can be accessed as an Array s ones   Is there anything like this in Java   I ve heard there is a collection called LinkedHashMap  but I haven t found anything like it for a set

User · Answer

If we are talking about inexpensive implementation of the skip-list, I wonder in term of big O, what the cost of this operation is:

YourType[] array = someSet.toArray(new YourType[yourSet.size()]);

I mean it is always get stuck into a whole array creation, so it is O(n):

java.util.Arrays#copyOf

User · Answer

Take a look at LinkedHashSet class  From Java doc    Hash table and linked list implementation of the Set interface  with predictable iteration order  This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries  This linked list defines the iteration ordering  which is the order in which elements were inserted into the set  insertion-order   Note that insertion order is not affected if an element is re-inserted into the set   An element e is reinserted into a set s if s add e  is invoked when s contains e  would return true immediately prior to the invocation

User · Answer

treeset is an ordered set  but you can t access via an items index  just iterate through or go to beginning end

User · Answer

You might also get some utility out of a Bidirectional Map like the BiMap from Google Guava  With a BiMap  you can pretty efficiently map an Integer  for random index access  to any other object type  BiMaps are one-to-one  so any given integer has  at most  one element associated with it  and any element has one associated integer  It s cleverly underpinned by two HashTable instances  so it uses almost double the memory  but it s a lot more efficient than a custom List as far as processing because contains    which gets called when an item is added to check if it already exists  is a constant-time and parallel-friendly operation like HashSet s  while List s implementation is a LOT slower

User · Answer

Every Set has an iterator    A normal HashSet s iterator is quite random  a TreeSet does it by sort order  a LinkedHashSet iterator iterates by insert order   You can t replace an element in a LinkedHashSet  however  You can remove one and add another  but the new element will not be in the place of the original  In a LinkedHashMap  you can replace a value for an existing key  and then the values will still be in the original order   Also  you can t insert at a certain position   Maybe you d better use an ArrayList with an explicit check to avoid inserting duplicates

User · Answer

I had a similar problem  I didn t quite need an ordered set but more a list with a fast indexOf contains  As I didn t find anything out there I implemented one myself  Here s the code  it implements both Set and List  though not all bulk list operations are as fast as the ArrayList versions   disclaimer  not tested  import java util ArrayList  import java util HashMap  import java util Set  import java util Collection  import java util Comparator  import java util function Predicate  import java util function UnaryOperator  import static java util Objects requireNonNull          An ArrayList that keeps an index of its content so that contains   indexOf   are fast  Duplicate entries are    ignored as most other java Set s do      public class IndexedArraySet lt E gt  extends ArrayList lt E gt  implements Set lt E gt         public IndexedArraySet     super           public IndexedArraySet Iterable lt E gt  c            super            addAll c              private HashMap lt E  Integer gt  indexMap   new HashMap lt  gt          private void reindex             indexMap clear            int idx   0          for  E item  this                addToIndex item  idx                          private E addToIndex E e  int idx            indexMap putIfAbsent requireNonNull e   idx           return e              Override     public boolean add E e            if indexMap putIfAbsent requireNonNull e   size       null  return false          super add e           return true              Override     public boolean addAll Collection lt   extends E gt  c            return addAll  Iterable lt   extends E gt   c             public boolean addAll Iterable lt   extends E gt  c            boolean rv   false          for  E item  c                rv    add item                     return rv              Override     public boolean contains Object e            return indexMap containsKey e               Override      public int indexOf Object e            if  e    null  return -1          Integer i   indexMap get e           return  i    null    -1   i              Override     public int lastIndexOf Object e            return indexOf e               Override  SuppressWarnings  unchecked       public Object clone             IndexedArraySet clone    IndexedArraySet  super clone            clone indexMap    HashMap  indexMap clone            return clone              Override     public void add int idx  E e            if indexMap putIfAbsent requireNonNull e   -1     null  return          super add idx  e           reindex                Override     public boolean remove Object e            boolean rv          try   rv   super remove e             finally   reindex              return rv              Override     public void clear             super clear            indexMap clear                Override     public boolean addAll int idx  Collection lt   extends E gt  c            boolean rv          try               for E item   c                       check uniqueness                 addToIndex item  -1                             rv   super addAll idx  c             finally               reindex                      return rv              Override     public boolean removeAll Collection lt   gt  c            boolean rv          try   rv   super removeAll c             finally   reindex              return rv              Override     public boolean retainAll Collection lt   gt  c            boolean rv          try   rv   super retainAll c             finally   reindex              return rv              Override     public boolean removeIf Predicate lt   super E gt  filter            boolean rv          try   rv   super removeIf filter             finally   reindex              return rv              Override     public void replaceAll final UnaryOperator lt E gt  operator            indexMap clear            try               int duplicates   0              for  int i   0  i  lt  size    i                      E newval   requireNonNull operator apply this get i                     if indexMap putIfAbsent newval  i-duplicates     null                        super set i-duplicates  newval                     else                       duplicates                                                removeRange size  -duplicates  size               catch  Exception ex                   If there s an exception the indexMap will be inconsistent             reindex                throw ex                         Override     public void sort Comparator lt   super E gt  c            try   super sort c             finally   reindex

User · Answer

TreeSet is ordered   http   docs oracle com javase 6 docs api java util TreeSet html

User · Answer

Try using java util TreeSet that implements SortedSet   To quote the doc       The elements are ordered using their natural ordering  or by a Comparator provided at set creation time  depending on which constructor is used    Note that add  remove and contains has a time cost log n     If you want to access the content of the set as an Array  you can convert it doing   YourType   array   someSet toArray new YourType yourSet size         This array will be sorted with the same criteria as the TreeSet  natural or by a comparator   and in many cases this will have a advantage instead of doing a Arrays sort

User · Answer

IndexedTreeSet from the indexed-tree-map project provides this functionality  ordered sorted set with list-like access by index

User · Answer

Take a look at the Java standard API doc  Right next to LinkedHashMap  there is a LinkedHashSet  But note that the order in those is the insertion order  not the natural order of the elements  And you can only iterate in that order  not do random access  except by counting iteration steps    There is also an interface SortedSet implemented by TreeSet and ConcurrentSkipListSet  Both allow iteration in the natural order of their elements or a Comparator  but not random access or insertion order   For a data structure that has both efficient access by index and can efficiently implement the set criterium  you d need a skip list  but there is no implementation with that functionality in the Java Standard API  though I am certain it s easy to find one on the internet

[java] Any implementation of Ordered Set in Java?

Examples related to java

Examples related to collections

Examples related to set