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

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

Revision: 20
          http://geom4j.svn.sourceforge.net/geom4j/?rev=20&view=rev
Author:   skhenkin
Date:     2009-12-14 23:44:34 +0000 (Mon, 14 Dec 2009)

Log Message:
-----------
BinaryTreeBasedSmartQueue switched to AVLTree instead of a simple BinarySearchTree

Modified Paths:
--------------
    trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java
    trunk/src/net/sourceforge/geom4j/util/AVLTree.java
    trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java

Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java	2009-12-14 22:57:47 UTC (rev 19)
+++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java	2009-12-14 23:44:34 UTC (rev 20)
@@ -97,7 +97,7 @@
         double X1 = 0, X2 = 1000, Y1 = 0, Y2 = 1000;
         SegmentSet ss = new SegmentSet();
         Random r = new Random();
-        for (int i = 0; i < 100; i++) {
+        for (int i = 0; i < 300; i++) {
             double x1 = r.nextDouble()*(X2-X1)+X1;
             double y1 = r.nextDouble()*(Y2-Y1)+Y1;
             double x2 = r.nextDouble()*(X2-X1)+X1;

Modified: trunk/src/net/sourceforge/geom4j/util/AVLTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/AVLTree.java	2009-12-14 22:57:47 UTC (rev 19)
+++ trunk/src/net/sourceforge/geom4j/util/AVLTree.java	2009-12-14 23:44:34 UTC (rev 20)
@@ -28,7 +28,11 @@
  * are performed with the complexity of O(log n),
  * where n is the number of elements in the tree.
  * This is achieved by keeping the tree balanced (for each node
- * heights of its left and right subtrees differ at most by 1).   
+ * heights of its left and right subtrees differ at most by 1).
+ * This balance is restored when needed using tree transformations
+ * called "rotations".
+ * See http://sky.fit.qut.edu.au/~maire/avl/System/AVLTree.html for more
+ * information and nice graphical explanation of rotations.    
  * 
  * @param <E> type of values stored in the tree
  * 

Modified: trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java	2009-12-14 22:57:47 UTC (rev 19)
+++ trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java	2009-12-14 23:44:34 UTC (rev 20)
@@ -18,11 +18,9 @@
 import java.util.Comparator;
 
 /**
- * "Smarter" implementation of SmartQueue based on a binary search tree.
- * It takes on average O(log n) time to insert/remove/swap 
- * or get prev/next elements.
- * There's still a room for performance improvements using some kind
- * of self-balancing trees (like AVL-trees or Red-Black trees).
+ * "Smarter" implementation of SmartQueue based on a self-balancing
+ * binary search tree (AVL tree).
+ * It takes O(log n) time to insert/remove/swap or get prev/next elements.
  * 
  * Actually this is a binary search tree with two added operations: 
  * poll() - for extracting the first tree element;
@@ -30,7 +28,7 @@
  * 
  * @author Sergey Khenkin
  */
-public class BinaryTreeBasedSmartQueue<E> extends BinarySearchTree<E> 
+public class BinaryTreeBasedSmartQueue<E> extends AVLTree<E> 
                                           implements SmartQueue<E> {
     
     public BinaryTreeBasedSmartQueue() {


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