Prelude:  Here's what my current array based implementation of ICollection looks like.  It builds upon a lot of suggestions as to the tradeoffs of perf vs. memory and uses delegates to place control in the person who creates the collection for how certain operations behave:

namespace Testing.Collections

{

    using System;

    using Testing.Functional;

 

    public class ArrayCollection<A> : ICollection<A>

    {

        private readonly Authenticator<A> authenticate;

        private A[] array;

        private uint count;

 

        private static readonly Authenticator<A> DefaultAuthenticate = delegate(A a1, A a2)

        {

            return object.Equals(a1, a2);

        };

 

        public ArrayCollection() : this(DefaultAuthenticate) {

        }

 

        public ArrayCollection(Authenticator<A> authenticate)

        {

            this.authenticate = authenticate;

            if (null == authenticate)

            {

                throw new ArgumentNullException("authenticate");

            }

        }

 

        #region ICollection<A> Members

 

        public bool Empty {

            get {

                return count == 0;

            }

        }

 

        public bool Add(A element) {

            //From CLR 369 (Dynamic Tables)

            EnsureSpace();

 

            array[count] = element;

            count++;

 

            //Adding an element always modifies an ArrayCollection

            return true;

        }

 

        private void EnsureSpace()

        {

            if (array == null)

            {

                array = new A[2];

            }

 

            if (count == array.Length)

            {

                A[] doubledArray = new A[count * 2];

                Array.Copy(array, doubledArray, count);

                array = doubledArray;

            }

        }

 

        public void Clear()

        {

            array = null;

            count = 0;

        }

 

        public bool Contains(A element)

        {

            for (uint i = 0; i < count; i++)

            {

                if (this.authenticate(array[i], element))

                {

                    return true;

                }

            }

 

            return false;

        }

 

        public bool Remove(A element)

        {

            for (uint i = 0; i < count; i++)

            {

                if (this.authenticate(array[i], element))               

                {

                    RemoveAt(i);

                    Contract();

 

                    return true;

                }

            }

 

            return false;

        }

 

        private void Contract()

        {

            //Shrink the array if the number of elements has gone below

            //1/4th the capacity.  See CLR 370 (Dynamic Tables: Table-Delete)

            if (count < (array.Length / 4))

            {

                A[] halvedArray = new A[array.Length / 2];

                Array.Copy(array, halvedArray, count);

            }

        }

 

        private void RemoveAt(uint i)

        {

            //Move the last element into the array into this position

            uint lastItem = count - 1;

            array[i] = array[lastItem];

            array[lastItem] = default(A);

            count--;

        }

 

        #endregion

    }

}

There are small changes to the first version of the code:

  1. I use null to represent an empty array
  2. When getting space initially for the array we default to a size of 2.  This was chosen because it's the smallest size that the array can reach when you call remove
  3. Equality is based on a delegate passed in the constructor.  If no delegate is passed then we use object.Equals(o1, o2) to test equality.

I'm writing this as a library that I intend people to use and augment.  So I don't feel a test is complete unless I try subclassing the class to provide a specialized implementation.  In this case I wanted to create an “IdentityCollection”.

My definition of an IdentityCollection was: an ICollection<A> where equality is defined as:

  1. Reference equality if A is a reference type
  2. Structural equality if A is a value type

So if you had checked if an object was in the collection it would only report true if that was in teh same location in memory.  I could do this with the following code:

ICollection<string> collection1 = new ArrayCollection<string>(delegate(string s1, string s2) {

                                                                  return object.ReferenceEquals(s1, s2);

                                                              });

However, this wouldn't work for value types.  For example, I would expect to be able to type:

collection.Add(4) and then have collection.Contains(4) return true.  However, using ReferenceEquals wouldn't work because it would automatically box those value type into objects in different locations in memory.

My initial stab at it looked like this:

class IdentityCollection<A> : ArrayCollection<A>

{

    public IdentityCollection() : base(delegate (A a1, A a2) {

        return a1 == a2;

    }) {}

} 

I figured that == would have reference semantics on objects and structural semantics on values.  Pretty intuitive considering that == has structural semantics on all the predefined value types in the system (bool, int, decimal, etc.).  However, when i tried this I got:

 Error 1  Operator '==' cannot be applied to operands of type 'A' and 'A'

Sigh... I'm reading through the language spec right now to understand this.  However, can anyone else think of way to get this done?