directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kayyag...@apache.org
Subject svn commit: r760418 - in /directory/apacheds/branches/ldif-partition/core-avl/src: main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursor.java test/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursorTest.java
Date Tue, 31 Mar 2009 12:39:37 GMT
Author: kayyagari
Date: Tue Mar 31 12:39:34 2009
New Revision: 760418

URL: http://svn.apache.org/viewvc?rev=760418&view=rev
Log:
a cursor implementation for AvlTreeMap without duplicate keys

Added:
    directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursor.java
    directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursorTest.java

Added: directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursor.java?rev=760418&view=auto
==============================================================================
--- directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursor.java
(added)
+++ directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursor.java
Tue Mar 31 12:39:34 2009
@@ -0,0 +1,273 @@
+/*
+ *   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.InvalidCursorPositionException;
+import org.apache.directory.server.xdbm.AbstractTupleCursor;
+import org.apache.directory.server.xdbm.Tuple;
+
+
+/**
+ * A Cursor for AvlTreeMap without duplicates.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AvlTreeMapNoDupsCursor<K,V> extends AbstractTupleCursor<K,V>
+{
+    private AvlTreeMap<K,V> tree;
+    private LinkedAvlMapNode<K,V> node;
+    private boolean onNode = false;
+    private boolean isAfterLast = false;
+    private boolean isBeforeFirst = true;
+    private Tuple<K,V> returnedTuple = new Tuple<K,V>();
+    
+    public AvlTreeMapNoDupsCursor( AvlTreeMap<K,V> tree )
+    {
+        this.tree = tree;
+    }
+
+    
+    public void after( Tuple<K,V> element ) throws Exception 
+    {
+        afterKey( element.getKey() );
+    }
+
+
+    public void afterLast() throws Exception 
+    {
+        checkNotClosed( "afterLast" );
+        node = tree.getLast();
+        isBeforeFirst = false;
+        isAfterLast = true;
+        onNode = false;
+    }
+
+
+    public boolean available()
+    {
+        return onNode;
+    }
+
+
+    public void before( Tuple<K,V> element ) throws Exception 
+    {
+        beforeKey( element.getKey() );
+    }
+
+
+    public void beforeFirst() throws Exception 
+    {
+        checkNotClosed( "beforeFirst" );
+        node = tree.getFirst();
+        isBeforeFirst = true;
+        isAfterLast = false;
+        onNode = false;
+    }
+
+
+    public boolean first() throws Exception 
+    {
+        checkNotClosed( "first" );
+        node = tree.getFirst();
+        isBeforeFirst = false;
+        isAfterLast = false;
+        return onNode = ( node != null );
+    }
+
+
+    public Tuple<K,V> get() throws Exception 
+    {
+        checkNotClosed( "get" );
+        if ( onNode )
+        {
+            returnedTuple.setKey( node.key );
+            returnedTuple.setValue( node.value );
+            return returnedTuple;
+        }
+        
+        throw new InvalidCursorPositionException();
+    }
+
+
+    public boolean isElementReused()
+    {
+        return true;
+    }
+
+
+    public boolean last() throws Exception 
+    {
+        checkNotClosed( "last" );
+        node = tree.getLast();
+        isBeforeFirst = false;
+        isAfterLast = false;
+        return onNode = ( node != null );
+    }
+
+
+    public boolean next() throws Exception 
+    {
+        checkNotClosed( "next" );
+        
+        if ( isBeforeFirst )
+        {
+            node = tree.getFirst();
+            isBeforeFirst = false;
+            isAfterLast = false;
+            return onNode = node != null;
+        }
+
+        if ( isAfterLast )
+        {
+            return false;
+        }
+        else if ( onNode )
+        {
+            if ( node == null )
+            {
+                node = tree.getFirst();
+                return true;
+            }
+            
+            if ( node.next == null )
+            {
+                onNode = false;
+                isAfterLast = true;
+                isBeforeFirst = false;
+                return false;
+            }
+            
+            node = node.next;
+            return true;
+        }
+
+        return node != null && ( onNode = true );
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        checkNotClosed( "previous" );
+
+        if ( isBeforeFirst )
+        {
+            return false;
+        }
+
+        if ( isAfterLast )
+        {
+            node = tree.getLast();
+            isBeforeFirst = false;
+            isAfterLast = false;
+            return onNode = node != null;
+        }
+
+        if ( onNode )
+        {
+            if ( node == null )
+            {
+                node = tree.getLast();
+                return true;
+            }
+            if ( node.previous == null )
+            {
+                onNode = false;
+                isAfterLast = false;
+                isBeforeFirst = true;
+                return false;
+            }
+            
+            node = node.previous;
+            return true;
+        }
+        
+        return false;
+    }
+
+
+    public void afterKey( K key ) throws Exception
+    {
+        checkNotClosed( "afterKey" );
+
+        if ( key == null )
+        {
+            afterLast();
+            return;
+        }
+
+        LinkedAvlMapNode<K,V> found = tree.findGreater( key );
+        
+        if ( found == null )
+        {
+            node = tree.getLast();
+            onNode = false;
+            isAfterLast = true;
+            isBeforeFirst = false;
+            return;
+        }
+
+        node = found;
+        isAfterLast = false;
+        isBeforeFirst = false;
+        onNode = false;
+
+    }
+
+
+    public void afterValue( K key, V value ) throws Exception
+    {
+        throw new UnsupportedOperationException( "This Cursor does not support duplicate
keys." );
+    }
+
+
+    public void beforeKey( K key ) throws Exception
+    {
+        checkNotClosed( "beforeKey" );
+
+        if ( key == null )
+        {
+            beforeFirst();
+            return;
+        }
+
+        LinkedAvlMapNode<K,V> found = tree.findLess( key );
+        if ( found == null )
+        {
+            node = tree.getFirst();
+            isAfterLast = false;
+            isBeforeFirst = true;
+        }
+        else
+        {
+            node = found.next;
+            isAfterLast = false;
+            isBeforeFirst = false;
+        }
+        onNode = false;
+    }
+
+
+    public void beforeValue( K key, V value ) throws Exception
+    {
+        throw new UnsupportedOperationException( "This Cursor does not support duplicate
keys." );
+    }
+}

Added: directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursorTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursorTest.java?rev=760418&view=auto
==============================================================================
--- directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursorTest.java
(added)
+++ directory/apacheds/branches/ldif-partition/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeMapNoDupsCursorTest.java
Tue Mar 31 12:39:34 2009
@@ -0,0 +1,292 @@
+/*
+ *   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.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.Comparator;
+
+import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
+import org.apache.directory.server.xdbm.Tuple;
+import org.junit.Before;
+import org.junit.Test;
+
+
+/**
+ * 
+ * AvlTreeMapNoDupsCursorTest.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AvlTreeMapNoDupsCursorTest
+{
+    AvlTreeMap<Integer, Integer> tree;
+
+    AvlTreeMapNoDupsCursor<Integer, Integer> cursor;
+
+
+    @Before
+    public void createTree()
+    {
+        Comparator<Integer> comparator = new Comparator<Integer>()
+        {
+
+            public int compare( Integer i1, Integer i2 )
+            {
+                return i1.compareTo( i2 );
+            }
+
+        };
+
+        tree = new AvlTreeMap<Integer, Integer>( comparator, comparator );
+
+        cursor = new AvlTreeMapNoDupsCursor<Integer, Integer>( tree );
+    }
+
+
+    @Test
+    public void testEmptyCursor() throws Exception
+    {
+        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( new Tuple( 3, null ) );
+        assertFalse( cursor.available() );
+
+        cursor.after( new Tuple( 3, null ) );
+        assertFalse( cursor.available() );
+
+        cursor.close();
+        assertTrue( cursor.isClosed() );
+    }
+
+
+    @Test
+    public void testCursor() throws Exception
+    {
+        tree.insert( 7, 7 );
+        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().getKey() );
+        assertEquals( 7, ( int ) cursor.get().getValue() );
+
+        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( new Tuple( 3, null ) );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get().getKey() );
+        assertEquals( 7, ( int ) cursor.get().getValue() );
+
+        cursor.after( new Tuple( 3, null ) );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get().getKey() );
+        assertEquals( 7, ( int ) cursor.get().getValue() );
+
+        cursor.before( new Tuple( 7, null ) );
+        assertFalse( cursor.available() );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get().getKey() );
+        assertEquals( 7, ( int ) cursor.get().getValue() );
+    }
+
+
+    @Test
+    public void testManyEntriesCursor() throws Exception
+    {
+        tree.insert( 3, 3 );
+        tree.insert( 7, 7 );
+        tree.insert( 10, 10 );
+        tree.insert( 11, 11 );
+
+        tree.insert( 3, 2 ); // try inserting a duplicate
+
+        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().getKey() );
+        assertEquals( 3, ( int ) cursor.get().getValue() );
+
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get().getKey() );
+        assertEquals( 7, ( int ) cursor.get().getValue() );
+
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 10, ( int ) cursor.get().getKey() );
+        assertEquals( 10, ( int ) cursor.get().getValue() );
+        
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, ( int ) cursor.get().getKey() );
+        assertEquals( 11, ( int ) cursor.get().getValue() );
+        assertFalse( cursor.next() );
+        assertFalse( cursor.available() );
+
+        cursor.afterLast();
+        assertFalse( cursor.available() );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, ( int ) cursor.get().getKey() );
+        assertEquals( 11, ( int ) cursor.get().getValue() );
+        
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 10, ( int ) cursor.get().getKey() );
+        assertEquals( 10, ( int ) cursor.get().getValue() );
+        
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get().getKey() );
+        assertEquals( 7, ( int ) cursor.get().getValue() );
+        assertTrue( cursor.previous() );
+        assertTrue( cursor.available() );
+        assertEquals( 3, ( int ) cursor.get().getKey() );
+        assertEquals( 3, ( int ) cursor.get().getValue() );
+        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( new Tuple( 5, null ) );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 7, ( int ) cursor.get().getKey() );
+        assertEquals( 7, ( int ) cursor.get().getValue() );
+        
+        cursor.before( new Tuple( 11, null ) );
+        assertTrue( cursor.next() );
+        assertTrue( cursor.available() );
+        assertEquals( 11, ( int ) cursor.get().getKey() );
+        assertEquals( 11, ( int ) cursor.get().getValue() );
+    }
+
+
+    @Test(expected = UnsupportedOperationException.class)
+    public void testAfterValue() throws Exception
+    {
+        cursor.afterValue( 0, 0 );
+    }
+
+
+    @Test(expected = UnsupportedOperationException.class)
+    public void testBeforeValue() throws Exception
+    {
+        cursor.beforeValue( 0, 0 );
+    }
+
+}



Mime
View raw message