[Geom4j-developer] SF.net SVN: geom4j:[18] trunk/src/net/sourceforge/geom4j/util
Status: Pre-Alpha
Brought to you by:
skhenkin
Menu
▾
▴
[Geom4j-developer] SF.net SVN: geom4j:[18] trunk/src/net/sourceforge/geom4j/util
|
From: <skh...@us...> - 2009-12-10 21:16:17
|
Revision: 18
http://geom4j.svn.sourceforge.net/geom4j/?rev=18&view=rev
Author: skhenkin
Date: 2009-12-10 21:16:10 +0000 (Thu, 10 Dec 2009)
Log Message:
-----------
Preparations for adding AVL tree code.
Modified Paths:
--------------
trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java
trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java
Added Paths:
-----------
trunk/src/net/sourceforge/geom4j/util/AVLTree.java
trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java
trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java
Added: trunk/src/net/sourceforge/geom4j/util/AVLTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/AVLTree.java (rev 0)
+++ trunk/src/net/sourceforge/geom4j/util/AVLTree.java 2009-12-10 21:16:10 UTC (rev 18)
@@ -0,0 +1,91 @@
+/*
+ * Copyright (c) 2009 Sergey Khenkin. All rights reserved.
+ * 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 net.sourceforge.geom4j.util;
+
+import java.util.Comparator;
+
+/**
+ * AVL tree is a kind of self-balancing binary tree.
+ * Stores elements of type E.
+ * Guarantees that all the following operations:
+ * insertion,
+ * removal,
+ * checking if element is in the tree,
+ * getting first or last element
+ * are performed with the complexity of O(log n),
+ * where n is the number of elements in the tree.
+ * This is achieved by keeping the tree balanced (for each node
+ * heights of its left and right subtrees differ at most by 1).
+ *
+ * @param <E> type of values stored in the tree
+ *
+ * @author Sergey Khenkin
+ */
+public class AVLTree<E> extends BinarySearchTree<E> {
+
+ /**
+ * AVL tree node element.
+ * Contains balance factor for each node.
+ */
+ protected class AVLNode extends Node {
+ /**
+ * Each node can have one of the following balance factors
+ *
+ * Left-High (balance factor -1)
+ * The left-sub tree is one level taller than the right-sub tree
+ *
+ * Balanced (balance factor 0)
+ * The left and right sub-trees are both the same heights
+ *
+ * Right-High (balance factor +1)
+ * The right sub-tree is one level taller than the left-sub tree.
+ *
+ * If the balance of a node becomes -2 (it was left high and a level
+ * was lost from the left sub-tree) or +2 (it was right high and a level
+ * was lost from the right sub-tree) it will require re-balancing.
+ * This is achieved by performing a rotation about this node.
+ */
+ public int balanceFactor = 0;
+
+ public AVLNode(E value, Node parent) {
+ super(value, parent);
+ }
+
+ }
+
+ /** Create an empty tree of comparable elements */
+ public AVLTree() {
+ super();
+ }
+
+ /** Create an empty tree with comparator provided */
+ public AVLTree(Comparator<? super E> comparator) {
+ super(comparator);
+ }
+
+ @Override
+ protected Node insertNode(E e, Node parent) {
+ // TODO add code for balancing
+ return super.insertNode(e, parent);
+ }
+
+ @Override
+ protected void removeNode(Node node) {
+ // TODO add code for balancing
+ super.removeNode(node);
+ }
+
+}
Added: trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java (rev 0)
+++ trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java 2009-12-10 21:16:10 UTC (rev 18)
@@ -0,0 +1,48 @@
+/*
+ * Copyright (c) 2009 Sergey Khenkin. All rights reserved.
+ * 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 net.sourceforge.geom4j.util;
+
+import static org.junit.Assert.assertEquals;
+
+import org.junit.Before;
+import org.junit.Test;
+
+public class AVLTreeTest extends BinarySearchTreeTestBase {
+
+ @Before
+ public void setUp() throws Exception {
+ }
+
+ @Override
+ protected SearchTree<Integer> createEmptyBinaryTree() {
+ return new AVLTree<Integer>();
+ }
+
+
+ @Test
+ public void testHeight() {
+ SearchTree<Integer> t = createBinaryTree(
+ new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4});
+ assertEquals(4, t.height());
+
+ t = createBinaryTree(
+ new Integer[] {7, 11, 17, 23, 15, 35});
+ assertEquals(3, t.height());
+
+ t = createEmptyBinaryTree();
+ assertEquals(0, t.height());
+ }
+}
Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-05 21:31:07 UTC (rev 17)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-10 21:16:10 UTC (rev 18)
@@ -116,12 +116,16 @@
}
} while (node != null);
if (c < 0) {
- parent.left = new Node(e, parent);
+ parent.left = insertNode(e, parent);
} else {
- parent.right = new Node(e, parent);
+ parent.right = insertNode(e, parent);
}
return true;
}
+
+ protected Node insertNode(E e, Node parent) {
+ return new Node(e, parent);
+ }
/**
* Remove element e from the tree.
Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java 2009-12-05 21:31:07 UTC (rev 17)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java 2009-12-10 21:16:10 UTC (rev 18)
@@ -1,140 +1,47 @@
+/*
+ * Copyright (c) 2009 Sergey Khenkin. All rights reserved.
+ * 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 net.sourceforge.geom4j.util;
-import static org.junit.Assert.*;
+import static org.junit.Assert.assertEquals;
-import java.util.Arrays;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.LinkedList;
-import java.util.List;
-import java.util.Random;
-import java.util.Set;
-
import org.junit.Before;
import org.junit.Test;
-public class BinarySearchTreeTest {
+public class BinarySearchTreeTest extends BinarySearchTreeTestBase {
@Before
public void setUp() throws Exception {
}
- @Test
- public void testSmallTree() {
- SearchTree<Integer> t = createBinaryTree(
- new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4});
- assertEquals(3, t.first());
- assertEquals(17, t.last());
- assertEquals(7, t.next(6));
- assertEquals(10, t.previous(11));
- assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 7, 9, 10, 11, 17},
- t.toList()));
- assertTrue(t.contains(7));
- t.remove(7);
- assertFalse(t.contains(7));
- assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 9, 10, 11, 17},
- t.toList()));
- assertTrue(t.contains(9));
- t.remove(9);
- assertFalse(t.contains(9));
- assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 10, 11, 17},
- t.toList()));
- assertTrue(t.contains(5));
- t.remove(5);
- assertFalse(t.contains(5));
- assertTrue(listsEqual(new Integer[] {3, 4, 6, 10, 11, 17},
- t.toList()));
- assertTrue(t.contains(17));
- t.remove(17);
- assertFalse(t.contains(17));
- assertTrue(listsEqual(new Integer[] {3, 4, 6, 10, 11},
- t.toList()));
+ @Override
+ protected SearchTree<Integer> createEmptyBinaryTree() {
+ return new BinarySearchTree<Integer>();
}
-
+
@Test
- public void testRandomTree() {
- Integer[] values = createRandomUniqueArray(3000, 10000);
- SearchTree<Integer> t = createBinaryTree(values);
- Arrays.sort(values);
- assertTrue(listsEqual(values, t.toList()));
- assertEquals(values.length, t.size());
- }
-
- @Test
- public void testSizeAndHeight() {
+ public void testHeight() {
SearchTree<Integer> t = createBinaryTree(
new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4});
- assertEquals(9, t.size());
assertEquals(4, t.height());
- t = new BinarySearchTree<Integer>();
- assertEquals(0, t.size());
+ t = createBinaryTree(
+ new Integer[] {7, 11, 17, 23, 15, 35});
+ assertEquals(5, t.height());
+
+ t = createEmptyBinaryTree();
assertEquals(0, t.height());
}
-
- @Test
- public void testIterator() {
- Integer[] values = new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4};
- SearchTree<Integer> t = createBinaryTree(values);
- Arrays.sort(values);
- List<Integer> treeValues = new LinkedList<Integer>();
- for (Integer i: t) {
- treeValues.add(i);
- }
- assertTrue(Arrays.equals(values, treeValues.toArray()));
- }
-
- @Test
- public void testIteratorRemoval() {
- Integer[] values = new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4};
- SearchTree<Integer> t = createBinaryTree(values);
- Arrays.sort(values);
- List<Integer> treeValues = new LinkedList<Integer>();
- Iterator<Integer> i = t.iterator();
- while (i.hasNext()) {
- Integer v = i.next();
- treeValues.add(v);
- i.remove();
- }
- assertTrue(Arrays.equals(values, treeValues.toArray()));
- }
-
-
- private boolean listsEqual(Integer[] values, List<Integer> list) {
- if (values.length != list.size())
- return false;
- int i = 0;
- for (Integer v: list) {
- if (!v.equals(values[i++]))
- return false;
- }
- return true;
- }
-
- private Integer[] createRandomUniqueArray(int size, int maxValue) {
- Random r = new Random();
- Set<Integer> used = new HashSet<Integer>();
- Integer[] values = new Integer[size];
- for (int i = 0; i < size; i++) {
- Integer v;
- do {
- v = r.nextInt(maxValue);
- } while (used.contains(v));
- values[i] = v;
- used.add(v);
- }
- return values;
- }
-
- private SearchTree<Integer> createBinaryTree(Integer[] values) {
- SearchTree<Integer> tree = new BinarySearchTree<Integer>();
- populateTree(tree, values);
- return tree;
- }
-
- private void populateTree(SearchTree<Integer> tree, Integer[] values) {
- for (int i: values) {
- tree.insert(i);
- }
- }
}
Added: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java (rev 0)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java 2009-12-10 21:16:10 UTC (rev 18)
@@ -0,0 +1,166 @@
+/*
+ * Copyright (c) 2009 Sergey Khenkin. All rights reserved.
+ * 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 net.sourceforge.geom4j.util;
+
+import static org.junit.Assert.*;
+
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Basic class for testing binary search tree functionality.
+ * All implementation-specific details should be tested in
+ * subclasses.
+ *
+ * @author Sergey Khenkin
+ */
+public abstract class BinarySearchTreeTestBase {
+
+ @Before
+ public void setUp() throws Exception {
+ }
+
+ @Test
+ public void testSmallTree() {
+ SearchTree<Integer> t = createBinaryTree(
+ new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4});
+ assertEquals(3, t.first());
+ assertEquals(17, t.last());
+ assertEquals(7, t.next(6));
+ assertEquals(10, t.previous(11));
+ assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 7, 9, 10, 11, 17},
+ t.toList()));
+ assertTrue(t.contains(7));
+ t.remove(7);
+ assertFalse(t.contains(7));
+ assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 9, 10, 11, 17},
+ t.toList()));
+ assertTrue(t.contains(9));
+ t.remove(9);
+ assertFalse(t.contains(9));
+ assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 10, 11, 17},
+ t.toList()));
+ assertTrue(t.contains(5));
+ t.remove(5);
+ assertFalse(t.contains(5));
+ assertTrue(listsEqual(new Integer[] {3, 4, 6, 10, 11, 17},
+ t.toList()));
+ assertTrue(t.contains(17));
+ t.remove(17);
+ assertFalse(t.contains(17));
+ assertTrue(listsEqual(new Integer[] {3, 4, 6, 10, 11},
+ t.toList()));
+ }
+
+ @Test
+ public void testRandomTree() {
+ Integer[] values = createRandomUniqueArray(3000, 10000);
+ SearchTree<Integer> t = createBinaryTree(values);
+ Arrays.sort(values);
+ assertTrue(listsEqual(values, t.toList()));
+ assertEquals(values.length, t.size());
+ }
+
+ @Test
+ public void testSize() {
+ SearchTree<Integer> t = createBinaryTree(
+ new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4});
+ assertEquals(9, t.size());
+
+ t = createEmptyBinaryTree();
+ assertEquals(0, t.size());
+ }
+
+ @Test
+ public void testIterator() {
+ Integer[] values = new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4};
+ SearchTree<Integer> t = createBinaryTree(values);
+ Arrays.sort(values);
+ List<Integer> treeValues = new LinkedList<Integer>();
+ for (Integer i: t) {
+ treeValues.add(i);
+ }
+ assertTrue(Arrays.equals(values, treeValues.toArray()));
+ }
+
+ @Test
+ public void testIteratorRemoval() {
+ Integer[] values = new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4};
+ SearchTree<Integer> t = createBinaryTree(values);
+ Arrays.sort(values);
+ List<Integer> treeValues = new LinkedList<Integer>();
+ Iterator<Integer> i = t.iterator();
+ while (i.hasNext()) {
+ Integer v = i.next();
+ treeValues.add(v);
+ i.remove();
+ }
+ assertTrue(Arrays.equals(values, treeValues.toArray()));
+ }
+
+
+ private boolean listsEqual(Integer[] values, List<Integer> list) {
+ if (values.length != list.size())
+ return false;
+ int i = 0;
+ for (Integer v: list) {
+ if (!v.equals(values[i++]))
+ return false;
+ }
+ return true;
+ }
+
+ private Integer[] createRandomUniqueArray(int size, int maxValue) {
+ Random r = new Random();
+ Set<Integer> used = new HashSet<Integer>();
+ Integer[] values = new Integer[size];
+ for (int i = 0; i < size; i++) {
+ Integer v;
+ do {
+ v = r.nextInt(maxValue);
+ } while (used.contains(v));
+ values[i] = v;
+ used.add(v);
+ }
+ return values;
+ }
+
+ protected SearchTree<Integer> createBinaryTree(Integer[] values) {
+ SearchTree<Integer> tree = createEmptyBinaryTree();
+ populateTree(tree, values);
+ return tree;
+ }
+
+ /**
+ * This method should be overridden in each subclass so that
+ * it creates and returns a tree of that subclass.
+ */
+ protected abstract SearchTree<Integer> createEmptyBinaryTree();
+
+ private void populateTree(SearchTree<Integer> tree, Integer[] values) {
+ for (int i: values) {
+ tree.insert(i);
+ }
+ }
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
