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