directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r633937 - in /directory/sandbox/akarasulu/bigbang/apacheds: core-avl/src/main/java/org/apache/directory/server/core/avltree/ core-avl/src/test/java/org/apache/directory/server/core/avltree/ core-cursor/src/main/java/org/apache/directory/ser...
Date Wed, 05 Mar 2008 17:18:28 GMT
Author: akarasulu
Date: Wed Mar  5 09:18:26 2008
New Revision: 633937

URL: http://svn.apache.org/viewvc?rev=633937&view=rev
Log:
Cursor implementation around an AvlTree

Added:
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeCursor.java
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java
Modified:
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
    directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
    directory/sandbox/akarasulu/bigbang/apacheds/core-cursor/src/main/java/org/apache/directory/server/core/cursor/Cursor.java

Modified: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java?rev=633937&r1=633936&r2=633937&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
Wed Mar  5 09:18:26 2008
@@ -24,8 +24,6 @@
 import java.util.Comparator;
 import java.util.List;
 
-import org.apache.commons.lang.NotImplementedException;
-
 
 /**
  * An AVL tree implementation
@@ -59,6 +57,12 @@
 	}
 	
 	
+	public Comparator<K> getComparator()
+	{
+	    return comparator;
+	}
+	
+	
 	/**
 	 * Inserts a LinkedAvlNode with the given key
 	 *
@@ -373,20 +377,25 @@
     //NOTE: This method is internally used by AVLTreeMarshaller
     public int getSize()
     {
-      if( root.isLeaf() )
-      {
-          return 1;
-      }
+        if ( root == null )
+        {
+            return 0;
+        }
+        
+        if( root.isLeaf() )
+        {
+            return 1;
+        }
       
-      LinkedAvlNode<K> x = first.next;
+        LinkedAvlNode<K> x = first.next;
       
-      while( x != null )
-      {
-        x.setIndex( x.previous.getIndex() + 1 );  
-        x = x.next;
-      }
+        while( x != null )
+        {
+            x.setIndex( x.previous.getIndex() + 1 );  
+            x = x.next;
+        }
       
-      return last.getIndex() + 1;
+        return last.getIndex() + 1;
     }
     
     

Added: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeCursor.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeCursor.java?rev=633937&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeCursor.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeCursor.java
Wed Mar  5 09:18:26 2008
@@ -0,0 +1,223 @@
+/*
+ *   Licensed to the Apache Software Foundation (ASF) under one
+ *   or more contributor license agreements.  See the NOTICE file
+ *   distributed with this work for additional information
+ *   regarding copyright ownership.  The ASF licenses this file
+ *   to you 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 org.apache.directory.server.core.avltree;
+
+
+import org.apache.directory.server.core.cursor.AbstractCursor;
+import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
+
+
+/**
+ * A Cursor for an AvlTree.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AvlTreeCursor<K> extends AbstractCursor<K>
+{
+    private AvlTree<K> tree;
+    private LinkedAvlNode<K> node;
+    private boolean onNode = false;
+    private boolean isAfterLast = false;
+    private boolean isBeforeFirst = true;
+ 
+    
+    public AvlTreeCursor( AvlTree<K> tree )
+    {
+        this.tree = tree;
+    }
+
+    
+    public void after( K element ) throws Exception 
+    {
+        checkClosed( "after" );
+        LinkedAvlNode<K> found = tree.findGreater( element );
+        
+        if ( found == null )
+        {
+            node = tree.getLast();
+            onNode = false;
+            isAfterLast = true;
+            isBeforeFirst = false;
+            return;
+        }
+
+        node = found;
+        isAfterLast = false;
+        isBeforeFirst = false;
+        onNode = false;
+    }
+
+
+    public void afterLast() throws Exception 
+    {
+        checkClosed( "afterLast" );
+        node = tree.getLast();
+        isBeforeFirst = false;
+        isAfterLast = true;
+        onNode = false;
+    }
+
+
+    public boolean available()
+    {
+        return onNode;
+    }
+
+
+    public void before( K element ) throws Exception 
+    {
+        checkClosed( "before" );
+        LinkedAvlNode<K> found = tree.findLess( element );
+        if ( found == null )
+        {
+            node = tree.getFirst();
+            isAfterLast = false;
+            isBeforeFirst = true;
+        }
+        else
+        {
+            node = found.next;
+            isAfterLast = false;
+            isBeforeFirst = false;
+        }
+        onNode = false;
+    }
+
+
+    public void beforeFirst() throws Exception 
+    {
+        checkClosed( "beforeFirst" );
+        node = tree.getFirst();
+        isBeforeFirst = true;
+        isAfterLast = false;
+        onNode = false;
+    }
+
+
+    public boolean first() throws Exception 
+    {
+        checkClosed( "first" );
+        node = tree.getFirst();
+        isBeforeFirst = false;
+        isAfterLast = false;
+        return onNode = node != null;
+    }
+
+
+    public K get() throws Exception 
+    {
+        checkClosed( "get" );
+        if ( onNode )
+        {
+            return node.getKey();
+        }
+        
+        throw new InvalidCursorPositionException();
+    }
+
+
+    public boolean isElementReused()
+    {
+        return true;
+    }
+
+
+    public boolean last() throws Exception 
+    {
+        checkClosed( "last" );
+        node = tree.getLast();
+        isBeforeFirst = false;
+        isAfterLast = false;
+        return onNode = node != null;
+    }
+
+
+    public boolean next() throws Exception 
+    {
+        checkClosed( "next" );
+        
+        if ( isBeforeFirst )
+        {
+            onNode = true;
+            isBeforeFirst = false;
+            isAfterLast = false;
+            return true;
+        }
+
+        if ( isAfterLast )
+        {
+            return false;
+        }
+        else if ( onNode )
+        {
+            if ( node.next == null )
+            {
+                onNode = false;
+                isAfterLast = true;
+                isBeforeFirst = false;
+                return false;
+            }
+            
+            node = node.next;
+            return true;
+        }
+
+        if ( node != null )
+        {
+            return onNode = true;
+        }
+        
+        return false;
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        checkClosed( "previous" );
+        if ( isAfterLast )
+        {
+            onNode = true;
+            isBeforeFirst = false;
+            isAfterLast = false;
+            return true;
+        }
+        
+        if ( isBeforeFirst )
+        {
+            return false;
+        }
+        else if ( onNode )
+        {
+            if ( node.previous == null )
+            {
+                onNode = false;
+                isAfterLast = false;
+                isBeforeFirst = true;
+                return false;
+            }
+            
+            node = node.previous;
+            return true;
+        }
+        
+        return false;
+    }
+}

Added: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java?rev=633937&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeCursorTest.java
Wed Mar  5 09:18:26 2008
@@ -0,0 +1,245 @@
+/*
+ *   Licensed to the Apache Software Foundation (ASF) under one
+ *   or more contributor license agreements.  See the NOTICE file
+ *   distributed with this work for additional information
+ *   regarding copyright ownership.  The ASF licenses this file
+ *   to you 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 org.apache.directory.server.core.avltree;
+
+
+import static org.junit.Assert.*;
+
+import java.util.Comparator;
+
+import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
+import org.junit.Test;
+
+
+/**
+ * Tests the AvlTreeCursor class.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AvlTreeCursorTest
+{
+    @Test
+    public void testEmptyCursor() throws Exception
+    {
+        AvlTree<Integer> tree = new AvlTree<Integer>( new IntegerComparator()
);
+        AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( tree );
+        
+        assertFalse( cursor.isClosed() );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.isElementReused() );
+        
+        try
+        {
+            cursor.get();
+            fail( "Should not get here" );
+        }
+        catch ( InvalidCursorPositionException e )
+        {
+            assertNotNull( e );
+        }
+        
+        cursor.beforeFirst();
+        assertFalse( cursor.available() );
+        
+        cursor.afterLast();
+        assertFalse( cursor.available() );
+        
+        assertFalse( cursor.first() );
+        assertFalse( cursor.available() );
+        
+        assertFalse( cursor.last() );
+        assertFalse( cursor.available() );
+        
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+        
+        assertFalse( cursor.previous() );
+        assertFalse( cursor.available() );
+
+        cursor.before( 3 );
+        assertFalse( cursor.available() );
+        
+        cursor.after( 3 );
+        assertFalse( cursor.available() );
+        
+        cursor.close();
+        assertTrue( cursor.isClosed() );
+    }
+    
+    
+    @Test
+    public void testOneEntryCursor() throws Exception
+    {
+        AvlTree<Integer> tree = new AvlTree<Integer>( new IntegerComparator()
);
+        tree.insert( 7 );
+        AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( tree );
+        
+        assertFalse( cursor.isClosed() );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.isElementReused() );
+        
+        try
+        {
+            cursor.get();
+            fail( "Should not get here" );
+        }
+        catch ( InvalidCursorPositionException e )
+        {
+            assertNotNull( e );
+        }
+        
+        cursor.beforeFirst();
+        assertFalse( cursor.available() );
+        assertFalse( cursor.previous() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get() );
+        
+        cursor.afterLast();
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+        
+        assertTrue( cursor.first() );
+        assertTrue( cursor.available() );
+        
+        assertTrue( cursor.last() );
+        assertTrue( cursor.available() );
+        
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+        
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+
+        cursor.before( 3 );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get() );
+        
+        cursor.after( 3 );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get() );
+
+        cursor.before( 7 );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get() );
+    }
+    
+    
+    @Test
+    public void testManyEntriesCursor() throws Exception
+    {
+        AvlTree<Integer> tree = new AvlTree<Integer>( new IntegerComparator()
);
+        tree.insert( 3 );
+        tree.insert( 7 );
+        tree.insert( 10 );
+        tree.insert( 11 );
+        AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( tree );
+        
+        assertFalse( cursor.isClosed() );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.isElementReused() );
+        assertEquals( 4, tree.getSize() );
+        
+        try
+        {
+            cursor.get();
+            fail( "Should not get here" );
+        }
+        catch ( InvalidCursorPositionException e )
+        {
+            assertNotNull( e );
+        }
+        
+        cursor.beforeFirst();
+        assertFalse( cursor.available() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 3, ( int ) cursor.get() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 10, ( int ) cursor.get() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, ( int ) cursor.get() );
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+        
+        
+        cursor.afterLast();
+        assertFalse( cursor.available() );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, ( int ) cursor.get() );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 10, ( int ) cursor.get() );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get() );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 3, ( int ) cursor.get() );
+        assertFalse( cursor.previous() );
+        assertFalse( cursor.available() );
+        
+        assertTrue( cursor.first() );
+        assertTrue( cursor.available() );
+        
+        assertTrue( cursor.last() );
+        assertTrue( cursor.available() );
+        
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+        
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        
+        cursor.after( 5 );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get() );
+        
+        
+        cursor.before( 11 );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, ( int ) cursor.get() );
+        
+    }
+   
+    
+    class IntegerComparator implements Comparator<Integer>
+    {
+        public int compare( Integer o1, Integer o2 )
+        {
+            return o1.compareTo( o2 );
+        }
+    }
+}

Modified: directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java?rev=633937&r1=633936&r2=633937&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
Wed Mar  5 09:18:26 2008
@@ -21,7 +21,6 @@
 
 import static junit.framework.Assert.assertEquals;
 import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertNotSame;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.assertNotNull;

Modified: directory/sandbox/akarasulu/bigbang/apacheds/core-cursor/src/main/java/org/apache/directory/server/core/cursor/Cursor.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/core-cursor/src/main/java/org/apache/directory/server/core/cursor/Cursor.java?rev=633937&r1=633936&r2=633937&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/core-cursor/src/main/java/org/apache/directory/server/core/cursor/Cursor.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/core-cursor/src/main/java/org/apache/directory/server/core/cursor/Cursor.java
Wed Mar  5 09:18:26 2008
@@ -49,14 +49,15 @@
 
     /**
      * Prepares this Cursor, so a subsequent call to Cursor#next() with a
-     * true return value, will have positioned the Cursor on a dataset element
-     * equal to or greater than the element argument but not less.  A call to
-     * Cursor#previous() with a true return value will position the Cursor on
-     * a dataset element less than the argument.  If Cursor#next() returns
-     * false then the Cursor is past the last element and so all values in the
-     * dataset are less than the argument.  If Cursor#previous() returns false
-     * then the Cursor is positioned before the first element and all elements
-     * in the dataset are greater than the argument.
+     * true return value, will have positioned the Cursor on a dataset 
+     * element equal to or less than the element argument but not greater.  
+     * A call to Cursor#previous() with a true return value will position 
+     * the Cursor on a dataset element less than the argument.  If 
+     * Cursor#next() returns false then the Cursor is past the last element 
+     * and so all values in the dataset are less than the argument.  If 
+     * Cursor#previous() returns false then the Cursor is positioned before 
+     * the first element and all elements in the dataset are greater than 
+     * the argument.
      *
      * @param element the element to be positioned before
      * @throws Exception with problems accessing the underlying btree



Mime
View raw message