Thread: [Geom4j-developer] SF.net SVN: geom4j:[13] trunk/src/net/sourceforge/geom4j

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Revision: 13
          http://geom4j.svn.sourceforge.net/geom4j/?rev=13&view=rev
Author:   skhenkin
Date:     2009-12-01 23:05:11 +0000 (Tue, 01 Dec 2009)

Log Message:
-----------
Binary search tree implemented. Tests for it added.

Modified Paths:
--------------
    trunk/src/net/sourceforge/geom4j/Vector.java
    trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java
    trunk/src/net/sourceforge/geom4j/util/SearchTree.java

Added Paths:
-----------
    trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java

Modified: trunk/src/net/sourceforge/geom4j/Vector.java
===================================================================

--- trunk/src/net/sourceforge/geom4j/Vector.java	2009-11-30 23:05:54 UTC (rev 12)
+++ trunk/src/net/sourceforge/geom4j/Vector.java	2009-12-01 23:05:11 UTC (rev 13)
@@ -15,7 +15,6 @@
 
 package net.sourceforge.geom4j;
 
-import java.util.Iterator;
 
 /**
  * A vector on a plane.

Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java	2009-11-30 23:05:54 UTC (rev 12)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java	2009-12-01 23:05:11 UTC (rev 13)
@@ -16,6 +16,8 @@
 package net.sourceforge.geom4j.util;
 
 import java.util.Comparator;
+import java.util.LinkedList;
+import java.util.List;
 
 /**
  * Binary search tree.
@@ -76,7 +78,7 @@
     protected Node findNode(E e) {
         Node node = root;
         while (node != null) {
-            int c = compare(node.value, e);
+            int c = compare(e, node.value);
             if (c == 0)
                 return node;
             else if (c < 0)
@@ -99,9 +101,10 @@
         }
         Node node = root;
         Node parent;
+        int c;
         do {
             parent = node;
-            int c = compare(node.value, e);
+            c = compare(e, node.value);
             if (c == 0) {
                 return false;
             } else if (c < 0) {
@@ -110,7 +113,7 @@
                 node = node.right;
             }
         } while (node != null);
-        if (node == parent.left) {
+        if (c < 0) {
             parent.left = new Node(e, parent);
         } else {
             parent.right = new Node(e, parent);
@@ -128,7 +131,7 @@
             return false;
         }
         do { // node != null
-            int c = compare(node.value, e);
+            int c = compare(e, node.value);
             if (c == 0) {
                 removeNode(node);
                 return true;
@@ -143,14 +146,50 @@
     }
 
     private void removeNode(Node node) {
-        // TODO: !!!
-        if (node.left == null && node.right == null) {
-            //detachNode(parent, node);
-        } else if (node.left == null){
-            node = node.right;    
+        if (node.left == null && node.right == null) { // remove node
+            updateNodeReferences(node, null);
+        } else if (node.left == null){ // replace node with its single right child
+            updateNodeReferences(node, node.right);
+        } else if (node.right == null){ // replace node with its single left child
+            updateNodeReferences(node, node.left);
+        } else {
+            /* We can either replace the node with the biggest element of its 
+             * left subtree or with the smallest element of its right subtree.
+             * We randomize the selection of this element to prevent tree
+             * degeneration into list
+             */
+            boolean pseudoRandomChoice = (node.hashCode() % 2 == 0);
+            if (pseudoRandomChoice) { 
+                // replace node value with its in-order predecessor's value
+                Node predecessor = previous(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.value = successor.value;
+                // remove successor (it can have at most one child)
+                removeNode(successor);
+            }
         }
     }
 
+    private void updateNodeReferences(Node node, Node replacement) {
+        if (node.parent == null) { // node == root
+            root = replacement;
+        } else {
+            if (node.parent.left == node) { 
+                node.parent.left = replacement;
+            } else {
+                node.parent.right = replacement;
+            }
+        }
+        if (replacement != null) {
+            replacement.parent = node.parent;
+        }
+    }
+
     @SuppressWarnings("unchecked")
     private int compare(E e1, E e2) {
         if (comparator == null)
@@ -225,6 +264,29 @@
         return parent;
     }
 
-    // TODO: create unit test; one of the ideas: build random tree, 
-    //       traverse its elements with next() and compare with the sorted set
+    /** Get ordered list of all tree elements */
+    public List<E> toList() {
+        List<E> list = new LinkedList<E>();
+        Node n = first(root);
+        while (n != null) {
+            list.add(n.value);
+            n = next(n);
+        }
+        return list;
+    }
+    
+    @Override
+    public String toString() {
+        return toString(root);
+    }
+    
+    public String toString(Node node) {
+        if (node == null)
+            return "*";
+        return new StringBuilder("[").append(node.value).append(" ")
+            .append(toString(node.left)).append(" ").append(toString(node.right))
+            .append("]").toString();
+    }
+    
+    // TODO: add iterator
 }

Added: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java	                        (rev 0)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java	2009-12-01 23:05:11 UTC (rev 13)
@@ -0,0 +1,100 @@
+package net.sourceforge.geom4j.util;
+
+import static org.junit.Assert.*;
+
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+import org.junit.Before;
+import org.junit.Test;
+
+public class BinarySearchTreeTest {
+
+    @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(300, 1000);
+        SearchTree<Integer> t = createBinaryTree(values);
+        Arrays.sort(values);
+        assertTrue(listsEqual(values, t.toList()));
+    }
+ 
+    // TODO: test removal
+    
+    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);
+        }
+    }
+
+}

Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/SearchTree.java	2009-11-30 23:05:54 UTC (rev 12)
+++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java	2009-12-01 23:05:11 UTC (rev 13)
@@ -15,6 +15,8 @@
 
 package net.sourceforge.geom4j.util;
 
+import java.util.List;
+
 /**
  * General purpose search tree.
  * Supports operations of inserting, searching and removing for
@@ -50,4 +52,7 @@
     
     /** Get previous (in-order predecessor) element for the given element */
     E previous(E e);
+
+    /** Get ordered list of all tree elements */
+    List<E> toList();
 }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.




Thread: [Geom4j-developer] SF.net SVN: geom4j:[13] trunk/src/net/sourceforge/geom4j

geom4j-developer