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

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