{
                KeyValuePair<TKey, TValue> dummy;
                tree.Insert(NewPair(key, value),
                                DuplicatePolicy.ReplaceLast, out dummy);
			}
		}

		/// <summary>
		/// Determines if this dictionary contains a key equal to <paramref name="key"/>. The dictionary
		/// is not changed.
		/// </summary>
        /// <remarks>Searching the dictionary for a key takes time O(log N), where N is the number of keys in the dictionary.</remarks>
        /// <param name="key">The key to search for.</param>
        /// <returns>True if the dictionary contains key. False if the dictionary does not contain key.</returns>
        public sealed override bool ContainsKey(TKey key)
        {
            KeyValuePair<TKey, TValue> pairFound;

            return tree.Find(NewPair(key), false, false, out pairFound);
		}

        /// <summary>
        /// Determines if this dictionary contains a key equal to <paramref name="key"/>. If so, the value
        /// associated with that key is returned through the value parameter.
        /// </summary>
        /// <remarks>TryGetValue takes time O(log N), where N is the number of entries in the dictionary.</remarks>
        /// <param name="key">The key to search for.</param>
        /// <param name="value">Returns the value associated with key, if true was returned.</param>
        /// <returns>True if the dictionary contains key. False if the dictionary does not contain key.</returns>
        public sealed override bool TryGetValue(TKey key, out TValue value)
        {
            KeyValuePair<TKey, TValue> pairFound;

            bool found = tree.Find(NewPair(key), false, false, out pairFound);
            value = pairFound.Value;
            return found;
        }

        #endregion

		#region ICollection<KeyValuePair<TKey,TValue>> Members

        /// <summary>
        /// Returns the number of keys in the dictionary.
		/// </summary>
        /// <remarks>The size of the dictionary is returned in constant time..</remarks>
        /// <value>The number of keys in the dictionary.</value>
        public sealed override int Count
		{
			get
			{
				return tree.ElementCount;
			}
		}

#endregion

		#region IEnumerable<KeyValuePair<TKey,TValue>> Members

		/// <summary>
		/// Returns an enumerator that enumerates all the entries in the dictionary. Each entry is 
		/// returned as a KeyValuePair&lt;TKey,TValue&gt;.
		/// The entries are enumerated in the sorted order of the keys.
		/// </summary>
		/// <remarks>
		/// <p>Typically, this method is not called directly. Instead the "foreach" statement is used
		/// to enumerate the elements of the dictionary, which uses this method implicitly.</p>
		/// <p>If an element is added to or deleted from the dictionary while it is being enumerated, then 
		/// the enumeration will end with an InvalidOperationException.</p>
		/// <p>Enumeration all the entries in the dictionary takes time O(N log N), where N is the number
		/// of entries in the dictionary.</p>
		/// </remarks>
		/// <returns>An enumerator for enumerating all the elements in the OrderedDictionary.</returns>		
		public sealed override IEnumerator<KeyValuePair<TKey,TValue>> GetEnumerator()
		{
            return tree.GetEnumerator();
		}

		#endregion

		#region ICloneable Members

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

		#endregion

        /// <summary>
        /// The OrderedDictionary&lt;TKey,TValue&gt;.View class is used to look at a subset of the keys and values
        /// inside an ordered dictionary. It is returned from the Range, RangeTo, RangeFrom, and Reversed methods. 
        /// </summary>
        ///<remarks>
        /// <p>Views are dynamic. If the underlying dictionary changes, the view changes in sync. If a change is made
        /// to the view, the underlying dictionary changes accordingly.</p>
        ///<p>Typically, this class is used in conjunction with a foreach statement to enumerate the keys
        /// and values in a subset of the OrderedDictionary. For example:</p>
        ///<code>
        /// foreach(KeyValuePair&lt;TKey, TValue&gt; pair in dictionary.Range(from, to)) {
        ///    // process pair
        /// }
        ///</code>
        ///</remarks>
        [Serializable]
        public class View : DictionaryBase<TKey, TValue>
        {
            private OrderedDictionary<TKey,TValue> myDictionary;
            private RedBlackTree<KeyValuePair<TKey,TValue>>.RangeTester rangeTester;   // range tester for the range being used.
            private bool entireTree;                   // is the view the whole tree?
            private bool reversed;                     // is the view reversed?

            /// <summary>
            /// Initialize the View.
            /// </summary>
            /// <param name="myDictionary">Associated OrderedDictionary to be viewed.</param>
            /// <param name="rangeTester">Range tester that defines the range being used.</param>
            /// <param name="entireTree">If true, then rangeTester defines the entire tree.</param>
            /// <param name="reversed">Is the view enuemerated in reverse order?</param>
            internal View(OrderedDictionary<TKey, TValue> myDictionary, RedBlackTree<KeyValuePair<TKey, TValue>>.RangeTester rangeTester, bool entireTree, bool reversed)
            {
                this.myDictionary = myDictionary;
                this.rangeTester = rangeTester;
                this.entireTree = entireTree;
                this.reversed = reversed;
            }

            /// <summary>
            /// Determine if the given key lies within the bounds of this view.
            /// </summary>
            /// <param name="key">Key to test.</param>
            /// <returns>True if the key is within the bounds of this view.</returns>
            private bool KeyInView(TKey key)
            {
                return rangeTester(NewPair(key, default(TValue))) == 0;
            }

            /// <summary>
            /// Enumerate all the keys and values in this view.
            /// </summary>
            /// <returns>An IEnumerator of KeyValuePairs with the keys and views in this view.</returns>
            public sealed override IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
            {
                if (reversed)
                    return myDictionary.tree.EnumerateRangeReversed(rangeTester).GetEnumerator();
                else
                    return myDictionary.tree.EnumerateRange(rangeTester).GetEnumerator();
            }

            /// <summary>
            /// Number of keys in this view.
            /// </summary>
            /// <value>Number of keys that lie within the bounds the view.</value>
            public sealed override int Count
            {
                get
                {
                    if (entireTree)
                        return myDictionary.Count;
                    else
                        return myDictionary.tree.CountRange(rangeTester);
                }
            }

            /// <summary>
            /// Tests if the key is present in the part of the dictionary being viewed.
            /// </summary>
            /// <param name="key">Key to check for.</param>
            /// <returns>True if the key is within this view. </returns>
            public sealed override bool ContainsKey(TKey key)
            {
                if (!KeyInView(key))
                    return false;
                else
                    return myDictionary.ContainsKey(key);
            }

            /// <summary>
            /// Determines if this view contains a key equal to <paramref name="key"/>. If so, the value
            /// associated with that key is returned through the value parameter. 
            /// </summary>
            /// <param name="key">The key to search for.</param>
            /// <param name="value">Returns the value associated with key, if true was returned.</param>
            /// <returns>True if the key is within this view. </returns>
            public sealed override bool TryGetValue(TKey key, out TValue value)
            {
                if (!KeyInView(key)) {
                    value = default(TValue);
                    return false;
                }
                else {
                    return myDictionary.TryGetValue(key, out value);
                }
            }

            /// <summary>
            /// Gets or sets the value associated with a given key. When getting a value, if this
            /// key is not found in the collection, then an ArgumentException is thrown. When setting
            /// a value, the value replaces any existing value in the dictionary. When setting a value, the 
            /// key must be within the range of keys being viewed.
            /// </summary>
            /// <value>The value associated with the key.</value>
            /// <exception cref="ArgumentException">A value is being retrieved, and the key is not present in the dictionary, 
            /// or a value is being set, and the key is outside the range of keys being viewed by this View.</exception>
            public sealed override TValue this[TKey key]
            {
                get       // technically we don't need to override this, but fixes a bug in NDOC.
                {
                    return base[key];
                }
                 set
                {
                    if (!KeyInView(key))
                        throw new ArgumentException(Strings.OutOfViewRange, "key");
                    else
                        myDictionary[key] = value;
                }
            }

            /// <summary>
            /// Removes the key (and associated value) from the underlying dictionary of this view. that is equal to the passed in key. If
            /// no key in the view is equal to the passed key, the dictionary and view are unchanged.
            /// </summary>
            /// <param name="key">The key to remove.</param>
            /// <returns>True if the key was found and removed. False if the key was not found.</returns>
            public sealed override bool Remove(TKey key)
            {
                if (!KeyInView(key))
                    return false;
                else
                    return myDictionary.Remove(key);
            }

            /// <summary>
            /// Removes all the keys and values within this view from the underlying OrderedDictionary.
            /// </summary>
            /// <example>The following removes all the keys that start with "A" from an OrderedDictionary.
            /// <code>
            /// dictionary.Range("A", "B").Clear();
            /// </code>
            /// </example>
            public sealed override void Clear()
            {
                if (entireTree) {
                    myDictionary.Clear();
                }
                else {
                    myDictionary.tree.DeleteRange(rangeTester);
                }
            }

            /// <summary>
            /// Creates a new View that has the same keys and values as this, in the reversed order.
            /// </summary>
            /// <returns>A new View that has the reversed order of this view.</returns>
            public View Reversed()
            {
                return new View(myDictionary, rangeTester, entireTree, !reversed);
            }
        }
    }
}