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