OrderedDictionary.cs :  » Development » TULP2G » Wintellect » PowerCollections » C# / CSharp Open Source

Home
C# / CSharp Open Source
1.2.6.4 mono .net core
2.2.6.4 mono core
3.Aspect Oriented Frameworks
4.Bloggers
5.Build Systems
6.Business Application
7.Charting Reporting Tools
8.Chat Servers
9.Code Coverage Tools
10.Content Management Systems CMS
11.CRM ERP
12.Database
13.Development
14.Email
15.Forum
16.Game
17.GIS
18.GUI
19.IDEs
20.Installers Generators
21.Inversion of Control Dependency Injection
22.Issue Tracking
23.Logging Tools
24.Message
25.Mobile
26.Network Clients
27.Network Servers
28.Office
29.PDF
30.Persistence Frameworks
31.Portals
32.Profilers
33.Project Management
34.RSS RDF
35.Rule Engines
36.Script
37.Search Engines
38.Sound Audio
39.Source Control
40.SQL Clients
41.Template Engines
42.Testing
43.UML
44.Web Frameworks
45.Web Service
46.Web Testing
47.Wiki Engines
48.Windows Presentation Foundation
49.Workflows
50.XML Parsers
C# / C Sharp
C# / C Sharp by API
C# / CSharp Tutorial
C# / CSharp Open Source » Development » TULP2G 
TULP2G » Wintellect » PowerCollections » OrderedDictionary.cs
//******************************
// 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;
using System.Collections.Generic;

namespace Wintellect.PowerCollections{
  /// <summary>
  /// OrderedDictionary&lt;TKey, TValue&gt; is a collection that maps keys of type TKey
  /// to values of type TValue. The keys are maintained in a sorted order, and at most one value
  /// is permitted for each key.
  /// </summary>
  /// <remarks>
  /// <p>The keys are compared in one of three ways. If TKey implements IComparable&lt;TKey&gt; or IComparable,
  /// then the CompareTo method of that interface will be used to compare elements. Alternatively, a comparison
  /// function can be passed in either as a delegate, or as an instance of IComparer&lt;TKey&gt;.</p>
  /// <p>OrderedDictionary is implemented as a balanced binary tree. Inserting, deleting, and looking up an
  /// an element all are done in log(N) type, where N is the number of keys in the tree.</p>
  /// <p><see cref="Dictionary&lt;TKey,TValue&gt;"/> is similar, but uses hashing instead of comparison, and does not maintain
  /// the keys in sorted order.</p>
  ///</remarks>
  ///<seealso cref="Dictionary&lt;TKey,TValue&gt;"/>
    [Serializable]
  public class OrderedDictionary<TKey,TValue>: DictionaryBase<TKey,TValue>, ICloneable
  {
        // The comparer for comparing keys. This is saved to return from the Comparer property,
        // but is otherwise not used.
        private IComparer<TKey> keyComparer;

    // The comparer for comparing key-value pairs.
    private IComparer<KeyValuePair<TKey,TValue>> pairComparer;

    private RedBlackTree<KeyValuePair<TKey,TValue>> tree;

        /// <summary>
        /// Helper function to create a new KeyValuePair struct.
        /// </summary>
        /// <param name="key">The key.</param>
        /// <param name="value">The value.</param>
        /// <returns>A new KeyValuePair.</returns>
        private static KeyValuePair<TKey,TValue> NewPair(TKey key, TValue value) {
            KeyValuePair<TKey, TValue> pair = new KeyValuePair<TKey,TValue>(key,value);
            return pair;
        }

        /// <summary>
        /// Helper function to create a new KeyValuePair struct with a default value.
        /// </summary>
        /// <param name="key">The key.</param>
        /// <returns>A new KeyValuePair.</returns>
        private static KeyValuePair<TKey, TValue> NewPair(TKey key)
        {
            KeyValuePair<TKey, TValue> pair = new KeyValuePair<TKey,TValue>(key, default(TValue));
            return pair;
        }

        /// <summary>
        /// Creates a new OrderedDictionary. The TKey must implemented IComparable&lt;TKey&gt;
    /// or IComparable. 
    /// The CompareTo method of this interface will be used to compare keys in this dictionary.
    /// </summary>
    /// <exception cref="InvalidOperationException">TKey does not implement IComparable&lt;TKey&gt;.</exception>
    public OrderedDictionary() :
            this(Comparers.DefaultComparer<TKey>())
    {
    }

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

        /// <summary>
    /// Creates a new OrderedDictionary. The passed delegate will be used to compare keys in this dictionary.
    /// </summary>
    /// <param name="comparison">A delegate to a method that will be used to compare keys.</param>
    public OrderedDictionary(Comparison<TKey> comparison) :
            this(null, Comparers.ComparerFromComparison<TKey>(comparison), Comparers.ComparerKeyValueFromComparisonKey<TKey, TValue>(comparison))
    {
        }

        /// <summary>
        /// <para>Creates a new OrderedDictionary. The TKey must implemented IComparable&lt;TKey&gt;
        /// or IComparable. 
        /// The CompareTo method of this interface will be used to compare keys in this dictionary.</para>
        /// <para>A collection and keys and values (typically another dictionary) is used to initialized the 
        /// contents of the dictionary.</para>
        /// </summary>
        /// <param name="keysAndValues">A collection of keys and values whose contents are used to initialized the dictionary.</param>
        /// <exception cref="InvalidOperationException">TKey does not implement IComparable&lt;TKey&gt;.</exception>
        public OrderedDictionary(IEnumerable<KeyValuePair<TKey,TValue>> keysAndValues)
            : this(keysAndValues, Comparers.DefaultComparer<TKey>())
        {
        }

        /// <summary>
        /// <para>Creates a new OrderedDictionary. The Compare method of the passed comparison object
        /// will be used to compare keys in this dictionary.</para>
        /// <para>A collection and keys and values (typically another dictionary) is used to initialized the 
        /// contents of the dictionary.</para>
        /// </summary>
        /// <remarks>
        /// The GetHashCode and Equals methods of the provided IComparer&lt;TKey&gt; will never
        /// be called, and need not be implemented.</remarks>
        /// <param name="keysAndValues">A collection of keys and values whose contents are used to initialized the dictionary.</param>
        /// <param name="comparer">An instance of IComparer&lt;TKey&gt; that will be used to compare keys.</param>
        public OrderedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> keysAndValues, IComparer<TKey> comparer)
            : this(keysAndValues, comparer, Comparers.ComparerKeyValueFromComparerKey<TKey, TValue>(comparer))
        {
            if (comparer == null)
                throw new ArgumentNullException("comparer");
        }

        /// <summary>
        /// <para>Creates a new OrderedDictionary. The passed delegate will be used to compare keys in this dictionary.</para>
        /// <para>A collection and keys and values (typically another dictionary) is used to initialized the 
        /// contents of the dictionary.</para>
        /// </summary>
        /// <param name="keysAndValues">A collection of keys and values whose contents are used to initialized the dictionary.</param>
        /// <param name="comparison">A delegate to a method that will be used to compare keys.</param>
        public OrderedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> keysAndValues, Comparison<TKey> comparison)
            : this(keysAndValues, Comparers.ComparerFromComparison<TKey>(comparison), Comparers.ComparerKeyValueFromComparisonKey<TKey, TValue>(comparison))
        {
        }

        /// <summary>
    /// Creates a new OrderedDictionary. The passed comparer 
    /// will be used to compare key-value pairs in this dictionary. Used internally  
    /// from other constructors.
    /// </summary>
        /// <param name="keysAndValues">A collection of keys and values whose contents are used to initialized the dictionary.</param>
        /// <param name="keyComparer">An IComparer that will be used to compare keys.</param>
        /// <param name="pairComparer">An IComparer that will be used to compare key-value pairs.</param>
        private OrderedDictionary(IEnumerable<KeyValuePair<TKey,TValue>> keysAndValues, IComparer<TKey> keyComparer, IComparer<KeyValuePair<TKey,TValue>> pairComparer)
    {
            this.keyComparer = keyComparer;
            this.pairComparer = pairComparer;
            tree = new RedBlackTree<KeyValuePair<TKey,TValue>>(this.pairComparer);

            if (keysAndValues != null)
                AddMany(keysAndValues);
    }

        /// <summary>
        /// Creates a new OrderedDictionary. The passed comparison delegate 
        /// will be used to compare keys in this dictionary, and the given tree is used. Used internally for Clone().
        /// </summary>
        /// <param name="keyComparer">An IComparer that will be used to compare keys.</param>
        /// <param name="pairComparer">A delegate to a method that will be used to compare key-value pairs.</param>
        /// <param name="tree">RedBlackTree that contains the data for the dictionary.</param>
        private OrderedDictionary(IComparer<TKey> keyComparer, IComparer<KeyValuePair<TKey, TValue>> pairComparer, RedBlackTree<KeyValuePair<TKey, TValue>> tree)
        {
            this.keyComparer = keyComparer;
            this.pairComparer = pairComparer;
            this.tree = tree;
        }

        /// <summary>
        /// Makes a shallow clone of this dictionary; i.e., if keys or values of the
    /// dictionary are reference types, then they are not cloned. If TKey or TValue is a value type,
    /// then each element is copied as if by simple assignment.
    /// </summary>
        /// <remarks>Cloning the dictionary takes time O(N), where N is the number of keys in the dictionary.</remarks>
        /// <returns>The cloned dictionary.</returns>
        public OrderedDictionary<TKey,TValue> Clone()
    {
      OrderedDictionary<TKey,TValue> newDict = new OrderedDictionary<TKey,TValue>(keyComparer, pairComparer, tree.Clone());
      return newDict;
    }

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

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

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

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

            OrderedDictionary<TKey, TValue> newDict = new OrderedDictionary<TKey, TValue>(null, keyComparer, pairComparer);

            foreach (KeyValuePair<TKey, TValue> pair in tree) {
                // Clone the key and value parts of the pair. Value types can be cloned
                // by just copying them, otherwise, ICloneable is used.
                TKey keyClone;
                TValue valueClone;

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

                if (valueIsValueType)
                    valueClone = pair.Value;
                else {
                    if (pair.Value == null)
                        valueClone = default(TValue);   // Really null, because we know TKey isn't a value type.
                    else
                        valueClone = (TValue)(((ICloneable)pair.Value).Clone());
                }

                newDict.Add(keyClone, valueClone);
            }

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


        /// <summary>
        /// Returns a View collection that can be used for enumerating the keys and values in the collection in 
        /// reversed order.
        /// </summary>
        ///<remarks>
        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
        ///<code>
        /// foreach(KeyValuePair&lt;TKey, TValue&gt; pair in dictionary.Reversed()) {
        ///    // process pair
        /// }
        ///</code></p>
        /// <p>If an entry is added to or deleted from the dictionary 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 dictionary, and the operation takes constant time.</p>
        ///</remarks>
        /// <returns>An OrderedDictionary.View of key-value pairs in reverse order.</returns>
        public View Reversed()
        {
            return new View(this, tree.EntireRangeTester, true, true);
        }

        /// <summary>
        /// Returns a collection that can be used for enumerating some of the keys and values in the collection. 
        /// Only keys that are greater than <paramref name="from"/> and 
        /// less than <paramref name="to"/> are included. The keys are enumerated in sorted order.
        /// Keys 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>The sorted order of the keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</p>
        ///<p>Typically, this property is used in conjunction with a foreach statement. For example:</p>
        ///<code>
        /// foreach(KeyValuePair&lt;TKey, TValue&gt; pair in dictionary.Range(from, true, to, false)) {
        ///    // process pair
        /// }
        ///</code>
        ///<p>Calling Range does not copy the data in the dictionary, 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--keys equal to the lower bound will
        /// be included in the range. If false, the lower bound is exclusive--keys 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--keys equal to the upper bound will
        /// be included in the range. If false, the upper bound is exclusive--keys equal to the upper bound will not
        /// be included in the range.</param>
        /// <returns>An OrderedDictionary.View of key-value pairs in the given range.</returns>
        public View Range(TKey from, bool fromInclusive, TKey to, bool toInclusive)
        {
            return new View(this, tree.DoubleBoundedRangeTester(NewPair(from), fromInclusive, NewPair(to), toInclusive), false, false);
        }


        /// <summary>
        /// Returns a collection that can be used for enumerating some of the keys and values in the collection. 
        /// Only keys that are greater than (and optionally, equal to) <paramref name="from"/> are included. 
        /// The keys are enumerated in sorted order. Keys equal to <paramref name="from"/> can be included
        /// or excluded depending on the <paramref name="fromInclusive"/> parameter.
        /// </summary>
        ///<remarks>
        ///<p>The sorted order of the keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</p>
        ///<p>Typically, this property is used in conjunction with a foreach statement. For example:</p>
        ///<code>
        /// foreach(KeyValuePair&lt;TKey, TValue&gt; pair in dictionary.RangeFrom(from, true)) {
        ///    // process pair
        /// }
        ///</code>
        ///<p>Calling RangeFrom does not copy of the data in the dictionary, 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--keys equal to the lower bound will
        /// be included in the range. If false, the lower bound is exclusive--keys equal to the lower bound will not
        /// be included in the range.</param>
        /// <returns>An OrderedDictionary.View of key-value pairs in the given range.</returns>
        public View RangeFrom(TKey from, bool fromInclusive)
        {
            return new View(this, tree.LowerBoundedRangeTester(NewPair(from), fromInclusive), false, false);
        }

        /// <summary>
        /// Returns a collection that can be used for enumerating some of the keys and values in the collection. 
        /// 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>The sorted order of the keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</p>
        ///<p>Typically, this property is used in conjunction with a foreach statement. For example:</p>
        ///<code>
        /// foreach(KeyValuePair&lt;TKey, TValue&gt; pair in dictionary.RangeFrom(from, false)) {
        ///    // process pair
        /// }
        ///</code>
        ///<p>Calling RangeTo does not copy the data in the dictionary, 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--keys equal to the upper bound will
        /// be included in the range. If false, the upper bound is exclusive--keys equal to the upper bound will not
        /// be included in the range.</param>
        /// <returns>An OrderedDictionary.View of key-value pairs in the given range.</returns>
        public View RangeTo(TKey to, bool toInclusive)
        {
            return new View(this, tree.UpperBoundedRangeTester(NewPair(to), toInclusive), false, false);
        }

    #region IDictionary<TKey,TValue> Members

    /// <summary>
    /// Removes the key (and associated value) from the collection that is equal to the passed in key. If
    /// no key in the dictionary is equal to the passed key, false is returned and the 
    /// dictionary is unchanged.
    /// </summary>
    /// <remarks>Equality between keys is determined by the comparison instance or delegate used
    /// to create the dictionary.</remarks>
    /// <param name="key">The key to remove.</param>
    /// <returns>True if the key was found and removed. False if the key was not found.</returns>
        public sealed override bool Remove(TKey key)
        {
            KeyValuePair<TKey, TValue> keyPair = NewPair(key);
      KeyValuePair<TKey, TValue> item;
      return tree.Delete(keyPair, true, out item);
    }

    /// <summary>
    /// Removes all keys and values from the dictionary.
    /// </summary>
        /// <remarks>Clearing the dictionary takes a constant amount of time, regardless of the number of keys 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<KeyValuePair<TKey,TValue>>(pairComparer);
    }

        /// <summary>
        /// Finds a key in the dictionary. If the dictionary already contains
        /// a key equal to the passed key, then the existing value is returned via value. If the dictionary
        /// doesn't contain that key, then value is associated with that key.
        /// </summary>
        /// <remarks><para> between keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</para>
        /// <para>This method takes time O(log N), where N is the number of keys in the dictionary. If a value is added, It is more efficient than
        /// calling TryGetValue followed by Add, because the dictionary is not searched twice.</para></remarks>
        /// <param name="key">The new key. </param>
        /// <param name="value">The new value to associated with that key, if the key isn't present. If the key was present, 
        /// returns the exist value associated with that key.</param>
        /// <returns>True if key was already present, false if key wasn't present (and a new value was added).</returns>
        public bool GetValueElseAdd(TKey key, ref TValue value)
        {
            KeyValuePair<TKey, TValue> pair = NewPair(key, value);
            KeyValuePair<TKey, TValue> old;

            bool added = tree.Insert(pair, DuplicatePolicy.DoNothing, out old);
            if (!added) 
                value = old.Value;
            return !added;
        }

        /// <summary>
        /// Adds a new key and value to the dictionary. If the dictionary already contains
        /// a key equal to the passed key, then an ArgumentException is thrown
        /// </summary>
        /// <remarks>
        /// <para>Equality between keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</para>
        /// <para>Adding an key and value takes time O(log N), where N is the number of keys in the dictionary.</para></remarks>
        /// <param name="key">The new key. "null" is a valid key value.</param>
        /// <param name="value">The new value to associated with that key.</param>
        /// <exception cref="ArgumentException">key is already present in the dictionary</exception>
        public sealed override void Add(TKey key, TValue value)
        {
            KeyValuePair<TKey, TValue> pair = NewPair(key, value);
            KeyValuePair<TKey, TValue> dummy;

            bool added = tree.Insert(pair, DuplicatePolicy.DoNothing, out dummy);
            if (! added) 
                throw new ArgumentException(Strings.KeyAlreadyPresent, "key");
        }

        /// <summary>
        /// Changes the value associated with a given key. If the dictionary does not contain
        /// a key equal to the passed key, then an ArgumentException is thrown.
        /// </summary>
        /// <remarks>
        /// <p>Unlike adding or removing an element, changing the value associated with a key
        /// can be performed while an enumeration (foreach) on the the dictionary is in progress.</p>
        /// <p>Equality between keys is determined by the comparison instance or delegate used
        /// to create the dictionary.</p>
        /// <p>Replace takes time O(log N), where N is the number of entries in the dictionary.</p></remarks>
        /// <param name="key">The new key. </param>
        /// <param name="value">The new value to associated with that key.</param>
        /// <exception cref="KeyNotFoundException">key is not present in the dictionary</exception>
        public void Replace(TKey key, TValue value)
        {
            KeyValuePair<TKey, TValue> pair = NewPair(key, value);
            KeyValuePair<TKey, TValue> dummy;

            bool found = tree.Find(pair, true, true, out dummy);
            if (!found)
                throw new KeyNotFoundException(Strings.KeyNotFound);   
        }

        /// <summary>
        /// Adds multiple key-value pairs to a dictionary. If a key exists in both the current instance and dictionaryToAdd,
        /// then the value is updated with the value from <paramref name="keysAndValues>"/> (no exception is thrown).
        /// Since IDictionary&lt;TKey,TValue&gt; inherits from IEnumerable&lt;KeyValuePair&lt;TKey,TValue&gt;&gt;, this
        /// method can be used to merge one dictionary into another.
        /// </summary>
        /// <remarks>AddMany takes time O(M log (N+M)), where M is the size of <paramref name="keysAndValues>"/>, and N is the size of
        /// this dictionary.</remarks>
        /// <param name="keysAndValues">A collection of keys and values whose contents are added to the current dictionary.</param>
        public void AddMany(IEnumerable<KeyValuePair<TKey, TValue>> keysAndValues)
        {
            if (keysAndValues == null)
                throw new ArgumentNullException("keysAndValues");

            foreach (KeyValuePair<TKey, TValue> pair in keysAndValues) {
                this[pair.Key] = pair.Value;
            }
        }

        /// <summary>
        /// Removes all the keys found in another collection (such as an array or List&lt;TKey&gt;). Each key in keyCollectionToRemove
        /// is removed from the dictionary. Keys that are not present are ignored.
        /// </summary>
        /// <remarks>RemoveMany takes time O(M log N), where M is the size of keyCollectionToRemove, and N is this
        /// size of this collection.</remarks>
        /// <returns>The number of keys removed from the dictionary.</returns>
        /// <param name="keyCollectionToRemove">A collection of keys to remove from the dictionary.</param>
        public int RemoveMany(IEnumerable<TKey> keyCollectionToRemove)
        {
            if (keyCollectionToRemove == null)
                throw new ArgumentNullException("keyCollectionToRemove");

            int count = 0;

            foreach (TKey key in keyCollectionToRemove) {
                if (this.Remove(key))
                    ++count;
            }

            return count;
        }

    /// <summary>
    /// Gets or sets the value associated with a given key. When getting a value, if this
    /// key is not found in the collection, then an ArgumentException is thrown. When setting
    /// a value, the value replaces any existing value in the dictionary.
    /// </summary>
        /// <remarks>The indexer takes time O(log N), where N is the number of entries in the dictionary.</remarks>
        /// <value>The value associated with the key</value>
        /// <exception cref="ArgumentException">A value is being retrieved, and the key is not present in the dictionary.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="key"/> is null.</exception>
        public sealed override TValue this[TKey key]
        {
      get
      {
                KeyValuePair<TKey,TValue> pairFound;
        bool found;
        
        found = tree.Find(NewPair(key), false, false, out pairFound);
        if (found)
          return pairFound.Value;
        else
          throw new KeyNotFoundException(Strings.KeyNotFound);
      }
      set
      {
                KeyValuePair<TKey, TValue> dummy;
                tree.Insert(NewPair(key, value),
                                DuplicatePolicy.ReplaceLast, out dummy);
      }
    }

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

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

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

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

        #endregion

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

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

#endregion

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

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

    #endregion

    #region ICloneable Members

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

    #endregion

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

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

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

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

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

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

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

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

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

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

            /// <summary>
            /// Creates a new View that has the same keys and values as this, in the reversed order.
            /// </summary>
            /// <returns>A new View that has the reversed order of this view.</returns>
            public View Reversed()
            {
                return new View(myDictionary, rangeTester, entireTree, !reversed);
            }
        }
    }
}
www.java2v.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.