mcs/class/Mono.C5/current/C5/Dictionaries.cs

   1 /*\r
   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
   9  \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
  12  \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
  19  SOFTWARE.\r
  20 */\r
  21 \r
  22 using System;\r
  23 using System.Diagnostics;\r
  24 using SCG = System.Collections.Generic;\r
  25 namespace C5\r
  26 {\r
  27   /// <summary>\r
  28   /// An entry in a dictionary from K to V.\r
  29   /// </summary>\r
  30   [Serializable]\r
  31   public struct KeyValuePair<K, V> : IEquatable<KeyValuePair<K, V>>, IShowable\r
  32   {\r
  33     /// <summary>\r
  34     /// The key field of the entry\r
  35     /// </summary>\r
  36     public K Key;\r
  37 \r
  38     /// <summary>\r
  39     /// The value field of the entry\r
  40     /// </summary>\r
  41     public V Value;\r
  42 \r
  43     /// <summary>\r
  44     /// Create an entry with specified key and value\r
  45     /// </summary>\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
  49 \r
  50 \r
  51     /// <summary>\r
  52     /// Create an entry with a specified key. The value will be the default value of type <code>V</code>.\r
  53     /// </summary>\r
  54     /// <param name="key">The key</param>\r
  55     public KeyValuePair(K key) { Key = key; Value = default(V); }\r
  56 \r
  57 \r
  58     /// <summary>\r
  59     /// Pretty print an entry\r
  60     /// </summary>\r
  61     /// <returns>(key, value)</returns>\r
  62     [Tested]\r
  63     public override string ToString() { return "(" + Key + ", " + Value + ")"; }\r
  64 \r
  65 \r
  66     /// <summary>\r
  67     /// Check equality of entries. \r
  68     /// </summary>\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
  71     [Tested]\r
  72     public override bool Equals(object obj)\r
  73     {\r
  74       if (!(obj is KeyValuePair<K, V>))\r
  75         return false;\r
  76       KeyValuePair<K, V> other = (KeyValuePair<K, V>)obj;\r
  77       return Equals(other);\r
  78     }\r
  79 \r
  80 \r
  81     /// <summary>\r
  82     /// Get the hash code of the pair.\r
  83     /// </summary>\r
  84     /// <returns>The hash code</returns>\r
  85     [Tested]\r
  86     public override int GetHashCode() { return EqualityComparer<K>.Default.GetHashCode(Key) + 13984681 * EqualityComparer<V>.Default.GetHashCode(Value); }\r
  87 \r
  88     /// <summary>\r
  89     /// \r
  90     /// </summary>\r
  91     /// <param name="other"></param>\r
  92     /// <returns></returns>\r
  93     public bool Equals(KeyValuePair<K, V> other)\r
  94     {\r
  95       return EqualityComparer<K>.Default.Equals(Key, other.Key) && EqualityComparer<V>.Default.Equals(Value, other.Value);\r
  96     }\r
  97 \r
  98     /// <summary>\r
  99     /// \r
 100     /// </summary>\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
 105 \r
 106     /// <summary>\r
 107     /// \r
 108     /// </summary>\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
 113 \r
 114     #region IShowable Members\r
 115 \r
 116     /// <summary>\r
 117     /// \r
 118     /// </summary>\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
 124     {\r
 125       if (rest < 0)\r
 126         return false;\r
 127       if (!Showing.Show(Key, stringbuilder, ref rest, formatProvider))\r
 128         return false;\r
 129       stringbuilder.Append(" => ");\r
 130       rest -= 4;\r
 131       if (!Showing.Show(Value, stringbuilder, ref rest, formatProvider))\r
 132         return false;\r
 133       return rest >= 0;\r
 134     }\r
 135     #endregion\r
 136 \r
 137     #region IFormattable Members\r
 138 \r
 139     /// <summary>\r
 140     /// \r
 141     /// </summary>\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
 146     {\r
 147       return Showing.ShowString(this, format, formatProvider);\r
 148     }\r
 149 \r
 150     #endregion\r
 151   }\r
 152 \r
 153 \r
 154 \r
 155   /// <summary>\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
 158   /// </summary>\r
 159   [Serializable]\r
 160   public class KeyValuePairComparer<K, V> : SCG.IComparer<KeyValuePair<K, V>>\r
 161   {\r
 162     SCG.IComparer<K> comparer;\r
 163 \r
 164 \r
 165     /// <summary>\r
 166     /// Create an entry comparer for a item comparer of the keys\r
 167     /// </summary>\r
 168     /// <param name="comparer">Comparer of keys</param>\r
 169     public KeyValuePairComparer(SCG.IComparer<K> comparer)\r
 170     {\r
 171       if (comparer == null)\r
 172         throw new NullReferenceException();\r
 173       this.comparer = comparer;\r
 174     }\r
 175 \r
 176 \r
 177     /// <summary>\r
 178     /// Compare two entries\r
 179     /// </summary>\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
 183     [Tested]\r
 184     public int Compare(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)\r
 185     { return comparer.Compare(entry1.Key, entry2.Key); }\r
 186   }\r
 187 \r
 188 \r
 189 \r
 190   /// <summary>\r
 191   /// Default equalityComparer for dictionary entries.\r
 192   /// Operations only look at keys and uses an externaly defined equalityComparer for that.\r
 193   /// </summary>\r
 194   [Serializable]\r
 195   public sealed class KeyValuePairEqualityComparer<K, V> : SCG.IEqualityComparer<KeyValuePair<K, V>>\r
 196   {\r
 197     SCG.IEqualityComparer<K> keyequalityComparer;\r
 198 \r
 199 \r
 200     /// <summary>\r
 201     /// Create an entry equalityComparer using the default equalityComparer for keys\r
 202     /// </summary>\r
 203     public KeyValuePairEqualityComparer() { keyequalityComparer = EqualityComparer<K>.Default; }\r
 204 \r
 205 \r
 206     /// <summary>\r
 207     /// Create an entry equalityComparer from a specified item equalityComparer for the keys\r
 208     /// </summary>\r
 209     /// <param name="keyequalityComparer">The key equalityComparer</param>\r
 210     public KeyValuePairEqualityComparer(SCG.IEqualityComparer<K> keyequalityComparer)\r
 211     {\r
 212       if (keyequalityComparer == null)\r
 213         throw new NullReferenceException("Key equality comparer cannot be null");\r
 214       this.keyequalityComparer = keyequalityComparer;\r
 215     }\r
 216 \r
 217 \r
 218     /// <summary>\r
 219     /// Get the hash code of the entry\r
 220     /// </summary>\r
 221     /// <param name="entry">The entry</param>\r
 222     /// <returns>The hash code of the key</returns>\r
 223     [Tested]\r
 224     public int GetHashCode(KeyValuePair<K, V> entry) { return keyequalityComparer.GetHashCode(entry.Key); }\r
 225 \r
 226 \r
 227     /// <summary>\r
 228     /// Test two entries for equality\r
 229     /// </summary>\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
 233     [Tested]\r
 234     public bool Equals(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)\r
 235     { return keyequalityComparer.Equals(entry1.Key, entry2.Key); }\r
 236   }\r
 237 \r
 238 \r
 239 \r
 240   /// <summary>\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
 243   /// \r
 244   /// </summary>\r
 245   [Serializable]\r
 246   public abstract class DictionaryBase<K, V> : CollectionValueBase<KeyValuePair<K, V>>, IDictionary<K, V>\r
 247   {\r
 248     /// <summary>\r
 249     /// The set collection of entries underlying this dictionary implementation\r
 250     /// </summary>\r
 251     protected ICollection<KeyValuePair<K, V>> pairs;\r
 252 \r
 253     SCG.IEqualityComparer<K> keyequalityComparer;\r
 254 \r
 255     #region Events\r
 256     ProxyEventBlock<KeyValuePair<K, V>> eventBlock;\r
 257 \r
 258     /// <summary>\r
 259     /// The change event. Will be raised for every change operation on the collection.\r
 260     /// </summary>\r
 261     public override event CollectionChangedHandler<KeyValuePair<K, V>> CollectionChanged\r
 262     {\r
 263       add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionChanged += value; }\r
 264       remove { if (eventBlock != null) eventBlock.CollectionChanged -= value; }\r
 265     }\r
 266 \r
 267     /// <summary>\r
 268     /// The change event. Will be raised for every change operation on the collection.\r
 269     /// </summary>\r
 270     public override event CollectionClearedHandler<KeyValuePair<K, V>> CollectionCleared\r
 271     {\r
 272       add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionCleared += value; }\r
 273       remove { if (eventBlock != null) eventBlock.CollectionCleared -= value; }\r
 274     }\r
 275 \r
 276     /// <summary>\r
 277     /// The item added  event. Will be raised for every individual addition to the collection.\r
 278     /// </summary>\r
 279     public override event ItemsAddedHandler<KeyValuePair<K, V>> ItemsAdded\r
 280     {\r
 281       add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsAdded += value; }\r
 282       remove { if (eventBlock != null) eventBlock.ItemsAdded -= value; }\r
 283     }\r
 284 \r
 285     /// <summary>\r
 286     /// The item added  event. Will be raised for every individual removal from the collection.\r
 287     /// </summary>\r
 288     public override event ItemsRemovedHandler<KeyValuePair<K, V>> ItemsRemoved\r
 289     {\r
 290       add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsRemoved += value; }\r
 291       remove { if (eventBlock != null) eventBlock.ItemsRemoved -= value; }\r
 292     }\r
 293 \r
 294     /// <summary>\r
 295     /// \r
 296     /// </summary>\r
 297     public override EventTypeEnum ListenableEvents\r
 298     {\r
 299       get\r
 300       {\r
 301         return EventTypeEnum.Basic;\r
 302       }\r
 303     }\r
 304 \r
 305     /// <summary>\r
 306     /// \r
 307     /// </summary>\r
 308     public override EventTypeEnum ActiveEvents\r
 309     {\r
 310       get\r
 311       {\r
 312         return pairs.ActiveEvents;\r
 313       }\r
 314     }\r
 315 \r
 316     #endregion\r
 317 \r
 318     /// <summary>\r
 319     /// \r
 320     /// </summary>\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
 326 \r
 327     #region IDictionary<K,V> Members\r
 328 \r
 329     /// <summary>\r
 330     /// \r
 331     /// </summary>\r
 332     /// <value></value>\r
 333     public virtual SCG.IEqualityComparer<K> EqualityComparer { get { return keyequalityComparer; } }\r
 334 \r
 335 \r
 336     /// <summary>\r
 337     /// Add a new (key, value) pair (a mapping) to the dictionary.\r
 338     /// </summary>\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
 342     [Tested]\r
 343     public virtual void Add(K key, V value)\r
 344     {\r
 345       KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);\r
 346 \r
 347       if (!pairs.Add(p))\r
 348         throw new DuplicateNotAllowedException("Key being added: '" + key + "'");\r
 349     }\r
 350 \r
 351     /// <summary>\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
 354     /// </summary>\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
 359         where L : K\r
 360         where W : V\r
 361     {\r
 362       foreach (KeyValuePair<L, W> pair in entries)\r
 363       {\r
 364         KeyValuePair<K, V> p = new KeyValuePair<K, V>(pair.Key, pair.Value);\r
 365         if (!pairs.Add(p))\r
 366           throw new DuplicateNotAllowedException("Key being added: '" + pair.Key + "'");\r
 367       }\r
 368     }\r
 369 \r
 370     /// <summary>\r
 371     /// Remove an entry with a given key from the dictionary\r
 372     /// </summary>\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
 375     [Tested]\r
 376     public virtual bool Remove(K key)\r
 377     {\r
 378       KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
 379 \r
 380       return pairs.Remove(p);\r
 381     }\r
 382 \r
 383 \r
 384     /// <summary>\r
 385     /// Remove an entry with a given key from the dictionary and report its value.\r
 386     /// </summary>\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
 390     [Tested]\r
 391     public virtual bool Remove(K key, out V value)\r
 392     {\r
 393       KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
 394 \r
 395       if (pairs.Remove(p, out p))\r
 396       {\r
 397         value = p.Value;\r
 398         return true;\r
 399       }\r
 400       else\r
 401       {\r
 402         value = default(V);\r
 403         return false;\r
 404       }\r
 405     }\r
 406 \r
 407 \r
 408     /// <summary>\r
 409     /// Remove all entries from the dictionary\r
 410     /// </summary>\r
 411     [Tested]\r
 412     public virtual void Clear() { pairs.Clear(); }\r
 413 \r
 414     /// <summary>\r
 415     /// \r
 416     /// </summary>\r
 417     /// <value></value>\r
 418     public virtual Speed ContainsSpeed { get { return pairs.ContainsSpeed; } }\r
 419 \r
 420     /// <summary>\r
 421     /// Check if there is an entry with a specified key\r
 422     /// </summary>\r
 423     /// <param name="key">The key to look for</param>\r
 424     /// <returns>True if key was found</returns>\r
 425     [Tested]\r
 426     public virtual bool Contains(K key)\r
 427     {\r
 428       KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
 429 \r
 430       return pairs.Contains(p);\r
 431     }\r
 432 \r
 433       class LiftedEnumerable<H> : SCG.IEnumerable<KeyValuePair<K, V>> where H : K\r
 434       {\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
 438 \r
 439           #region IEnumerable Members\r
 440 \r
 441           System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()\r
 442           {\r
 443               throw new Exception("The method or operation is not implemented.");\r
 444           }\r
 445 \r
 446           #endregion\r
 447       }\r
 448 \r
 449     /// <summary>\r
 450     /// \r
 451     /// </summary>\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
 455       {\r
 456           return pairs.ContainsAll(new LiftedEnumerable<H>(keys));\r
 457       }\r
 458 \r
 459     /// <summary>\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
 462     /// </summary>\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
 466     [Tested]\r
 467     public virtual bool Find(K key, out V value)\r
 468     {\r
 469       return Find(ref key, out value);\r
 470     }\r
 471     /// <summary>\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
 474     /// </summary>\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
 479     {\r
 480       KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
 481 \r
 482       if (pairs.Find(ref p))\r
 483       {\r
 484         key = p.Key;\r
 485         value = p.Value;\r
 486         return true;\r
 487       }\r
 488       else\r
 489       {\r
 490         value = default(V);\r
 491         return false;\r
 492       }\r
 493     }\r
 494 \r
 495 \r
 496     /// <summary>\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
 499     /// </summary>\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
 503     [Tested]\r
 504     public virtual bool Update(K key, V value)\r
 505     {\r
 506       KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);\r
 507 \r
 508       return pairs.Update(p);\r
 509     }\r
 510 \r
 511 \r
 512     /// <summary>\r
 513     /// \r
 514     /// </summary>\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
 520     {\r
 521       KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);\r
 522 \r
 523       bool retval = pairs.Update(p, out p);\r
 524       oldvalue = p.Value;\r
 525       return retval;\r
 526     }\r
 527 \r
 528 \r
 529     /// <summary>\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
 532     /// </summary>\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
 537     [Tested]\r
 538     public virtual bool FindOrAdd(K key, ref V value)\r
 539     {\r
 540       KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);\r
 541 \r
 542       if (!pairs.FindOrAdd(ref p))\r
 543         return false;\r
 544       else\r
 545       {\r
 546         value = p.Value;\r
 547         //key = p.key;\r
 548         return true;\r
 549       }\r
 550     }\r
 551 \r
 552 \r
 553     /// <summary>\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
 556     /// </summary>\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
 560     [Tested]\r
 561     public virtual bool UpdateOrAdd(K key, V value)\r
 562     {\r
 563       return pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value));\r
 564     }\r
 565 \r
 566 \r
 567     /// <summary>\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
 570     /// </summary>\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
 576     {\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
 580       return retval;\r
 581     }\r
 582 \r
 583 \r
 584 \r
 585     #region Keys,Values support classes\r
 586 \r
 587     internal class ValuesCollection : CollectionValueBase<V>, ICollectionValue<V>\r
 588     {\r
 589       ICollection<KeyValuePair<K, V>> pairs;\r
 590 \r
 591 \r
 592       internal ValuesCollection(ICollection<KeyValuePair<K, V>> pairs)\r
 593       { this.pairs = pairs; }\r
 594 \r
 595 \r
 596       public override V Choose() { return pairs.Choose().Value; }\r
 597 \r
 598       [Tested]\r
 599       public override SCG.IEnumerator<V> GetEnumerator()\r
 600       {\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
 604       }\r
 605 \r
 606       public override bool IsEmpty { get { return pairs.IsEmpty; } }\r
 607 \r
 608       [Tested]\r
 609       public override int Count { [Tested]get { return pairs.Count; } }\r
 610 \r
 611       public override Speed CountSpeed { get { return Speed.Constant; } }\r
 612     }\r
 613 \r
 614 \r
 615 \r
 616     internal class KeysCollection : CollectionValueBase<K>, ICollectionValue<K>\r
 617     {\r
 618       ICollection<KeyValuePair<K, V>> pairs;\r
 619 \r
 620 \r
 621       internal KeysCollection(ICollection<KeyValuePair<K, V>> pairs)\r
 622       { this.pairs = pairs; }\r
 623 \r
 624       public override K Choose() { return pairs.Choose().Key; }\r
 625 \r
 626       [Tested]\r
 627       public override SCG.IEnumerator<K> GetEnumerator()\r
 628       {\r
 629         foreach (KeyValuePair<K, V> p in pairs)\r
 630           yield return p.Key;\r
 631       }\r
 632 \r
 633       public override bool IsEmpty { get { return pairs.IsEmpty; } }\r
 634 \r
 635       [Tested]\r
 636       public override int Count { [Tested]get { return pairs.Count; } }\r
 637 \r
 638       public override Speed CountSpeed { get { return pairs.CountSpeed; } }\r
 639     }\r
 640     #endregion\r
 641 \r
 642     /// <summary>\r
 643     /// \r
 644     /// </summary>\r
 645     /// <value>A collection containg the all the keys of the dictionary</value>\r
 646     [Tested]\r
 647     public virtual ICollectionValue<K> Keys { [Tested]get { return new KeysCollection(pairs); } }\r
 648 \r
 649 \r
 650     /// <summary>\r
 651     /// \r
 652     /// </summary>\r
 653     /// <value>A collection containing all the values of the dictionary</value>\r
 654     [Tested]\r
 655     public virtual ICollectionValue<V> Values { [Tested]get { return new ValuesCollection(pairs); } }\r
 656 \r
 657     /// <summary>\r
 658     /// \r
 659     /// </summary>\r
 660     public virtual Fun<K, V> Fun { get { return delegate(K k) { return this[k]; }; } }\r
 661 \r
 662     /// <summary>\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
 666     /// </summary>\r
 667     /// <exception cref="NoSuchItemException"> On get if no entry is found. </exception>\r
 668     /// <value>The value corresponding to the key</value>\r
 669     [Tested]\r
 670     public virtual V this[K key]\r
 671     {\r
 672       [Tested]\r
 673       get\r
 674       {\r
 675         KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
 676 \r
 677         if (pairs.Find(ref p))\r
 678           return p.Value;\r
 679         else\r
 680           throw new NoSuchItemException("Key '" + key.ToString() + "' not present in Dictionary");\r
 681       }\r
 682       [Tested]\r
 683       set\r
 684       { pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value)); }\r
 685     }\r
 686 \r
 687 \r
 688     /// <summary>\r
 689     /// \r
 690     /// </summary>\r
 691     /// <value>True if dictionary is read  only</value>\r
 692     [Tested]\r
 693     public virtual bool IsReadOnly { [Tested]get { return pairs.IsReadOnly; } }\r
 694 \r
 695 \r
 696     /// <summary>\r
 697     /// Check the integrity of the internal data structures of this dictionary.\r
 698     /// </summary>\r
 699     /// <returns>True if check does not fail.</returns>\r
 700     [Tested]\r
 701     public virtual bool Check() { return pairs.Check(); }\r
 702 \r
 703     #endregion\r
 704 \r
 705     #region ICollectionValue<KeyValuePair<K,V>> Members\r
 706 \r
 707     /// <summary>\r
 708     /// \r
 709     /// </summary>\r
 710     /// <value>True if this collection is empty.</value>\r
 711     public override bool IsEmpty { get { return pairs.IsEmpty; } }\r
 712 \r
 713 \r
 714     /// <summary>\r
 715     /// \r
 716     /// </summary>\r
 717     /// <value>The number of entrues in the dictionary</value>\r
 718     [Tested]\r
 719     public override int Count { [Tested]get { return pairs.Count; } }\r
 720 \r
 721     /// <summary>\r
 722     /// \r
 723     /// </summary>\r
 724     /// <value>The number of entrues in the dictionary</value>\r
 725     [Tested]\r
 726     public override Speed CountSpeed { [Tested]get { return pairs.CountSpeed; } }\r
 727 \r
 728     /// <summary>\r
 729     /// Choose some entry in this Dictionary. \r
 730     /// </summary>\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
 734 \r
 735     /// <summary>\r
 736     /// Create an enumerator for the collection of entries of the dictionary\r
 737     /// </summary>\r
 738     /// <returns>The enumerator</returns>\r
 739     [Tested]\r
 740     public override SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator()\r
 741     {\r
 742       return pairs.GetEnumerator(); ;\r
 743     }\r
 744 \r
 745     #endregion\r
 746 \r
 747     /// <summary>\r
 748     /// \r
 749     /// </summary>\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
 755     {\r
 756       return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);\r
 757     }\r
 758 \r
 759     /// <summary>\r
 760     /// \r
 761     /// </summary>\r
 762     /// <returns></returns>\r
 763     public abstract object Clone();\r
 764 \r
 765   }\r
 766 \r
 767   /// <summary>\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
 770   /// \r
 771   /// </summary>\r
 772   public abstract class SortedDictionaryBase<K, V> : DictionaryBase<K, V>, ISortedDictionary<K, V>\r
 773   {\r
 774     #region Fields\r
 775 \r
 776     /// <summary>\r
 777     /// \r
 778     /// </summary>\r
 779     protected ISorted<KeyValuePair<K, V>> sortedpairs;\r
 780     SCG.IComparer<K> keycomparer;\r
 781 \r
 782     /// <summary>\r
 783     /// \r
 784     /// </summary>\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
 788 \r
 789     #endregion\r
 790 \r
 791     #region ISortedDictionary<K,V> Members\r
 792 \r
 793     /// <summary>\r
 794     /// The key comparer used by this dictionary.\r
 795     /// </summary>\r
 796     /// <value></value>\r
 797     public SCG.IComparer<K> Comparer { get { return keycomparer; } }\r
 798 \r
 799     /// <summary>\r
 800     /// \r
 801     /// </summary>\r
 802     /// <value></value>\r
 803     public new ISorted<K> Keys { get { return new SortedKeysCollection(this, sortedpairs, keycomparer, EqualityComparer); } }\r
 804 \r
 805     /// <summary>\r
 806     /// Get the entry in the dictionary whose key is the\r
 807     /// predecessor of a specified key.\r
 808     /// </summary>\r
 809     /// <exception cref="NoSuchItemException"></exception>\r
 810     /// <param name="key">The key</param>\r
 811     /// <returns>The entry</returns>\r
 812     [Tested]\r
 813     public KeyValuePair<K, V> Predecessor(K key)\r
 814     {\r
 815       KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
 816 \r
 817       return sortedpairs.Predecessor(p);\r
 818     }\r
 819 \r
 820 \r
 821     /// <summary>\r
 822     /// Get the entry in the dictionary whose key is the\r
 823     /// weak predecessor of a specified key.\r
 824     /// </summary>\r
 825     /// <exception cref="NoSuchItemException"></exception>\r
 826     /// <param name="key">The key</param>\r
 827     /// <returns>The entry</returns>\r
 828     [Tested]\r
 829     public KeyValuePair<K, V> WeakPredecessor(K key)\r
 830     {\r
 831       KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
 832 \r
 833       return sortedpairs.WeakPredecessor(p);\r
 834     }\r
 835 \r
 836 \r
 837     /// <summary>\r
 838     /// Get the entry in the dictionary whose key is the\r
 839     /// successor of a specified key.\r
 840     /// </summary>\r
 841     /// <exception cref="NoSuchItemException"></exception>\r
 842     /// <param name="key">The key</param>\r
 843     /// <returns>The entry</returns>\r
 844     [Tested]\r
 845     public KeyValuePair<K, V> Successor(K key)\r
 846     {\r
 847       KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);\r
 848 \r
 849       return sortedpairs.Successor(p);\r
 850     }\r
 851 \r
 852 \r
 853     /// <summary>\r
 854     /// Get the entry in the dictionary whose key is the\r
 855     /// weak successor of a specified key.\r
 856     /// </summary>\r
 857     /// <exception cref="NoSuchItemException"></exception>\r
 858     /// <param name="key">The key</param>\r
 859     /// <returns>The entry</returns>\r
 860     [Tested]\r
 861     public KeyValuePair<K, V> WeakSuccessor(K key)\r
 862     {\r
 863       return sortedpairs.WeakSuccessor(new KeyValuePair<K, V>(key));\r
 864     }\r
 865 \r
 866     #endregion\r
 867 \r
 868     #region ISortedDictionary<K,V> Members\r
 869 \r
 870     /// <summary>\r
 871     /// \r
 872     /// </summary>\r
 873     /// <returns></returns>\r
 874     public KeyValuePair<K, V> FindMin()\r
 875     {\r
 876       return sortedpairs.FindMin();\r
 877     }\r
 878 \r
 879     /// <summary>\r
 880     /// \r
 881     /// </summary>\r
 882     /// <returns></returns>\r
 883     public KeyValuePair<K, V> DeleteMin()\r
 884     {\r
 885       return sortedpairs.DeleteMin();\r
 886     }\r
 887 \r
 888     /// <summary>\r
 889     /// \r
 890     /// </summary>\r
 891     /// <returns></returns>\r
 892     public KeyValuePair<K, V> FindMax()\r
 893     {\r
 894       return sortedpairs.FindMax();\r
 895     }\r
 896 \r
 897     /// <summary>\r
 898     /// \r
 899     /// </summary>\r
 900     /// <returns></returns>\r
 901     public KeyValuePair<K, V> DeleteMax()\r
 902     {\r
 903       return sortedpairs.DeleteMax();\r
 904     }\r
 905 \r
 906     /// <summary>\r
 907     /// \r
 908     /// </summary>\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
 916     {\r
 917       return sortedpairs.Cut(new KeyValuePairComparable(cutter), out lowEntry, out lowIsValid, out highEntry, out highIsValid);\r
 918     }\r
 919 \r
 920     /// <summary>\r
 921     /// \r
 922     /// </summary>\r
 923     /// <param name="bot"></param>\r
 924     /// <returns></returns>\r
 925     public IDirectedEnumerable<KeyValuePair<K, V>> RangeFrom(K bot)\r
 926     {\r
 927       return sortedpairs.RangeFrom(new KeyValuePair<K, V>(bot));\r
 928     }\r
 929 \r
 930     /// <summary>\r
 931     /// \r
 932     /// </summary>\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
 937     {\r
 938       return sortedpairs.RangeFromTo(new KeyValuePair<K, V>(bot), new KeyValuePair<K, V>(top));\r
 939     }\r
 940 \r
 941     /// <summary>\r
 942     /// \r
 943     /// </summary>\r
 944     /// <param name="top"></param>\r
 945     /// <returns></returns>\r
 946     public IDirectedEnumerable<KeyValuePair<K, V>> RangeTo(K top)\r
 947     {\r
 948       return sortedpairs.RangeTo(new KeyValuePair<K, V>(top));\r
 949     }\r
 950 \r
 951     /// <summary>\r
 952     /// \r
 953     /// </summary>\r
 954     /// <returns></returns>\r
 955     public IDirectedCollectionValue<KeyValuePair<K, V>> RangeAll()\r
 956     {\r
 957       return sortedpairs.RangeAll();\r
 958     }\r
 959 \r
 960     /// <summary>\r
 961     /// \r
 962     /// </summary>\r
 963     /// <param name="items"></param>\r
 964     public void AddSorted(SCG.IEnumerable<KeyValuePair<K, V>> items)\r
 965     {\r
 966       sortedpairs.AddSorted(items);\r
 967     }\r
 968 \r
 969     /// <summary>\r
 970     /// \r
 971     /// </summary>\r
 972     /// <param name="lowKey"></param>\r
 973     public void RemoveRangeFrom(K lowKey)\r
 974     {\r
 975       sortedpairs.RemoveRangeFrom(new KeyValuePair<K, V>(lowKey));\r
 976     }\r
 977 \r
 978     /// <summary>\r
 979     /// \r
 980     /// </summary>\r
 981     /// <param name="lowKey"></param>\r
 982     /// <param name="highKey"></param>\r
 983     public void RemoveRangeFromTo(K lowKey, K highKey)\r
 984     {\r
 985       sortedpairs.RemoveRangeFromTo(new KeyValuePair<K, V>(lowKey), new KeyValuePair<K, V>(highKey));\r
 986     }\r
 987 \r
 988     /// <summary>\r
 989     /// \r
 990     /// </summary>\r
 991     /// <param name="highKey"></param>\r
 992     public void RemoveRangeTo(K highKey)\r
 993     {\r
 994       sortedpairs.RemoveRangeTo(new KeyValuePair<K, V>(highKey));\r
 995     }\r
 996 \r
 997     #endregion\r
 998 \r
 999     class KeyValuePairComparable : IComparable<KeyValuePair<K, V>>\r
1000     {\r
1001       IComparable<K> cutter;\r
1002 \r
1003       internal KeyValuePairComparable(IComparable<K> cutter) { this.cutter = cutter; }\r
1004 \r
1005       public int CompareTo(KeyValuePair<K, V> other) { return cutter.CompareTo(other.Key); }\r
1006 \r
1007       public bool Equals(KeyValuePair<K, V> other) { return cutter.Equals(other.Key); }\r
1008     }\r
1009 \r
1010     class ProjectedDirectedEnumerable : MappedDirectedEnumerable<KeyValuePair<K, V>, K>\r
1011     {\r
1012       public ProjectedDirectedEnumerable(IDirectedEnumerable<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }\r
1013 \r
1014       public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }\r
1015 \r
1016     }\r
1017 \r
1018     class ProjectedDirectedCollectionValue : MappedDirectedCollectionValue<KeyValuePair<K, V>, K>\r
1019     {\r
1020       public ProjectedDirectedCollectionValue(IDirectedCollectionValue<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }\r
1021 \r
1022       public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }\r
1023 \r
1024     }\r
1025 \r
1026     class SortedKeysCollection : SequencedBase<K>, ISorted<K>\r
1027     {\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
1033 \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
1036       {\r
1037         this.sorteddict = sorteddict;\r
1038         this.sortedpairs = sortedpairs;\r
1039         this.comparer = comparer;\r
1040       }\r
1041 \r
1042       public override K Choose() { return sorteddict.Choose().Key; }\r
1043 \r
1044       public override SCG.IEnumerator<K> GetEnumerator()\r
1045       {\r
1046         foreach (KeyValuePair<K, V> p in sorteddict)\r
1047           yield return p.Key;\r
1048       }\r
1049 \r
1050       public override bool IsEmpty { get { return sorteddict.IsEmpty; } }\r
1051 \r
1052       public override int Count { [Tested]get { return sorteddict.Count; } }\r
1053 \r
1054       public override Speed CountSpeed { get { return sorteddict.CountSpeed; } }\r
1055 \r
1056       #region ISorted<K> Members\r
1057 \r
1058       public K FindMin() { return sorteddict.FindMin().Key; }\r
1059 \r
1060       public K DeleteMin() { throw new ReadOnlyCollectionException(); }\r
1061 \r
1062       public K FindMax() { return sorteddict.FindMax().Key; }\r
1063 \r
1064       public K DeleteMax() { throw new ReadOnlyCollectionException(); }\r
1065 \r
1066       public SCG.IComparer<K> Comparer { get { return comparer; } }\r
1067 \r
1068       public K Predecessor(K item) { return sorteddict.Predecessor(item).Key; }\r
1069 \r
1070       public K Successor(K item) { return sorteddict.Successor(item).Key; }\r
1071 \r
1072       public K WeakPredecessor(K item) { return sorteddict.WeakPredecessor(item).Key; }\r
1073 \r
1074       public K WeakSuccessor(K item) { return sorteddict.WeakSuccessor(item).Key; }\r
1075 \r
1076       public bool Cut(IComparable<K> c, out K low, out bool lowIsValid, out K high, out bool highIsValid)\r
1077       {\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
1082         return retval;\r
1083       }\r
1084 \r
1085       public IDirectedEnumerable<K> RangeFrom(K bot)\r
1086       {\r
1087         return new ProjectedDirectedEnumerable(sorteddict.RangeFrom(bot));\r
1088       }\r
1089 \r
1090       public IDirectedEnumerable<K> RangeFromTo(K bot, K top)\r
1091       {\r
1092         return new ProjectedDirectedEnumerable(sorteddict.RangeFromTo(bot, top));\r
1093       }\r
1094 \r
1095       public IDirectedEnumerable<K> RangeTo(K top)\r
1096       {\r
1097         return new ProjectedDirectedEnumerable(sorteddict.RangeTo(top));\r
1098       }\r
1099 \r
1100       public IDirectedCollectionValue<K> RangeAll()\r
1101       {\r
1102         return new ProjectedDirectedCollectionValue(sorteddict.RangeAll());\r
1103       }\r
1104 \r
1105       public void AddSorted<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }\r
1106 \r
1107       public void RemoveRangeFrom(K low) { throw new ReadOnlyCollectionException(); }\r
1108 \r
1109       public void RemoveRangeFromTo(K low, K hi) { throw new ReadOnlyCollectionException(); }\r
1110 \r
1111       public void RemoveRangeTo(K hi) { throw new ReadOnlyCollectionException(); }\r
1112       #endregion\r
1113 \r
1114       #region ICollection<K> Members\r
1115       public Speed ContainsSpeed { get { return sorteddict.ContainsSpeed; } }\r
1116 \r
1117       public bool Contains(K key) { return sorteddict.Contains(key); ;      }\r
1118 \r
1119       public int ContainsCount(K item) { return sorteddict.Contains(item) ? 1 : 0; }\r
1120 \r
1121       /// <summary>\r
1122       /// \r
1123       /// </summary>\r
1124       /// <returns></returns>\r
1125       public virtual ICollectionValue<K> UniqueItems()\r
1126       {\r
1127         return this;\r
1128       }\r
1129 \r
1130       /// <summary>\r
1131       /// \r
1132       /// </summary>\r
1133       /// <returns></returns>\r
1134       public virtual ICollectionValue<KeyValuePair<K, int>> ItemMultiplicities()\r
1135       {\r
1136         return new MultiplicityOne<K>(this);\r
1137       }\r
1138 \r
1139 \r
1140       public bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : K\r
1141       {\r
1142         //TODO: optimize?\r
1143         foreach (K item in items)\r
1144           if (!sorteddict.Contains(item))\r
1145             return false;\r
1146         return true;\r
1147       }\r
1148 \r
1149       public bool Find(ref K item)\r
1150       {\r
1151         KeyValuePair<K, V> p = new KeyValuePair<K, V>(item);\r
1152         bool retval = sortedpairs.Find(ref p);\r
1153         item = p.Key;\r
1154         return retval;\r
1155       }\r
1156 \r
1157       public bool FindOrAdd(ref K item) { throw new ReadOnlyCollectionException(); }\r
1158 \r
1159       public bool Update(K item) { throw new ReadOnlyCollectionException(); }\r
1160 \r
1161       public bool Update(K item, out K olditem) { throw new ReadOnlyCollectionException(); }\r
1162 \r
1163       public bool UpdateOrAdd(K item) { throw new ReadOnlyCollectionException(); }\r
1164 \r
1165       public bool UpdateOrAdd(K item, out K olditem) { throw new ReadOnlyCollectionException(); }\r
1166 \r
1167       public bool Remove(K item) { throw new ReadOnlyCollectionException(); }\r
1168 \r
1169       public bool Remove(K item, out K removeditem) { throw new ReadOnlyCollectionException(); }\r
1170 \r
1171       public void RemoveAllCopies(K item) { throw new ReadOnlyCollectionException(); }\r
1172 \r
1173       public void RemoveAll<U> (SCG.IEnumerable<U> items)  where U : K { throw new ReadOnlyCollectionException(); }\r
1174 \r
1175       public void Clear() { throw new ReadOnlyCollectionException(); }\r
1176 \r
1177       public void RetainAll<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }\r
1178 \r
1179       #endregion\r
1180 \r
1181       #region IExtensible<K> Members\r
1182       public override bool IsReadOnly { get { return true; } }\r
1183 \r
1184       public bool AllowsDuplicates { get { return false; } }\r
1185 \r
1186       public bool DuplicatesByCounting { get { return true; } }\r
1187 \r
1188       public bool Add(K item) { throw new ReadOnlyCollectionException(); }\r
1189 \r
1190       public void AddAll(System.Collections.Generic.IEnumerable<K> items) { throw new ReadOnlyCollectionException(); }\r
1191 \r
1192       public void AddAll<U>(System.Collections.Generic.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }\r
1193 \r
1194       public bool Check() { return sorteddict.Check(); }\r
1195 \r
1196       #endregion\r
1197 \r
1198       #region IDirectedCollectionValue<K> Members\r
1199 \r
1200       public override IDirectedCollectionValue<K> Backwards()\r
1201       {\r
1202         return RangeAll().Backwards();\r
1203       }\r
1204 \r
1205       #endregion\r
1206 \r
1207       #region IDirectedEnumerable<K> Members\r
1208 \r
1209       IDirectedEnumerable<K> IDirectedEnumerable<K>.Backwards() { return Backwards(); }\r
1210       #endregion\r
1211 \r
1212       #region ICloneable Members\r
1213 \r
1214       //TODO: test\r
1215       /// <summary>\r
1216       /// Make a shallow copy of this SortedKeysCollection.\r
1217       /// </summary>\r
1218       /// <returns></returns>\r
1219       public virtual object Clone()\r
1220       {\r
1221         //\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
1225         {\r
1226           sortedpairsclone.Add(new KeyValuePair<K, V>(key, default(V)));\r
1227         }\r
1228         return new SortedKeysCollection(dictclone, sortedpairsclone, comparer, EqualityComparer);\r
1229       }\r
1230 \r
1231       #endregion\r
1232 \r
1233     }\r
1234 \r
1235     /// <summary>\r
1236     /// \r
1237     /// </summary>\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
1243     {\r
1244       return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);\r
1245     }\r
1246 \r
1247   }\r
1248 \r
1249   class SortedArrayDictionary<K, V> : SortedDictionaryBase<K, V>, IDictionary<K, V>, ISortedDictionary<K, V>\r
1250   {\r
1251     #region Constructors\r
1252 \r
1253     public SortedArrayDictionary() : this(Comparer<K>.Default, EqualityComparer<K>.Default) { }\r
1254 \r
1255     /// <summary>\r
1256     /// Create a red-black tree dictionary using an external comparer for keys.\r
1257     /// </summary>\r
1258     /// <param name="comparer">The external comparer</param>\r
1259     public SortedArrayDictionary(SCG.IComparer<K> comparer) : this(comparer, new ComparerZeroHashCodeEqualityComparer<K>(comparer)) { }\r
1260 \r
1261     /// <summary>\r
1262     /// \r
1263     /// </summary>\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
1267     {\r
1268       pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(new KeyValuePairComparer<K, V>(comparer));\r
1269     }\r
1270 \r
1271     /// <summary>\r
1272     /// \r
1273     /// </summary>\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
1278     {\r
1279       pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(capacity, new KeyValuePairComparer<K, V>(comparer));\r
1280     }\r
1281     #endregion\r
1282 \r
1283     /// <summary>\r
1284     /// \r
1285     /// </summary>\r
1286     /// <returns></returns>\r
1287     public override object Clone()\r
1288     {\r
1289       SortedArrayDictionary<K, V> clone = new SortedArrayDictionary<K, V>(Comparer, EqualityComparer);\r
1290       clone.sortedpairs.AddSorted(sortedpairs);\r
1291       return clone;\r
1292     }\r
1293 \r
1294   }\r
1295 }