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