// Value was not found.
                    return false;
                }
            }
            else {
                return false;         // key not found.
            }
        }


        /// <summary>
        /// Removes a key and all associated values from the dictionary. If the
        /// key is not present in the dictionary, it is unchanged and false is returned.
        /// </summary>
        /// <param name="key">The key to remove.</param>
        /// <returns>True if the key was present and was removed. Returns 
        /// false if the key was not present.</returns>
        public sealed override bool Remove(TKey key)
        {
            KeyAndValues dummy;
            return hash.Delete(new KeyAndValues(key), out dummy);
        }

        /// <summary>
        /// Removes all keys and values from the dictionary.
        /// </summary>
        public sealed override void Clear()
        {
            hash.StopEnumerations();  // Invalidate any enumerations.

            // The simplest and fastest way is simply to throw away the old hash and create a new one.
            hash = new Hash<KeyAndValues>(equalityComparer);
        }

        #endregion Add or remove items

        #region Query items

        /// <summary>
        /// Returns the IEqualityComparer&lt;T&gt; used to compare keys in this dictionary. 
        /// </summary>
        /// <value>If the dictionary was created using a comparer, that comparer is returned. Otherwise
        /// the default comparer for TKey (EqualityComparer&lt;TKey&gt;.Default) is returned.</value>
        public IEqualityComparer<TKey> KeyComparer
        {
            get
            {
                return this.keyEqualityComparer;
            }
        }

        /// <summary>
        /// Returns the IEqualityComparer&lt;T&gt; used to compare values in this dictionary. 
        /// </summary>
        /// <value>If the dictionary was created using a comparer, that comparer is returned. Otherwise
        /// the default comparer for TValue (EqualityComparer&lt;TValue&gt;.Default) is returned.</value>
        public IEqualityComparer<TValue> ValueComparer
        {
            get
            {
                return this.valueEqualityComparer;
            }
        }

        /// <summary>
        /// Determine if two values are equal.
        /// </summary>
        /// <param name="value1">First value to compare.</param>
        /// <param name="value2">Second value to compare.</param>
        /// <returns>True if the values are equal.</returns>
        protected sealed override bool EqualValues(TValue value1, TValue value2)
        {
            return valueEqualityComparer.Equals(value1, value2);
        }

        /// <summary>
        /// Gets the number of key-value pairs in the dictionary. Each value associated
        /// with a given key is counted. If duplicate values are permitted, each duplicate
        /// value is included in the count.
        /// </summary>
        /// <value>The number of key-value pairs in the dictionary.</value>
        public sealed override int Count
        {
            get
            {
                return hash.ElementCount;
            }
        }

        /// <summary>
        /// Checks to see if <paramref name="value"/> is associated with <paramref name="key"/>
        /// in the dictionary.
        /// </summary>
        /// <param name="key">The key to check.</param>
        /// <param name="value">The value to check.</param>
        /// <returns>True if <paramref name="value"/> is associated with <paramref name="key"/>.</returns>
        public sealed override bool Contains(TKey key, TValue value)
        {
            KeyAndValues find = new KeyAndValues(key);
            KeyAndValues item;
            if (hash.Find(find, false, out item)) {
                int existingCount = item.Count;
                int valueHash = Util.GetHashCode(value, valueEqualityComparer);
                for (int i = 0; i < existingCount; ++i) {
                    if (Util.GetHashCode(item.Values[i], valueEqualityComparer) == valueHash &&
                        valueEqualityComparer.Equals(item.Values[i], value)) {
                        // Found an equal existing value. 
                        return true;
                    }
                }
            }
            
            return false;
        }

        /// <summary>
        /// Checks to see if the key is present in the dictionary and has
        /// at least one value associated with it.
        /// </summary>
        /// <param name="key">The key to check.</param>
        /// <returns>True if <paramref name="key"/> is present and has at least
        /// one value associated with it. Returns false otherwise.</returns>
        public sealed override bool ContainsKey(TKey key)
        {
            KeyAndValues find = new KeyAndValues(key);
            KeyAndValues temp;
            return hash.Find(find, false, out temp);
        }

        /// <summary>
        /// Enumerate all the keys in the dictionary. 
        /// </summary>
        /// <returns>An IEnumerator&lt;TKey&gt; that enumerates all of the keys in the dictionary that
        /// have at least one value associated with them.</returns>
        protected sealed override IEnumerator<TKey> EnumerateKeys()
        {
            foreach (KeyAndValues item in hash) {
                yield return item.Key;
            }
        }

        /// <summary>
        ///  Enumerate the values in the a KeyAndValues structure. Can't return
        /// the array directly because:
        ///   a) The array might be larger than the count.
        ///   b) We can't allow clients to down-cast to the array and modify it.
        ///   c) We have to abort enumeration if the hash changes.
        /// </summary>
        /// <param name="keyAndValues">Item with the values to enumerate..</param>
        /// <returns>An enumerable that enumerates the items in the KeyAndValues structure.</returns>
        private IEnumerator<TValue> EnumerateValues(KeyAndValues keyAndValues)
        {
            int count = keyAndValues.Count;
            int stamp = hash.GetEnumerationStamp();

            for (int i = 0; i < count; ++i) {
                yield return keyAndValues.Values[i];
                hash.CheckEnumerationStamp(stamp);
            }
        }

        /// <summary>
        /// Determines if this dictionary contains a key equal to <paramref name="key"/>. If so, all the values
        /// associated with that key are returned through the values parameter. 
        /// </summary>
        /// <param name="key">The key to search for.</param>
        /// <param name="values">Returns all values associated with key, if true was returned.</param>
        /// <returns>True if the dictionary contains key. False if the dictionary does not contain key.</returns>
        protected sealed override bool TryEnumerateValuesForKey(TKey key, out IEnumerator<TValue> values)
        {
            KeyAndValues find = new KeyAndValues(key);
            KeyAndValues item;
            if (hash.Find(find, false, out item)) {
                values = EnumerateValues(item);
                return true;
            }
            else {
                values = null;
                return false;
            }
        }

        /// <summary>
        /// Gets the number of values associated with a given key.
        /// </summary>
        /// <param name="key">The key to count values of.</param>
        /// <returns>The number of values associated with <paramref name="key"/>. If <paramref name="key"/>
        /// is not present in the dictionary, zero is returned.</returns>
        protected sealed override int CountValues(TKey key)
        {
            KeyAndValues find = new KeyAndValues(key);
            KeyAndValues item;
            if (hash.Find(find, false, out item)) {
                return item.Count;
            }
            else {
                return 0;
            }
        }

        #endregion Query items

        #region Cloning

        /// <summary>
        /// Makes a shallow clone of this dictionary; i.e., if keys or values of the
        /// dictionary are reference types, then they are not cloned. If TKey or TValue is a value type,
        /// then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks>Cloning the dictionary takes time O(N), where N is the number of key-value pairs in the dictionary.</remarks>
        /// <returns>The cloned dictionary.</returns>
        public MultiDictionary<TKey, TValue> Clone()
        {
            return new MultiDictionary<TKey, TValue>(allowDuplicateValues, keyEqualityComparer, valueEqualityComparer, equalityComparer, 
                hash.Clone(KeyAndValues.Copy));
        }

        /// <summary>
        /// Implements ICloneable.Clone. Makes a shallow clone of this dictionary; i.e., if keys or values are reference types, then they are not cloned.
        /// </summary>
        /// <returns>The cloned dictionary.</returns>
        object ICloneable.Clone()
        {
            return Clone();
        }

        /// <summary>
        /// Throw an InvalidOperationException indicating that this type is not cloneable.
        /// </summary>
        /// <param name="t">Type to test.</param>
        private void NonCloneableType(Type t)
        {
            throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, t.FullName));
        }

        /// <summary>
        /// Makes a deep clone of this dictionary. A new dictionary is created with a clone of
        /// each entry of this dictionary, by calling ICloneable.Clone on each element. If TKey or TValue is
        /// a value type, then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks><para>If TKey or TValue is a reference type, it must implement
        /// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
        /// <para>Cloning the dictionary takes time O(N log N), where N is the number of key-value pairs in the dictionary.</para></remarks>
        /// <returns>The cloned dictionary.</returns>
        /// <exception cref="InvalidOperationException">TKey or TValue is a reference type that does not implement ICloneable.</exception>
        public MultiDictionary<TKey, TValue> CloneContents()
        {
            bool keyIsValueType, valueIsValueType;

            // Make sure that TKey and TValue can be cloned.
            if (!Util.IsCloneableType(typeof(TKey), out keyIsValueType))
                NonCloneableType(typeof(TKey));

            if (!Util.IsCloneableType(typeof(TValue), out valueIsValueType))
                NonCloneableType(typeof(TValue));

            // It's tempting to do a more efficient cloning, utilizing the hash.Clone() method. However, we can't know that
            // the cloned version of the key has the same hash value.

            MultiDictionary<TKey, TValue> newDict = new MultiDictionary<TKey, TValue>(allowDuplicateValues, keyEqualityComparer, valueEqualityComparer);

            foreach (KeyAndValues item in hash) {
                // Clone the key and values parts. Value types can be cloned
                // by just copying them, otherwise, ICloneable is used.
                TKey keyClone;
                TValue[] valuesClone;

                if (keyIsValueType)
                    keyClone = item.Key;
                else {
                    if (item.Key == null)
                        keyClone = default(TKey);  // Really null, because we know TKey isn't a value type.
                    else
                        keyClone = (TKey)(((ICloneable)item.Key).Clone());
                }

                valuesClone = new TValue[item.Count];
                if (valueIsValueType)
                    Array.Copy(item.Values, valuesClone, item.Count);
                else {
                    for (int i = 0; i < item.Count; ++i) {
                        if (item.Values[i] == null)
                            valuesClone[i] = default(TValue);   // Really null, because we know TKey isn't a value type.
                        else
                            valuesClone[i] = (TValue)(((ICloneable)item.Values[i]).Clone());
                    }
                }

                newDict.AddMany(keyClone, valuesClone);
            }

            return newDict;
        }

        #endregion Cloning

    }
}