A sorted Collection with multiple instances but unique object identity

Question

I was looking for something implementing the Collection interface where I can add multiple instances of the same object (based on the given Comparator), but the collection cannot contain twice the same object identity (based on the == operator). The collection has to be sorted and I must be able to remove one particular element (based on the == operator).

In other words, it has to satisfy the following testcase :

public MyCollection<E> implements Collection<E>
{ ... }

public class MyCollectionTest extends TestCase
{
   static class MyComparator implements Comparator<MyInterface>
   {
      @Override
      public int compare(MyInterface pO1, MyInterface pO2)
      {
         // the return type of getCategory() is just an enum.
         return pO1.getCategory().ordinal() - pO2.getCategory().ordinal();
      }
   }

   public void testAdd()
   {
      MyCollection<MyInterface> sut = new MyCollection<MyInterface>(new MyComparator());
      MyInterface svc1 = EasyMock.createNiceMock(MyInterface.class);
      MyInterface svc2 = EasyMock.createNiceMock(MyInterface.class);
      EasyMock.expect(svc1.getCategory()).andStubReturn(Category.CAR);
      EasyMock.expect(svc2.getCategory()).andStubReturn(Category.VAN);
      EasyMock.replay(svc1, svc2);
      sut.add(svc1);
      sut.add(svc2);
      assertEquals(2, sut.size());
      assertSame(svc1, sut.last());
      assertSame(svc2, sut.first());
   }

   public void testAddDouble()
   {
      MyCollection<MyInterface> sut = new MyCollection<MyInterface>(new MyComparator());
      MyInterface svc1 = EasyMock.createNiceMock(MyInterface.class);
      EasyMock.expect(svc1.getCategory()).andStubReturn(Category.CAR);
      sut.add(svc1);
      sut.add(svc1);
      assertEquals(1, sut.size());
   }

   public void testRemove()
   {
      MyCollection<MyInterface> sut = new MyCollection<MyInterface>(new MyComparator());
      MyInterface svc1 = EasyMock.createNiceMock(MyInterface.class);
      MyInterface svc2 = EasyMock.createNiceMock(MyInterface.class);
      EasyMock.expect(svc1.getCategory()).andStubReturn(Category.VAN);
      EasyMock.expect(svc2.getCategory()).andStubReturn(Category.VAN);
      EasyMock.replay(svc1, svc2);
      sut.add(svc1);
      sut.add(svc2);
      assertEquals(2, sut.size());
      sut.remove(svc1);
      assertEquals(1, sut.size());
   }
}

Any help ?

Thank you!

Answer 1

EDIT: Actually I think this can be solved with just new TreeSet<>(Ordering.natural().thenComparing(Ordering.arbitrary())) (with Guava's Ordering)

---

If you don't have Guava, you could roll your own using TreeMap and IdentityHashMap, something like:

public class IdentityTreeSet<T extends Comparable> extends AbstractCollection<T> {

    private SortedMap<T, Set<T>> values = new TreeMap<>();

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Iterator<Set<T>> outerIterator = values.values().iterator();
            Set<T> currentSet = Collections.newSetFromMap(new IdentityHashMap<>());
            Iterator<T> innerIterator = currentSet.iterator();

            @Override
            public boolean hasNext() {
                return innerIterator.hasNext() || outerIterator.hasNext();
            }

            @Override
            public T next() {
                if (innerIterator.hasNext()) {
                    return innerIterator.next();
                } else {
                    currentSet = outerIterator.next();
                    innerIterator = currentSet.iterator();
                    return next();
                }
            }

            @Override
            public void remove() {
                innerIterator.remove();
                if (currentSet.isEmpty()) {
                    outerIterator.remove();
                }
            }

        };
    }

    @Override
    public int size() {
        int i = 0;
        for (Set<T> set : values.values()) {
            i += set.size();
        }
        return i;
    }

    @Override
    public boolean add(T e) {
        Set<T> entrySet = values.get(e);

        if (entrySet == null) {
            Set<T> newSet = Collections.newSetFromMap(new IdentityHashMap<>());
            newSet.add(e);
            values.put(e, newSet);
            return true;
        } else {
            return entrySet.add(e);
        }
    }

    @Override
    public boolean remove(Object o) {
        Set<T> entrySet = values.get(o);

        if (entrySet == null) {
            return false;
        } else {
            boolean removed = entrySet.remove(o);
            if (entrySet.isEmpty()) {
                values.remove(o);
            }
            return removed;
        }
    }

}

Note that the documentation for Collection.remove is written in terms of equals, so this class cannot strictly adhere to the Collection contract, and may cause errors if passed as a Collection to code you don't control.

Answer 2

If no existing collection does exactly what you want, consider the following strategy:

Define a class whose public methods do exactly what you need, no more and no less.

Implement the class using existing collections to take care of the busy work, but with your code in control to impose your requirements.

For example, your class might have a TreeSet each of whose elements is a non-empty IdentityHashMap of the underlying class. The TreeSet comparator would pull an element from each IdentityHashMap and return the result of comparing them.

To remove an element, first check whether removing it would empty its IdentityHashMap (it is present, and the set size is 1). If so, remove the IdentityHashMap from the TreeSet. If not, remove the element from its IdentityHashMap.

This is only an outline, with a lot of details that need to be filled in. The main point is the idea of building exactly what you want, based on what already exists wrapped in a class you write.

Answer 3

Concerning this part of your question "but the collection cannot contain twice the same object identity (based on the == operator)", if you want two objects to be both equal by equals and == operator, you need to read about instance controlled objects (basically objects that hash their own instances, and return you the same cached object instead of creating a new one when the object being requested already exists).