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

   1 #if NET_2_0\r
   2 /*\r
   3  Copyright (c) 2003-2004 Niels Kokholm <kokholm@itu.dk> and Peter Sestoft <sestoft@dina.kvl.dk>\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 MSG = 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         public struct KeyValuePair<K,V>\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 \r
  44                 /// <summary>\r
  45                 /// Create an entry with specified key and value\r
  46                 /// </summary>\r
  47                 /// <param name="k">The key</param>\r
  48                 /// <param name="v">The value</param>\r
  49                 public KeyValuePair(K k, V v) { key = k; value = v; }\r
  50 \r
  51 \r
  52                 /// <summary>\r
  53                 /// Create an entry with a specified key. The value is undefined.\r
  54                 /// </summary>\r
  55                 /// <param name="k">The key</param>\r
  56                 public KeyValuePair(K k) { key = k; 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</returns>\r
  72                 [Tested]\r
  73                 public override bool Equals(object obj)\r
  74                 { return obj is KeyValuePair<K,V> && key.Equals(((KeyValuePair<K,V>)obj).key); }\r
  75 \r
  76 \r
  77                 /// <summary>\r
  78                 /// Get the hash code of the key.\r
  79                 /// </summary>\r
  80                 /// <returns>The hash code</returns>\r
  81                 [Tested]\r
  82                 public override int GetHashCode() { return key.GetHashCode(); }\r
  83         }\r
  84 \r
  85 \r
  86 \r
  87         /// <summary>\r
  88         /// Default comparer for dictionary entries in a sorted dictionary.\r
  89         /// Entry comparisons only look at keys.\r
  90         /// </summary>\r
  91         public class KeyValuePairComparer<K,V>: IComparer<KeyValuePair<K,V>>\r
  92         {\r
  93                 IComparer<K> myc;\r
  94 \r
  95 \r
  96                 /// <summary>\r
  97                 /// Create an entry comparer for a item comparer of the keys\r
  98                 /// </summary>\r
  99                 /// <param name="c">Comparer of keys</param>\r
 100                 public KeyValuePairComparer(IComparer<K> c) { myc = c; }\r
 101 \r
 102 \r
 103                 /// <summary>\r
 104                 /// Compare two entries\r
 105                 /// </summary>\r
 106                 /// <param name="a">First entry</param>\r
 107                 /// <param name="b">Second entry</param>\r
 108                 /// <returns>The result of comparing the keys</returns>\r
 109                 [Tested]\r
 110                 public int Compare(KeyValuePair<K,V> a, KeyValuePair<K,V> b)\r
 111                 { return myc.Compare(a.key, b.key); }\r
 112         }\r
 113 \r
 114 \r
 115 \r
 116         /// <summary>\r
 117         /// Default hasher for dictionary entries.\r
 118         /// Operations only look at keys.\r
 119         /// </summary>\r
 120         public sealed class KeyValuePairHasher<K,V>: IHasher<KeyValuePair<K,V>>\r
 121         {\r
 122                 IHasher<K> myh;\r
 123 \r
 124 \r
 125                 /// <summary>\r
 126                 /// Create an entry hasher using the default hasher for keys\r
 127                 /// </summary>\r
 128                 public KeyValuePairHasher() { myh = HasherBuilder.ByPrototype<K>.Examine(); }\r
 129 \r
 130 \r
 131                 /// <summary>\r
 132                 /// Create an entry hasher from a specified item hasher for the keys\r
 133                 /// </summary>\r
 134                 /// <param name="c">The key hasher</param>\r
 135                 public KeyValuePairHasher(IHasher<K> c) { myh = c; }\r
 136 \r
 137 \r
 138                 /// <summary>\r
 139                 /// Get the hash code of the entry\r
 140                 /// </summary>\r
 141                 /// <param name="item">The entry</param>\r
 142                 /// <returns>The hash code of the key</returns>\r
 143                 [Tested]\r
 144                 public int GetHashCode(KeyValuePair<K,V> item) { return myh.GetHashCode(item.key); }\r
 145 \r
 146 \r
 147                 /// <summary>\r
 148                 /// Test two entries for equality\r
 149                 /// </summary>\r
 150                 /// <param name="i1">First entry</param>\r
 151                 /// <param name="i2">Second entry</param>\r
 152                 /// <returns>True if keys are equal</returns>\r
 153                 [Tested]\r
 154                 public bool Equals(KeyValuePair<K,V> i1, KeyValuePair<K,V> i2)\r
 155                 { return myh.Equals(i1.key, i2.key); }\r
 156         }\r
 157 \r
 158 \r
 159 \r
 160         /// <summary>\r
 161         /// A base class for implementing a dictionary based on a set collection implementation.\r
 162         /// <p>See the source code for <see cref="T:C5.HashDictionary!2"/> for an example</p>\r
 163         /// \r
 164         /// </summary>\r
 165         public abstract class DictionaryBase<K,V>: EnumerableBase<KeyValuePair<K,V>>, IDictionary<K,V>\r
 166         {\r
 167                 /// <summary>\r
 168                 /// The set collection of entries underlying this dictionary implementation\r
 169                 /// </summary>\r
 170                 protected ICollection<KeyValuePair<K,V>> pairs;\r
 171 \r
 172 \r
 173                 #region IDictionary<K,V> Members\r
 174 \r
 175                 /// <summary>\r
 176                 /// \r
 177                 /// </summary>\r
 178                 /// <value>The number of entrues in the dictionary</value>\r
 179                 [Tested]\r
 180                 public int Count { [Tested]get { return pairs.Count; } }\r
 181 \r
 182 \r
 183                 /// <summary>\r
 184                 /// \r
 185                 /// </summary>\r
 186                 /// <value>A distinguished object to use for locking to synchronize multithreaded access</value>\r
 187                 [Tested]\r
 188                 public object SyncRoot { [Tested]get { return pairs.SyncRoot; } }\r
 189 \r
 190 \r
 191                 /// <summary>\r
 192                 /// Add a new (key, value) pair (a mapping) to the dictionary.\r
 193                 /// <exception cref="InvalidOperationException"/> if there already is an entry with the same key. \r
 194                 /// </summary>\r
 195                 /// <param name="key">Key to add</param>\r
 196                 /// <param name="val">Value to add</param>\r
 197                 [Tested]\r
 198                 public void Add(K key, V val)\r
 199                 {\r
 200                         KeyValuePair<K,V> p = new KeyValuePair<K,V>(key, val);\r
 201 \r
 202                         if (!pairs.Add(p))\r
 203                                 throw new System.ArgumentException("Item has already been added.  Key in dictionary: '" + key + "'  Key being added: '" + key + "'");\r
 204                 }\r
 205 \r
 206 \r
 207                 /// <summary>\r
 208                 /// Remove an entry with a given key from the dictionary\r
 209                 /// </summary>\r
 210                 /// <param name="key">The key of the entry to remove</param>\r
 211                 /// <returns>True if an entry was found (and removed)</returns>\r
 212                 [Tested]\r
 213                 public bool Remove(K key)\r
 214                 {\r
 215                         KeyValuePair<K,V> p = new KeyValuePair<K,V>(key);\r
 216 \r
 217                         return pairs.Remove(p);\r
 218                 }\r
 219 \r
 220 \r
 221                 /// <summary>\r
 222                 /// Remove an entry with a given key from the dictionary and report its value.\r
 223                 /// </summary>\r
 224                 /// <param name="key">The key of the entry to remove</param>\r
 225                 /// <param name="val">On exit, the value of the removed entry</param>\r
 226                 /// <returns>True if an entry was found (and removed)</returns>\r
 227                 [Tested]\r
 228                 public bool Remove(K key, out V val)\r
 229                 {\r
 230                         KeyValuePair<K,V> p = new KeyValuePair<K,V>(key);\r
 231 \r
 232                         if (pairs.RemoveWithReturn(ref p))\r
 233                         {\r
 234                                 val = p.value;\r
 235                                 return true;\r
 236                         }\r
 237                         else\r
 238                         {\r
 239                                 val = default(V);\r
 240                                 return false;\r
 241                         }\r
 242                 }\r
 243 \r
 244 \r
 245                 /// <summary>\r
 246                 /// Remove all entries from the dictionary\r
 247                 /// </summary>\r
 248                 [Tested]\r
 249                 public void Clear() { pairs.Clear(); }\r
 250 \r
 251 \r
 252                 /// <summary>\r
 253                 /// Check if there is an entry with a specified key\r
 254                 /// </summary>\r
 255                 /// <param name="key">The key to look for</param>\r
 256                 /// <returns>True if key was found</returns>\r
 257                 [Tested]\r
 258                 public bool Contains(K key)\r
 259                 {\r
 260                         KeyValuePair<K,V> p = new KeyValuePair<K,V>(key);\r
 261 \r
 262                         return pairs.Contains(p);\r
 263                 }\r
 264 \r
 265 \r
 266                 /// <summary>\r
 267                 /// Check if there is an entry with a specified key and report the corresponding\r
 268                 /// value if found. This can be seen as a safe form of "val = this[key]".\r
 269                 /// </summary>\r
 270                 /// <param name="key">The key to look for</param>\r
 271                 /// <param name="val">On exit, the value of the entry</param>\r
 272                 /// <returns>True if key was found</returns>\r
 273                 [Tested]\r
 274                 public bool Find(K key, out V val)\r
 275                 {\r
 276                         KeyValuePair<K,V> p = new KeyValuePair<K,V>(key);\r
 277 \r
 278                         if (pairs.Find(ref p))\r
 279                         {\r
 280                                 val = p.value;\r
 281                                 return true;\r
 282                         }\r
 283                         else\r
 284                         {\r
 285                                 val = default(V);\r
 286                                 return false;\r
 287                         }\r
 288                 }\r
 289 \r
 290 \r
 291                 /// <summary>\r
 292                 /// Look for a specific key in the dictionary and if found replace the value with a new one.\r
 293                 /// This can be seen as a non-adding version of "this[key] = val".\r
 294                 /// </summary>\r
 295                 /// <param name="key">The key to look for</param>\r
 296                 /// <param name="val">The new value</param>\r
 297                 /// <returns>True if key was found</returns>\r
 298                 [Tested]\r
 299                 public bool Update(K key, V val)\r
 300                 {\r
 301                         KeyValuePair<K,V> p = new KeyValuePair<K,V>(key, val);\r
 302 \r
 303                         return pairs.Update(p);\r
 304                 }\r
 305 \r
 306 \r
 307                 /// <summary>\r
 308                 /// Look for a specific key in the dictionary. If found, report the corresponding value,\r
 309                 /// else add an entry with the key and the supplied value.\r
 310                 /// </summary>\r
 311                 /// <param name="key">The key to look for</param>\r
 312                 /// <param name="val">On entry the value to add if the key is not found.\r
 313                 /// On exit the value found if any.</param>\r
 314                 /// <returns>True if key was found</returns>\r
 315                 [Tested]\r
 316                 public bool FindOrAdd(K key, ref V val)\r
 317                 {\r
 318                         KeyValuePair<K,V> p = new KeyValuePair<K,V>(key, val);\r
 319 \r
 320                         if (!pairs.FindOrAdd(ref p))\r
 321                                 return false;\r
 322                         else\r
 323                         {\r
 324                                 val = p.value;\r
 325                                 return true;\r
 326                         }\r
 327                 }\r
 328 \r
 329 \r
 330                 /// <summary>\r
 331                 /// Update value in dictionary corresponding to key if found, else add new entry.\r
 332                 /// More general than "this[key] = val;" by reporting if key was found.\r
 333                 /// </summary>\r
 334                 /// <param name="key">The key to look for</param>\r
 335                 /// <param name="val">The value to add or replace with.</param>\r
 336                 /// <returns>True if entry was updated.</returns>\r
 337                 [Tested]\r
 338                 public bool UpdateOrAdd(K key, V val)\r
 339                 {\r
 340                         return pairs.UpdateOrAdd(new KeyValuePair<K,V>(key, val));\r
 341                 }\r
 342 \r
 343 \r
 344 \r
 345                 #region Keys,Values support classes\r
 346                         \r
 347                 internal class ValuesCollection: CollectionValueBase<V>, ICollectionValue<V>\r
 348                 {\r
 349                         ICollection<KeyValuePair<K,V>> pairs;\r
 350 \r
 351 \r
 352                         internal ValuesCollection(ICollection<KeyValuePair<K,V>> pairs)\r
 353                         { this.pairs = pairs; }\r
 354 \r
 355 \r
 356                         [Tested]\r
 357                         public override MSG.IEnumerator<V> GetEnumerator()\r
 358                         {\r
 359                                 //Updatecheck is performed by the pairs enumerator\r
 360                                 foreach (KeyValuePair<K,V> p in pairs)\r
 361                                         yield return p.value;\r
 362                         }\r
 363 \r
 364 \r
 365                         [Tested]\r
 366             public override int Count { [Tested]get { return pairs.Count; } }\r
 367 \r
 368             public override Speed CountSpeed { get { return Speed.Constant; } }\r
 369         }\r
 370 \r
 371 \r
 372 \r
 373         internal class KeysCollection: CollectionValueBase<K>, ICollectionValue<K>\r
 374                 {\r
 375                         ICollection<KeyValuePair<K,V>> pairs;\r
 376 \r
 377 \r
 378                         internal KeysCollection(ICollection<KeyValuePair<K,V>> pairs)\r
 379                         { this.pairs = pairs; }\r
 380 \r
 381 \r
 382                         [Tested]\r
 383                         public override MSG.IEnumerator<K> GetEnumerator()\r
 384                         {\r
 385                                 foreach (KeyValuePair<K,V> p in pairs)\r
 386                                         yield return p.key;\r
 387                         }\r
 388 \r
 389 \r
 390                         [Tested]\r
 391                         public override int Count { [Tested]get { return pairs.Count; } }\r
 392 \r
 393             public override Speed CountSpeed { get { return pairs.CountSpeed; } }\r
 394         }\r
 395                 #endregion\r
 396 \r
 397                 /// <summary>\r
 398                 /// \r
 399                 /// </summary>\r
 400                 /// <value>A collection containg the all the keys of the dictionary</value>\r
 401                 [Tested]\r
 402                 public ICollectionValue<K> Keys { [Tested]get { return new KeysCollection(pairs); } }\r
 403 \r
 404 \r
 405                 /// <summary>\r
 406                 /// \r
 407                 /// </summary>\r
 408                 /// <value>A collection containing all the values of the dictionary</value>\r
 409                 [Tested]\r
 410                 public ICollectionValue<V> Values { [Tested]get { return new ValuesCollection(pairs); } }\r
 411 \r
 412 \r
 413                 /// <summary>\r
 414                 /// Indexer for dictionary.\r
 415                 /// <exception cref="InvalidOperationException"/> if no entry is found. \r
 416                 /// </summary>\r
 417                 /// <value>The value corresponding to the key</value>\r
 418                 [Tested]\r
 419                 public V this[K key]\r
 420                 {\r
 421                         [Tested]\r
 422                         get\r
 423                         {\r
 424                                 KeyValuePair<K,V> p = new KeyValuePair<K,V>(key);\r
 425 \r
 426                                 if (pairs.Find(ref p))\r
 427                                         return p.value;\r
 428                                 else\r
 429                                         throw new System.ArgumentException("Key not present in Dictionary");\r
 430                         }\r
 431                         [Tested]\r
 432                         set\r
 433                         { pairs.UpdateOrAdd(new KeyValuePair<K,V>(key, value)); }\r
 434                 }\r
 435 \r
 436 \r
 437                 /// <summary>\r
 438                 /// \r
 439                 /// </summary>\r
 440                 /// <value>True if dictionary is read  only</value>\r
 441                 [Tested]\r
 442                 public bool IsReadOnly { [Tested]get { return pairs.IsReadOnly; } }\r
 443 \r
 444 \r
 445                 /// <summary>\r
 446                 /// Check the integrity of the internal data structures of this dictionary.\r
 447                 /// Only avaliable in DEBUG builds???\r
 448                 /// </summary>\r
 449                 /// <returns>True if check does not fail.</returns>\r
 450                 [Tested]\r
 451                 public bool Check() { return pairs.Check(); }\r
 452 \r
 453                 #endregion\r
 454 \r
 455                 #region IEnumerable<KeyValuePair<K,V>> Members\r
 456 \r
 457 \r
 458                 /// <summary>\r
 459                 /// Create an enumerator for the collection of entries of the dictionary\r
 460                 /// </summary>\r
 461                 /// <returns>The enumerator</returns>\r
 462                 [Tested]\r
 463                 public override MSG.IEnumerator<KeyValuePair<K,V>> GetEnumerator()\r
 464                 {\r
 465                         return pairs.GetEnumerator();;\r
 466                 }\r
 467 \r
 468                 #endregion\r
 469         }\r
 470 }\r
 471 #endif\r