2 Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
\r
3 Permission is hereby granted, free of charge, to any person obtaining a copy
\r
4 of this software and associated documentation files (the "Software"), to deal
\r
5 in the Software without restriction, including without limitation the rights
\r
6 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
\r
7 copies of the Software, and to permit persons to whom the Software is
\r
8 furnished to do so, subject to the following conditions:
\r
10 The above copyright notice and this permission notice shall be included in
\r
11 all copies or substantial portions of the Software.
\r
13 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
\r
14 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
\r
15 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
\r
16 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
\r
17 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
\r
18 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
\r
23 using System.Diagnostics;
\r
24 using SCG = System.Collections.Generic;
\r
28 /// An entry in a dictionary from K to V.
\r
31 public struct KeyValuePair<K, V> : IEquatable<KeyValuePair<K, V>>, IShowable
\r
34 /// The key field of the entry
\r
39 /// The value field of the entry
\r
44 /// Create an entry with specified key and value
\r
46 /// <param name="key">The key</param>
\r
47 /// <param name="value">The value</param>
\r
48 public KeyValuePair(K key, V value) { Key = key; Value = value; }
\r
52 /// Create an entry with a specified key. The value will be the default value of type <code>V</code>.
\r
54 /// <param name="key">The key</param>
\r
55 public KeyValuePair(K key) { Key = key; Value = default(V); }
\r
59 /// Pretty print an entry
\r
61 /// <returns>(key, value)</returns>
\r
63 public override string ToString() { return "(" + Key + ", " + Value + ")"; }
\r
67 /// Check equality of entries.
\r
69 /// <param name="obj">The other object</param>
\r
70 /// <returns>True if obj is an entry of the same type and has the same key and value</returns>
\r
72 public override bool Equals(object obj)
\r
74 if (!(obj is KeyValuePair<K, V>))
\r
76 KeyValuePair<K, V> other = (KeyValuePair<K, V>)obj;
\r
77 return Equals(other);
\r
82 /// Get the hash code of the pair.
\r
84 /// <returns>The hash code</returns>
\r
86 public override int GetHashCode() { return EqualityComparer<K>.Default.GetHashCode(Key) + 13984681 * EqualityComparer<V>.Default.GetHashCode(Value); }
\r
91 /// <param name="other"></param>
\r
92 /// <returns></returns>
\r
93 public bool Equals(KeyValuePair<K, V> other)
\r
95 return EqualityComparer<K>.Default.Equals(Key, other.Key) && EqualityComparer<V>.Default.Equals(Value, other.Value);
\r
101 /// <param name="pair1"></param>
\r
102 /// <param name="pair2"></param>
\r
103 /// <returns></returns>
\r
104 public static bool operator ==(KeyValuePair<K, V> pair1, KeyValuePair<K, V> pair2) { return pair1.Equals(pair2); }
\r
109 /// <param name="pair1"></param>
\r
110 /// <param name="pair2"></param>
\r
111 /// <returns></returns>
\r
112 public static bool operator !=(KeyValuePair<K, V> pair1, KeyValuePair<K, V> pair2) { return !pair1.Equals(pair2); }
\r
114 #region IShowable Members
\r
119 /// <param name="stringbuilder"></param>
\r
120 /// <param name="formatProvider"></param>
\r
121 /// <param name="rest"></param>
\r
122 /// <returns></returns>
\r
123 public bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
\r
127 if (!Showing.Show(Key, stringbuilder, ref rest, formatProvider))
\r
129 stringbuilder.Append(" => ");
\r
131 if (!Showing.Show(Value, stringbuilder, ref rest, formatProvider))
\r
137 #region IFormattable Members
\r
142 /// <param name="format"></param>
\r
143 /// <param name="formatProvider"></param>
\r
144 /// <returns></returns>
\r
145 public string ToString(string format, IFormatProvider formatProvider)
\r
147 return Showing.ShowString(this, format, formatProvider);
\r
156 /// Default comparer for dictionary entries in a sorted dictionary.
\r
157 /// Entry comparisons only look at keys and uses an externally defined comparer for that.
\r
160 public class KeyValuePairComparer<K, V> : SCG.IComparer<KeyValuePair<K, V>>
\r
162 SCG.IComparer<K> comparer;
\r
166 /// Create an entry comparer for a item comparer of the keys
\r
168 /// <param name="comparer">Comparer of keys</param>
\r
169 public KeyValuePairComparer(SCG.IComparer<K> comparer)
\r
171 if (comparer == null)
\r
172 throw new NullReferenceException();
\r
173 this.comparer = comparer;
\r
178 /// Compare two entries
\r
180 /// <param name="entry1">First entry</param>
\r
181 /// <param name="entry2">Second entry</param>
\r
182 /// <returns>The result of comparing the keys</returns>
\r
184 public int Compare(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)
\r
185 { return comparer.Compare(entry1.Key, entry2.Key); }
\r
191 /// Default equalityComparer for dictionary entries.
\r
192 /// Operations only look at keys and uses an externaly defined equalityComparer for that.
\r
195 public sealed class KeyValuePairEqualityComparer<K, V> : SCG.IEqualityComparer<KeyValuePair<K, V>>
\r
197 SCG.IEqualityComparer<K> keyequalityComparer;
\r
201 /// Create an entry equalityComparer using the default equalityComparer for keys
\r
203 public KeyValuePairEqualityComparer() { keyequalityComparer = EqualityComparer<K>.Default; }
\r
207 /// Create an entry equalityComparer from a specified item equalityComparer for the keys
\r
209 /// <param name="keyequalityComparer">The key equalityComparer</param>
\r
210 public KeyValuePairEqualityComparer(SCG.IEqualityComparer<K> keyequalityComparer)
\r
212 if (keyequalityComparer == null)
\r
213 throw new NullReferenceException("Key equality comparer cannot be null");
\r
214 this.keyequalityComparer = keyequalityComparer;
\r
219 /// Get the hash code of the entry
\r
221 /// <param name="entry">The entry</param>
\r
222 /// <returns>The hash code of the key</returns>
\r
224 public int GetHashCode(KeyValuePair<K, V> entry) { return keyequalityComparer.GetHashCode(entry.Key); }
\r
228 /// Test two entries for equality
\r
230 /// <param name="entry1">First entry</param>
\r
231 /// <param name="entry2">Second entry</param>
\r
232 /// <returns>True if keys are equal</returns>
\r
234 public bool Equals(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)
\r
235 { return keyequalityComparer.Equals(entry1.Key, entry2.Key); }
\r
241 /// A base class for implementing a dictionary based on a set collection implementation.
\r
242 /// <i>See the source code for <see cref="T:C5.HashDictionary`2"/> for an example</i>
\r
246 public abstract class DictionaryBase<K, V> : CollectionValueBase<KeyValuePair<K, V>>, IDictionary<K, V>
\r
249 /// The set collection of entries underlying this dictionary implementation
\r
251 protected ICollection<KeyValuePair<K, V>> pairs;
\r
253 SCG.IEqualityComparer<K> keyequalityComparer;
\r
256 ProxyEventBlock<KeyValuePair<K, V>> eventBlock;
\r
259 /// The change event. Will be raised for every change operation on the collection.
\r
261 public override event CollectionChangedHandler<KeyValuePair<K, V>> CollectionChanged
\r
263 add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionChanged += value; }
\r
264 remove { if (eventBlock != null) eventBlock.CollectionChanged -= value; }
\r
268 /// The change event. Will be raised for every change operation on the collection.
\r
270 public override event CollectionClearedHandler<KeyValuePair<K, V>> CollectionCleared
\r
272 add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionCleared += value; }
\r
273 remove { if (eventBlock != null) eventBlock.CollectionCleared -= value; }
\r
277 /// The item added event. Will be raised for every individual addition to the collection.
\r
279 public override event ItemsAddedHandler<KeyValuePair<K, V>> ItemsAdded
\r
281 add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsAdded += value; }
\r
282 remove { if (eventBlock != null) eventBlock.ItemsAdded -= value; }
\r
286 /// The item added event. Will be raised for every individual removal from the collection.
\r
288 public override event ItemsRemovedHandler<KeyValuePair<K, V>> ItemsRemoved
\r
290 add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsRemoved += value; }
\r
291 remove { if (eventBlock != null) eventBlock.ItemsRemoved -= value; }
\r
297 public override EventTypeEnum ListenableEvents
\r
301 return EventTypeEnum.Basic;
\r
308 public override EventTypeEnum ActiveEvents
\r
312 return pairs.ActiveEvents;
\r
321 /// <param name="keyequalityComparer"></param>
\r
322 public DictionaryBase(SCG.IEqualityComparer<K> keyequalityComparer) {
\r
323 if (keyequalityComparer == null)
\r
324 throw new NullReferenceException("Key equality comparer cannot be null");
\r
325 this.keyequalityComparer = keyequalityComparer; }
\r
327 #region IDictionary<K,V> Members
\r
332 /// <value></value>
\r
333 public virtual SCG.IEqualityComparer<K> EqualityComparer { get { return keyequalityComparer; } }
\r
337 /// Add a new (key, value) pair (a mapping) to the dictionary.
\r
339 /// <exception cref="DuplicateNotAllowedException"> if there already is an entry with the same key. </exception>
\r
340 /// <param name="key">Key to add</param>
\r
341 /// <param name="value">Value to add</param>
\r
343 public virtual void Add(K key, V value)
\r
345 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
\r
348 throw new DuplicateNotAllowedException("Key being added: '" + key + "'");
\r
352 /// Add the entries from a collection of <see cref="T:C5.KeyValuePair`2"/> pairs to this dictionary.
\r
353 /// <para><b>TODO: add restrictions L:K and W:V when the .Net SDK allows it </b></para>
\r
355 /// <exception cref="DuplicateNotAllowedException">
\r
356 /// If the input contains duplicate keys or a key already present in this dictionary.</exception>
\r
357 /// <param name="entries"></param>
\r
358 public virtual void AddAll<L,W>(SCG.IEnumerable<KeyValuePair<L, W>> entries)
\r
362 foreach (KeyValuePair<L, W> pair in entries)
\r
364 KeyValuePair<K, V> p = new KeyValuePair<K, V>(pair.Key, pair.Value);
\r
366 throw new DuplicateNotAllowedException("Key being added: '" + pair.Key + "'");
\r
371 /// Remove an entry with a given key from the dictionary
\r
373 /// <param name="key">The key of the entry to remove</param>
\r
374 /// <returns>True if an entry was found (and removed)</returns>
\r
376 public virtual bool Remove(K key)
\r
378 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
380 return pairs.Remove(p);
\r
385 /// Remove an entry with a given key from the dictionary and report its value.
\r
387 /// <param name="key">The key of the entry to remove</param>
\r
388 /// <param name="value">On exit, the value of the removed entry</param>
\r
389 /// <returns>True if an entry was found (and removed)</returns>
\r
391 public virtual bool Remove(K key, out V value)
\r
393 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
395 if (pairs.Remove(p, out p))
\r
402 value = default(V);
\r
409 /// Remove all entries from the dictionary
\r
412 public virtual void Clear() { pairs.Clear(); }
\r
417 /// <value></value>
\r
418 public virtual Speed ContainsSpeed { get { return pairs.ContainsSpeed; } }
\r
421 /// Check if there is an entry with a specified key
\r
423 /// <param name="key">The key to look for</param>
\r
424 /// <returns>True if key was found</returns>
\r
426 public virtual bool Contains(K key)
\r
428 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
430 return pairs.Contains(p);
\r
433 class LiftedEnumerable<H> : SCG.IEnumerable<KeyValuePair<K, V>> where H : K
\r
435 SCG.IEnumerable<H> keys;
\r
436 public LiftedEnumerable(SCG.IEnumerable<H> keys) { this.keys = keys; }
\r
437 public SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator() { foreach (H key in keys) yield return new KeyValuePair<K, V>(key); }
\r
439 #region IEnumerable Members
\r
441 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
\r
443 throw new Exception("The method or operation is not implemented.");
\r
452 /// <param name="keys"></param>
\r
453 /// <returns></returns>
\r
454 public virtual bool ContainsAll<H>(SCG.IEnumerable<H> keys) where H : K
\r
456 return pairs.ContainsAll(new LiftedEnumerable<H>(keys));
\r
460 /// Check if there is an entry with a specified key and report the corresponding
\r
461 /// value if found. This can be seen as a safe form of "val = this[key]".
\r
463 /// <param name="key">The key to look for</param>
\r
464 /// <param name="value">On exit, the value of the entry</param>
\r
465 /// <returns>True if key was found</returns>
\r
467 public virtual bool Find(K key, out V value)
\r
469 return Find(ref key, out value);
\r
472 /// Check if there is an entry with a specified key and report the corresponding
\r
473 /// value if found. This can be seen as a safe form of "val = this[key]".
\r
475 /// <param name="key">The key to look for</param>
\r
476 /// <param name="value">On exit, the value of the entry</param>
\r
477 /// <returns>True if key was found</returns>
\r
478 public virtual bool Find(ref K key, out V value)
\r
480 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
482 if (pairs.Find(ref p))
\r
490 value = default(V);
\r
497 /// Look for a specific key in the dictionary and if found replace the value with a new one.
\r
498 /// This can be seen as a non-adding version of "this[key] = val".
\r
500 /// <param name="key">The key to look for</param>
\r
501 /// <param name="value">The new value</param>
\r
502 /// <returns>True if key was found</returns>
\r
504 public virtual bool Update(K key, V value)
\r
506 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
\r
508 return pairs.Update(p);
\r
515 /// <param name="key"></param>
\r
516 /// <param name="value"></param>
\r
517 /// <param name="oldvalue"></param>
\r
518 /// <returns></returns>
\r
519 public virtual bool Update(K key, V value, out V oldvalue)
\r
521 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
\r
523 bool retval = pairs.Update(p, out p);
\r
524 oldvalue = p.Value;
\r
530 /// Look for a specific key in the dictionary. If found, report the corresponding value,
\r
531 /// else add an entry with the key and the supplied value.
\r
533 /// <param name="key">On entry the key to look for</param>
\r
534 /// <param name="value">On entry the value to add if the key is not found.
\r
535 /// On exit the value found if any.</param>
\r
536 /// <returns>True if key was found</returns>
\r
538 public virtual bool FindOrAdd(K key, ref V value)
\r
540 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
\r
542 if (!pairs.FindOrAdd(ref p))
\r
554 /// Update value in dictionary corresponding to key if found, else add new entry.
\r
555 /// More general than "this[key] = val;" by reporting if key was found.
\r
557 /// <param name="key">The key to look for</param>
\r
558 /// <param name="value">The value to add or replace with.</param>
\r
559 /// <returns>True if entry was updated.</returns>
\r
561 public virtual bool UpdateOrAdd(K key, V value)
\r
563 return pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value));
\r
568 /// Update value in dictionary corresponding to key if found, else add new entry.
\r
569 /// More general than "this[key] = val;" by reporting if key was found and the old value if any.
\r
571 /// <param name="key"></param>
\r
572 /// <param name="value"></param>
\r
573 /// <param name="oldvalue"></param>
\r
574 /// <returns></returns>
\r
575 public virtual bool UpdateOrAdd(K key, V value, out V oldvalue)
\r
577 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
\r
578 bool retval = pairs.UpdateOrAdd(p, out p);
\r
579 oldvalue = p.Value;
\r
585 #region Keys,Values support classes
\r
587 internal class ValuesCollection : CollectionValueBase<V>, ICollectionValue<V>
\r
589 ICollection<KeyValuePair<K, V>> pairs;
\r
592 internal ValuesCollection(ICollection<KeyValuePair<K, V>> pairs)
\r
593 { this.pairs = pairs; }
\r
596 public override V Choose() { return pairs.Choose().Value; }
\r
599 public override SCG.IEnumerator<V> GetEnumerator()
\r
601 //Updatecheck is performed by the pairs enumerator
\r
602 foreach (KeyValuePair<K, V> p in pairs)
\r
603 yield return p.Value;
\r
606 public override bool IsEmpty { get { return pairs.IsEmpty; } }
\r
609 public override int Count { [Tested]get { return pairs.Count; } }
\r
611 public override Speed CountSpeed { get { return Speed.Constant; } }
\r
616 internal class KeysCollection : CollectionValueBase<K>, ICollectionValue<K>
\r
618 ICollection<KeyValuePair<K, V>> pairs;
\r
621 internal KeysCollection(ICollection<KeyValuePair<K, V>> pairs)
\r
622 { this.pairs = pairs; }
\r
624 public override K Choose() { return pairs.Choose().Key; }
\r
627 public override SCG.IEnumerator<K> GetEnumerator()
\r
629 foreach (KeyValuePair<K, V> p in pairs)
\r
630 yield return p.Key;
\r
633 public override bool IsEmpty { get { return pairs.IsEmpty; } }
\r
636 public override int Count { [Tested]get { return pairs.Count; } }
\r
638 public override Speed CountSpeed { get { return pairs.CountSpeed; } }
\r
645 /// <value>A collection containg the all the keys of the dictionary</value>
\r
647 public virtual ICollectionValue<K> Keys { [Tested]get { return new KeysCollection(pairs); } }
\r
653 /// <value>A collection containing all the values of the dictionary</value>
\r
655 public virtual ICollectionValue<V> Values { [Tested]get { return new ValuesCollection(pairs); } }
\r
660 public virtual Fun<K, V> Fun { get { return delegate(K k) { return this[k]; }; } }
\r
663 /// Indexer by key for dictionary.
\r
664 /// <para>The get method will throw an exception if no entry is found. </para>
\r
665 /// <para>The set method behaves like <see cref="M:C5.DictionaryBase`2.UpdateOrAdd(`0,`1)"/>.</para>
\r
667 /// <exception cref="NoSuchItemException"> On get if no entry is found. </exception>
\r
668 /// <value>The value corresponding to the key</value>
\r
670 public virtual V this[K key]
\r
675 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
677 if (pairs.Find(ref p))
\r
680 throw new NoSuchItemException("Key '" + key.ToString() + "' not present in Dictionary");
\r
684 { pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value)); }
\r
691 /// <value>True if dictionary is read only</value>
\r
693 public virtual bool IsReadOnly { [Tested]get { return pairs.IsReadOnly; } }
\r
697 /// Check the integrity of the internal data structures of this dictionary.
\r
699 /// <returns>True if check does not fail.</returns>
\r
701 public virtual bool Check() { return pairs.Check(); }
\r
705 #region ICollectionValue<KeyValuePair<K,V>> Members
\r
710 /// <value>True if this collection is empty.</value>
\r
711 public override bool IsEmpty { get { return pairs.IsEmpty; } }
\r
717 /// <value>The number of entrues in the dictionary</value>
\r
719 public override int Count { [Tested]get { return pairs.Count; } }
\r
724 /// <value>The number of entrues in the dictionary</value>
\r
726 public override Speed CountSpeed { [Tested]get { return pairs.CountSpeed; } }
\r
729 /// Choose some entry in this Dictionary.
\r
731 /// <exception cref="NoSuchItemException">if collection is empty.</exception>
\r
732 /// <returns></returns>
\r
733 public override KeyValuePair<K, V> Choose() { return pairs.Choose(); }
\r
736 /// Create an enumerator for the collection of entries of the dictionary
\r
738 /// <returns>The enumerator</returns>
\r
740 public override SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator()
\r
742 return pairs.GetEnumerator(); ;
\r
750 /// <param name="stringbuilder"></param>
\r
751 /// <param name="rest"></param>
\r
752 /// <param name="formatProvider"></param>
\r
753 /// <returns></returns>
\r
754 public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
\r
756 return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);
\r
762 /// <returns></returns>
\r
763 public abstract object Clone();
\r
768 /// A base class for implementing a sorted dictionary based on a sorted set collection implementation.
\r
769 /// <i>See the source code for <see cref="T:C5.TreeDictionary`2"/> for an example</i>
\r
772 public abstract class SortedDictionaryBase<K, V> : DictionaryBase<K, V>, ISortedDictionary<K, V>
\r
779 protected ISorted<KeyValuePair<K, V>> sortedpairs;
\r
780 SCG.IComparer<K> keycomparer;
\r
785 /// <param name="keycomparer"></param>
\r
786 /// <param name="keyequalityComparer"></param>
\r
787 public SortedDictionaryBase(SCG.IComparer<K> keycomparer, SCG.IEqualityComparer<K> keyequalityComparer) : base(keyequalityComparer) { this.keycomparer = keycomparer; }
\r
791 #region ISortedDictionary<K,V> Members
\r
794 /// The key comparer used by this dictionary.
\r
796 /// <value></value>
\r
797 public SCG.IComparer<K> Comparer { get { return keycomparer; } }
\r
802 /// <value></value>
\r
803 public new ISorted<K> Keys { get { return new SortedKeysCollection(this, sortedpairs, keycomparer, EqualityComparer); } }
\r
806 /// Get the entry in the dictionary whose key is the
\r
807 /// predecessor of a specified key.
\r
809 /// <exception cref="NoSuchItemException"></exception>
\r
810 /// <param name="key">The key</param>
\r
811 /// <returns>The entry</returns>
\r
813 public KeyValuePair<K, V> Predecessor(K key)
\r
815 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
817 return sortedpairs.Predecessor(p);
\r
822 /// Get the entry in the dictionary whose key is the
\r
823 /// weak predecessor of a specified key.
\r
825 /// <exception cref="NoSuchItemException"></exception>
\r
826 /// <param name="key">The key</param>
\r
827 /// <returns>The entry</returns>
\r
829 public KeyValuePair<K, V> WeakPredecessor(K key)
\r
831 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
833 return sortedpairs.WeakPredecessor(p);
\r
838 /// Get the entry in the dictionary whose key is the
\r
839 /// successor of a specified key.
\r
841 /// <exception cref="NoSuchItemException"></exception>
\r
842 /// <param name="key">The key</param>
\r
843 /// <returns>The entry</returns>
\r
845 public KeyValuePair<K, V> Successor(K key)
\r
847 KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
\r
849 return sortedpairs.Successor(p);
\r
854 /// Get the entry in the dictionary whose key is the
\r
855 /// weak successor of a specified key.
\r
857 /// <exception cref="NoSuchItemException"></exception>
\r
858 /// <param name="key">The key</param>
\r
859 /// <returns>The entry</returns>
\r
861 public KeyValuePair<K, V> WeakSuccessor(K key)
\r
863 return sortedpairs.WeakSuccessor(new KeyValuePair<K, V>(key));
\r
868 #region ISortedDictionary<K,V> Members
\r
873 /// <returns></returns>
\r
874 public KeyValuePair<K, V> FindMin()
\r
876 return sortedpairs.FindMin();
\r
882 /// <returns></returns>
\r
883 public KeyValuePair<K, V> DeleteMin()
\r
885 return sortedpairs.DeleteMin();
\r
891 /// <returns></returns>
\r
892 public KeyValuePair<K, V> FindMax()
\r
894 return sortedpairs.FindMax();
\r
900 /// <returns></returns>
\r
901 public KeyValuePair<K, V> DeleteMax()
\r
903 return sortedpairs.DeleteMax();
\r
909 /// <param name="cutter"></param>
\r
910 /// <param name="lowEntry"></param>
\r
911 /// <param name="lowIsValid"></param>
\r
912 /// <param name="highEntry"></param>
\r
913 /// <param name="highIsValid"></param>
\r
914 /// <returns></returns>
\r
915 public bool Cut(IComparable<K> cutter, out KeyValuePair<K, V> lowEntry, out bool lowIsValid, out KeyValuePair<K, V> highEntry, out bool highIsValid)
\r
917 return sortedpairs.Cut(new KeyValuePairComparable(cutter), out lowEntry, out lowIsValid, out highEntry, out highIsValid);
\r
923 /// <param name="bot"></param>
\r
924 /// <returns></returns>
\r
925 public IDirectedEnumerable<KeyValuePair<K, V>> RangeFrom(K bot)
\r
927 return sortedpairs.RangeFrom(new KeyValuePair<K, V>(bot));
\r
933 /// <param name="bot"></param>
\r
934 /// <param name="top"></param>
\r
935 /// <returns></returns>
\r
936 public IDirectedEnumerable<KeyValuePair<K, V>> RangeFromTo(K bot, K top)
\r
938 return sortedpairs.RangeFromTo(new KeyValuePair<K, V>(bot), new KeyValuePair<K, V>(top));
\r
944 /// <param name="top"></param>
\r
945 /// <returns></returns>
\r
946 public IDirectedEnumerable<KeyValuePair<K, V>> RangeTo(K top)
\r
948 return sortedpairs.RangeTo(new KeyValuePair<K, V>(top));
\r
954 /// <returns></returns>
\r
955 public IDirectedCollectionValue<KeyValuePair<K, V>> RangeAll()
\r
957 return sortedpairs.RangeAll();
\r
963 /// <param name="items"></param>
\r
964 public void AddSorted(SCG.IEnumerable<KeyValuePair<K, V>> items)
\r
966 sortedpairs.AddSorted(items);
\r
972 /// <param name="lowKey"></param>
\r
973 public void RemoveRangeFrom(K lowKey)
\r
975 sortedpairs.RemoveRangeFrom(new KeyValuePair<K, V>(lowKey));
\r
981 /// <param name="lowKey"></param>
\r
982 /// <param name="highKey"></param>
\r
983 public void RemoveRangeFromTo(K lowKey, K highKey)
\r
985 sortedpairs.RemoveRangeFromTo(new KeyValuePair<K, V>(lowKey), new KeyValuePair<K, V>(highKey));
\r
991 /// <param name="highKey"></param>
\r
992 public void RemoveRangeTo(K highKey)
\r
994 sortedpairs.RemoveRangeTo(new KeyValuePair<K, V>(highKey));
\r
999 class KeyValuePairComparable : IComparable<KeyValuePair<K, V>>
\r
1001 IComparable<K> cutter;
\r
1003 internal KeyValuePairComparable(IComparable<K> cutter) { this.cutter = cutter; }
\r
1005 public int CompareTo(KeyValuePair<K, V> other) { return cutter.CompareTo(other.Key); }
\r
1007 public bool Equals(KeyValuePair<K, V> other) { return cutter.Equals(other.Key); }
\r
1010 class ProjectedDirectedEnumerable : MappedDirectedEnumerable<KeyValuePair<K, V>, K>
\r
1012 public ProjectedDirectedEnumerable(IDirectedEnumerable<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }
\r
1014 public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }
\r
1018 class ProjectedDirectedCollectionValue : MappedDirectedCollectionValue<KeyValuePair<K, V>, K>
\r
1020 public ProjectedDirectedCollectionValue(IDirectedCollectionValue<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }
\r
1022 public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }
\r
1026 class SortedKeysCollection : SequencedBase<K>, ISorted<K>
\r
1028 ISortedDictionary<K, V> sorteddict;
\r
1029 //TODO: eliminate this. Only problem is the Find method because we lack method on dictionary that also
\r
1030 // returns the actual key.
\r
1031 ISorted<KeyValuePair<K, V>> sortedpairs;
\r
1032 SCG.IComparer<K> comparer;
\r
1034 internal SortedKeysCollection(ISortedDictionary<K, V> sorteddict, ISorted<KeyValuePair<K, V>> sortedpairs, SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> itemequalityComparer)
\r
1035 :base(itemequalityComparer)
\r
1037 this.sorteddict = sorteddict;
\r
1038 this.sortedpairs = sortedpairs;
\r
1039 this.comparer = comparer;
\r
1042 public override K Choose() { return sorteddict.Choose().Key; }
\r
1044 public override SCG.IEnumerator<K> GetEnumerator()
\r
1046 foreach (KeyValuePair<K, V> p in sorteddict)
\r
1047 yield return p.Key;
\r
1050 public override bool IsEmpty { get { return sorteddict.IsEmpty; } }
\r
1052 public override int Count { [Tested]get { return sorteddict.Count; } }
\r
1054 public override Speed CountSpeed { get { return sorteddict.CountSpeed; } }
\r
1056 #region ISorted<K> Members
\r
1058 public K FindMin() { return sorteddict.FindMin().Key; }
\r
1060 public K DeleteMin() { throw new ReadOnlyCollectionException(); }
\r
1062 public K FindMax() { return sorteddict.FindMax().Key; }
\r
1064 public K DeleteMax() { throw new ReadOnlyCollectionException(); }
\r
1066 public SCG.IComparer<K> Comparer { get { return comparer; } }
\r
1068 public K Predecessor(K item) { return sorteddict.Predecessor(item).Key; }
\r
1070 public K Successor(K item) { return sorteddict.Successor(item).Key; }
\r
1072 public K WeakPredecessor(K item) { return sorteddict.WeakPredecessor(item).Key; }
\r
1074 public K WeakSuccessor(K item) { return sorteddict.WeakSuccessor(item).Key; }
\r
1076 public bool Cut(IComparable<K> c, out K low, out bool lowIsValid, out K high, out bool highIsValid)
\r
1078 KeyValuePair<K, V> lowpair, highpair;
\r
1079 bool retval = sorteddict.Cut(c, out lowpair, out lowIsValid, out highpair, out highIsValid);
\r
1080 low = lowpair.Key;
\r
1081 high = highpair.Key;
\r
1085 public IDirectedEnumerable<K> RangeFrom(K bot)
\r
1087 return new ProjectedDirectedEnumerable(sorteddict.RangeFrom(bot));
\r
1090 public IDirectedEnumerable<K> RangeFromTo(K bot, K top)
\r
1092 return new ProjectedDirectedEnumerable(sorteddict.RangeFromTo(bot, top));
\r
1095 public IDirectedEnumerable<K> RangeTo(K top)
\r
1097 return new ProjectedDirectedEnumerable(sorteddict.RangeTo(top));
\r
1100 public IDirectedCollectionValue<K> RangeAll()
\r
1102 return new ProjectedDirectedCollectionValue(sorteddict.RangeAll());
\r
1105 public void AddSorted<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
\r
1107 public void RemoveRangeFrom(K low) { throw new ReadOnlyCollectionException(); }
\r
1109 public void RemoveRangeFromTo(K low, K hi) { throw new ReadOnlyCollectionException(); }
\r
1111 public void RemoveRangeTo(K hi) { throw new ReadOnlyCollectionException(); }
\r
1114 #region ICollection<K> Members
\r
1115 public Speed ContainsSpeed { get { return sorteddict.ContainsSpeed; } }
\r
1117 public bool Contains(K key) { return sorteddict.Contains(key); ; }
\r
1119 public int ContainsCount(K item) { return sorteddict.Contains(item) ? 1 : 0; }
\r
1124 /// <returns></returns>
\r
1125 public virtual ICollectionValue<K> UniqueItems()
\r
1133 /// <returns></returns>
\r
1134 public virtual ICollectionValue<KeyValuePair<K, int>> ItemMultiplicities()
\r
1136 return new MultiplicityOne<K>(this);
\r
1140 public bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : K
\r
1143 foreach (K item in items)
\r
1144 if (!sorteddict.Contains(item))
\r
1149 public bool Find(ref K item)
\r
1151 KeyValuePair<K, V> p = new KeyValuePair<K, V>(item);
\r
1152 bool retval = sortedpairs.Find(ref p);
\r
1157 public bool FindOrAdd(ref K item) { throw new ReadOnlyCollectionException(); }
\r
1159 public bool Update(K item) { throw new ReadOnlyCollectionException(); }
\r
1161 public bool Update(K item, out K olditem) { throw new ReadOnlyCollectionException(); }
\r
1163 public bool UpdateOrAdd(K item) { throw new ReadOnlyCollectionException(); }
\r
1165 public bool UpdateOrAdd(K item, out K olditem) { throw new ReadOnlyCollectionException(); }
\r
1167 public bool Remove(K item) { throw new ReadOnlyCollectionException(); }
\r
1169 public bool Remove(K item, out K removeditem) { throw new ReadOnlyCollectionException(); }
\r
1171 public void RemoveAllCopies(K item) { throw new ReadOnlyCollectionException(); }
\r
1173 public void RemoveAll<U> (SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
\r
1175 public void Clear() { throw new ReadOnlyCollectionException(); }
\r
1177 public void RetainAll<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
\r
1181 #region IExtensible<K> Members
\r
1182 public override bool IsReadOnly { get { return true; } }
\r
1184 public bool AllowsDuplicates { get { return false; } }
\r
1186 public bool DuplicatesByCounting { get { return true; } }
\r
1188 public bool Add(K item) { throw new ReadOnlyCollectionException(); }
\r
1190 public void AddAll(System.Collections.Generic.IEnumerable<K> items) { throw new ReadOnlyCollectionException(); }
\r
1192 public void AddAll<U>(System.Collections.Generic.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
\r
1194 public bool Check() { return sorteddict.Check(); }
\r
1198 #region IDirectedCollectionValue<K> Members
\r
1200 public override IDirectedCollectionValue<K> Backwards()
\r
1202 return RangeAll().Backwards();
\r
1207 #region IDirectedEnumerable<K> Members
\r
1209 IDirectedEnumerable<K> IDirectedEnumerable<K>.Backwards() { return Backwards(); }
\r
1212 #region ICloneable Members
\r
1216 /// Make a shallow copy of this SortedKeysCollection.
\r
1218 /// <returns></returns>
\r
1219 public virtual object Clone()
\r
1222 SortedArrayDictionary<K, V> dictclone = new SortedArrayDictionary<K, V>(sortedpairs.Count, comparer, EqualityComparer);
\r
1223 SortedArray<KeyValuePair<K, V>> sortedpairsclone = (SortedArray<KeyValuePair<K, V>>)(dictclone.sortedpairs);
\r
1224 foreach (K key in sorteddict.Keys)
\r
1226 sortedpairsclone.Add(new KeyValuePair<K, V>(key, default(V)));
\r
1228 return new SortedKeysCollection(dictclone, sortedpairsclone, comparer, EqualityComparer);
\r
1238 /// <param name="stringbuilder"></param>
\r
1239 /// <param name="rest"></param>
\r
1240 /// <param name="formatProvider"></param>
\r
1241 /// <returns></returns>
\r
1242 public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
\r
1244 return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);
\r
1249 class SortedArrayDictionary<K, V> : SortedDictionaryBase<K, V>, IDictionary<K, V>, ISortedDictionary<K, V>
\r
1251 #region Constructors
\r
1253 public SortedArrayDictionary() : this(Comparer<K>.Default, EqualityComparer<K>.Default) { }
\r
1256 /// Create a red-black tree dictionary using an external comparer for keys.
\r
1258 /// <param name="comparer">The external comparer</param>
\r
1259 public SortedArrayDictionary(SCG.IComparer<K> comparer) : this(comparer, new ComparerZeroHashCodeEqualityComparer<K>(comparer)) { }
\r
1264 /// <param name="comparer"></param>
\r
1265 /// <param name="equalityComparer"></param>
\r
1266 public SortedArrayDictionary(SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> equalityComparer) : base(comparer,equalityComparer)
\r
1268 pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(new KeyValuePairComparer<K, V>(comparer));
\r
1274 /// <param name="comparer"></param>
\r
1275 /// <param name="equalityComparer"></param>
\r
1276 /// <param name="capacity"></param>
\r
1277 public SortedArrayDictionary(int capacity, SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> equalityComparer) : base(comparer,equalityComparer)
\r
1279 pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(capacity, new KeyValuePairComparer<K, V>(comparer));
\r
1286 /// <returns></returns>
\r
1287 public override object Clone()
\r
1289 SortedArrayDictionary<K, V> clone = new SortedArrayDictionary<K, V>(Comparer, EqualityComparer);
\r
1290 clone.sortedpairs.AddSorted(sortedpairs);
\r