mcs/class/referencesource/mscorlib/system/collections/sortedlist.cs

   1 // ==++==
   2 //
   3 //   Copyright (c) Microsoft Corporation.  All rights reserved.
   4 //
   5 // ==--==
   6 /*============================================================
   7 **
   8 ** Class:  SortedList
   9 **
  10 ** <OWNER>[....]</OWNER>
  11 **
  12 ** Purpose: A sorted dictionary.
  13 **
  14 **
  15 ===========================================================*/
  16 namespace System.Collections {
  17     using System;
  18     using System.Security.Permissions;
  19     using System.Diagnostics;
  20     using System.Diagnostics.CodeAnalysis;
  21     using System.Diagnostics.Contracts;
  22     using System.Globalization;
  23
  24     // The SortedList class implements a sorted list of keys and values. Entries in
  25     // a sorted list are sorted by their keys and are accessible both by key and by
  26     // index. The keys of a sorted list can be ordered either according to a
  27     // specific IComparer implementation given when the sorted list is
  28     // instantiated, or according to the IComparable implementation provided
  29     // by the keys themselves. In either case, a sorted list does not allow entries
  30     // with duplicate keys.
  31     //
  32     // A sorted list internally maintains two arrays that store the keys and
  33     // values of the entries. The capacity of a sorted list is the allocated
  34     // length of these internal arrays. As elements are added to a sorted list, the
  35     // capacity of the sorted list is automatically increased as required by
  36     // reallocating the internal arrays.  The capacity is never automatically
  37     // decreased, but users can call either TrimToSize or
  38     // Capacity explicitly.
  39     //
  40     // The GetKeyList and GetValueList methods of a sorted list
  41     // provides access to the keys and values of the sorted list in the form of
  42     // List implementations. The List objects returned by these
  43     // methods are aliases for the underlying sorted list, so modifications
  44     // made to those lists are directly reflected in the sorted list, and vice
  45     // versa.
  46     //
  47     // The SortedList class provides a convenient way to create a sorted
  48     // copy of another dictionary, such as a Hashtable. For example:
  49     //
  50     // Hashtable h = new Hashtable();
  51     // h.Add(...);
  52     // h.Add(...);
  53     // ...
  54     // SortedList s = new SortedList(h);
  55     //
  56     // The last line above creates a sorted list that contains a copy of the keys
  57     // and values stored in the hashtable. In this particular example, the keys
  58     // will be ordered according to the IComparable interface, which they
  59     // all must implement. To impose a different ordering, SortedList also
  60     // has a constructor that allows a specific IComparer implementation to
  61     // be specified.
  62     //
  63     [DebuggerTypeProxy(typeof(System.Collections.SortedList.SortedListDebugView))]
  64     [DebuggerDisplay("Count = {Count}")]
  65 [System.Runtime.InteropServices.ComVisible(true)]
  66 #if FEATURE_CORECLR
  67     [Obsolete("Non-generic collections have been deprecated. Please use collections in System.Collections.Generic.")]
  68 #endif
  69     [Serializable]
  70     public class SortedList : IDictionary, ICloneable
  71     {
  72         private Object[] keys;
  73         private Object[] values;
  74         private int _size;
  75         private int version;
  76         private IComparer comparer;
  77         private KeyList keyList;
  78         private ValueList valueList;
  79         [NonSerialized]
  80         private Object _syncRoot;
  81
  82         private const int _defaultCapacity = 16;
  83
  84         private static Object[] emptyArray = EmptyArray<Object>.Value;
  85
  86         // Constructs a new sorted list. The sorted list is initially empty and has
  87         // a capacity of zero. Upon adding the first element to the sorted list the
  88         // capacity is increased to 16, and then increased in multiples of two as
  89         // required. The elements of the sorted list are ordered according to the
  90         // IComparable interface, which must be implemented by the keys of
  91         // all entries added to the sorted list.
  92         public SortedList() {
  93             Init();
  94         }
  95         private void Init()
  96         {
  97             keys = emptyArray;
  98             values = emptyArray;
  99             _size = 0;
 100             comparer = new Comparer(CultureInfo.CurrentCulture);
 101         }
 102
 103         // Constructs a new sorted list. The sorted list is initially empty and has
 104         // a capacity of zero. Upon adding the first element to the sorted list the
 105         // capacity is increased to 16, and then increased in multiples of two as
 106         // required. The elements of the sorted list are ordered according to the
 107         // IComparable interface, which must be implemented by the keys of
 108         // all entries added to the sorted list.
 109         //
 110         public SortedList(int initialCapacity) {
 111             if (initialCapacity < 0)
 112                 throw new ArgumentOutOfRangeException("initialCapacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
 113             Contract.EndContractBlock();
 114             keys = new Object[initialCapacity];
 115             values = new Object[initialCapacity];
 116             comparer = new Comparer(CultureInfo.CurrentCulture);
 117         }
 118
 119         // Constructs a new sorted list with a given IComparer
 120         // implementation. The sorted list is initially empty and has a capacity of
 121         // zero. Upon adding the first element to the sorted list the capacity is
 122         // increased to 16, and then increased in multiples of two as required. The
 123         // elements of the sorted list are ordered according to the given
 124         // IComparer implementation. If comparer is null, the
 125         // elements are compared to each other using the IComparable
 126         // interface, which in that case must be implemented by the keys of all
 127         // entries added to the sorted list.
 128         //
 129         public SortedList(IComparer comparer)
 130             : this() {
 131             if (comparer != null) this.comparer = comparer;
 132         }
 133
 134         // Constructs a new sorted list with a given IComparer
 135         // implementation and a given initial capacity. The sorted list is
 136         // initially empty, but will have room for the given number of elements
 137         // before any reallocations are required. The elements of the sorted list
 138         // are ordered according to the given IComparer implementation. If
 139         // comparer is null, the elements are compared to each other using
 140         // the IComparable interface, which in that case must be implemented
 141         // by the keys of all entries added to the sorted list.
 142         //
 143         public SortedList(IComparer comparer, int capacity)
 144             : this(comparer) {
 145             Capacity = capacity;
 146         }
 147
 148         // Constructs a new sorted list containing a copy of the entries in the
 149         // given dictionary. The elements of the sorted list are ordered according
 150         // to the IComparable interface, which must be implemented by the
 151         // keys of all entries in the the given dictionary as well as keys
 152         // subsequently added to the sorted list.
 153         //
 154         public SortedList(IDictionary d)
 155             : this(d, null) {
 156         }
 157
 158         // Constructs a new sorted list containing a copy of the entries in the
 159         // given dictionary. The elements of the sorted list are ordered according
 160         // to the given IComparer implementation. If comparer is
 161         // null, the elements are compared to each other using the
 162         // IComparable interface, which in that case must be implemented
 163         // by the keys of all entries in the the given dictionary as well as keys
 164         // subsequently added to the sorted list.
 165         //
 166         public SortedList(IDictionary d, IComparer comparer)
 167             : this(comparer, (d != null ? d.Count : 0)) {
 168             if (d==null)
 169                 throw new ArgumentNullException("d", Environment.GetResourceString("ArgumentNull_Dictionary"));
 170             Contract.EndContractBlock();
 171             d.Keys.CopyTo(keys, 0);
 172             d.Values.CopyTo(values, 0);
 173             Array.Sort(keys, values, comparer);
 174             _size = d.Count;
 175         }
 176
 177         // Adds an entry with the given key and value to this sorted list. An
 178         // ArgumentException is thrown if the key is already present in the sorted list.
 179         //
 180         public virtual void Add(Object key, Object value) {
 181             if (key == null) throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
 182             Contract.EndContractBlock();
 183             int i = Array.BinarySearch(keys, 0, _size, key, comparer);
 184             if (i >= 0)
 185                 throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", GetKey(i), key));
 186             Insert(~i, key, value);
 187         }
 188
 189         // Returns the capacity of this sorted list. The capacity of a sorted list
 190         // represents the allocated length of the internal arrays used to store the
 191         // keys and values of the list, and thus also indicates the maximum number
 192         // of entries the list can contain before a reallocation of the internal
 193         // arrays is required.
 194         //
 195          public virtual int Capacity {
 196             get {
 197                 return keys.Length;
 198             }
 199             set {
 200                 if (value < Count) {
 201                     throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
 202                 }
 203                 Contract.EndContractBlock();
 204
 205                 if (value != keys.Length) {
 206                     if (value > 0) {
 207                         Object[] newKeys = new Object[value];
 208                         Object[] newValues = new Object[value];
 209                         if (_size > 0) {
 210                             Array.Copy(keys, 0, newKeys, 0, _size);
 211                             Array.Copy(values, 0, newValues, 0, _size);
 212                         }
 213                         keys = newKeys;
 214                         values = newValues;
 215                     }
 216                     else {
 217                         // size can only be zero here.
 218                         Contract.Assert( _size == 0, "Size is not zero");
 219                         keys = emptyArray;
 220                         values = emptyArray;
 221                     }
 222                 }
 223             }
 224         }
 225
 226         // Returns the number of entries in this sorted list.
 227         //
 228         public virtual int Count {
 229             get {
 230                 return _size;
 231             }
 232         }
 233
 234         // Returns a collection representing the keys of this sorted list. This
 235         // method returns the same object as GetKeyList, but typed as an
 236         // ICollection instead of an IList.
 237         //
 238          public virtual ICollection Keys {
 239             get {
 240                return GetKeyList();
 241             }
 242         }
 243
 244         // Returns a collection representing the values of this sorted list. This
 245         // method returns the same object as GetValueList, but typed as an
 246         // ICollection instead of an IList.
 247         //
 248          public virtual ICollection Values {
 249             get {
 250                 return GetValueList();
 251             }
 252         }
 253
 254         // Is this SortedList read-only?
 255         public virtual bool IsReadOnly {
 256             get { return false; }
 257         }
 258
 259         public virtual bool IsFixedSize {
 260             get { return false; }
 261         }
 262
 263         // Is this SortedList synchronized (thread-safe)?
 264         public virtual bool IsSynchronized {
 265             get { return false; }
 266         }
 267
 268         // Synchronization root for this object.
 269         public virtual Object SyncRoot {
 270             get {
 271                 if( _syncRoot == null) {
 272                     System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
 273                 }
 274                 return _syncRoot;
 275             }
 276         }
 277
 278         // Removes all entries from this sorted list.
 279         public virtual void Clear() {
 280             // clear does not change the capacity
 281             version++;
 282             Array.Clear(keys, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
 283             Array.Clear(values, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
 284             _size = 0;
 285
 286         }
 287
 288         // Makes a virtually identical copy of this SortedList.  This is a shallow
 289         // copy.  IE, the Objects in the SortedList are not cloned - we copy the
 290         // references to those objects.
 291         public virtual Object Clone()
 292         {
 293             SortedList sl = new SortedList(_size);
 294             Array.Copy(keys, 0, sl.keys, 0, _size);
 295             Array.Copy(values, 0, sl.values, 0, _size);
 296             sl._size = _size;
 297             sl.version = version;
 298             sl.comparer = comparer;
 299             // Don't copy keyList nor valueList.
 300             return sl;
 301         }
 302
 303
 304         // Checks if this sorted list contains an entry with the given key.
 305         //
 306         public virtual bool Contains(Object key) {
 307             return IndexOfKey(key) >= 0;
 308         }
 309
 310         // Checks if this sorted list contains an entry with the given key.
 311         //
 312         public virtual bool ContainsKey(Object key) {
 313             // Yes, this is a SPEC'ed duplicate of Contains().
 314             return IndexOfKey(key) >= 0;
 315         }
 316
 317         // Checks if this sorted list contains an entry with the given value. The
 318         // values of the entries of the sorted list are compared to the given value
 319         // using the Object.Equals method. This method performs a linear
 320         // search and is substantially slower than the Contains
 321         // method.
 322         //
 323         public virtual bool ContainsValue(Object value) {
 324             return IndexOfValue(value) >= 0;
 325         }
 326
 327         // Copies the values in this SortedList to an array.
 328         public virtual void CopyTo(Array array, int arrayIndex) {
 329             if (array == null)
 330                 throw new ArgumentNullException("array", Environment.GetResourceString("ArgumentNull_Array"));
 331             if (array.Rank != 1)
 332                 throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
 333             if (arrayIndex < 0)
 334                 throw new ArgumentOutOfRangeException("arrayIndex", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
 335             if (array.Length - arrayIndex < Count)
 336                 throw new ArgumentException(Environment.GetResourceString("Arg_ArrayPlusOffTooSmall"));
 337             Contract.EndContractBlock();
 338             for (int i = 0; i<Count; i++) {
 339                 DictionaryEntry entry = new DictionaryEntry(keys[i],values[i]);
 340                 array.SetValue(entry, i + arrayIndex);
 341             }
 342         }
 343
 344         // Copies the values in this SortedList to an KeyValuePairs array.
 345         // KeyValuePairs is different from Dictionary Entry in that it has special
 346         // debugger attributes on its fields.
 347
 348         internal virtual KeyValuePairs[] ToKeyValuePairsArray() {
 349             KeyValuePairs[] array = new KeyValuePairs[Count];
 350             for (int i = 0; i < Count; i++) {
 351                 array[i] = new KeyValuePairs(keys[i],values[i]);
 352             }
 353             return array;
 354         }
 355
 356         // Ensures that the capacity of this sorted list is at least the given
 357         // minimum value. If the currect capacity of the list is less than
 358         // min, the capacity is increased to twice the current capacity or
 359         // to min, whichever is larger.
 360         private void EnsureCapacity(int min) {
 361             int newCapacity = keys.Length == 0? 16: keys.Length * 2;
 362             // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
 363             // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
 364             if ((uint)newCapacity > Array_ReferenceSources.MaxArrayLength) newCapacity = Array_ReferenceSources.MaxArrayLength;
 365             if (newCapacity < min) newCapacity = min;
 366             Capacity = newCapacity;
 367         }
 368
 369         // Returns the value of the entry at the given index.
 370         //
 371         public virtual Object GetByIndex(int index) {
 372             if (index < 0 || index >= Count)
 373                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
 374             Contract.EndContractBlock();
 375             return values[index];
 376         }
 377
 378         // Returns an IEnumerator for this sorted list.  If modifications
 379         // made to the sorted list while an enumeration is in progress,
 380         // the MoveNext and Remove methods
 381         // of the enumerator will throw an exception.
 382         //
 383         IEnumerator IEnumerable.GetEnumerator() {
 384             return new SortedListEnumerator(this, 0, _size, SortedListEnumerator.DictEntry);
 385         }
 386
 387         // Returns an IDictionaryEnumerator for this sorted list.  If modifications
 388         // made to the sorted list while an enumeration is in progress,
 389         // the MoveNext and Remove methods
 390         // of the enumerator will throw an exception.
 391         //
 392         public virtual IDictionaryEnumerator GetEnumerator() {
 393             return new SortedListEnumerator(this, 0, _size, SortedListEnumerator.DictEntry);
 394         }
 395
 396         // Returns the key of the entry at the given index.
 397         //
 398         public virtual Object GetKey(int index) {
 399             if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
 400             Contract.EndContractBlock();
 401             return keys[index];
 402         }
 403
 404         // Returns an IList representing the keys of this sorted list. The
 405         // returned list is an alias for the keys of this sorted list, so
 406         // modifications made to the returned list are directly reflected in the
 407         // underlying sorted list, and vice versa. The elements of the returned
 408         // list are ordered in the same way as the elements of the sorted list. The
 409         // returned list does not support adding, inserting, or modifying elements
 410         // (the Add, AddRange, Insert, InsertRange,
 411         // Reverse, Set, SetRange, and Sort methods
 412         // throw exceptions), but it does allow removal of elements (through the
 413         // Remove and RemoveRange methods or through an enumerator).
 414         // Null is an invalid key value.
 415         //
 416         public virtual IList GetKeyList() {
 417             if (keyList == null) keyList = new KeyList(this);
 418             return keyList;
 419         }
 420
 421         // Returns an IList representing the values of this sorted list. The
 422         // returned list is an alias for the values of this sorted list, so
 423         // modifications made to the returned list are directly reflected in the
 424         // underlying sorted list, and vice versa. The elements of the returned
 425         // list are ordered in the same way as the elements of the sorted list. The
 426         // returned list does not support adding or inserting elements (the
 427         // Add, AddRange, Insert and InsertRange
 428         // methods throw exceptions), but it does allow modification and removal of
 429         // elements (through the Remove, RemoveRange, Set and
 430         // SetRange methods or through an enumerator).
 431         //
 432         public virtual IList GetValueList() {
 433             if (valueList == null) valueList = new ValueList(this);
 434             return valueList;
 435         }
 436
 437         // Returns the value associated with the given key. If an entry with the
 438         // given key is not found, the returned value is null.
 439         //
 440         public virtual Object this[Object key] {
 441             get {
 442                 int i = IndexOfKey(key);
 443                 if (i >= 0) return values[i];
 444                 return null;
 445             }
 446             set {
 447                 if (key == null) throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
 448                 Contract.EndContractBlock();
 449                 int i = Array.BinarySearch(keys, 0, _size, key, comparer);
 450                 if (i >= 0) {
 451                     values[i] = value;
 452                     version++;
 453                     return;
 454                 }
 455                 Insert(~i, key, value);
 456             }
 457         }
 458
 459         // Returns the index of the entry with a given key in this sorted list. The
 460         // key is located through a binary search, and thus the average execution
 461         // time of this method is proportional to Log2(size), where
 462         // size is the size of this sorted list. The returned value is -1 if
 463         // the given key does not occur in this sorted list. Null is an invalid
 464         // key value.
 465         //
 466         public virtual int IndexOfKey(Object key) {
 467             if (key == null)
 468                 throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
 469             Contract.EndContractBlock();
 470             int ret = Array.BinarySearch(keys, 0, _size, key, comparer);
 471             return ret >=0 ? ret : -1;
 472         }
 473
 474         // Returns the index of the first occurrence of an entry with a given value
 475         // in this sorted list. The entry is located through a linear search, and
 476         // thus the average execution time of this method is proportional to the
 477         // size of this sorted list. The elements of the list are compared to the
 478         // given value using the Object.Equals method.
 479         //
 480         public virtual int IndexOfValue(Object value) {
 481             return Array.IndexOf(values, value, 0, _size);
 482         }
 483
 484         // Inserts an entry with a given key and value at a given index.
 485         private void Insert(int index, Object key, Object value) {
 486             if (_size == keys.Length) EnsureCapacity(_size + 1);
 487             if (index < _size) {
 488                 Array.Copy(keys, index, keys, index + 1, _size - index);
 489                 Array.Copy(values, index, values, index + 1, _size - index);
 490             }
 491             keys[index] = key;
 492             values[index] = value;
 493             _size++;
 494             version++;
 495         }
 496
 497         // Removes the entry at the given index. The size of the sorted list is
 498         // decreased by one.
 499         //
 500         public virtual void RemoveAt(int index) {
 501             if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
 502             Contract.EndContractBlock();
 503             _size--;
 504             if (index < _size) {
 505                 Array.Copy(keys, index + 1, keys, index, _size - index);
 506                 Array.Copy(values, index + 1, values, index, _size - index);
 507             }
 508             keys[_size] = null;
 509             values[_size] = null;
 510             version++;
 511         }
 512
 513         // Removes an entry from this sorted list. If an entry with the specified
 514         // key exists in the sorted list, it is removed. An ArgumentException is
 515         // thrown if the key is null.
 516         //
 517         public virtual void Remove(Object key) {
 518             int i = IndexOfKey(key);
 519             if (i >= 0)
 520             RemoveAt(i);
 521         }
 522
 523         // Sets the value at an index to a given value.  The previous value of
 524         // the given entry is overwritten.
 525         //
 526         public virtual void SetByIndex(int index, Object value) {
 527             if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
 528             Contract.EndContractBlock();
 529             values[index] = value;
 530             version++;
 531         }
 532
 533         // Returns a thread-safe SortedList.
 534         //
 535         [HostProtection(Synchronization=true)]
 536         public static SortedList Synchronized(SortedList list) {
 537             if (list==null)
 538                 throw new ArgumentNullException("list");
 539             Contract.EndContractBlock();
 540             return new SyncSortedList(list);
 541         }
 542
 543         // Sets the capacity of this sorted list to the size of the sorted list.
 544         // This method can be used to minimize a sorted list's memory overhead once
 545         // it is known that no new elements will be added to the sorted list. To
 546         // completely clear a sorted list and release all memory referenced by the
 547         // sorted list, execute the following statements:
 548         //
 549         // sortedList.Clear();
 550         // sortedList.TrimToSize();
 551         //
 552         public virtual void TrimToSize() {
 553             Capacity = _size;
 554         }
 555
 556         [Serializable]
 557         private class SyncSortedList : SortedList
 558         {
 559             private SortedList _list;
 560             private Object _root;
 561
 562
 563             internal SyncSortedList(SortedList list) {
 564                 _list = list;
 565                 _root = list.SyncRoot;
 566             }
 567
 568             public override int Count {
 569                 get { lock(_root) { return _list.Count; } }
 570             }
 571
 572             public override Object SyncRoot {
 573                 get { return _root; }
 574             }
 575
 576             public override bool IsReadOnly {
 577                 get { return _list.IsReadOnly; }
 578             }
 579
 580             public override bool IsFixedSize {
 581                 get { return _list.IsFixedSize; }
 582             }
 583
 584
 585             public override bool IsSynchronized {
 586                 get { return true; }
 587             }
 588
 589             public override Object this[Object key] {
 590                 get {
 591                     lock(_root) {
 592                         return _list[key];
 593                     }
 594                 }
 595                 set {
 596                     lock(_root) {
 597                         _list[key] = value;
 598                     }
 599                 }
 600             }
 601
 602             public override void Add(Object key, Object value) {
 603                 lock(_root) {
 604                     _list.Add(key, value);
 605                 }
 606             }
 607
 608             public override int Capacity {
 609                 get{ lock(_root) {  return _list.Capacity; } }
 610             }
 611
 612             public override void Clear() {
 613                 lock(_root) {
 614                     _list.Clear();
 615                 }
 616             }
 617
 618             public override Object Clone() {
 619                 lock(_root) {
 620                     return _list.Clone();
 621                 }
 622             }
 623
 624             public override bool Contains(Object key) {
 625                 lock(_root) {
 626                     return _list.Contains(key);
 627                 }
 628             }
 629
 630             public override bool ContainsKey(Object key) {
 631                 lock(_root) {
 632                     return _list.ContainsKey(key);
 633                 }
 634             }
 635
 636             public override bool ContainsValue(Object key) {
 637                 lock(_root) {
 638                     return _list.ContainsValue(key);
 639                 }
 640             }
 641
 642             public override void CopyTo(Array array, int index) {
 643                 lock(_root) {
 644                     _list.CopyTo(array, index);
 645                 }
 646             }
 647
 648             [SuppressMessage("Microsoft.Contracts", "CC1055")]  // Skip extra error checking to avoid *potential* AppCompat problems.
 649             public override Object GetByIndex(int index) {
 650                 lock(_root) {
 651                     return _list.GetByIndex(index);
 652                 }
 653             }
 654
 655             public override IDictionaryEnumerator GetEnumerator() {
 656                 lock(_root) {
 657                     return _list.GetEnumerator();
 658                 }
 659             }
 660
 661             [SuppressMessage("Microsoft.Contracts", "CC1055")]  // Skip extra error checking to avoid *potential* AppCompat problems.
 662             public override Object GetKey(int index) {
 663                 lock(_root) {
 664                     return _list.GetKey(index);
 665                 }
 666             }
 667
 668             public override IList GetKeyList() {
 669                 lock(_root) {
 670                     return _list.GetKeyList();
 671                 }
 672             }
 673
 674             public override IList GetValueList() {
 675                 lock(_root) {
 676                     return _list.GetValueList();
 677                 }
 678             }
 679
 680             public override int IndexOfKey(Object key) {
 681                 if (key == null)
 682                     throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
 683                 Contract.EndContractBlock();
 684
 685                 lock(_root) {
 686                     return _list.IndexOfKey(key);
 687                 }
 688             }
 689
 690             [SuppressMessage("Microsoft.Contracts", "CC1055")]  // Skip extra error checking to avoid *potential* AppCompat problems.
 691             public override int IndexOfValue(Object value) {
 692                 lock(_root) {
 693                     return _list.IndexOfValue(value);
 694                 }
 695             }
 696
 697             [SuppressMessage("Microsoft.Contracts", "CC1055")]  // Skip extra error checking to avoid *potential* AppCompat problems.
 698             public override void RemoveAt(int index) {
 699                 lock(_root) {
 700                     _list.RemoveAt(index);
 701                 }
 702             }
 703
 704             public override void Remove(Object key) {
 705                 lock(_root) {
 706                     _list.Remove(key);
 707                 }
 708             }
 709
 710             [SuppressMessage("Microsoft.Contracts", "CC1055")]  // Skip extra error checking to avoid *potential* AppCompat problems.
 711             public override void SetByIndex(int index, Object value) {
 712                 lock(_root) {
 713                     _list.SetByIndex(index, value);
 714                 }
 715             }
 716
 717             internal override KeyValuePairs[] ToKeyValuePairsArray() {
 718                 return _list.ToKeyValuePairsArray();
 719             }
 720
 721             public override void TrimToSize() {
 722                 lock(_root) {
 723                     _list.TrimToSize();
 724                 }
 725             }
 726         }
 727
 728
 729         [Serializable]
 730         private class SortedListEnumerator : IDictionaryEnumerator, ICloneable
 731         {
 732             private SortedList sortedList;
 733             private Object key;
 734             private Object value;
 735             private int index;
 736             private int startIndex;        // Store for Reset.
 737             private int endIndex;
 738             private int version;
 739             private bool current;       // Is the current element valid?
 740             private int getObjectRetType;  // What should GetObject return?
 741
 742             internal const int Keys = 1;
 743             internal const int Values = 2;
 744             internal const int DictEntry = 3;
 745
 746             internal SortedListEnumerator(SortedList sortedList, int index, int count,
 747                                  int getObjRetType) {
 748                 this.sortedList = sortedList;
 749                 this.index = index;
 750                 startIndex = index;
 751                 endIndex = index + count;
 752                 version = sortedList.version;
 753                 getObjectRetType = getObjRetType;
 754                 current = false;
 755             }
 756
 757             public Object Clone()
 758             {
 759                 return MemberwiseClone();
 760             }
 761
 762             public virtual Object Key {
 763                 get {
 764                     if (version != sortedList.version) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
 765                     if (current == false) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumOpCantHappen"));
 766                     return key;
 767                 }
 768             }
 769
 770             public virtual bool MoveNext() {
 771                 if (version != sortedList.version) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
 772                 if (index < endIndex) {
 773                     key = sortedList.keys[index];
 774                     value = sortedList.values[index];
 775                     index++;
 776                     current = true;
 777                     return true;
 778                 }
 779                 key = null;
 780                 value = null;
 781                 current = false;
 782                 return false;
 783             }
 784
 785             public virtual DictionaryEntry Entry {
 786                 get {
 787                     if (version != sortedList.version) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
 788                     if (current == false) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumOpCantHappen"));
 789                     return new DictionaryEntry(key, value);
 790                 }
 791             }
 792
 793             public virtual Object Current {
 794                 get {
 795                     if (current == false) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumOpCantHappen"));
 796
 797                     if (getObjectRetType==Keys)
 798                         return key;
 799                     else if (getObjectRetType==Values)
 800                         return value;
 801                     else
 802                         return new DictionaryEntry(key, value);
 803                 }
 804             }
 805
 806             public virtual Object Value {
 807                 get {
 808                     if (version != sortedList.version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
 809                     if (current == false) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumOpCantHappen"));
 810                     return value;
 811                 }
 812             }
 813
 814             public virtual void Reset() {
 815                 if (version != sortedList.version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
 816                 index = startIndex;
 817                 current = false;
 818                 key = null;
 819                 value = null;
 820             }
 821         }
 822
 823         [Serializable]
 824         private class KeyList : IList
 825         {
 826             private SortedList sortedList;
 827
 828             internal KeyList(SortedList sortedList) {
 829                 this.sortedList = sortedList;
 830             }
 831
 832             public virtual int Count {
 833                 get { return sortedList._size; }
 834             }
 835
 836             public virtual bool IsReadOnly {
 837                 get { return true; }
 838             }
 839
 840             public virtual bool IsFixedSize {
 841                 get { return true; }
 842             }
 843
 844             public virtual bool IsSynchronized {
 845                 get { return sortedList.IsSynchronized; }
 846             }
 847
 848             public virtual Object SyncRoot {
 849                 get { return sortedList.SyncRoot; }
 850             }
 851
 852             public virtual int Add(Object key) {
 853                 throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite));
 854                 //            return 0; // suppress compiler warning
 855             }
 856
 857             public virtual void Clear() {
 858                 throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite));
 859             }
 860
 861             public virtual bool Contains(Object key) {
 862                 return sortedList.Contains(key);
 863             }
 864
 865             public virtual void CopyTo(Array array, int arrayIndex) {
 866                 if (array != null && array.Rank != 1)
 867                     throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
 868                 Contract.EndContractBlock();
 869
 870                 // defer error checking to Array.Copy
 871                 Array.Copy(sortedList.keys, 0, array, arrayIndex, sortedList.Count);
 872             }
 873
 874             public virtual void Insert(int index, Object value) {
 875                 throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite));
 876             }
 877
 878             public virtual Object this[int index] {
 879                 get {
 880                     return sortedList.GetKey(index);
 881                 }
 882                 set {
 883                     throw new NotSupportedException(Environment.GetResourceString("NotSupported_KeyCollectionSet"));
 884                 }
 885             }
 886
 887             public virtual IEnumerator GetEnumerator() {
 888                 return new SortedListEnumerator(sortedList, 0, sortedList.Count, SortedListEnumerator.Keys);
 889             }
 890
 891             public virtual int IndexOf(Object key) {
 892                 if (key==null)
 893                     throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
 894                 Contract.EndContractBlock();
 895
 896                 int i = Array.BinarySearch(sortedList.keys, 0,
 897                                            sortedList.Count, key, sortedList.comparer);
 898                 if (i >= 0) return i;
 899                 return -1;
 900             }
 901
 902             public virtual void Remove(Object key) {
 903                 throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite));
 904             }
 905
 906             public virtual void RemoveAt(int index) {
 907                 throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite));
 908             }
 909         }
 910
 911         [Serializable]
 912         private class ValueList : IList
 913         {
 914             private SortedList sortedList;
 915
 916             internal ValueList(SortedList sortedList) {
 917                 this.sortedList = sortedList;
 918             }
 919
 920             public virtual int Count {
 921                 get { return sortedList._size; }
 922             }
 923
 924             public virtual bool IsReadOnly {
 925                 get { return true; }
 926             }
 927
 928             public virtual bool IsFixedSize {
 929                 get { return true; }
 930             }
 931
 932             public virtual bool IsSynchronized {
 933                 get { return sortedList.IsSynchronized; }
 934             }
 935
 936             public virtual Object SyncRoot {
 937                 get { return sortedList.SyncRoot; }
 938             }
 939
 940             public virtual int Add(Object key) {
 941                 throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite));
 942             }
 943
 944             public virtual void Clear() {
 945                 throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite));
 946             }
 947
 948             public virtual bool Contains(Object value) {
 949                 return sortedList.ContainsValue(value);
 950             }
 951
 952             public virtual void CopyTo(Array array, int arrayIndex) {
 953                 if (array != null && array.Rank != 1)
 954                     throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
 955                 Contract.EndContractBlock();
 956
 957                 // defer error checking to Array.Copy
 958                 Array.Copy(sortedList.values, 0, array, arrayIndex, sortedList.Count);
 959             }
 960
 961             public virtual void Insert(int index, Object value) {
 962                 throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite));
 963             }
 964
 965             public virtual Object this[int index] {
 966                 get {
 967                     return sortedList.GetByIndex(index);
 968                 }
 969                 set {
 970                     throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite));
 971                 }
 972             }
 973
 974             public virtual IEnumerator GetEnumerator() {
 975                 return new SortedListEnumerator(sortedList, 0, sortedList.Count, SortedListEnumerator.Values);
 976             }
 977
 978             public virtual int IndexOf(Object value) {
 979                 return Array.IndexOf(sortedList.values, value, 0, sortedList.Count);
 980             }
 981
 982             public virtual void Remove(Object value) {
 983                 throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite));
 984             }
 985
 986             public virtual void RemoveAt(int index) {
 987                 throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite));
 988             }
 989
 990         }
 991
 992         // internal debug view class for sorted list
 993         internal class SortedListDebugView {
 994             private SortedList sortedList;
 995
 996             public SortedListDebugView( SortedList sortedList) {
 997                 if( sortedList == null) {
 998                     throw new ArgumentNullException("sortedList");
 999                 }
1000                 Contract.EndContractBlock();
1001
1002                 this.sortedList = sortedList;
1003             }
1004
1005             [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
1006             public KeyValuePairs[] Items {
1007                 get {
1008                     return sortedList.ToKeyValuePairsArray();
1009                 }
1010             }
1011         }
1012     }
1013 }