java - 具有多个实例但具有唯一对象标识的已排序集合

Question

我一直在寻找实现 Collection 接口(interface)的东西，在其中我可以添加同一对象的多个实例(基于给定的比较器)，但集合不能包含两次相同的对象标识(基于 == 运算符)。该集合必须进行排序，并且我必须能够删除一个特定元素(基于 == 运算符)。

换句话说，它必须满足以下测试用例:

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());
   }
}

有什么帮助吗？

谢谢!

Answer 1

编辑:实际上我认为这可以通过 new TreeSet<>(Ordering.natural().thenComparing(Ordering.arbitrary())) 来解决(与 Guava 的 Ordering )

<小时/>

如果您没有 Guava，您可以使用 TreeMap 和 IdentityHashMap 自行推出，例如:

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;
        }
    }

}

请注意 Collection.remove 的文档写成 equals ，因此此类不能严格遵守 Collection 契约，并且如果作为 Collection 传递给您无法控制的代码，则可能会导致错误。