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>(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 + + /// + /// + /// + /// + protected 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); + } + + [Serializable] + 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 + [Serializable] + 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; } } + } + + + + [Serializable] + 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 + /// + /// + [Serializable] + public abstract class SortedDictionaryBase : DictionaryBase, ISortedDictionary + { + #region Fields + + /// + /// + /// + protected ISorted> sortedpairs; + SCG.IComparer keycomparer; + + /// + /// + /// + /// + /// + protected 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); } } + + /// + /// Find the entry in the dictionary whose key is the + /// predecessor of the specified key. + /// + /// The key + /// The predecessor, if any + /// True if key has a predecessor + [Tested] + public bool TryPredecessor(K key, out KeyValuePair res) + { + return sortedpairs.TryPredecessor(new KeyValuePair(key), out res); + } + + /// + /// Find the entry in the dictionary whose key is the + /// successor of the specified key. + /// + /// The key + /// The successor, if any + /// True if the key has a successor + [Tested] + public bool TrySuccessor(K key, out KeyValuePair res) + { + return sortedpairs.TrySuccessor(new KeyValuePair(key), out res); + } + + /// + /// Find the entry in the dictionary whose key is the + /// weak predecessor of the specified key. + /// + /// The key + /// The predecessor, if any + /// True if key has a weak predecessor + [Tested] + public bool TryWeakPredecessor(K key, out KeyValuePair res) + { + return sortedpairs.TryWeakPredecessor(new KeyValuePair(key), out res); + } + + /// + /// Find the entry in the dictionary whose key is the + /// weak successor of the specified key. + /// + /// The key + /// The weak successor, if any + /// True if the key has a weak successor + [Tested] + public bool TryWeakSuccessor(K key, out KeyValuePair res) + { + return sortedpairs.TryWeakSuccessor(new KeyValuePair(key), out res); + } + + /// + /// Get the entry in the dictionary whose key is the + /// predecessor of the specified key. + /// + /// + /// The key + /// The entry + [Tested] + public KeyValuePair Predecessor(K key) + { + return sortedpairs.Predecessor(new KeyValuePair(key)); + } + + /// + /// Get the entry in the dictionary whose key is the + /// successor of the specified key. + /// + /// + /// The key + /// The entry + [Tested] + public KeyValuePair Successor(K key) + { + return sortedpairs.Successor(new KeyValuePair(key)); + } + + /// + /// Get the entry in the dictionary whose key is the + /// weak predecessor of the specified key. + /// + /// + /// The key + /// The entry + [Tested] + public KeyValuePair WeakPredecessor(K key) + { + return sortedpairs.WeakPredecessor(new KeyValuePair(key)); + } + + /// + /// Get the entry in the dictionary whose key is the + /// weak successor of the 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 + [Serializable] + 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); } + } + + [Serializable] + class ProjectedDirectedEnumerable : MappedDirectedEnumerable, K> + { + public ProjectedDirectedEnumerable(IDirectedEnumerable> directedpairs) : base(directedpairs) { } + + public override K Map(KeyValuePair pair) { return pair.Key; } + + } + + [Serializable] + class ProjectedDirectedCollectionValue : MappedDirectedCollectionValue, K> + { + public ProjectedDirectedCollectionValue(IDirectedCollectionValue> directedpairs) : base(directedpairs) { } + + public override K Map(KeyValuePair pair) { return pair.Key; } + + } + + [Serializable] + 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 bool TryPredecessor(K item, out K res) + { + KeyValuePair pRes; + bool success = sorteddict.TryPredecessor(item, out pRes); + res = pRes.Key; + return success; + } + + public bool TrySuccessor(K item, out K res) + { + KeyValuePair pRes; + bool success = sorteddict.TrySuccessor(item, out pRes); + res = pRes.Key; + return success; + } + + public bool TryWeakPredecessor(K item, out K res) + { + KeyValuePair pRes; + bool success = sorteddict.TryWeakPredecessor(item, out pRes); + res = pRes.Key; + return success; + } + + public bool TryWeakSuccessor(K item, out K res) + { + KeyValuePair 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 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(); } + + void SCG.ICollection.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); + } + + } + + [Serializable] + 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; + } + + } +} \ No newline at end of file