Skip to content

Ghidra is a software reverse engineering (SRE) framework

10.7 KB
Raw Blame
/* ###
 * IP: GHIDRA
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package generic.stl;

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;

import generic.test.AbstractGenericTest;

public class RedBlackTreeTest extends AbstractGenericTest {
	RedBlackTree<Integer, String> tree;
	RedBlackTree<Integer, String> treeWithDups;

	public RedBlackTreeTest() {
		super();
	}
	
    @Before
    public void setUp() throws Exception {
		tree = new RedBlackTree<Integer, String>(new SelfComparator<Integer>(), false);
		treeWithDups = new RedBlackTree<Integer, String>(new SelfComparator<Integer>(), true);
		
		tree.put(5, "five");
		tree.put(10, "ten");
		tree.put(3, "three");
		tree.put(7, "seven");
		tree.put(1, "one");
		tree.put(9, "nine");
		tree.put(2, "two");
		tree.put(6, "six");
		tree.put(4, "four");
		

		treeWithDups.put(5, "five");
		treeWithDups.put(10, "ten");
		treeWithDups.put(3, "three");
		treeWithDups.put(7, "seven");
		treeWithDups.put(1, "one");
		treeWithDups.put(9, "nine");
		treeWithDups.put(2, "two");
		treeWithDups.put(6, "six");
		treeWithDups.put(4, "four");

		treeWithDups.put(1, "one-a");
		treeWithDups.put(1, "one-b");
		treeWithDups.put(5, "five-a");
		treeWithDups.put(7, "seven-a");
		treeWithDups.put(1, "one-c");
		treeWithDups.put(5, "five-b");
		treeWithDups.put(5, "five-c");
		
	}
@Test
    public void testSize() {
		assertEquals(9, tree.size());
		assertEquals(16, treeWithDups.size());
	}
	
@Test
    public void testPut() {
		Pair<RedBlackNode<Integer, String>, Boolean> result = tree.put( 5, "five - dup" );
		assertTrue( !result.second );
		
		result = tree.put( 3, "three - dup" );
		assertTrue( !result.second );
		
		result = tree.put( 200, "two hundred" );
		assertTrue( result.second );
		
		treeWithDups.put( 5, "five - dup" );
		assertTrue( result.second );
		
		result = treeWithDups.put( 200, "two hundred" );
		assertTrue( result.second );
	}
	
@Test
    public void testContains() {
		assertTrue(tree.containsKey(1));
		assertTrue(tree.containsKey(2));
		assertTrue(tree.containsKey(3));
		assertTrue(tree.containsKey(4));
		assertTrue(tree.containsKey(5));
		assertTrue(tree.containsKey(6));
		assertTrue(tree.containsKey(7));
		assertTrue(tree.containsKey(9));
		assertTrue(tree.containsKey(10));

		assertTrue(!tree.containsKey(0));
		assertTrue(!tree.containsKey(11));
		assertTrue(!tree.containsKey(8));
		
		assertTrue(treeWithDups.containsKey(1));
		assertTrue(treeWithDups.containsKey(2));
		assertTrue(treeWithDups.containsKey(3));
		assertTrue(treeWithDups.containsKey(4));
		assertTrue(treeWithDups.containsKey(5));
		assertTrue(treeWithDups.containsKey(6));
		assertTrue(treeWithDups.containsKey(7));
		assertTrue(treeWithDups.containsKey(9));
		assertTrue(treeWithDups.containsKey(10));

		assertTrue(!treeWithDups.containsKey(0));
		assertTrue(!treeWithDups.containsKey(11));
		assertTrue(!treeWithDups.containsKey(8));
		
	}
@Test
    public void testGetFirstLast() {
		RedBlackNode<Integer,String> node = tree.getFirst();
		assertEquals(1, (int)node.getKey());
		
		node = treeWithDups.getFirst();
		assertEquals(1, (int)node.getKey());

		node = tree.getLast();
		assertEquals(10, (int)node.getKey());
		node = treeWithDups.getLast();
		assertEquals(10, (int)node.getKey());

	}
	
@Test
    public void testUpperBound() {
		RedBlackNode<Integer,String> node = tree.upperBound(-1);
		assertEquals(1, (int)node.getKey());
		node = tree.upperBound(2);
		assertEquals(3, (int)node.getKey());
		node = tree.upperBound(7);
		assertEquals(9, (int)node.getKey());
		
		node = tree.upperBound(8);
		assertEquals(9, (int)node.getKey());

		node = tree.upperBound(10);
		assertEquals(null, node);
		node = tree.upperBound(20);
		assertEquals(null, node);

		
		node = treeWithDups.upperBound(-1);
		assertEquals(1, (int)node.getKey());
		node = treeWithDups.upperBound(2);
		assertEquals(3, (int)node.getKey());
		node = treeWithDups.upperBound(7);
		assertEquals(9, (int)node.getKey());
		
		node = treeWithDups.upperBound(4);
		assertEquals(5, (int)node.getKey());
		assertEquals("five", node.getValue());
		
		node = treeWithDups.upperBound(8);
		assertEquals(9, (int)node.getKey());

		node = treeWithDups.upperBound(10);
		assertEquals(null, node);
		node = treeWithDups.upperBound(20);
		assertEquals(null, node);
		
	}
@Test
    public void testLowerBound() {
		RedBlackNode<Integer,String> node = tree.lowerBound(12);
		assertNull(node);
		node = tree.lowerBound(9);
		assertEquals(9, (int)node.getKey());
		node = tree.lowerBound(8);
		assertEquals(9, (int)node.getKey());
		
		node = tree.lowerBound(3);
		assertEquals(3, (int)node.getKey());

		node = tree.lowerBound(1);
		assertEquals(1, (int)node.getKey());
		node = tree.lowerBound(-5);
		assertEquals(1, (int)node.getKey());

		node = treeWithDups.lowerBound(12);
		assertNull(node);
		node = treeWithDups.lowerBound(9);
		assertEquals(9, (int)node.getKey());
		node = treeWithDups.lowerBound(8);
		assertEquals(9, (int)node.getKey());

		node = treeWithDups.lowerBound(5);
		assertEquals(5, (int)node.getKey());
		assertEquals("five", node.getValue());
		
		node = treeWithDups.lowerBound(3);
		assertEquals(3, (int)node.getKey());

		node = treeWithDups.lowerBound(1);
		assertEquals(1, (int)node.getKey());
		assertEquals("one", node.getValue());
		
		node = treeWithDups.lowerBound(-5);
		assertEquals(1, (int)node.getKey());
		assertEquals("one", node.getValue());
		
	}
@Test
    public void testFindFirst() {
		RedBlackNode<Integer,String> node = tree.findFirstNode(7);
		assertNotNull(node);
		assertEquals(7, (int)node.key);
		
		node = tree.findFirstNode(8);
		assertNull(node);
			
		node = treeWithDups.findFirstNode(7);
		assertNotNull(node);
		assertEquals(7, (int)node.key);
		
		node = tree.findFirstNode(8);
		assertNull(node);
		
		node = tree.findFirstNode(5);
		assertNotNull(node);
		assertEquals("five", node.getValue());

	}
@Test
    public void testFindLast() {
		RedBlackNode<Integer,String> node = tree.findLastNode(7);
		assertNotNull(node);
		assertEquals(7, (int)node.key);
		assertEquals("seven", node.value);
		
		node = tree.findLastNode(8);
		assertNull(node);
			
		node = treeWithDups.findLastNode(7);
		assertNotNull(node);
		assertEquals(7, (int)node.key);
		assertEquals("seven-a", node.value);
		
		node = treeWithDups.findLastNode(8);
		assertNull(node);
		
		node = treeWithDups.findLastNode(5);
		assertNotNull(node);
		assertEquals("five-c", node.getValue());

	}	
@Test
    public void testGetNextNode() {
		RedBlackNode<Integer,String> node = tree.getFirst();
		assertEquals("one", node.value);
		node = node.getSuccessor();
		assertEquals("two", node.value);
		node = node.getSuccessor();
		assertEquals("three", node.value);
		node = node.getSuccessor();
		assertEquals("four", node.value);
		node = node.getSuccessor();
		assertEquals("five", node.value);
		node = node.getSuccessor();
		assertEquals("six", node.value);
		node = node.getSuccessor();
		assertEquals("seven", node.value);
		node = node.getSuccessor();
		assertEquals("nine", node.value);
		node = node.getSuccessor();
		assertEquals("ten", node.value);
		node = node.getSuccessor();
		assertNull(node);

	
		node = treeWithDups.getFirst();
		assertEquals("one", node.value);
		node = node.getSuccessor();
		assertEquals("one-a", node.value);
		node = node.getSuccessor();
		assertEquals("one-b", node.value);
		node = node.getSuccessor();
		assertEquals("one-c", node.value);
		node = node.getSuccessor();

		
		assertEquals("two", node.value);
		node = node.getSuccessor();
		assertEquals("three", node.value);
		node = node.getSuccessor();
		assertEquals("four", node.value);
		node = node.getSuccessor();
		assertEquals("five", node.value);
		node = node.getSuccessor();
		assertEquals("five-a", node.value);
		node = node.getSuccessor();
		assertEquals("five-b", node.value);
		node = node.getSuccessor();
		assertEquals("five-c", node.value);
		node = node.getSuccessor();
		assertEquals("six", node.value);
		node = node.getSuccessor();
		assertEquals("seven", node.value);
		node = node.getSuccessor();
		assertEquals("seven-a", node.value);
		node = node.getSuccessor();
		assertEquals("nine", node.value);
		node = node.getSuccessor();
		assertEquals("ten", node.value);
		node = node.getSuccessor();
		assertNull(node);
	
	}
@Test
    public void testRemove() {
		assertEquals(9, tree.size());
		tree.remove(5);
		assertEquals(8, tree.size());

		assertEquals(16, treeWithDups.size());
		assertEquals("five",treeWithDups.remove(5));
		assertEquals(15, treeWithDups.size());
		assertEquals("five-a",treeWithDups.remove(5));
		assertEquals(14, treeWithDups.size());
		assertEquals("five-b",treeWithDups.remove(5));
		assertEquals(13, treeWithDups.size());
		assertEquals("five-c",treeWithDups.remove(5));
		assertEquals(12, treeWithDups.size());
		assertNull(treeWithDups.remove(5));
		assertEquals(12, treeWithDups.size());

	}
@Test
    public void testDeleteEntry() {
		RedBlackNode<Integer, String> node = treeWithDups.findFirstNode(5);
		node = node.getSuccessor();
		treeWithDups.deleteEntry(node);
		node = treeWithDups.findFirstNode(5);
		node = node.getSuccessor();
		assertEquals("five-b", node.value);
	}
	
@Test
    public void testDepth() {
		tree = new RedBlackTree<Integer, String>(new SelfComparator<Integer>(), false);
		tree.put(1, "one");
		tree.put(2, "two");
		tree.put(3, "three");
		tree.put(4, "four");
		tree.put(5, "five");
		tree.put(6, "six");
		tree.put(7, "seven");
		tree.put(8, "eight");
		tree.put(9, "nine");
		tree.put(10, "ten");
		
		assertEquals(4, getTreeDepth(tree));

		tree = new RedBlackTree<Integer, String>(new SelfComparator<Integer>(), false);
		tree.put(10, "ten");
		tree.put(9, "nine");
		tree.put(8, "eight");
		tree.put(7, "seven");
		tree.put(6, "six");
		tree.put(5, "five");
		tree.put(4, "four");
		tree.put(3, "three");
		tree.put(2, "two");
		tree.put(1, "one");
		
		assertEquals(4, getTreeDepth(tree));

	}
	
	private int getTreeDepth(RedBlackTree<Integer, String> rbTree) {
		int treeDepth = 0;
		RedBlackNode<Integer, String> node = rbTree.getFirst();
		while(node != null) {
			int nodeDepth = getNodeDepth(node);
			if (nodeDepth > treeDepth) {
				treeDepth = nodeDepth;
			}
			node = node.getSuccessor();
		}
		return treeDepth;
	}
	private int getNodeDepth(RedBlackNode<Integer, String> node) {
		int nodeDepth = 0;
		while (node.parent != null) {
			nodeDepth++;
			node = node.parent;
		}
		return nodeDepth;
	}
}