Fixed bug in the red black tree implementation.

I added unit tests for them - an earlier fix broke something, shadowed
the real issue. With tests this won't have happen.

3 files changed, 110 insertions, 0 deletions

diff --git a/main/tests/UnitTests/Makefile.am b/main/tests/UnitTests/Makefile.am
index a5a9a4f90e..b26d4afaad 100644
--- a/main/tests/UnitTests/Makefile.am
+++ b/main/tests/UnitTests/Makefile.am
@@ -49,6 +49,7 @@ FILES =  \
 	Mono.TextEditor.Tests/FoldingTests.cs \
 	Mono.TextEditor.Tests/InsertionModeTests.cs \
 	Mono.TextEditor.Tests/LineSplitterTests.cs \
+	Mono.TextEditor.Tests/RedBlackTreeTests.cs \
 	Mono.TextEditor.Tests/SearchTests.cs \
 	Mono.TextEditor.Tests/SegmentTreeTests.cs \
 	Mono.TextEditor.Tests/SelectionTests.cs \
diff --git a/main/tests/UnitTests/Mono.TextEditor.Tests/RedBlackTreeTests.cs b/main/tests/UnitTests/Mono.TextEditor.Tests/RedBlackTreeTests.cs
new file mode 100644
index 0000000000..6523c71423
--- /dev/null
+++ b/main/tests/UnitTests/Mono.TextEditor.Tests/RedBlackTreeTests.cs
@@ -0,0 +1,108 @@
+// 
+// RedBlackTreeTests.cs
+//  
+// Author:
+//       Mike Krüger <mkrueger@novell.com>
+// 
+// Copyright (c) 2011 Novell, Inc (http://www.novell.com)
+// 
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+// 
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+// 
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+using System;
+using Mono.TextEditor.Utils;
+using NUnit.Framework;
+
+namespace Mono.TextEditor.Tests
+{
+	[TestFixture()]
+	public class RedBlackTreeTests
+	{
+		class TestNode : IRedBlackTreeNode, IComparable
+		{
+			int val;
+			
+			public TestNode (int val)
+			{
+				this.val = val;
+			}
+
+			#region IRedBlackTreeNode implementation
+			public void UpdateAugmentedData ()
+			{
+			}
+
+			public IRedBlackTreeNode Parent {
+				get;
+				set;
+			}
+
+			public IRedBlackTreeNode Left {
+				get;
+				set;
+			}
+
+			public IRedBlackTreeNode Right {
+				get;
+				set;
+			}
+
+			public RedBlackColor Color {
+				get;
+				set;
+			}
+			#endregion
+
+			#region IComparable implementation
+			public int CompareTo (object obj)
+			{
+				return val.CompareTo (((TestNode)obj).val);
+			}
+			#endregion
+		}
+		
+		[Test()]
+		public void TestRemoveBug ()
+		{
+			var tree = new RedBlackTree<TestNode> ();
+			TestNode t1 = new TestNode (1);
+			TestNode t2 = new TestNode (2);
+			TestNode t3 = new TestNode (3);
+			
+			tree.Add (t1);
+			tree.InsertRight (t1, t2);
+			tree.InsertLeft (t1, t3);
+			tree.Remove (t1);
+			Assert.AreEqual (2, tree.Count);
+		} 
+		
+		[Test()]
+		public void TestAddBug ()
+		{
+			var tree = new RedBlackTree<TestNode> ();
+			TestNode t1 = new TestNode (1);
+			TestNode t2 = new TestNode (2);
+			TestNode t3 = new TestNode (3);
+			
+			tree.Add (t1);
+			tree.Add (t2);
+			tree.Add (t3);
+			Assert.AreEqual (3, tree.Count);
+		} 
+	}
+}
+
diff --git a/main/tests/UnitTests/UnitTests.csproj b/main/tests/UnitTests/UnitTests.csproj
index 4ebaaad328..8ae5bdadf2 100644
--- a/main/tests/UnitTests/UnitTests.csproj
+++ b/main/tests/UnitTests/UnitTests.csproj
@@ -235,6 +235,7 @@
     <Compile Include="Mono.TextEditor.Tests\TextBreakerTests.cs" />
     <Compile Include="MonoDevelop.VersionControl.Git\GitUtilsTests.cs" />
     <Compile Include="Mono.TextEditor.Tests\SegmentTreeTests.cs" />
+    <Compile Include="Mono.TextEditor.Tests\RedBlackTreeTests.cs" />
   </ItemGroup>
   <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
   <Import Project="..\..\md.targets" />