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

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