mcs/class/System/System.Collections.Generic/SortedDictionary.cs

   1 //
   2 // System.Collections.Generic.SortedDictionary
   3 //
   4 // Author:
   5 //    Raja R Harinath <rharinath@novell.com>
   6 //
   7 // Authors of previous (superseded) version:
   8 //    Kazuki Oikawa (kazuki@panicode.com)
   9 //    Atsushi Enomoto (atsushi@ximian.com)
  10 //
  11
  12 //
  13 // Copyright (C) 2007, Novell, Inc.
  14 //
  15 // Permission is hereby granted, free of charge, to any person obtaining
  16 // a copy of this software and associated documentation files (the
  17 // "Software"), to deal in the Software without restriction, including
  18 // without limitation the rights to use, copy, modify, merge, publish,
  19 // distribute, sublicense, and/or sell copies of the Software, and to
  20 // permit persons to whom the Software is furnished to do so, subject to
  21 // the following conditions:
  22 //
  23 // The above copyright notice and this permission notice shall be
  24 // included in all copies or substantial portions of the Software.
  25 //
  26 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  27 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  28 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  29 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  30 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  31 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  32 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  33 //
  34
  35 #if NET_2_0
  36 using System;
  37 using System.Collections;
  38
  39 namespace System.Collections.Generic
  40 {
  41         [Serializable]
  42         public class SortedDictionary<TKey,TValue> : IDictionary<TKey,TValue>, ICollection<KeyValuePair<TKey,TValue>>, IEnumerable<KeyValuePair<TKey,TValue>>, IDictionary, ICollection, IEnumerable
  43         {
  44                 class Node : RBTree.Node {
  45                         public TKey key;
  46                         public TValue value;
  47
  48                         public Node (TKey key)
  49                         {
  50                                 this.key = key;
  51                         }
  52
  53                         public Node (TKey key, TValue value)
  54                         {
  55                                 this.key = key;
  56                                 this.value = value;
  57                         }
  58
  59                         public override void SwapValue (RBTree.Node other)
  60                         {
  61                                 Node o = (Node) other;
  62                                 TKey k = key; key = o.key; o.key = k;
  63                                 TValue v = value; value = o.value; o.value = v;
  64                         }
  65
  66                         public KeyValuePair<TKey, TValue> AsKV ()
  67                         {
  68                                 return new KeyValuePair<TKey, TValue> (key, value);
  69                         }
  70
  71                         public DictionaryEntry AsDE ()
  72                         {
  73                                 return new DictionaryEntry (key, value);
  74                         }
  75                 }
  76
  77                 class NodeHelper : RBTree.INodeHelper<TKey> {
  78                         public IComparer<TKey> cmp;
  79
  80                         public int Compare (TKey key, RBTree.Node node)
  81                         {
  82                                 return cmp.Compare (key, ((Node) node).key);
  83                         }
  84
  85                         public RBTree.Node CreateNode (TKey key)
  86                         {
  87                                 return new Node (key);
  88                         }
  89
  90                         private NodeHelper (IComparer<TKey> cmp)
  91                         {
  92                                 this.cmp = cmp;
  93                         }
  94                         static NodeHelper Default = new NodeHelper (Comparer<TKey>.Default);
  95                         public static NodeHelper GetHelper (IComparer<TKey> cmp)
  96                         {
  97                                 if (cmp == null || cmp == Comparer<TKey>.Default)
  98                                         return Default;
  99                                 return new NodeHelper (cmp);
 100                         }
 101                 }
 102
 103                 RBTree tree;
 104                 NodeHelper hlp;
 105
 106                 #region Constructor
 107                 public SortedDictionary () : this ((IComparer<TKey>) null)
 108                 {
 109                 }
 110
 111                 public SortedDictionary (IComparer<TKey> comparer)
 112                 {
 113                         hlp = NodeHelper.GetHelper (comparer);
 114                         tree = new RBTree (hlp);
 115                 }
 116
 117                 public SortedDictionary (IDictionary<TKey,TValue> dic) : this (dic, null)
 118                 {
 119                 }
 120
 121                 public SortedDictionary (IDictionary<TKey,TValue> dic, IComparer<TKey> comparer) : this (comparer)
 122                 {
 123                         if (dic == null)
 124                                 throw new ArgumentNullException ();
 125                         foreach (KeyValuePair<TKey, TValue> entry in dic)
 126                                 Add (entry.Key, entry.Value);
 127                 }
 128                 #endregion
 129
 130                 #region PublicProperty
 131
 132                 public IComparer<TKey> Comparer {
 133                         get { return hlp.cmp; }
 134                 }
 135
 136                 public int Count {
 137                         get { return (int) tree.Count; }
 138                 }
 139
 140                 public TValue this [TKey key] {
 141                         get {
 142                                 Node n = (Node) tree.Lookup (key);
 143                                 if (n == null)
 144                                         throw new KeyNotFoundException ();
 145                                 return n.value;
 146                         }
 147                         set {
 148                                 if (key == null)
 149                                         throw new ArgumentNullException ("key");
 150                                 Node n = (Node) tree.Intern (key, null);
 151                                 n.value = value;
 152                         }
 153                 }
 154
 155                 public KeyCollection Keys {
 156                         get { return new KeyCollection (this); }
 157                 }
 158
 159                 public ValueCollection Values {
 160                         get { return new ValueCollection (this); }
 161                 }
 162                 #endregion
 163
 164                 #region PublicMethod
 165
 166                 public void Add (TKey key, TValue value)
 167                 {
 168                         if (key == null)
 169                                 throw new ArgumentNullException ("key");
 170
 171                         RBTree.Node n = new Node (key, value);
 172                         if (tree.Intern (key, n) != n)
 173                                 throw new ArgumentException ("key already present in dictionary", "key");
 174                 }
 175
 176                 public void Clear ()
 177                 {
 178                         tree.Clear ();
 179                 }
 180
 181                 public bool ContainsKey (TKey key)
 182                 {
 183                         return tree.Lookup (key) != null;
 184                 }
 185
 186                 public bool ContainsValue (TValue value)
 187                 {
 188                         IEqualityComparer<TValue> vcmp = EqualityComparer<TValue>.Default;
 189                         foreach (Node n in tree)
 190                                 if (vcmp.Equals (value, n.value))
 191                                         return true;
 192                         return false;
 193                 }
 194
 195                 public void CopyTo (KeyValuePair<TKey,TValue>[] array, int arrayIndex)
 196                 {
 197                         if (array == null)
 198                                 throw new ArgumentNullException ();
 199                         if (arrayIndex < 0 || array.Length <= arrayIndex)
 200                                 throw new ArgumentOutOfRangeException ();
 201                         if (array.Length - arrayIndex < Count)
 202                                 throw new ArgumentException ();
 203
 204                         foreach (Node n in tree)
 205                                 array [arrayIndex ++] = n.AsKV ();
 206                 }
 207
 208                 public Enumerator GetEnumerator ()
 209                 {
 210                         return new Enumerator (this);
 211                 }
 212
 213                 public bool Remove (TKey key)
 214                 {
 215                         return tree.Remove (key) != null;
 216                 }
 217
 218                 public bool TryGetValue (TKey key, out TValue value)
 219                 {
 220                         Node n = (Node) tree.Lookup (key);
 221                         value = n == null ? default (TValue) : n.value;
 222                         return n != null;
 223                 }
 224
 225                 #endregion
 226
 227                 #region PrivateMethod
 228                 TKey ToKey (object key)
 229                 {
 230                         if (key == null)
 231                                 throw new ArgumentNullException ("key");
 232                         if (!(key is TKey))
 233                                 throw new ArgumentException (String.Format ("Key \"{0}\" cannot be converted to the key type {1}.", key, typeof (TKey)));
 234                         return (TKey) key;
 235                 }
 236
 237                 TValue ToValue (object value)
 238                 {
 239                         if (!(value is TValue) && (value != null || typeof (TValue).IsValueType))
 240                                 throw new ArgumentException (String.Format ("Value \"{0}\" cannot be converted to the value type {1}.", value, typeof (TValue)));
 241                         return (TValue) value;
 242                 }
 243                 #endregion
 244
 245                 #region IDictionary<TKey,TValue> Member
 246
 247                 ICollection<TKey> IDictionary<TKey,TValue>.Keys {
 248                         get { return new KeyCollection (this); }
 249                 }
 250
 251                 ICollection<TValue> IDictionary<TKey,TValue>.Values {
 252                         get { return new ValueCollection (this); }
 253                 }
 254
 255                 #endregion
 256
 257                 #region ICollection<KeyValuePair<TKey,TValue>> Member
 258
 259                 void ICollection<KeyValuePair<TKey,TValue>>.Add (KeyValuePair<TKey,TValue> item)
 260                 {
 261                         Add (item.Key, item.Value);
 262                 }
 263
 264                 bool ICollection<KeyValuePair<TKey,TValue>>.Contains (KeyValuePair<TKey,TValue> item)
 265                 {
 266                         TValue value;
 267                         return TryGetValue (item.Key, out value) &&
 268                                 EqualityComparer<TValue>.Default.Equals (item.Value, value);
 269                 }
 270
 271                 bool ICollection<KeyValuePair<TKey,TValue>>.IsReadOnly {
 272                         get { return false; }
 273                 }
 274
 275                 bool ICollection<KeyValuePair<TKey,TValue>>.Remove (KeyValuePair<TKey,TValue> item)
 276                 {
 277                         TValue value;
 278                         return TryGetValue (item.Key, out value) &&
 279                                 EqualityComparer<TValue>.Default.Equals (item.Value, value) &&
 280                                 Remove (item.Key);
 281                 }
 282
 283                 #endregion
 284
 285                 #region IDictionary Member
 286
 287                 void IDictionary.Add (object key, object value)
 288                 {
 289                         Add (ToKey (key), ToValue (value));
 290                 }
 291
 292                 bool IDictionary.Contains (object key)
 293                 {
 294                         return ContainsKey (ToKey (key));
 295                 }
 296
 297                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 298                 {
 299                         return new Enumerator (this);
 300                 }
 301
 302                 bool IDictionary.IsFixedSize {
 303                         get { return false; }
 304                 }
 305
 306                 bool IDictionary.IsReadOnly {
 307                         get { return false; }
 308                 }
 309
 310                 ICollection IDictionary.Keys  {
 311                         get { return new KeyCollection (this); }
 312                 }
 313
 314                 void IDictionary.Remove (object key)
 315                 {
 316                         Remove (ToKey (key));
 317                 }
 318
 319                 ICollection IDictionary.Values {
 320                         get { return new ValueCollection (this); }
 321                 }
 322
 323                 object IDictionary.this [object key] {
 324                         get { return this [ToKey (key)]; }
 325                         set { this [ToKey (key)] = ToValue (value); }
 326                 }
 327
 328                 #endregion
 329
 330                 #region ICollection Member
 331
 332                 void ICollection.CopyTo (Array array, int index)
 333                 {
 334                         if (array == null)
 335                                 throw new ArgumentNullException ();
 336                         if (index < 0 || array.Length <= index)
 337                                 throw new ArgumentOutOfRangeException ();
 338                         if (array.Length - index < Count)
 339                                 throw new ArgumentException ();
 340
 341                         foreach (Node n in tree)
 342                                 array.SetValue (n.AsDE (), index++);
 343                 }
 344
 345                 bool ICollection.IsSynchronized {
 346                         get { return false; }
 347                 }
 348
 349                 // TODO:Is this correct? If this is wrong,please fix.
 350                 object ICollection.SyncRoot {
 351                         get { return this; }
 352                 }
 353
 354                 #endregion
 355
 356                 #region IEnumerable Member
 357
 358                 IEnumerator IEnumerable.GetEnumerator ()
 359                 {
 360                         return new Enumerator (this);
 361                 }
 362
 363                 #endregion
 364
 365                 #region IEnumerable<TKey> Member
 366
 367                 IEnumerator<KeyValuePair<TKey,TValue>> IEnumerable<KeyValuePair<TKey,TValue>>.GetEnumerator ()
 368                 {
 369                         return new Enumerator (this);
 370                 }
 371
 372                 #endregion
 373
 374                 [Serializable]
 375                 public sealed class ValueCollection : ICollection<TValue>,
 376                         IEnumerable<TValue>, ICollection, IEnumerable
 377                 {
 378                         SortedDictionary<TKey,TValue> _dic;
 379
 380                         public ValueCollection (SortedDictionary<TKey,TValue> dic)
 381                         {
 382                                 _dic = dic;
 383                         }
 384
 385                         void ICollection<TValue>.Add (TValue item)
 386                         {
 387                                 throw new NotSupportedException ();
 388                         }
 389
 390                         void ICollection<TValue>.Clear ()
 391                         {
 392                                 throw new NotSupportedException ();
 393                         }
 394
 395                         bool ICollection<TValue>.Contains (TValue item)
 396                         {
 397                                 return _dic.ContainsValue (item);
 398                         }
 399
 400                         public void CopyTo (TValue [] array, int arrayIndex)
 401                         {
 402                                 if (array == null)
 403                                         throw new ArgumentNullException ();
 404                                 if (arrayIndex < 0 || array.Length <= arrayIndex)
 405                                         throw new ArgumentOutOfRangeException ();
 406                                 if (array.Length - arrayIndex < Count)
 407                                         throw new ArgumentException ();
 408                                 foreach (Node n in _dic.tree)
 409                                         array [arrayIndex++] = n.value;
 410                         }
 411
 412                         public int Count {
 413                                 get { return _dic.Count; }
 414                         }
 415
 416                         bool ICollection<TValue>.IsReadOnly {
 417                                 get { return true; }
 418                         }
 419
 420                         bool ICollection<TValue>.Remove (TValue item)
 421                         {
 422                                 throw new NotSupportedException ();
 423                         }
 424
 425                         IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator ()
 426                         {
 427                                 return GetEnumerator ();
 428                         }
 429
 430                         public Enumerator GetEnumerator ()
 431                         {
 432                                 return new Enumerator (_dic);
 433                         }
 434
 435                         void ICollection.CopyTo (Array array, int index)
 436                         {
 437                                 if (array == null)
 438                                         throw new ArgumentNullException ();
 439                                 if (index < 0 || array.Length <= index)
 440                                         throw new ArgumentOutOfRangeException ();
 441                                 if (array.Length - index < Count)
 442                                         throw new ArgumentException ();
 443                                 foreach (Node n in _dic.tree)
 444                                         array.SetValue (n.value, index++);
 445                         }
 446
 447                         bool ICollection.IsSynchronized {
 448                                 get { return false; }
 449                         }
 450
 451                         object ICollection.SyncRoot {
 452                                 get { return _dic; }
 453                         }
 454
 455                         IEnumerator IEnumerable.GetEnumerator ()
 456                         {
 457                                 return new Enumerator (_dic);
 458                         }
 459
 460                         public struct Enumerator : IEnumerator<TValue>,IEnumerator, IDisposable
 461                         {
 462                                 RBTree.NodeEnumerator host;
 463
 464                                 internal Enumerator (SortedDictionary<TKey,TValue> dic)
 465                                 {
 466                                         host = dic.tree.GetEnumerator ();
 467                                 }
 468
 469                                 public TValue Current {
 470                                         get { return ((Node) host.Current).value; }
 471                                 }
 472
 473                                 public bool MoveNext ()
 474                                 {
 475                                         return host.MoveNext ();
 476                                 }
 477
 478                                 public void Dispose ()
 479                                 {
 480                                         host.Dispose ();
 481                                 }
 482
 483                                 object IEnumerator.Current {
 484                                         get { return Current; }
 485                                 }
 486
 487                                 void IEnumerator.Reset ()
 488                                 {
 489                                         host.Reset ();
 490                                 }
 491                         }
 492                 }
 493
 494                 [Serializable]
 495                 public sealed class KeyCollection : ICollection<TKey>,
 496                         IEnumerable<TKey>, ICollection, IEnumerable
 497                 {
 498                         SortedDictionary<TKey,TValue> _dic;
 499
 500                         public KeyCollection (SortedDictionary<TKey,TValue> dic)
 501                         {
 502                                 _dic = dic;
 503                         }
 504
 505                         void ICollection<TKey>.Add (TKey item)
 506                         {
 507                                 throw new NotSupportedException ();
 508                         }
 509
 510                         void ICollection<TKey>.Clear ()
 511                         {
 512                                 throw new NotSupportedException ();
 513                         }
 514
 515                         bool ICollection<TKey>.Contains (TKey item)
 516                         {
 517                                 return _dic.ContainsKey (item);
 518                         }
 519
 520                         IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator ()
 521                         {
 522                                 return GetEnumerator ();
 523                         }
 524
 525                         public void CopyTo (TKey [] array, int arrayIndex)
 526                         {
 527                                 if (array == null)
 528                                         throw new ArgumentNullException ();
 529                                 if (arrayIndex < 0 || array.Length <= arrayIndex)
 530                                         throw new ArgumentOutOfRangeException ();
 531                                 if (array.Length - arrayIndex < Count)
 532                                         throw new ArgumentException ();
 533                                 foreach (Node n in _dic.tree)
 534                                         array [arrayIndex++] = n.key;
 535                         }
 536
 537                         public int Count {
 538                                 get { return _dic.Count; }
 539                         }
 540
 541                         bool ICollection<TKey>.IsReadOnly {
 542                                 get { return true; }
 543                         }
 544
 545                         bool ICollection<TKey>.Remove (TKey item)
 546                         {
 547                                 throw new NotSupportedException ();
 548                         }
 549
 550                         public Enumerator GetEnumerator ()
 551                         {
 552                                 return new Enumerator (_dic);
 553                         }
 554
 555                         void ICollection.CopyTo (Array array, int index)
 556                         {
 557                                 if (array == null)
 558                                         throw new ArgumentNullException ();
 559                                 if (index < 0 || array.Length <= index)
 560                                         throw new ArgumentOutOfRangeException ();
 561                                 if (array.Length - index < Count)
 562                                         throw new ArgumentException ();
 563                                 foreach (Node n in _dic.tree)
 564                                         array.SetValue (n.key, index++);
 565                         }
 566
 567                         bool ICollection.IsSynchronized {
 568                                 get { return false; }
 569                         }
 570
 571                         object ICollection.SyncRoot {
 572                                 get { return _dic; }
 573                         }
 574
 575                         IEnumerator IEnumerable.GetEnumerator ()
 576                         {
 577                                 return new Enumerator (_dic);
 578                         }
 579
 580                         public struct Enumerator : IEnumerator<TKey>, IEnumerator, IDisposable
 581                         {
 582                                 RBTree.NodeEnumerator host;
 583
 584                                 internal Enumerator (SortedDictionary<TKey,TValue> dic)
 585                                 {
 586                                         host = dic.tree.GetEnumerator ();
 587                                 }
 588
 589                                 public TKey Current {
 590                                         get { return ((Node) host.Current).key; }
 591                                 }
 592
 593                                 public bool MoveNext ()
 594                                 {
 595                                         return host.MoveNext ();
 596                                 }
 597
 598                                 public void Dispose ()
 599                                 {
 600                                         host.Dispose ();
 601                                 }
 602
 603                                 object IEnumerator.Current {
 604                                         get { return Current; }
 605                                 }
 606
 607                                 void IEnumerator.Reset ()
 608                                 {
 609                                         host.Reset ();
 610                                 }
 611                         }
 612                 }
 613
 614                 public struct Enumerator : IEnumerator<KeyValuePair<TKey,TValue>>, IDisposable, IDictionaryEnumerator, IEnumerator
 615                 {
 616                         RBTree.NodeEnumerator host;
 617
 618                         internal Enumerator (SortedDictionary<TKey,TValue> dic)
 619                         {
 620                                 host = dic.tree.GetEnumerator ();
 621                         }
 622
 623                         public KeyValuePair<TKey,TValue> Current {
 624                                 get { return ((Node) host.Current).AsKV (); }
 625                         }
 626
 627                         public bool MoveNext ()
 628                         {
 629                                 return host.MoveNext ();
 630                         }
 631
 632                         public void Dispose ()
 633                         {
 634                                 host.Dispose ();
 635                         }
 636
 637                         DictionaryEntry IDictionaryEnumerator.Entry {
 638                                 get { return ((Node) host.Current).AsDE (); }
 639                         }
 640
 641                         object IDictionaryEnumerator.Key {
 642                                 get { return ((Node) host.Current).key; }
 643                         }
 644
 645                         object IDictionaryEnumerator.Value {
 646                                 get { return ((Node) host.Current).value; }
 647                         }
 648
 649                         object IEnumerator.Current {
 650                                 get { return ((Node) host.Current).AsDE (); }
 651                         }
 652
 653                         void IEnumerator.Reset ()
 654                         {
 655                                 host.Reset ();
 656                         }
 657                 }
 658         }
 659 }
 660 #endif