一個有多個實例但唯一對象標識的排序集合

Question

我正在尋找一些實現Collection接口的地方，我可以添加同一對象的多個實例（基於給定的比較器），但該集合不能包含兩次相同的對象標識（基於==運算符）。集合必須進行排序，我必須能夠刪除一個特定的元素（基於==運算符）。

換句話說，它必須滿足以下測試用例：

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()))來解決（與番石榴的Ordering）

---

我以前建議使用多集是行不通的。下面是一個實現只是使用標準庫，使用一些的帕特里夏的想法：

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

} 

這將是清潔的，如果IdentityHashMap<T, Object>被包裹成一個新的類IdentityHashSet<T>，但是這個代碼已經是有點多後的StackOverflow的回答，所以我會把它作爲讀者的練習。

請注意，Collection.remove的文檔是根據equals編寫的，所以此類不能嚴格遵守收集合同，並且如果作爲集合傳遞給您不受控制的代碼，則可能會導致錯誤。

Answer 2

關於你的問題的這部分內容「但該集合不能包含兩倍相同的對象標識（基於==運算符）」，如果你想要兩個對象都等於等於和==運算符，你需要閱讀實例控制的對象（基本上是散列它們自己的實例的對象，並且當請求的對象已經存在時返回相同的緩存對象，而不是創建新對象）。

Answer 3

如果沒有現有的集合不正是你想要的，請考慮以下策略：

定義一個類，它的公共方法做的正是你所需要的，不能多也不能少。

使用現有的集合來實現這個類來處理忙碌的工作，但是通過控制代碼來強加您的需求。

例如，您的類可能具有TreeSet，其每個元素都是基礎類的非空IdentityHashMap。 TreeSet比較器將從每個IdentityHashMap中抽取一個元素並返回比較它們的結果。

要移除一個元素，首先檢查移除它是否會清空其IdentityHashMap（它存在，並且設置大小爲1）。如果是這樣，請從TreeSet中移除IdentityHashMap。如果不是，則從IdentityHashMap中刪除該元素。

這只是一個大綱，需要填寫大量細節。主要觀點是根據您編寫的類中已經存在的內容準確構建您想要的內容。