3 Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
\r
4 Permission is hereby granted, free of charge, to any person obtaining a copy
\r
5 of this software and associated documentation files (the "Software"), to deal
\r
6 in the Software without restriction, including without limitation the rights
\r
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
\r
8 copies of the Software, and to permit persons to whom the Software is
\r
9 furnished to do so, subject to the following conditions:
\r
11 The above copyright notice and this permission notice shall be included in
\r
12 all copies or substantial portions of the Software.
\r
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
\r
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
\r
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
\r
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
\r
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
\r
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
\r
24 using System.Diagnostics;
\r
25 using SCG = System.Collections.Generic;
\r
29 /// An entry in a dictionary from K to V.
\r
32 public struct KeyValuePair<K, V> : IEquatable<KeyValuePair<K, V>>, IShowable
\r
35 /// The key field of the entry
\r
40 /// The value field of the entry
\r
45 /// Create an entry with specified key and value
\r
47 /// <param name="key">The key</param>
\r
48 /// <param name="value">The value</param>
\r
49 public KeyValuePair(K key, V value) { Key = key; Value = value; }
\r
53 /// Create an entry with a specified key. The value will be the default value of type <code>V</code>.
\r
55 /// <param name="key">The key</param>
\r
56 public KeyValuePair(K key) { Key = key; Value = default(V); }
\r
60 /// Pretty print an entry
\r
62 /// <returns>(key, value)</returns>
\r
64 public override string ToString() { return "(" + Key + ", " + Value + ")"; }
\r
68 /// Check equality of entries.
\r
70 /// <param name="obj">The other object</param>
\r
71 /// <returns>True if obj is an entry of the same type and has the same key and value</returns>
\r
73 public override bool Equals(object obj)
\r
75 if (!(obj is KeyValuePair<K, V>))
\r
77 KeyValuePair<K, V> other = (KeyValuePair<K, V>)obj;
\r
78 return Equals(other);
\r
83 /// Get the hash code of the pair.
\r
85 /// <returns>The hash code</returns>
\r
87 public override int GetHashCode() { return EqualityComparer<K>.Default.GetHashCode(Key) + 13984681 * EqualityComparer<V>.Default.GetHashCode(Value); }
\r
92 /// <param name="other"></param>
\r
93 /// <returns></returns>
\r
94 public bool Equals(KeyValuePair<K, V> other)
\r
96 return EqualityComparer<K>.Default.Equals(Key, other.Key) && EqualityComparer<V>.Default.Equals(Value, other.Value);
\r
102 /// <param name="pair1"></param>
\r
103 /// <param name="pair2"></param>
\r
104 /// <returns></returns>
\r
105 public static bool operator ==(KeyValuePair<K, V> pair1, KeyValuePair<K, V> pair2) { return pair1.Equals(pair2); }
\r
110 /// <param name="pair1"></param>
\r
111 /// <param name="pair2"></param>
\r
112 /// <returns></returns>
\r
113 public static bool operator !=(KeyValuePair<K, V> pair1, KeyValuePair<K, V> pair2) { return !pair1.Equals(pair2); }
\r
115 #region IShowable Members
\r
120 /// <param name="stringbuilder"></param>
\r
121 /// <param name="formatProvider"></param>
\r
122 /// <param name="rest"></param>
\r
123 /// <returns></returns>
\r
124 public bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
\r
128 if (!Showing.Show(Key, stringbuilder, ref rest, formatProvider))
\r
130 stringbuilder.Append(" => ");
\r
132 if (!Showing.Show(Value, stringbuilder, ref rest, formatProvider))
\r
138 #region IFormattable Members
\r
143 /// <param name="format"></param>
\r
144 /// <param name="formatProvider"></param>
\r
145 /// <returns></returns>
\r
146 public string ToString(string format, IFormatProvider formatProvider)
\r
148 return Showing.ShowString(this, format, formatProvider);
\r
157 /// Default comparer for dictionary entries in a sorted dictionary.
\r
158 /// Entry comparisons only look at keys and uses an externally defined comparer for that.
\r
161 public class KeyValuePairComparer<K, V> : SCG.IComparer<KeyValuePair<K, V>>
\r
163 SCG.IComparer<K> comparer;
\r
167 /// Create an entry comparer for a item comparer of the keys
\r
169 /// <param name="comparer">Comparer of keys</param>
\r
170 public KeyValuePairComparer(SCG.IComparer<K> comparer)
\r
172 if (comparer == null)
\r
173 throw new NullReferenceException();
\r
174 this.comparer = comparer;
\r
179 /// Compare two entries
\r
181 /// <param name="entry1">First entry</param>
\r
182 /// <param name="entry2">Second entry</param>
\r
183 /// <returns>The result of comparing the keys</returns>
\r
185 public int Compare(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)
\r
186 { return comparer.Compare(entry1.Key, entry2.Key); }
\r
192 /// Default equalityComparer for dictionary entries.
\r
193 /// Operations only look at keys and uses an externaly defined equalityComparer for that.
\r
196 public sealed class KeyValuePairEqualityComparer<K, V> : SCG.IEqualityComparer<KeyValuePair<K, V>>
\r
198 SCG.IEqualityComparer<K> keyequalityComparer;
\r
202 /// Create an entry equalityComparer using the default equalityComparer for keys
\r
204 public KeyValuePairEqualityComparer() { keyequalityComparer = EqualityComparer<K>.Default; }
\r
208 /// Create an entry equalityComparer from a specified item equalityComparer for the keys
\r
210 /// <param name="keyequalityComparer">The key equalityComparer</param>
\r
211 public KeyValuePairEqualityComparer(SCG.IEqualityComparer<K> keyequalityComparer)
\r
213 if (keyequalityComparer == null)
\r
214 throw new NullReferenceException("Key equality comparer cannot be null");
\r
215 this.keyequalityComparer = keyequalityComparer;
\r
220 /// Get the hash code of the entry
\r
222 /// <param name="entry">The entry</param>
\r
223 /// <returns>The hash code of the key</returns>
\r
225 public int GetHashCode(KeyValuePair<K, V> entry) { return keyequalityComparer.GetHashCode(entry.Key); }
\r
229 /// Test two entries for equality
\r
231 /// <param name="entry1">First entry</param>
\r
232 /// <param name="entry2">Second entry</param>
\r
233 /// <returns>True if keys are equal</returns>
\r
235 public bool Equals(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)
\r
236 { return keyequalityComparer.Equals(entry1.Key, entry2.Key); }
\r
242 /// A base class for implementing a dictionary based on a set collection implementation.
\r
243 /// <i>See the source code for <see cref="T:C5.HashDictionary`2"/> for an example</i>
\r
247 public abstract class DictionaryBase<K, V> : CollectionValueBase<KeyValuePair<K, V>>, IDictionary<K, V>
\r
250 /// The set collection of entries underlying this dictionary implementation
\r
252 protected ICollection<KeyValuePair<K, V>> pairs;
\r
254 SCG.IEqualityComparer<K> keyequalityComparer;
\r
257 ProxyEventBlock<KeyValuePair<K, V>> eventBlock;
\r
260 /// The change event. Will be raised for every change operation on the collection.
\r
262 public override event CollectionChangedHandler<KeyValuePair<K, V>> CollectionChanged
\r
264 add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionChanged += value; }
\r
265 remove { if (eventBlock != null) eventBlock.CollectionChanged -= value; }
\r
269 /// The change event. Will be raised for every change operation on the collection.
\r
271 public override event CollectionClearedHandler<KeyValuePair<K, V>> CollectionCleared
\r
273 add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionCleared += value; }
\r
274 remove { if (eventBlock != null) eventBlock.CollectionCleared -= value; }
\r
278 /// The item added event. Will be raised for every individual addition to the collection.
\r
280 public override event ItemsAddedHandler<KeyValuePair<K, V>> ItemsAdded
\r
282 add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsAdded += value; }
\r
283 remove { if (eventBlock != null) eventBlock.ItemsAdded -= value; }
\r
287 /// The item added event. Will be raised for every individual removal from the collection.
\r
289 public override event ItemsRemovedHandler<KeyValuePair<K, V>> ItemsRemoved
\r
291 add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsRemoved += value; }
\r
292 remove { if (eventBlock != null) eventBlock.ItemsRemoved -= value; }
\r
298 public override EventTypeEnum ListenableEvents
\r
302 return EventTypeEnum.Basic;
\r
309 public override EventTypeEnum ActiveEvents
\r
313 return pairs.ActiveEvents;
\r
322 /// <param name="keyequalityComparer"></param>
\r
323 public DictionaryBase(SCG.IEqualityComparer<K> keyequalityComparer) {
\r
324 if (keyequalityComparer == null)
\r
325 throw new NullReferenceException("Key equality comparer cannot be null");
\r
326 this.keyequalityComparer = keyequalityComparer; }
\r
328 #region IDictionary<K,V> Members
\r
333 /// <value></value>
\r
334 public virtual SCG.IEqualityComparer<K> EqualityComparer { get { return keyequalityComparer; } }
\r
338 /// Add a new (key, value) pair (a mapping) to the dictionary.
\r
340 /// <exception cref="DuplicateNotAllowedException"> if there already is an entry with the same key. </exception>
\r
341 /// <param name="key">Key to add</param>
\r
342 /// <param name="value">Value to add</param>
\r
344 public virtual void Add(K key, V value)
\r
346 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
\r
349 throw new DuplicateNotAllowedException("Key being added: '" + key + "'");
\r
353 /// Add the entries from a collection of <see cref="T:C5.KeyValuePair`2"/> pairs to this dictionary.
\r
354 /// <para><b>TODO: add restrictions L:K and W:V when the .Net SDK allows it </b></para>
\r
356 /// <exception cref="DuplicateNotAllowedException">
\r
357 /// If the input contains duplicate keys or a key already present in this dictionary.</exception>
\r
358 /// <param name="entries"></param>
\r
359 public virtual void AddAll<L,W>(SCG.IEnumerable<KeyValuePair<L, W>> entries)
\r
363 foreach (KeyValuePair<L, W> pair in entries)
\r
365 KeyValuePair<K, V> p = new KeyValuePair<K, V>(pair.Key, pair.Value);
\r
367 throw new DuplicateNotAllowedException("Key being added: '" + pair.Key + "'");
\r
372 /// Remove an entry with a given key from the dictionary
\r
374 /// <param name="key">The key of the entry to remove</param>
\r
375 /// <returns>True if an entry was found (and removed)</returns>
\r
377 public virtual bool Remove(K key)
\r
379 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
381 return pairs.Remove(p);
\r
386 /// Remove an entry with a given key from the dictionary and report its value.
\r
388 /// <param name="key">The key of the entry to remove</param>
\r
389 /// <param name="value">On exit, the value of the removed entry</param>
\r
390 /// <returns>True if an entry was found (and removed)</returns>
\r
392 public virtual bool Remove(K key, out V value)
\r
394 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
396 if (pairs.Remove(p, out p))
\r
403 value = default(V);
\r
410 /// Remove all entries from the dictionary
\r
413 public virtual void Clear() { pairs.Clear(); }
\r
418 /// <value></value>
\r
419 public virtual Speed ContainsSpeed { get { return pairs.ContainsSpeed; } }
\r
422 /// Check if there is an entry with a specified key
\r
424 /// <param name="key">The key to look for</param>
\r
425 /// <returns>True if key was found</returns>
\r
427 public virtual bool Contains(K key)
\r
429 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
431 return pairs.Contains(p);
\r
434 class LiftedEnumerable<H> : SCG.IEnumerable<KeyValuePair<K, V>> where H : K
\r
436 SCG.IEnumerable<H> keys;
\r
437 public LiftedEnumerable(SCG.IEnumerable<H> keys) { this.keys = keys; }
\r
438 public SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator() { foreach (H key in keys) yield return new KeyValuePair<K, V>(key); }
\r
440 #region IEnumerable Members
\r
442 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
\r
444 throw new Exception("The method or operation is not implemented.");
\r
453 /// <param name="keys"></param>
\r
454 /// <returns></returns>
\r
455 public virtual bool ContainsAll<H>(SCG.IEnumerable<H> keys) where H : K
\r
457 return pairs.ContainsAll(new LiftedEnumerable<H>(keys));
\r
461 /// Check if there is an entry with a specified key and report the corresponding
\r
462 /// value if found. This can be seen as a safe form of "val = this[key]".
\r
464 /// <param name="key">The key to look for</param>
\r
465 /// <param name="value">On exit, the value of the entry</param>
\r
466 /// <returns>True if key was found</returns>
\r
468 public virtual bool Find(K key, out V value)
\r
470 return Find(ref key, out value);
\r
473 /// Check if there is an entry with a specified key and report the corresponding
\r
474 /// value if found. This can be seen as a safe form of "val = this[key]".
\r
476 /// <param name="key">The key to look for</param>
\r
477 /// <param name="value">On exit, the value of the entry</param>
\r
478 /// <returns>True if key was found</returns>
\r
479 public virtual bool Find(ref K key, out V value)
\r
481 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
483 if (pairs.Find(ref p))
\r
491 value = default(V);
\r
498 /// Look for a specific key in the dictionary and if found replace the value with a new one.
\r
499 /// This can be seen as a non-adding version of "this[key] = val".
\r
501 /// <param name="key">The key to look for</param>
\r
502 /// <param name="value">The new value</param>
\r
503 /// <returns>True if key was found</returns>
\r
505 public virtual bool Update(K key, V value)
\r
507 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
\r
509 return pairs.Update(p);
\r
516 /// <param name="key"></param>
\r
517 /// <param name="value"></param>
\r
518 /// <param name="oldvalue"></param>
\r
519 /// <returns></returns>
\r
520 public virtual bool Update(K key, V value, out V oldvalue)
\r
522 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
\r
524 bool retval = pairs.Update(p, out p);
\r
525 oldvalue = p.Value;
\r
531 /// Look for a specific key in the dictionary. If found, report the corresponding value,
\r
532 /// else add an entry with the key and the supplied value.
\r
534 /// <param name="key">On entry the key to look for</param>
\r
535 /// <param name="value">On entry the value to add if the key is not found.
\r
536 /// On exit the value found if any.</param>
\r
537 /// <returns>True if key was found</returns>
\r
539 public virtual bool FindOrAdd(K key, ref V value)
\r
541 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
\r
543 if (!pairs.FindOrAdd(ref p))
\r
555 /// Update value in dictionary corresponding to key if found, else add new entry.
\r
556 /// More general than "this[key] = val;" by reporting if key was found.
\r
558 /// <param name="key">The key to look for</param>
\r
559 /// <param name="value">The value to add or replace with.</param>
\r
560 /// <returns>True if entry was updated.</returns>
\r
562 public virtual bool UpdateOrAdd(K key, V value)
\r
564 return pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value));
\r
569 /// Update value in dictionary corresponding to key if found, else add new entry.
\r
570 /// More general than "this[key] = val;" by reporting if key was found and the old value if any.
\r
572 /// <param name="key"></param>
\r
573 /// <param name="value"></param>
\r
574 /// <param name="oldvalue"></param>
\r
575 /// <returns></returns>
\r
576 public virtual bool UpdateOrAdd(K key, V value, out V oldvalue)
\r
578 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
\r
579 bool retval = pairs.UpdateOrAdd(p, out p);
\r
580 oldvalue = p.Value;
\r
586 #region Keys,Values support classes
\r
588 internal class ValuesCollection : CollectionValueBase<V>, ICollectionValue<V>
\r
590 ICollection<KeyValuePair<K, V>> pairs;
\r
593 internal ValuesCollection(ICollection<KeyValuePair<K, V>> pairs)
\r
594 { this.pairs = pairs; }
\r
597 public override V Choose() { return pairs.Choose().Value; }
\r
600 public override SCG.IEnumerator<V> GetEnumerator()
\r
602 //Updatecheck is performed by the pairs enumerator
\r
603 foreach (KeyValuePair<K, V> p in pairs)
\r
604 yield return p.Value;
\r
607 public override bool IsEmpty { get { return pairs.IsEmpty; } }
\r
610 public override int Count { [Tested]get { return pairs.Count; } }
\r
612 public override Speed CountSpeed { get { return Speed.Constant; } }
\r
617 internal class KeysCollection : CollectionValueBase<K>, ICollectionValue<K>
\r
619 ICollection<KeyValuePair<K, V>> pairs;
\r
622 internal KeysCollection(ICollection<KeyValuePair<K, V>> pairs)
\r
623 { this.pairs = pairs; }
\r
625 public override K Choose() { return pairs.Choose().Key; }
\r
628 public override SCG.IEnumerator<K> GetEnumerator()
\r
630 foreach (KeyValuePair<K, V> p in pairs)
\r
631 yield return p.Key;
\r
634 public override bool IsEmpty { get { return pairs.IsEmpty; } }
\r
637 public override int Count { [Tested]get { return pairs.Count; } }
\r
639 public override Speed CountSpeed { get { return pairs.CountSpeed; } }
\r
646 /// <value>A collection containg the all the keys of the dictionary</value>
\r
648 public virtual ICollectionValue<K> Keys { [Tested]get { return new KeysCollection(pairs); } }
\r
654 /// <value>A collection containing all the values of the dictionary</value>
\r
656 public virtual ICollectionValue<V> Values { [Tested]get { return new ValuesCollection(pairs); } }
\r
661 public virtual Fun<K, V> Fun { get { return delegate(K k) { return this[k]; }; } }
\r
664 /// Indexer by key for dictionary.
\r
665 /// <para>The get method will throw an exception if no entry is found. </para>
\r
666 /// <para>The set method behaves like <see cref="M:C5.DictionaryBase`2.UpdateOrAdd(`0,`1)"/>.</para>
\r
668 /// <exception cref="NoSuchItemException"> On get if no entry is found. </exception>
\r
669 /// <value>The value corresponding to the key</value>
\r
671 public virtual V this[K key]
\r
676 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
678 if (pairs.Find(ref p))
\r
681 throw new NoSuchItemException("Key '" + key.ToString() + "' not present in Dictionary");
\r
685 { pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value)); }
\r
692 /// <value>True if dictionary is read only</value>
\r
694 public virtual bool IsReadOnly { [Tested]get { return pairs.IsReadOnly; } }
\r
698 /// Check the integrity of the internal data structures of this dictionary.
\r
700 /// <returns>True if check does not fail.</returns>
\r
702 public virtual bool Check() { return pairs.Check(); }
\r
706 #region ICollectionValue<KeyValuePair<K,V>> Members
\r
711 /// <value>True if this collection is empty.</value>
\r
712 public override bool IsEmpty { get { return pairs.IsEmpty; } }
\r
718 /// <value>The number of entrues in the dictionary</value>
\r
720 public override int Count { [Tested]get { return pairs.Count; } }
\r
725 /// <value>The number of entrues in the dictionary</value>
\r
727 public override Speed CountSpeed { [Tested]get { return pairs.CountSpeed; } }
\r
730 /// Choose some entry in this Dictionary.
\r
732 /// <exception cref="NoSuchItemException">if collection is empty.</exception>
\r
733 /// <returns></returns>
\r
734 public override KeyValuePair<K, V> Choose() { return pairs.Choose(); }
\r
737 /// Create an enumerator for the collection of entries of the dictionary
\r
739 /// <returns>The enumerator</returns>
\r
741 public override SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator()
\r
743 return pairs.GetEnumerator(); ;
\r
751 /// <param name="stringbuilder"></param>
\r
752 /// <param name="rest"></param>
\r
753 /// <param name="formatProvider"></param>
\r
754 /// <returns></returns>
\r
755 public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
\r
757 return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);
\r
763 /// <returns></returns>
\r
764 public abstract object Clone();
\r
769 /// A base class for implementing a sorted dictionary based on a sorted set collection implementation.
\r
770 /// <i>See the source code for <see cref="T:C5.TreeDictionary`2"/> for an example</i>
\r
773 public abstract class SortedDictionaryBase<K, V> : DictionaryBase<K, V>, ISortedDictionary<K, V>
\r
780 protected ISorted<KeyValuePair<K, V>> sortedpairs;
\r
781 SCG.IComparer<K> keycomparer;
\r
786 /// <param name="keycomparer"></param>
\r
787 /// <param name="keyequalityComparer"></param>
\r
788 public SortedDictionaryBase(SCG.IComparer<K> keycomparer, SCG.IEqualityComparer<K> keyequalityComparer) : base(keyequalityComparer) { this.keycomparer = keycomparer; }
\r
792 #region ISortedDictionary<K,V> Members
\r
795 /// The key comparer used by this dictionary.
\r
797 /// <value></value>
\r
798 public SCG.IComparer<K> Comparer { get { return keycomparer; } }
\r
803 /// <value></value>
\r
804 public new ISorted<K> Keys { get { return new SortedKeysCollection(this, sortedpairs, keycomparer, EqualityComparer); } }
\r
807 /// Get the entry in the dictionary whose key is the
\r
808 /// predecessor of a specified key.
\r
810 /// <exception cref="NoSuchItemException"></exception>
\r
811 /// <param name="key">The key</param>
\r
812 /// <returns>The entry</returns>
\r
814 public KeyValuePair<K, V> Predecessor(K key)
\r
816 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
818 return sortedpairs.Predecessor(p);
\r
823 /// Get the entry in the dictionary whose key is the
\r
824 /// weak predecessor of a specified key.
\r
826 /// <exception cref="NoSuchItemException"></exception>
\r
827 /// <param name="key">The key</param>
\r
828 /// <returns>The entry</returns>
\r
830 public KeyValuePair<K, V> WeakPredecessor(K key)
\r
832 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
834 return sortedpairs.WeakPredecessor(p);
\r
839 /// Get the entry in the dictionary whose key is the
\r
840 /// successor of a specified key.
\r
842 /// <exception cref="NoSuchItemException"></exception>
\r
843 /// <param name="key">The key</param>
\r
844 /// <returns>The entry</returns>
\r
846 public KeyValuePair<K, V> Successor(K key)
\r
848 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
850 return sortedpairs.Successor(p);
\r
855 /// Get the entry in the dictionary whose key is the
\r
856 /// weak successor of a specified key.
\r
858 /// <exception cref="NoSuchItemException"></exception>
\r
859 /// <param name="key">The key</param>
\r
860 /// <returns>The entry</returns>
\r
862 public KeyValuePair<K, V> WeakSuccessor(K key)
\r
864 return sortedpairs.WeakSuccessor(new KeyValuePair<K, V>(key));
\r
869 #region ISortedDictionary<K,V> Members
\r
874 /// <returns></returns>
\r
875 public KeyValuePair<K, V> FindMin()
\r
877 return sortedpairs.FindMin();
\r
883 /// <returns></returns>
\r
884 public KeyValuePair<K, V> DeleteMin()
\r
886 return sortedpairs.DeleteMin();
\r
892 /// <returns></returns>
\r
893 public KeyValuePair<K, V> FindMax()
\r
895 return sortedpairs.FindMax();
\r
901 /// <returns></returns>
\r
902 public KeyValuePair<K, V> DeleteMax()
\r
904 return sortedpairs.DeleteMax();
\r
910 /// <param name="cutter"></param>
\r
911 /// <param name="lowEntry"></param>
\r
912 /// <param name="lowIsValid"></param>
\r
913 /// <param name="highEntry"></param>
\r
914 /// <param name="highIsValid"></param>
\r
915 /// <returns></returns>
\r
916 public bool Cut(IComparable<K> cutter, out KeyValuePair<K, V> lowEntry, out bool lowIsValid, out KeyValuePair<K, V> highEntry, out bool highIsValid)
\r
918 return sortedpairs.Cut(new KeyValuePairComparable(cutter), out lowEntry, out lowIsValid, out highEntry, out highIsValid);
\r
924 /// <param name="bot"></param>
\r
925 /// <returns></returns>
\r
926 public IDirectedEnumerable<KeyValuePair<K, V>> RangeFrom(K bot)
\r
928 return sortedpairs.RangeFrom(new KeyValuePair<K, V>(bot));
\r
934 /// <param name="bot"></param>
\r
935 /// <param name="top"></param>
\r
936 /// <returns></returns>
\r
937 public IDirectedEnumerable<KeyValuePair<K, V>> RangeFromTo(K bot, K top)
\r
939 return sortedpairs.RangeFromTo(new KeyValuePair<K, V>(bot), new KeyValuePair<K, V>(top));
\r
945 /// <param name="top"></param>
\r
946 /// <returns></returns>
\r
947 public IDirectedEnumerable<KeyValuePair<K, V>> RangeTo(K top)
\r
949 return sortedpairs.RangeTo(new KeyValuePair<K, V>(top));
\r
955 /// <returns></returns>
\r
956 public IDirectedCollectionValue<KeyValuePair<K, V>> RangeAll()
\r
958 return sortedpairs.RangeAll();
\r
964 /// <param name="items"></param>
\r
965 public void AddSorted(SCG.IEnumerable<KeyValuePair<K, V>> items)
\r
967 sortedpairs.AddSorted(items);
\r
973 /// <param name="lowKey"></param>
\r
974 public void RemoveRangeFrom(K lowKey)
\r
976 sortedpairs.RemoveRangeFrom(new KeyValuePair<K, V>(lowKey));
\r
982 /// <param name="lowKey"></param>
\r
983 /// <param name="highKey"></param>
\r
984 public void RemoveRangeFromTo(K lowKey, K highKey)
\r
986 sortedpairs.RemoveRangeFromTo(new KeyValuePair<K, V>(lowKey), new KeyValuePair<K, V>(highKey));
\r
992 /// <param name="highKey"></param>
\r
993 public void RemoveRangeTo(K highKey)
\r
995 sortedpairs.RemoveRangeTo(new KeyValuePair<K, V>(highKey));
\r
1000 class KeyValuePairComparable : IComparable<KeyValuePair<K, V>>
\r
1002 IComparable<K> cutter;
\r
1004 internal KeyValuePairComparable(IComparable<K> cutter) { this.cutter = cutter; }
\r
1006 public int CompareTo(KeyValuePair<K, V> other) { return cutter.CompareTo(other.Key); }
\r
1008 public bool Equals(KeyValuePair<K, V> other) { return cutter.Equals(other.Key); }
\r
1011 class ProjectedDirectedEnumerable : MappedDirectedEnumerable<KeyValuePair<K, V>, K>
\r
1013 public ProjectedDirectedEnumerable(IDirectedEnumerable<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }
\r
1015 public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }
\r
1019 class ProjectedDirectedCollectionValue : MappedDirectedCollectionValue<KeyValuePair<K, V>, K>
\r
1021 public ProjectedDirectedCollectionValue(IDirectedCollectionValue<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }
\r
1023 public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }
\r
1027 class SortedKeysCollection : SequencedBase<K>, ISorted<K>
\r
1029 ISortedDictionary<K, V> sorteddict;
\r
1030 //TODO: eliminate this. Only problem is the Find method because we lack method on dictionary that also
\r
1031 // returns the actual key.
\r
1032 ISorted<KeyValuePair<K, V>> sortedpairs;
\r
1033 SCG.IComparer<K> comparer;
\r
1035 internal SortedKeysCollection(ISortedDictionary<K, V> sorteddict, ISorted<KeyValuePair<K, V>> sortedpairs, SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> itemequalityComparer)
\r
1036 :base(itemequalityComparer)
\r
1038 this.sorteddict = sorteddict;
\r
1039 this.sortedpairs = sortedpairs;
\r
1040 this.comparer = comparer;
\r
1043 public override K Choose() { return sorteddict.Choose().Key; }
\r
1045 public override SCG.IEnumerator<K> GetEnumerator()
\r
1047 foreach (KeyValuePair<K, V> p in sorteddict)
\r
1048 yield return p.Key;
\r
1051 public override bool IsEmpty { get { return sorteddict.IsEmpty; } }
\r
1053 public override int Count { [Tested]get { return sorteddict.Count; } }
\r
1055 public override Speed CountSpeed { get { return sorteddict.CountSpeed; } }
\r
1057 #region ISorted<K> Members
\r
1059 public K FindMin() { return sorteddict.FindMin().Key; }
\r
1061 public K DeleteMin() { throw new ReadOnlyCollectionException(); }
\r
1063 public K FindMax() { return sorteddict.FindMax().Key; }
\r
1065 public K DeleteMax() { throw new ReadOnlyCollectionException(); }
\r
1067 public SCG.IComparer<K> Comparer { get { return comparer; } }
\r
1069 public K Predecessor(K item) { return sorteddict.Predecessor(item).Key; }
\r
1071 public K Successor(K item) { return sorteddict.Successor(item).Key; }
\r
1073 public K WeakPredecessor(K item) { return sorteddict.WeakPredecessor(item).Key; }
\r
1075 public K WeakSuccessor(K item) { return sorteddict.WeakSuccessor(item).Key; }
\r
1077 public bool Cut(IComparable<K> c, out K low, out bool lowIsValid, out K high, out bool highIsValid)
\r
1079 KeyValuePair<K, V> lowpair, highpair;
\r
1080 bool retval = sorteddict.Cut(c, out lowpair, out lowIsValid, out highpair, out highIsValid);
\r
1081 low = lowpair.Key;
\r
1082 high = highpair.Key;
\r
1086 public IDirectedEnumerable<K> RangeFrom(K bot)
\r
1088 return new ProjectedDirectedEnumerable(sorteddict.RangeFrom(bot));
\r
1091 public IDirectedEnumerable<K> RangeFromTo(K bot, K top)
\r
1093 return new ProjectedDirectedEnumerable(sorteddict.RangeFromTo(bot, top));
\r
1096 public IDirectedEnumerable<K> RangeTo(K top)
\r
1098 return new ProjectedDirectedEnumerable(sorteddict.RangeTo(top));
\r
1101 public IDirectedCollectionValue<K> RangeAll()
\r
1103 return new ProjectedDirectedCollectionValue(sorteddict.RangeAll());
\r
1106 public void AddSorted<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
\r
1108 public void RemoveRangeFrom(K low) { throw new ReadOnlyCollectionException(); }
\r
1110 public void RemoveRangeFromTo(K low, K hi) { throw new ReadOnlyCollectionException(); }
\r
1112 public void RemoveRangeTo(K hi) { throw new ReadOnlyCollectionException(); }
\r
1115 #region ICollection<K> Members
\r
1116 public Speed ContainsSpeed { get { return sorteddict.ContainsSpeed; } }
\r
1118 public bool Contains(K key) { return sorteddict.Contains(key); ; }
\r
1120 public int ContainsCount(K item) { return sorteddict.Contains(item) ? 1 : 0; }
\r
1125 /// <returns></returns>
\r
1126 public virtual ICollectionValue<K> UniqueItems()
\r
1134 /// <returns></returns>
\r
1135 public virtual ICollectionValue<KeyValuePair<K, int>> ItemMultiplicities()
\r
1137 return new MultiplicityOne<K>(this);
\r
1141 public bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : K
\r
1144 foreach (K item in items)
\r
1145 if (!sorteddict.Contains(item))
\r
1150 public bool Find(ref K item)
\r
1152 KeyValuePair<K, V> p = new KeyValuePair<K, V>(item);
\r
1153 bool retval = sortedpairs.Find(ref p);
\r
1158 public bool FindOrAdd(ref K item) { throw new ReadOnlyCollectionException(); }
\r
1160 public bool Update(K item) { throw new ReadOnlyCollectionException(); }
\r
1162 public bool Update(K item, out K olditem) { throw new ReadOnlyCollectionException(); }
\r
1164 public bool UpdateOrAdd(K item) { throw new ReadOnlyCollectionException(); }
\r
1166 public bool UpdateOrAdd(K item, out K olditem) { throw new ReadOnlyCollectionException(); }
\r
1168 public bool Remove(K item) { throw new ReadOnlyCollectionException(); }
\r
1170 public bool Remove(K item, out K removeditem) { throw new ReadOnlyCollectionException(); }
\r
1172 public void RemoveAllCopies(K item) { throw new ReadOnlyCollectionException(); }
\r
1174 public void RemoveAll<U> (SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
\r
1176 public void Clear() { throw new ReadOnlyCollectionException(); }
\r
1178 public void RetainAll<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
\r
1182 #region IExtensible<K> Members
\r
1183 public override bool IsReadOnly { get { return true; } }
\r
1185 public bool AllowsDuplicates { get { return false; } }
\r
1187 public bool DuplicatesByCounting { get { return true; } }
\r
1189 public bool Add(K item) { throw new ReadOnlyCollectionException(); }
\r
1191 public void AddAll(System.Collections.Generic.IEnumerable<K> items) { throw new ReadOnlyCollectionException(); }
\r
1193 public void AddAll<U>(System.Collections.Generic.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
\r
1195 public bool Check() { return sorteddict.Check(); }
\r
1199 #region IDirectedCollectionValue<K> Members
\r
1201 public override IDirectedCollectionValue<K> Backwards()
\r
1203 return RangeAll().Backwards();
\r
1208 #region IDirectedEnumerable<K> Members
\r
1210 IDirectedEnumerable<K> IDirectedEnumerable<K>.Backwards() { return Backwards(); }
\r
1213 #region ICloneable Members
\r
1217 /// Make a shallow copy of this SortedKeysCollection.
\r
1219 /// <returns></returns>
\r
1220 public virtual object Clone()
\r
1223 SortedArrayDictionary<K, V> dictclone = new SortedArrayDictionary<K, V>(sortedpairs.Count, comparer, EqualityComparer);
\r
1224 SortedArray<KeyValuePair<K, V>> sortedpairsclone = (SortedArray<KeyValuePair<K, V>>)(dictclone.sortedpairs);
\r
1225 foreach (K key in sorteddict.Keys)
\r
1227 sortedpairsclone.Add(new KeyValuePair<K, V>(key, default(V)));
\r
1229 return new SortedKeysCollection(dictclone, sortedpairsclone, comparer, EqualityComparer);
\r
1239 /// <param name="stringbuilder"></param>
\r
1240 /// <param name="rest"></param>
\r
1241 /// <param name="formatProvider"></param>
\r
1242 /// <returns></returns>
\r
1243 public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
\r
1245 return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);
\r
1250 class SortedArrayDictionary<K, V> : SortedDictionaryBase<K, V>, IDictionary<K, V>, ISortedDictionary<K, V>
\r
1252 #region Constructors
\r
1254 public SortedArrayDictionary() : this(Comparer<K>.Default, EqualityComparer<K>.Default) { }
\r
1257 /// Create a red-black tree dictionary using an external comparer for keys.
\r
1259 /// <param name="comparer">The external comparer</param>
\r
1260 public SortedArrayDictionary(SCG.IComparer<K> comparer) : this(comparer, new ComparerZeroHashCodeEqualityComparer<K>(comparer)) { }
\r
1265 /// <param name="comparer"></param>
\r
1266 /// <param name="equalityComparer"></param>
\r
1267 public SortedArrayDictionary(SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> equalityComparer) : base(comparer,equalityComparer)
\r
1269 pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(new KeyValuePairComparer<K, V>(comparer));
\r
1275 /// <param name="comparer"></param>
\r
1276 /// <param name="equalityComparer"></param>
\r
1277 /// <param name="capacity"></param>
\r
1278 public SortedArrayDictionary(int capacity, SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> equalityComparer) : base(comparer,equalityComparer)
\r
1280 pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(capacity, new KeyValuePairComparer<K, V>(comparer));
\r
1287 /// <returns></returns>
\r
1288 public override object Clone()
\r
1290 SortedArrayDictionary<K, V> clone = new SortedArrayDictionary<K, V>(Comparer, EqualityComparer);
\r
1291 clone.sortedpairs.AddSorted(sortedpairs);
\r