List implementation that maintains ordering

Question

Is there an existing List implementation in Java that maintains order based on provided Comparator?

Something that can be used in the following way:

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

so that someT gets inserted such that the order in the list is maintained according to cmp

(On @andersoj suggestion I am completing my question with one more request)

Also I want to be able to traverse the list in sorted order without removing the elements, i.e:

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

should pass.

All suggestions are welcome (except telling me to use Collections.sort on the unordered full list), though, I would prefer something in java.* or eventually org.apache.* since it would be hard to introduce new libraries at this moment.

Note: (UPDATE4) I realized that implementations of this kind of list would have inadequate performance. There two general approaches:

1. Use Linked structure (sort of) B-tree or similar
2. Use array and insertion (with binary search)

No 1. has problem with CPU cache misses No 2. has problem with shifting elements in array.

UPDATE2: TreeSet does not work because it uses the provided comparator (MyComparator) to check for equality and based on it assumes that the elements are equal and exclude them. I need that comparator only for ordering, not "uniqueness" filtering (since the elements by their natural ordering are not equal)

UPDATE3: PriorityQueue does not work as List (as I need) because there is no way to traverse it in the order it is "sorted", to get the elements in the sorted order you have to remove them from the collection.

UPDATE:

Similar question:
A good Sorted List for Java
Sorted array list in Java

Answer 1

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

Answer 2

You should probably be using a TreeSet:

The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

Example:

Comparator<T> cmp = new MyComparator<T>();
TreeSet<T> t = new TreeSet<T>(cmp);
l.add(someT);

Note that this is a set, so no duplicate entries are allowed. This may or may not work for your specific use-case.

Answer 3

I have a similar problem and I'm thinking of using a TreeSet. To avoid excluding "equal" elements I will modify the comparator so instead of returning 0 it will return a random number between (-1,1) or it will return always 1.

If you have no control over the Comparator or if you are using it for something else different than inserting this solution won't work for you.