/// <summary>
        /// Determines if this bag contains an item equal to <paramref name="item"/>. The bag
        /// is not changed.
        /// </summary>
        /// <remarks>Searching the bag for an item takes time O(log N), where N is the number of items in the bag.</remarks>
        /// <param name="item">The item to search for.</param>
        /// <returns>True if the bag contains <paramref name="item"/>. False if the bag does not contain <paramref name="item"/>.</returns>
        public sealed override bool Contains(T item)
        {
            T dummy;
            return tree.Find(item, false, false, out dummy);
        }

        /// <summary>
        /// <para>Enumerates all of the items in this bag that are equal to <paramref name="item"/>, according to the 
        /// comparison mechanism that was used when the bag was created. The bag
        /// is not changed.</para>
        /// <para>If the bag does contain an item equal to <paramref name="item"/>, then the enumeration contains
        /// no items.</para>
        /// </summary>
        /// <remarks>Enumeration the items in the bag equal to <paramref name="item"/> takes time O(log N + M), where N 
        /// is the total number of items in the bag, and M is the number of items equal to <paramref name="item"/>.</remarks>
        /// <param name="item">The item to search for.</param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates all the items in the bag equal to <paramref name="item"/>. </returns>
        public IEnumerable<T> GetEqualItems(T item)
        {
            return tree.EnumerateRange(tree.EqualRangeTester(item));  
        }

        /// <summary>
        /// Enumerates all the items in the bag, but enumerates equal items
        /// just once, even if they occur multiple times in the bag.
        /// </summary>
        /// <remarks>If the bag is changed while items are being enumerated, the
        /// enumeration will terminate with an InvalidOperationException.</remarks>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates the unique items.</returns>
        public IEnumerable<T> DistinctItems()
        {
            T previous = default(T);
            bool atBeginning = true;

            // Enumerate the items, but only yield ones not equal to the previous one.
            foreach (T item in this) {
                if (atBeginning || comparer.Compare(item, previous) != 0)
                    yield return item;
                previous = item;
                atBeginning = false;
            }
        }

        #endregion

        #region Index by sorted order

        /// <summary>
        /// Get the item by its index in the sorted order. The smallest item has index 0,
        /// the next smallest item has index 1, and the largest item has index Count-1. 
        /// </summary>
        /// <remarks>The indexer takes time O(log N), which N is the number of items in 
        /// the set.</remarks>
        /// <param name="index">The index to get the item by.</param>
        /// <returns>The item at the given index.</returns>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
        /// less than zero or greater than or equal to Count.</exception>
        public T this[int index]
        {
            get
            {
                if (index < 0 || index >= Count)
                    throw new ArgumentOutOfRangeException("index");

                return tree.GetItemByIndex(index);
            }
        }

        /// <summary>
        /// Get the index of the given item in the sorted order. The smallest item has index 0,
        /// the next smallest item has index 1, and the largest item has index Count-1. If multiple
        /// equal items exist, the largest index of the equal items is returned.
        /// </summary>
        /// <remarks>Finding the index takes time O(log N), which N is the number of items in 
        /// the set.</remarks>
        /// <param name="item">The item to get the index of.</param>
        /// <returns>The index of the last item in the sorted bag equal to <paramref name="item"/>, or -1 if the item is not present
        /// in the set.</returns>
        public int LastIndexOf(T item)
        {
            return tree.FindIndex(item, false);
        }

        /// <summary>
        /// Get the index of the given item in the sorted order. The smallest item has index 0,
        /// the next smallest item has index 1, and the largest item has index Count-1. If multiple
        /// equal items exist, the smallest index of the equal items is returned.
        /// </summary>
        /// <remarks>Finding the index takes time O(log N), which N is the number of items in 
        /// the set.</remarks>
        /// <param name="item">The item to get the index of.</param>
        /// <returns>The index of the first item in the sorted bag equal to <paramref name="item"/>, or -1 if the item is not present
        /// in the set.</returns>
        public int IndexOf(T item)
        {
            return tree.FindIndex(item, true);
        }

        #endregion

        #region Adding elements

        /// <summary>
        /// Adds a new item to the bag. Since bags can contain duplicate items, the item 
        /// is added even if the bag already contains an item equal to <paramref name="item"/>. In
        /// this case, the new item is placed after all equal items already present in the bag.
        /// </summary>
        /// <remarks>
        /// <para>Adding an item takes time O(log N), where N is the number of items in the bag.</para></remarks>
        /// <param name="item">The item to add to the bag.</param>
        public sealed override void Add(T item)
        {
            T dummy;
            tree.Insert(item, DuplicatePolicy.InsertLast, out dummy);
        }

        /// <summary>
        /// Adds all the items in <paramref name="collection"/> to the bag. 
        /// </summary>
        /// <remarks>
        /// <para>Adding the collection takes time O(M log N), where N is the number of items in the bag, and M is the 
        /// number of items in <paramref name="collection"/>.</para></remarks>
        /// <param name="collection">A collection of items to add to the bag.</param>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public void AddMany(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            // If we're adding ourselves, we need to copy to a separate array to avoid modification
            // during enumeration.
            if (this == collection)
                collection = this.ToArray();

            foreach (T item in collection)
                Add(item);
        }

        #endregion Adding elements

        #region Removing elements

        /// <summary>
        /// Searches the bag for one item equal to <paramref name="item"/>, and if found,
        /// removes it from the bag. If not found, the bag is unchanged. If more than one item
        /// equal to <paramref name="item"/>, the item that was last inserted is removed.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparison instance or delegate used
        /// to create the bag.</para>
        /// <para>Removing an item from the bag takes time O(log N), where N is the number of items in the bag.</para></remarks>
        /// <param name="item">The item to remove.</param>
        /// <returns>True if <paramref name="item"/> was found and removed. False if <paramref name="item"/> was not in the bag.</returns>
        public sealed override bool Remove(T item)
        {
            T dummy;
            return tree.Delete(item, false, out dummy);
        }

        /// <summary>
        /// Searches the bag for all items equal to <paramref name="item"/>, and 
        /// removes all of them from the bag. If not found, the bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparison instance or delegate used
        /// to create the bag.</para>
        /// <para>RemoveAllCopies() takes time O(M log N), where N is the total number of items in the bag, and M is
        /// the number of items equal to <paramref name="item"/>.</para></remarks>
        /// <param name="item">The item to remove.</param>
        /// <returns>The number of copies of <paramref name="item"/> that were found and removed. </returns>
        public int RemoveAllCopies(T item)
        {
            return tree.DeleteRange(tree.EqualRangeTester(item));
        }

        /// <summary>
        /// Removes all the items in <paramref name="collection"/> from the bag. Items not
        /// present in the bag are ignored.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparison instance or delegate used
        /// to create the bag.</para>
        /// <para>Removing the collection takes time O(M log N), where N is the number of items in the bag, and M is the 
        /// number of items in <paramref name="collection"/>.</para></remarks>
        /// <param name="collection">A collection of items to remove from the bag.</param>
        /// <returns>The number of items removed from the bag.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public int RemoveMany(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            int count = 0;

            if (collection == this) {
                count = Count;
                Clear();            // special case, otherwise we will throw.
            }
            else {
                foreach (T item in collection) {
                    if (Remove(item))
                        ++count;
                }
            }

            return count;
        }

        /// <summary>
        /// Removes all items from the bag.
        /// </summary>
        /// <remarks>Clearing the bag takes a constant amount of time, regardless of the number of items in it.</remarks>
        public sealed override void Clear()
        {
            tree.StopEnumerations();  // Invalidate any enumerations.

            // The simplest and fastest way is simply to throw away the old tree and create a new one.
            tree = new RedBlackTree<T>(comparer);
        }

        #endregion Removing elements

        #region First/last items

        /// <summary>
        /// If the collection is empty, throw an invalid operation exception.
        /// </summary>
        /// <exception cref="InvalidOperationException">The bag is empty.</exception>
        private void CheckEmpty()
        {
            if (Count == 0)
                throw new InvalidOperationException(Strings.CollectionIsEmpty);
        }

        /// <summary>
        /// Returns the first item in the bag: the item
        /// that would appear first if the bag was enumerated. This is also
        /// the smallest item in the bag.
        /// </summary>
        /// <remarks>GetFirst() takes time O(log N), where N is the number of items in the bag.</remarks>
        /// <returns>The first item in the bag. If more than one item
        /// is smallest, the first one added is returned.</returns>
        /// <exception cref="InvalidOperationException">The bag is empty.</exception>
        public T GetFirst()
        {
            T item;
            CheckEmpty();
            tree.FirstItemInRange(tree.EntireRangeTester, out item);
            return item;
        }

        /// <summary>
        /// Returns the last item in the bag: the item
        /// that would appear last if the bag was enumerated. This is also the largest
        /// item in the bag.
        /// </summary>
        /// <remarks>GetLast() takes time O(log N), where N is the number of items in the bag.</remarks>
        /// <returns>The last item in the bag. If more than one item
        /// is largest, the last one added is returned.</returns>
        /// <exception cref="InvalidOperationException">The bag is empty.</exception>
        public T GetLast()