[Geom4j-developer] SF.net SVN: geom4j:[14] trunk/src/net/sourceforge/geom4j/util
Status: Pre-Alpha
Brought to you by:
skhenkin
Menu
▾
▴
[Geom4j-developer] SF.net SVN: geom4j:[14] trunk/src/net/sourceforge/geom4j/util
|
From: <skh...@us...> - 2009-12-02 20:28:14
|
Revision: 14
http://geom4j.svn.sourceforge.net/geom4j/?rev=14&view=rev
Author: skhenkin
Date: 2009-12-02 20:28:03 +0000 (Wed, 02 Dec 2009)
Log Message:
-----------
Binary search tree updated. Added methods for tree height and size calculation. Tree made iterable.
Modified Paths:
--------------
trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java
trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java
trunk/src/net/sourceforge/geom4j/util/SearchTree.java
Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-01 23:05:11 UTC (rev 13)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-02 20:28:03 UTC (rev 14)
@@ -16,8 +16,10 @@
package net.sourceforge.geom4j.util;
import java.util.Comparator;
+import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
+import java.util.NoSuchElementException;
/**
* Binary search tree.
@@ -161,13 +163,13 @@
boolean pseudoRandomChoice = (node.hashCode() % 2 == 0);
if (pseudoRandomChoice) {
// replace node value with its in-order predecessor's value
- Node predecessor = previous(node);
+ Node predecessor = previousNode(node);
node.value = predecessor.value;
// remove predecessor (it can have at most one child)
removeNode(predecessor);
} else {
// replace node value with its in-order successor's value
- Node successor = next(node);
+ Node successor = nextNode(node);
node.value = successor.value;
// remove successor (it can have at most one child)
removeNode(successor);
@@ -200,11 +202,11 @@
/** Get first element */
public E first() {
- Node firstNode = first(root);
+ Node firstNode = firstNode(root);
return firstNode != null ? firstNode.value : null;
}
- protected Node first(Node node) {
+ protected Node firstNode(Node node) {
if (node != null)
while (node.left != null)
node = node.left;
@@ -213,11 +215,11 @@
/** Get last element */
public E last() {
- Node lastNode = last(root);
+ Node lastNode = lastNode(root);
return lastNode != null ? lastNode.value : null;
}
- public Node last(Node node) {
+ public Node lastNode(Node node) {
if (node != null)
while (node.right != null)
node = node.right;
@@ -227,14 +229,14 @@
/** Get next (in-order successor) element for the given element */
public E next(E e) {
Node node = findNode(e);
- Node nextNode = next(node);
+ Node nextNode = nextNode(node);
return nextNode != null ? nextNode.value : null;
}
- protected Node next(Node node) {
+ protected Node nextNode(Node node) {
if (node == null) return null;
if (node.right != null) {
- return first(node.right);
+ return firstNode(node.right);
}
Node parent = node.parent;
while (parent != null && parent.right == node) {
@@ -247,14 +249,14 @@
/** Get previous (in-order predecessor) element for the given element */
public E previous(E e) {
Node node = findNode(e);
- Node prevNode = previous(node);
+ Node prevNode = previousNode(node);
return prevNode != null ? prevNode.value : null;
}
- protected Node previous(Node node) {
+ protected Node previousNode(Node node) {
if (node == null) return null;
if (node.left != null) {
- return last(node.left);
+ return lastNode(node.left);
}
Node parent = node.parent;
while (parent != null && parent.left == node) {
@@ -267,10 +269,10 @@
/** Get ordered list of all tree elements */
public List<E> toList() {
List<E> list = new LinkedList<E>();
- Node n = first(root);
+ Node n = firstNode(root);
while (n != null) {
list.add(n.value);
- n = next(n);
+ n = nextNode(n);
}
return list;
}
@@ -288,5 +290,78 @@
.append("]").toString();
}
- // TODO: add iterator
+ /** Get tree height (max number of nodes on the path from root to leaf) */
+ @Override
+ public int height() {
+ return heightNode(root);
+ }
+
+ protected int heightNode(Node node) {
+ if (node == null) {
+ return 0;
+ } else {
+ return 1 + Math.max(heightNode(node.left), heightNode(node.right));
+ }
+ }
+
+ /** Get the number of elements in the tree */
+ @Override
+ public int size() {
+ return sizeNode(root);
+ }
+
+ protected int sizeNode(Node node) {
+ if (node == null) {
+ return 0;
+ } else {
+ return 1 + sizeNode(node.left) + sizeNode(node.right);
+ }
+ }
+
+ /** Return iterator for the tree elements */
+ @Override
+ public Iterator<E> iterator() {
+ return new BinarySearchTreeIterator(firstNode(root));
+ }
+
+ /** Iterator object for the binary search tree */
+ public class BinarySearchTreeIterator implements Iterator<E> {
+ private Node node;
+ private Node lastAccessed = null;
+
+ public BinarySearchTreeIterator(Node node) {
+ this.node = node;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return node != null;
+ }
+
+ @Override
+ public E next() {
+ if (node == null) {
+ throw new NoSuchElementException();
+ }
+ lastAccessed = node;
+ node = nextNode(node);
+ return lastAccessed.value;
+ }
+
+ @Override
+ public void remove() {
+ if (lastAccessed == null) {
+ throw new IllegalStateException();
+ }
+ E nextValue = (node != null ? node.value : null);
+ removeNode(lastAccessed);
+ if (lastAccessed != null && node != null
+ && compare(nextValue, lastAccessed.value) == 0) {
+ // check if the removed element is replaced by the current one
+ node = lastAccessed;
+ }
+ lastAccessed = null;
+ }
+
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java 2009-12-01 23:05:11 UTC (rev 13)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java 2009-12-02 20:28:03 UTC (rev 14)
@@ -4,6 +4,8 @@
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;
@@ -51,14 +53,53 @@
@Test
public void testRandomTree() {
- Integer[] values = createRandomUniqueArray(300, 1000);
+ Integer[] values = createRandomUniqueArray(3000, 10000);
SearchTree<Integer> t = createBinaryTree(values);
Arrays.sort(values);
assertTrue(listsEqual(values, t.toList()));
+ assertEquals(values.length, t.size());
}
- // TODO: test removal
+ @Test
+ public void testSizeAndHeight() {
+ 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());
+ 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;
@@ -96,5 +137,4 @@
tree.insert(i);
}
}
-
}
Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-01 23:05:11 UTC (rev 13)
+++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-02 20:28:03 UTC (rev 14)
@@ -21,12 +21,16 @@
* General purpose search tree.
* Supports operations of inserting, searching and removing for
* the elements of type E.
+ * Duplicate elements are discarded during insertion.
+ * Tree stores only unique elements.
*
* @author Sergey Khenkin
*/
-public interface SearchTree<E> {
+public interface SearchTree<E> extends Iterable<E> {
/**
- * Insert element e into the tree
+ * Insert element e into the tree.
+ * If the tree already contains an equal element
+ * the new one does not get inserted.
* @return true if element was actually inserted and has not
* already been present in the tree
*/
@@ -55,4 +59,10 @@
/** Get ordered list of all tree elements */
List<E> toList();
+
+ /** Get tree height (max number of nodes on the path from root to leaf) */
+ int height();
+
+ /** Get the number of elements in the tree */
+ int size();
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
