PeeWee2201 PeeWee2201 - 3 months ago 17
Java Question

A sorted Collection with multiple instances but unique object identity

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

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


My previous suggestion using MultiSets wouldn't work. Here's an implementation just using the standard library, using some of Patricia's ideas:

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

    private static final Object PRESENT = new Object(); 

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

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>()
        {
            Iterator<IdentityHashMap<T, Object>> outerIterator = values.values().iterator();
            IdentityHashMap<T, Object> currentMap = new IdentityHashMap();
            Iterator<T> innerIterator = currentMap.keySet().iterator();

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

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

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

        };
    }

    @Override
    public int size()
    {
        int i = 0;
        for (T t: this)
        {
            i++;
        }
        return i;
    }

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

        if (entrySet == null)
        {
            IdentityHashMap<T, Object> newList = new IdentityHashMap<T, Object>();
            newList.put(e, PRESENT);
            values.put(e, newList);
            return true;
        }
        else
        {
            if (entrySet.containsKey(e))
            {
                return false;
            }
            entrySet.put(e, PRESENT);
            return true;
        }
    }

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

        if (entrySet == null)
        {
            return false;
        }
        else
        {
            if (! entrySet.containsKey(o))
            {
                return false;
            }
            else
            {
                entrySet.remove(o);
                if (entrySet.isEmpty())
                {
                    values.remove(o);
                }
                return true;
            }
        }
    }

}

This would be cleaner if IdentityHashMap<T, Object> was wrapped up into a new class IdentityHashSet<T>, but this code is already a bit much to post as a StackOverflow answer, so I'll leave that as an exercise for the reader.

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.