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

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

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

Log Message:
-----------
next() and previous() implementations added to BinarySearchTree

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

Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java	2009-11-30 21:26:47 UTC (rev 11)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java	2009-11-30 23:05:54 UTC (rev 12)
@@ -1,3 +1,18 @@
+/*
+ * 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;
@@ -54,19 +69,24 @@
     
     /** Check if the tree contains element e */  
     public boolean contains(E e) {
+        return findNode(e) != null;
+    }
+
+    /** Find element node in the tree */
+    protected Node findNode(E e) {
         Node node = root;
         while (node != null) {
             int c = compare(node.value, e);
             if (c == 0)
-                return true;
+                return node;
             else if (c < 0)
                 node = node.left;
             else //  c > 0
                 node = node.right;
         }
-        return false;
+        return node;
     }
-
+    
     /** 
      * Insert element e into the tree 
      * @return true if element was actually inserted and has not 
@@ -141,32 +161,70 @@
 
     /** Get first element */
     public E first() {
-        Node node = root;
-        if (root != null)
+        Node firstNode = first(root);
+        return firstNode != null ? firstNode.value : null;
+    }
+
+    protected Node first(Node node) {
+        if (node != null)
             while (node.left != null)
                 node = node.left;
-        return node == null ? null : node.value;
+        return node;
     }
 
     /** Get last element */
     public E last() {
-        Node node = root;
-        if (root != null)
+        Node lastNode = last(root);
+        return lastNode != null ? lastNode.value : null;
+    }
+
+    public Node last(Node node) {
+        if (node != null)
             while (node.right != null)
                 node = node.right;
-        return node == null ? null : node.value;
+        return node;
     }
 
     /** Get next (in-order successor) element for the given element */
     public E next(E e) {
-        // TODO Auto-generated method stub
-        return null;
+        Node node = findNode(e);
+        Node nextNode = next(node);
+        return nextNode != null ? nextNode.value : null;
     }
+    
+    protected Node next(Node node) {
+        if (node == null) return null;
+        if (node.right != null) {
+            return first(node.right);
+        }
+        Node parent = node.parent;
+        while (parent != null && parent.right == node) {
+            node = parent;
+            parent = parent.parent;
+        }
+        return parent;
+    }
 
     /** Get previous (in-order predecessor) element for the given element */
     public E previous(E e) {
-        // TODO Auto-generated method stub
-        return null;
+        Node node = findNode(e);
+        Node prevNode = previous(node);
+        return prevNode != null ? prevNode.value : null;
     }
     
+    protected Node previous(Node node) {
+        if (node == null) return null;
+        if (node.left != null) {
+            return last(node.left);
+        }
+        Node parent = node.parent;
+        while (parent != null && parent.left == node) {
+            node = parent;
+            parent = parent.parent;
+        }
+        return parent;
+    }
+
+    // TODO: create unit test; one of the ideas: build random tree, 
+    //       traverse its elements with next() and compare with the sorted set
 }

Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/SearchTree.java	2009-11-30 21:26:47 UTC (rev 11)
+++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java	2009-11-30 23:05:54 UTC (rev 12)
@@ -1,3 +1,18 @@
+/*
+ * 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;
 
 /**

Modified: trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java	2009-11-30 21:26:47 UTC (rev 11)
+++ trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java	2009-11-30 23:05:54 UTC (rev 12)
@@ -1,3 +1,18 @@
+/*
+ * 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.*;


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