// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
-#if NET_2_0
-
using System;
using System.Collections;
using System.Globalization;
using System.Runtime.InteropServices;
+using System.Diagnostics;
namespace System.Collections.Generic
{
/// </summary>
[Serializable]
[ComVisible(false)]
+ [DebuggerDisplay ("Count={Count}")]
+ [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
public class SortedList<TKey, TValue> : IDictionary<TKey, TValue>,
IDictionary,
ICollection,
object IDictionary.this [object key] {
get {
- if (!(key is TKey))
- return null;
- else
- return this [(TKey)key];
+ TValue obj;
+ if (key is TKey && TryGetValue ((TKey)key, out obj))
+ return obj;
+ return null;
}
set {
Array.Copy (table, newTable, inUse);
this.table = newTable;
}
-#if NET_1_0
- else if (current > defaultCapacity && value < current) {
- KeyValuePair<TKey, TValue> [] newTable = new KeyValuePair<TKey, TValue> [defaultCapacity];
- Array.Copy (table, newTable, inUse);
- this.table = newTable;
- }
-#endif
else if (value > inUse) {
KeyValuePair<TKey, TValue> [] newTable = new KeyValuePair<TKey, TValue> [value];
Array.Copy (table, newTable, inUse);
void ICollection<KeyValuePair<TKey, TValue>>.Clear ()
{
- defaultCapacity = INITIAL_SIZE;
- this.table = new KeyValuePair<TKey, TValue> [defaultCapacity];
- inUse = 0;
- modificationCount++;
+ Clear ();
}
public void Clear ()
{
- defaultCapacity = INITIAL_SIZE;
- this.table = new KeyValuePair<TKey, TValue> [defaultCapacity];
+ Array.Clear (table, 0, table.Length);
inUse = 0;
modificationCount++;
}
void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{
+ if (Count == 0)
+ return;
+
if (null == array)
throw new ArgumentNullException();
void ICollection.CopyTo (Array array, int arrayIndex)
{
+ if (Count == 0)
+ return;
+
if (null == array)
throw new ArgumentNullException();
if (key == null)
throw new ArgumentNullException ("key");
- int indx = 0;
- try {
- indx = Find (key);
- } catch (Exception) {
- throw new InvalidOperationException();
- }
+ int indx = Find (key);
return (indx | (indx >> 31));
}
KeyValuePair<TKey, TValue> [] table = this.table;
- int freeIndx = -1;
-
- try {
- freeIndx = Find (key);
- } catch (Exception) {
- throw new InvalidOperationException();
- }
+ int freeIndx = Find (key);
if (freeIndx >= 0) {
if (!overwrite)
}
}
+ private int Compare (TKey a, TKey b)
+ {
+ try {
+ return comparer.Compare (a, b);
+ } catch (Exception ex) {
+ throw new InvalidOperationException ("Failed to compare two elements.", ex);
+ }
+ }
+
private int Find (TKey key)
{
KeyValuePair<TKey, TValue> [] table = this.table;
int right = len-1;
while (left <= right) {
- int guess = (left + right) >> 1;
+ int guess = left + ((right - left) >> 1);
- int cmp = comparer.Compare (key, table[guess].Key);
+ int cmp = Compare (table[guess].Key, key);
if (cmp == 0) return guess;
- if (cmp > 0) left = guess+1;
+ if (cmp < 0) left = guess+1;
else right = guess-1;
}
}
}
+ [Serializable]
+ struct KeyEnumerator : IEnumerator <TKey>, IDisposable {
+ const int NOT_STARTED = -2;
+
+ // this MUST be -1, because we depend on it in move next.
+ // we just decr the size, so, 0 - 1 == FINISHED
+ const int FINISHED = -1;
+
+ SortedList <TKey, TValue> l;
+ int idx;
+ int ver;
+
+ internal KeyEnumerator (SortedList<TKey, TValue> l)
+ {
+ this.l = l;
+ idx = NOT_STARTED;
+ ver = l.modificationCount;
+ }
+
+ public void Dispose ()
+ {
+ idx = NOT_STARTED;
+ }
+
+ public bool MoveNext ()
+ {
+ if (ver != l.modificationCount)
+ throw new InvalidOperationException ("Collection was modified after the enumerator was instantiated.");
+
+ if (idx == NOT_STARTED)
+ idx = l.Count;
+
+ return idx != FINISHED && -- idx != FINISHED;
+ }
+
+ public TKey Current {
+ get {
+ if (idx < 0)
+ throw new InvalidOperationException ();
+
+ return l.KeyAt (l.Count - 1 - idx);
+ }
+ }
+
+ void IEnumerator.Reset ()
+ {
+ if (ver != l.modificationCount)
+ throw new InvalidOperationException ("Collection was modified after the enumerator was instantiated.");
+
+ idx = NOT_STARTED;
+ }
+
+ object IEnumerator.Current {
+ get { return Current; }
+ }
+ }
+
+ [Serializable]
+ struct ValueEnumerator : IEnumerator <TValue>, IDisposable {
+ const int NOT_STARTED = -2;
+
+ // this MUST be -1, because we depend on it in move next.
+ // we just decr the size, so, 0 - 1 == FINISHED
+ const int FINISHED = -1;
+
+ SortedList <TKey, TValue> l;
+ int idx;
+ int ver;
+
+ internal ValueEnumerator (SortedList<TKey, TValue> l)
+ {
+ this.l = l;
+ idx = NOT_STARTED;
+ ver = l.modificationCount;
+ }
+
+ public void Dispose ()
+ {
+ idx = NOT_STARTED;
+ }
+
+ public bool MoveNext ()
+ {
+ if (ver != l.modificationCount)
+ throw new InvalidOperationException ("Collection was modified after the enumerator was instantiated.");
+
+ if (idx == NOT_STARTED)
+ idx = l.Count;
+
+ return idx != FINISHED && -- idx != FINISHED;
+ }
+
+ public TValue Current {
+ get {
+ if (idx < 0)
+ throw new InvalidOperationException ();
+
+ return l.ValueAt (l.Count - 1 - idx);
+ }
+ }
+
+ void IEnumerator.Reset ()
+ {
+ if (ver != l.modificationCount)
+ throw new InvalidOperationException ("Collection was modified after the enumerator was instantiated.");
+
+ idx = NOT_STARTED;
+ }
+
+ object IEnumerator.Current {
+ get { return Current; }
+ }
+ }
private class ListKeys : IList<TKey>, ICollection, IEnumerable {
public virtual IEnumerator<TKey> GetEnumerator ()
{
- for (int i = 0; i < host.Count; ++i)
- yield return host.KeyAt (i);
+ /* We couldn't use yield as it does not support Reset () */
+ return new KeyEnumerator (host);
}
//
public virtual IEnumerator<TValue> GetEnumerator ()
{
- for (int i = 0; i < host.Count; ++i)
- yield return host.ValueAt (i);
+ /* We couldn't use yield as it does not support Reset () */
+ return new ValueEnumerator (host);
}
//
} // SortedList
} // System.Collections.Generic
-
-#endif
projects / mono.git / blobdiff