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                                 if (dictionary == null)
 418                                         throw new ArgumentNullException ("dictionary");
 419
 420                                 _dic = dictionary;
 421                         }
 422
 423                         void ICollection<TValue>.Add (TValue item)
 424                         {
 425                                 throw new NotSupportedException ();
 426                         }
 427
 428                         void ICollection<TValue>.Clear ()
 429                         {
 430                                 throw new NotSupportedException ();
 431                         }
 432
 433                         bool ICollection<TValue>.Contains (TValue item)
 434                         {
 435                                 return _dic.ContainsValue (item);
 436                         }
 437
 438                         public void CopyTo (TValue [] array, int index)
 439                         {
 440                                 if (Count == 0)
 441                                         return;
 442                                 if (array == null)
 443                                         throw new ArgumentNullException ();
 444                                 if (index < 0 || array.Length <= index)
 445                                         throw new ArgumentOutOfRangeException ();
 446                                 if (array.Length - index < Count)
 447                                         throw new ArgumentException ();
 448                                 foreach (Node n in _dic.tree)
 449                                         array [index++] = n.value;
 450                         }
 451
 452                         public int Count {
 453                                 get { return _dic.Count; }
 454                         }
 455
 456                         bool ICollection<TValue>.IsReadOnly {
 457                                 get { return true; }
 458                         }
 459
 460                         bool ICollection<TValue>.Remove (TValue item)
 461                         {
 462                                 throw new NotSupportedException ();
 463                         }
 464
 465                         IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator ()
 466                         {
 467                                 return GetEnumerator ();
 468                         }
 469
 470                         public Enumerator GetEnumerator ()
 471                         {
 472                                 return new Enumerator (_dic);
 473                         }
 474
 475                         void ICollection.CopyTo (Array array, int index)
 476                         {
 477                                 if (Count == 0)
 478                                         return;
 479                                 if (array == null)
 480                                         throw new ArgumentNullException ();
 481                                 if (index < 0 || array.Length <= index)
 482                                         throw new ArgumentOutOfRangeException ();
 483                                 if (array.Length - index < Count)
 484                                         throw new ArgumentException ();
 485                                 foreach (Node n in _dic.tree)
 486                                         array.SetValue (n.value, index++);
 487                         }
 488
 489                         bool ICollection.IsSynchronized {
 490                                 get { return false; }
 491                         }
 492
 493                         object ICollection.SyncRoot {
 494                                 get { return _dic; }
 495                         }
 496
 497                         IEnumerator IEnumerable.GetEnumerator ()
 498                         {
 499                                 return new Enumerator (_dic);
 500                         }
 501
 502                         public struct Enumerator : IEnumerator<TValue>,IEnumerator, IDisposable
 503                         {
 504                                 RBTree.NodeEnumerator host;
 505
 506                                 TValue current;
 507
 508                                 internal Enumerator (SortedDictionary<TKey,TValue> dictionary)
 509                                         : this ()
 510                                 {
 511                                         host = dictionary.tree.GetEnumerator ();
 512                                 }
 513
 514                                 public TValue Current {
 515                                         get { return current; }
 516                                 }
 517
 518                                 public bool MoveNext ()
 519                                 {
 520                                         if (!host.MoveNext ())
 521                                                 return false;
 522                                         current = ((Node) host.Current).value;
 523                                         return true;
 524                                 }
 525
 526                                 public void Dispose ()
 527                                 {
 528                                         host.Dispose ();
 529                                 }
 530
 531                                 object IEnumerator.Current {
 532                                         get {
 533                                                 host.check_current ();
 534                                                 return current;
 535                                         }
 536                                 }
 537
 538                                 void IEnumerator.Reset ()
 539                                 {
 540                                         host.Reset ();
 541                                 }
 542                         }
 543                 }
 544
 545                 [Serializable]
 546                 [DebuggerDisplay ("Count={Count}")]
 547                 [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
 548                 public sealed class KeyCollection : ICollection<TKey>,
 549                         IEnumerable<TKey>, ICollection, IEnumerable
 550                 {
 551                         SortedDictionary<TKey,TValue> _dic;
 552
 553                         public KeyCollection (SortedDictionary<TKey,TValue> dictionary)
 554                         {
 555                                 _dic = dictionary;
 556                         }
 557
 558                         void ICollection<TKey>.Add (TKey item)
 559                         {
 560                                 throw new NotSupportedException ();
 561                         }
 562
 563                         void ICollection<TKey>.Clear ()
 564                         {
 565                                 throw new NotSupportedException ();
 566                         }
 567
 568                         bool ICollection<TKey>.Contains (TKey item)
 569                         {
 570                                 return _dic.ContainsKey (item);
 571                         }
 572
 573                         IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator ()
 574                         {
 575                                 return GetEnumerator ();
 576                         }
 577
 578                         public void CopyTo (TKey [] array, int index)
 579                         {
 580                                 if (Count == 0)
 581                                         return;
 582                                 if (array == null)
 583                                         throw new ArgumentNullException ();
 584                                 if (index < 0 || array.Length <= index)
 585                                         throw new ArgumentOutOfRangeException ();
 586                                 if (array.Length - index < Count)
 587                                         throw new ArgumentException ();
 588                                 foreach (Node n in _dic.tree)
 589                                         array [index++] = n.key;
 590                         }
 591
 592                         public int Count {
 593                                 get { return _dic.Count; }
 594                         }
 595
 596                         bool ICollection<TKey>.IsReadOnly {
 597                                 get { return true; }
 598                         }
 599
 600                         bool ICollection<TKey>.Remove (TKey item)
 601                         {
 602                                 throw new NotSupportedException ();
 603                         }
 604
 605                         public Enumerator GetEnumerator ()
 606                         {
 607                                 return new Enumerator (_dic);
 608                         }
 609
 610                         void ICollection.CopyTo (Array array, int index)
 611                         {
 612                                 if (Count == 0)
 613                                         return;
 614                                 if (array == null)
 615                                         throw new ArgumentNullException ();
 616                                 if (index < 0 || array.Length <= index)
 617                                         throw new ArgumentOutOfRangeException ();
 618                                 if (array.Length - index < Count)
 619                                         throw new ArgumentException ();
 620                                 foreach (Node n in _dic.tree)
 621                                         array.SetValue (n.key, index++);
 622                         }
 623
 624                         bool ICollection.IsSynchronized {
 625                                 get { return false; }
 626                         }
 627
 628                         object ICollection.SyncRoot {
 629                                 get { return _dic; }
 630                         }
 631
 632                         IEnumerator IEnumerable.GetEnumerator ()
 633                         {
 634                                 return new Enumerator (_dic);
 635                         }
 636
 637                         public struct Enumerator : IEnumerator<TKey>, IEnumerator, IDisposable
 638                         {
 639                                 RBTree.NodeEnumerator host;
 640
 641                                 TKey current;
 642
 643                                 internal Enumerator (SortedDictionary<TKey,TValue> dic)
 644                                         : this ()
 645                                 {
 646                                         host = dic.tree.GetEnumerator ();
 647                                 }
 648
 649                                 public TKey Current {
 650                                         get { return current; }
 651                                 }
 652
 653                                 public bool MoveNext ()
 654                                 {
 655                                         if (!host.MoveNext ())
 656                                                 return false;
 657                                         current = ((Node) host.Current).key;
 658                                         return true;
 659                                 }
 660
 661                                 public void Dispose ()
 662                                 {
 663                                         host.Dispose ();
 664                                 }
 665
 666                                 object IEnumerator.Current {
 667                                         get {
 668                                                 host.check_current ();
 669                                                 return current;
 670                                         }
 671                                 }
 672
 673                                 void IEnumerator.Reset ()
 674                                 {
 675                                         host.Reset ();
 676                                 }
 677                         }
 678                 }
 679
 680                 public struct Enumerator : IEnumerator<KeyValuePair<TKey,TValue>>, IDisposable, IDictionaryEnumerator, IEnumerator
 681                 {
 682                         RBTree.NodeEnumerator host;
 683
 684                         KeyValuePair<TKey, TValue> current;
 685
 686                         internal Enumerator (SortedDictionary<TKey,TValue> dic)
 687                                 : this ()
 688                         {
 689                                 host = dic.tree.GetEnumerator ();
 690                         }
 691
 692                         public KeyValuePair<TKey,TValue> Current {
 693                                 get { return current; }
 694                         }
 695
 696                         public bool MoveNext ()
 697                         {
 698                                 if (!host.MoveNext ())
 699                                         return false;
 700                                 current = ((Node) host.Current).AsKV ();
 701                                 return true;
 702                         }
 703
 704                         public void Dispose ()
 705                         {
 706                                 host.Dispose ();
 707                         }
 708
 709                         Node CurrentNode {
 710                                 get {
 711                                         host.check_current ();
 712                                         return (Node) host.Current;
 713                                 }
 714                         }
 715
 716                         DictionaryEntry IDictionaryEnumerator.Entry {
 717                                 get { return CurrentNode.AsDE (); }
 718                         }
 719
 720                         object IDictionaryEnumerator.Key {
 721                                 get { return CurrentNode.key; }
 722                         }
 723
 724                         object IDictionaryEnumerator.Value {
 725                                 get { return CurrentNode.value; }
 726                         }
 727
 728                         object IEnumerator.Current {
 729                                 get { return CurrentNode.AsDE (); }
 730                         }
 731
 732                         void IEnumerator.Reset ()
 733                         {
 734                                 host.Reset ();
 735                         }
 736                 }
 737         }
 738 }