[Geom4j-developer] SF.net SVN: geom4j:[12] trunk/src/net/sourceforge/geom4j/util
Status: Pre-Alpha
Brought to you by:
skhenkin
Menu
▾
▴
[Geom4j-developer] SF.net SVN: geom4j:[12] trunk/src/net/sourceforge/geom4j/util
|
From: <skh...@us...> - 2009-11-30 23:06:01
|
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.
|