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 using System;
  36 using System.Collections;
  37 using System.Diagnostics;
  38
  39 namespace System.Collections.Generic
  40 {
  41         [Serializable]
  42         [DebuggerDisplay ("Count={Count}")]
  43         [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
  44         public class SortedDictionary<TKey,TValue> : IDictionary<TKey,TValue>, ICollection<KeyValuePair<TKey,TValue>>, IEnumerable<KeyValuePair<TKey,TValue>>, IDictionary, ICollection, IEnumerable
  45         {
  46                 class Node : RBTree.Node {
  47                         public TKey key;
  48                         public TValue value;
  49
  50                         public Node (TKey key)
  51                         {
  52                                 this.key = key;
  53                         }
  54
  55                         public Node (TKey key, TValue value)
  56                         {
  57                                 this.key = key;
  58                                 this.value = value;
  59                         }
  60
  61                         public override void SwapValue (RBTree.Node other)
  62                         {
  63                                 Node o = (Node) other;
  64                                 TKey k = key; key = o.key; o.key = k;
  65                                 TValue v = value; value = o.value; o.value = v;
  66                         }
  67
  68                         public KeyValuePair<TKey, TValue> AsKV ()
  69                         {
  70                                 return new KeyValuePair<TKey, TValue> (key, value);
  71                         }
  72
  73                         public DictionaryEntry AsDE ()
  74                         {
  75                                 return new DictionaryEntry (key, value);
  76                         }
  77                 }
  78
  79                 class NodeHelper : RBTree.INodeHelper<TKey> {
  80                         public IComparer<TKey> cmp;
  81
  82                         public int Compare (TKey key, RBTree.Node node)
  83                         {
  84                                 return cmp.Compare (key, ((Node) node).key);
  85                         }
  86
  87                         public RBTree.Node CreateNode (TKey key)
  88                         {
  89                                 return new Node (key);
  90                         }
  91
  92                         private NodeHelper (IComparer<TKey> cmp)
  93                         {
  94                                 this.cmp = cmp;
  95                         }
  96                         static NodeHelper Default = new NodeHelper (Comparer<TKey>.Default);
  97                         public static NodeHelper GetHelper (IComparer<TKey> cmp)
  98                         {
  99                                 if (cmp == null || cmp == Comparer<TKey>.Default)
 100                                         return Default;
 101                                 return new NodeHelper (cmp);
 102                         }
 103                 }
 104
 105                 RBTree tree;
 106                 NodeHelper hlp;
 107
 108                 #region Constructor
 109                 public SortedDictionary () : this ((IComparer<TKey>) null)
 110                 {
 111                 }
 112
 113                 public SortedDictionary (IComparer<TKey> comparer)
 114                 {
 115                         hlp = NodeHelper.GetHelper (comparer);
 116                         tree = new RBTree (hlp);
 117                 }
 118
 119                 public SortedDictionary (IDictionary<TKey,TValue> dic) : this (dic, null)
 120                 {
 121                 }
 122
 123                 public SortedDictionary (IDictionary<TKey,TValue> dic, IComparer<TKey> comparer) : this (comparer)
 124                 {
 125                         if (dic == null)
 126                                 throw new ArgumentNullException ();
 127                         foreach (KeyValuePair<TKey, TValue> entry in dic)
 128                                 Add (entry.Key, entry.Value);
 129                 }
 130                 #endregion
 131
 132                 #region PublicProperty
 133
 134                 public IComparer<TKey> Comparer {
 135                         get { return hlp.cmp; }
 136                 }
 137
 138                 public int Count {
 139                         get { return (int) tree.Count; }
 140                 }
 141
 142                 public TValue this [TKey key] {
 143                         get {
 144                                 Node n = (Node) tree.Lookup (key);
 145                                 if (n == null)
 146                                         throw new KeyNotFoundException ();
 147                                 return n.value;
 148                         }
 149                         set {
 150                                 if (key == null)
 151                                         throw new ArgumentNullException ("key");
 152                                 Node n = (Node) tree.Intern (key, null);
 153                                 n.value = value;
 154                         }
 155                 }
 156
 157                 public KeyCollection Keys {
 158                         get { return new KeyCollection (this); }
 159                 }
 160
 161                 public ValueCollection Values {
 162                         get { return new ValueCollection (this); }
 163                 }
 164                 #endregion
 165
 166                 #region PublicMethod
 167
 168                 public void Add (TKey key, TValue value)
 169                 {
 170                         if (key == null)
 171                                 throw new ArgumentNullException ("key");
 172
 173                         RBTree.Node n = new Node (key, value);
 174                         if (tree.Intern (key, n) != n)
 175                                 throw new ArgumentException ("key already present in dictionary", "key");
 176                 }
 177
 178                 public void Clear ()
 179                 {
 180                         tree.Clear ();
 181                 }
 182
 183                 public bool ContainsKey (TKey key)
 184                 {
 185                         return tree.Lookup (key) != null;
 186                 }
 187
 188                 public bool ContainsValue (TValue value)
 189                 {
 190                         IEqualityComparer<TValue> vcmp = EqualityComparer<TValue>.Default;
 191                         foreach (Node n in tree)
 192                                 if (vcmp.Equals (value, n.value))
 193                                         return true;
 194                         return false;
 195                 }
 196
 197                 public void CopyTo (KeyValuePair<TKey,TValue>[] array, int arrayIndex)
 198                 {
 199                         if (Count == 0)
 200                                 return;
 201                         if (array == null)
 202                                 throw new ArgumentNullException ();
 203                         if (arrayIndex < 0 || array.Length <= arrayIndex)
 204                                 throw new ArgumentOutOfRangeException ();
 205                         if (array.Length - arrayIndex < Count)
 206                                 throw new ArgumentException ();
 207
 208                         foreach (Node n in tree)
 209                                 array [arrayIndex ++] = n.AsKV ();
 210                 }
 211
 212                 public Enumerator GetEnumerator ()
 213                 {
 214                         return new Enumerator (this);
 215                 }
 216
 217                 public bool Remove (TKey key)
 218                 {
 219                         return tree.Remove (key) != null;
 220                 }
 221
 222                 public bool TryGetValue (TKey key, out TValue value)
 223                 {
 224                         Node n = (Node) tree.Lookup (key);
 225                         value = n == null ? default (TValue) : n.value;
 226                         return n != null;
 227                 }
 228
 229                 #endregion
 230
 231                 #region PrivateMethod
 232                 TKey ToKey (object key)
 233                 {
 234                         if (key == null)
 235                                 throw new ArgumentNullException ("key");
 236                         if (!(key is TKey))
 237                                 throw new ArgumentException (String.Format ("Key \"{0}\" cannot be converted to the key type {1}.", key, typeof (TKey)));
 238                         return (TKey) key;
 239                 }
 240
 241                 TValue ToValue (object value)
 242                 {
 243                         if (!(value is TValue) && (value != null || typeof (TValue).IsValueType))
 244                                 throw new ArgumentException (String.Format ("Value \"{0}\" cannot be converted to the value type {1}.", value, typeof (TValue)));
 245                         return (TValue) value;
 246                 }
 247                 #endregion
 248
 249                 #region IDictionary<TKey,TValue> Member
 250
 251                 ICollection<TKey> IDictionary<TKey,TValue>.Keys {
 252                         get { return new KeyCollection (this); }
 253                 }
 254
 255                 ICollection<TValue> IDictionary<TKey,TValue>.Values {
 256                         get { return new ValueCollection (this); }
 257                 }
 258
 259                 #endregion
 260
 261                 #region ICollection<KeyValuePair<TKey,TValue>> Member
 262
 263                 void ICollection<KeyValuePair<TKey,TValue>>.Add (KeyValuePair<TKey,TValue> item)
 264                 {
 265                         Add (item.Key, item.Value);
 266                 }
 267
 268                 bool ICollection<KeyValuePair<TKey,TValue>>.Contains (KeyValuePair<TKey,TValue> item)
 269                 {
 270                         TValue value;
 271                         return TryGetValue (item.Key, out value) &&
 272                                 EqualityComparer<TValue>.Default.Equals (item.Value, value);
 273                 }
 274
 275                 bool ICollection<KeyValuePair<TKey,TValue>>.IsReadOnly {
 276                         get { return false; }
 277                 }
 278
 279                 bool ICollection<KeyValuePair<TKey,TValue>>.Remove (KeyValuePair<TKey,TValue> item)
 280                 {
 281                         TValue value;
 282                         return TryGetValue (item.Key, out value) &&
 283                                 EqualityComparer<TValue>.Default.Equals (item.Value, value) &&
 284                                 Remove (item.Key);
 285                 }
 286
 287                 #endregion
 288
 289                 #region IDictionary Member
 290
 291                 void IDictionary.Add (object key, object value)
 292                 {
 293                         Add (ToKey (key), ToValue (value));
 294                 }
 295
 296                 bool IDictionary.Contains (object key)
 297                 {
 298                         return ContainsKey (ToKey (key));
 299                 }
 300
 301                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 302                 {
 303                         return new Enumerator (this);
 304                 }
 305
 306                 bool IDictionary.IsFixedSize {
 307                         get { return false; }
 308                 }
 309
 310                 bool IDictionary.IsReadOnly {
 311                         get { return false; }
 312                 }
 313
 314                 ICollection IDictionary.Keys  {
 315                         get { return new KeyCollection (this); }
 316                 }
 317
 318                 void IDictionary.Remove (object key)
 319                 {
 320                         Remove (ToKey (key));
 321                 }
 322
 323                 ICollection IDictionary.Values {
 324                         get { return new ValueCollection (this); }
 325                 }
 326
 327                 object IDictionary.this [object key] {
 328                         get { return this [ToKey (key)]; }
 329                         set { this [ToKey (key)] = ToValue (value); }
 330                 }
 331
 332                 #endregion
 333
 334                 #region ICollection Member
 335
 336                 void ICollection.CopyTo (Array array, int index)
 337                 {
 338                         if (Count == 0)
 339                                 return;
 340                         if (array == null)
 341                                 throw new ArgumentNullException ();
 342                         if (index < 0 || array.Length <= index)
 343                                 throw new ArgumentOutOfRangeException ();
 344                         if (array.Length - index < Count)
 345                                 throw new ArgumentException ();
 346
 347                         foreach (Node n in tree)
 348                                 array.SetValue (n.AsDE (), index++);
 349                 }
 350
 351                 bool ICollection.IsSynchronized {
 352                         get { return false; }
 353                 }
 354
 355                 // TODO:Is this correct? If this is wrong,please fix.
 356                 object ICollection.SyncRoot {
 357                         get { return this; }
 358                 }
 359
 360                 #endregion
 361
 362                 #region IEnumerable Member
 363
 364                 IEnumerator IEnumerable.GetEnumerator ()
 365                 {
 366                         return new Enumerator (this);
 367                 }
 368
 369                 #endregion
 370
 371                 #region IEnumerable<TKey> Member
 372
 373                 IEnumerator<KeyValuePair<TKey,TValue>> IEnumerable<KeyValuePair<TKey,TValue>>.GetEnumerator ()
 374                 {
 375                         return new Enumerator (this);
 376                 }
 377
 378                 #endregion
 379
 380                 [Serializable]
 381                 [DebuggerDisplay ("Count={Count}")]
 382                 [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
 383                 public sealed class ValueCollection : ICollection<TValue>,
 384                         IEnumerable<TValue>, ICollection, IEnumerable
 385                 {
 386                         SortedDictionary<TKey,TValue> _dic;
 387
 388                         public ValueCollection (SortedDictionary<TKey,TValue> dic)
 389                         {
 390                                 _dic = dic;
 391                         }
 392
 393                         void ICollection<TValue>.Add (TValue item)
 394                         {
 395                                 throw new NotSupportedException ();
 396                         }
 397
 398                         void ICollection<TValue>.Clear ()
 399                         {
 400                                 throw new NotSupportedException ();
 401                         }
 402
 403                         bool ICollection<TValue>.Contains (TValue item)
 404                         {
 405                                 return _dic.ContainsValue (item);
 406                         }
 407
 408                         public void CopyTo (TValue [] array, int arrayIndex)
 409                         {
 410                                 if (Count == 0)
 411                                         return;
 412                                 if (array == null)
 413                                         throw new ArgumentNullException ();
 414                                 if (arrayIndex < 0 || array.Length <= arrayIndex)
 415                                         throw new ArgumentOutOfRangeException ();
 416                                 if (array.Length - arrayIndex < Count)
 417                                         throw new ArgumentException ();
 418                                 foreach (Node n in _dic.tree)
 419                                         array [arrayIndex++] = n.value;
 420                         }
 421
 422                         public int Count {
 423                                 get { return _dic.Count; }
 424                         }
 425
 426                         bool ICollection<TValue>.IsReadOnly {
 427                                 get { return true; }
 428                         }
 429
 430                         bool ICollection<TValue>.Remove (TValue item)
 431                         {
 432                                 throw new NotSupportedException ();
 433                         }
 434
 435                         IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator ()
 436                         {
 437                                 return GetEnumerator ();
 438                         }
 439
 440                         public Enumerator GetEnumerator ()
 441                         {
 442                                 return new Enumerator (_dic);
 443                         }
 444
 445                         void ICollection.CopyTo (Array array, int index)
 446                         {
 447                                 if (Count == 0)
 448                                         return;
 449                                 if (array == null)
 450                                         throw new ArgumentNullException ();
 451                                 if (index < 0 || array.Length <= index)
 452                                         throw new ArgumentOutOfRangeException ();
 453                                 if (array.Length - index < Count)
 454                                         throw new ArgumentException ();
 455                                 foreach (Node n in _dic.tree)
 456                                         array.SetValue (n.value, index++);
 457                         }
 458
 459                         bool ICollection.IsSynchronized {
 460                                 get { return false; }
 461                         }
 462
 463                         object ICollection.SyncRoot {
 464                                 get { return _dic; }
 465                         }
 466
 467                         IEnumerator IEnumerable.GetEnumerator ()
 468                         {
 469                                 return new Enumerator (_dic);
 470                         }
 471
 472                         public struct Enumerator : IEnumerator<TValue>,IEnumerator, IDisposable
 473                         {
 474                                 RBTree.NodeEnumerator host;
 475
 476                                 TValue current;
 477
 478                                 internal Enumerator (SortedDictionary<TKey,TValue> dic)
 479                                         : this ()
 480                                 {
 481                                         host = dic.tree.GetEnumerator ();
 482                                 }
 483
 484                                 public TValue Current {
 485                                         get { return current; }
 486                                 }
 487
 488                                 public bool MoveNext ()
 489                                 {
 490                                         if (!host.MoveNext ())
 491                                                 return false;
 492                                         current = ((Node) host.Current).value;
 493                                         return true;
 494                                 }
 495
 496                                 public void Dispose ()
 497                                 {
 498                                         host.Dispose ();
 499                                 }
 500
 501                                 object IEnumerator.Current {
 502                                         get {
 503                                                 host.check_current ();
 504                                                 return current;
 505                                         }
 506                                 }
 507
 508                                 void IEnumerator.Reset ()
 509                                 {
 510                                         host.Reset ();
 511                                 }
 512                         }
 513                 }
 514
 515                 [Serializable]
 516                 [DebuggerDisplay ("Count={Count}")]
 517                 [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
 518                 public sealed class KeyCollection : ICollection<TKey>,
 519                         IEnumerable<TKey>, ICollection, IEnumerable
 520                 {
 521                         SortedDictionary<TKey,TValue> _dic;
 522
 523                         public KeyCollection (SortedDictionary<TKey,TValue> dic)
 524                         {
 525                                 _dic = dic;
 526                         }
 527
 528                         void ICollection<TKey>.Add (TKey item)
 529                         {
 530                                 throw new NotSupportedException ();
 531                         }
 532
 533                         void ICollection<TKey>.Clear ()
 534                         {
 535                                 throw new NotSupportedException ();
 536                         }
 537
 538                         bool ICollection<TKey>.Contains (TKey item)
 539                         {
 540                                 return _dic.ContainsKey (item);
 541                         }
 542
 543                         IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator ()
 544                         {
 545                                 return GetEnumerator ();
 546                         }
 547
 548                         public void CopyTo (TKey [] array, int arrayIndex)
 549                         {
 550                                 if (Count == 0)
 551                                         return;
 552                                 if (array == null)
 553                                         throw new ArgumentNullException ();
 554                                 if (arrayIndex < 0 || array.Length <= arrayIndex)
 555                                         throw new ArgumentOutOfRangeException ();
 556                                 if (array.Length - arrayIndex < Count)
 557                                         throw new ArgumentException ();
 558                                 foreach (Node n in _dic.tree)
 559                                         array [arrayIndex++] = n.key;
 560                         }
 561
 562                         public int Count {
 563                                 get { return _dic.Count; }
 564                         }
 565
 566                         bool ICollection<TKey>.IsReadOnly {
 567                                 get { return true; }
 568                         }
 569
 570                         bool ICollection<TKey>.Remove (TKey item)
 571                         {
 572                                 throw new NotSupportedException ();
 573                         }
 574
 575                         public Enumerator GetEnumerator ()
 576                         {
 577                                 return new Enumerator (_dic);
 578                         }
 579
 580                         void ICollection.CopyTo (Array array, int index)
 581                         {
 582                                 if (Count == 0)
 583                                         return;
 584                                 if (array == null)
 585                                         throw new ArgumentNullException ();
 586                                 if (index < 0 || array.Length <= index)
 587                                         throw new ArgumentOutOfRangeException ();
 588                                 if (array.Length - index < Count)
 589                                         throw new ArgumentException ();
 590                                 foreach (Node n in _dic.tree)
 591                                         array.SetValue (n.key, index++);
 592                         }
 593
 594                         bool ICollection.IsSynchronized {
 595                                 get { return false; }
 596                         }
 597
 598                         object ICollection.SyncRoot {
 599                                 get { return _dic; }
 600                         }
 601
 602                         IEnumerator IEnumerable.GetEnumerator ()
 603                         {
 604                                 return new Enumerator (_dic);
 605                         }
 606
 607                         public struct Enumerator : IEnumerator<TKey>, IEnumerator, IDisposable
 608                         {
 609                                 RBTree.NodeEnumerator host;
 610
 611                                 TKey current;
 612
 613                                 internal Enumerator (SortedDictionary<TKey,TValue> dic)
 614                                         : this ()
 615                                 {
 616                                         host = dic.tree.GetEnumerator ();
 617                                 }
 618
 619                                 public TKey Current {
 620                                         get { return current; }
 621                                 }
 622
 623                                 public bool MoveNext ()
 624                                 {
 625                                         if (!host.MoveNext ())
 626                                                 return false;
 627                                         current = ((Node) host.Current).key;
 628                                         return true;
 629                                 }
 630
 631                                 public void Dispose ()
 632                                 {
 633                                         host.Dispose ();
 634                                 }
 635
 636                                 object IEnumerator.Current {
 637                                         get {
 638                                                 host.check_current ();
 639                                                 return current;
 640                                         }
 641                                 }
 642
 643                                 void IEnumerator.Reset ()
 644                                 {
 645                                         host.Reset ();
 646                                 }
 647                         }
 648                 }
 649
 650                 public struct Enumerator : IEnumerator<KeyValuePair<TKey,TValue>>, IDisposable, IDictionaryEnumerator, IEnumerator
 651                 {
 652                         RBTree.NodeEnumerator host;
 653
 654                         KeyValuePair<TKey, TValue> current;
 655
 656                         internal Enumerator (SortedDictionary<TKey,TValue> dic)
 657                                 : this ()
 658                         {
 659                                 host = dic.tree.GetEnumerator ();
 660                         }
 661
 662                         public KeyValuePair<TKey,TValue> Current {
 663                                 get { return current; }
 664                         }
 665
 666                         public bool MoveNext ()
 667                         {
 668                                 if (!host.MoveNext ())
 669                                         return false;
 670                                 current = ((Node) host.Current).AsKV ();
 671                                 return true;
 672                         }
 673
 674                         public void Dispose ()
 675                         {
 676                                 host.Dispose ();
 677                         }
 678
 679                         Node CurrentNode {
 680                                 get {
 681                                         host.check_current ();
 682                                         return (Node) host.Current;
 683                                 }
 684                         }
 685
 686                         DictionaryEntry IDictionaryEnumerator.Entry {
 687                                 get { return CurrentNode.AsDE (); }
 688                         }
 689
 690                         object IDictionaryEnumerator.Key {
 691                                 get { return CurrentNode.key; }
 692                         }
 693
 694                         object IDictionaryEnumerator.Value {
 695                                 get { return CurrentNode.value; }
 696                         }
 697
 698                         object IEnumerator.Current {
 699                                 get { return CurrentNode.AsDE (); }
 700                         }
 701
 702                         void IEnumerator.Reset ()
 703                         {
 704                                 host.Reset ();
 705                         }
 706                 }
 707         }
 708 }