mcs/class/corlib/System.Collections/SortedList.cs

   1 //
   2 // System.Collections.SortedList.cs
   3 //
   4 // Author:
   5 //   Sergey Chaban (serge@wildwestsoftware.com)
   6 //   Duncan Mak (duncan@ximian.com)
   7 //   Herve Poussineau (hpoussineau@fr.st
   8 //
   9
  10 //
  11 // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
  12 //
  13 // Permission is hereby granted, free of charge, to any person obtaining
  14 // a copy of this software and associated documentation files (the
  15 // "Software"), to deal in the Software without restriction, including
  16 // without limitation the rights to use, copy, modify, merge, publish,
  17 // distribute, sublicense, and/or sell copies of the Software, and to
  18 // permit persons to whom the Software is furnished to do so, subject to
  19 // the following conditions:
  20 //
  21 // The above copyright notice and this permission notice shall be
  22 // included in all copies or substantial portions of the Software.
  23 //
  24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  31 //
  32
  33 using System.Globalization;
  34 using System.Runtime.InteropServices;
  35 using System.Diagnostics;
  36
  37 namespace System.Collections {
  38
  39         /// <summary>
  40         ///  Represents a collection of associated keys and values
  41         ///  that are sorted by the keys and are accessible by key
  42         ///  and by index.
  43         /// </summary>
  44         [Serializable]
  45         [ComVisible(true)]
  46         [DebuggerDisplay ("Count={Count}")]
  47         [DebuggerTypeProxy (typeof (CollectionDebuggerView))]
  48         public class SortedList : IDictionary, ICollection,
  49                                   IEnumerable, ICloneable {
  50
  51
  52                 [Serializable]
  53                 internal struct Slot {
  54                         internal Object key;
  55                         internal Object value;
  56                 }
  57
  58                 const int INITIAL_SIZE = 16;
  59
  60                 private enum EnumeratorMode : int { KEY_MODE = 0, VALUE_MODE, ENTRY_MODE }
  61
  62                 private Slot[] table;
  63                 private IComparer comparer;
  64                 private int inUse;
  65                 private int modificationCount;
  66                 private int defaultCapacity;
  67
  68                 //
  69                 // Constructors
  70                 //
  71                 public SortedList ()
  72                         : this (null, INITIAL_SIZE)
  73                 {
  74                 }
  75
  76                 public SortedList (int initialCapacity)
  77                         : this (null, initialCapacity)
  78                 {
  79                 }
  80
  81                 public SortedList (IComparer comparer, int capacity)
  82                 {
  83                         if (capacity < 0)
  84                                 throw new ArgumentOutOfRangeException ("capacity");
  85
  86                         if (capacity == 0)
  87                                 defaultCapacity = 0;
  88                         else
  89                                 defaultCapacity = INITIAL_SIZE;
  90
  91                         this.comparer = comparer;
  92                         InitTable (capacity, true);
  93                 }
  94
  95                 public SortedList (IComparer comparer)
  96                 {
  97                         this.comparer = comparer;
  98                         InitTable (INITIAL_SIZE, true);
  99                 }
 100
 101
 102                 public SortedList (IDictionary d) : this (d, null)
 103                 {
 104                 }
 105
 106                 // LAMESPEC: MSDN docs talk about an InvalidCastException but
 107                 // I wasn't able to duplicate such a case in the unit tests.
 108                 public SortedList (IDictionary d, IComparer comparer)
 109                 {
 110                         if (d  ==  null)
 111                                 throw new ArgumentNullException ("dictionary");
 112
 113                         InitTable (d.Count, true);
 114                         this.comparer = comparer;
 115
 116                         IDictionaryEnumerator it = d.GetEnumerator ();
 117                         while (it.MoveNext ()) {
 118                                 Add (it.Key, it.Value);
 119                         }
 120                 }
 121
 122                 //
 123                 // Properties
 124                 //
 125
 126                 // ICollection
 127
 128                 public virtual int Count {
 129                         get {
 130                                 return inUse;
 131                         }
 132                 }
 133
 134                 public virtual bool IsSynchronized {
 135                         get {
 136                                 return false;
 137                         }
 138                 }
 139
 140                 public virtual Object SyncRoot {
 141                         get {
 142                                 return this;
 143                         }
 144                 }
 145
 146
 147                 // IDictionary
 148
 149                 public virtual bool IsFixedSize {
 150                         get {
 151                                 return false;
 152                         }
 153                 }
 154
 155
 156                 public virtual bool IsReadOnly {
 157                         get {
 158                                 return false;
 159                         }
 160                 }
 161
 162                 public virtual ICollection Keys {
 163                         get {
 164                                 return new ListKeys (this);
 165                         }
 166                 }
 167
 168                 public virtual ICollection Values {
 169                         get {
 170                                 return new ListValues (this);
 171                         }
 172                 }
 173
 174
 175
 176                 public virtual Object this [Object key] {
 177                         get {
 178                                 if (key == null)
 179                                         throw new ArgumentNullException();
 180                                 return GetImpl (key);
 181                         }
 182                         set {
 183                                 if (key == null)
 184                                         throw new ArgumentNullException();
 185                                 if (IsReadOnly)
 186                                         throw new NotSupportedException("SortedList is Read Only.");
 187                                 if (Find(key) < 0 && IsFixedSize)
 188                                         throw new NotSupportedException("Key not found and SortedList is fixed size.");
 189
 190                                 PutImpl (key, value, true);
 191                         }
 192                 }
 193
 194                 public virtual int Capacity {
 195                         get {
 196                                 return table.Length;
 197                         }
 198
 199                         set {
 200                                 int current = this.table.Length;
 201
 202                                 if (inUse > value) {
 203                                         throw new ArgumentOutOfRangeException("capacity too small");
 204                                 }
 205                                 else if (value == 0) {
 206                                         // return to default size
 207                                         Slot [] newTable = new Slot [defaultCapacity];
 208                                         Array.Copy (table, newTable, inUse);
 209                                         this.table = newTable;
 210                                 }
 211                                 else if (value > inUse) {
 212                                         Slot [] newTable = new Slot [value];
 213                                         Array.Copy (table, newTable, inUse);
 214                                         this.table = newTable;
 215                                 }
 216                                 else if (value > current) {
 217                                         Slot [] newTable = new Slot [value];
 218                                         Array.Copy (table, newTable, current);
 219                                         this.table = newTable;
 220                                 }
 221                         }
 222                 }
 223
 224                 //
 225                 // Public instance methods.
 226                 //
 227
 228                 // IEnumerable
 229
 230                 IEnumerator IEnumerable.GetEnumerator ()
 231                 {
 232                         return new Enumerator (this, EnumeratorMode.ENTRY_MODE);
 233                 }
 234
 235
 236                 // IDictionary
 237
 238                 public virtual void Add (object key, object value)
 239                 {
 240                         PutImpl (key, value, false);
 241                 }
 242
 243
 244                 public virtual void Clear ()
 245                 {
 246                         Array.Clear (table, 0, table.Length);
 247                         inUse = 0;
 248                         modificationCount++;
 249                 }
 250
 251                 public virtual bool Contains (object key)
 252                 {
 253                         if (null == key)
 254                                 throw new ArgumentNullException();
 255
 256                         try {
 257                                 return (Find (key) >= 0);
 258                         } catch (Exception) {
 259                                 throw new InvalidOperationException();
 260                         }
 261                 }
 262
 263
 264                 public virtual IDictionaryEnumerator GetEnumerator ()
 265                 {
 266                         return new Enumerator (this, EnumeratorMode.ENTRY_MODE);
 267                 }
 268
 269                 public virtual void Remove (object key)
 270                 {
 271                         int i = IndexOfKey (key);
 272                         if (i >= 0) RemoveAt (i);
 273                 }
 274
 275
 276                 // ICollection
 277
 278                 public virtual void CopyTo (Array array, int arrayIndex)
 279                 {
 280                         if (null == array)
 281                                 throw new ArgumentNullException();
 282
 283                         if (arrayIndex < 0)
 284                                 throw new ArgumentOutOfRangeException();
 285
 286                         if (array.Rank > 1)
 287                                 throw new ArgumentException("array is multi-dimensional");
 288                         if (arrayIndex >= array.Length)
 289                                 throw new ArgumentNullException("arrayIndex is greater than or equal to array.Length");
 290                         if (Count > (array.Length - arrayIndex))
 291                                 throw new ArgumentNullException("Not enough space in array from arrayIndex to end of array");
 292
 293                         IDictionaryEnumerator it = GetEnumerator ();
 294                         int i = arrayIndex;
 295
 296                         while (it.MoveNext ()) {
 297                                 array.SetValue (it.Entry, i++);
 298                         }
 299                 }
 300
 301
 302
 303                 // ICloneable
 304
 305                 public virtual object Clone ()
 306                 {
 307                         SortedList sl = new SortedList (this, comparer);
 308                         sl.modificationCount = this.modificationCount;
 309                         return sl;
 310                 }
 311
 312
 313
 314
 315                 //
 316                 // SortedList
 317                 //
 318
 319                 public virtual IList GetKeyList ()
 320                 {
 321                         return new ListKeys (this);
 322                 }
 323
 324
 325                 public virtual IList GetValueList ()
 326                 {
 327                         return new ListValues (this);
 328                 }
 329
 330
 331                 public virtual void RemoveAt (int index)
 332                 {
 333                         Slot [] table = this.table;
 334                         int cnt = Count;
 335                         if (index >= 0 && index < cnt) {
 336                                 if (index != cnt - 1) {
 337                                         Array.Copy (table, index+1, table, index, cnt-1-index);
 338                                 } else {
 339                                         table [index].key = null;
 340                                         table [index].value = null;
 341                                 }
 342                                 --inUse;
 343                                 ++modificationCount;
 344                         } else {
 345                                 throw new ArgumentOutOfRangeException("index out of range");
 346                         }
 347                 }
 348
 349                 public virtual int IndexOfKey (object key)
 350                 {
 351                         if (null == key)
 352                                 throw new ArgumentNullException();
 353
 354                         int indx = 0;
 355                         try {
 356                                 indx = Find (key);
 357                         } catch (Exception) {
 358                                 throw new InvalidOperationException();
 359                         }
 360
 361                         return (indx | (indx >> 31));
 362                 }
 363
 364
 365                 public virtual int IndexOfValue (object value)
 366                 {
 367                         if (inUse == 0)
 368                                 return -1;
 369
 370                         for (int i = 0; i < inUse; i ++) {
 371                                 Slot current = this.table [i];
 372
 373                                 if (Equals (value, current.value))
 374                                         return i;
 375                         }
 376
 377                         return -1;
 378                 }
 379
 380
 381                 public virtual bool ContainsKey (object key)
 382                 {
 383                         if (null == key)
 384                                 throw new ArgumentNullException();
 385
 386                         try {
 387                                 return Contains (key);
 388                         } catch (Exception) {
 389                                 throw new InvalidOperationException();
 390                         }
 391                 }
 392
 393
 394                 public virtual bool ContainsValue (object value)
 395                 {
 396                         return IndexOfValue (value) >= 0;
 397                 }
 398
 399
 400                 public virtual object GetByIndex (int index)
 401                 {
 402                         if (index >= 0 && index < Count)
 403                                 return table [index].value;
 404
 405                         else
 406                                 throw new ArgumentOutOfRangeException("index out of range");
 407                 }
 408
 409
 410                 public virtual void SetByIndex (int index, object value)
 411                 {
 412                         if (index >= 0 && index < Count)
 413                                 table [index].value = value;
 414
 415                         else
 416                                 throw new ArgumentOutOfRangeException("index out of range");
 417                 }
 418
 419
 420                 public virtual object GetKey (int index)
 421                 {
 422                         if (index >= 0 && index < Count)
 423                                 return table [index].key;
 424
 425                         else
 426                                 throw new ArgumentOutOfRangeException("index out of range");
 427                 }
 428
 429                 public static SortedList Synchronized (SortedList list)
 430                 {
 431                         if (list == null)
 432                                 throw new ArgumentNullException (Locale.GetText ("Base list is null."));
 433
 434                         return new SynchedSortedList (list);
 435                 }
 436
 437                 public virtual void TrimToSize ()
 438                 {
 439                         // From Beta2:
 440                         // Trimming an empty SortedList sets the capacity
 441                         // of the SortedList to the default capacity,
 442                         // not zero.
 443                         if (Count == 0)
 444                                 Resize (defaultCapacity, false);
 445                         else
 446                                 Resize (Count, true);
 447                 }
 448
 449
 450                 //
 451                 // Private methods
 452                 //
 453
 454
 455                 private void Resize (int n, bool copy)
 456                 {
 457                         Slot [] table = this.table;
 458                         Slot [] newTable = new Slot [n];
 459                         if (copy) Array.Copy (table, 0, newTable, 0, n);
 460                         this.table = newTable;
 461                 }
 462
 463
 464                 private void EnsureCapacity (int n, int free)
 465                 {
 466                         Slot [] table = this.table;
 467                         Slot [] newTable = null;
 468                         int cap = Capacity;
 469                         bool gap = (free >=0 && free < Count);
 470
 471                         if (n > cap) {
 472                                 newTable = new Slot [n << 1];
 473                         }
 474
 475                         if (newTable != null) {
 476                                 if (gap) {
 477                                         int copyLen = free;
 478                                         if (copyLen > 0) {
 479                                                 Array.Copy (table, 0, newTable, 0, copyLen);
 480                                         }
 481                                         copyLen = Count - free;
 482                                         if (copyLen > 0) {
 483                                                 Array.Copy (table, free, newTable, free+1, copyLen);
 484                                         }
 485                                 } else {
 486                                         // Just a resizing, copy the entire table.
 487                                         Array.Copy (table, newTable, Count);
 488                                 }
 489                                 this.table = newTable;
 490                         } else if (gap) {
 491                                 Array.Copy (table, free, table, free+1, Count - free);
 492                         }
 493                 }
 494
 495
 496                 private void PutImpl (object key, object value, bool overwrite)
 497                 {
 498                         if (key == null)
 499                                 throw new ArgumentNullException ("null key");
 500
 501                         Slot [] table = this.table;
 502
 503                         int freeIndx = -1;
 504
 505                         try {
 506                                 freeIndx = Find (key);
 507                         } catch (Exception) {
 508                                 throw new InvalidOperationException();
 509                         }
 510
 511                         if (freeIndx >= 0) {
 512                                 if (!overwrite) {
 513                                         string msg = Locale.GetText ("Key '{0}' already exists in list.", key);
 514                                         throw new ArgumentException (msg);
 515                                 }
 516
 517                                 table [freeIndx].value = value;
 518                                 ++modificationCount;
 519                                 return;
 520                         }
 521
 522                         freeIndx = ~freeIndx;
 523
 524                         if (freeIndx > Capacity + 1)
 525                                 throw new Exception ("SortedList::internal error ("+key+", "+value+") at ["+freeIndx+"]");
 526
 527
 528                         EnsureCapacity (Count+1, freeIndx);
 529
 530                         table = this.table;
 531                         table [freeIndx].key = key;
 532                         table [freeIndx].value = value;
 533
 534                         ++inUse;
 535                         ++modificationCount;
 536
 537                 }
 538
 539
 540                 private object GetImpl (object key)
 541                 {
 542                         int i = Find (key);
 543
 544                         if (i >= 0)
 545                                 return table [i].value;
 546                         else
 547                                 return null;
 548                 }
 549
 550                 private void InitTable (int capacity, bool forceSize)
 551                 {
 552                         if (!forceSize && (capacity < defaultCapacity))
 553                                 capacity = defaultCapacity;
 554                         this.table = new Slot [capacity];
 555                         this.inUse = 0;
 556                         this.modificationCount = 0;
 557                 }
 558
 559                 private void  CopyToArray (Array arr, int i,
 560                                            EnumeratorMode mode)
 561                 {
 562                         if (arr == null)
 563                                 throw new ArgumentNullException ("arr");
 564
 565                         if (i < 0 || i + this.Count > arr.Length)
 566                                 throw new ArgumentOutOfRangeException ("i");
 567
 568                         IEnumerator it = new Enumerator (this, mode);
 569
 570                         while (it.MoveNext ()) {
 571                                 arr.SetValue (it.Current, i++);
 572                         }
 573                 }
 574
 575
 576                 private int Find (object key)
 577                 {
 578                         Slot [] table = this.table;
 579                         int len = Count;
 580
 581                         if (len == 0) return ~0;
 582
 583                         IComparer comparer = (this.comparer == null)
 584                                               ? Comparer.Default
 585                                               : this.comparer;
 586
 587                         int left = 0;
 588                         int right = len-1;
 589
 590                         while (left <= right) {
 591                                 int guess = (left + right) >> 1;
 592
 593                                 int cmp = comparer.Compare (table[guess].key, key);
 594                                 if (cmp == 0) return guess;
 595
 596                                 if (cmp <  0) left = guess+1;
 597                                 else right = guess-1;
 598                         }
 599
 600                         return ~left;
 601                 }
 602
 603
 604
 605                 //
 606                 // Inner classes
 607                 //
 608
 609
 610                 private sealed class Enumerator : ICloneable, IDictionaryEnumerator, IEnumerator {
 611
 612                         private SortedList host;
 613                         private object currentKey;
 614                         private object currentValue;
 615
 616                         private int stamp;
 617                         private int pos;
 618                         private int size;
 619                         private EnumeratorMode mode;
 620
 621                         bool invalid;
 622
 623                         const string xstr = "SortedList.Enumerator: snapshot out of sync.";
 624
 625                         public Enumerator (SortedList host, EnumeratorMode mode)
 626                         {
 627                                 this.host = host;
 628                                 stamp = host.modificationCount;
 629                                 size = host.Count;
 630                                 this.mode = mode;
 631                                 Reset ();
 632                         }
 633
 634                         public Enumerator (SortedList host)
 635                         : this (host, EnumeratorMode.ENTRY_MODE)
 636                         {
 637                         }
 638
 639                         public void Reset ()
 640                         {
 641                                 if (host.modificationCount != stamp || invalid)
 642                                         throw new InvalidOperationException (xstr);
 643
 644                                 pos = -1;
 645                                 currentKey = null;
 646                                 currentValue = null;
 647                         }
 648
 649                         public bool MoveNext ()
 650                         {
 651                                 if (host.modificationCount != stamp || invalid)
 652                                         throw new InvalidOperationException (xstr);
 653
 654                                 Slot [] table = host.table;
 655
 656                                 if (++pos < size) {
 657                                         Slot entry = table [pos];
 658
 659                                         currentKey = entry.key;
 660                                         currentValue = entry.value;
 661                                         return true;
 662                                 }
 663
 664                                 currentKey = null;
 665                                 currentValue = null;
 666                                 return false;
 667                         }
 668
 669                         public DictionaryEntry Entry
 670                         {
 671                                 get {
 672                                         if (invalid || pos >= size || pos == -1)
 673                                                 throw new InvalidOperationException (xstr);
 674
 675                                         return new DictionaryEntry (currentKey,
 676                                                                     currentValue);
 677                                 }
 678                         }
 679
 680                         public Object Key {
 681                                 get {
 682                                         if (invalid || pos >= size || pos == -1)
 683                                                 throw new InvalidOperationException (xstr);
 684                                         return currentKey;
 685                                 }
 686                         }
 687
 688                         public Object Value {
 689                                 get {
 690                                         if (invalid || pos >= size || pos == -1)
 691                                                 throw new InvalidOperationException (xstr);
 692                                         return currentValue;
 693                                 }
 694                         }
 695
 696                         public Object Current {
 697                                 get {
 698                                         if (invalid || pos >= size || pos == -1)
 699                                                 throw new InvalidOperationException (xstr);
 700
 701                                         switch (mode) {
 702                                         case EnumeratorMode.KEY_MODE:
 703                                                 return currentKey;
 704                                         case EnumeratorMode.VALUE_MODE:
 705                                                 return currentValue;
 706                                         case EnumeratorMode.ENTRY_MODE:
 707                                                 return this.Entry;
 708
 709                                         default:
 710                                                 throw new NotSupportedException (mode + " is not a supported mode.");
 711                                         }
 712                                 }
 713                         }
 714
 715                         // ICloneable
 716
 717                         public object Clone ()
 718                         {
 719                                 Enumerator e = new Enumerator (host, mode);
 720                                 e.stamp = stamp;
 721                                 e.pos = pos;
 722                                 e.size = size;
 723                                 e.currentKey = currentKey;
 724                                 e.currentValue = currentValue;
 725                                 e.invalid = invalid;
 726                                 return e;
 727                         }
 728                 }
 729
 730                 [Serializable]
 731                 private class ListKeys : IList, IEnumerable {
 732
 733                         private SortedList host;
 734
 735
 736                         public ListKeys (SortedList host)
 737                         {
 738                                 if (host == null)
 739                                         throw new ArgumentNullException ();
 740
 741                                 this.host = host;
 742                         }
 743
 744                         //
 745                         // ICollection
 746                         //
 747
 748                         public virtual int Count {
 749                                 get {
 750                                         return host.Count;
 751                                 }
 752                         }
 753
 754                         public virtual bool IsSynchronized {
 755                                 get {
 756                                         return host.IsSynchronized;
 757                                 }
 758                         }
 759
 760                         public virtual Object SyncRoot {
 761                                 get {
 762                                         return host.SyncRoot;
 763                                 }
 764                         }
 765
 766                         public virtual void CopyTo (Array array, int arrayIndex)
 767                         {
 768                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.KEY_MODE);
 769                         }
 770
 771
 772                         //
 773                         // IList
 774                         //
 775
 776                         public virtual bool IsFixedSize {
 777                                 get {
 778                                         return true;
 779                                 }
 780                         }
 781
 782                         public virtual bool IsReadOnly {
 783                                 get {
 784                                         return true;
 785                                 }
 786                         }
 787
 788
 789                         public virtual object this [int index] {
 790                                 get {
 791                                         return host.GetKey (index);
 792                                 }
 793                                 set {
 794                                         throw new NotSupportedException("attempt to modify a key");
 795                                 }
 796                         }
 797
 798                         public virtual int Add (object value)
 799                         {
 800                                 throw new NotSupportedException("IList::Add not supported");
 801                         }
 802
 803                         public virtual void Clear ()
 804                         {
 805                                 throw new NotSupportedException("IList::Clear not supported");
 806                         }
 807
 808                         public virtual bool Contains (object key)
 809                         {
 810                                 return host.Contains (key);
 811                         }
 812
 813
 814                         public virtual int IndexOf (object key)
 815                         {
 816                                 return host.IndexOfKey (key);
 817                         }
 818
 819
 820                         public virtual void Insert (int index, object value)
 821                         {
 822                                 throw new NotSupportedException("IList::Insert not supported");
 823                         }
 824
 825
 826                         public virtual void Remove (object value)
 827                         {
 828                                 throw new NotSupportedException("IList::Remove not supported");
 829                         }
 830
 831
 832                         public virtual void RemoveAt (int index)
 833                         {
 834                                 throw new NotSupportedException("IList::RemoveAt not supported");
 835                         }
 836
 837
 838                         //
 839                         // IEnumerable
 840                         //
 841
 842                         public virtual IEnumerator GetEnumerator ()
 843                         {
 844                                 return new SortedList.Enumerator (host, EnumeratorMode.KEY_MODE);
 845                         }
 846
 847
 848                 }
 849
 850                 [Serializable]
 851                 private class ListValues : IList, IEnumerable {
 852
 853                         private SortedList host;
 854
 855
 856                         public ListValues (SortedList host)
 857                         {
 858                                 if (host == null)
 859                                         throw new ArgumentNullException ();
 860
 861                                 this.host = host;
 862                         }
 863
 864                         //
 865                         // ICollection
 866                         //
 867
 868                         public virtual int Count {
 869                                 get {
 870                                         return host.Count;
 871                                 }
 872                         }
 873
 874                         public virtual bool IsSynchronized {
 875                                 get {
 876                                         return host.IsSynchronized;
 877                                 }
 878                         }
 879
 880                         public virtual Object SyncRoot {
 881                                 get {
 882                                         return host.SyncRoot;
 883                                 }
 884                         }
 885
 886                         public virtual void CopyTo (Array array, int arrayIndex)
 887                         {
 888                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.VALUE_MODE);
 889                         }
 890
 891
 892                         //
 893                         // IList
 894                         //
 895
 896                         public virtual bool IsFixedSize {
 897                                 get {
 898                                         return true;
 899                                 }
 900                         }
 901
 902                         public virtual bool IsReadOnly {
 903                                 get {
 904                                         return true;
 905                                 }
 906                         }
 907
 908
 909                         public virtual object this [int index] {
 910                                 get {
 911                                         return host.GetByIndex (index);
 912                                 }
 913                                 set {
 914                                         throw new NotSupportedException("This operation is not supported on GetValueList return");
 915                                 }
 916                         }
 917
 918                         public virtual int Add (object value)
 919                         {
 920                                 throw new NotSupportedException("IList::Add not supported");
 921                         }
 922
 923                         public virtual void Clear ()
 924                         {
 925                                 throw new NotSupportedException("IList::Clear not supported");
 926                         }
 927
 928                         public virtual bool Contains (object value)
 929                         {
 930                                 return host.ContainsValue (value);
 931                         }
 932
 933
 934                         public virtual int IndexOf (object value)
 935                         {
 936                                 return host.IndexOfValue (value);
 937                         }
 938
 939
 940                         public virtual void Insert (int index, object value)
 941                         {
 942                                 throw new NotSupportedException("IList::Insert not supported");
 943                         }
 944
 945
 946                         public virtual void Remove (object value)
 947                         {
 948                                 throw new NotSupportedException("IList::Remove not supported");
 949                         }
 950
 951
 952                         public virtual void RemoveAt (int index)
 953                         {
 954                                 throw new NotSupportedException("IList::RemoveAt not supported");
 955                         }
 956
 957
 958                         //
 959                         // IEnumerable
 960                         //
 961
 962                         public virtual IEnumerator GetEnumerator ()
 963                         {
 964                                 return new SortedList.Enumerator (host, EnumeratorMode.VALUE_MODE);
 965                         }
 966
 967                 }
 968
 969                 private class SynchedSortedList : SortedList {
 970
 971                         private SortedList host;
 972
 973                         public SynchedSortedList (SortedList host)
 974                         {
 975                                 if (host == null)
 976                                         throw new ArgumentNullException ();
 977                                 this.host = host;
 978                         }
 979
 980                         public override int Capacity {
 981                                 get {
 982                                         lock (host.SyncRoot) {
 983                                                 return host.Capacity;
 984                                         }
 985                                 }
 986                                 set {
 987                                         lock (host.SyncRoot) {
 988                                                 host.Capacity = value;
 989                                         }
 990                                 }
 991                         }
 992
 993                         // ICollection
 994
 995                         public override int Count {
 996                                 get {
 997                                         return host.Count;
 998                                 }
 999                         }
1000
1001                         public override bool IsSynchronized {
1002                                 get {
1003                                         return true;
1004                                 }
1005                         }
1006
1007                         public override Object SyncRoot {
1008                                 get {
1009                                         return host.SyncRoot;
1010                                 }
1011                         }
1012
1013
1014
1015                         // IDictionary
1016
1017                         public override bool IsFixedSize {
1018                                 get {
1019                                         return host.IsFixedSize;
1020                                 }
1021                         }
1022
1023
1024                         public override bool IsReadOnly {
1025                                 get {
1026                                         return host.IsReadOnly;
1027                                 }
1028                         }
1029
1030                         public override ICollection Keys {
1031                                 get {
1032                                         ICollection keys = null;
1033                                         lock (host.SyncRoot) {
1034                                                 keys = host.Keys;
1035                                         }
1036                                         return keys;
1037                                 }
1038                         }
1039
1040                         public override ICollection Values {
1041                                 get {
1042                                         ICollection vals = null;
1043                                         lock (host.SyncRoot) {
1044                                                 vals = host.Values;
1045                                         }
1046                                         return vals;
1047                                 }
1048                         }
1049
1050
1051
1052                         public override Object this [object key] {
1053                                 get {
1054                                         lock (host.SyncRoot) {
1055                                                 return host.GetImpl (key);
1056                                         }
1057                                 }
1058                                 set {
1059                                         lock (host.SyncRoot) {
1060                                                 host.PutImpl (key, value, true);
1061                                         }
1062                                 }
1063                         }
1064
1065
1066
1067                         // ICollection
1068
1069                         public override void CopyTo (Array array, int arrayIndex)
1070                         {
1071                                 lock (host.SyncRoot) {
1072                                         host.CopyTo (array, arrayIndex);
1073                                 }
1074                         }
1075
1076
1077                         // IDictionary
1078
1079                         public override void Add (object key, object value)
1080                         {
1081                                 lock (host.SyncRoot) {
1082                                         host.PutImpl (key, value, false);
1083                                 }
1084                         }
1085
1086                         public override void Clear ()
1087                         {
1088                                 lock (host.SyncRoot) {
1089                                         host.Clear ();
1090                                 }
1091                         }
1092
1093                         public override bool Contains (object key)
1094                         {
1095                                 lock (host.SyncRoot) {
1096                                         return (host.Find (key) >= 0);
1097                                 }
1098                         }
1099
1100                         public override IDictionaryEnumerator GetEnumerator ()
1101                         {
1102                                 lock (host.SyncRoot) {
1103                                         return host.GetEnumerator();
1104                                 }
1105                         }
1106
1107                         public override void Remove (object key)
1108                         {
1109                                 lock (host.SyncRoot) {
1110                                         host.Remove (key);
1111                                 }
1112                         }
1113
1114
1115
1116                         public override bool ContainsKey (object key)
1117                         {
1118                                 lock (host.SyncRoot) {
1119                                         return host.Contains (key);
1120                                 }
1121                         }
1122
1123                         public override bool ContainsValue (object value)
1124                         {
1125                                 lock (host.SyncRoot) {
1126                                         return host.ContainsValue (value);
1127                                 }
1128                         }
1129
1130
1131                         // ICloneable
1132
1133                         public override object Clone ()
1134                         {
1135                                 lock (host.SyncRoot) {
1136                                         return (host.Clone () as SortedList);
1137                                 }
1138                         }
1139
1140
1141
1142                         //
1143                         // SortedList overrides
1144                         //
1145
1146                         public override Object GetByIndex (int index)
1147                         {
1148                                 lock (host.SyncRoot) {
1149                                         return host.GetByIndex (index);
1150                                 }
1151                         }
1152
1153                         public override Object GetKey (int index)
1154                         {
1155                                 lock (host.SyncRoot) {
1156                                         return host.GetKey (index);
1157                                 }
1158                         }
1159
1160                         public override IList GetKeyList ()
1161                         {
1162                                 lock (host.SyncRoot) {
1163                                         return new ListKeys (host);
1164                                 }
1165                         }
1166
1167
1168                         public override IList GetValueList ()
1169                         {
1170                                 lock (host.SyncRoot) {
1171                                         return new ListValues (host);
1172                                 }
1173                         }
1174
1175                         public override void RemoveAt (int index)
1176                         {
1177                                 lock (host.SyncRoot) {
1178                                         host.RemoveAt (index);
1179                                 }
1180                         }
1181
1182                         public override int IndexOfKey (object key)
1183                         {
1184                                 lock (host.SyncRoot) {
1185                                         return host.IndexOfKey (key);
1186                                 }
1187                         }
1188
1189                         public override int IndexOfValue (Object val)
1190                         {
1191                                 lock (host.SyncRoot) {
1192                                         return host.IndexOfValue (val);
1193                                 }
1194                         }
1195
1196                         public override void SetByIndex (int index, object value)
1197                         {
1198                                 lock (host.SyncRoot) {
1199                                         host.SetByIndex (index, value);
1200                                 }
1201                         }
1202
1203                         public override void TrimToSize()
1204                         {
1205                                 lock (host.SyncRoot) {
1206                                         host.TrimToSize();
1207                                 }
1208                         }
1209
1210
1211                 } // SynchedSortedList
1212
1213         } // SortedList
1214
1215 } // System.Collections