Unit testing + Collections

Another principle that i think I will be following is to design around interfaces.  Because I am attempting to write a library, I feel that it's important not to tie people down to classes.  If i do this then people are forced to use my implementations instead of being able to provide their own which might be far better suited to their domain.  However, it's unclear to me the best way to test this.  Take the following simple interface definition:

public interface ICollection<A> {

    void Add(A element);

    bool Empty { get; }

}

I initially started by saying: Ok, so I'll try to formalize the invariants of the system and the write tests for them.  In this case we could write a test:

namespace Collections.Tests {
 [TextFixture]
 public abstract class Collections {

  protected abstract ICollection<int> NewCollection();

  [Test]
  void InitiallyEmpty() {
   //Tests the invariant that a new collection starts out empty
   ICollection<int> collection = NewCollection();
   Assert(collection.Empty);
  }

  [Test]
  void NotEmptyAfterAdd() {
   ICollection<int> collection = NewCollection();
   collection.Add(0);
   Assert(!collection.Empty);
  }
 }
}

The test is abstract because it's testing an interface and it has no idea how to instantiate that interface.  Thus it is up to subclasses to instantiate an instance and then the tests will run over that instance. 

However, i then realized something.  Say in the future I have something like a FilteredCollection which does not add values that don't match a specified filter.  Then it might be possible to try to add a value, have it fail, and have the size not change.

I struggled a bit over if that should throw an exception or not.  However, i decided that such an behavior could be considered expected.  Say you had an ISet<int> and you tried to add 0 twice.  You'd expect the first to be added, and the second to not be.  Because of that i felt that modifying the signature of Add to be: "bool Add(A element);" (where the bool indicated if an element was added or not) was the most compelling choice.  However, it also makes me feel that collections that contain unique elements should be marked as such.  I.e. either IUniqueElements or UniqueElementsAttribute (most likely the latter)

We coudl then remove NotEmptyAfterAdd and replace with:

  void EmptyAfterAdd() {
   ICollection<int> collection = NewCollection();
   bool modified = collection.Add(0);

   if (modified) {
     Assert(!collection.Empty);
   } else {
     Assert(collection.Empty);
   }
  }

Did thinking about my tests first make me realize an issue with API far ahead of time?  Did they help me reason better about the correct way to go about fixing/sidestepping the issue?  It's not clear to me at all yet :-)