2 // System.Collections.Generic.SortedList.cs
5 // Sergey Chaban (serge@wildwestsoftware.com)
6 // Duncan Mak (duncan@ximian.com)
7 // Herve Poussineau (hpoussineau@fr.st
8 // Zoltan Varga (vargaz@gmail.com)
12 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
14 // Permission is hereby granted, free of charge, to any person obtaining
15 // a copy of this software and associated documentation files (the
16 // "Software"), to deal in the Software without restriction, including
17 // without limitation the rights to use, copy, modify, merge, publish,
18 // distribute, sublicense, and/or sell copies of the Software, and to
19 // permit persons to whom the Software is furnished to do so, subject to
20 // the following conditions:
22 // The above copyright notice and this permission notice shall be
23 // included in all copies or substantial portions of the Software.
25 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
26 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
27 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
28 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
29 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
30 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
31 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 using System.Collections;
36 using System.Globalization;
37 using System.Runtime.InteropServices;
38 using System.Diagnostics;
40 namespace System.Collections.Generic
43 /// Represents a collection of associated keys and values
44 /// that are sorted by the keys and are accessible by key
49 [DebuggerDisplay ("Count={Count}")]
50 [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
51 public class SortedList<TKey, TValue> : IDictionary<TKey, TValue>,
54 ICollection<KeyValuePair<TKey, TValue>>,
55 IEnumerable<KeyValuePair<TKey, TValue>>,
58 private readonly static int INITIAL_SIZE = 16;
60 private enum EnumeratorMode : int { KEY_MODE = 0, VALUE_MODE, ENTRY_MODE }
63 private int modificationCount;
64 private KeyValuePair<TKey, TValue>[] table;
65 private IComparer<TKey> comparer;
66 private int defaultCapacity;
72 : this (INITIAL_SIZE, null)
76 public SortedList (int capacity)
77 : this (capacity, null)
81 public SortedList (int capacity, IComparer<TKey> comparer)
84 throw new ArgumentOutOfRangeException ("initialCapacity");
89 defaultCapacity = INITIAL_SIZE;
90 Init (comparer, capacity, true);
93 public SortedList (IComparer<TKey> comparer) : this (INITIAL_SIZE, comparer)
97 public SortedList (IDictionary<TKey, TValue> dictionary) : this (dictionary, null)
101 public SortedList (IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer)
103 if (dictionary == null)
104 throw new ArgumentNullException ("dictionary");
106 Init (comparer, dictionary.Count, true);
108 foreach (KeyValuePair<TKey, TValue> kvp in dictionary)
109 Add (kvp.Key, kvp.Value);
124 bool ICollection.IsSynchronized {
130 Object ICollection.SyncRoot {
138 bool IDictionary.IsFixedSize {
144 bool IDictionary.IsReadOnly {
150 public TValue this [TKey key] {
153 throw new ArgumentNullException("key");
158 return table [i].Value;
160 throw new KeyNotFoundException ();
164 throw new ArgumentNullException("key");
166 PutImpl (key, value, true);
170 object IDictionary.this [object key] {
175 return this [(TKey)key];
179 this [ToKey (key)] = ToValue (value);
183 public int Capacity {
189 int current = this.table.Length;
192 throw new ArgumentOutOfRangeException("capacity too small");
194 else if (value == 0) {
195 // return to default size
196 KeyValuePair<TKey, TValue> [] newTable = new KeyValuePair<TKey, TValue> [defaultCapacity];
197 Array.Copy (table, newTable, inUse);
198 this.table = newTable;
201 else if (current > defaultCapacity && value < current) {
202 KeyValuePair<TKey, TValue> [] newTable = new KeyValuePair<TKey, TValue> [defaultCapacity];
203 Array.Copy (table, newTable, inUse);
204 this.table = newTable;
207 else if (value > inUse) {
208 KeyValuePair<TKey, TValue> [] newTable = new KeyValuePair<TKey, TValue> [value];
209 Array.Copy (table, newTable, inUse);
210 this.table = newTable;
212 else if (value > current) {
213 KeyValuePair<TKey, TValue> [] newTable = new KeyValuePair<TKey, TValue> [value];
214 Array.Copy (table, newTable, current);
215 this.table = newTable;
220 public IList<TKey> Keys {
222 return new ListKeys (this);
226 public IList<TValue> Values {
228 return new ListValues (this);
232 ICollection IDictionary.Keys {
234 return new ListKeys (this);
238 ICollection IDictionary.Values {
240 return new ListValues (this);
244 ICollection<TKey> IDictionary<TKey, TValue>.Keys {
250 ICollection<TValue> IDictionary<TKey, TValue>.Values {
256 public IComparer<TKey> Comparer {
262 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
269 // Public instance methods.
272 public void Add (TKey key, TValue value)
275 throw new ArgumentNullException ("key");
277 PutImpl (key, value, false);
280 public bool ContainsKey (TKey key)
283 throw new ArgumentNullException ("key");
285 return (Find (key) >= 0);
288 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator ()
290 for (int i = 0; i < inUse; i ++) {
291 KeyValuePair<TKey, TValue> current = this.table [i];
293 yield return new KeyValuePair<TKey, TValue> (current.Key, current.Value);
297 public bool Remove (TKey key)
300 throw new ArgumentNullException ("key");
302 int i = IndexOfKey (key);
311 // ICollection<KeyValuePair<TKey, TValue>>
313 void ICollection<KeyValuePair<TKey, TValue>>.Clear ()
315 defaultCapacity = INITIAL_SIZE;
316 this.table = new KeyValuePair<TKey, TValue> [defaultCapacity];
323 defaultCapacity = INITIAL_SIZE;
324 this.table = new KeyValuePair<TKey, TValue> [defaultCapacity];
329 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue>[] array, int arrayIndex)
335 throw new ArgumentNullException();
338 throw new ArgumentOutOfRangeException();
340 if (arrayIndex >= array.Length)
341 throw new ArgumentNullException("arrayIndex is greater than or equal to array.Length");
342 if (Count > (array.Length - arrayIndex))
343 throw new ArgumentNullException("Not enough space in array from arrayIndex to end of array");
346 foreach (KeyValuePair<TKey, TValue> pair in this)
350 void ICollection<KeyValuePair<TKey, TValue>>.Add (KeyValuePair<TKey, TValue> keyValuePair) {
351 Add (keyValuePair.Key, keyValuePair.Value);
354 bool ICollection<KeyValuePair<TKey, TValue>>.Contains (KeyValuePair<TKey, TValue> keyValuePair) {
355 int i = Find (keyValuePair.Key);
358 return Comparer<KeyValuePair<TKey, TValue>>.Default.Compare (table [i], keyValuePair) == 0;
363 bool ICollection<KeyValuePair<TKey, TValue>>.Remove (KeyValuePair<TKey, TValue> keyValuePair) {
364 int i = Find (keyValuePair.Key);
366 if (i >= 0 && (Comparer<KeyValuePair<TKey, TValue>>.Default.Compare (table [i], keyValuePair) == 0)) {
374 // IEnumerable<KeyValuePair<TKey, TValue>>
376 IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator ()
378 for (int i = 0; i < inUse; i ++) {
379 KeyValuePair<TKey, TValue> current = this.table [i];
381 yield return new KeyValuePair<TKey, TValue> (current.Key, current.Value);
387 IEnumerator IEnumerable.GetEnumerator ()
389 return GetEnumerator ();
394 void IDictionary.Add (object key, object value)
396 PutImpl (ToKey (key), ToValue (value), false);
399 bool IDictionary.Contains (object key)
402 throw new ArgumentNullException();
406 return (Find ((TKey)key) >= 0);
409 IDictionaryEnumerator IDictionary.GetEnumerator ()
411 return new Enumerator (this, EnumeratorMode.ENTRY_MODE);
414 void IDictionary.Remove (object key)
417 throw new ArgumentNullException ("key");
420 int i = IndexOfKey ((TKey)key);
421 if (i >= 0) RemoveAt (i);
426 void ICollection.CopyTo (Array array, int arrayIndex)
432 throw new ArgumentNullException();
435 throw new ArgumentOutOfRangeException();
438 throw new ArgumentException("array is multi-dimensional");
439 if (arrayIndex >= array.Length)
440 throw new ArgumentNullException("arrayIndex is greater than or equal to array.Length");
441 if (Count > (array.Length - arrayIndex))
442 throw new ArgumentNullException("Not enough space in array from arrayIndex to end of array");
444 IEnumerator<KeyValuePair<TKey,TValue>> it = GetEnumerator ();
447 while (it.MoveNext ()) {
448 array.SetValue (it.Current, i++);
453 // SortedList<TKey, TValue>
456 public void RemoveAt (int index)
458 KeyValuePair<TKey, TValue> [] table = this.table;
460 if (index >= 0 && index < cnt) {
461 if (index != cnt - 1) {
462 Array.Copy (table, index+1, table, index, cnt-1-index);
464 table [index] = default (KeyValuePair <TKey, TValue>);
469 throw new ArgumentOutOfRangeException("index out of range");
473 public int IndexOfKey (TKey key)
476 throw new ArgumentNullException ("key");
481 } catch (Exception) {
482 throw new InvalidOperationException();
485 return (indx | (indx >> 31));
488 public int IndexOfValue (TValue value)
493 for (int i = 0; i < inUse; i ++) {
494 KeyValuePair<TKey, TValue> current = this.table [i];
496 if (Equals (value, current.Value))
503 public bool ContainsValue (TValue value)
505 return IndexOfValue (value) >= 0;
508 public void TrimExcess ()
510 if (inUse < table.Length * 0.9)
514 public bool TryGetValue (TKey key, out TValue value)
517 throw new ArgumentNullException("key");
522 value = table [i].Value;
526 value = default (TValue);
535 private void EnsureCapacity (int n, int free)
537 KeyValuePair<TKey, TValue> [] table = this.table;
538 KeyValuePair<TKey, TValue> [] newTable = null;
540 bool gap = (free >=0 && free < Count);
543 newTable = new KeyValuePair<TKey, TValue> [n << 1];
546 if (newTable != null) {
550 Array.Copy (table, 0, newTable, 0, copyLen);
552 copyLen = Count - free;
554 Array.Copy (table, free, newTable, free+1, copyLen);
557 // Just a resizing, copy the entire table.
558 Array.Copy (table, newTable, Count);
560 this.table = newTable;
562 Array.Copy (table, free, table, free+1, Count - free);
566 private void PutImpl (TKey key, TValue value, bool overwrite)
569 throw new ArgumentNullException ("null key");
571 KeyValuePair<TKey, TValue> [] table = this.table;
576 freeIndx = Find (key);
577 } catch (Exception) {
578 throw new InvalidOperationException();
583 throw new ArgumentException("element already exists");
585 table [freeIndx] = new KeyValuePair <TKey, TValue> (key, value);
590 freeIndx = ~freeIndx;
592 if (freeIndx > Capacity + 1)
593 throw new Exception ("SortedList::internal error ("+key+", "+value+") at ["+freeIndx+"]");
596 EnsureCapacity (Count+1, freeIndx);
599 table [freeIndx] = new KeyValuePair <TKey, TValue> (key, value);
606 private void Init (IComparer<TKey> comparer, int capacity, bool forceSize)
608 if (comparer == null)
609 comparer = Comparer<TKey>.Default;
610 this.comparer = comparer;
611 if (!forceSize && (capacity < defaultCapacity))
612 capacity = defaultCapacity;
613 this.table = new KeyValuePair<TKey, TValue> [capacity];
615 this.modificationCount = 0;
618 private void CopyToArray (Array arr, int i,
622 throw new ArgumentNullException ("arr");
624 if (i < 0 || i + this.Count > arr.Length)
625 throw new ArgumentOutOfRangeException ("i");
627 IEnumerator it = new Enumerator (this, mode);
629 while (it.MoveNext ()) {
630 arr.SetValue (it.Current, i++);
634 private int Find (TKey key)
636 KeyValuePair<TKey, TValue> [] table = this.table;
639 if (len == 0) return ~0;
644 while (left <= right) {
645 int guess = (left + right) >> 1;
647 int cmp = comparer.Compare (table[guess].Key, key);
648 if (cmp == 0) return guess;
650 if (cmp < 0) left = guess+1;
651 else right = guess-1;
657 private TKey ToKey (object key) {
659 throw new ArgumentNullException ("key");
661 throw new ArgumentException ("The value \"" + key + "\" isn't of type \"" + typeof (TKey) + "\" and can't be used in this generic collection.", "key");
665 private TValue ToValue (object value) {
666 if (!(value is TValue))
667 throw new ArgumentException ("The value \"" + value + "\" isn't of type \"" + typeof (TValue) + "\" and can't be used in this generic collection.", "value");
668 return (TValue)value;
671 internal TKey KeyAt (int index) {
672 if (index >= 0 && index < Count)
673 return table [index].Key;
675 throw new ArgumentOutOfRangeException("Index out of range");
678 internal TValue ValueAt (int index) {
679 if (index >= 0 && index < Count)
680 return table [index].Value;
682 throw new ArgumentOutOfRangeException("Index out of range");
690 private sealed class Enumerator : ICloneable, IDictionaryEnumerator, IEnumerator {
692 private SortedList<TKey, TValue>host;
696 private EnumeratorMode mode;
698 private object currentKey;
699 private object currentValue;
701 bool invalid = false;
703 private readonly static string xstr = "SortedList.Enumerator: snapshot out of sync.";
705 public Enumerator (SortedList<TKey, TValue>host, EnumeratorMode mode)
708 stamp = host.modificationCount;
714 public Enumerator (SortedList<TKey, TValue>host)
715 : this (host, EnumeratorMode.ENTRY_MODE)
721 if (host.modificationCount != stamp || invalid)
722 throw new InvalidOperationException (xstr);
729 public bool MoveNext ()
731 if (host.modificationCount != stamp || invalid)
732 throw new InvalidOperationException (xstr);
734 KeyValuePair<TKey, TValue> [] table = host.table;
737 KeyValuePair<TKey, TValue> entry = table [pos];
739 currentKey = entry.Key;
740 currentValue = entry.Value;
749 public DictionaryEntry Entry
752 if (invalid || pos >= size || pos == -1)
753 throw new InvalidOperationException (xstr);
755 return new DictionaryEntry (currentKey,
762 if (invalid || pos >= size || pos == -1)
763 throw new InvalidOperationException (xstr);
768 public Object Value {
770 if (invalid || pos >= size || pos == -1)
771 throw new InvalidOperationException (xstr);
776 public Object Current {
778 if (invalid || pos >= size || pos == -1)
779 throw new InvalidOperationException (xstr);
782 case EnumeratorMode.KEY_MODE:
784 case EnumeratorMode.VALUE_MODE:
786 case EnumeratorMode.ENTRY_MODE:
790 throw new NotSupportedException (mode + " is not a supported mode.");
797 public object Clone ()
799 Enumerator e = new Enumerator (host, mode);
803 e.currentKey = currentKey;
804 e.currentValue = currentValue;
811 struct KeyEnumerator : IEnumerator <TKey>, IDisposable {
812 const int NOT_STARTED = -2;
814 // this MUST be -1, because we depend on it in move next.
815 // we just decr the size, so, 0 - 1 == FINISHED
816 const int FINISHED = -1;
818 SortedList <TKey, TValue> l;
822 internal KeyEnumerator (SortedList<TKey, TValue> l)
826 ver = l.modificationCount;
829 public void Dispose ()
834 public bool MoveNext ()
836 if (ver != l.modificationCount)
837 throw new InvalidOperationException ("Collection was modified after the enumerator was instantiated.");
839 if (idx == NOT_STARTED)
842 return idx != FINISHED && -- idx != FINISHED;
845 public TKey Current {
848 throw new InvalidOperationException ();
850 return l.KeyAt (l.Count - 1 - idx);
854 void IEnumerator.Reset ()
856 if (ver != l.modificationCount)
857 throw new InvalidOperationException ("Collection was modified after the enumerator was instantiated.");
862 object IEnumerator.Current {
863 get { return Current; }
868 struct ValueEnumerator : IEnumerator <TValue>, IDisposable {
869 const int NOT_STARTED = -2;
871 // this MUST be -1, because we depend on it in move next.
872 // we just decr the size, so, 0 - 1 == FINISHED
873 const int FINISHED = -1;
875 SortedList <TKey, TValue> l;
879 internal ValueEnumerator (SortedList<TKey, TValue> l)
883 ver = l.modificationCount;
886 public void Dispose ()
891 public bool MoveNext ()
893 if (ver != l.modificationCount)
894 throw new InvalidOperationException ("Collection was modified after the enumerator was instantiated.");
896 if (idx == NOT_STARTED)
899 return idx != FINISHED && -- idx != FINISHED;
902 public TValue Current {
905 throw new InvalidOperationException ();
907 return l.ValueAt (l.Count - 1 - idx);
911 void IEnumerator.Reset ()
913 if (ver != l.modificationCount)
914 throw new InvalidOperationException ("Collection was modified after the enumerator was instantiated.");
919 object IEnumerator.Current {
920 get { return Current; }
924 private class ListKeys : IList<TKey>, ICollection, IEnumerable {
926 private SortedList<TKey, TValue> host;
928 public ListKeys (SortedList<TKey, TValue> host)
931 throw new ArgumentNullException ();
938 public virtual void Add (TKey item) {
939 throw new NotSupportedException();
942 public virtual bool Remove (TKey key) {
943 throw new NotSupportedException ();
946 public virtual void Clear () {
947 throw new NotSupportedException();
950 public virtual void CopyTo (TKey[] array, int arrayIndex) {
954 throw new ArgumentNullException ("array");
956 throw new ArgumentOutOfRangeException();
957 if (arrayIndex >= array.Length)
958 throw new ArgumentOutOfRangeException ("arrayIndex is greater than or equal to array.Length");
959 if (Count > (array.Length - arrayIndex))
960 throw new ArgumentOutOfRangeException("Not enough space in array from arrayIndex to end of array");
963 for (int i = 0; i < Count; ++i)
964 array [j ++] = host.KeyAt (i);
967 public virtual bool Contains (TKey item) {
968 return host.IndexOfKey (item) > -1;
974 public virtual int IndexOf (TKey item) {
975 return host.IndexOfKey (item);
978 public virtual void Insert (int index, TKey item) {
979 throw new NotSupportedException ();
982 public virtual void RemoveAt (int index) {
983 throw new NotSupportedException ();
986 public virtual TKey this [int index] {
988 return host.KeyAt (index);
991 throw new NotSupportedException("attempt to modify a key");
999 public virtual IEnumerator<TKey> GetEnumerator ()
1001 /* We couldn't use yield as it does not support Reset () */
1002 return new KeyEnumerator (host);
1009 public virtual int Count {
1015 public virtual bool IsSynchronized {
1017 return ((ICollection)host).IsSynchronized;
1021 public virtual bool IsReadOnly {
1027 public virtual Object SyncRoot {
1029 return ((ICollection)host).SyncRoot;
1033 public virtual void CopyTo (Array array, int arrayIndex)
1035 host.CopyToArray (array, arrayIndex, EnumeratorMode.KEY_MODE);
1042 IEnumerator IEnumerable.GetEnumerator ()
1044 for (int i = 0; i < host.Count; ++i)
1045 yield return host.KeyAt (i);
1049 private class ListValues : IList<TValue>, ICollection, IEnumerable {
1051 private SortedList<TKey, TValue>host;
1053 public ListValues (SortedList<TKey, TValue>host)
1056 throw new ArgumentNullException ();
1061 // ICollection<TValue>
1063 public virtual void Add (TValue item) {
1064 throw new NotSupportedException();
1067 public virtual bool Remove (TValue value) {
1068 throw new NotSupportedException ();
1071 public virtual void Clear () {
1072 throw new NotSupportedException();
1075 public virtual void CopyTo (TValue[] array, int arrayIndex) {
1076 if (host.Count == 0)
1079 throw new ArgumentNullException ("array");
1081 throw new ArgumentOutOfRangeException();
1082 if (arrayIndex >= array.Length)
1083 throw new ArgumentOutOfRangeException ("arrayIndex is greater than or equal to array.Length");
1084 if (Count > (array.Length - arrayIndex))
1085 throw new ArgumentOutOfRangeException("Not enough space in array from arrayIndex to end of array");
1088 for (int i = 0; i < Count; ++i)
1089 array [j ++] = host.ValueAt (i);
1092 public virtual bool Contains (TValue item) {
1093 return host.IndexOfValue (item) > -1;
1099 public virtual int IndexOf (TValue item) {
1100 return host.IndexOfValue (item);
1103 public virtual void Insert (int index, TValue item) {
1104 throw new NotSupportedException ();
1107 public virtual void RemoveAt (int index) {
1108 throw new NotSupportedException ();
1111 public virtual TValue this [int index] {
1113 return host.ValueAt (index);
1116 throw new NotSupportedException("attempt to modify a key");
1121 // IEnumerable<TValue>
1124 public virtual IEnumerator<TValue> GetEnumerator ()
1126 /* We couldn't use yield as it does not support Reset () */
1127 return new ValueEnumerator (host);
1134 public virtual int Count {
1140 public virtual bool IsSynchronized {
1142 return ((ICollection)host).IsSynchronized;
1146 public virtual bool IsReadOnly {
1152 public virtual Object SyncRoot {
1154 return ((ICollection)host).SyncRoot;
1158 public virtual void CopyTo (Array array, int arrayIndex)
1160 host.CopyToArray (array, arrayIndex, EnumeratorMode.VALUE_MODE);
1167 IEnumerator IEnumerable.GetEnumerator ()
1169 for (int i = 0; i < host.Count; ++i)
1170 yield return host.ValueAt (i);
1176 } // System.Collections.Generic