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