List implementation that maintains ordering

collections, insertion-order, java, list

Solution

Response to new requirement. I see two potentials:

Do what the JavaDoc for `PriorityQueue` says:

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method `iterator()` is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using `Arrays.sort(pq.toArray())`.

I suspect this will yield the best performance given your requirements. If this is not acceptable, you'll need to better explain what you're trying to accomplish.

Build a List that simply sorts itself upon addition of new elements. This is a real pain... if you used a linked structure, you can do an efficient insertion sort, but locality is bad. If you used an array-backed structure, insertion sort is a pain but traversal is better. If iteration/traversal is infrequent, you could hold the list contents unsorted and sort only on demand.

Consider using a PriorityQueue as I suggested, and in the event you need to iterate in order, write a wrapper iterator:

class PqIter implements Iterator<T>
{
   final PriorityQueue<T> pq;
   public PqIter(PriorityQueue <T> source)
   {
     pq = new PriorityQueue(source); 
   }

   @Override
   public boolean hasNext()
   {
     return pq.peek() != null
   }

   @Override
   public T next()
   { return pq.poll(); }

   @Override
   public void remove()
   { throw new UnsupportedOperationException(""); }
}

Use Guava's `TreeMultiSet`. I tested the following code with `Integer` and it seems to do the right thing.

import com.google.common.collect.TreeMultiset;

public class TreeMultiSetTest { 
  public static void main(String[] args) {
    TreeMultiset<Integer> ts = TreeMultiset.create();
    ts.add(1);  ts.add(0); ts.add(2);
    ts.add(-1); ts.add(5); ts.add(2);

    for (Integer i : ts) {
      System.out.println(i);
    } 
  } 
}

The below addresses the uniqueness/filtering problem you were having when using a `SortedSet`. I see that you also want an iterator, so this won't work.

If what you really want is an ordered list-like thing, you can make use of a `PriorityQueue`.

Comparator<T> cmp = new MyComparator<T>();
PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
pq.add(someT);

Take note of what the API documentation says about the time properties of various operations:

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (`offer`, `poll`, `remove()` and `add`); linear time for the `remove(Object)` and `contains(Object)` methods; and constant time for the retrieval methods (`peek`, `element`, and `size`).

You should also be aware that the iterators produced by `PriorityQueue` do not behave as one might expect:

The `Iterator` provided in method `iterator()` is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using `Arrays.sort(pq.toArray())`.

I just noticed that Guava provides a `MinMaxPriorityQueue`. This implementation is array-backed, rather than the linked form provided in the JDK's `PriorityQueue`, and thus likely has different timing behavior. If you're doing something performance sensitive, you may wish to take a look. While the notes give slightly different (linear and logarithmic) big-O times, all those times should also be bounded, which may be useful.

There is not a `List` implementation per se that maintains ordering, but what you are likely looking for are implementations of `SortedSet`. A `TreeSet` is the most common. The other implementation, a `ConcurrentSkipListSet` is for more specific uses. Note that a `SortedSet` provides ordering, but does not allow duplicate entries, as does a `List`.

Refs:

- Blog post `PriorityQueue` iterator is not ordered

- SO question on PQ ordered iterator

Problem

Original source

Related problems

• A good Sorted List for Java
• Sorted array list in Java
• The built-in iterator for java's PriorityQueue does not traverse the data structure in any particular order. Why?
• Sorted collection in Java