You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ka...@apache.org on 2009/03/31 14:39:37 UTC
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
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 );
+ }
+
+}