2 // System.Collections.SortedList.cs
5 // Sergey Chaban (serge@wildwestsoftware.com)
6 // Duncan Mak (duncan@ximian.com)
7 // Herve Poussineau (hpoussineau@fr.st
11 // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
13 // Permission is hereby granted, free of charge, to any person obtaining
14 // a copy of this software and associated documentation files (the
15 // "Software"), to deal in the Software without restriction, including
16 // without limitation the rights to use, copy, modify, merge, publish,
17 // distribute, sublicense, and/or sell copies of the Software, and to
18 // permit persons to whom the Software is furnished to do so, subject to
19 // the following conditions:
21 // The above copyright notice and this permission notice shall be
22 // included in all copies or substantial portions of the Software.
24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 using System.Globalization;
34 using System.Runtime.InteropServices;
36 namespace System.Collections {
39 /// Represents a collection of associated keys and values
40 /// that are sorted by the keys and are accessible by key
47 public class SortedList : IDictionary, ICollection,
48 IEnumerable, ICloneable {
52 internal struct Slot {
54 internal Object value;
57 private readonly static int INITIAL_SIZE = 16;
59 private enum EnumeratorMode : int { KEY_MODE = 0, VALUE_MODE, ENTRY_MODE }
62 private int modificationCount;
64 private IComparer comparer;
65 private int defaultCapacity;
71 : this (null, INITIAL_SIZE)
75 public SortedList (int initialCapacity)
76 : this (null, initialCapacity)
80 public SortedList (IComparer comparer, int initialCapacity)
82 if (initialCapacity < 0)
83 throw new ArgumentOutOfRangeException ("initialCapacity");
85 if (initialCapacity == 0)
88 defaultCapacity = INITIAL_SIZE;
90 this.comparer = comparer;
91 InitTable (initialCapacity, true);
94 public SortedList (IComparer comparer)
96 this.comparer = comparer;
97 InitTable (INITIAL_SIZE, true);
101 public SortedList (IDictionary d) : this (d, null)
105 // LAMESPEC: MSDN docs talk about an InvalidCastException but
106 // I wasn't able to duplicate such a case in the unit tests.
107 public SortedList (IDictionary d, IComparer comparer)
110 throw new ArgumentNullException ("dictionary");
112 InitTable (d.Count, true);
113 this.comparer = comparer;
115 IDictionaryEnumerator it = d.GetEnumerator ();
116 while (it.MoveNext ()) {
117 Add (it.Key, it.Value);
127 public virtual int Count {
133 public virtual bool IsSynchronized {
139 public virtual Object SyncRoot {
148 public virtual bool IsFixedSize {
155 public virtual bool IsReadOnly {
161 public virtual ICollection Keys {
163 return new ListKeys (this);
167 public virtual ICollection Values {
169 return new ListValues (this);
175 public virtual Object this [Object key] {
178 throw new ArgumentNullException();
179 return GetImpl (key);
183 throw new ArgumentNullException();
185 throw new NotSupportedException("SortedList is Read Only.");
186 if (Find(key) < 0 && IsFixedSize)
187 throw new NotSupportedException("Key not found and SortedList is fixed size.");
189 PutImpl (key, value, true);
193 public virtual int Capacity {
199 int current = this.table.Length;
202 throw new ArgumentOutOfRangeException("capacity too small");
204 else if (value == 0) {
205 // return to default size
206 Slot [] newTable = new Slot [defaultCapacity];
207 Array.Copy (table, newTable, inUse);
208 this.table = newTable;
211 else if (current > defaultCapacity && value < current) {
212 Slot [] newTable = new Slot [defaultCapacity];
213 Array.Copy (table, newTable, inUse);
214 this.table = newTable;
217 else if (value > inUse) {
218 Slot [] newTable = new Slot [value];
219 Array.Copy (table, newTable, inUse);
220 this.table = newTable;
222 else if (value > current) {
223 Slot [] newTable = new Slot [value];
224 Array.Copy (table, newTable, current);
225 this.table = newTable;
231 // Public instance methods.
236 IEnumerator IEnumerable.GetEnumerator ()
238 return new Enumerator (this, EnumeratorMode.ENTRY_MODE);
244 public virtual void Add (object key, object value)
246 PutImpl (key, value, false);
250 public virtual void Clear ()
252 defaultCapacity = INITIAL_SIZE;
253 this.table = new Slot [defaultCapacity];
258 public virtual bool Contains (object key)
261 throw new ArgumentNullException();
264 return (Find (key) >= 0);
265 } catch (Exception) {
266 throw new InvalidOperationException();
271 public virtual IDictionaryEnumerator GetEnumerator ()
273 return new Enumerator (this, EnumeratorMode.ENTRY_MODE);
276 public virtual void Remove (object key)
278 int i = IndexOfKey (key);
279 if (i >= 0) RemoveAt (i);
285 public virtual void CopyTo (Array array, int arrayIndex)
288 throw new ArgumentNullException();
291 throw new ArgumentOutOfRangeException();
294 throw new ArgumentException("array is multi-dimensional");
295 if (arrayIndex >= array.Length)
296 throw new ArgumentNullException("arrayIndex is greater than or equal to array.Length");
297 if (Count > (array.Length - arrayIndex))
298 throw new ArgumentNullException("Not enough space in array from arrayIndex to end of array");
300 IDictionaryEnumerator it = GetEnumerator ();
303 while (it.MoveNext ()) {
304 array.SetValue (it.Entry, i++);
312 public virtual object Clone ()
314 SortedList sl = new SortedList (this, comparer);
315 sl.modificationCount = this.modificationCount;
326 public virtual IList GetKeyList ()
328 return new ListKeys (this);
332 public virtual IList GetValueList ()
334 return new ListValues (this);
338 public virtual void RemoveAt (int index)
340 Slot [] table = this.table;
342 if (index >= 0 && index < cnt) {
343 if (index != cnt - 1) {
344 Array.Copy (table, index+1, table, index, cnt-1-index);
346 table [index].key = null;
347 table [index].value = null;
352 throw new ArgumentOutOfRangeException("index out of range");
356 public virtual int IndexOfKey (object key)
359 throw new ArgumentNullException();
364 } catch (Exception) {
365 throw new InvalidOperationException();
368 return (indx | (indx >> 31));
372 public virtual int IndexOfValue (object value)
377 for (int i = 0; i < inUse; i ++) {
378 Slot current = this.table [i];
380 if (Equals (value, current.value))
388 public virtual bool ContainsKey (object key)
391 throw new ArgumentNullException();
394 return Contains (key);
395 } catch (Exception) {
396 throw new InvalidOperationException();
401 public virtual bool ContainsValue (object value)
403 return IndexOfValue (value) >= 0;
407 public virtual object GetByIndex (int index)
409 if (index >= 0 && index < Count)
410 return table [index].value;
413 throw new ArgumentOutOfRangeException("index out of range");
417 public virtual void SetByIndex (int index, object value)
419 if (index >= 0 && index < Count)
420 table [index].value = value;
423 throw new ArgumentOutOfRangeException("index out of range");
427 public virtual object GetKey (int index)
429 if (index >= 0 && index < Count)
430 return table [index].key;
433 throw new ArgumentOutOfRangeException("index out of range");
436 public static SortedList Synchronized (SortedList list)
439 throw new ArgumentNullException (Locale.GetText ("Base list is null."));
441 return new SynchedSortedList (list);
444 public virtual void TrimToSize ()
447 // Trimming an empty SortedList sets the capacity
448 // of the SortedList to the default capacity,
451 Resize (defaultCapacity, false);
453 Resize (Count, true);
462 private void Resize (int n, bool copy)
464 Slot [] table = this.table;
465 Slot [] newTable = new Slot [n];
466 if (copy) Array.Copy (table, 0, newTable, 0, n);
467 this.table = newTable;
471 private void EnsureCapacity (int n, int free)
473 Slot [] table = this.table;
474 Slot [] newTable = null;
476 bool gap = (free >=0 && free < Count);
479 newTable = new Slot [n << 1];
482 if (newTable != null) {
486 Array.Copy (table, 0, newTable, 0, copyLen);
488 copyLen = Count - free;
490 Array.Copy (table, free, newTable, free+1, copyLen);
493 // Just a resizing, copy the entire table.
494 Array.Copy (table, newTable, Count);
496 this.table = newTable;
498 Array.Copy (table, free, table, free+1, Count - free);
503 private void PutImpl (object key, object value, bool overwrite)
506 throw new ArgumentNullException ("null key");
508 Slot [] table = this.table;
513 freeIndx = Find (key);
514 } catch (Exception) {
515 throw new InvalidOperationException();
520 string msg = Locale.GetText ("Key '{0}' already exists in list.", key);
521 throw new ArgumentException (msg);
524 table [freeIndx].value = value;
529 freeIndx = ~freeIndx;
531 if (freeIndx > Capacity + 1)
532 throw new Exception ("SortedList::internal error ("+key+", "+value+") at ["+freeIndx+"]");
535 EnsureCapacity (Count+1, freeIndx);
538 table [freeIndx].key = key;
539 table [freeIndx].value = value;
547 private object GetImpl (object key)
552 return table [i].value;
557 private void InitTable (int capacity, bool forceSize)
559 if (!forceSize && (capacity < defaultCapacity))
560 capacity = defaultCapacity;
561 this.table = new Slot [capacity];
563 this.modificationCount = 0;
566 private void CopyToArray (Array arr, int i,
570 throw new ArgumentNullException ("arr");
572 if (i < 0 || i + this.Count > arr.Length)
573 throw new ArgumentOutOfRangeException ("i");
575 IEnumerator it = new Enumerator (this, mode);
577 while (it.MoveNext ()) {
578 arr.SetValue (it.Current, i++);
583 private int Find (object key)
585 Slot [] table = this.table;
588 if (len == 0) return ~0;
590 IComparer comparer = (this.comparer == null)
597 while (left <= right) {
598 int guess = (left + right) >> 1;
600 int cmp = comparer.Compare (key, table[guess].key);
601 if (cmp == 0) return guess;
603 if (cmp > 0) left = guess+1;
604 else right = guess-1;
617 private sealed class Enumerator : ICloneable, IDictionaryEnumerator, IEnumerator {
619 private SortedList host;
623 private EnumeratorMode mode;
625 private object currentKey;
626 private object currentValue;
628 bool invalid = false;
630 private readonly static string xstr = "SortedList.Enumerator: snapshot out of sync.";
632 public Enumerator (SortedList host, EnumeratorMode mode)
635 stamp = host.modificationCount;
641 public Enumerator (SortedList host)
642 : this (host, EnumeratorMode.ENTRY_MODE)
648 if (host.modificationCount != stamp || invalid)
649 throw new InvalidOperationException (xstr);
656 public bool MoveNext ()
658 if (host.modificationCount != stamp || invalid)
659 throw new InvalidOperationException (xstr);
661 Slot [] table = host.table;
664 Slot entry = table [pos];
666 currentKey = entry.key;
667 currentValue = entry.value;
676 public DictionaryEntry Entry
679 if (invalid || pos >= size || pos == -1)
680 throw new InvalidOperationException (xstr);
682 return new DictionaryEntry (currentKey,
689 if (invalid || pos >= size || pos == -1)
690 throw new InvalidOperationException (xstr);
695 public Object Value {
697 if (invalid || pos >= size || pos == -1)
698 throw new InvalidOperationException (xstr);
703 public Object Current {
705 if (invalid || pos >= size || pos == -1)
706 throw new InvalidOperationException (xstr);
709 case EnumeratorMode.KEY_MODE:
711 case EnumeratorMode.VALUE_MODE:
713 case EnumeratorMode.ENTRY_MODE:
717 throw new NotSupportedException (mode + " is not a supported mode.");
724 public object Clone ()
726 Enumerator e = new Enumerator (host, mode);
730 e.currentKey = currentKey;
731 e.currentValue = currentValue;
738 private class ListKeys : IList, IEnumerable {
740 private SortedList host;
743 public ListKeys (SortedList host)
746 throw new ArgumentNullException ();
755 public virtual int Count {
761 public virtual bool IsSynchronized {
763 return host.IsSynchronized;
767 public virtual Object SyncRoot {
769 return host.SyncRoot;
773 public virtual void CopyTo (Array array, int arrayIndex)
775 host.CopyToArray (array, arrayIndex, EnumeratorMode.KEY_MODE);
783 public virtual bool IsFixedSize {
789 public virtual bool IsReadOnly {
796 public virtual object this [int index] {
798 return host.GetKey (index);
801 throw new NotSupportedException("attempt to modify a key");
805 public virtual int Add (object value)
807 throw new NotSupportedException("IList::Add not supported");
810 public virtual void Clear ()
812 throw new NotSupportedException("IList::Clear not supported");
815 public virtual bool Contains (object key)
817 return host.Contains (key);
821 public virtual int IndexOf (object key)
823 return host.IndexOfKey (key);
827 public virtual void Insert (int index, object value)
829 throw new NotSupportedException("IList::Insert not supported");
833 public virtual void Remove (object value)
835 throw new NotSupportedException("IList::Remove not supported");
839 public virtual void RemoveAt (int index)
841 throw new NotSupportedException("IList::RemoveAt not supported");
849 public virtual IEnumerator GetEnumerator ()
851 return new SortedList.Enumerator (host, EnumeratorMode.KEY_MODE);
858 private class ListValues : IList, IEnumerable {
860 private SortedList host;
863 public ListValues (SortedList host)
866 throw new ArgumentNullException ();
875 public virtual int Count {
881 public virtual bool IsSynchronized {
883 return host.IsSynchronized;
887 public virtual Object SyncRoot {
889 return host.SyncRoot;
893 public virtual void CopyTo (Array array, int arrayIndex)
895 host.CopyToArray (array, arrayIndex, EnumeratorMode.VALUE_MODE);
903 public virtual bool IsFixedSize {
909 public virtual bool IsReadOnly {
916 public virtual object this [int index] {
918 return host.GetByIndex (index);
921 throw new NotSupportedException("This operation is not supported on GetValueList return");
925 public virtual int Add (object value)
927 throw new NotSupportedException("IList::Add not supported");
930 public virtual void Clear ()
932 throw new NotSupportedException("IList::Clear not supported");
935 public virtual bool Contains (object value)
937 return host.ContainsValue (value);
941 public virtual int IndexOf (object value)
943 return host.IndexOfValue (value);
947 public virtual void Insert (int index, object value)
949 throw new NotSupportedException("IList::Insert not supported");
953 public virtual void Remove (object value)
955 throw new NotSupportedException("IList::Remove not supported");
959 public virtual void RemoveAt (int index)
961 throw new NotSupportedException("IList::RemoveAt not supported");
969 public virtual IEnumerator GetEnumerator ()
971 return new SortedList.Enumerator (host, EnumeratorMode.VALUE_MODE);
976 private class SynchedSortedList : SortedList {
978 private SortedList host;
980 public SynchedSortedList (SortedList host)
983 throw new ArgumentNullException ();
987 public override int Capacity {
989 lock (host.SyncRoot) {
990 return host.Capacity;
994 lock (host.SyncRoot) {
995 host.Capacity = value;
1002 public override int Count {
1008 public override bool IsSynchronized {
1014 public override Object SyncRoot {
1016 return host.SyncRoot;
1024 public override bool IsFixedSize {
1026 return host.IsFixedSize;
1031 public override bool IsReadOnly {
1033 return host.IsReadOnly;
1037 public override ICollection Keys {
1039 ICollection keys = null;
1040 lock (host.SyncRoot) {
1047 public override ICollection Values {
1049 ICollection vals = null;
1050 lock (host.SyncRoot) {
1059 public override Object this [object key] {
1061 lock (host.SyncRoot) {
1062 return host.GetImpl (key);
1066 lock (host.SyncRoot) {
1067 host.PutImpl (key, value, true);
1076 public override void CopyTo (Array array, int arrayIndex)
1078 lock (host.SyncRoot) {
1079 host.CopyTo (array, arrayIndex);
1086 public override void Add (object key, object value)
1088 lock (host.SyncRoot) {
1089 host.PutImpl (key, value, false);
1093 public override void Clear ()
1095 lock (host.SyncRoot) {
1100 public override bool Contains (object key)
1102 lock (host.SyncRoot) {
1103 return (host.Find (key) >= 0);
1107 public override IDictionaryEnumerator GetEnumerator ()
1109 lock (host.SyncRoot) {
1110 return host.GetEnumerator();
1114 public override void Remove (object key)
1116 lock (host.SyncRoot) {
1123 public override bool ContainsKey (object key)
1125 lock (host.SyncRoot) {
1126 return host.Contains (key);
1130 public override bool ContainsValue (object value)
1132 lock (host.SyncRoot) {
1133 return host.ContainsValue (value);
1140 public override object Clone ()
1142 lock (host.SyncRoot) {
1143 return (host.Clone () as SortedList);
1150 // SortedList overrides
1153 public override Object GetByIndex (int index)
1155 lock (host.SyncRoot) {
1156 return host.GetByIndex (index);
1160 public override Object GetKey (int index)
1162 lock (host.SyncRoot) {
1163 return host.GetKey (index);
1167 public override IList GetKeyList ()
1169 lock (host.SyncRoot) {
1170 return new ListKeys (host);
1175 public override IList GetValueList ()
1177 lock (host.SyncRoot) {
1178 return new ListValues (host);
1182 public override void RemoveAt (int index)
1184 lock (host.SyncRoot) {
1185 host.RemoveAt (index);
1189 public override int IndexOfKey (object key)
1191 lock (host.SyncRoot) {
1192 return host.IndexOfKey (key);
1196 public override int IndexOfValue (Object val)
1198 lock (host.SyncRoot) {
1199 return host.IndexOfValue (val);
1203 public override void SetByIndex (int index, object value)
1205 lock (host.SyncRoot) {
1206 host.SetByIndex (index, value);
1210 public override void TrimToSize()
1212 lock (host.SyncRoot) {
1218 } // SynchedSortedList
1222 } // System.Collections