[Geom4j-developer] SF.net SVN: geom4j:[11] trunk/src/net/sourceforge/geom4j/util

[<skh...@us...>]

Revision: 11
          http://geom4j.svn.sourceforge.net/geom4j/?rev=11&view=rev
Author:   skhenkin
Date:     2009-11-30 21:26:47 +0000 (Mon, 30 Nov 2009)

Log Message:
-----------
SearchTree interface extended. contains(), insert(), first() and last() methods implemented for binary search tree.

Modified Paths:
--------------
    trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.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-11-29 23:06:05 UTC (rev 10)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java	2009-11-30 21:26:47 UTC (rev 11)
@@ -18,16 +18,19 @@
 public class BinarySearchTree<E> implements SearchTree<E> {
     
     /** Tree node element */
-    protected class Node<E> {
+    protected class Node {
         /** Tree node value */
         E value;
         /** Reference to the root node of the left subtree */
         Node left = null;
         /** Reference to the root node of the right subtree */
         Node right = null;
+        /** Reference to the parent node */
+        Node parent = null;
         
-        public Node(E value) {
+        public Node(E value, Node parent) {
             this.value = value;
+            this.parent = parent;
         }
     }
 
@@ -49,23 +52,121 @@
         this.comparator = comparator;
     }
     
-    @Override
+    /** Check if the tree contains element e */  
     public boolean contains(E e) {
-        // TODO Auto-generated method stub
+        Node node = root;
+        while (node != null) {
+            int c = compare(node.value, e);
+            if (c == 0)
+                return true;
+            else if (c < 0)
+                node = node.left;
+            else //  c > 0
+                node = node.right;
+        }
         return false;
     }
 
-    @Override
-    public void insert(E e) {
-        // TODO Auto-generated method stub
-        
+    /** 
+     * Insert element e into the tree 
+     * @return true if element was actually inserted and has not 
+     *         already been present in the tree
+     */
+    public boolean insert(E e) {
+        if (root == null) {
+            root = new Node(e, null);
+            return true;
+        }
+        Node node = root;
+        Node parent;
+        do {
+            parent = node;
+            int c = compare(node.value, e);
+            if (c == 0) {
+                return false;
+            } else if (c < 0) {
+                node = node.left;
+            } else { // c > 0
+                node = node.right;
+            }
+        } while (node != null);
+        if (node == parent.left) {
+            parent.left = new Node(e, parent);
+        } else {
+            parent.right = new Node(e, parent);
+        }
+        return true;
     }
 
-    @Override
+    /** 
+     * Remove element e from the tree.
+     * @return true if element was actually present in the tree before removal
+     */
     public boolean remove(E e) {
-        // TODO Auto-generated method stub
+        Node node = root;
+        if (node == null) {
+            return false;
+        }
+        do { // node != null
+            int c = compare(node.value, e);
+            if (c == 0) {
+                removeNode(node);
+                return true;
+            } 
+            if (c < 0) {
+                node = node.left;
+            } else { // c > 0
+                node = node.right;
+            }
+        } while (node != null);
         return false;
     }
+
+    private void removeNode(Node node) {
+        // TODO: !!!
+        if (node.left == null && node.right == null) {
+            //detachNode(parent, node);
+        } else if (node.left == null){
+            node = node.right;    
+        }
+    }
+
+    @SuppressWarnings("unchecked")
+    private int compare(E e1, E e2) {
+        if (comparator == null)
+            return ((Comparable<? super E>) e1).compareTo(e2);
+        else
+            return comparator.compare(e1, e2);
+    }
+
+    /** Get first element */
+    public E first() {
+        Node node = root;
+        if (root != null)
+            while (node.left != null)
+                node = node.left;
+        return node == null ? null : node.value;
+    }
+
+    /** Get last element */
+    public E last() {
+        Node node = root;
+        if (root != null)
+            while (node.right != null)
+                node = node.right;
+        return node == null ? null : node.value;
+    }
+
+    /** Get next (in-order successor) element for the given element */
+    public E next(E e) {
+        // TODO Auto-generated method stub
+        return null;
+    }
+
+    /** Get previous (in-order predecessor) element for the given element */
+    public E previous(E e) {
+        // TODO Auto-generated method stub
+        return null;
+    }
     
-
 }

Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/SearchTree.java	2009-11-29 23:06:05 UTC (rev 10)
+++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java	2009-11-30 21:26:47 UTC (rev 11)
@@ -8,8 +8,12 @@
  * @author Sergey Khenkin
  */
 public interface SearchTree<E> {
-    /** Insert element e into the tree */
-    void insert(E e);
+    /** 
+     * Insert element e into the tree 
+     * @return true if element was actually inserted and has not 
+     *         already been present in the tree
+     */
+    boolean insert(E e);
     
     /** Check if the tree contains element e */  
     boolean contains(E e);
@@ -19,4 +23,16 @@
      * @return true if element was actually present in the tree before removal
      */
     boolean remove(E e);
+    
+    /** Get first element */
+    E first();
+    
+    /** Get last element */
+    E last();
+    
+    /** Get next (in-order successor) element for the given element */
+    E next(E e);
+    
+    /** Get previous (in-order predecessor) element for the given element */
+    E previous(E e);
 }


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