//
// System.Collections.Generic.SortedDictionary
//
-// Authors:
+// Author:
+// Raja R Harinath <rharinath@novell.com>
+//
+// Authors of previous (superseded) version:
// Kazuki Oikawa (kazuki@panicode.com)
// Atsushi Enomoto (atsushi@ximian.com)
//
+//
+// Copyright (C) 2007, Novell, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
-#if NET_2_0
using System;
using System.Collections;
+using System.Diagnostics;
+using System.Runtime.Serialization;
+using System.Security.Permissions;
namespace System.Collections.Generic
{
[Serializable]
- public class SortedDictionary<TKey,TValue> : IDictionary<TKey,TValue>, ICollection<KeyValuePair<TKey,TValue>>, IEnumerable<KeyValuePair<TKey,TValue>>, IDictionary, ICollection, IEnumerable
+ [DebuggerDisplay ("Count={Count}")]
+ [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
+ public class SortedDictionary<TKey,TValue> : IDictionary<TKey,TValue>, ICollection<KeyValuePair<TKey,TValue>>, IEnumerable<KeyValuePair<TKey,TValue>>, IDictionary, ICollection, IEnumerable, ISerializable
{
- TKey [] _keys;
- TValue [] _values;
- IComparer<TKey> _comparer;
- int _size;
- int _version = 0;
- const int DefaultCapacitySize = 4;
+ class Node : RBTree.Node {
+ public TKey key;
+ public TValue value;
- KeyCollection _keyList;
- ValueCollection _valueList;
+ public Node (TKey key)
+ {
+ this.key = key;
+ }
- #region Constructor
- public SortedDictionary () : this (0, null)
- {
+ public Node (TKey key, TValue value)
+ {
+ this.key = key;
+ this.value = value;
+ }
+
+ public override void SwapValue (RBTree.Node other)
+ {
+ Node o = (Node) other;
+ TKey k = key; key = o.key; o.key = k;
+ TValue v = value; value = o.value; o.value = v;
+ }
+
+ public KeyValuePair<TKey, TValue> AsKV ()
+ {
+ return new KeyValuePair<TKey, TValue> (key, value);
+ }
+
+ public DictionaryEntry AsDE ()
+ {
+ return new DictionaryEntry (key, value);
+ }
}
- public SortedDictionary (IComparer<TKey> comparer) : this (0, comparer)
- {
+ [Serializable]
+ class NodeHelper : RBTree.INodeHelper<TKey> {
+ public IComparer<TKey> cmp;
+
+ public int Compare (TKey key, RBTree.Node node)
+ {
+ return cmp.Compare (key, ((Node) node).key);
+ }
+
+ public RBTree.Node CreateNode (TKey key)
+ {
+ return new Node (key);
+ }
+
+ private NodeHelper (IComparer<TKey> cmp)
+ {
+ this.cmp = cmp;
+ }
+ static NodeHelper Default = new NodeHelper (Comparer<TKey>.Default);
+ public static NodeHelper GetHelper (IComparer<TKey> cmp)
+ {
+ if (cmp == null || cmp == Comparer<TKey>.Default)
+ return Default;
+ return new NodeHelper (cmp);
+ }
}
- public SortedDictionary (IDictionary<TKey,TValue> dic) : this (dic, null)
+ RBTree tree;
+ NodeHelper hlp;
+
+ #region Constructor
+ public SortedDictionary () : this ((IComparer<TKey>) null)
{
}
- // it disappeared in 2.0 RTM
- SortedDictionary (int capacity) : this (capacity, null)
+ public SortedDictionary (IComparer<TKey> comparer)
{
-
+ hlp = NodeHelper.GetHelper (comparer);
+ tree = new RBTree (hlp);
}
- public SortedDictionary (IDictionary<TKey,TValue> dic, IComparer<TKey> comparer) : this (dic == null ? 0 : dic.Count, comparer)
+ public SortedDictionary (IDictionary<TKey,TValue> dictionary) : this (dictionary, null)
{
- if (dic == null)
- throw new ArgumentNullException ();
-
- dic.Keys.CopyTo (_keys, 0);
- dic.Values.CopyTo (_values, 0);
- Array.Sort<TKey,TValue> (_keys, _values);
- _size = dic.Count;
}
- // it disappeared in 2.0 RTM
- SortedDictionary (int capacity, IComparer<TKey> comparer)
+ public SortedDictionary (IDictionary<TKey,TValue> dictionary, IComparer<TKey> comparer) : this (comparer)
{
- if (capacity < 0)
- throw new ArgumentOutOfRangeException ();
+ if (dictionary == null)
+ throw new ArgumentNullException ("dictionary");
+
+ foreach (KeyValuePair<TKey, TValue> entry in dictionary)
+ Add (entry.Key, entry.Value);
+ }
- _keys = new TKey [capacity];
- _values = new TValue [capacity];
- _size = 0;
+ protected SortedDictionary (SerializationInfo info, StreamingContext context)
+ {
+ hlp = (NodeHelper)info.GetValue("Helper", typeof(NodeHelper));
+ tree = new RBTree (hlp);
- if (comparer == null)
- _comparer = Comparer<TKey>.Default;
- else
- _comparer = comparer;
+ KeyValuePair<TKey, TValue> [] data = (KeyValuePair<TKey, TValue>[])info.GetValue("KeyValuePairs", typeof(KeyValuePair<TKey, TValue>[]));
+ foreach (KeyValuePair<TKey, TValue> entry in data)
+ Add(entry.Key, entry.Value);
}
+
#endregion
#region PublicProperty
public IComparer<TKey> Comparer {
- get { return _comparer; }
- }
-
- // It disappeared in 2.0 RTM.
- int Capacity {
- get { return _keys.Length; }
- set {
- if (value < _size)
- throw new ArgumentOutOfRangeException ();
-
- Array.Resize<TKey> (ref _keys, value);
- Array.Resize<TValue> (ref _values, value);
- }
+ get { return hlp.cmp; }
}
public int Count {
- get { return _size; }
+ get { return (int) tree.Count; }
}
public TValue this [TKey key] {
get {
- int index = IndexOfKey (key);
- if (index >= 0)
- return _values [index];
-
- throw new KeyNotFoundException ();
+ Node n = (Node) tree.Lookup (key);
+ if (n == null)
+ throw new KeyNotFoundException ();
+ return n.value;
}
set {
if (key == null)
- throw new ArgumentNullException ();
-
- int index = IndexOfKey (key);
- if (index < 0)
- Add (key, value);
- else
- _values [index] = value;
+ throw new ArgumentNullException ("key");
+ Node n = (Node) tree.Intern (key, null);
+ n.value = value;
}
}
public KeyCollection Keys {
- get { return GetKeyCollection (); }
+ get { return new KeyCollection (this); }
}
public ValueCollection Values {
- get { return GetValueCollection (); }
+ get { return new ValueCollection (this); }
}
#endregion
public void Add (TKey key, TValue value)
{
if (key == null)
- throw new ArgumentNullException ();
-
- int index = Array.BinarySearch<TKey> (_keys, 0, _size, key, _comparer);
- if (index >= 0)
- throw new ArgumentException ();
-
- index = ~index;
-
- if (_size == _keys.Length)
- Capacity += Capacity > 0 ? Capacity : DefaultCapacitySize;
-
- if (index < _size) {
- Array.Copy (_keys, index, _keys, index + 1, _size - index);
- Array.Copy (_values, index, _values, index + 1, _size - index);
- }
+ throw new ArgumentNullException ("key");
- _keys [index] = key;
- _values [index] = value;
- _size++;
- _version++;
+ RBTree.Node n = new Node (key, value);
+ if (tree.Intern (key, n) != n)
+ throw new ArgumentException ("key already present in dictionary", "key");
}
public void Clear ()
{
- Array.Clear (_keys, 0, _size);
- Array.Clear (_values, 0, _size);
- _size = 0;
- _version++;
+ tree.Clear ();
}
public bool ContainsKey (TKey key)
{
- return IndexOfKey (key) >= 0;
+ return tree.Lookup (key) != null;
}
public bool ContainsValue (TValue value)
{
- return IndexOfValue (value) >= 0;
+ IEqualityComparer<TValue> vcmp = EqualityComparer<TValue>.Default;
+ foreach (Node n in tree)
+ if (vcmp.Equals (value, n.value))
+ return true;
+ return false;
}
- public void CopyTo (KeyValuePair<TKey,TValue>[] array, int arrayIndex)
+ public void CopyTo (KeyValuePair<TKey,TValue>[] array, int index)
{
+ if (Count == 0)
+ return;
if (array == null)
throw new ArgumentNullException ();
- if (arrayIndex < 0 || array.Length <= arrayIndex)
+ if (index < 0 || array.Length <= index)
throw new ArgumentOutOfRangeException ();
- if (array.Length - arrayIndex < _size)
+ if (array.Length - index < Count)
throw new ArgumentException ();
- for (int i = 0; i < _size; i ++) {
- array [arrayIndex + i] = new KeyValuePair<TKey,TValue> (_keys [i], _values [i]);
- }
+ foreach (Node n in tree)
+ array [index ++] = n.AsKV ();
}
public Enumerator GetEnumerator ()
return new Enumerator (this);
}
- int IndexOfKey (TKey key)
- {
- if (key == null)
- throw new ArgumentNullException ();
-
- return Array.BinarySearch<TKey> (_keys, 0, _size, key, _comparer);
- }
-
- int IndexOfValue (TValue value)
- {
- return Array.IndexOf<TValue> (_values, value, 0, _size);
- }
-
public bool Remove (TKey key)
{
- int index = IndexOfKey (key);
- if (index >= 0) {
- RemoveAt (index);
- return true;
- }
- return false;
+ return tree.Remove (key) != null;
}
- void RemoveAt (int index)
+ public bool TryGetValue (TKey key, out TValue value)
{
- if (index < 0 || _size <= index)
- throw new ArgumentOutOfRangeException ();
-
- _size--;
- if (index < _size) {
- Array.Copy (_keys, index + 1, _keys, index, _size - index);
- Array.Copy (_values, index + 1, _values, index, _size - index);
- }
-
- _keys[_size] = default (TKey) ;
- _values[_size] = default (TValue) ;
- _version++;
+ Node n = (Node) tree.Lookup (key);
+ value = n == null ? default (TValue) : n.value;
+ return n != null;
}
- public bool TryGetValue (TKey key, out TValue value)
+ [SecurityPermission (SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)]
+ public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
{
- int index = IndexOfKey (key);
- if (index >= 0) {
- value = _values [index];
- return true;
- }
+ if (info == null)
+ throw new ArgumentNullException ("info");
- value = default (TValue) ;
- return false;
+ KeyValuePair<TKey, TValue> [] data = new KeyValuePair<TKey,TValue> [Count];
+ CopyTo (data, 0);
+ info.AddValue ("KeyValuePairs", data);
+ info.AddValue ("Helper", hlp);
}
#endregion
#region PrivateMethod
- private KeyCollection GetKeyCollection ()
- {
- if (_keyList == null)
- _keyList = new KeyCollection (this);
- return _keyList;
- }
- private ValueCollection GetValueCollection ()
- {
- if (_valueList == null)
- _valueList = new ValueCollection (this);
- return _valueList;
- }
-
TKey ToKey (object key)
{
if (key == null)
#region IDictionary<TKey,TValue> Member
ICollection<TKey> IDictionary<TKey,TValue>.Keys {
- get { return GetKeyCollection (); }
+ get { return new KeyCollection (this); }
}
ICollection<TValue> IDictionary<TKey,TValue>.Values {
- get { return GetValueCollection (); }
+ get { return new ValueCollection (this); }
}
#endregion
bool ICollection<KeyValuePair<TKey,TValue>>.Contains (KeyValuePair<TKey,TValue> item)
{
- int index = IndexOfKey (item.Key);
- return index >= 0 && Comparer<TValue>.Default.Compare (_values [index], item.Value) == 0;
+ TValue value;
+ return TryGetValue (item.Key, out value) &&
+ EqualityComparer<TValue>.Default.Equals (item.Value, value);
}
bool ICollection<KeyValuePair<TKey,TValue>>.IsReadOnly {
bool ICollection<KeyValuePair<TKey,TValue>>.Remove (KeyValuePair<TKey,TValue> item)
{
- int index = IndexOfKey (item.Key);
- if (index >= 0 && Comparer<TValue>.Default.Compare (_values [index], item.Value) == 0) {
- RemoveAt (index);
- return true;
- }
- return false;
+ TValue value;
+ return TryGetValue (item.Key, out value) &&
+ EqualityComparer<TValue>.Default.Equals (item.Value, value) &&
+ Remove (item.Key);
}
#endregion
}
ICollection IDictionary.Keys {
- get { return GetKeyCollection (); }
+ get { return new KeyCollection (this); }
}
void IDictionary.Remove (object key)
{
Remove (ToKey (key));
}
+
ICollection IDictionary.Values {
- get { return GetValueCollection (); }
+ get { return new ValueCollection (this); }
}
object IDictionary.this [object key] {
- get {
- return this [ToKey (key)];
- }
- set {
- if (!(value is TValue))
- throw new ArgumentException ();
-
- this [ToKey (key)] = ToValue (value);
- }
+ get { return this [ToKey (key)]; }
+ set { this [ToKey (key)] = ToValue (value); }
}
#endregion
void ICollection.CopyTo (Array array, int index)
{
+ if (Count == 0)
+ return;
if (array == null)
throw new ArgumentNullException ();
if (index < 0 || array.Length <= index)
throw new ArgumentOutOfRangeException ();
- if (array.Length - index < _size)
+ if (array.Length - index < Count)
throw new ArgumentException ();
- for (int i = 0; i < _size; i ++) {
- array.SetValue (new KeyValuePair<TKey,TValue> (_keys [i], _values [i]), i);
- }
+ foreach (Node n in tree)
+ array.SetValue (n.AsDE (), index++);
}
bool ICollection.IsSynchronized {
#endregion
[Serializable]
+ [DebuggerDisplay ("Count={Count}")]
+ [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
public sealed class ValueCollection : ICollection<TValue>,
IEnumerable<TValue>, ICollection, IEnumerable
{
SortedDictionary<TKey,TValue> _dic;
- public ValueCollection (SortedDictionary<TKey,TValue> dic)
+ public ValueCollection (SortedDictionary<TKey,TValue> dictionary)
{
- _dic = dic;
+ if (dictionary == null)
+ throw new ArgumentNullException ("dictionary");
+
+ _dic = dictionary;
}
void ICollection<TValue>.Add (TValue item)
return _dic.ContainsValue (item);
}
- public void CopyTo (TValue [] array, int arrayIndex)
+ public void CopyTo (TValue [] array, int index)
{
+ if (Count == 0)
+ return;
if (array == null)
throw new ArgumentNullException ();
- if (arrayIndex < 0 || array.Length <= arrayIndex)
+ if (index < 0 || array.Length <= index)
throw new ArgumentOutOfRangeException ();
- if (array.Length - arrayIndex < _dic._size)
+ if (array.Length - index < Count)
throw new ArgumentException ();
- Array.Copy (_dic._values, 0, array, arrayIndex, _dic._size);
+ foreach (Node n in _dic.tree)
+ array [index++] = n.value;
}
public int Count {
- get { return _dic._size; }
+ get { return _dic.Count; }
}
bool ICollection<TValue>.IsReadOnly {
return new Enumerator (_dic);
}
- void ICollection.CopyTo(Array array, int index)
+ void ICollection.CopyTo (Array array, int index)
{
+ if (Count == 0)
+ return;
if (array == null)
throw new ArgumentNullException ();
if (index < 0 || array.Length <= index)
throw new ArgumentOutOfRangeException ();
- if (array.Length - index < _dic._size)
+ if (array.Length - index < Count)
throw new ArgumentException ();
- Array.Copy (_dic._values, 0, array, index, _dic._size);
+ foreach (Node n in _dic.tree)
+ array.SetValue (n.value, index++);
}
bool ICollection.IsSynchronized {
IEnumerator IEnumerable.GetEnumerator ()
{
- return new Enumerator (_dic);
+ return new Enumerator (_dic);
}
public struct Enumerator : IEnumerator<TValue>,IEnumerator, IDisposable
{
- SortedDictionary<TKey,TValue> _dic;
- int _version;
- int _index;
- int _count;
+ RBTree.NodeEnumerator host;
- internal Enumerator (SortedDictionary<TKey,TValue> dic)
+ TValue current;
+
+ internal Enumerator (SortedDictionary<TKey,TValue> dictionary)
+ : this ()
{
- _dic = dic;
- _version = dic._version;
- _index = -1;
- _count = dic._size;
+ host = dictionary.tree.GetEnumerator ();
}
public TValue Current {
- get {
- if (_count <= _index)
- throw new InvalidOperationException ();
- return _dic._values [_index];
- }
+ get { return current; }
}
public bool MoveNext ()
{
- if (_version != _dic._version)
- throw new InvalidOperationException ();
-
- if (_index + 1 < _count) {
- _index ++;
- return true;
- }
-
- return false;
+ if (!host.MoveNext ())
+ return false;
+ current = ((Node) host.Current).value;
+ return true;
}
public void Dispose ()
{
- _dic = null;
+ host.Dispose ();
}
object IEnumerator.Current {
- get { return Current; }
+ get {
+ host.check_current ();
+ return current;
+ }
}
void IEnumerator.Reset ()
{
- if (_version != _dic._version)
- throw new InvalidOperationException ();
- _index = -1;
+ host.Reset ();
}
}
}
[Serializable]
+ [DebuggerDisplay ("Count={Count}")]
+ [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
public sealed class KeyCollection : ICollection<TKey>,
IEnumerable<TKey>, ICollection, IEnumerable
{
SortedDictionary<TKey,TValue> _dic;
- public KeyCollection (SortedDictionary<TKey,TValue> dic)
+ public KeyCollection (SortedDictionary<TKey,TValue> dictionary)
{
- _dic = dic;
+ _dic = dictionary;
}
void ICollection<TKey>.Add (TKey item)
return GetEnumerator ();
}
- public void CopyTo (TKey [] array, int arrayIndex)
+ public void CopyTo (TKey [] array, int index)
{
- Array.Copy (_dic._keys, 0, array, arrayIndex, _dic._size);
+ if (Count == 0)
+ return;
+ if (array == null)
+ throw new ArgumentNullException ();
+ if (index < 0 || array.Length <= index)
+ throw new ArgumentOutOfRangeException ();
+ if (array.Length - index < Count)
+ throw new ArgumentException ();
+ foreach (Node n in _dic.tree)
+ array [index++] = n.key;
}
public int Count {
- get { return _dic._size; }
+ get { return _dic.Count; }
}
bool ICollection<TKey>.IsReadOnly {
void ICollection.CopyTo (Array array, int index)
{
+ if (Count == 0)
+ return;
if (array == null)
throw new ArgumentNullException ();
if (index < 0 || array.Length <= index)
throw new ArgumentOutOfRangeException ();
- if (array.Length - index < _dic._size)
+ if (array.Length - index < Count)
throw new ArgumentException ();
- Array.Copy (_dic._keys, 0, array, index, _dic._size);
+ foreach (Node n in _dic.tree)
+ array.SetValue (n.key, index++);
}
bool ICollection.IsSynchronized {
IEnumerator IEnumerable.GetEnumerator ()
{
- return new Enumerator (_dic);
+ return new Enumerator (_dic);
}
public struct Enumerator : IEnumerator<TKey>, IEnumerator, IDisposable
{
- SortedDictionary<TKey,TValue> _dic;
- int _version;
- int _index;
- int _count;
+ RBTree.NodeEnumerator host;
+
+ TKey current;
internal Enumerator (SortedDictionary<TKey,TValue> dic)
+ : this ()
{
- _dic = dic;
- _version = dic._version;
- _index = -1;
- _count = dic._size;
+ host = dic.tree.GetEnumerator ();
}
public TKey Current {
- get {
- if (_count <= _index)
- throw new InvalidOperationException ();
- return _dic._keys [_index];
- }
+ get { return current; }
}
public bool MoveNext ()
{
- if (_version != _dic._version)
- throw new InvalidOperationException ();
-
- if (_index + 1 < _count) {
- _index ++;
- return true;
- }
-
- return false;
+ if (!host.MoveNext ())
+ return false;
+ current = ((Node) host.Current).key;
+ return true;
}
public void Dispose ()
{
- _dic = null;
+ host.Dispose ();
}
object IEnumerator.Current {
- get { return Current; }
+ get {
+ host.check_current ();
+ return current;
+ }
}
void IEnumerator.Reset ()
{
- if (_version != _dic._version)
- throw new InvalidOperationException ();
- _index = -1;
+ host.Reset ();
}
}
-
}
- public struct Enumerator : IEnumerator<KeyValuePair<TKey,TValue>>, IDisposable , IDictionaryEnumerator, IEnumerator
+ public struct Enumerator : IEnumerator<KeyValuePair<TKey,TValue>>, IDisposable, IDictionaryEnumerator, IEnumerator
{
- SortedDictionary<TKey,TValue> _dic;
- int _version;
- int _index;
- int _count;
+ RBTree.NodeEnumerator host;
+
+ KeyValuePair<TKey, TValue> current;
internal Enumerator (SortedDictionary<TKey,TValue> dic)
+ : this ()
{
- _dic = dic;
- _version = dic._version;
- _index = -1;
- _count = dic._size;
+ host = dic.tree.GetEnumerator ();
}
public KeyValuePair<TKey,TValue> Current {
- get {
- if (_count <= _index)
- throw new InvalidOperationException ();
- return new KeyValuePair<TKey,TValue> (_dic._keys [_index], _dic._values [_index]);
- }
+ get { return current; }
}
public bool MoveNext ()
{
- if (_version != _dic._version)
- throw new InvalidOperationException ();
-
- if (_index + 1 < _count) {
- _index ++;
- return true;
- }
-
- return false;
+ if (!host.MoveNext ())
+ return false;
+ current = ((Node) host.Current).AsKV ();
+ return true;
}
public void Dispose ()
{
- _dic = null;
+ host.Dispose ();
}
- DictionaryEntry IDictionaryEnumerator.Entry {
+ Node CurrentNode {
get {
- if (_count <= _index)
- throw new InvalidOperationException ();
- return new DictionaryEntry (_dic._keys [_index], _dic._values [_index]);
+ host.check_current ();
+ return (Node) host.Current;
}
}
+ DictionaryEntry IDictionaryEnumerator.Entry {
+ get { return CurrentNode.AsDE (); }
+ }
+
object IDictionaryEnumerator.Key {
- get {
- if (_count <= _index)
- throw new InvalidOperationException ();
- return _dic._keys [_index];
- }
+ get { return CurrentNode.key; }
}
object IDictionaryEnumerator.Value {
- get {
- if (_count <= _index)
- throw new InvalidOperationException ();
- return _dic._values [_index];
- }
+ get { return CurrentNode.value; }
}
object IEnumerator.Current {
- get {
- if (_count <= _index)
- throw new InvalidOperationException ();
- return new DictionaryEntry (_dic._keys [_index], _dic._values [_index]);
- }
+ get { return CurrentNode.AsDE (); }
}
void IEnumerator.Reset ()
{
- if (_version != _dic._version)
- throw new InvalidOperationException ();
-
- _index = -1;
+ host.Reset ();
}
}
}
}
-#endif
projects / mono.git / blobdiff