Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Auto-filter for Microsoft WPF DataGrid

, 29 Jan 2009
Allows auto filtering functionality for DataGrid columns.
WPFGridFilter.zip
WPFGridFilter
PowerCollections
PowerCollections.csproj.user
Properties
Stepi.Collections
bin
Filters
Properties
Stepi.UIFilters
bin
Initializers
Properties
Settings.settings
Themes
Test.GridSorting
bin
Debug
Test.GridFilter.vshost.exe
Properties
Settings.settings
//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement 
// contained in the file "License.txt" accompanying this file.
//******************************

using System;
using System.Collections.Generic;
using System.Collections;

// CONSIDER: RemoveIdentical to remove an identical item only. Can this be done with current RedBlack tree implementation? How
// CONSIDER: useful is it?

namespace Wintellect.PowerCollections
{
    /// <summary>
    /// OrderedBag&lt;T&gt; is a collection that contains items of type T. 
    /// The item are maintained in a sorted order. Unlike a OrderedSet, duplicate items (items that
    /// compare equal to each other) are allows in an OrderedBag.
    /// </summary>
    /// <remarks>
    /// <p>The items are compared in one of three ways. If T implements IComparable&lt;TKey&gt; or IComparable,
    /// then the CompareTo method of that interface will be used to compare items. Alternatively, a comparison
    /// function can be passed in either as a delegate, or as an instance of IComparer&lt;TKey&gt;.</p>
    /// <p>OrderedBag is implemented as a balanced binary tree. Inserting, deleting, and looking up an
    /// an element all are done in log(N) + M time, where N is the number of keys in the tree, and M is the current number
    /// of copies of the element being handled.</p>
    /// <p><see cref="Bag&lt;T&gt;"/> is similar, but uses hashing instead of comparison, and does not maintain
    /// the keys in sorted order.</p>
    ///</remarks>
    ///<seealso cref="Bag&lt;T&gt;"/>
    [Serializable]
    public class OrderedBag<T> : CollectionBase<T>, ICloneable
    {
        // The comparer used to compare items. 
        private IComparer<T> comparer;

        // The red-black tree that actually does the work of storing the items.
        private RedBlackTree<T> tree;

        #region Constructors

        /// <summary>
        /// Creates a new OrderedBag. The T must implement IComparable&lt;T&gt;
        /// or IComparable. 
        /// The CompareTo method of this interface will be used to compare items in this bag.
        /// </summary>
        ///<remarks>
        /// Items that are null are permitted, and will be sorted before all other items.
        ///</remarks>
        /// <exception cref="InvalidOperationException">T does not implement IComparable&lt;TKey&gt;.</exception>
        public OrderedBag(): 
            this(Comparers.DefaultComparer<T>())
        {
        }

        /// <summary>
        /// Creates a new OrderedBag. The passed delegate will be used to compare items in this bag.
        /// </summary>
        /// <param name="comparison">A delegate to a method that will be used to compare items.</param>
        public OrderedBag(Comparison<T> comparison) :
            this(Comparers.ComparerFromComparison<T>(comparison))
        {
        }

        /// <summary>
        /// Creates a new OrderedBag. The Compare method of the passed comparison object
        /// will be used to compare items in this bag.
        /// </summary>
        /// <remarks>
        /// The GetHashCode and Equals methods of the provided IComparer&lt;T&gt; will never
        /// be called, and need not be implemented.
        /// </remarks>
        /// <param name="comparer">An instance of IComparer&lt;T&gt; that will be used to compare items.</param>
        public OrderedBag(IComparer<T> comparer)
        {
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            this.comparer = comparer;
            tree = new RedBlackTree<T>(comparer);
        }

        /// <summary>
        /// Creates a new OrderedBag. The T must implement IComparable&lt;T&gt;
        /// or IComparable. 
        /// The CompareTo method of this interface will be used to compare items in this bag. The bag is
        /// initialized with all the items in the given collection.
        /// </summary>
        ///<remarks>
        /// Items that are null are permitted, and will be sorted before all other items.
        ///</remarks>
        /// <param name="collection">A collection with items to be placed into the OrderedBag.</param>
        /// <exception cref="InvalidOperationException">T does not implement IComparable&lt;TKey&gt;.</exception>
        public OrderedBag(IEnumerable<T> collection): 
            this(collection, Comparers.DefaultComparer<T>())
        {
        }

        /// <summary>
        /// Creates a new OrderedBag. The passed delegate will be used to compare items in this bag.
        /// The bag is initialized with all the items in the given collection.
        /// </summary>
        /// <param name="collection">A collection with items to be placed into the OrderedBag.</param>
        /// <param name="comparison">A delegate to a method that will be used to compare items.</param>
        public OrderedBag(IEnumerable<T> collection, Comparison<T> comparison):
            this(collection, Comparers.ComparerFromComparison<T>(comparison))
        {
        }

        /// <summary>
        /// Creates a new OrderedBag. The Compare method of the passed comparison object
        /// will be used to compare items in this bag. The bag is
        /// initialized with all the items in the given collection.
        /// </summary>
        /// <remarks>
        /// The GetHashCode and Equals methods of the provided IComparer&lt;T&gt; will never
        /// be called, and need not be implemented.
        /// </remarks>
        /// <param name="collection">A collection with items to be placed into the OrderedBag.</param>
        /// <param name="comparer">An instance of IComparer&lt;T&gt; that will be used to compare items.</param>
        public OrderedBag(IEnumerable<T> collection, IComparer<T> comparer):
            this(comparer)
        {
            AddMany(collection);
        }

        /// <summary>
        /// Creates a new OrderedBag given a comparer and a tree that contains the data. Used
        /// internally for Clone.
        /// </summary>
        /// <param name="comparer">Comparer for the bag.</param>
        /// <param name="tree">Data for the bag.</param>
        private OrderedBag(IComparer<T> comparer, RedBlackTree<T> tree) 
        {
            this.comparer = comparer;
            this.tree = tree;
        }

        #endregion Constructors

        #region Cloning

        /// <summary>
        /// Makes a shallow clone of this bag; i.e., if items of the
        /// bag are reference types, then they are not cloned. If T is a value type,
        /// then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks>Cloning the bag takes time O(N), where N is the number of items in the bag.</remarks>
        /// <returns>The cloned bag.</returns>
        object ICloneable.Clone()
        {
            return this.Clone();
        }

        /// <summary>
        /// Makes a shallow clone of this bag; i.e., if items of the
        /// bag are reference types, then they are not cloned. If T is a value type,
        /// then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks>Cloning the bag takes time O(N), where N is the number of items in the bag.</remarks>
        /// <returns>The cloned bag.</returns>
        public OrderedBag<T> Clone()
        {
            OrderedBag<T> newBag = new OrderedBag<T>(comparer, tree.Clone());
            return newBag;
        }

        /// <summary>
        /// Makes a deep clone of this bag. A new bag is created with a clone of
        /// each element of this bag, by calling ICloneable.Clone on each element. If T is
        /// a value type, then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks><para>If T is a reference type, it must implement
        /// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
        /// <para>Cloning the bag takes time O(N log N), where N is the number of items in the bag.</para></remarks>
        /// <returns>The cloned bag.</returns>
        /// <exception cref="InvalidOperationException">T is a reference type that does not implement ICloneable.</exception>
        public OrderedBag<T> CloneContents()
        {
            bool itemIsValueType;
            if (!Util.IsCloneableType(typeof(T), out itemIsValueType))
                throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, typeof(T).FullName));

            OrderedBag<T> clone = new OrderedBag<T>(comparer);

            // Clone each item, and add it to the new ordered bag.
            foreach (T item in this) {
                T itemClone;

                if (itemIsValueType)
                    itemClone = item;
                else {
                    if (item == null)
                        itemClone = default(T);    // Really null, because we know T is a reference type
                    else
                        itemClone = (T)(((ICloneable)item).Clone());
                }

                clone.Add(itemClone);
            }

            return clone;
        }

        #endregion Cloning

        #region Basic collection containment

        /// <summary>
        /// Returns the IComparer&lt;T&gt; used to compare items in this bag. 
        /// </summary>
        /// <value>If the bag was created using a comparer, that comparer is returned. If the bag was
        /// created using a comparison delegate, then a comparer equivalent to that delegate
        /// is returned. Otherwise
        /// the default comparer for T (Comparer&lt;T&gt;.Default) is returned.</value>
        public IComparer<T> Comparer
        {
            get
            {
                return this.comparer;
            }
        }

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

        /// <summary>
        /// Returns the number of copies of <paramref name="item"/> in the bag. More precisely, returns
        /// the number of items in the bag that compare equal to <paramref name="item"/>.
        /// </summary>
        /// <remarks>NumberOfCopies() takes time O(log N + M), where N is the total number of items in the
        /// bag, and M is the number of copies of <paramref name="item"/> in the bag.</remarks>
        /// <param name="item">The item to search for in the bag.</param>
        /// <returns>The number of items in the bag that compare equal to <paramref name="item"/>.</returns>
        public int NumberOfCopies(T item)
        {
            return tree.CountRange(tree.EqualRangeTester(item));
        }

        /// <summary>
        /// Returns an enumerator that enumerates all the items in the bag. 
        /// The items are enumerated in sorted order.
        /// </summary>
        /// <remarks>
        /// <p>Typically, this method is not called directly. Instead the "foreach" statement is used
        /// to enumerate the items, which uses this method implicitly.</p>
        /// <p>If an item is added to or deleted from the bag while it is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        /// <p>Enumeration all the items in the bag takes time O(N), where N is the number
        /// of items in the bag.</p>
        /// </remarks>
        /// <returns>An enumerator for enumerating all the items in the OrderedBag.</returns>		
        public sealed override IEnumerator<T> GetEnumerator()
        {
            return tree.GetEnumerator();
        }

        /// <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()
        {
            T item;
            CheckEmpty();
            tree.LastItemInRange(tree.EntireRangeTester, out item);
            return item;
        }

        /// <summary>
        /// Removes the first item in the bag. This is also the smallest
        /// item in the bag.
        /// </summary>
        /// <remarks>RemoveFirst() takes time O(log N), where N is the number of items in the bag.</remarks>
        /// <returns>The item that was removed, which was the smallest item in the bag. </returns>
        /// <exception cref="InvalidOperationException">The bag is empty.</exception>
        public T RemoveFirst()
        {
            CheckEmpty();
            T item;
            tree.DeleteItemFromRange(tree.EntireRangeTester, true, out item);
            return item;
        }

        /// <summary>
        /// Removes the last item in the bag. This is also the largest item in the bag.
        /// </summary>
        /// <remarks>RemoveLast() takes time O(log N), where N is the number of items in the bag.</remarks>
        /// <returns>The item that was removed, which was the largest item in the bag. </returns>
        /// <exception cref="InvalidOperationException">The bag is empty.</exception>
        public T RemoveLast()
        {
            CheckEmpty();
            T item;
            tree.DeleteItemFromRange(tree.EntireRangeTester, false, out item);
            return item;
        }

        #endregion

        #region Set operations

        /// <summary>
        /// Check that this bag and another bag were created with the same comparison
        /// mechanism. Throws exception if not compatible.
        /// </summary>
        /// <param name="otherBag">Other bag to check comparision mechanism.</param>
        /// <exception cref="InvalidOperationException">If otherBag and this bag don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        private void CheckConsistentComparison(OrderedBag<T> otherBag)
        {
            if (otherBag == null)
                throw new ArgumentNullException("otherBag");

            if (!object.Equals(comparer, otherBag.comparer))
                throw new InvalidOperationException(Strings.InconsistentComparisons);
        }

        /// <summary>
        /// Determines if this bag is a superset of another bag. Neither bag is modified.
        /// This bag is a superset of <paramref name="otherBag"/> if every element in
        /// <paramref name="otherBag"/> is also in this bag, at least the same number of
        /// times.
        /// </summary>
        /// <remarks>IsSupersetOf is computed in time O(M log N), where M is the size of the 
        /// <paramref name="otherSet"/>, and N is the size of the this set.</remarks>
        /// <param name="otherBag">OrderedBag to compare to.</param>
        /// <returns>True if this is a superset of <paramref name="otherBag"/>.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public bool IsSupersetOf(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            if (otherBag.Count > this.Count)
                return false;     // Can't be a superset of a bigger bag

            // Check each item in the other bag to make sure it is in this bag.
            foreach (T item in otherBag.DistinctItems()) {
                if (this.NumberOfCopies(item) < otherBag.NumberOfCopies(item))
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Determines if this bag is a proper superset of another bag. Neither bag is modified.
        /// This bag is a proper superset of <paramref name="otherBag"/> if every element in
        /// <paramref name="otherBag"/> is also in this bag, at least the same number of
        /// times. Additional, this bag must have strictly more items than <paramref name="otherBag"/>.
        /// </summary>
        /// <remarks>IsProperSupersetOf is computed in time O(M log N), where M is the number of unique items in 
        /// <paramref name="otherBag"/>.</remarks>
        /// <param name="otherBag">OrderedBag to compare to.</param>
        /// <returns>True if this is a proper superset of <paramref name="otherBag"/>.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public bool IsProperSupersetOf(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            if (otherBag.Count >= this.Count)
                return false;     // Can't be a proper superset of a bigger or equal set

            return IsSupersetOf(otherBag);
        }

        /// <summary>
        /// Determines if this bag is a subset of another bag. Neither bag is modified.
        /// This bag is a subset of <paramref name="otherBag"/> if every element in this bag
        /// is also in <paramref name="otherBag"/>, at least the same number of
        /// times.
        /// </summary>
        /// <remarks>IsSubsetOf is computed in time O(N log M), where M is the size of the 
        /// <paramref name="otherBag"/>, and N is the size of the this bag.</remarks>
        /// <param name="otherBag">OrderedBag to compare to.</param>
        /// <returns>True if this is a subset of <paramref name="otherBag"/>.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public bool IsSubsetOf(OrderedBag<T> otherBag)
        {
            return otherBag.IsSupersetOf(this);
        }

        /// <summary>
        /// Determines if this bag is a proper subset of another bag. Neither bag is modified.
        /// This bag is a subset of <paramref name="otherBag"/> if every element in this bag
        /// is also in <paramref name="otherBag"/>, at least the same number of
        /// times. Additional, this bag must have strictly fewer items than <paramref name="otherBag"/>.
        /// </summary>
        /// <remarks>IsSubsetOf is computed in time O(N log M), where M is the size of the 
        /// <paramref nameb="otherBag"/>, and N is the size of the this bag.</remarks>
        /// <param name="otherBag">OrderedBag to compare to.</param>
        /// <returns>True if this is a proper subset of <paramref name="otherBag"/>.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public bool IsProperSubsetOf(OrderedBag<T> otherBag)
        {
            return otherBag.IsProperSupersetOf(this);
        }

        /// <summary>
        /// Determines if this bag is disjoint from another bag. Two bags are disjoint
        /// if no item from one set is equal to any item in the other bag.
        /// </summary>
        /// <remarks>
        /// <para>The answer is computed in time O(N), where N is the size of the smaller set.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to check disjointness with.</param>
        /// <returns>True if the two bags are disjoint, false otherwise.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        public bool IsDisjointFrom(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            OrderedBag<T> smaller, larger;
            if (otherBag.Count > this.Count) {
                smaller = this; larger = otherBag;
            }
            else {
                smaller = otherBag; larger = this;
            }

            foreach (T item in smaller) {
                if (larger.Contains(item))
                    return false;
            }

            return true;
        }
            
        /// <summary>
        /// Determines if this bag is equal to another bag. This bag is equal to
        /// <paramref name="otherBag"/> if they contain the same items, each the
        /// same number of times.
        /// </summary>
        /// <remarks>IsEqualTo is computed in time O(N), where N is the number of items in 
        /// this bag.</remarks>
        /// <param name="otherBag">OrderedBag to compare to</param>
        /// <returns>True if this bag is equal to <paramref name="otherBag"/>, false otherwise.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        public bool IsEqualTo(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            // Must be the same size.
            if (otherBag.Count != this.Count)
                return false;

            // Since both bags are ordered, we can simply compare items in order.
            using (IEnumerator<T> enum1 = this.GetEnumerator(), enum2 = otherBag.GetEnumerator()) {
                bool continue1, continue2;

                for (; ; ) {
                    continue1 = enum1.MoveNext(); continue2 = enum2.MoveNext();
                    if (!continue1 || !continue2)
                        break;

                    if (comparer.Compare(enum1.Current, enum2.Current) != 0)
                        return false;     // the two items are not equal.
                }

                // If both continue1 and continue2 are false, we reached the end of both sequences at the same
                // time and found success. If one is true and one is false, the sequences were of difference lengths -- failure.
                return (continue1 == continue2);
            }
        }

        /// <summary>
        /// Computes the union of this bag with another bag. The union of two bags
        /// is all items from both of the bags. If an item appears X times in one bag,
        /// and Y times in the other bag, the union contains the item Maximum(X,Y) times. This bag receives
        /// the union of the two bags, the other bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The union of two bags is computed in time O(M + N log M), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to union with.</param>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public void UnionWith(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            T previous = default(T);
            bool atBeginning = true;
            int copiesInThis = 0, copiesInOther = 0;

            // Enumerate each of the items in the other bag. Add items that need to be
            // added to this bag.
            // CONSIDER: may be able to improve this algorithm if otherBag is larger than this bag.
            foreach (T item in otherBag) {
                if (atBeginning || comparer.Compare(item, previous) != 0) {
                    copiesInThis = this.NumberOfCopies(item);
                    copiesInOther = 1;
                }
                else {
                    ++copiesInOther;
                }

                if (copiesInOther > copiesInThis)
                    this.Add(item);

                previous = item;
                atBeginning = false;
            }
        }

        /// <summary>
        /// Computes the union of this bag with another bag. The union of two bags
        /// is all items from both of the bags.  If an item appears X times in one bag,
        /// and Y times in the other bag, the union contains the item Maximum(X,Y) times. A new bag is 
        /// created with the union of the bags and is returned. This bag and the other bag 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The union of two bags is computed in time O(M + N log M), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to union with.</param>
        /// <returns>The union of the two bags.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public OrderedBag<T> Union(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            OrderedBag<T> smaller, larger, result;
            if (otherBag.Count > this.Count) {
                smaller = this; larger = otherBag;
            }
            else {
                smaller = otherBag; larger = this;
            }

            result = larger.Clone();
            result.UnionWith(smaller);
            return result;
        }

        /// <summary>
        /// Computes the sum of this bag with another bag. The sum of two bags
        /// is all items from both of the bags. If an item appears X times in one bag,
        /// and Y times in the other bag, the sum contains the item (X+Y) times. This bag receives
        /// the sum of the two bags, the other bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The sum of two bags is computed in time O(M + N log M), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to sum with.</param>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public void SumWith(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            AddMany(otherBag);

            // CONSIDER: if otherBag is much larger, maybe better to clone it,
            // add all of the current into it, and replace.
        }

        /// <summary>
        /// Computes the sum of this bag with another bag. he sum of two bags
        /// is all items from both of the bags.  If an item appears X times in one bag,
        /// and Y times in the other bag, the sum contains the item (X+Y) times. A new bag is 
        /// created with the sum of the bags and is returned. This bag and the other bag 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The sum of two bags is computed in time O(M + N log M), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to sum with.</param>
        /// <returns>The sum of the two bags.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public OrderedBag<T> Sum(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            OrderedBag<T> smaller, larger, result;
            if (otherBag.Count > this.Count) {
                smaller = this; larger = otherBag;
            }
            else {
                smaller = otherBag; larger = this;
            }

            result = larger.Clone();
            result.AddMany(smaller);
            return result;
        }

        /// <summary>
        /// Computes the intersection of this bag with another bag. The intersection of two bags
        /// is all items that appear in both of the bags. If an item appears X times in one bag,
        /// and Y times in the other bag, the sum contains the item Minimum(X,Y) times. This bag receives
        /// the intersection of the two bags, the other bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both bags, the intersection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>The intersection of two bags is computed in time O(N log M), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to intersection with.</param>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public void IntersectionWith(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            tree.StopEnumerations();

            OrderedBag<T> smaller, larger;
            if (otherBag.Count > this.Count) {
                smaller = this; larger = otherBag;
            }
            else {
                smaller = otherBag; larger = this;
            }

            T dummy;
            RedBlackTree<T> newTree = new RedBlackTree<T>(comparer);

            T previous = default(T);
            bool atBeginning = true;
            int copiesInSmaller = 0, copiesInLarger = 0;

            // Enumerate each of the items in the smaller bag. Add items that need to be
            // added to the intersection.
            foreach (T item in smaller) {
                if (atBeginning || comparer.Compare(item, previous) != 0) {
                    copiesInLarger = larger.NumberOfCopies(item);
                    copiesInSmaller = 1;
                }
                else {
                    ++copiesInSmaller;
                }

                if (copiesInSmaller <= copiesInLarger)
                    newTree.Insert(item, DuplicatePolicy.InsertLast, out dummy);

                previous = item;
                atBeginning = false;
            }

            tree = newTree;
        }

        /// <summary>
        /// Computes the intersection of this bag with another bag. The intersection of two bags
        /// is all items that appear in both of the bags. If an item appears X times in one bag,
        /// and Y times in the other bag, the sum contains the item Minimum(X,Y) times. A new bag is 
        /// created with the intersection of the bags and is returned. This bag and the other bag 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both bags, the intersection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>The intersection of two bags is computed in time O(N log M), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to intersection with.</param>
        /// <returns>The intersection of the two bags.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public OrderedBag<T> Intersection(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            OrderedBag<T> smaller, larger, result;
            if (otherBag.Count > this.Count) {
                smaller = this; larger = otherBag;
            }
            else {
                smaller = otherBag; larger = this;
            }

            T previous = default(T);
            bool atBeginning = true;
            int copiesInSmaller = 0, copiesInLarger = 0;

            // Enumerate each of the items in the smaller bag. Add items that need to be
            // added to the intersection.
            result = new OrderedBag<T>(comparer);
            foreach (T item in smaller) {
                if (atBeginning || comparer.Compare(item, previous) != 0) {
                    copiesInLarger = larger.NumberOfCopies(item);
                    copiesInSmaller = 1;
                }
                else {
                    ++copiesInSmaller;
                }

                if (copiesInSmaller <= copiesInLarger)
                    result.Add(item);

                previous = item;
                atBeginning = false;
            }

            return result;
        }

        /// <summary>
        /// Computes the difference of this bag with another bag. The difference of these two bags
        /// is all items that appear in this bag, but not in <paramref name="otherBag"/>. If an item appears X times in this bag,
        /// and Y times in the other bag, the difference contains the item X - Y times (zero times if Y >= X). This bag receives
        /// the difference of the two bags; the other bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The difference of two bags is computed in time O(M + N log M), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to difference with.</param>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public void DifferenceWith(OrderedBag<T> otherBag)
        {
            // Difference with myself is nothing. This check is needed because the
            // main algorithm doesn't work correctly otherwise.
            if (this == otherBag)
                Clear();

            CheckConsistentComparison(otherBag);

            T previous = default(T);
            bool atBeginning = true;
            int copiesInThis = 0, copiesInOther = 0;

            // Enumerate each of the items in the other bag. Remove items that need to be
            // removed from this bag.
            // CONSIDER: should be able to improve this algorithm if otherBag is larger than this bag.
            foreach (T item in otherBag) {
                if (atBeginning || comparer.Compare(item, previous) != 0) {
                    copiesInThis = this.NumberOfCopies(item);
                    copiesInOther = 1;
                }
                else {
                    ++copiesInOther;
                }

                if (copiesInOther <= copiesInThis)
                    this.Remove(item);

                previous = item;
                atBeginning = false;
            }

        }

        /// <summary>
        /// Computes the difference of this bag with another bag. The difference of these two bags
        /// is all items that appear in this bag, but not in <paramref name="otherBag"/>. If an item appears X times in this bag,
        /// and Y times in the other bag, the difference contains the item X - Y times (zero times if Y >= X).  A new bag is 
        /// created with the difference of the bags and is returned. This bag and the other bag 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The difference of two bags is computed in time O(M + N log M), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to difference with.</param>
        /// <returns>The difference of the two bags.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public OrderedBag<T> Difference(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            OrderedBag<T> result = this.Clone();
            result.DifferenceWith(otherBag);
            return result;
        }

        /// <summary>
        /// Computes the symmetric difference of this bag with another bag. The symmetric difference of two bags
        /// is all items that appear in either of the bags, but not both. If an item appears X times in one bag,
        /// and Y times in the other bag, the symmetric difference contains the item AbsoluteValue(X - Y times). This bag receives
        /// the symmetric difference of the two bags; the other bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The symmetric difference of two bags is computed in time O(M + N), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to symmetric difference with.</param>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public void SymmetricDifferenceWith(OrderedBag<T> otherBag)
        {
            tree = SymmetricDifference(otherBag).tree;
        }

        /// <summary>
        /// Computes the symmetric difference of this bag with another bag. The symmetric difference of two bags
        /// is all items that appear in either of the bags, but not both. If an item appears X times in one bag,
        /// and Y times in the other bag, the symmetric difference contains the item AbsoluteValue(X - Y times). A new bag is 
        /// created with the symmetric difference of the bags and is returned. This bag and the other bag 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The symmetric difference of two bags is computed in time O(M + N), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to symmetric difference with.</param>
        /// <returns>The symmetric difference of the two bags.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public OrderedBag<T> SymmetricDifference(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            OrderedBag<T> result = new OrderedBag<T>(comparer);
            IEnumerator<T> enum1 = this.GetEnumerator(), enum2 = otherBag.GetEnumerator();

            bool valid1 = enum1.MoveNext();
            bool valid2 = enum2.MoveNext();
            int compare;
            for (;;) {
                // Which item is smaller? The end (!valid) is considered larger than any item.
                if (! valid1) {
                    if (! valid2)
                        break;
                    compare = 1;
                }
                else if (! valid2)
                    compare = -1;
                else 
                    compare = comparer.Compare(enum1.Current, enum2.Current);

                // If equal, move through both bags without adding. Otherwise, add the smaller item and advance
                // just through that bag.
                if (compare == 0) {
                    valid1 = enum1.MoveNext();
                    valid2 = enum2.MoveNext();
                }
                else if (compare < 0) {
                    result.Add(enum1.Current);
                    valid1 = enum1.MoveNext();
                }
                else { // compare > 0
                    result.Add(enum2.Current);
                    valid2 = enum2.MoveNext();
                }
            }

            return result;
        }

        #endregion Set operations

        #region Read-only list view

        /// <summary>
        /// Get a read-only list view of the items in this ordered bag. The
        /// items in the list are in sorted order, with the smallest item
        /// at index 0. This view does not copy any data, and reflects any
        /// changes to the underlying OrderedBag.
        /// </summary>
        /// <returns>A read-only IList&lt;T&gt; view onto this OrderedBag.</returns>
        public IList<T> AsList()
        {
            return new ListView(this, tree.EntireRangeTester, true, false);
        }

        /// <summary>
        /// The nested class that provides a read-only list view
        /// of all or part of the collection.
        /// </summary>
        [Serializable]
        private class ListView : ReadOnlyListBase<T>
        {
            private OrderedBag<T> myBag;
            private RedBlackTree<T>.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>
            /// Create a new list view wrapped the given set.
            /// </summary>
            /// <param name="myBag">The ordered bag to wrap.</param>
            /// <param name="rangeTester">Range tester that defines the range being used.</param>
            /// <param name="entireTree">If true, then rangeTester defines the entire tree. Used to optimize some operations.</param>
            /// <param name="reversed">Is the view enuemerated in reverse order?</param>
            public ListView(OrderedBag<T> myBag, RedBlackTree<T>.RangeTester rangeTester, bool entireTree, bool reversed)
            {
                this.myBag = myBag;
                this.rangeTester = rangeTester;
                this.entireTree = entireTree;
                this.reversed = reversed;
            }

            public sealed override int Count
            {
                get
                {
                    if (entireTree)
                        return myBag.Count;
                    else {
                        // Note: we can't cache the result of this call because the underlying
                        // set can change, which would make the cached value incorrect.
                        return myBag.tree.CountRange(rangeTester);
                    }
                }
            }

            public sealed override T this[int index]
            {
                get
                {
                    if (entireTree) {
                        if (reversed)
                            return myBag[myBag.Count - 1 - index];
                        else
                            return myBag[index];
                    }
                    else {
                        T dummy;
                        int firstIndex = myBag.tree.FirstItemInRange(rangeTester, out dummy);
                        int lastIndex = myBag.tree.LastItemInRange(rangeTester, out dummy);
                        if (firstIndex < 0 || lastIndex < 0 || index < 0 || index >= (lastIndex - firstIndex + 1))
                            throw new ArgumentOutOfRangeException("index");

                        if (reversed)
                            return myBag[lastIndex - index];
                        else
                            return myBag[firstIndex + index];
                    }
                }
            }

            public sealed override int IndexOf(T item)
            {
                if (entireTree) {
                    if (reversed)
                        return myBag.Count - 1 - myBag.LastIndexOf(item);
                    else
                        return myBag.IndexOf(item);
                }
                else {
                    T dummy;

                    if (rangeTester(item) != 0)
                        return -1;

                    if (reversed) {
                        int indexInSet = myBag.tree.FindIndex(item, false);
                        if (indexInSet < 0)
                            return -1;
                        int indexOfEnd = myBag.tree.LastItemInRange(rangeTester, out dummy);
                        return indexOfEnd - indexInSet;

                    }
                    else {
                        int indexInSet = myBag.tree.FindIndex(item, true);
                        if (indexInSet < 0)
                            return -1;
                        int indexOfStart = myBag.tree.FirstItemInRange(rangeTester, out dummy);
                        return indexInSet - indexOfStart;
                    }
                }
            }
        }

        #endregion Read-only list view

        #region Sub-views

        /// <summary>
        /// Returns a View collection that can be used for enumerating the items in the bag in 
        /// reversed order.
        /// </summary>
        ///<remarks>
        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
        ///<code>
        /// foreach(T item in bag.Reversed()) {
        ///    // process item
        /// }
        ///</code></p>
        /// <p>If an item is added to or deleted from the bag while the View is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        ///<p>Calling Reverse does not copy the data in the tree, and the operation takes constant time.</p>
        ///</remarks>
        /// <returns>An OrderedBag.View of items in reverse order.</returns>
        public View Reversed()   // A reversed view that can be enumerated
        {
            return new View(this, tree.EntireRangeTester, true, true);
        }

        /// <summary>
        /// Returns a View collection that can be used for enumerating a range of the items in the bag.
        /// Only items that are greater than <paramref name="from"/> and 
        /// less than <paramref name="to"/> are included. The items are enumerated in sorted order.
        /// Items equal to the end points of the range can be included or excluded depending on the
        /// <paramref name="fromInclusive"/> and <paramref name="toInclusive"/> parameters.
        /// </summary>
        ///<remarks>
        ///<p>If <paramref name="from"/> is greater than or equal to <paramref name="to"/>, the returned collection is empty. </p>
        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
        ///<code>
        /// foreach(T item in bag.Range(from, true, to, false)) {
        ///    // process item
        /// }
        ///</code></p>
        /// <p>If an item is added to or deleted from the bag while the View is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        ///<p>Calling Range does not copy the data in the tree, and the operation takes constant time.</p>
        ///</remarks>
        /// <param name="from">The lower bound of the range.</param>
        /// <param name="fromInclusive">If true, the lower bound is inclusive--items equal to the lower bound will
        /// be included in the range. If false, the lower bound is exclusive--items equal to the lower bound will not
        /// be included in the range.</param>
        /// <param name="to">The upper bound of the range. </param>
        /// <param name="toInclusive">If true, the upper bound is inclusive--items equal to the upper bound will
        /// be included in the range. If false, the upper bound is exclusive--items equal to the upper bound will not
        /// be included in the range.</param>
        /// <returns>An OrderedBag.View of items in the given range.</returns>
        public View Range(T from, bool fromInclusive, T to, bool toInclusive)  // A partial view that can be enumerated
        {
            return new View(this, tree.DoubleBoundedRangeTester(from, fromInclusive, to, toInclusive), false, false);
        }

        /// <summary>
        /// Returns a View collection that can be used for enumerating a range of the items in the bag.
        /// Only items that are greater than (and optionally, equal to) <paramref name="from"/> are included. 
        /// The items are enumerated in sorted order. Items equal to <paramref name="from"/> can be included
        /// or excluded depending on the <paramref name="fromInclusive"/> parameter.
        /// </summary>
        ///<remarks>
        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
        ///<code>
        /// foreach(T item in bag.RangeFrom(from, true)) {
        ///    // process item
        /// }
        ///</code></p>
        /// <p>If an item is added to or deleted from the bag while the View is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        ///<p>Calling RangeFrom does not copy the data in the tree, and the operation takes constant time.</p>
        ///</remarks>
        /// <param name="from">The lower bound of the range.</param>
        /// <param name="fromInclusive">If true, the lower bound is inclusive--items equal to the lower bound will
        /// be included in the range. If false, the lower bound is exclusive--items equal to the lower bound will not
        /// be included in the range.</param>
        /// <returns>An OrderedBag.View of items in the given range.</returns>
        public View RangeFrom(T from, bool fromInclusive)  // A partial view that can be enumerated
        {
            return new View(this, tree.LowerBoundedRangeTester(from, fromInclusive), false, false);
        }

        /// <summary>
        /// Returns a View collection that can be used for enumerating a range of the items in the bag.
        /// Only items that are less than (and optionally, equal to) <paramref name="to"/> are included. 
        /// The items are enumerated in sorted order. Items equal to <paramref name="to"/> can be included
        /// or excluded depending on the <paramref name="toInclusive"/> parameter.
        /// </summary>
        ///<remarks>
        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
        ///<code>
        /// foreach(T item in bag.RangeTo(to, false)) {
        ///    // process item
        /// }
        ///</code></p>
        /// <p>If an item is added to or deleted from the bag while the View is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        ///<p>Calling RangeTo does not copy the data in the tree, and the operation takes constant time.</p>
        ///</remarks>
        /// <param name="to">The upper bound of the range. </param>
        /// <param name="toInclusive">If true, the upper bound is inclusive--items equal to the upper bound will
        /// be included in the range. If false, the upper bound is exclusive--items equal to the upper bound will not
        /// be included in the range.</param>
        /// <returns>An OrderedBag.View of items in the given range.</returns>
        public View RangeTo(T to, bool toInclusive)  // A partial view that can be enumerated
        {
            return new View(this, tree.UpperBoundedRangeTester(to, toInclusive), false, false);
        }

        #endregion

        #region View nested class

        /// <summary>
        /// The OrderedBag&lt;T&gt;.View class is used to look at a subset of the items
        /// inside an ordered bag. It is returned from the Range, RangeTo, RangeFrom, and Reversed methods. 
        /// </summary>
        ///<remarks>
        /// <p>Views are dynamic. If the underlying bag changes, the view changes in sync. If a change is made
        /// to the view, the underlying bag changes accordingly.</p>
        ///<p>Typically, this class is used in conjunction with a foreach statement to enumerate the items 
        /// in a subset of the OrderedBag. For example:</p>
        ///<code>
        /// foreach(T item in bag.Range(from, to)) {
        ///    // process item
        /// }
        ///</code>
        ///</remarks>
        [Serializable]
        public class View : CollectionBase<T>
        {
            private OrderedBag<T> myBag;
            private RedBlackTree<T>.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="myBag">OrderedBag being 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(OrderedBag<T> myBag, RedBlackTree<T>.RangeTester rangeTester, bool entireTree, bool reversed)
            {
                this.myBag = myBag;
                this.rangeTester = rangeTester;
                this.entireTree = entireTree;
                this.reversed = reversed;
            }

            /// <summary>
            /// Determine if the given item lies within the bounds of this view.
            /// </summary>
            /// <param name="item">Item to test.</param>
            /// <returns>True if the item is within the bounds of this view.</returns>
            private bool ItemInView(T item)
            {
                return rangeTester(item) == 0;
            }

            /// <summary>
            /// Enumerate all the items in this view.
            /// </summary>
            /// <returns>An IEnumerator&lt;T&gt; with the items in this view.</returns>
            public sealed override IEnumerator<T> GetEnumerator()
            {
                if (reversed)
                    return myBag.tree.EnumerateRangeReversed(rangeTester).GetEnumerator();
                else
                    return myBag.tree.EnumerateRange(rangeTester).GetEnumerator();
            }

            /// <summary>
            /// Number of items in this view.
            /// </summary>
            /// <value>Number of items that lie within the bounds the view.</value>
            public sealed override int Count
            {
                get
                {
                    if (entireTree)
                        return myBag.Count;
                    else {
                        // Note: we can't cache the result of this call because the underlying
                        // set can change, which would make the cached value incorrect.
                        return myBag.tree.CountRange(rangeTester);
                    }
                }
            }

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

            /// <summary>
            /// Adds a new item to the bag underlying this View. If the bag already contains an item equal to
            /// <paramref name="item"/>, that item is replaces with <paramref name="item"/>. If
            /// <paramref name="item"/> is outside the range of this view, an InvalidOperationException
            /// is thrown.
            /// </summary>
            /// <remarks>
            /// <para>Equality between items is determined by the comparison instance or delegate used
            /// to create the bag.</para>
            /// <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.</param>
            /// <returns>True if the bag already contained an item equal to <paramref name="item"/> (which was replaced), false 
            /// otherwise.</returns>
            public sealed override void Add(T item)
            {
                if (!ItemInView(item))
                    throw new ArgumentException(Strings.OutOfViewRange, "item");
                else
                    myBag.Add(item);
            }

            /// <summary>
            /// Searches the underlying bag for an item equal to <paramref name="item"/>, and if found,
            /// removes it from the bag. If not found, the bag is unchanged. If the item is outside
            /// the range of this view, 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>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, or
            /// was outside the range of this view.</returns>
            public sealed override bool Remove(T item)
            {
                if (!ItemInView(item))
                    return false;
                else
                    return myBag.Remove(item);
            }

            /// <summary>
            /// Determines if this view of the bag contains an item equal to <paramref name="item"/>. The bag
            /// is not changed. If 
            /// </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"/>, and <paramref name="item"/> is within
            /// the range of this view. False otherwise.</returns>
            public sealed override bool Contains(T item)
            {
                if (!ItemInView(item))
                    return false;
                else
                    return myBag.Contains(item);
            }

            /// <summary>
            /// Get the first index of the given item in the view. The smallest item in the view has index 0,
            /// the next smallest item has index 1, and the largest item has index Count-1. 
            /// </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 view equal to <paramref name="item"/>, or -1 if the item is not present
            /// in the view.</returns>
            public int IndexOf(T item)
            {
                if (entireTree) {
                    if (reversed) {
                        int indexInSet = myBag.tree.FindIndex(item, false);
                        if (indexInSet < 0)
                            return -1;

                        return myBag.Count - 1 - indexInSet;
                    }
                    else {
                        return myBag.tree.FindIndex(item, true);
                    }
                }
                else {
                    T dummy;

                    if (!ItemInView(item))
                        return -1;

                    if (reversed) {
                        int indexInSet = myBag.tree.FindIndex(item, false);
                        if (indexInSet < 0)
                            return -1;
                        int indexOfEnd = myBag.tree.LastItemInRange(rangeTester, out dummy);
                        return indexOfEnd - indexInSet;

                    }
                    else {
                        int indexInSet = myBag.tree.FindIndex(item, true);
                        if (indexInSet < 0)
                            return -1;
                        int indexOfStart = myBag.tree.FirstItemInRange(rangeTester, out dummy);
                        return indexInSet - indexOfStart;
                    }
                }
            }

            /// <summary>
            /// Get the last index of the given item in the view. The smallest item in the view has index 0,
            /// the next smallest item has index 1, and the largest item has index Count-1. 
            /// </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 view equal to <paramref name="item"/>, or -1 if the item is not present
            /// in the view.</returns>
            public int LastIndexOf(T item)
            {
                if (entireTree) {
                    if (reversed) {
                        int indexInSet = myBag.tree.FindIndex(item, true);
                        if (indexInSet < 0)
                            return -1;

                        return myBag.Count - 1 - indexInSet;
                    }
                    else {
                        return myBag.tree.FindIndex(item, false);
                    }
                }
                else {
                    T dummy;

                    if (!ItemInView(item))
                        return -1;

                    if (reversed) {
                        int indexInSet = myBag.tree.FindIndex(item, true);
                        if (indexInSet < 0)
                            return -1;
                        int indexOfEnd = myBag.tree.LastItemInRange(rangeTester, out dummy);
                        return indexOfEnd - indexInSet;

                    }
                    else {
                        int indexInSet = myBag.tree.FindIndex(item, false);
                        if (indexInSet < 0)
                            return -1;
                        int indexOfStart = myBag.tree.FirstItemInRange(rangeTester, out dummy);
                        return indexInSet - indexOfStart;
                    }
                }
            }

            /// <summary>
            /// Get the item by its index in the sorted order. The smallest item in the view 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 (entireTree) {
                        if (reversed) {
                            return myBag[myBag.Count - 1 - index];
                        }
                        else {
                            return myBag[index];
                        }
                    }
                    else {
                        T dummy;
                        int firstIndex = myBag.tree.FirstItemInRange(rangeTester, out dummy);
                        int lastIndex = myBag.tree.LastItemInRange(rangeTester, out dummy);
                        if (firstIndex < 0 || lastIndex < 0 || index < 0 || index >= (lastIndex - firstIndex + 1))
                            throw new ArgumentOutOfRangeException("index");

                        if (reversed)
                            return myBag[lastIndex - index];
                        else
                            return myBag[firstIndex + index];
                    }
                }
            }

            /// <summary>
            /// Get a read-only list view of the items in this view. The
            /// items in the list are in sorted order, with the smallest item
            /// at index 0. This view does not copy any data, and reflects any
            /// changes to the underlying OrderedSet.
            /// </summary>
            /// <returns>A read-only IList&lt;T&gt; view onto this view.</returns>
            public IList<T> AsList()
            {
                return new ListView(myBag, rangeTester, entireTree, reversed);
            }

            /// <summary>
            /// Creates a new View that has the same items as this view, in the reversed order.
            /// </summary>
            /// <returns>A new View that has the reversed order of this view, with the same upper 
            /// and lower bounds.</returns>
            public View Reversed()
            {
                return new View(myBag, rangeTester, entireTree, !reversed);
            }

            /// <summary>
            /// Returns the first item in this view: the item
            /// that would appear first if the view was enumerated. 
            /// </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 view. </returns>
            /// <exception cref="InvalidOperationException">The view has no items in it.</exception>
            public T GetFirst()
            {
                T item;
                int found;

                if (reversed)
                    found = myBag.tree.LastItemInRange(rangeTester, out item);
                else
                    found = myBag.tree.FirstItemInRange(rangeTester, out item);

                if (found < 0)
                    throw new InvalidOperationException(Strings.CollectionIsEmpty);

                return item;
            }

            /// <summary>
            /// Returns the last item in the view: the item
            /// that would appear last if the view was enumerated. 
            /// </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 view. </returns>
            /// <exception cref="InvalidOperationException">The view has no items in it.</exception>
            public T GetLast()
            {
                T item;
                int found;

                if (reversed)
                    found = myBag.tree.FirstItemInRange(rangeTester, out item);
                else
                    found = myBag.tree.LastItemInRange(rangeTester, out item);

                if (found < 0)
                    throw new InvalidOperationException(Strings.CollectionIsEmpty);

                return item;
            }
        }

        #endregion
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Eclipse Public License 1.0

About the Author

Stefan Bocutiu
Software Developer (Senior) Lab49
United Kingdom United Kingdom
No Biography provided

| Advertise | Privacy | Mobile
Web03 | 2.8.140721.1 | Last Updated 29 Jan 2009
Article Copyright 2009 by Stefan Bocutiu
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid