X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mcs%2Fclass%2FMono.C5%2FC5%2FDictionaries.cs;h=54899e2c9c8d0aebe322a4685176686f59f5a4ce;hb=81bd8db9cf9449aa500910c9fc9003cd77ed5244;hp=fcf84c2eb71ded5a3abe84a7cc52e480dfeaeeb0;hpb=04d1b4116331e3813b8f75304f714a5d61ba1214;p=mono.git
diff --git a/mcs/class/Mono.C5/C5/Dictionaries.cs b/mcs/class/Mono.C5/C5/Dictionaries.cs
index fcf84c2eb71..54899e2c9c8 100644
--- a/mcs/class/Mono.C5/C5/Dictionaries.cs
+++ b/mcs/class/Mono.C5/C5/Dictionaries.cs
@@ -1,1297 +1,1383 @@
-#if NET_2_0
-/*
- 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
-{
- ///
- /// An entry in a dictionary from K to V.
- ///
- [Serializable]
- public struct KeyValuePair : IEquatable>, IShowable
- {
- ///
- /// The key field of the entry
- ///
- public K Key;
-
- ///
- /// The value field of the entry
- ///
- public V Value;
-
- ///
- /// Create an entry with specified key and value
- ///
- /// The key
- /// The value
- public KeyValuePair(K key, V value) { Key = key; Value = value; }
-
-
- ///
- /// Create an entry with a specified key. The value will be the default value of type V
.
- ///
- /// The key
- public KeyValuePair(K key) { Key = key; Value = default(V); }
-
-
- ///
- /// Pretty print an entry
- ///
- /// (key, value)
- [Tested]
- public override string ToString() { return "(" + Key + ", " + Value + ")"; }
-
-
- ///
- /// Check equality of entries.
- ///
- /// The other object
- /// True if obj is an entry of the same type and has the same key and value
- [Tested]
- public override bool Equals(object obj)
- {
- if (!(obj is KeyValuePair))
- return false;
- KeyValuePair other = (KeyValuePair)obj;
- return Equals(other);
- }
-
-
- ///
- /// Get the hash code of the pair.
- ///
- /// The hash code
- [Tested]
- public override int GetHashCode() { return EqualityComparer.Default.GetHashCode(Key) + 13984681 * EqualityComparer.Default.GetHashCode(Value); }
-
- ///
- ///
- ///
- ///
- ///
- public bool Equals(KeyValuePair other)
- {
- return EqualityComparer.Default.Equals(Key, other.Key) && EqualityComparer.Default.Equals(Value, other.Value);
- }
-
- ///
- ///
- ///
- ///
- ///
- ///
- public static bool operator ==(KeyValuePair pair1, KeyValuePair pair2) { return pair1.Equals(pair2); }
-
- ///
- ///
- ///
- ///
- ///
- ///
- public static bool operator !=(KeyValuePair pair1, KeyValuePair pair2) { return !pair1.Equals(pair2); }
-
- #region IShowable Members
-
- ///
- ///
- ///
- ///
- ///
- ///
- ///
- 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
-
- ///
- ///
- ///
- ///
- ///
- ///
- public string ToString(string format, IFormatProvider formatProvider)
- {
- return Showing.ShowString(this, format, formatProvider);
- }
-
- #endregion
- }
-
-
-
- ///
- /// Default comparer for dictionary entries in a sorted dictionary.
- /// Entry comparisons only look at keys and uses an externally defined comparer for that.
- ///
- [Serializable]
- public class KeyValuePairComparer : SCG.IComparer>
- {
- SCG.IComparer comparer;
-
-
- ///
- /// Create an entry comparer for a item comparer of the keys
- ///
- /// Comparer of keys
- public KeyValuePairComparer(SCG.IComparer comparer)
- {
- if (comparer == null)
- throw new NullReferenceException();
- this.comparer = comparer;
- }
-
-
- ///
- /// Compare two entries
- ///
- /// First entry
- /// Second entry
- /// The result of comparing the keys
- [Tested]
- public int Compare(KeyValuePair entry1, KeyValuePair entry2)
- { return comparer.Compare(entry1.Key, entry2.Key); }
- }
-
-
-
- ///
- /// Default equalityComparer for dictionary entries.
- /// Operations only look at keys and uses an externaly defined equalityComparer for that.
- ///
- [Serializable]
- public sealed class KeyValuePairEqualityComparer : SCG.IEqualityComparer>
- {
- SCG.IEqualityComparer keyequalityComparer;
-
-
- ///
- /// Create an entry equalityComparer using the default equalityComparer for keys
- ///
- public KeyValuePairEqualityComparer() { keyequalityComparer = EqualityComparer.Default; }
-
-
- ///
- /// Create an entry equalityComparer from a specified item equalityComparer for the keys
- ///
- /// The key equalityComparer
- public KeyValuePairEqualityComparer(SCG.IEqualityComparer keyequalityComparer)
- {
- if (keyequalityComparer == null)
- throw new NullReferenceException("Key equality comparer cannot be null");
- this.keyequalityComparer = keyequalityComparer;
- }
-
-
- ///
- /// Get the hash code of the entry
- ///
- /// The entry
- /// The hash code of the key
- [Tested]
- public int GetHashCode(KeyValuePair entry) { return keyequalityComparer.GetHashCode(entry.Key); }
-
-
- ///
- /// Test two entries for equality
- ///
- /// First entry
- /// Second entry
- /// True if keys are equal
- [Tested]
- public bool Equals(KeyValuePair entry1, KeyValuePair entry2)
- { return keyequalityComparer.Equals(entry1.Key, entry2.Key); }
- }
-
-
-
- ///
- /// A base class for implementing a dictionary based on a set collection implementation.
- /// See the source code for for an example
- ///
- ///
- [Serializable]
- public abstract class DictionaryBase : CollectionValueBase>, IDictionary
- {
- ///
- /// The set collection of entries underlying this dictionary implementation
- ///
- protected ICollection> pairs;
-
- SCG.IEqualityComparer keyequalityComparer;
-
- #region Events
- ProxyEventBlock> eventBlock;
-
- ///
- /// The change event. Will be raised for every change operation on the collection.
- ///
- public override event CollectionChangedHandler> CollectionChanged
- {
- add { (eventBlock ?? (eventBlock = new ProxyEventBlock>(this, pairs))).CollectionChanged += value; }
- remove { if (eventBlock != null) eventBlock.CollectionChanged -= value; }
- }
-
- ///
- /// The change event. Will be raised for every change operation on the collection.
- ///
- public override event CollectionClearedHandler> CollectionCleared
- {
- add { (eventBlock ?? (eventBlock = new ProxyEventBlock>(this, pairs))).CollectionCleared += value; }
- remove { if (eventBlock != null) eventBlock.CollectionCleared -= value; }
- }
-
- ///
- /// The item added event. Will be raised for every individual addition to the collection.
- ///
- public override event ItemsAddedHandler> ItemsAdded
- {
- add { (eventBlock ?? (eventBlock = new ProxyEventBlock>(this, pairs))).ItemsAdded += value; }
- remove { if (eventBlock != null) eventBlock.ItemsAdded -= value; }
- }
-
- ///
- /// The item added event. Will be raised for every individual removal from the collection.
- ///
- public override event ItemsRemovedHandler> ItemsRemoved
- {
- add { (eventBlock ?? (eventBlock = new ProxyEventBlock>(this, pairs))).ItemsRemoved += value; }
- remove { if (eventBlock != null) eventBlock.ItemsRemoved -= value; }
- }
-
- ///
- ///
- ///
- public override EventTypeEnum ListenableEvents
- {
- get
- {
- return EventTypeEnum.Basic;
- }
- }
-
- ///
- ///
- ///
- public override EventTypeEnum ActiveEvents
- {
- get
- {
- return pairs.ActiveEvents;
- }
- }
-
- #endregion
-
- ///
- ///
- ///
- ///
- public DictionaryBase(SCG.IEqualityComparer keyequalityComparer) {
- if (keyequalityComparer == null)
- throw new NullReferenceException("Key equality comparer cannot be null");
- this.keyequalityComparer = keyequalityComparer; }
-
- #region IDictionary Members
-
- ///
- ///
- ///
- ///
- public virtual SCG.IEqualityComparer EqualityComparer { get { return keyequalityComparer; } }
-
-
- ///
- /// Add a new (key, value) pair (a mapping) to the dictionary.
- ///
- /// if there already is an entry with the same key.
- /// Key to add
- /// Value to add
- [Tested]
- public virtual void Add(K key, V value)
- {
- KeyValuePair p = new KeyValuePair(key, value);
-
- if (!pairs.Add(p))
- throw new DuplicateNotAllowedException("Key being added: '" + key + "'");
- }
-
- ///
- /// Add the entries from a collection of pairs to this dictionary.
- /// TODO: add restrictions L:K and W:V when the .Net SDK allows it
- ///
- ///
- /// If the input contains duplicate keys or a key already present in this dictionary.
- ///
- public virtual void AddAll(SCG.IEnumerable> entries)
- where L : K
- where W : V
- {
- foreach (KeyValuePair pair in entries)
- {
- KeyValuePair p = new KeyValuePair(pair.Key, pair.Value);
- if (!pairs.Add(p))
- throw new DuplicateNotAllowedException("Key being added: '" + pair.Key + "'");
- }
- }
-
- ///
- /// Remove an entry with a given key from the dictionary
- ///
- /// The key of the entry to remove
- /// True if an entry was found (and removed)
- [Tested]
- public virtual bool Remove(K key)
- {
- KeyValuePair p = new KeyValuePair(key);
-
- return pairs.Remove(p);
- }
-
-
- ///
- /// Remove an entry with a given key from the dictionary and report its value.
- ///
- /// The key of the entry to remove
- /// On exit, the value of the removed entry
- /// True if an entry was found (and removed)
- [Tested]
- public virtual bool Remove(K key, out V value)
- {
- KeyValuePair p = new KeyValuePair(key);
-
- if (pairs.Remove(p, out p))
- {
- value = p.Value;
- return true;
- }
- else
- {
- value = default(V);
- return false;
- }
- }
-
-
- ///
- /// Remove all entries from the dictionary
- ///
- [Tested]
- public virtual void Clear() { pairs.Clear(); }
-
- ///
- ///
- ///
- ///
- public virtual Speed ContainsSpeed { get { return pairs.ContainsSpeed; } }
-
- ///
- /// Check if there is an entry with a specified key
- ///
- /// The key to look for
- /// True if key was found
- [Tested]
- public virtual bool Contains(K key)
- {
- KeyValuePair p = new KeyValuePair(key);
-
- return pairs.Contains(p);
- }
-
- class LiftedEnumerable : SCG.IEnumerable> where H : K
- {
- SCG.IEnumerable keys;
- public LiftedEnumerable(SCG.IEnumerable keys) { this.keys = keys; }
- public SCG.IEnumerator> GetEnumerator() { foreach (H key in keys) yield return new KeyValuePair(key); }
-
- #region IEnumerable Members
-
- System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
- {
- throw new Exception("The method or operation is not implemented.");
- }
-
- #endregion
- }
-
- ///
- ///
- ///
- ///
- ///
- public virtual bool ContainsAll(SCG.IEnumerable keys) where H : K
- {
- return pairs.ContainsAll(new LiftedEnumerable(keys));
- }
-
- ///
- /// 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]".
- ///
- /// The key to look for
- /// On exit, the value of the entry
- /// True if key was found
- [Tested]
- public virtual bool Find(K key, out V value)
- {
- return Find(ref key, out value);
- }
- ///
- /// 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]".
- ///
- /// The key to look for
- /// On exit, the value of the entry
- /// True if key was found
- public virtual bool Find(ref K key, out V value)
- {
- KeyValuePair p = new KeyValuePair(key);
-
- if (pairs.Find(ref p))
- {
- key = p.Key;
- value = p.Value;
- return true;
- }
- else
- {
- value = default(V);
- return false;
- }
- }
-
-
- ///
- /// 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".
- ///
- /// The key to look for
- /// The new value
- /// True if key was found
- [Tested]
- public virtual bool Update(K key, V value)
- {
- KeyValuePair p = new KeyValuePair(key, value);
-
- return pairs.Update(p);
- }
-
-
- ///
- ///
- ///
- ///
- ///
- ///
- ///
- public virtual bool Update(K key, V value, out V oldvalue)
- {
- KeyValuePair p = new KeyValuePair(key, value);
-
- bool retval = pairs.Update(p, out p);
- oldvalue = p.Value;
- return retval;
- }
-
-
- ///
- /// 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.
- ///
- /// On entry the key to look for
- /// On entry the value to add if the key is not found.
- /// On exit the value found if any.
- /// True if key was found
- [Tested]
- public virtual bool FindOrAdd(K key, ref V value)
- {
- KeyValuePair p = new KeyValuePair(key, value);
-
- if (!pairs.FindOrAdd(ref p))
- return false;
- else
- {
- value = p.Value;
- //key = p.key;
- return true;
- }
- }
-
-
- ///
- /// 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.
- ///
- /// The key to look for
- /// The value to add or replace with.
- /// True if entry was updated.
- [Tested]
- public virtual bool UpdateOrAdd(K key, V value)
- {
- return pairs.UpdateOrAdd(new KeyValuePair(key, value));
- }
-
-
- ///
- /// 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.
- ///
- ///
- ///
- ///
- ///
- public virtual bool UpdateOrAdd(K key, V value, out V oldvalue)
- {
- KeyValuePair p = new KeyValuePair(key, value);
- bool retval = pairs.UpdateOrAdd(p, out p);
- oldvalue = p.Value;
- return retval;
- }
-
-
-
- #region Keys,Values support classes
-
- internal class ValuesCollection : CollectionValueBase, ICollectionValue
- {
- ICollection> pairs;
-
-
- internal ValuesCollection(ICollection> pairs)
- { this.pairs = pairs; }
-
-
- public override V Choose() { return pairs.Choose().Value; }
-
- [Tested]
- public override SCG.IEnumerator GetEnumerator()
- {
- //Updatecheck is performed by the pairs enumerator
- foreach (KeyValuePair 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; } }
- }
-
-
-
- internal class KeysCollection : CollectionValueBase, ICollectionValue
- {
- ICollection> pairs;
-
-
- internal KeysCollection(ICollection> pairs)
- { this.pairs = pairs; }
-
- public override K Choose() { return pairs.Choose().Key; }
-
- [Tested]
- public override SCG.IEnumerator GetEnumerator()
- {
- foreach (KeyValuePair 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
-
- ///
- ///
- ///
- /// A collection containg the all the keys of the dictionary
- [Tested]
- public virtual ICollectionValue Keys { [Tested]get { return new KeysCollection(pairs); } }
-
-
- ///
- ///
- ///
- /// A collection containing all the values of the dictionary
- [Tested]
- public virtual ICollectionValue Values { [Tested]get { return new ValuesCollection(pairs); } }
-
- ///
- ///
- ///
- public virtual Fun Fun { get { return delegate(K k) { return this[k]; }; } }
-
- ///
- /// Indexer by key for dictionary.
- /// The get method will throw an exception if no entry is found.
- /// The set method behaves like .
- ///
- /// On get if no entry is found.
- /// The value corresponding to the key
- [Tested]
- public virtual V this[K key]
- {
- [Tested]
- get
- {
- KeyValuePair p = new KeyValuePair(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(key, value)); }
- }
-
-
- ///
- ///
- ///
- /// True if dictionary is read only
- [Tested]
- public virtual bool IsReadOnly { [Tested]get { return pairs.IsReadOnly; } }
-
-
- ///
- /// Check the integrity of the internal data structures of this dictionary.
- ///
- /// True if check does not fail.
- [Tested]
- public virtual bool Check() { return pairs.Check(); }
-
- #endregion
-
- #region ICollectionValue> Members
-
- ///
- ///
- ///
- /// True if this collection is empty.
- public override bool IsEmpty { get { return pairs.IsEmpty; } }
-
-
- ///
- ///
- ///
- /// The number of entrues in the dictionary
- [Tested]
- public override int Count { [Tested]get { return pairs.Count; } }
-
- ///
- ///
- ///
- /// The number of entrues in the dictionary
- [Tested]
- public override Speed CountSpeed { [Tested]get { return pairs.CountSpeed; } }
-
- ///
- /// Choose some entry in this Dictionary.
- ///
- /// if collection is empty.
- ///
- public override KeyValuePair Choose() { return pairs.Choose(); }
-
- ///
- /// Create an enumerator for the collection of entries of the dictionary
- ///
- /// The enumerator
- [Tested]
- public override SCG.IEnumerator> GetEnumerator()
- {
- return pairs.GetEnumerator(); ;
- }
-
- #endregion
-
- ///
- ///
- ///
- ///
- ///
- ///
- ///
- public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
- {
- return Showing.ShowDictionary(this, stringbuilder, ref rest, formatProvider);
- }
-
- ///
- ///
- ///
- ///
- public abstract object Clone();
-
- }
-
- ///
- /// A base class for implementing a sorted dictionary based on a sorted set collection implementation.
- /// See the source code for for an example
- ///
- ///
- public abstract class SortedDictionaryBase : DictionaryBase, ISortedDictionary
- {
- #region Fields
-
- ///
- ///
- ///
- protected ISorted> sortedpairs;
- SCG.IComparer keycomparer;
-
- ///
- ///
- ///
- ///
- ///
- public SortedDictionaryBase(SCG.IComparer keycomparer, SCG.IEqualityComparer keyequalityComparer) : base(keyequalityComparer) { this.keycomparer = keycomparer; }
-
- #endregion
-
- #region ISortedDictionary Members
-
- ///
- /// The key comparer used by this dictionary.
- ///
- ///
- public SCG.IComparer Comparer { get { return keycomparer; } }
-
- ///
- ///
- ///
- ///
- public new ISorted Keys { get { return new SortedKeysCollection(this, sortedpairs, keycomparer, EqualityComparer); } }
-
- ///
- /// Get the entry in the dictionary whose key is the
- /// predecessor of a specified key.
- ///
- ///
- /// The key
- /// The entry
- [Tested]
- public KeyValuePair Predecessor(K key)
- {
- KeyValuePair p = new KeyValuePair(key);
-
- return sortedpairs.Predecessor(p);
- }
-
-
- ///
- /// Get the entry in the dictionary whose key is the
- /// weak predecessor of a specified key.
- ///
- ///
- /// The key
- /// The entry
- [Tested]
- public KeyValuePair WeakPredecessor(K key)
- {
- KeyValuePair p = new KeyValuePair(key);
-
- return sortedpairs.WeakPredecessor(p);
- }
-
-
- ///
- /// Get the entry in the dictionary whose key is the
- /// successor of a specified key.
- ///
- ///
- /// The key
- /// The entry
- [Tested]
- public KeyValuePair Successor(K key)
- {
- KeyValuePair p = new KeyValuePair(key);
-
- return sortedpairs.Successor(p);
- }
-
-
- ///
- /// Get the entry in the dictionary whose key is the
- /// weak successor of a specified key.
- ///
- ///
- /// The key
- /// The entry
- [Tested]
- public KeyValuePair WeakSuccessor(K key)
- {
- return sortedpairs.WeakSuccessor(new KeyValuePair(key));
- }
-
- #endregion
-
- #region ISortedDictionary Members
-
- ///
- ///
- ///
- ///
- public KeyValuePair FindMin()
- {
- return sortedpairs.FindMin();
- }
-
- ///
- ///
- ///
- ///
- public KeyValuePair DeleteMin()
- {
- return sortedpairs.DeleteMin();
- }
-
- ///
- ///
- ///
- ///
- public KeyValuePair FindMax()
- {
- return sortedpairs.FindMax();
- }
-
- ///
- ///
- ///
- ///
- public KeyValuePair DeleteMax()
- {
- return sortedpairs.DeleteMax();
- }
-
- ///
- ///
- ///
- ///
- ///
- ///
- ///
- ///
- ///
- public bool Cut(IComparable cutter, out KeyValuePair lowEntry, out bool lowIsValid, out KeyValuePair highEntry, out bool highIsValid)
- {
- return sortedpairs.Cut(new KeyValuePairComparable(cutter), out lowEntry, out lowIsValid, out highEntry, out highIsValid);
- }
-
- ///
- ///
- ///
- ///
- ///
- public IDirectedEnumerable> RangeFrom(K bot)
- {
- return sortedpairs.RangeFrom(new KeyValuePair(bot));
- }
-
- ///
- ///
- ///
- ///
- ///
- ///
- public IDirectedEnumerable> RangeFromTo(K bot, K top)
- {
- return sortedpairs.RangeFromTo(new KeyValuePair(bot), new KeyValuePair(top));
- }
-
- ///
- ///
- ///
- ///
- ///
- public IDirectedEnumerable> RangeTo(K top)
- {
- return sortedpairs.RangeTo(new KeyValuePair(top));
- }
-
- ///
- ///
- ///
- ///
- public IDirectedCollectionValue> RangeAll()
- {
- return sortedpairs.RangeAll();
- }
-
- ///
- ///
- ///
- ///
- public void AddSorted(SCG.IEnumerable> items)
- {
- sortedpairs.AddSorted(items);
- }
-
- ///
- ///
- ///
- ///
- public void RemoveRangeFrom(K lowKey)
- {
- sortedpairs.RemoveRangeFrom(new KeyValuePair(lowKey));
- }
-
- ///
- ///
- ///
- ///
- ///
- public void RemoveRangeFromTo(K lowKey, K highKey)
- {
- sortedpairs.RemoveRangeFromTo(new KeyValuePair(lowKey), new KeyValuePair(highKey));
- }
-
- ///
- ///
- ///
- ///
- public void RemoveRangeTo(K highKey)
- {
- sortedpairs.RemoveRangeTo(new KeyValuePair(highKey));
- }
-
- #endregion
-
- class KeyValuePairComparable : IComparable>
- {
- IComparable cutter;
-
- internal KeyValuePairComparable(IComparable cutter) { this.cutter = cutter; }
-
- public int CompareTo(KeyValuePair other) { return cutter.CompareTo(other.Key); }
-
- public bool Equals(KeyValuePair other) { return cutter.Equals(other.Key); }
- }
-
- class ProjectedDirectedEnumerable : MappedDirectedEnumerable, K>
- {
- public ProjectedDirectedEnumerable(IDirectedEnumerable> directedpairs) : base(directedpairs) { }
-
- public override K Map(KeyValuePair pair) { return pair.Key; }
-
- }
-
- class ProjectedDirectedCollectionValue : MappedDirectedCollectionValue, K>
- {
- public ProjectedDirectedCollectionValue(IDirectedCollectionValue> directedpairs) : base(directedpairs) { }
-
- public override K Map(KeyValuePair pair) { return pair.Key; }
-
- }
-
- class SortedKeysCollection : SequencedBase, ISorted
- {
- ISortedDictionary sorteddict;
- //TODO: eliminate this. Only problem is the Find method because we lack method on dictionary that also
- // returns the actual key.
- ISorted> sortedpairs;
- SCG.IComparer comparer;
-
- internal SortedKeysCollection(ISortedDictionary sorteddict, ISorted> sortedpairs, SCG.IComparer comparer, SCG.IEqualityComparer itemequalityComparer)
- :base(itemequalityComparer)
- {
- this.sorteddict = sorteddict;
- this.sortedpairs = sortedpairs;
- this.comparer = comparer;
- }
-
- public override K Choose() { return sorteddict.Choose().Key; }
-
- public override SCG.IEnumerator GetEnumerator()
- {
- foreach (KeyValuePair 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 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 Comparer { get { return comparer; } }
-
- 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 c, out K low, out bool lowIsValid, out K high, out bool highIsValid)
- {
- KeyValuePair 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 RangeFrom(K bot)
- {
- return new ProjectedDirectedEnumerable(sorteddict.RangeFrom(bot));
- }
-
- public IDirectedEnumerable RangeFromTo(K bot, K top)
- {
- return new ProjectedDirectedEnumerable(sorteddict.RangeFromTo(bot, top));
- }
-
- public IDirectedEnumerable RangeTo(K top)
- {
- return new ProjectedDirectedEnumerable(sorteddict.RangeTo(top));
- }
-
- public IDirectedCollectionValue RangeAll()
- {
- return new ProjectedDirectedCollectionValue(sorteddict.RangeAll());
- }
-
- public void AddSorted(SCG.IEnumerable 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 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; }
-
- ///
- ///
- ///
- ///
- public virtual ICollectionValue UniqueItems()
- {
- return this;
- }
-
- ///
- ///
- ///
- ///
- public virtual ICollectionValue> ItemMultiplicities()
- {
- return new MultiplicityOne(this);
- }
-
-
- public bool ContainsAll(SCG.IEnumerable 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 p = new KeyValuePair(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 (SCG.IEnumerable items) where U : K { throw new ReadOnlyCollectionException(); }
-
- public void Clear() { throw new ReadOnlyCollectionException(); }
-
- public void RetainAll(SCG.IEnumerable items) where U : K { throw new ReadOnlyCollectionException(); }
-
- #endregion
-
- #region IExtensible 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(); }
-
- public void AddAll(System.Collections.Generic.IEnumerable items) { throw new ReadOnlyCollectionException(); }
-
- public void AddAll(System.Collections.Generic.IEnumerable items) where U : K { throw new ReadOnlyCollectionException(); }
-
- public bool Check() { return sorteddict.Check(); }
-
- #endregion
-
- #region IDirectedCollectionValue Members
-
- public override IDirectedCollectionValue Backwards()
- {
- return RangeAll().Backwards();
- }
-
- #endregion
-
- #region IDirectedEnumerable Members
-
- IDirectedEnumerable IDirectedEnumerable.Backwards() { return Backwards(); }
- #endregion
-
- #region ICloneable Members
-
- //TODO: test
- ///
- /// Make a shallow copy of this SortedKeysCollection.
- ///
- ///
- public virtual object Clone()
- {
- //
- SortedArrayDictionary dictclone = new SortedArrayDictionary(sortedpairs.Count, comparer, EqualityComparer);
- SortedArray> sortedpairsclone = (SortedArray>)(dictclone.sortedpairs);
- foreach (K key in sorteddict.Keys)
- {
- sortedpairsclone.Add(new KeyValuePair(key, default(V)));
- }
- return new SortedKeysCollection(dictclone, sortedpairsclone, comparer, EqualityComparer);
- }
-
- #endregion
-
- }
-
- ///
- ///
- ///
- ///
- ///
- ///
- ///
- public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
- {
- return Showing.ShowDictionary(this, stringbuilder, ref rest, formatProvider);
- }
-
- }
-
- class SortedArrayDictionary : SortedDictionaryBase, IDictionary, ISortedDictionary
- {
- #region Constructors
-
- public SortedArrayDictionary() : this(Comparer.Default, EqualityComparer.Default) { }
-
- ///
- /// Create a red-black tree dictionary using an external comparer for keys.
- ///
- /// The external comparer
- public SortedArrayDictionary(SCG.IComparer comparer) : this(comparer, new ComparerZeroHashCodeEqualityComparer(comparer)) { }
-
- ///
- ///
- ///
- ///
- ///
- public SortedArrayDictionary(SCG.IComparer comparer, SCG.IEqualityComparer equalityComparer) : base(comparer,equalityComparer)
- {
- pairs = sortedpairs = new SortedArray>(new KeyValuePairComparer(comparer));
- }
-
- ///
- ///
- ///
- ///
- ///
- ///
- public SortedArrayDictionary(int capacity, SCG.IComparer comparer, SCG.IEqualityComparer equalityComparer) : base(comparer,equalityComparer)
- {
- pairs = sortedpairs = new SortedArray>(capacity, new KeyValuePairComparer(comparer));
- }
- #endregion
-
- ///
- ///
- ///
- ///
- public override object Clone()
- {
- SortedArrayDictionary clone = new SortedArrayDictionary(Comparer, EqualityComparer);
- clone.sortedpairs.AddSorted(sortedpairs);
- return clone;
- }
-
- }
-}
-#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
+{
+ ///
+ /// An entry in a dictionary from K to V.
+ ///
+ [Serializable]
+ public struct KeyValuePair : IEquatable>, IShowable
+ {
+ ///
+ /// The key field of the entry
+ ///
+ public K Key;
+
+ ///
+ /// The value field of the entry
+ ///
+ public V Value;
+
+ ///
+ /// Create an entry with specified key and value
+ ///
+ /// The key
+ /// The value
+ public KeyValuePair(K key, V value) { Key = key; Value = value; }
+
+
+ ///
+ /// Create an entry with a specified key. The value will be the default value of type V
.
+ ///
+ /// The key
+ public KeyValuePair(K key) { Key = key; Value = default(V); }
+
+
+ ///
+ /// Pretty print an entry
+ ///
+ /// (key, value)
+ [Tested]
+ public override string ToString() { return "(" + Key + ", " + Value + ")"; }
+
+
+ ///
+ /// Check equality of entries.
+ ///
+ /// The other object
+ /// True if obj is an entry of the same type and has the same key and value
+ [Tested]
+ public override bool Equals(object obj)
+ {
+ if (!(obj is KeyValuePair))
+ return false;
+ KeyValuePair other = (KeyValuePair)obj;
+ return Equals(other);
+ }
+
+
+ ///
+ /// Get the hash code of the pair.
+ ///
+ /// The hash code
+ [Tested]
+ public override int GetHashCode() { return EqualityComparer.Default.GetHashCode(Key) + 13984681 * EqualityComparer.Default.GetHashCode(Value); }
+
+ ///
+ ///
+ ///
+ ///
+ ///
+ public bool Equals(KeyValuePair other)
+ {
+ return EqualityComparer.Default.Equals(Key, other.Key) && EqualityComparer.Default.Equals(Value, other.Value);
+ }
+
+ ///
+ ///
+ ///
+ ///
+ ///
+ ///
+ public static bool operator ==(KeyValuePair pair1, KeyValuePair pair2) { return pair1.Equals(pair2); }
+
+ ///
+ ///
+ ///
+ ///
+ ///
+ ///
+ public static bool operator !=(KeyValuePair pair1, KeyValuePair pair2) { return !pair1.Equals(pair2); }
+
+ #region IShowable Members
+
+ ///
+ ///
+ ///
+ ///
+ ///
+ ///
+ ///
+ 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
+
+ ///
+ ///
+ ///
+ ///
+ ///
+ ///
+ public string ToString(string format, IFormatProvider formatProvider)
+ {
+ return Showing.ShowString(this, format, formatProvider);
+ }
+
+ #endregion
+ }
+
+
+
+ ///
+ /// Default comparer for dictionary entries in a sorted dictionary.
+ /// Entry comparisons only look at keys and uses an externally defined comparer for that.
+ ///
+ [Serializable]
+ public class KeyValuePairComparer : SCG.IComparer>
+ {
+ SCG.IComparer comparer;
+
+
+ ///
+ /// Create an entry comparer for a item comparer of the keys
+ ///
+ /// Comparer of keys
+ public KeyValuePairComparer(SCG.IComparer comparer)
+ {
+ if (comparer == null)
+ throw new NullReferenceException();
+ this.comparer = comparer;
+ }
+
+
+ ///
+ /// Compare two entries
+ ///
+ /// First entry
+ /// Second entry
+ /// The result of comparing the keys
+ [Tested]
+ public int Compare(KeyValuePair entry1, KeyValuePair entry2)
+ { return comparer.Compare(entry1.Key, entry2.Key); }
+ }
+
+
+
+ ///
+ /// Default equalityComparer for dictionary entries.
+ /// Operations only look at keys and uses an externaly defined equalityComparer for that.
+ ///
+ [Serializable]
+ public sealed class KeyValuePairEqualityComparer : SCG.IEqualityComparer>
+ {
+ SCG.IEqualityComparer keyequalityComparer;
+
+
+ ///
+ /// Create an entry equalityComparer using the default equalityComparer for keys
+ ///
+ public KeyValuePairEqualityComparer() { keyequalityComparer = EqualityComparer.Default; }
+
+
+ ///
+ /// Create an entry equalityComparer from a specified item equalityComparer for the keys
+ ///
+ /// The key equalityComparer
+ public KeyValuePairEqualityComparer(SCG.IEqualityComparer keyequalityComparer)
+ {
+ if (keyequalityComparer == null)
+ throw new NullReferenceException("Key equality comparer cannot be null");
+ this.keyequalityComparer = keyequalityComparer;
+ }
+
+
+ ///
+ /// Get the hash code of the entry
+ ///
+ /// The entry
+ /// The hash code of the key
+ [Tested]
+ public int GetHashCode(KeyValuePair entry) { return keyequalityComparer.GetHashCode(entry.Key); }
+
+
+ ///
+ /// Test two entries for equality
+ ///
+ /// First entry
+ /// Second entry
+ /// True if keys are equal
+ [Tested]
+ public bool Equals(KeyValuePair entry1, KeyValuePair entry2)
+ { return keyequalityComparer.Equals(entry1.Key, entry2.Key); }
+ }
+
+
+
+ ///
+ /// A base class for implementing a dictionary based on a set collection implementation.
+ /// See the source code for for an example
+ ///
+ ///
+ [Serializable]
+ public abstract class DictionaryBase : CollectionValueBase>, IDictionary
+ {
+ ///
+ /// The set collection of entries underlying this dictionary implementation
+ ///
+ protected ICollection> pairs;
+
+ SCG.IEqualityComparer keyequalityComparer;
+
+ #region Events
+ ProxyEventBlock> eventBlock;
+
+ ///
+ /// The change event. Will be raised for every change operation on the collection.
+ ///
+ public override event CollectionChangedHandler> CollectionChanged
+ {
+ add { (eventBlock ?? (eventBlock = new ProxyEventBlock