Author: raja
Date: 2007-05-01 15:07:31 -0400 (Tue, 01 May 2007)
New Revision: 76537
Modified:
trunk/mcs/class/System/ChangeLog
trunk/mcs/class/System/System.Collections.Generic/ChangeLog
trunk/mcs/class/System/System.Collections.Generic/RBTree.cs
trunk/mcs/class/System/System.Collections.Generic/SortedDictionary.cs
trunk/mcs/class/System/System.dll.sources
trunk/mcs/class/System/Test/System.Collections.Generic/ChangeLog
trunk/mcs/class/System/Test/System.Collections.Generic/SortedDictionaryTest.cs
Log:
In .:
* System.dll.sources: Add RBTree.cs.
In System.Collections.Generic:
Make add and remove operations O(log n).
* SortedDictionary.cs: Rewrite to use the red-black tree
implementation from RBTree.cs.
* RBTree.cs: Some more refactoring. Rename Insert() to Intern(),
and modify semantics slightly. Replace Contains() with Lookup().
In Test/System.Collections.Generic:
* SortedDictionaryTest.cs (AddNullKeyNullable): Enable.
Modified: trunk/mcs/class/System/ChangeLog
===================================================================
--- trunk/mcs/class/System/ChangeLog 2007-05-01 18:58:31 UTC (rev 76536)
+++ trunk/mcs/class/System/ChangeLog 2007-05-01 19:07:31 UTC (rev 76537)
@@ -1,3 +1,7 @@
+2007-05-02 Raja R Harinath <[EMAIL PROTECTED]>
+
+ * System.dll.sources: Add RBTree.cs.
+
2007-04-16 Rolf Bjarne Kvinge <[EMAIL PROTECTED]>
* System_test.dll.sources: Added CodeGeneratorFromBinaryOperatorTest.cs.
Modified: trunk/mcs/class/System/System.Collections.Generic/ChangeLog
===================================================================
--- trunk/mcs/class/System/System.Collections.Generic/ChangeLog 2007-05-01
18:58:31 UTC (rev 76536)
+++ trunk/mcs/class/System/System.Collections.Generic/ChangeLog 2007-05-01
19:07:31 UTC (rev 76537)
@@ -1,3 +1,11 @@
+2007-05-02 Raja R Harinath <[EMAIL PROTECTED]>
+
+ Make add and remove operations O(log n).
+ * SortedDictionary.cs: Rewrite to use the red-black tree
+ implementation from RBTree.cs.
+ * RBTree.cs: Some more refactoring. Rename Insert() to Intern(),
+ and modify semantics slightly. Replace Contains() with Lookup().
+
2007-04-30 Raja R Harinath <[EMAIL PROTECTED]>
* RBTree.cs: Refactor to reduce generics code.
Modified: trunk/mcs/class/System/System.Collections.Generic/RBTree.cs
===================================================================
--- trunk/mcs/class/System/System.Collections.Generic/RBTree.cs 2007-05-01
18:58:31 UTC (rev 76536)
+++ trunk/mcs/class/System/System.Collections.Generic/RBTree.cs 2007-05-01
19:07:31 UTC (rev 76537)
@@ -36,7 +36,7 @@
namespace System.Collections.Generic
{
- internal class RBTreeCore {
+ internal class RBTree : IEnumerable, IEnumerable<RBTree.Node> {
public interface INodeComparer<T> {
int Compare (T value, Node node);
}
@@ -144,15 +144,22 @@
}
#endif
- public RBTreeCore (object cmp)
+ public RBTree (object cmp)
{
// cmp is INodeComparer<T> for some T
this.cmp = cmp;
}
- // returns the newly inserted node (or null if the value is
already in the tree)
- public Node Insert<T> (T key, Node new_node)
+ public void Clear ()
{
+ root = null;
+ ++version;
+ }
+
+ // if key is already in the tree, return the node associated
with it
+ // if not, insert new_node into the tree, and return it
+ public Node Intern<T> (T key, Node new_node)
+ {
if (root == null) {
root = new_node;
root.IsBlack = true;
@@ -162,7 +169,7 @@
List<Node> path = alloc_path ();
int in_tree_cmp = find_key (key, path);
- Node retval = in_tree_cmp == 0 ? null : do_insert
(in_tree_cmp, new_node, path);
+ Node retval = in_tree_cmp == 0 ? path [path.Count - 1]
: do_insert (in_tree_cmp, new_node, path);
// no need for a try .. finally, this is only used to
mitigate allocations
release_path (path);
return retval;
@@ -182,9 +189,17 @@
return retval;
}
- public bool Contains<T> (T key)
+ public Node Lookup<T> (T key)
{
- return root != null && find_key (key, null) == 0;
+ INodeComparer<T> cmp = (INodeComparer<T>) this.cmp;
+ Node current = root;
+ while (current != null) {
+ int c = cmp.Compare (key, current);
+ if (c == 0)
+ break;
+ current = c < 0 ? current.left : current.right;
+ }
+ return current;
}
public int Count {
@@ -215,11 +230,21 @@
}
}
- public NodeEnumerator GetNodeEnumerator ()
+ public NodeEnumerator GetEnumerator ()
{
return new NodeEnumerator (this);
}
+ IEnumerator<Node> IEnumerable<Node>.GetEnumerator ()
+ {
+ return GetEnumerator ();
+ }
+
+ IEnumerator IEnumerable.GetEnumerator ()
+ {
+ return GetEnumerator ();
+ }
+
#if TEST
public void VerifyInvariants ()
{
@@ -555,13 +580,13 @@
}
public struct NodeEnumerator : IEnumerator, IEnumerator<Node> {
- RBTreeCore tree;
+ RBTree tree;
uint version;
List<Node> path;
Node current;
- internal NodeEnumerator (RBTreeCore tree)
+ internal NodeEnumerator (RBTree tree)
{
this.tree = tree;
version = tree.version;
@@ -569,7 +594,7 @@
path = null;
}
- void IEnumerator.Reset ()
+ public void Reset ()
{
check_version ();
current = null;
@@ -650,7 +675,7 @@
internal class TreeSet<T> : IEnumerable<T>, IEnumerable
{
- public class Node : RBTreeCore.Node {
+ public class Node : RBTree.Node {
public T value;
public Node (T v)
@@ -658,7 +683,7 @@
value = v;
}
- public override void SwapValue (RBTreeCore.Node other)
+ public override void SwapValue (RBTree.Node other)
{
Node o = (Node) other;
T v = value;
@@ -676,10 +701,10 @@
}
}
- public class NodeComparer : RBTreeCore.INodeComparer<T> {
+ public class NodeComparer : RBTree.INodeComparer<T> {
IComparer<T> cmp;
- public int Compare (T value, RBTreeCore.Node node)
+ public int Compare (T value, RBTree.Node node)
{
return cmp.Compare (value, ((Node) node).value);
}
@@ -698,16 +723,16 @@
}
public struct Enumerator : IDisposable, IEnumerator,
IEnumerator<T> {
- RBTreeCore.NodeEnumerator host;
+ RBTree.NodeEnumerator host;
internal Enumerator (TreeSet<T> tree)
{
- host = new RBTreeCore.NodeEnumerator
(tree.tree);
+ host = new RBTree.NodeEnumerator (tree.tree);
}
void IEnumerator.Reset ()
{
- ((IEnumerator) host).Reset ();
+ host.Reset ();
}
public T Current {
@@ -729,7 +754,7 @@
}
}
- RBTreeCore tree;
+ RBTree tree;
public TreeSet () : this (null)
{
@@ -737,7 +762,7 @@
public TreeSet (IComparer<T> cmp)
{
- tree = new RBTreeCore (NodeComparer.GetComparer (cmp));
+ tree = new RBTree (NodeComparer.GetComparer (cmp));
}
IEnumerator IEnumerable.GetEnumerator ()
@@ -755,19 +780,22 @@
return new Enumerator (this);
}
- public Node Insert (T value)
+ // returns true if the value was inserted, false if the value
already existed in the tree
+ public bool Insert (T value)
{
- return (Node) tree.Insert (value, new Node (value));
+ RBTree.Node n = new Node (value);
+ return tree.Intern (value, n) == n;
}
- public Node Remove (T value)
+ // returns true if the value was removed, false if the value
didn't exist in the tree
+ public bool Remove (T value)
{
- return (Node) tree.Remove (value);
+ return tree.Remove (value) != null;
}
public bool Contains (T value)
{
- return tree.Contains (value);
+ return tree.Lookup (value) != null;
}
public T this [int index] {
@@ -806,11 +834,11 @@
continue;
d [n] = n;
- if (t.Contains (n))
- throw new Exception ("tree says it has
a number it shouldn't");
-
try {
- t.Insert (n);
+ if (t.Contains (n))
+ throw new Exception ("tree says
it has a number it shouldn't");
+ if (!t.Insert (n))
+ throw new Exception ("tree says
it has a number it shouldn't");
} catch {
Console.Error.WriteLine ("Exception
while inserting {0} in iteration {1}", n, i);
throw;
@@ -850,7 +878,7 @@
if ((j++ % 100) == 0)
t.VerifyInvariants ();
try {
- if (t.Remove (n) == null)
+ if (!t.Remove (n))
throw new Exception ("tree says
it doesn't have a number it should");
} catch {
Modified: trunk/mcs/class/System/System.Collections.Generic/SortedDictionary.cs
===================================================================
--- trunk/mcs/class/System/System.Collections.Generic/SortedDictionary.cs
2007-05-01 18:58:31 UTC (rev 76536)
+++ trunk/mcs/class/System/System.Collections.Generic/SortedDictionary.cs
2007-05-01 19:07:31 UTC (rev 76537)
@@ -36,111 +36,116 @@
[Serializable]
public class SortedDictionary<TKey,TValue> : IDictionary<TKey,TValue>,
ICollection<KeyValuePair<TKey,TValue>>, IEnumerable<KeyValuePair<TKey,TValue>>,
IDictionary, ICollection, IEnumerable
{
- 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, 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);
+ }
+ }
+
+ class NodeComparer : RBTree.INodeComparer<TKey> {
+ public IComparer<TKey> cmp;
+
+ public int Compare (TKey key, RBTree.Node node)
+ {
+ return cmp.Compare (key, ((Node) node).key);
+ }
+
+ private NodeComparer (IComparer<TKey> cmp)
+ {
+ this.cmp = cmp;
+ }
+ static NodeComparer Default = new NodeComparer
(Comparer<TKey>.Default);
+ public static NodeComparer GetComparer (IComparer<TKey>
cmp)
+ {
+ if (cmp == null || cmp ==
Comparer<TKey>.Default)
+ return Default;
+ return new NodeComparer (cmp);
+ }
+ }
+
+ RBTree tree;
+ NodeComparer cmp;
+
#region Constructor
- public SortedDictionary () : this (0, null)
+ public SortedDictionary () : this ((IComparer<TKey>) null)
{
}
- public SortedDictionary (IComparer<TKey> comparer) : this (0,
comparer)
+ public SortedDictionary (IComparer<TKey> comparer)
{
+ cmp = NodeComparer.GetComparer (comparer);
+ tree = new RBTree (cmp);
}
public SortedDictionary (IDictionary<TKey,TValue> dic) : this
(dic, null)
{
}
- // it disappeared in 2.0 RTM
- SortedDictionary (int capacity) : this (capacity, null)
+ public SortedDictionary (IDictionary<TKey,TValue> dic,
IComparer<TKey> comparer) : this (comparer)
{
-
- }
-
- public SortedDictionary (IDictionary<TKey,TValue> dic,
IComparer<TKey> comparer) : this (dic == null ? 0 : dic.Count, comparer)
- {
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;
+ foreach (KeyValuePair<TKey, TValue> entry in dic)
+ Add (entry.Key, entry.Value);
}
-
- // it disappeared in 2.0 RTM
- SortedDictionary (int capacity, IComparer<TKey> comparer)
- {
- if (capacity < 0)
- throw new ArgumentOutOfRangeException ();
-
- _keys = new TKey [capacity];
- _values = new TValue [capacity];
- _size = 0;
-
- if (comparer == null)
- _comparer = Comparer<TKey>.Default;
- else
- _comparer = comparer;
- }
#endregion
#region PublicProperty
public IComparer<TKey> Comparer {
- get { return _comparer; }
+ get { return cmp.cmp; }
}
- // 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);
- }
- }
-
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;
+
+ RBTree.Node n1 = new Node (key, value);
+ Node n2 = (Node) tree.Intern (key, n1);
+ if (n2 != n1)
+ n2.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
@@ -150,43 +155,30 @@
{
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);
- }
-
- _keys [index] = key;
- _values [index] = value;
- _size++;
- _version++;
+ RBTree.Node n1 = new Node (key, value);
+ Node n2 = (Node) tree.Intern (key, n1);
+ if (n2 != n1)
+ throw new ArgumentException ();
}
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)
@@ -195,12 +187,11 @@
throw new ArgumentNullException ();
if (arrayIndex < 0 || array.Length <= arrayIndex)
throw new ArgumentOutOfRangeException ();
- if (array.Length - arrayIndex < _size)
+ if (array.Length - arrayIndex < 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 [arrayIndex ++] = n.AsKV ();
}
public Enumerator GetEnumerator ()
@@ -208,73 +199,21 @@
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)
- {
- 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++;
- }
-
public bool TryGetValue (TKey key, out TValue value)
{
- int index = IndexOfKey (key);
- if (index >= 0) {
- value = _values [index];
- return true;
- }
-
- value = default (TValue) ;
- return false;
+ Node n = (Node) tree.Lookup (key);
+ value = n == null ? default (TValue) : n.value;
+ return n != null;
}
#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)
@@ -295,11 +234,11 @@
#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
@@ -313,8 +252,8 @@
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;
+ Node n = (Node) tree.Lookup (item.Key);
+ return n != null && item.Value.Equals (n.value);
}
bool ICollection<KeyValuePair<TKey,TValue>>.IsReadOnly {
@@ -323,10 +262,10 @@
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;
+ TValue value;
+ if (TryGetValue (item.Key, out value)) {
+ if (EqualityComparer<TValue>.Default.Equals
(item.Value, value))
+ return Remove (item.Key);
}
return false;
}
@@ -359,7 +298,7 @@
}
ICollection IDictionary.Keys {
- get { return GetKeyCollection (); }
+ get { return new KeyCollection (this); }
}
void IDictionary.Remove (object key)
@@ -367,19 +306,12 @@
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
@@ -392,12 +324,11 @@
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 {
@@ -461,13 +392,14 @@
throw new ArgumentNullException ();
if (arrayIndex < 0 || array.Length <=
arrayIndex)
throw new ArgumentOutOfRangeException
();
- if (array.Length - arrayIndex < _dic._size)
+ if (array.Length - arrayIndex < Count)
throw new ArgumentException ();
- Array.Copy (_dic._values, 0, array, arrayIndex,
_dic._size);
+ foreach (Node n in _dic.tree)
+ array [arrayIndex++] = n.value;
}
public int Count {
- get { return _dic._size; }
+ get { return _dic.Count; }
}
bool ICollection<TValue>.IsReadOnly {
@@ -489,15 +421,16 @@
return new Enumerator (_dic);
}
- void ICollection.CopyTo(Array array, int index)
+ void ICollection.CopyTo (Array array, int index)
{
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 {
@@ -515,43 +448,25 @@
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)
{
- _dic = dic;
- _version = dic._version;
- _index = -1;
- _count = dic._size;
+ host = dic.tree.GetEnumerator ();
}
public TValue Current {
- get {
- if (_count <= _index)
- throw new
InvalidOperationException ();
- return _dic._values [_index];
- }
+ get { return ((Node)
host.Current).value; }
}
public bool MoveNext ()
{
- if (_version != _dic._version)
- throw new
InvalidOperationException ();
-
- if (_index + 1 < _count) {
- _index ++;
- return true;
- }
-
- return false;
+ return host.MoveNext ();
}
public void Dispose ()
{
- _dic = null;
+ host.Dispose ();
}
object IEnumerator.Current {
@@ -560,9 +475,7 @@
void IEnumerator.Reset ()
{
- if (_version != _dic._version)
- throw new
InvalidOperationException ();
- _index = -1;
+ host.Reset ();
}
}
}
@@ -600,11 +513,18 @@
public void CopyTo (TKey [] array, int arrayIndex)
{
- Array.Copy (_dic._keys, 0, array, arrayIndex,
_dic._size);
+ if (array == null)
+ throw new ArgumentNullException ();
+ if (arrayIndex < 0 || array.Length <=
arrayIndex)
+ throw new ArgumentOutOfRangeException
();
+ if (array.Length - arrayIndex < Count)
+ throw new ArgumentException ();
+ foreach (Node n in _dic.tree)
+ array [arrayIndex++] = n.key;
}
public int Count {
- get { return _dic._size; }
+ get { return _dic.Count; }
}
bool ICollection<TKey>.IsReadOnly {
@@ -627,9 +547,10 @@
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 {
@@ -647,43 +568,25 @@
public struct Enumerator : IEnumerator<TKey>,
IEnumerator, IDisposable
{
- SortedDictionary<TKey,TValue> _dic;
- int _version;
- int _index;
- int _count;
+ RBTree.NodeEnumerator host;
internal Enumerator
(SortedDictionary<TKey,TValue> dic)
{
- _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 ((Node) host.Current).key;
}
}
public bool MoveNext ()
{
- if (_version != _dic._version)
- throw new
InvalidOperationException ();
-
- if (_index + 1 < _count) {
- _index ++;
- return true;
- }
-
- return false;
+ return host.MoveNext ();
}
public void Dispose ()
{
- _dic = null;
+ host.Dispose ();
}
object IEnumerator.Current {
@@ -692,9 +595,7 @@
void IEnumerator.Reset ()
{
- if (_version != _dic._version)
- throw new
InvalidOperationException ();
- _index = -1;
+ host.Reset ();
}
}
@@ -702,83 +603,46 @@
public struct Enumerator :
IEnumerator<KeyValuePair<TKey,TValue>>, IDisposable , IDictionaryEnumerator,
IEnumerator
{
- SortedDictionary<TKey,TValue> _dic;
- int _version;
- int _index;
- int _count;
+ RBTree.NodeEnumerator host;
internal Enumerator (SortedDictionary<TKey,TValue> dic)
{
- _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 ((Node) host.Current).AsKV (); }
}
public bool MoveNext ()
{
- if (_version != _dic._version)
- throw new InvalidOperationException ();
-
- if (_index + 1 < _count) {
- _index ++;
- return true;
- }
-
- return false;
+ return host.MoveNext ();
}
public void Dispose ()
{
- _dic = null;
+ host.Dispose ();
}
DictionaryEntry IDictionaryEnumerator.Entry {
- get {
- if (_count <= _index)
- throw new
InvalidOperationException ();
- return new DictionaryEntry (_dic._keys
[_index], _dic._values [_index]);
- }
+ get { return ((Node) host.Current).AsDE (); }
}
object IDictionaryEnumerator.Key {
- get {
- if (_count <= _index)
- throw new
InvalidOperationException ();
- return _dic._keys [_index];
- }
+ get { return ((Node) host.Current).key; }
}
object IDictionaryEnumerator.Value {
- get {
- if (_count <= _index)
- throw new
InvalidOperationException ();
- return _dic._values [_index];
- }
+ get { return ((Node) host.Current).value; }
}
object IEnumerator.Current {
- get {
- if (_count <= _index)
- throw new
InvalidOperationException ();
- return new DictionaryEntry (_dic._keys
[_index], _dic._values [_index]);
- }
+ get { return ((Node) host.Current).AsDE (); }
}
void IEnumerator.Reset ()
{
- if (_version != _dic._version)
- throw new InvalidOperationException ();
-
- _index = -1;
+ host.Reset ();
}
}
}
Modified: trunk/mcs/class/System/System.dll.sources
===================================================================
--- trunk/mcs/class/System/System.dll.sources 2007-05-01 18:58:31 UTC (rev
76536)
+++ trunk/mcs/class/System/System.dll.sources 2007-05-01 19:07:31 UTC (rev
76537)
@@ -138,6 +138,7 @@
System.CodeDom/MemberAttributes.cs
System.Collections.Generic/LinkedList.cs
System.Collections.Generic/LinkedListNode.cs
+System.Collections.Generic/RBTree.cs
System.Collections.Generic/Queue.cs
System.Collections.Generic/SortedDictionary.cs
System.Collections.Generic/SortedList.cs
Modified: trunk/mcs/class/System/Test/System.Collections.Generic/ChangeLog
===================================================================
--- trunk/mcs/class/System/Test/System.Collections.Generic/ChangeLog
2007-05-01 18:58:31 UTC (rev 76536)
+++ trunk/mcs/class/System/Test/System.Collections.Generic/ChangeLog
2007-05-01 19:07:31 UTC (rev 76537)
@@ -1,3 +1,7 @@
+2007-05-02 Raja R Harinath <[EMAIL PROTECTED]>
+
+ * SortedDictionaryTest.cs (AddNullKeyNullable): Enable.
+
2007-04-19 Gert Driesen <[EMAIL PROTECTED]>
* QueueTest.cs: Removed usage of deprecated Assertion class. Added
Modified:
trunk/mcs/class/System/Test/System.Collections.Generic/SortedDictionaryTest.cs
===================================================================
---
trunk/mcs/class/System/Test/System.Collections.Generic/SortedDictionaryTest.cs
2007-05-01 18:58:31 UTC (rev 76536)
+++
trunk/mcs/class/System/Test/System.Collections.Generic/SortedDictionaryTest.cs
2007-05-01 19:07:31 UTC (rev 76537)
@@ -134,11 +134,9 @@
[Test]
[ExpectedException (typeof (ArgumentNullException))]
- [Category ("NotWorking")] // see bug #78019
public void AddNullKeyNullable ()
{
- SortedDictionary<Nullable<int>,string> d =
- new SortedDictionary<Nullable<int>,string> ();
+ SortedDictionary<int?,string> d = new
SortedDictionary<int?,string> ();
d.Add (null, "TEST");
}
_______________________________________________
Mono-patches maillist - [email protected]
http://lists.ximian.com/mailman/listinfo/mono-patches
