Code Coverage Statistics for Source File

c:\Tools\SD3\src\Libraries\ICSharpCode.TextEditor\Project\Src\Util\AugmentableRedBlackTree.cs

Sequence Point Coverage N/A 0 of 0	Branch Coverage N/A 0 of 0	Lines 590

Sequence Point Coverage

N/A

0 of 0

Branch Coverage

N/A

0 of 0

Lines

590

Highlight: Uncovered Code Covered Code


// <file>
//     <copyright see="prj:///doc/copyright.txt"/>
//     <license see="prj:///doc/license.txt"/>
//     <owner name="Daniel Grunwald" email="daniel@danielgrunwald.de"/>
//     <version>$Revision: 2497 $</version>
// </file>

using System;
using System.Text;
using System.Diagnostics;
using System.Collections.Generic;

namespace ICSharpCode.TextEditor.Util
{
	internal sealed class RedBlackTreeNode<T>
	{
		internal RedBlackTreeNode<T> left, right, parent;
		internal T val;
		internal bool color;
		
		internal RedBlackTreeNode(T val)
		{
			this.val = val;
		}
		
		internal RedBlackTreeNode<T> LeftMost {
			get {
				RedBlackTreeNode<T> node = this;
				while (node.left != null)
					node = node.left;
				return node;
			}
		}
		
		internal RedBlackTreeNode<T> RightMost {
			get {
				RedBlackTreeNode<T> node = this;
				while (node.right != null)
					node = node.right;
				return node;
			}
		}
	}
	
	internal interface IRedBlackTreeHost<T> : IComparer<T>
	{
		bool Equals(T a, T b);
		
		void UpdateAfterChildrenChange(RedBlackTreeNode<T> node);
		void UpdateAfterRotateLeft(RedBlackTreeNode<T> node);
		void UpdateAfterRotateRight(RedBlackTreeNode<T> node);
	}
	
	/// <summary>
	/// Description of RedBlackTree.
	/// </summary>
	internal sealed class AugmentableRedBlackTree<T, Host> : ICollection<T> where Host : IRedBlackTreeHost<T>
	{
		readonly Host host;
		int count;
		internal RedBlackTreeNode<T> root;
		
		public AugmentableRedBlackTree(Host host)
		{
			if (host == null) throw new ArgumentNullException("host");
			this.host = host;
		}
		
		public int Count {
			get { return count; }
		}
		
		public void Clear()
		{
			root = null;
			count = 0;
		}
		
		#region Debugging code
		#if DEBUG
		/// <summary>
		/// Check tree for consistency and being balanced.
		/// </summary>
		[Conditional("DATACONSISTENCYTEST")]
		void CheckProperties()
		{
			int blackCount = -1;
			CheckNodeProperties(root, null, RED, 0, ref blackCount);
			
			int nodeCount = 0;
			foreach (T val in this) {
				nodeCount++;
			}
			Debug.Assert(count == nodeCount);
		}
		
		/*
		1. A node is either red or black.
		2. The root is black.
		3. All leaves are black. (The leaves are the NIL children.)
		4. Both children of every red node are black. (So every red node must have a black parent.)
		5. Every simple path from a node to a descendant leaf contains the same number of black nodes. (Not counting the leaf node.)
		 */
		void CheckNodeProperties(RedBlackTreeNode<T> node, RedBlackTreeNode<T> parentNode, bool parentColor, int blackCount, ref int expectedBlackCount)
		{
			if (node == null) return;
			
			Debug.Assert(node.parent == parentNode);
			
			if (parentColor == RED) {
				Debug.Assert(node.color == BLACK);
			}
			if (node.color == BLACK) {
				blackCount++;
			}
			if (node.left == null && node.right == null) {
				// node is a leaf node:
				if (expectedBlackCount == -1)
					expectedBlackCount = blackCount;
				else
					Debug.Assert(expectedBlackCount == blackCount);
			}
			CheckNodeProperties(node.left, node, node.color, blackCount, ref expectedBlackCount);
			CheckNodeProperties(node.right, node, node.color, blackCount, ref expectedBlackCount);
		}
		
		public string GetTreeAsString()
		{
			StringBuilder b = new StringBuilder();
			AppendTreeToString(root, b, 0);
			return b.ToString();
		}
		
		static void AppendTreeToString(RedBlackTreeNode<T> node, StringBuilder b, int indent)
		{
			if (node.color == RED)
				b.Append("RED   ");
			else
				b.Append("BLACK ");
			b.AppendLine(node.val.ToString());
			indent += 2;
			if (node.left != null) {
				b.Append(' ', indent);
				b.Append("L: ");
				AppendTreeToString(node.left, b, indent);
			}
			if (node.right != null) {
				b.Append(' ', indent);
				b.Append("R: ");
				AppendTreeToString(node.right, b, indent);
			}
		}
		#endif
		#endregion
		
		#region Add
		public void Add(T item)
		{
			AddInternal(new RedBlackTreeNode<T>(item));
			#if DEBUG
			CheckProperties();
			#endif
		}
		
		void AddInternal(RedBlackTreeNode<T> newNode)
		{
			Debug.Assert(newNode.color == BLACK);
			if (root == null) {
				count = 1;
				root = newNode;
				return;
			}
			// Insert into the tree
			RedBlackTreeNode<T> parentNode = root;
			while (true) {
				if (host.Compare(newNode.val, parentNode.val) <= 0) {
					if (parentNode.left == null) {
						InsertAsLeft(parentNode, newNode);
						return;
					}
					parentNode = parentNode.left;
				} else {
					if (parentNode.right == null) {
						InsertAsRight(parentNode, newNode);
						return;
					}
					parentNode = parentNode.right;
				}
			}
		}
		
		internal void InsertAsLeft(RedBlackTreeNode<T> parentNode, RedBlackTreeNode<T> newNode)
		{
			Debug.Assert(parentNode.left == null);
			parentNode.left = newNode;
			newNode.parent = parentNode;
			newNode.color = RED;
			host.UpdateAfterChildrenChange(parentNode);
			FixTreeOnInsert(newNode);
			count++;
		}
		
		internal void InsertAsRight(RedBlackTreeNode<T> parentNode, RedBlackTreeNode<T> newNode)
		{
			Debug.Assert(parentNode.right == null);
			parentNode.right = newNode;
			newNode.parent = parentNode;
			newNode.color = RED;
			host.UpdateAfterChildrenChange(parentNode);
			FixTreeOnInsert(newNode);
			count++;
		}
		
		void FixTreeOnInsert(RedBlackTreeNode<T> node)
		{
			Debug.Assert(node != null);
			Debug.Assert(node.color == RED);
			Debug.Assert(node.left == null || node.left.color == BLACK);
			Debug.Assert(node.right == null || node.right.color == BLACK);
			
			RedBlackTreeNode<T> parentNode = node.parent;
			if (parentNode == null) {
				// we inserted in the root -> the node must be black
				// since this is a root node, making the node black increments the number of black nodes
				// on all paths by one, so it is still the same for all paths.
				node.color = BLACK;
				return;
			}
			if (parentNode.color == BLACK) {
				// if the parent node where we inserted was black, our red node is placed correctly.
				// since we inserted a red node, the number of black nodes on each path is unchanged
				// -> the tree is still balanced
				return;
			}
			// parentNode is red, so there is a conflict here!
			
			// because the root is black, parentNode is not the root -> there is a grandparent node
			RedBlackTreeNode<T> grandparentNode = parentNode.parent;
			RedBlackTreeNode<T> uncleNode = Sibling(parentNode);
			if (uncleNode != null && uncleNode.color == RED) {
				parentNode.color = BLACK;
				uncleNode.color = BLACK;
				grandparentNode.color = RED;
				FixTreeOnInsert(grandparentNode);
				return;
			}
			// now we know: parent is red but uncle is black
			// First rotation:
			if (node == parentNode.right && parentNode == grandparentNode.left) {
				RotateLeft(parentNode);
				node = node.left;
			} else if (node == parentNode.left && parentNode == grandparentNode.right) {
				RotateRight(parentNode);
				node = node.right;
			}
			// because node might have changed, reassign variables:
			parentNode = node.parent;
			grandparentNode = parentNode.parent;
			
			// Now recolor a bit:
			parentNode.color = BLACK;
			grandparentNode.color = RED;
			// Second rotation:
			if (node == parentNode.left && parentNode == grandparentNode.left) {
				RotateRight(grandparentNode);
			} else {
				// because of the first rotation, this is guaranteed:
				Debug.Assert(node == parentNode.right && parentNode == grandparentNode.right);
				RotateLeft(grandparentNode);
			}
		}
		
		void ReplaceNode(RedBlackTreeNode<T> replacedNode, RedBlackTreeNode<T> newNode)
		{
			if (replacedNode.parent == null) {
				Debug.Assert(replacedNode == root);
				root = newNode;
			} else {
				if (replacedNode.parent.left == replacedNode)
					replacedNode.parent.left = newNode;
				else
					replacedNode.parent.right = newNode;
			}
			if (newNode != null) {
				newNode.parent = replacedNode.parent;
			}
			replacedNode.parent = null;
		}
		
		void RotateLeft(RedBlackTreeNode<T> p)
		{
			// let q be p's right child
			RedBlackTreeNode<T> q = p.right;
			Debug.Assert(q != null);
			Debug.Assert(q.parent == p);
			// set q to be the new root
			ReplaceNode(p, q);
			
			// set p's right child to be q's left child
			p.right = q.left;
			if (p.right != null) p.right.parent = p;
			// set q's left child to be p
			q.left = p;
			p.parent = q;
			host.UpdateAfterRotateLeft(p);
		}
		
		void RotateRight(RedBlackTreeNode<T> p)
		{
			// let q be p's left child
			RedBlackTreeNode<T> q = p.left;
			Debug.Assert(q != null);
			Debug.Assert(q.parent == p);
			// set q to be the new root
			ReplaceNode(p, q);
			
			// set p's left child to be q's right child
			p.left = q.right;
			if (p.left != null) p.left.parent = p;
			// set q's right child to be p
			q.right = p;
			p.parent = q;
			host.UpdateAfterRotateRight(p);
		}
		
		RedBlackTreeNode<T> Sibling(RedBlackTreeNode<T> node)
		{
			if (node == node.parent.left)
				return node.parent.right;
			else
				return node.parent.left;
		}
		#endregion
		
		#region Remove
		public void RemoveAt(RedBlackTreeIterator<T> iterator)
		{
			RedBlackTreeNode<T> node = iterator.node;
			if (node == null)
				throw new ArgumentException("Invalid iterator");
			while (node.parent != null)
				node = node.parent;
			if (node != root)
				throw new ArgumentException("Iterator does not belong to this tree");
			RemoveNode(iterator.node);
			#if DEBUG
			CheckProperties();
			#endif
		}
		
		internal void RemoveNode(RedBlackTreeNode<T> removedNode)
		{
			if (removedNode.left != null && removedNode.right != null) {
				// replace removedNode with it's in-order successor
				
				RedBlackTreeNode<T> leftMost = removedNode.right.LeftMost;
				RemoveNode(leftMost); // remove leftMost from its current location
				
				// and overwrite the removedNode with it
				ReplaceNode(removedNode, leftMost);
				leftMost.left = removedNode.left;
				if (leftMost.left != null) leftMost.left.parent = leftMost;
				leftMost.right = removedNode.right;
				if (leftMost.right != null) leftMost.right.parent = leftMost;
				leftMost.color = removedNode.color;
				
				host.UpdateAfterChildrenChange(leftMost);
				if (leftMost.parent != null) host.UpdateAfterChildrenChange(leftMost.parent);
				return;
			}
			
			count--;
			
			// now either removedNode.left or removedNode.right is null
			// get the remaining child
			RedBlackTreeNode<T> parentNode = removedNode.parent;
			RedBlackTreeNode<T> childNode = removedNode.left ?? removedNode.right;
			ReplaceNode(removedNode, childNode);
			if (parentNode != null) host.UpdateAfterChildrenChange(parentNode);
			if (removedNode.color == BLACK) {
				if (childNode != null && childNode.color == RED) {
					childNode.color = BLACK;
				} else {
					FixTreeOnDelete(childNode, parentNode);
				}
			}
		}
		
		static RedBlackTreeNode<T> Sibling(RedBlackTreeNode<T> node, RedBlackTreeNode<T> parentNode)
		{
			Debug.Assert(node == null || node.parent == parentNode);
			if (node == parentNode.left)
				return parentNode.right;
			else
				return parentNode.left;
		}
		
		const bool RED = true;
		const bool BLACK = false;
		
		static bool GetColor(RedBlackTreeNode<T> node)
		{
			return node != null ? node.color : BLACK;
		}
		
		void FixTreeOnDelete(RedBlackTreeNode<T> node, RedBlackTreeNode<T> parentNode)
		{
			Debug.Assert(node == null || node.parent == parentNode);
			if (parentNode == null)
				return;
			
			// warning: node may be null
			RedBlackTreeNode<T> sibling = Sibling(node, parentNode);
			if (sibling.color == RED) {
				parentNode.color = RED;
				sibling.color = BLACK;
				if (node == parentNode.left) {
					RotateLeft(parentNode);
				} else {
					RotateRight(parentNode);
				}
				
				sibling = Sibling(node, parentNode); // update value of sibling after rotation
			}
			
			if (parentNode.color == BLACK
			    && sibling.color == BLACK
			    && GetColor(sibling.left) == BLACK
			    && GetColor(sibling.right) == BLACK)
			{
				sibling.color = RED;
				FixTreeOnDelete(parentNode, parentNode.parent);
				return;
			}
			
			if (parentNode.color == RED
			    && sibling.color == BLACK
			    && GetColor(sibling.left) == BLACK
			    && GetColor(sibling.right) == BLACK)
			{
				sibling.color = RED;
				parentNode.color = BLACK;
				return;
			}
			
			if (node == parentNode.left &&
			    sibling.color == BLACK &&
			    GetColor(sibling.left) == RED &&
			    GetColor(sibling.right) == BLACK)
			{
				sibling.color = RED;
				sibling.left.color = BLACK;
				RotateRight(sibling);
			}
			else if (node == parentNode.right &&
			         sibling.color == BLACK &&
			         GetColor(sibling.right) == RED &&
			         GetColor(sibling.left) == BLACK)
			{
				sibling.color = RED;
				sibling.right.color = BLACK;
				RotateLeft(sibling);
			}
			sibling = Sibling(node, parentNode); // update value of sibling after rotation
			
			sibling.color = parentNode.color;
			parentNode.color = BLACK;
			if (node == parentNode.left) {
				if (sibling.right != null) {
					Debug.Assert(sibling.right.color == RED);
					sibling.right.color = BLACK;
				}
				RotateLeft(parentNode);
			} else {
				if (sibling.left != null) {
					Debug.Assert(sibling.left.color == RED);
					sibling.left.color = BLACK;
				}
				RotateRight(parentNode);
			}
		}
		#endregion
		
		#region Find/LowerBound/UpperBound/GetEnumerator
		/// <summary>
		/// Returns the iterator pointing to the specified item, or an iterator in End state if the item is not found.
		/// </summary>
		public RedBlackTreeIterator<T> Find(T item)
		{
			RedBlackTreeIterator<T> it = LowerBound(item);
			while (it.IsValid && host.Compare(it.Current, item) == 0) {
				if (host.Equals(it.Current, item))
					return it;
				it.MoveNext();
			}
			return default(RedBlackTreeIterator<T>);
		}
		
		/// <summary>
		/// Returns the iterator pointing to the first item greater or equal to <paramref name="item"/>.
		/// </summary>
		public RedBlackTreeIterator<T> LowerBound(T item)
		{
			RedBlackTreeNode<T> node = root;
			RedBlackTreeNode<T> resultNode = null;
			while (node != null) {
				if (host.Compare(node.val, item) < 0) {
					node = node.right;
				} else {
					resultNode = node;
					node = node.left;
				}
			}
			return new RedBlackTreeIterator<T>(resultNode);
		}
		
		/// <summary>
		/// Returns the iterator pointing to the first item greater than <paramref name="item"/>.
		/// </summary>
		public RedBlackTreeIterator<T> UpperBound(T item)
		{
			RedBlackTreeIterator<T> it = LowerBound(item);
			while (it.IsValid && host.Compare(it.Current, item) == 0) {
				it.MoveNext();
			}
			return it;
		}
		
		/// <summary>
		/// Gets a tree iterator that starts on the first node.
		/// </summary>
		public RedBlackTreeIterator<T> Begin()
		{
			if (root == null) return default(RedBlackTreeIterator<T>);
			return new RedBlackTreeIterator<T>(root.LeftMost);
		}
		
		/// <summary>
		/// Gets a tree iterator that starts one node before the first node.
		/// </summary>
		public RedBlackTreeIterator<T> GetEnumerator()
		{
			if (root == null) return default(RedBlackTreeIterator<T>);
			RedBlackTreeNode<T> dummyNode = new RedBlackTreeNode<T>(default(T));
			dummyNode.right = root;
			return new RedBlackTreeIterator<T>(dummyNode);
		}
		#endregion
		
		#region ICollection members
		public bool Contains(T item)
		{
			return Find(item).IsValid;
		}
		
		public bool Remove(T item)
		{
			RedBlackTreeIterator<T> it = Find(item);
			if (!it.IsValid) {
				return false;
			} else {
				RemoveAt(it);
				return true;
			}
		}
		
		IEnumerator<T> IEnumerable<T>.GetEnumerator()
		{
			return GetEnumerator();
		}
		
		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return GetEnumerator();
		}
		
		bool ICollection<T>.IsReadOnly {
			get { return false; }
		}
		
		public void CopyTo(T[] array, int arrayIndex)
		{
			if (array == null) throw new ArgumentNullException("array");
			foreach (T val in this) {
				array[arrayIndex++] = val;
			}
		}
		#endregion
	}
}

L	V	Source
1		// <file>
2		// <copyright see="prj:///doc/copyright.txt"/>
3		// <license see="prj:///doc/license.txt"/>
4		// <owner name="Daniel Grunwald" email="daniel@danielgrunwald.de"/>
5		// <version>$Revision: 2497 $</version>
6		// </file>
7
8		using System;
9		using System.Text;
10		using System.Diagnostics;
11		using System.Collections.Generic;
12
13		namespace ICSharpCode.TextEditor.Util
14		{
15		internal sealed class RedBlackTreeNode<T>
16		{
17		internal RedBlackTreeNode<T> left, right, parent;
18		internal T val;
19		internal bool color;
20
21		internal RedBlackTreeNode(T val)
22		{
23		this.val = val;
24		}
25
26		internal RedBlackTreeNode<T> LeftMost {
27		get {
28		RedBlackTreeNode<T> node = this;
29		while (node.left != null)
30		node = node.left;
31		return node;
32		}
33		}
34
35		internal RedBlackTreeNode<T> RightMost {
36		get {
37		RedBlackTreeNode<T> node = this;
38		while (node.right != null)
39		node = node.right;
40		return node;
41		}
42		}
43		}
44
45		internal interface IRedBlackTreeHost<T> : IComparer<T>
46		{
47		bool Equals(T a, T b);
48
49		void UpdateAfterChildrenChange(RedBlackTreeNode<T> node);
50		void UpdateAfterRotateLeft(RedBlackTreeNode<T> node);
51		void UpdateAfterRotateRight(RedBlackTreeNode<T> node);
52		}
53
54		/// <summary>
55		/// Description of RedBlackTree.
56		/// </summary>
57		internal sealed class AugmentableRedBlackTree<T, Host> : ICollection<T> where Host : IRedBlackTreeHost<T>
58		{
59		readonly Host host;
60		int count;
61		internal RedBlackTreeNode<T> root;
62
63		public AugmentableRedBlackTree(Host host)
64		{
65		if (host == null) throw new ArgumentNullException("host");
66		this.host = host;
67		}
68
69		public int Count {
70		get { return count; }
71		}
72
73		public void Clear()
74		{
75		root = null;
76		count = 0;
77		}
78
79		#region Debugging code
80		#if DEBUG
81		/// <summary>
82		/// Check tree for consistency and being balanced.
83		/// </summary>
84		[Conditional("DATACONSISTENCYTEST")]
85		void CheckProperties()
86		{
87		int blackCount = -1;
88		CheckNodeProperties(root, null, RED, 0, ref blackCount);
89
90		int nodeCount = 0;
91		foreach (T val in this) {
92		nodeCount++;
93		}
94		Debug.Assert(count == nodeCount);
95		}
96
97		/*
98		1. A node is either red or black.
99		2. The root is black.
100		3. All leaves are black. (The leaves are the NIL children.)
101		4. Both children of every red node are black. (So every red node must have a black parent.)
102		5. Every simple path from a node to a descendant leaf contains the same number of black nodes. (Not counting the leaf node.)
103		*/
104		void CheckNodeProperties(RedBlackTreeNode<T> node, RedBlackTreeNode<T> parentNode, bool parentColor, int blackCount, ref int expectedBlackCount)
105		{
106		if (node == null) return;
107
108		Debug.Assert(node.parent == parentNode);
109
110		if (parentColor == RED) {
111		Debug.Assert(node.color == BLACK);
112		}
113		if (node.color == BLACK) {
114		blackCount++;
115		}
116		if (node.left == null && node.right == null) {
117		// node is a leaf node:
118		if (expectedBlackCount == -1)
119		expectedBlackCount = blackCount;
120		else
121		Debug.Assert(expectedBlackCount == blackCount);
122		}
123		CheckNodeProperties(node.left, node, node.color, blackCount, ref expectedBlackCount);
124		CheckNodeProperties(node.right, node, node.color, blackCount, ref expectedBlackCount);
125		}
126
127		public string GetTreeAsString()
128		{
129		StringBuilder b = new StringBuilder();
130		AppendTreeToString(root, b, 0);
131		return b.ToString();
132		}
133
134		static void AppendTreeToString(RedBlackTreeNode<T> node, StringBuilder b, int indent)
135		{
136		if (node.color == RED)
137		b.Append("RED ");
138		else
139		b.Append("BLACK ");
140		b.AppendLine(node.val.ToString());
141		indent += 2;
142		if (node.left != null) {
143		b.Append(' ', indent);
144		b.Append("L: ");
145		AppendTreeToString(node.left, b, indent);
146		}
147		if (node.right != null) {
148		b.Append(' ', indent);
149		b.Append("R: ");
150		AppendTreeToString(node.right, b, indent);
151		}
152		}
153		#endif
154		#endregion
155
156		#region Add
157		public void Add(T item)
158		{
159		AddInternal(new RedBlackTreeNode<T>(item));
160		#if DEBUG
161		CheckProperties();
162		#endif
163		}
164
165		void AddInternal(RedBlackTreeNode<T> newNode)
166		{
167		Debug.Assert(newNode.color == BLACK);
168		if (root == null) {
169		count = 1;
170		root = newNode;
171		return;
172		}
173		// Insert into the tree
174		RedBlackTreeNode<T> parentNode = root;
175		while (true) {
176		if (host.Compare(newNode.val, parentNode.val) <= 0) {
177		if (parentNode.left == null) {
178		InsertAsLeft(parentNode, newNode);
179		return;
180		}
181		parentNode = parentNode.left;
182		} else {
183		if (parentNode.right == null) {
184		InsertAsRight(parentNode, newNode);
185		return;
186		}
187		parentNode = parentNode.right;
188		}
189		}
190		}
191
192		internal void InsertAsLeft(RedBlackTreeNode<T> parentNode, RedBlackTreeNode<T> newNode)
193		{
194		Debug.Assert(parentNode.left == null);
195		parentNode.left = newNode;
196		newNode.parent = parentNode;
197		newNode.color = RED;
198		host.UpdateAfterChildrenChange(parentNode);
199		FixTreeOnInsert(newNode);
200		count++;
201		}
202
203		internal void InsertAsRight(RedBlackTreeNode<T> parentNode, RedBlackTreeNode<T> newNode)
204		{
205		Debug.Assert(parentNode.right == null);
206		parentNode.right = newNode;
207		newNode.parent = parentNode;
208		newNode.color = RED;
209		host.UpdateAfterChildrenChange(parentNode);
210		FixTreeOnInsert(newNode);
211		count++;
212		}
213
214		void FixTreeOnInsert(RedBlackTreeNode<T> node)
215		{
216		Debug.Assert(node != null);
217		Debug.Assert(node.color == RED);
218		Debug.Assert(node.left == null \|\| node.left.color == BLACK);
219		Debug.Assert(node.right == null \|\| node.right.color == BLACK);
220
221		RedBlackTreeNode<T> parentNode = node.parent;
222		if (parentNode == null) {
223		// we inserted in the root -> the node must be black
224		// since this is a root node, making the node black increments the number of black nodes
225		// on all paths by one, so it is still the same for all paths.
226		node.color = BLACK;
227		return;
228		}
229		if (parentNode.color == BLACK) {
230		// if the parent node where we inserted was black, our red node is placed correctly.
231		// since we inserted a red node, the number of black nodes on each path is unchanged
232		// -> the tree is still balanced
233		return;
234		}
235		// parentNode is red, so there is a conflict here!
236
237		// because the root is black, parentNode is not the root -> there is a grandparent node
238		RedBlackTreeNode<T> grandparentNode = parentNode.parent;
239		RedBlackTreeNode<T> uncleNode = Sibling(parentNode);
240		if (uncleNode != null && uncleNode.color == RED) {
241		parentNode.color = BLACK;
242		uncleNode.color = BLACK;
243		grandparentNode.color = RED;
244		FixTreeOnInsert(grandparentNode);
245		return;
246		}
247		// now we know: parent is red but uncle is black
248		// First rotation:
249		if (node == parentNode.right && parentNode == grandparentNode.left) {
250		RotateLeft(parentNode);
251		node = node.left;
252		} else if (node == parentNode.left && parentNode == grandparentNode.right) {
253		RotateRight(parentNode);
254		node = node.right;
255		}
256		// because node might have changed, reassign variables:
257		parentNode = node.parent;
258		grandparentNode = parentNode.parent;
259
260		// Now recolor a bit:
261		parentNode.color = BLACK;
262		grandparentNode.color = RED;
263		// Second rotation:
264		if (node == parentNode.left && parentNode == grandparentNode.left) {
265		RotateRight(grandparentNode);
266		} else {
267		// because of the first rotation, this is guaranteed:
268		Debug.Assert(node == parentNode.right && parentNode == grandparentNode.right);
269		RotateLeft(grandparentNode);
270		}
271		}
272
273		void ReplaceNode(RedBlackTreeNode<T> replacedNode, RedBlackTreeNode<T> newNode)
274		{
275		if (replacedNode.parent == null) {
276		Debug.Assert(replacedNode == root);
277		root = newNode;
278		} else {
279		if (replacedNode.parent.left == replacedNode)
280		replacedNode.parent.left = newNode;
281		else
282		replacedNode.parent.right = newNode;
283		}
284		if (newNode != null) {
285		newNode.parent = replacedNode.parent;
286		}
287		replacedNode.parent = null;
288		}
289
290		void RotateLeft(RedBlackTreeNode<T> p)
291		{
292		// let q be p's right child
293		RedBlackTreeNode<T> q = p.right;
294		Debug.Assert(q != null);
295		Debug.Assert(q.parent == p);
296		// set q to be the new root
297		ReplaceNode(p, q);
298
299		// set p's right child to be q's left child
300		p.right = q.left;
301		if (p.right != null) p.right.parent = p;
302		// set q's left child to be p
303		q.left = p;
304		p.parent = q;
305		host.UpdateAfterRotateLeft(p);
306		}
307
308		void RotateRight(RedBlackTreeNode<T> p)
309		{
310		// let q be p's left child
311		RedBlackTreeNode<T> q = p.left;
312		Debug.Assert(q != null);
313		Debug.Assert(q.parent == p);
314		// set q to be the new root
315		ReplaceNode(p, q);
316
317		// set p's left child to be q's right child
318		p.left = q.right;
319		if (p.left != null) p.left.parent = p;
320		// set q's right child to be p
321		q.right = p;
322		p.parent = q;
323		host.UpdateAfterRotateRight(p);
324		}
325
326		RedBlackTreeNode<T> Sibling(RedBlackTreeNode<T> node)
327		{
328		if (node == node.parent.left)
329		return node.parent.right;
330		else
331		return node.parent.left;
332		}
333		#endregion
334
335		#region Remove
336		public void RemoveAt(RedBlackTreeIterator<T> iterator)
337		{
338		RedBlackTreeNode<T> node = iterator.node;
339		if (node == null)
340		throw new ArgumentException("Invalid iterator");
341		while (node.parent != null)
342		node = node.parent;
343		if (node != root)
344		throw new ArgumentException("Iterator does not belong to this tree");
345		RemoveNode(iterator.node);
346		#if DEBUG
347		CheckProperties();
348		#endif
349		}
350
351		internal void RemoveNode(RedBlackTreeNode<T> removedNode)
352		{
353		if (removedNode.left != null && removedNode.right != null) {
354		// replace removedNode with it's in-order successor
355
356		RedBlackTreeNode<T> leftMost = removedNode.right.LeftMost;
357		RemoveNode(leftMost); // remove leftMost from its current location
358
359		// and overwrite the removedNode with it
360		ReplaceNode(removedNode, leftMost);
361		leftMost.left = removedNode.left;
362		if (leftMost.left != null) leftMost.left.parent = leftMost;
363		leftMost.right = removedNode.right;
364		if (leftMost.right != null) leftMost.right.parent = leftMost;
365		leftMost.color = removedNode.color;
366
367		host.UpdateAfterChildrenChange(leftMost);
368		if (leftMost.parent != null) host.UpdateAfterChildrenChange(leftMost.parent);
369		return;
370		}
371
372		count--;
373
374		// now either removedNode.left or removedNode.right is null
375		// get the remaining child
376		RedBlackTreeNode<T> parentNode = removedNode.parent;
377		RedBlackTreeNode<T> childNode = removedNode.left ?? removedNode.right;
378		ReplaceNode(removedNode, childNode);
379		if (parentNode != null) host.UpdateAfterChildrenChange(parentNode);
380		if (removedNode.color == BLACK) {
381		if (childNode != null && childNode.color == RED) {
382		childNode.color = BLACK;
383		} else {
384		FixTreeOnDelete(childNode, parentNode);
385		}
386		}
387		}
388
389		static RedBlackTreeNode<T> Sibling(RedBlackTreeNode<T> node, RedBlackTreeNode<T> parentNode)
390		{
391		Debug.Assert(node == null \|\| node.parent == parentNode);
392		if (node == parentNode.left)
393		return parentNode.right;
394		else
395		return parentNode.left;
396		}
397
398		const bool RED = true;
399		const bool BLACK = false;
400
401		static bool GetColor(RedBlackTreeNode<T> node)
402		{
403		return node != null ? node.color : BLACK;
404		}
405
406		void FixTreeOnDelete(RedBlackTreeNode<T> node, RedBlackTreeNode<T> parentNode)
407		{
408		Debug.Assert(node == null \|\| node.parent == parentNode);
409		if (parentNode == null)
410		return;
411
412		// warning: node may be null
413		RedBlackTreeNode<T> sibling = Sibling(node, parentNode);
414		if (sibling.color == RED) {
415		parentNode.color = RED;
416		sibling.color = BLACK;
417		if (node == parentNode.left) {
418		RotateLeft(parentNode);
419		} else {
420		RotateRight(parentNode);
421		}
422
423		sibling = Sibling(node, parentNode); // update value of sibling after rotation
424		}
425
426		if (parentNode.color == BLACK
427		&& sibling.color == BLACK
428		&& GetColor(sibling.left) == BLACK
429		&& GetColor(sibling.right) == BLACK)
430		{
431		sibling.color = RED;
432		FixTreeOnDelete(parentNode, parentNode.parent);
433		return;
434		}
435
436		if (parentNode.color == RED
437		&& sibling.color == BLACK
438		&& GetColor(sibling.left) == BLACK
439		&& GetColor(sibling.right) == BLACK)
440		{
441		sibling.color = RED;
442		parentNode.color = BLACK;
443		return;
444		}
445
446		if (node == parentNode.left &&
447		sibling.color == BLACK &&
448		GetColor(sibling.left) == RED &&
449		GetColor(sibling.right) == BLACK)
450		{
451		sibling.color = RED;
452		sibling.left.color = BLACK;
453		RotateRight(sibling);
454		}
455		else if (node == parentNode.right &&
456		sibling.color == BLACK &&
457		GetColor(sibling.right) == RED &&
458		GetColor(sibling.left) == BLACK)
459		{
460		sibling.color = RED;
461		sibling.right.color = BLACK;
462		RotateLeft(sibling);
463		}
464		sibling = Sibling(node, parentNode); // update value of sibling after rotation
465
466		sibling.color = parentNode.color;
467		parentNode.color = BLACK;
468		if (node == parentNode.left) {
469		if (sibling.right != null) {
470		Debug.Assert(sibling.right.color == RED);
471		sibling.right.color = BLACK;
472		}
473		RotateLeft(parentNode);
474		} else {
475		if (sibling.left != null) {
476		Debug.Assert(sibling.left.color == RED);
477		sibling.left.color = BLACK;
478		}
479		RotateRight(parentNode);
480		}
481		}
482		#endregion
483
484		#region Find/LowerBound/UpperBound/GetEnumerator
485		/// <summary>
486		/// Returns the iterator pointing to the specified item, or an iterator in End state if the item is not found.
487		/// </summary>
488		public RedBlackTreeIterator<T> Find(T item)
489		{
490		RedBlackTreeIterator<T> it = LowerBound(item);
491		while (it.IsValid && host.Compare(it.Current, item) == 0) {
492		if (host.Equals(it.Current, item))
493		return it;
494		it.MoveNext();
495		}
496		return default(RedBlackTreeIterator<T>);
497		}
498
499		/// <summary>
500		/// Returns the iterator pointing to the first item greater or equal to <paramref name="item"/>.