-#if NET_2_0
-/*\r
- Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\r
- Permission is hereby granted, free of charge, to any person obtaining a copy\r
- of this software and associated documentation files (the "Software"), to deal\r
- in the Software without restriction, including without limitation the rights\r
- to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
- copies of the Software, and to permit persons to whom the Software is\r
- furnished to do so, subject to the following conditions:\r
- \r
- The above copyright notice and this permission notice shall be included in\r
- all copies or substantial portions of the Software.\r
- \r
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
- IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
- FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
- AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
- LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
- OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
- SOFTWARE.\r
-*/\r
-\r
-using System;\r
-using System.Diagnostics;\r
-using SCG = System.Collections.Generic;\r
-namespace C5\r
-{\r
- /// <summary>\r
- /// An entry in a dictionary from K to V.\r
- /// </summary>\r
- [Serializable]\r
- public struct KeyValuePair<K, V> : IEquatable<KeyValuePair<K, V>>, IShowable\r
- {\r
- /// <summary>\r
- /// The key field of the entry\r
- /// </summary>\r
- public K Key;\r
-\r
- /// <summary>\r
- /// The value field of the entry\r
- /// </summary>\r
- public V Value;\r
-\r
- /// <summary>\r
- /// Create an entry with specified key and value\r
- /// </summary>\r
- /// <param name="key">The key</param>\r
- /// <param name="value">The value</param>\r
- public KeyValuePair(K key, V value) { Key = key; Value = value; }\r
-\r
-\r
- /// <summary>\r
- /// Create an entry with a specified key. The value will be the default value of type <code>V</code>.\r
- /// </summary>\r
- /// <param name="key">The key</param>\r
- public KeyValuePair(K key) { Key = key; Value = default(V); }\r
-\r
-\r
- /// <summary>\r
- /// Pretty print an entry\r
- /// </summary>\r
- /// <returns>(key, value)</returns>\r
- [Tested]\r
- public override string ToString() { return "(" + Key + ", " + Value + ")"; }\r
-\r
-\r
- /// <summary>\r
- /// Check equality of entries. \r
- /// </summary>\r
- /// <param name="obj">The other object</param>\r
- /// <returns>True if obj is an entry of the same type and has the same key and value</returns>\r
- [Tested]\r
- public override bool Equals(object obj)\r
- {\r
- if (!(obj is KeyValuePair<K, V>))\r
- return false;\r
- KeyValuePair<K, V> other = (KeyValuePair<K, V>)obj;\r
- return Equals(other);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Get the hash code of the pair.\r
- /// </summary>\r
- /// <returns>The hash code</returns>\r
- [Tested]\r
- public override int GetHashCode() { return EqualityComparer<K>.Default.GetHashCode(Key) + 13984681 * EqualityComparer<V>.Default.GetHashCode(Value); }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="other"></param>\r
- /// <returns></returns>\r
- public bool Equals(KeyValuePair<K, V> other)\r
- {\r
- return EqualityComparer<K>.Default.Equals(Key, other.Key) && EqualityComparer<V>.Default.Equals(Value, other.Value);\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="pair1"></param>\r
- /// <param name="pair2"></param>\r
- /// <returns></returns>\r
- public static bool operator ==(KeyValuePair<K, V> pair1, KeyValuePair<K, V> pair2) { return pair1.Equals(pair2); }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="pair1"></param>\r
- /// <param name="pair2"></param>\r
- /// <returns></returns>\r
- public static bool operator !=(KeyValuePair<K, V> pair1, KeyValuePair<K, V> pair2) { return !pair1.Equals(pair2); }\r
-\r
- #region IShowable Members\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="stringbuilder"></param>\r
- /// <param name="formatProvider"></param>\r
- /// <param name="rest"></param>\r
- /// <returns></returns>\r
- public bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)\r
- {\r
- if (rest < 0)\r
- return false;\r
- if (!Showing.Show(Key, stringbuilder, ref rest, formatProvider))\r
- return false;\r
- stringbuilder.Append(" => ");\r
- rest -= 4;\r
- if (!Showing.Show(Value, stringbuilder, ref rest, formatProvider))\r
- return false;\r
- return rest >= 0;\r
- }\r
- #endregion\r
-\r
- #region IFormattable Members\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="format"></param>\r
- /// <param name="formatProvider"></param>\r
- /// <returns></returns>\r
- public string ToString(string format, IFormatProvider formatProvider)\r
- {\r
- return Showing.ShowString(this, format, formatProvider);\r
- }\r
-\r
- #endregion\r
- }\r
-\r
-\r
-\r
- /// <summary>\r
- /// Default comparer for dictionary entries in a sorted dictionary.\r
- /// Entry comparisons only look at keys and uses an externally defined comparer for that.\r
- /// </summary>\r
- [Serializable]\r
- public class KeyValuePairComparer<K, V> : SCG.IComparer<KeyValuePair<K, V>>\r
- {\r
- SCG.IComparer<K> comparer;\r
-\r
-\r
- /// <summary>\r
- /// Create an entry comparer for a item comparer of the keys\r
- /// </summary>\r
- /// <param name="comparer">Comparer of keys</param>\r
- public KeyValuePairComparer(SCG.IComparer<K> comparer)\r
- {\r
- if (comparer == null)\r
- throw new NullReferenceException();\r
- this.comparer = comparer;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Compare two entries\r
- /// </summary>\r
- /// <param name="entry1">First entry</param>\r
- /// <param name="entry2">Second entry</param>\r
- /// <returns>The result of comparing the keys</returns>\r
- [Tested]\r
- public int Compare(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)\r
- { return comparer.Compare(entry1.Key, entry2.Key); }\r
- }\r
-\r
-\r
-\r
- /// <summary>\r
- /// Default equalityComparer for dictionary entries.\r
- /// Operations only look at keys and uses an externaly defined equalityComparer for that.\r
- /// </summary>\r
- [Serializable]\r
- public sealed class KeyValuePairEqualityComparer<K, V> : SCG.IEqualityComparer<KeyValuePair<K, V>>\r
- {\r
- SCG.IEqualityComparer<K> keyequalityComparer;\r
-\r
-\r
- /// <summary>\r
- /// Create an entry equalityComparer using the default equalityComparer for keys\r
- /// </summary>\r
- public KeyValuePairEqualityComparer() { keyequalityComparer = EqualityComparer<K>.Default; }\r
-\r
-\r
- /// <summary>\r
- /// Create an entry equalityComparer from a specified item equalityComparer for the keys\r
- /// </summary>\r
- /// <param name="keyequalityComparer">The key equalityComparer</param>\r
- public KeyValuePairEqualityComparer(SCG.IEqualityComparer<K> keyequalityComparer)\r
- {\r
- if (keyequalityComparer == null)\r
- throw new NullReferenceException("Key equality comparer cannot be null");\r
- this.keyequalityComparer = keyequalityComparer;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Get the hash code of the entry\r
- /// </summary>\r
- /// <param name="entry">The entry</param>\r
- /// <returns>The hash code of the key</returns>\r
- [Tested]\r
- public int GetHashCode(KeyValuePair<K, V> entry) { return keyequalityComparer.GetHashCode(entry.Key); }\r
-\r
-\r
- /// <summary>\r
- /// Test two entries for equality\r
- /// </summary>\r
- /// <param name="entry1">First entry</param>\r
- /// <param name="entry2">Second entry</param>\r
- /// <returns>True if keys are equal</returns>\r
- [Tested]\r
- public bool Equals(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)\r
- { return keyequalityComparer.Equals(entry1.Key, entry2.Key); }\r
- }\r
-\r
-\r
-\r
- /// <summary>\r
- /// A base class for implementing a dictionary based on a set collection implementation.\r
- /// <i>See the source code for <see cref="T:C5.HashDictionary`2"/> for an example</i>\r
- /// \r
- /// </summary>\r
- [Serializable]\r
- public abstract class DictionaryBase<K, V> : CollectionValueBase<KeyValuePair<K, V>>, IDictionary<K, V>\r
- {\r
- /// <summary>\r
- /// The set collection of entries underlying this dictionary implementation\r
- /// </summary>\r
- protected ICollection<KeyValuePair<K, V>> pairs;\r
-\r
- SCG.IEqualityComparer<K> keyequalityComparer;\r
-\r
- #region Events\r
- ProxyEventBlock<KeyValuePair<K, V>> eventBlock;\r
-\r
- /// <summary>\r
- /// The change event. Will be raised for every change operation on the collection.\r
- /// </summary>\r
- public override event CollectionChangedHandler<KeyValuePair<K, V>> CollectionChanged\r
- {\r
- add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionChanged += value; }\r
- remove { if (eventBlock != null) eventBlock.CollectionChanged -= value; }\r
- }\r
-\r
- /// <summary>\r
- /// The change event. Will be raised for every change operation on the collection.\r
- /// </summary>\r
- public override event CollectionClearedHandler<KeyValuePair<K, V>> CollectionCleared\r
- {\r
- add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionCleared += value; }\r
- remove { if (eventBlock != null) eventBlock.CollectionCleared -= value; }\r
- }\r
-\r
- /// <summary>\r
- /// The item added event. Will be raised for every individual addition to the collection.\r
- /// </summary>\r
- public override event ItemsAddedHandler<KeyValuePair<K, V>> ItemsAdded\r
- {\r
- add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsAdded += value; }\r
- remove { if (eventBlock != null) eventBlock.ItemsAdded -= value; }\r
- }\r
-\r
- /// <summary>\r
- /// The item added event. Will be raised for every individual removal from the collection.\r
- /// </summary>\r
- public override event ItemsRemovedHandler<KeyValuePair<K, V>> ItemsRemoved\r
- {\r
- add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsRemoved += value; }\r
- remove { if (eventBlock != null) eventBlock.ItemsRemoved -= value; }\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- public override EventTypeEnum ListenableEvents\r
- {\r
- get\r
- {\r
- return EventTypeEnum.Basic;\r
- }\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- public override EventTypeEnum ActiveEvents\r
- {\r
- get\r
- {\r
- return pairs.ActiveEvents;\r
- }\r
- }\r
-\r
- #endregion\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="keyequalityComparer"></param>\r
- public DictionaryBase(SCG.IEqualityComparer<K> keyequalityComparer) {\r
- if (keyequalityComparer == null)\r
- throw new NullReferenceException("Key equality comparer cannot be null");\r
- this.keyequalityComparer = keyequalityComparer; }\r
-\r
- #region IDictionary<K,V> Members\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value></value>\r
- public virtual SCG.IEqualityComparer<K> EqualityComparer { get { return keyequalityComparer; } }\r
-\r
-\r
- /// <summary>\r
- /// Add a new (key, value) pair (a mapping) to the dictionary.\r
- /// </summary>\r
- /// <exception cref="DuplicateNotAllowedException"> if there already is an entry with the same key. </exception>\r
- /// <param name="key">Key to add</param>\r
- /// <param name="value">Value to add</param>\r
- [Tested]\r
- public virtual void Add(K key, V value)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);\r
-\r
- if (!pairs.Add(p))\r
- throw new DuplicateNotAllowedException("Key being added: '" + key + "'");\r
- }\r
-\r
- /// <summary>\r
- /// Add the entries from a collection of <see cref="T:C5.KeyValuePair`2"/> pairs to this dictionary.\r
- /// <para><b>TODO: add restrictions L:K and W:V when the .Net SDK allows it </b></para>\r
- /// </summary>\r
- /// <exception cref="DuplicateNotAllowedException"> \r
- /// If the input contains duplicate keys or a key already present in this dictionary.</exception>\r
- /// <param name="entries"></param>\r
- public virtual void AddAll<L,W>(SCG.IEnumerable<KeyValuePair<L, W>> entries)\r
- where L : K\r
- where W : V\r
- {\r
- foreach (KeyValuePair<L, W> pair in entries)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(pair.Key, pair.Value);\r
- if (!pairs.Add(p))\r
- throw new DuplicateNotAllowedException("Key being added: '" + pair.Key + "'");\r
- }\r
- }\r
-\r
- /// <summary>\r
- /// Remove an entry with a given key from the dictionary\r
- /// </summary>\r
- /// <param name="key">The key of the entry to remove</param>\r
- /// <returns>True if an entry was found (and removed)</returns>\r
- [Tested]\r
- public virtual bool Remove(K key)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
-\r
- return pairs.Remove(p);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove an entry with a given key from the dictionary and report its value.\r
- /// </summary>\r
- /// <param name="key">The key of the entry to remove</param>\r
- /// <param name="value">On exit, the value of the removed entry</param>\r
- /// <returns>True if an entry was found (and removed)</returns>\r
- [Tested]\r
- public virtual bool Remove(K key, out V value)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
-\r
- if (pairs.Remove(p, out p))\r
- {\r
- value = p.Value;\r
- return true;\r
- }\r
- else\r
- {\r
- value = default(V);\r
- return false;\r
- }\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove all entries from the dictionary\r
- /// </summary>\r
- [Tested]\r
- public virtual void Clear() { pairs.Clear(); }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value></value>\r
- public virtual Speed ContainsSpeed { get { return pairs.ContainsSpeed; } }\r
-\r
- /// <summary>\r
- /// Check if there is an entry with a specified key\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <returns>True if key was found</returns>\r
- [Tested]\r
- public virtual bool Contains(K key)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
-\r
- return pairs.Contains(p);\r
- }\r
-\r
- class LiftedEnumerable<H> : SCG.IEnumerable<KeyValuePair<K, V>> where H : K\r
- {\r
- SCG.IEnumerable<H> keys;\r
- public LiftedEnumerable(SCG.IEnumerable<H> keys) { this.keys = keys; }\r
- public SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator() { foreach (H key in keys) yield return new KeyValuePair<K, V>(key); }\r
-\r
- #region IEnumerable Members\r
-\r
- System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()\r
- {\r
- throw new Exception("The method or operation is not implemented.");\r
- }\r
-\r
- #endregion\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="keys"></param>\r
- /// <returns></returns>\r
- public virtual bool ContainsAll<H>(SCG.IEnumerable<H> keys) where H : K\r
- {\r
- return pairs.ContainsAll(new LiftedEnumerable<H>(keys));\r
- }\r
-\r
- /// <summary>\r
- /// Check if there is an entry with a specified key and report the corresponding\r
- /// value if found. This can be seen as a safe form of "val = this[key]".\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <param name="value">On exit, the value of the entry</param>\r
- /// <returns>True if key was found</returns>\r
- [Tested]\r
- public virtual bool Find(K key, out V value)\r
- {\r
- return Find(ref key, out value);\r
- }\r
- /// <summary>\r
- /// Check if there is an entry with a specified key and report the corresponding\r
- /// value if found. This can be seen as a safe form of "val = this[key]".\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <param name="value">On exit, the value of the entry</param>\r
- /// <returns>True if key was found</returns>\r
- public virtual bool Find(ref K key, out V value)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
-\r
- if (pairs.Find(ref p))\r
- {\r
- key = p.Key;\r
- value = p.Value;\r
- return true;\r
- }\r
- else\r
- {\r
- value = default(V);\r
- return false;\r
- }\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Look for a specific key in the dictionary and if found replace the value with a new one.\r
- /// This can be seen as a non-adding version of "this[key] = val".\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <param name="value">The new value</param>\r
- /// <returns>True if key was found</returns>\r
- [Tested]\r
- public virtual bool Update(K key, V value)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);\r
-\r
- return pairs.Update(p);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="key"></param>\r
- /// <param name="value"></param>\r
- /// <param name="oldvalue"></param>\r
- /// <returns></returns>\r
- public virtual bool Update(K key, V value, out V oldvalue)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);\r
-\r
- bool retval = pairs.Update(p, out p);\r
- oldvalue = p.Value;\r
- return retval;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Look for a specific key in the dictionary. If found, report the corresponding value,\r
- /// else add an entry with the key and the supplied value.\r
- /// </summary>\r
- /// <param name="key">On entry the key to look for</param>\r
- /// <param name="value">On entry the value to add if the key is not found.\r
- /// On exit the value found if any.</param>\r
- /// <returns>True if key was found</returns>\r
- [Tested]\r
- public virtual bool FindOrAdd(K key, ref V value)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);\r
-\r
- if (!pairs.FindOrAdd(ref p))\r
- return false;\r
- else\r
- {\r
- value = p.Value;\r
- //key = p.key;\r
- return true;\r
- }\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Update value in dictionary corresponding to key if found, else add new entry.\r
- /// More general than "this[key] = val;" by reporting if key was found.\r
- /// </summary>\r
- /// <param name="key">The key to look for</param>\r
- /// <param name="value">The value to add or replace with.</param>\r
- /// <returns>True if entry was updated.</returns>\r
- [Tested]\r
- public virtual bool UpdateOrAdd(K key, V value)\r
- {\r
- return pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value));\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Update value in dictionary corresponding to key if found, else add new entry.\r
- /// More general than "this[key] = val;" by reporting if key was found and the old value if any.\r
- /// </summary>\r
- /// <param name="key"></param>\r
- /// <param name="value"></param>\r
- /// <param name="oldvalue"></param>\r
- /// <returns></returns>\r
- public virtual bool UpdateOrAdd(K key, V value, out V oldvalue)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);\r
- bool retval = pairs.UpdateOrAdd(p, out p);\r
- oldvalue = p.Value;\r
- return retval;\r
- }\r
-\r
-\r
-\r
- #region Keys,Values support classes\r
-\r
- internal class ValuesCollection : CollectionValueBase<V>, ICollectionValue<V>\r
- {\r
- ICollection<KeyValuePair<K, V>> pairs;\r
-\r
-\r
- internal ValuesCollection(ICollection<KeyValuePair<K, V>> pairs)\r
- { this.pairs = pairs; }\r
-\r
-\r
- public override V Choose() { return pairs.Choose().Value; }\r
-\r
- [Tested]\r
- public override SCG.IEnumerator<V> GetEnumerator()\r
- {\r
- //Updatecheck is performed by the pairs enumerator\r
- foreach (KeyValuePair<K, V> p in pairs)\r
- yield return p.Value;\r
- }\r
-\r
- public override bool IsEmpty { get { return pairs.IsEmpty; } }\r
-\r
- [Tested]\r
- public override int Count { [Tested]get { return pairs.Count; } }\r
-\r
- public override Speed CountSpeed { get { return Speed.Constant; } }\r
- }\r
-\r
-\r
-\r
- internal class KeysCollection : CollectionValueBase<K>, ICollectionValue<K>\r
- {\r
- ICollection<KeyValuePair<K, V>> pairs;\r
-\r
-\r
- internal KeysCollection(ICollection<KeyValuePair<K, V>> pairs)\r
- { this.pairs = pairs; }\r
-\r
- public override K Choose() { return pairs.Choose().Key; }\r
-\r
- [Tested]\r
- public override SCG.IEnumerator<K> GetEnumerator()\r
- {\r
- foreach (KeyValuePair<K, V> p in pairs)\r
- yield return p.Key;\r
- }\r
-\r
- public override bool IsEmpty { get { return pairs.IsEmpty; } }\r
-\r
- [Tested]\r
- public override int Count { [Tested]get { return pairs.Count; } }\r
-\r
- public override Speed CountSpeed { get { return pairs.CountSpeed; } }\r
- }\r
- #endregion\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>A collection containg the all the keys of the dictionary</value>\r
- [Tested]\r
- public virtual ICollectionValue<K> Keys { [Tested]get { return new KeysCollection(pairs); } }\r
-\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>A collection containing all the values of the dictionary</value>\r
- [Tested]\r
- public virtual ICollectionValue<V> Values { [Tested]get { return new ValuesCollection(pairs); } }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- public virtual Fun<K, V> Fun { get { return delegate(K k) { return this[k]; }; } }\r
-\r
- /// <summary>\r
- /// Indexer by key for dictionary. \r
- /// <para>The get method will throw an exception if no entry is found. </para>\r
- /// <para>The set method behaves like <see cref="M:C5.DictionaryBase`2.UpdateOrAdd(`0,`1)"/>.</para>\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"> On get if no entry is found. </exception>\r
- /// <value>The value corresponding to the key</value>\r
- [Tested]\r
- public virtual V this[K key]\r
- {\r
- [Tested]\r
- get\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
-\r
- if (pairs.Find(ref p))\r
- return p.Value;\r
- else\r
- throw new NoSuchItemException("Key '" + key.ToString() + "' not present in Dictionary");\r
- }\r
- [Tested]\r
- set\r
- { pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value)); }\r
- }\r
-\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>True if dictionary is read only</value>\r
- [Tested]\r
- public virtual bool IsReadOnly { [Tested]get { return pairs.IsReadOnly; } }\r
-\r
-\r
- /// <summary>\r
- /// Check the integrity of the internal data structures of this dictionary.\r
- /// </summary>\r
- /// <returns>True if check does not fail.</returns>\r
- [Tested]\r
- public virtual bool Check() { return pairs.Check(); }\r
-\r
- #endregion\r
-\r
- #region ICollectionValue<KeyValuePair<K,V>> Members\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>True if this collection is empty.</value>\r
- public override bool IsEmpty { get { return pairs.IsEmpty; } }\r
-\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>The number of entrues in the dictionary</value>\r
- [Tested]\r
- public override int Count { [Tested]get { return pairs.Count; } }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value>The number of entrues in the dictionary</value>\r
- [Tested]\r
- public override Speed CountSpeed { [Tested]get { return pairs.CountSpeed; } }\r
-\r
- /// <summary>\r
- /// Choose some entry in this Dictionary. \r
- /// </summary>\r
- /// <exception cref="NoSuchItemException">if collection is empty.</exception>\r
- /// <returns></returns>\r
- public override KeyValuePair<K, V> Choose() { return pairs.Choose(); }\r
-\r
- /// <summary>\r
- /// Create an enumerator for the collection of entries of the dictionary\r
- /// </summary>\r
- /// <returns>The enumerator</returns>\r
- [Tested]\r
- public override SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator()\r
- {\r
- return pairs.GetEnumerator(); ;\r
- }\r
-\r
- #endregion\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="stringbuilder"></param>\r
- /// <param name="rest"></param>\r
- /// <param name="formatProvider"></param>\r
- /// <returns></returns>\r
- public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)\r
- {\r
- return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <returns></returns>\r
- public abstract object Clone();\r
-\r
- }\r
-\r
- /// <summary>\r
- /// A base class for implementing a sorted dictionary based on a sorted set collection implementation.\r
- /// <i>See the source code for <see cref="T:C5.TreeDictionary`2"/> for an example</i>\r
- /// \r
- /// </summary>\r
- public abstract class SortedDictionaryBase<K, V> : DictionaryBase<K, V>, ISortedDictionary<K, V>\r
- {\r
- #region Fields\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- protected ISorted<KeyValuePair<K, V>> sortedpairs;\r
- SCG.IComparer<K> keycomparer;\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="keycomparer"></param>\r
- /// <param name="keyequalityComparer"></param>\r
- public SortedDictionaryBase(SCG.IComparer<K> keycomparer, SCG.IEqualityComparer<K> keyequalityComparer) : base(keyequalityComparer) { this.keycomparer = keycomparer; }\r
-\r
- #endregion\r
-\r
- #region ISortedDictionary<K,V> Members\r
-\r
- /// <summary>\r
- /// The key comparer used by this dictionary.\r
- /// </summary>\r
- /// <value></value>\r
- public SCG.IComparer<K> Comparer { get { return keycomparer; } }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <value></value>\r
- public new ISorted<K> Keys { get { return new SortedKeysCollection(this, sortedpairs, keycomparer, EqualityComparer); } }\r
-\r
- /// <summary>\r
- /// Get the entry in the dictionary whose key is the\r
- /// predecessor of a specified key.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"></exception>\r
- /// <param name="key">The key</param>\r
- /// <returns>The entry</returns>\r
- [Tested]\r
- public KeyValuePair<K, V> Predecessor(K key)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
-\r
- return sortedpairs.Predecessor(p);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Get the entry in the dictionary whose key is the\r
- /// weak predecessor of a specified key.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"></exception>\r
- /// <param name="key">The key</param>\r
- /// <returns>The entry</returns>\r
- [Tested]\r
- public KeyValuePair<K, V> WeakPredecessor(K key)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
-\r
- return sortedpairs.WeakPredecessor(p);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Get the entry in the dictionary whose key is the\r
- /// successor of a specified key.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"></exception>\r
- /// <param name="key">The key</param>\r
- /// <returns>The entry</returns>\r
- [Tested]\r
- public KeyValuePair<K, V> Successor(K key)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
-\r
- return sortedpairs.Successor(p);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Get the entry in the dictionary whose key is the\r
- /// weak successor of a specified key.\r
- /// </summary>\r
- /// <exception cref="NoSuchItemException"></exception>\r
- /// <param name="key">The key</param>\r
- /// <returns>The entry</returns>\r
- [Tested]\r
- public KeyValuePair<K, V> WeakSuccessor(K key)\r
- {\r
- return sortedpairs.WeakSuccessor(new KeyValuePair<K, V>(key));\r
- }\r
-\r
- #endregion\r
-\r
- #region ISortedDictionary<K,V> Members\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <returns></returns>\r
- public KeyValuePair<K, V> FindMin()\r
- {\r
- return sortedpairs.FindMin();\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <returns></returns>\r
- public KeyValuePair<K, V> DeleteMin()\r
- {\r
- return sortedpairs.DeleteMin();\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <returns></returns>\r
- public KeyValuePair<K, V> FindMax()\r
- {\r
- return sortedpairs.FindMax();\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <returns></returns>\r
- public KeyValuePair<K, V> DeleteMax()\r
- {\r
- return sortedpairs.DeleteMax();\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="cutter"></param>\r
- /// <param name="lowEntry"></param>\r
- /// <param name="lowIsValid"></param>\r
- /// <param name="highEntry"></param>\r
- /// <param name="highIsValid"></param>\r
- /// <returns></returns>\r
- public bool Cut(IComparable<K> cutter, out KeyValuePair<K, V> lowEntry, out bool lowIsValid, out KeyValuePair<K, V> highEntry, out bool highIsValid)\r
- {\r
- return sortedpairs.Cut(new KeyValuePairComparable(cutter), out lowEntry, out lowIsValid, out highEntry, out highIsValid);\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="bot"></param>\r
- /// <returns></returns>\r
- public IDirectedEnumerable<KeyValuePair<K, V>> RangeFrom(K bot)\r
- {\r
- return sortedpairs.RangeFrom(new KeyValuePair<K, V>(bot));\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="bot"></param>\r
- /// <param name="top"></param>\r
- /// <returns></returns>\r
- public IDirectedEnumerable<KeyValuePair<K, V>> RangeFromTo(K bot, K top)\r
- {\r
- return sortedpairs.RangeFromTo(new KeyValuePair<K, V>(bot), new KeyValuePair<K, V>(top));\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="top"></param>\r
- /// <returns></returns>\r
- public IDirectedEnumerable<KeyValuePair<K, V>> RangeTo(K top)\r
- {\r
- return sortedpairs.RangeTo(new KeyValuePair<K, V>(top));\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <returns></returns>\r
- public IDirectedCollectionValue<KeyValuePair<K, V>> RangeAll()\r
- {\r
- return sortedpairs.RangeAll();\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="items"></param>\r
- public void AddSorted(SCG.IEnumerable<KeyValuePair<K, V>> items)\r
- {\r
- sortedpairs.AddSorted(items);\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="lowKey"></param>\r
- public void RemoveRangeFrom(K lowKey)\r
- {\r
- sortedpairs.RemoveRangeFrom(new KeyValuePair<K, V>(lowKey));\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="lowKey"></param>\r
- /// <param name="highKey"></param>\r
- public void RemoveRangeFromTo(K lowKey, K highKey)\r
- {\r
- sortedpairs.RemoveRangeFromTo(new KeyValuePair<K, V>(lowKey), new KeyValuePair<K, V>(highKey));\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="highKey"></param>\r
- public void RemoveRangeTo(K highKey)\r
- {\r
- sortedpairs.RemoveRangeTo(new KeyValuePair<K, V>(highKey));\r
- }\r
-\r
- #endregion\r
-\r
- class KeyValuePairComparable : IComparable<KeyValuePair<K, V>>\r
- {\r
- IComparable<K> cutter;\r
-\r
- internal KeyValuePairComparable(IComparable<K> cutter) { this.cutter = cutter; }\r
-\r
- public int CompareTo(KeyValuePair<K, V> other) { return cutter.CompareTo(other.Key); }\r
-\r
- public bool Equals(KeyValuePair<K, V> other) { return cutter.Equals(other.Key); }\r
- }\r
-\r
- class ProjectedDirectedEnumerable : MappedDirectedEnumerable<KeyValuePair<K, V>, K>\r
- {\r
- public ProjectedDirectedEnumerable(IDirectedEnumerable<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }\r
-\r
- public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }\r
-\r
- }\r
-\r
- class ProjectedDirectedCollectionValue : MappedDirectedCollectionValue<KeyValuePair<K, V>, K>\r
- {\r
- public ProjectedDirectedCollectionValue(IDirectedCollectionValue<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }\r
-\r
- public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }\r
-\r
- }\r
-\r
- class SortedKeysCollection : SequencedBase<K>, ISorted<K>\r
- {\r
- ISortedDictionary<K, V> sorteddict;\r
- //TODO: eliminate this. Only problem is the Find method because we lack method on dictionary that also \r
- // returns the actual key.\r
- ISorted<KeyValuePair<K, V>> sortedpairs;\r
- SCG.IComparer<K> comparer;\r
-\r
- internal SortedKeysCollection(ISortedDictionary<K, V> sorteddict, ISorted<KeyValuePair<K, V>> sortedpairs, SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> itemequalityComparer) \r
- :base(itemequalityComparer)\r
- {\r
- this.sorteddict = sorteddict;\r
- this.sortedpairs = sortedpairs;\r
- this.comparer = comparer;\r
- }\r
-\r
- public override K Choose() { return sorteddict.Choose().Key; }\r
-\r
- public override SCG.IEnumerator<K> GetEnumerator()\r
- {\r
- foreach (KeyValuePair<K, V> p in sorteddict)\r
- yield return p.Key;\r
- }\r
-\r
- public override bool IsEmpty { get { return sorteddict.IsEmpty; } }\r
-\r
- public override int Count { [Tested]get { return sorteddict.Count; } }\r
-\r
- public override Speed CountSpeed { get { return sorteddict.CountSpeed; } }\r
-\r
- #region ISorted<K> Members\r
-\r
- public K FindMin() { return sorteddict.FindMin().Key; }\r
-\r
- public K DeleteMin() { throw new ReadOnlyCollectionException(); }\r
-\r
- public K FindMax() { return sorteddict.FindMax().Key; }\r
-\r
- public K DeleteMax() { throw new ReadOnlyCollectionException(); }\r
-\r
- public SCG.IComparer<K> Comparer { get { return comparer; } }\r
-\r
- public K Predecessor(K item) { return sorteddict.Predecessor(item).Key; }\r
-\r
- public K Successor(K item) { return sorteddict.Successor(item).Key; }\r
-\r
- public K WeakPredecessor(K item) { return sorteddict.WeakPredecessor(item).Key; }\r
-\r
- public K WeakSuccessor(K item) { return sorteddict.WeakSuccessor(item).Key; }\r
-\r
- public bool Cut(IComparable<K> c, out K low, out bool lowIsValid, out K high, out bool highIsValid)\r
- {\r
- KeyValuePair<K, V> lowpair, highpair;\r
- bool retval = sorteddict.Cut(c, out lowpair, out lowIsValid, out highpair, out highIsValid);\r
- low = lowpair.Key;\r
- high = highpair.Key;\r
- return retval;\r
- }\r
-\r
- public IDirectedEnumerable<K> RangeFrom(K bot)\r
- {\r
- return new ProjectedDirectedEnumerable(sorteddict.RangeFrom(bot));\r
- }\r
-\r
- public IDirectedEnumerable<K> RangeFromTo(K bot, K top)\r
- {\r
- return new ProjectedDirectedEnumerable(sorteddict.RangeFromTo(bot, top));\r
- }\r
-\r
- public IDirectedEnumerable<K> RangeTo(K top)\r
- {\r
- return new ProjectedDirectedEnumerable(sorteddict.RangeTo(top));\r
- }\r
-\r
- public IDirectedCollectionValue<K> RangeAll()\r
- {\r
- return new ProjectedDirectedCollectionValue(sorteddict.RangeAll());\r
- }\r
-\r
- public void AddSorted<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }\r
-\r
- public void RemoveRangeFrom(K low) { throw new ReadOnlyCollectionException(); }\r
-\r
- public void RemoveRangeFromTo(K low, K hi) { throw new ReadOnlyCollectionException(); }\r
-\r
- public void RemoveRangeTo(K hi) { throw new ReadOnlyCollectionException(); }\r
- #endregion\r
-\r
- #region ICollection<K> Members\r
- public Speed ContainsSpeed { get { return sorteddict.ContainsSpeed; } }\r
-\r
- public bool Contains(K key) { return sorteddict.Contains(key); ; }\r
-\r
- public int ContainsCount(K item) { return sorteddict.Contains(item) ? 1 : 0; }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <returns></returns>\r
- public virtual ICollectionValue<K> UniqueItems()\r
- {\r
- return this;\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <returns></returns>\r
- public virtual ICollectionValue<KeyValuePair<K, int>> ItemMultiplicities()\r
- {\r
- return new MultiplicityOne<K>(this);\r
- }\r
-\r
-\r
- public bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : K\r
- {\r
- //TODO: optimize?\r
- foreach (K item in items)\r
- if (!sorteddict.Contains(item))\r
- return false;\r
- return true;\r
- }\r
-\r
- public bool Find(ref K item)\r
- {\r
- KeyValuePair<K, V> p = new KeyValuePair<K, V>(item);\r
- bool retval = sortedpairs.Find(ref p);\r
- item = p.Key;\r
- return retval;\r
- }\r
-\r
- public bool FindOrAdd(ref K item) { throw new ReadOnlyCollectionException(); }\r
-\r
- public bool Update(K item) { throw new ReadOnlyCollectionException(); }\r
-\r
- public bool Update(K item, out K olditem) { throw new ReadOnlyCollectionException(); }\r
-\r
- public bool UpdateOrAdd(K item) { throw new ReadOnlyCollectionException(); }\r
-\r
- public bool UpdateOrAdd(K item, out K olditem) { throw new ReadOnlyCollectionException(); }\r
-\r
- public bool Remove(K item) { throw new ReadOnlyCollectionException(); }\r
-\r
- public bool Remove(K item, out K removeditem) { throw new ReadOnlyCollectionException(); }\r
-\r
- public void RemoveAllCopies(K item) { throw new ReadOnlyCollectionException(); }\r
-\r
- public void RemoveAll<U> (SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }\r
-\r
- public void Clear() { throw new ReadOnlyCollectionException(); }\r
-\r
- public void RetainAll<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }\r
-\r
- #endregion\r
-\r
- #region IExtensible<K> Members\r
- public override bool IsReadOnly { get { return true; } }\r
-\r
- public bool AllowsDuplicates { get { return false; } }\r
-\r
- public bool DuplicatesByCounting { get { return true; } }\r
-\r
- public bool Add(K item) { throw new ReadOnlyCollectionException(); }\r
-\r
- public void AddAll(System.Collections.Generic.IEnumerable<K> items) { throw new ReadOnlyCollectionException(); }\r
-\r
- public void AddAll<U>(System.Collections.Generic.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }\r
-\r
- public bool Check() { return sorteddict.Check(); }\r
-\r
- #endregion\r
-\r
- #region IDirectedCollectionValue<K> Members\r
-\r
- public override IDirectedCollectionValue<K> Backwards()\r
- {\r
- return RangeAll().Backwards();\r
- }\r
-\r
- #endregion\r
-\r
- #region IDirectedEnumerable<K> Members\r
-\r
- IDirectedEnumerable<K> IDirectedEnumerable<K>.Backwards() { return Backwards(); }\r
- #endregion\r
-\r
- #region ICloneable Members\r
-\r
- //TODO: test\r
- /// <summary>\r
- /// Make a shallow copy of this SortedKeysCollection.\r
- /// </summary>\r
- /// <returns></returns>\r
- public virtual object Clone()\r
- {\r
- //\r
- SortedArrayDictionary<K, V> dictclone = new SortedArrayDictionary<K, V>(sortedpairs.Count, comparer, EqualityComparer);\r
- SortedArray<KeyValuePair<K, V>> sortedpairsclone = (SortedArray<KeyValuePair<K, V>>)(dictclone.sortedpairs);\r
- foreach (K key in sorteddict.Keys)\r
- {\r
- sortedpairsclone.Add(new KeyValuePair<K, V>(key, default(V)));\r
- }\r
- return new SortedKeysCollection(dictclone, sortedpairsclone, comparer, EqualityComparer);\r
- }\r
-\r
- #endregion\r
-\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="stringbuilder"></param>\r
- /// <param name="rest"></param>\r
- /// <param name="formatProvider"></param>\r
- /// <returns></returns>\r
- public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)\r
- {\r
- return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);\r
- }\r
-\r
- }\r
-\r
- class SortedArrayDictionary<K, V> : SortedDictionaryBase<K, V>, IDictionary<K, V>, ISortedDictionary<K, V>\r
- {\r
- #region Constructors\r
-\r
- public SortedArrayDictionary() : this(Comparer<K>.Default, EqualityComparer<K>.Default) { }\r
-\r
- /// <summary>\r
- /// Create a red-black tree dictionary using an external comparer for keys.\r
- /// </summary>\r
- /// <param name="comparer">The external comparer</param>\r
- public SortedArrayDictionary(SCG.IComparer<K> comparer) : this(comparer, new ComparerZeroHashCodeEqualityComparer<K>(comparer)) { }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="comparer"></param>\r
- /// <param name="equalityComparer"></param>\r
- public SortedArrayDictionary(SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> equalityComparer) : base(comparer,equalityComparer)\r
- {\r
- pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(new KeyValuePairComparer<K, V>(comparer));\r
- }\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <param name="comparer"></param>\r
- /// <param name="equalityComparer"></param>\r
- /// <param name="capacity"></param>\r
- public SortedArrayDictionary(int capacity, SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> equalityComparer) : base(comparer,equalityComparer)\r
- {\r
- pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(capacity, new KeyValuePairComparer<K, V>(comparer));\r
- }\r
- #endregion\r
-\r
- /// <summary>\r
- /// \r
- /// </summary>\r
- /// <returns></returns>\r
- public override object Clone()\r
- {\r
- SortedArrayDictionary<K, V> clone = new SortedArrayDictionary<K, V>(Comparer, EqualityComparer);\r
- clone.sortedpairs.AddSorted(sortedpairs);\r
- return clone;\r
- }\r
-\r
- }\r
-}
-#endif
+/*
+ Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ SOFTWARE.
+*/
+
+using System;
+using System.Diagnostics;
+using SCG = System.Collections.Generic;
+namespace C5
+{
+ /// <summary>
+ /// An entry in a dictionary from K to V.
+ /// </summary>
+ [Serializable]
+ public struct KeyValuePair<K, V> : IEquatable<KeyValuePair<K, V>>, IShowable
+ {
+ /// <summary>
+ /// The key field of the entry
+ /// </summary>
+ public K Key;
+
+ /// <summary>
+ /// The value field of the entry
+ /// </summary>
+ public V Value;
+
+ /// <summary>
+ /// Create an entry with specified key and value
+ /// </summary>
+ /// <param name="key">The key</param>
+ /// <param name="value">The value</param>
+ public KeyValuePair(K key, V value) { Key = key; Value = value; }
+
+
+ /// <summary>
+ /// Create an entry with a specified key. The value will be the default value of type <code>V</code>.
+ /// </summary>
+ /// <param name="key">The key</param>
+ public KeyValuePair(K key) { Key = key; Value = default(V); }
+
+
+ /// <summary>
+ /// Pretty print an entry
+ /// </summary>
+ /// <returns>(key, value)</returns>
+ [Tested]
+ public override string ToString() { return "(" + Key + ", " + Value + ")"; }
+
+
+ /// <summary>
+ /// Check equality of entries.
+ /// </summary>
+ /// <param name="obj">The other object</param>
+ /// <returns>True if obj is an entry of the same type and has the same key and value</returns>
+ [Tested]
+ public override bool Equals(object obj)
+ {
+ if (!(obj is KeyValuePair<K, V>))
+ return false;
+ KeyValuePair<K, V> other = (KeyValuePair<K, V>)obj;
+ return Equals(other);
+ }
+
+
+ /// <summary>
+ /// Get the hash code of the pair.
+ /// </summary>
+ /// <returns>The hash code</returns>
+ [Tested]
+ public override int GetHashCode() { return EqualityComparer<K>.Default.GetHashCode(Key) + 13984681 * EqualityComparer<V>.Default.GetHashCode(Value); }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="other"></param>
+ /// <returns></returns>
+ public bool Equals(KeyValuePair<K, V> other)
+ {
+ return EqualityComparer<K>.Default.Equals(Key, other.Key) && EqualityComparer<V>.Default.Equals(Value, other.Value);
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="pair1"></param>
+ /// <param name="pair2"></param>
+ /// <returns></returns>
+ public static bool operator ==(KeyValuePair<K, V> pair1, KeyValuePair<K, V> pair2) { return pair1.Equals(pair2); }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="pair1"></param>
+ /// <param name="pair2"></param>
+ /// <returns></returns>
+ public static bool operator !=(KeyValuePair<K, V> pair1, KeyValuePair<K, V> pair2) { return !pair1.Equals(pair2); }
+
+ #region IShowable Members
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="stringbuilder"></param>
+ /// <param name="formatProvider"></param>
+ /// <param name="rest"></param>
+ /// <returns></returns>
+ public bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
+ {
+ if (rest < 0)
+ return false;
+ if (!Showing.Show(Key, stringbuilder, ref rest, formatProvider))
+ return false;
+ stringbuilder.Append(" => ");
+ rest -= 4;
+ if (!Showing.Show(Value, stringbuilder, ref rest, formatProvider))
+ return false;
+ return rest >= 0;
+ }
+ #endregion
+
+ #region IFormattable Members
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="format"></param>
+ /// <param name="formatProvider"></param>
+ /// <returns></returns>
+ public string ToString(string format, IFormatProvider formatProvider)
+ {
+ return Showing.ShowString(this, format, formatProvider);
+ }
+
+ #endregion
+ }
+
+
+
+ /// <summary>
+ /// Default comparer for dictionary entries in a sorted dictionary.
+ /// Entry comparisons only look at keys and uses an externally defined comparer for that.
+ /// </summary>
+ [Serializable]
+ public class KeyValuePairComparer<K, V> : SCG.IComparer<KeyValuePair<K, V>>
+ {
+ SCG.IComparer<K> comparer;
+
+
+ /// <summary>
+ /// Create an entry comparer for a item comparer of the keys
+ /// </summary>
+ /// <param name="comparer">Comparer of keys</param>
+ public KeyValuePairComparer(SCG.IComparer<K> comparer)
+ {
+ if (comparer == null)
+ throw new NullReferenceException();
+ this.comparer = comparer;
+ }
+
+
+ /// <summary>
+ /// Compare two entries
+ /// </summary>
+ /// <param name="entry1">First entry</param>
+ /// <param name="entry2">Second entry</param>
+ /// <returns>The result of comparing the keys</returns>
+ [Tested]
+ public int Compare(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)
+ { return comparer.Compare(entry1.Key, entry2.Key); }
+ }
+
+
+
+ /// <summary>
+ /// Default equalityComparer for dictionary entries.
+ /// Operations only look at keys and uses an externaly defined equalityComparer for that.
+ /// </summary>
+ [Serializable]
+ public sealed class KeyValuePairEqualityComparer<K, V> : SCG.IEqualityComparer<KeyValuePair<K, V>>
+ {
+ SCG.IEqualityComparer<K> keyequalityComparer;
+
+
+ /// <summary>
+ /// Create an entry equalityComparer using the default equalityComparer for keys
+ /// </summary>
+ public KeyValuePairEqualityComparer() { keyequalityComparer = EqualityComparer<K>.Default; }
+
+
+ /// <summary>
+ /// Create an entry equalityComparer from a specified item equalityComparer for the keys
+ /// </summary>
+ /// <param name="keyequalityComparer">The key equalityComparer</param>
+ public KeyValuePairEqualityComparer(SCG.IEqualityComparer<K> keyequalityComparer)
+ {
+ if (keyequalityComparer == null)
+ throw new NullReferenceException("Key equality comparer cannot be null");
+ this.keyequalityComparer = keyequalityComparer;
+ }
+
+
+ /// <summary>
+ /// Get the hash code of the entry
+ /// </summary>
+ /// <param name="entry">The entry</param>
+ /// <returns>The hash code of the key</returns>
+ [Tested]
+ public int GetHashCode(KeyValuePair<K, V> entry) { return keyequalityComparer.GetHashCode(entry.Key); }
+
+
+ /// <summary>
+ /// Test two entries for equality
+ /// </summary>
+ /// <param name="entry1">First entry</param>
+ /// <param name="entry2">Second entry</param>
+ /// <returns>True if keys are equal</returns>
+ [Tested]
+ public bool Equals(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)
+ { return keyequalityComparer.Equals(entry1.Key, entry2.Key); }
+ }
+
+
+
+ /// <summary>
+ /// A base class for implementing a dictionary based on a set collection implementation.
+ /// <i>See the source code for <see cref="T:C5.HashDictionary`2"/> for an example</i>
+ ///
+ /// </summary>
+ [Serializable]
+ public abstract class DictionaryBase<K, V> : CollectionValueBase<KeyValuePair<K, V>>, IDictionary<K, V>
+ {
+ /// <summary>
+ /// The set collection of entries underlying this dictionary implementation
+ /// </summary>
+ protected ICollection<KeyValuePair<K, V>> pairs;
+
+ SCG.IEqualityComparer<K> keyequalityComparer;
+
+ #region Events
+ ProxyEventBlock<KeyValuePair<K, V>> eventBlock;
+
+ /// <summary>
+ /// The change event. Will be raised for every change operation on the collection.
+ /// </summary>
+ public override event CollectionChangedHandler<KeyValuePair<K, V>> CollectionChanged
+ {
+ add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionChanged += value; }
+ remove { if (eventBlock != null) eventBlock.CollectionChanged -= value; }
+ }
+
+ /// <summary>
+ /// The change event. Will be raised for every change operation on the collection.
+ /// </summary>
+ public override event CollectionClearedHandler<KeyValuePair<K, V>> CollectionCleared
+ {
+ add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionCleared += value; }
+ remove { if (eventBlock != null) eventBlock.CollectionCleared -= value; }
+ }
+
+ /// <summary>
+ /// The item added event. Will be raised for every individual addition to the collection.
+ /// </summary>
+ public override event ItemsAddedHandler<KeyValuePair<K, V>> ItemsAdded
+ {
+ add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsAdded += value; }
+ remove { if (eventBlock != null) eventBlock.ItemsAdded -= value; }
+ }
+
+ /// <summary>
+ /// The item added event. Will be raised for every individual removal from the collection.
+ /// </summary>
+ public override event ItemsRemovedHandler<KeyValuePair<K, V>> ItemsRemoved
+ {
+ add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsRemoved += value; }
+ remove { if (eventBlock != null) eventBlock.ItemsRemoved -= value; }
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ public override EventTypeEnum ListenableEvents
+ {
+ get
+ {
+ return EventTypeEnum.Basic;
+ }
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ public override EventTypeEnum ActiveEvents
+ {
+ get
+ {
+ return pairs.ActiveEvents;
+ }
+ }
+
+ #endregion
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="keyequalityComparer"></param>
+ protected DictionaryBase(SCG.IEqualityComparer<K> keyequalityComparer)
+ {
+ if (keyequalityComparer == null)
+ throw new NullReferenceException("Key equality comparer cannot be null");
+ this.keyequalityComparer = keyequalityComparer;
+ }
+
+ #region IDictionary<K,V> Members
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value></value>
+ public virtual SCG.IEqualityComparer<K> EqualityComparer { get { return keyequalityComparer; } }
+
+
+ /// <summary>
+ /// Add a new (key, value) pair (a mapping) to the dictionary.
+ /// </summary>
+ /// <exception cref="DuplicateNotAllowedException"> if there already is an entry with the same key. </exception>
+ /// <param name="key">Key to add</param>
+ /// <param name="value">Value to add</param>
+ [Tested]
+ public virtual void Add(K key, V value)
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
+
+ if (!pairs.Add(p))
+ throw new DuplicateNotAllowedException("Key being added: '" + key + "'");
+ }
+
+ /// <summary>
+ /// Add the entries from a collection of <see cref="T:C5.KeyValuePair`2"/> pairs to this dictionary.
+ /// <para><b>TODO: add restrictions L:K and W:V when the .Net SDK allows it </b></para>
+ /// </summary>
+ /// <exception cref="DuplicateNotAllowedException">
+ /// If the input contains duplicate keys or a key already present in this dictionary.</exception>
+ /// <param name="entries"></param>
+ public virtual void AddAll<L, W>(SCG.IEnumerable<KeyValuePair<L, W>> entries)
+ where L : K
+ where W : V
+ {
+ foreach (KeyValuePair<L, W> pair in entries)
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(pair.Key, pair.Value);
+ if (!pairs.Add(p))
+ throw new DuplicateNotAllowedException("Key being added: '" + pair.Key + "'");
+ }
+ }
+
+ /// <summary>
+ /// Remove an entry with a given key from the dictionary
+ /// </summary>
+ /// <param name="key">The key of the entry to remove</param>
+ /// <returns>True if an entry was found (and removed)</returns>
+ [Tested]
+ public virtual bool Remove(K key)
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
+
+ return pairs.Remove(p);
+ }
+
+
+ /// <summary>
+ /// Remove an entry with a given key from the dictionary and report its value.
+ /// </summary>
+ /// <param name="key">The key of the entry to remove</param>
+ /// <param name="value">On exit, the value of the removed entry</param>
+ /// <returns>True if an entry was found (and removed)</returns>
+ [Tested]
+ public virtual bool Remove(K key, out V value)
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
+
+ if (pairs.Remove(p, out p))
+ {
+ value = p.Value;
+ return true;
+ }
+ else
+ {
+ value = default(V);
+ return false;
+ }
+ }
+
+
+ /// <summary>
+ /// Remove all entries from the dictionary
+ /// </summary>
+ [Tested]
+ public virtual void Clear() { pairs.Clear(); }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value></value>
+ public virtual Speed ContainsSpeed { get { return pairs.ContainsSpeed; } }
+
+ /// <summary>
+ /// Check if there is an entry with a specified key
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <returns>True if key was found</returns>
+ [Tested]
+ public virtual bool Contains(K key)
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
+
+ return pairs.Contains(p);
+ }
+
+ [Serializable]
+ class LiftedEnumerable<H> : SCG.IEnumerable<KeyValuePair<K, V>> where H : K
+ {
+ SCG.IEnumerable<H> keys;
+ public LiftedEnumerable(SCG.IEnumerable<H> keys) { this.keys = keys; }
+ public SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator() { foreach (H key in keys) yield return new KeyValuePair<K, V>(key); }
+
+ #region IEnumerable Members
+
+ System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
+ {
+ throw new Exception("The method or operation is not implemented.");
+ }
+
+ #endregion
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="keys"></param>
+ /// <returns></returns>
+ public virtual bool ContainsAll<H>(SCG.IEnumerable<H> keys) where H : K
+ {
+ return pairs.ContainsAll(new LiftedEnumerable<H>(keys));
+ }
+
+ /// <summary>
+ /// Check if there is an entry with a specified key and report the corresponding
+ /// value if found. This can be seen as a safe form of "val = this[key]".
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <param name="value">On exit, the value of the entry</param>
+ /// <returns>True if key was found</returns>
+ [Tested]
+ public virtual bool Find(K key, out V value)
+ {
+ return Find(ref key, out value);
+ }
+ /// <summary>
+ /// Check if there is an entry with a specified key and report the corresponding
+ /// value if found. This can be seen as a safe form of "val = this[key]".
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <param name="value">On exit, the value of the entry</param>
+ /// <returns>True if key was found</returns>
+ public virtual bool Find(ref K key, out V value)
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
+
+ if (pairs.Find(ref p))
+ {
+ key = p.Key;
+ value = p.Value;
+ return true;
+ }
+ else
+ {
+ value = default(V);
+ return false;
+ }
+ }
+
+
+ /// <summary>
+ /// Look for a specific key in the dictionary and if found replace the value with a new one.
+ /// This can be seen as a non-adding version of "this[key] = val".
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <param name="value">The new value</param>
+ /// <returns>True if key was found</returns>
+ [Tested]
+ public virtual bool Update(K key, V value)
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
+
+ return pairs.Update(p);
+ }
+
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="key"></param>
+ /// <param name="value"></param>
+ /// <param name="oldvalue"></param>
+ /// <returns></returns>
+ public virtual bool Update(K key, V value, out V oldvalue)
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
+
+ bool retval = pairs.Update(p, out p);
+ oldvalue = p.Value;
+ return retval;
+ }
+
+
+ /// <summary>
+ /// Look for a specific key in the dictionary. If found, report the corresponding value,
+ /// else add an entry with the key and the supplied value.
+ /// </summary>
+ /// <param name="key">On entry the key to look for</param>
+ /// <param name="value">On entry the value to add if the key is not found.
+ /// On exit the value found if any.</param>
+ /// <returns>True if key was found</returns>
+ [Tested]
+ public virtual bool FindOrAdd(K key, ref V value)
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
+
+ if (!pairs.FindOrAdd(ref p))
+ return false;
+ else
+ {
+ value = p.Value;
+ //key = p.key;
+ return true;
+ }
+ }
+
+
+ /// <summary>
+ /// Update value in dictionary corresponding to key if found, else add new entry.
+ /// More general than "this[key] = val;" by reporting if key was found.
+ /// </summary>
+ /// <param name="key">The key to look for</param>
+ /// <param name="value">The value to add or replace with.</param>
+ /// <returns>True if entry was updated.</returns>
+ [Tested]
+ public virtual bool UpdateOrAdd(K key, V value)
+ {
+ return pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value));
+ }
+
+
+ /// <summary>
+ /// Update value in dictionary corresponding to key if found, else add new entry.
+ /// More general than "this[key] = val;" by reporting if key was found and the old value if any.
+ /// </summary>
+ /// <param name="key"></param>
+ /// <param name="value"></param>
+ /// <param name="oldvalue"></param>
+ /// <returns></returns>
+ public virtual bool UpdateOrAdd(K key, V value, out V oldvalue)
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
+ bool retval = pairs.UpdateOrAdd(p, out p);
+ oldvalue = p.Value;
+ return retval;
+ }
+
+
+
+ #region Keys,Values support classes
+ [Serializable]
+ internal class ValuesCollection : CollectionValueBase<V>, ICollectionValue<V>
+ {
+ ICollection<KeyValuePair<K, V>> pairs;
+
+
+ internal ValuesCollection(ICollection<KeyValuePair<K, V>> pairs)
+ { this.pairs = pairs; }
+
+
+ public override V Choose() { return pairs.Choose().Value; }
+
+ [Tested]
+ public override SCG.IEnumerator<V> GetEnumerator()
+ {
+ //Updatecheck is performed by the pairs enumerator
+ foreach (KeyValuePair<K, V> p in pairs)
+ yield return p.Value;
+ }
+
+ public override bool IsEmpty { get { return pairs.IsEmpty; } }
+
+ [Tested]
+ public override int Count { [Tested]get { return pairs.Count; } }
+
+ public override Speed CountSpeed { get { return Speed.Constant; } }
+ }
+
+
+
+ [Serializable]
+ internal class KeysCollection : CollectionValueBase<K>, ICollectionValue<K>
+ {
+ ICollection<KeyValuePair<K, V>> pairs;
+
+
+ internal KeysCollection(ICollection<KeyValuePair<K, V>> pairs)
+ { this.pairs = pairs; }
+
+ public override K Choose() { return pairs.Choose().Key; }
+
+ [Tested]
+ public override SCG.IEnumerator<K> GetEnumerator()
+ {
+ foreach (KeyValuePair<K, V> p in pairs)
+ yield return p.Key;
+ }
+
+ public override bool IsEmpty { get { return pairs.IsEmpty; } }
+
+ [Tested]
+ public override int Count { [Tested]get { return pairs.Count; } }
+
+ public override Speed CountSpeed { get { return pairs.CountSpeed; } }
+ }
+ #endregion
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>A collection containg the all the keys of the dictionary</value>
+ [Tested]
+ public virtual ICollectionValue<K> Keys { [Tested]get { return new KeysCollection(pairs); } }
+
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>A collection containing all the values of the dictionary</value>
+ [Tested]
+ public virtual ICollectionValue<V> Values { [Tested]get { return new ValuesCollection(pairs); } }
+
+ /// <summary>
+ ///
+ /// </summary>
+ public virtual Fun<K, V> Fun { get { return delegate(K k) { return this[k]; }; } }
+
+ /// <summary>
+ /// Indexer by key for dictionary.
+ /// <para>The get method will throw an exception if no entry is found. </para>
+ /// <para>The set method behaves like <see cref="M:C5.DictionaryBase`2.UpdateOrAdd(`0,`1)"/>.</para>
+ /// </summary>
+ /// <exception cref="NoSuchItemException"> On get if no entry is found. </exception>
+ /// <value>The value corresponding to the key</value>
+ [Tested]
+ public virtual V this[K key]
+ {
+ [Tested]
+ get
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
+
+ if (pairs.Find(ref p))
+ return p.Value;
+ else
+ throw new NoSuchItemException("Key '" + key.ToString() + "' not present in Dictionary");
+ }
+ [Tested]
+ set
+ { pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value)); }
+ }
+
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>True if dictionary is read only</value>
+ [Tested]
+ public virtual bool IsReadOnly { [Tested]get { return pairs.IsReadOnly; } }
+
+
+ /// <summary>
+ /// Check the integrity of the internal data structures of this dictionary.
+ /// </summary>
+ /// <returns>True if check does not fail.</returns>
+ [Tested]
+ public virtual bool Check() { return pairs.Check(); }
+
+ #endregion
+
+ #region ICollectionValue<KeyValuePair<K,V>> Members
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>True if this collection is empty.</value>
+ public override bool IsEmpty { get { return pairs.IsEmpty; } }
+
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>The number of entrues in the dictionary</value>
+ [Tested]
+ public override int Count { [Tested]get { return pairs.Count; } }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>The number of entrues in the dictionary</value>
+ [Tested]
+ public override Speed CountSpeed { [Tested]get { return pairs.CountSpeed; } }
+
+ /// <summary>
+ /// Choose some entry in this Dictionary.
+ /// </summary>
+ /// <exception cref="NoSuchItemException">if collection is empty.</exception>
+ /// <returns></returns>
+ public override KeyValuePair<K, V> Choose() { return pairs.Choose(); }
+
+ /// <summary>
+ /// Create an enumerator for the collection of entries of the dictionary
+ /// </summary>
+ /// <returns>The enumerator</returns>
+ [Tested]
+ public override SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator()
+ {
+ return pairs.GetEnumerator(); ;
+ }
+
+ #endregion
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="stringbuilder"></param>
+ /// <param name="rest"></param>
+ /// <param name="formatProvider"></param>
+ /// <returns></returns>
+ public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
+ {
+ return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ public abstract object Clone();
+
+ }
+
+ /// <summary>
+ /// A base class for implementing a sorted dictionary based on a sorted set collection implementation.
+ /// <i>See the source code for <see cref="T:C5.TreeDictionary`2"/> for an example</i>
+ ///
+ /// </summary>
+ [Serializable]
+ public abstract class SortedDictionaryBase<K, V> : DictionaryBase<K, V>, ISortedDictionary<K, V>
+ {
+ #region Fields
+
+ /// <summary>
+ ///
+ /// </summary>
+ protected ISorted<KeyValuePair<K, V>> sortedpairs;
+ SCG.IComparer<K> keycomparer;
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="keycomparer"></param>
+ /// <param name="keyequalityComparer"></param>
+ protected SortedDictionaryBase(SCG.IComparer<K> keycomparer, SCG.IEqualityComparer<K> keyequalityComparer) : base(keyequalityComparer) { this.keycomparer = keycomparer; }
+
+ #endregion
+
+ #region ISortedDictionary<K,V> Members
+
+ /// <summary>
+ /// The key comparer used by this dictionary.
+ /// </summary>
+ /// <value></value>
+ public SCG.IComparer<K> Comparer { get { return keycomparer; } }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value></value>
+ public new ISorted<K> Keys { get { return new SortedKeysCollection(this, sortedpairs, keycomparer, EqualityComparer); } }
+
+ /// <summary>
+ /// Find the entry in the dictionary whose key is the
+ /// predecessor of the specified key.
+ /// </summary>
+ /// <param name="key">The key</param>
+ /// <param name="res">The predecessor, if any</param>
+ /// <returns>True if key has a predecessor</returns>
+ [Tested]
+ public bool TryPredecessor(K key, out KeyValuePair<K, V> res)
+ {
+ return sortedpairs.TryPredecessor(new KeyValuePair<K, V>(key), out res);
+ }
+
+ /// <summary>
+ /// Find the entry in the dictionary whose key is the
+ /// successor of the specified key.
+ /// </summary>
+ /// <param name="key">The key</param>
+ /// <param name="res">The successor, if any</param>
+ /// <returns>True if the key has a successor</returns>
+ [Tested]
+ public bool TrySuccessor(K key, out KeyValuePair<K, V> res)
+ {
+ return sortedpairs.TrySuccessor(new KeyValuePair<K, V>(key), out res);
+ }
+
+ /// <summary>
+ /// Find the entry in the dictionary whose key is the
+ /// weak predecessor of the specified key.
+ /// </summary>
+ /// <param name="key">The key</param>
+ /// <param name="res">The predecessor, if any</param>
+ /// <returns>True if key has a weak predecessor</returns>
+ [Tested]
+ public bool TryWeakPredecessor(K key, out KeyValuePair<K, V> res)
+ {
+ return sortedpairs.TryWeakPredecessor(new KeyValuePair<K, V>(key), out res);
+ }
+
+ /// <summary>
+ /// Find the entry in the dictionary whose key is the
+ /// weak successor of the specified key.
+ /// </summary>
+ /// <param name="key">The key</param>
+ /// <param name="res">The weak successor, if any</param>
+ /// <returns>True if the key has a weak successor</returns>
+ [Tested]
+ public bool TryWeakSuccessor(K key, out KeyValuePair<K, V> res)
+ {
+ return sortedpairs.TryWeakSuccessor(new KeyValuePair<K, V>(key), out res);
+ }
+
+ /// <summary>
+ /// Get the entry in the dictionary whose key is the
+ /// predecessor of the specified key.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"></exception>
+ /// <param name="key">The key</param>
+ /// <returns>The entry</returns>
+ [Tested]
+ public KeyValuePair<K, V> Predecessor(K key)
+ {
+ return sortedpairs.Predecessor(new KeyValuePair<K, V>(key));
+ }
+
+ /// <summary>
+ /// Get the entry in the dictionary whose key is the
+ /// successor of the specified key.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"></exception>
+ /// <param name="key">The key</param>
+ /// <returns>The entry</returns>
+ [Tested]
+ public KeyValuePair<K, V> Successor(K key)
+ {
+ return sortedpairs.Successor(new KeyValuePair<K, V>(key));
+ }
+
+ /// <summary>
+ /// Get the entry in the dictionary whose key is the
+ /// weak predecessor of the specified key.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"></exception>
+ /// <param name="key">The key</param>
+ /// <returns>The entry</returns>
+ [Tested]
+ public KeyValuePair<K, V> WeakPredecessor(K key)
+ {
+ return sortedpairs.WeakPredecessor(new KeyValuePair<K, V>(key));
+ }
+
+ /// <summary>
+ /// Get the entry in the dictionary whose key is the
+ /// weak successor of the specified key.
+ /// </summary>
+ /// <exception cref="NoSuchItemException"></exception>
+ /// <param name="key">The key</param>
+ /// <returns>The entry</returns>
+ [Tested]
+ public KeyValuePair<K, V> WeakSuccessor(K key)
+ {
+ return sortedpairs.WeakSuccessor(new KeyValuePair<K, V>(key));
+ }
+
+ #endregion
+
+ #region ISortedDictionary<K,V> Members
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ public KeyValuePair<K, V> FindMin()
+ {
+ return sortedpairs.FindMin();
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ public KeyValuePair<K, V> DeleteMin()
+ {
+ return sortedpairs.DeleteMin();
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ public KeyValuePair<K, V> FindMax()
+ {
+ return sortedpairs.FindMax();
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ public KeyValuePair<K, V> DeleteMax()
+ {
+ return sortedpairs.DeleteMax();
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="cutter"></param>
+ /// <param name="lowEntry"></param>
+ /// <param name="lowIsValid"></param>
+ /// <param name="highEntry"></param>
+ /// <param name="highIsValid"></param>
+ /// <returns></returns>
+ public bool Cut(IComparable<K> cutter, out KeyValuePair<K, V> lowEntry, out bool lowIsValid, out KeyValuePair<K, V> highEntry, out bool highIsValid)
+ {
+ return sortedpairs.Cut(new KeyValuePairComparable(cutter), out lowEntry, out lowIsValid, out highEntry, out highIsValid);
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="bot"></param>
+ /// <returns></returns>
+ public IDirectedEnumerable<KeyValuePair<K, V>> RangeFrom(K bot)
+ {
+ return sortedpairs.RangeFrom(new KeyValuePair<K, V>(bot));
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="bot"></param>
+ /// <param name="top"></param>
+ /// <returns></returns>
+ public IDirectedEnumerable<KeyValuePair<K, V>> RangeFromTo(K bot, K top)
+ {
+ return sortedpairs.RangeFromTo(new KeyValuePair<K, V>(bot), new KeyValuePair<K, V>(top));
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="top"></param>
+ /// <returns></returns>
+ public IDirectedEnumerable<KeyValuePair<K, V>> RangeTo(K top)
+ {
+ return sortedpairs.RangeTo(new KeyValuePair<K, V>(top));
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ public IDirectedCollectionValue<KeyValuePair<K, V>> RangeAll()
+ {
+ return sortedpairs.RangeAll();
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="items"></param>
+ public void AddSorted(SCG.IEnumerable<KeyValuePair<K, V>> items)
+ {
+ sortedpairs.AddSorted(items);
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="lowKey"></param>
+ public void RemoveRangeFrom(K lowKey)
+ {
+ sortedpairs.RemoveRangeFrom(new KeyValuePair<K, V>(lowKey));
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="lowKey"></param>
+ /// <param name="highKey"></param>
+ public void RemoveRangeFromTo(K lowKey, K highKey)
+ {
+ sortedpairs.RemoveRangeFromTo(new KeyValuePair<K, V>(lowKey), new KeyValuePair<K, V>(highKey));
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="highKey"></param>
+ public void RemoveRangeTo(K highKey)
+ {
+ sortedpairs.RemoveRangeTo(new KeyValuePair<K, V>(highKey));
+ }
+
+ #endregion
+ [Serializable]
+ class KeyValuePairComparable : IComparable<KeyValuePair<K, V>>
+ {
+ IComparable<K> cutter;
+
+ internal KeyValuePairComparable(IComparable<K> cutter) { this.cutter = cutter; }
+
+ public int CompareTo(KeyValuePair<K, V> other) { return cutter.CompareTo(other.Key); }
+
+ public bool Equals(KeyValuePair<K, V> other) { return cutter.Equals(other.Key); }
+ }
+
+ [Serializable]
+ class ProjectedDirectedEnumerable : MappedDirectedEnumerable<KeyValuePair<K, V>, K>
+ {
+ public ProjectedDirectedEnumerable(IDirectedEnumerable<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }
+
+ public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }
+
+ }
+
+ [Serializable]
+ class ProjectedDirectedCollectionValue : MappedDirectedCollectionValue<KeyValuePair<K, V>, K>
+ {
+ public ProjectedDirectedCollectionValue(IDirectedCollectionValue<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }
+
+ public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }
+
+ }
+
+ [Serializable]
+ class SortedKeysCollection : SequencedBase<K>, ISorted<K>
+ {
+ ISortedDictionary<K, V> sorteddict;
+ //TODO: eliminate this. Only problem is the Find method because we lack method on dictionary that also
+ // returns the actual key.
+ ISorted<KeyValuePair<K, V>> sortedpairs;
+ SCG.IComparer<K> comparer;
+
+ internal SortedKeysCollection(ISortedDictionary<K, V> sorteddict, ISorted<KeyValuePair<K, V>> sortedpairs, SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> itemequalityComparer)
+ : base(itemequalityComparer)
+ {
+ this.sorteddict = sorteddict;
+ this.sortedpairs = sortedpairs;
+ this.comparer = comparer;
+ }
+
+ public override K Choose() { return sorteddict.Choose().Key; }
+
+ public override SCG.IEnumerator<K> GetEnumerator()
+ {
+ foreach (KeyValuePair<K, V> p in sorteddict)
+ yield return p.Key;
+ }
+
+ public override bool IsEmpty { get { return sorteddict.IsEmpty; } }
+
+ public override int Count { [Tested]get { return sorteddict.Count; } }
+
+ public override Speed CountSpeed { get { return sorteddict.CountSpeed; } }
+
+ #region ISorted<K> Members
+
+ public K FindMin() { return sorteddict.FindMin().Key; }
+
+ public K DeleteMin() { throw new ReadOnlyCollectionException(); }
+
+ public K FindMax() { return sorteddict.FindMax().Key; }
+
+ public K DeleteMax() { throw new ReadOnlyCollectionException(); }
+
+ public SCG.IComparer<K> Comparer { get { return comparer; } }
+
+ public bool TryPredecessor(K item, out K res)
+ {
+ KeyValuePair<K, V> pRes;
+ bool success = sorteddict.TryPredecessor(item, out pRes);
+ res = pRes.Key;
+ return success;
+ }
+
+ public bool TrySuccessor(K item, out K res)
+ {
+ KeyValuePair<K, V> pRes;
+ bool success = sorteddict.TrySuccessor(item, out pRes);
+ res = pRes.Key;
+ return success;
+ }
+
+ public bool TryWeakPredecessor(K item, out K res)
+ {
+ KeyValuePair<K, V> pRes;
+ bool success = sorteddict.TryWeakPredecessor(item, out pRes);
+ res = pRes.Key;
+ return success;
+ }
+
+ public bool TryWeakSuccessor(K item, out K res)
+ {
+ KeyValuePair<K, V> pRes;
+ bool success = sorteddict.TryWeakSuccessor(item, out pRes);
+ res = pRes.Key;
+ return success;
+ }
+
+ public K Predecessor(K item) { return sorteddict.Predecessor(item).Key; }
+
+ public K Successor(K item) { return sorteddict.Successor(item).Key; }
+
+ public K WeakPredecessor(K item) { return sorteddict.WeakPredecessor(item).Key; }
+
+ public K WeakSuccessor(K item) { return sorteddict.WeakSuccessor(item).Key; }
+
+ public bool Cut(IComparable<K> c, out K low, out bool lowIsValid, out K high, out bool highIsValid)
+ {
+ KeyValuePair<K, V> lowpair, highpair;
+ bool retval = sorteddict.Cut(c, out lowpair, out lowIsValid, out highpair, out highIsValid);
+ low = lowpair.Key;
+ high = highpair.Key;
+ return retval;
+ }
+
+ public IDirectedEnumerable<K> RangeFrom(K bot)
+ {
+ return new ProjectedDirectedEnumerable(sorteddict.RangeFrom(bot));
+ }
+
+ public IDirectedEnumerable<K> RangeFromTo(K bot, K top)
+ {
+ return new ProjectedDirectedEnumerable(sorteddict.RangeFromTo(bot, top));
+ }
+
+ public IDirectedEnumerable<K> RangeTo(K top)
+ {
+ return new ProjectedDirectedEnumerable(sorteddict.RangeTo(top));
+ }
+
+ public IDirectedCollectionValue<K> RangeAll()
+ {
+ return new ProjectedDirectedCollectionValue(sorteddict.RangeAll());
+ }
+
+ public void AddSorted<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
+
+ public void RemoveRangeFrom(K low) { throw new ReadOnlyCollectionException(); }
+
+ public void RemoveRangeFromTo(K low, K hi) { throw new ReadOnlyCollectionException(); }
+
+ public void RemoveRangeTo(K hi) { throw new ReadOnlyCollectionException(); }
+ #endregion
+
+ #region ICollection<K> Members
+ public Speed ContainsSpeed { get { return sorteddict.ContainsSpeed; } }
+
+ public bool Contains(K key) { return sorteddict.Contains(key); ; }
+
+ public int ContainsCount(K item) { return sorteddict.Contains(item) ? 1 : 0; }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ public virtual ICollectionValue<K> UniqueItems()
+ {
+ return this;
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ public virtual ICollectionValue<KeyValuePair<K, int>> ItemMultiplicities()
+ {
+ return new MultiplicityOne<K>(this);
+ }
+
+
+ public bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : K
+ {
+ //TODO: optimize?
+ foreach (K item in items)
+ if (!sorteddict.Contains(item))
+ return false;
+ return true;
+ }
+
+ public bool Find(ref K item)
+ {
+ KeyValuePair<K, V> p = new KeyValuePair<K, V>(item);
+ bool retval = sortedpairs.Find(ref p);
+ item = p.Key;
+ return retval;
+ }
+
+ public bool FindOrAdd(ref K item) { throw new ReadOnlyCollectionException(); }
+
+ public bool Update(K item) { throw new ReadOnlyCollectionException(); }
+
+ public bool Update(K item, out K olditem) { throw new ReadOnlyCollectionException(); }
+
+ public bool UpdateOrAdd(K item) { throw new ReadOnlyCollectionException(); }
+
+ public bool UpdateOrAdd(K item, out K olditem) { throw new ReadOnlyCollectionException(); }
+
+ public bool Remove(K item) { throw new ReadOnlyCollectionException(); }
+
+ public bool Remove(K item, out K removeditem) { throw new ReadOnlyCollectionException(); }
+
+ public void RemoveAllCopies(K item) { throw new ReadOnlyCollectionException(); }
+
+ public void RemoveAll<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
+
+ public void Clear() { throw new ReadOnlyCollectionException(); }
+
+ public void RetainAll<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
+
+ #endregion
+
+ #region IExtensible<K> Members
+ public override bool IsReadOnly { get { return true; } }
+
+ public bool AllowsDuplicates { get { return false; } }
+
+ public bool DuplicatesByCounting { get { return true; } }
+
+ public bool Add(K item) { throw new ReadOnlyCollectionException(); }
+
+ void SCG.ICollection<K>.Add(K item) { throw new ReadOnlyCollectionException(); }
+
+ public void AddAll(System.Collections.Generic.IEnumerable<K> items) { throw new ReadOnlyCollectionException(); }
+
+ public void AddAll<U>(System.Collections.Generic.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
+
+ public bool Check() { return sorteddict.Check(); }
+
+ #endregion
+
+ #region IDirectedCollectionValue<K> Members
+
+ public override IDirectedCollectionValue<K> Backwards()
+ {
+ return RangeAll().Backwards();
+ }
+
+ #endregion
+
+ #region IDirectedEnumerable<K> Members
+
+ IDirectedEnumerable<K> IDirectedEnumerable<K>.Backwards() { return Backwards(); }
+ #endregion
+
+ #region ICloneable Members
+
+ //TODO: test
+ /// <summary>
+ /// Make a shallow copy of this SortedKeysCollection.
+ /// </summary>
+ /// <returns></returns>
+ public virtual object Clone()
+ {
+ //
+ SortedArrayDictionary<K, V> dictclone = new SortedArrayDictionary<K, V>(sortedpairs.Count, comparer, EqualityComparer);
+ SortedArray<KeyValuePair<K, V>> sortedpairsclone = (SortedArray<KeyValuePair<K, V>>)(dictclone.sortedpairs);
+ foreach (K key in sorteddict.Keys)
+ {
+ sortedpairsclone.Add(new KeyValuePair<K, V>(key, default(V)));
+ }
+ return new SortedKeysCollection(dictclone, sortedpairsclone, comparer, EqualityComparer);
+ }
+
+ #endregion
+
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="stringbuilder"></param>
+ /// <param name="rest"></param>
+ /// <param name="formatProvider"></param>
+ /// <returns></returns>
+ public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
+ {
+ return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);
+ }
+
+ }
+
+ [Serializable]
+ class SortedArrayDictionary<K, V> : SortedDictionaryBase<K, V>, IDictionary<K, V>, ISortedDictionary<K, V>
+ {
+ #region Constructors
+
+ public SortedArrayDictionary() : this(Comparer<K>.Default, EqualityComparer<K>.Default) { }
+
+ /// <summary>
+ /// Create a red-black tree dictionary using an external comparer for keys.
+ /// </summary>
+ /// <param name="comparer">The external comparer</param>
+ public SortedArrayDictionary(SCG.IComparer<K> comparer) : this(comparer, new ComparerZeroHashCodeEqualityComparer<K>(comparer)) { }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="comparer"></param>
+ /// <param name="equalityComparer"></param>
+ public SortedArrayDictionary(SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> equalityComparer)
+ : base(comparer, equalityComparer)
+ {
+ pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(new KeyValuePairComparer<K, V>(comparer));
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <param name="comparer"></param>
+ /// <param name="equalityComparer"></param>
+ /// <param name="capacity"></param>
+ public SortedArrayDictionary(int capacity, SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> equalityComparer)
+ : base(comparer, equalityComparer)
+ {
+ pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(capacity, new KeyValuePairComparer<K, V>(comparer));
+ }
+ #endregion
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ public override object Clone()
+ {
+ SortedArrayDictionary<K, V> clone = new SortedArrayDictionary<K, V>(Comparer, EqualityComparer);
+ clone.sortedpairs.AddSorted(sortedpairs);
+ return clone;
+ }
+
+ }
+}
\ No newline at end of file
projects / mono.git / blobdiff