[Geom4j-developer] SF.net SVN: geom4j:[14] trunk/src/net/sourceforge/geom4j/util
Status: Pre-Alpha
Brought to you by:
skhenkin
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. |