You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2010/09/28 19:39:10 UTC
svn commit: r1002287 - in /directory/shared/trunk/ldap/src:
main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java
test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java
Author: elecharny
Date: Tue Sep 28 17:39:09 2010
New Revision: 1002287
URL: http://svn.apache.org/viewvc?rev=1002287&view=rev
Log:
Added some methods and tests
Modified:
directory/shared/trunk/ldap/src/main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java
directory/shared/trunk/ldap/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java
Modified: directory/shared/trunk/ldap/src/main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java
URL: http://svn.apache.org/viewvc/directory/shared/trunk/ldap/src/main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java?rev=1002287&r1=1002286&r2=1002287&view=diff
==============================================================================
--- directory/shared/trunk/ldap/src/main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java (original)
+++ directory/shared/trunk/ldap/src/main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java Tue Sep 28 17:39:09 2010
@@ -19,6 +19,7 @@
*/
package org.apache.directory.shared.ldap.util.tree;
+import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
@@ -35,7 +36,7 @@ import org.slf4j.LoggerFactory;
/**
- * An class for nodes in a tree designed to quickly lookup hierarchical DN.
+ * An class storing nodes in a tree designed to map DNs.<br/>
* Branch nodes in this tree refers to child nodes. Leaf nodes in the tree
* don't have any children. <br/>
* A node may contain a reference to an object whose suffix is the path through the
@@ -128,7 +129,19 @@ public class DnNode<N> implements Clonea
return rootNode;
}
-
+
+ /**
+ * Store the given element into the node
+ */
+ private void setElement( N element )
+ {
+ this.element = element;
+ }
+
+
+ //-------------------------------------------------------------------------
+ // Constructors
+ //-------------------------------------------------------------------------
/**
* Creates a new instance of DnNode.
*/
@@ -268,7 +281,7 @@ public class DnNode<N> implements Clonea
return node.element;
}
-
+
/**
* @return True if the Node stores an element. BranchNode may not hold any
* element.
@@ -296,6 +309,130 @@ public class DnNode<N> implements Clonea
return node.element != null;
}
+
+ /**
+ * recursively check if the node has a descendant having an element
+ */
+ private boolean hasDescendantElement( DnNode<N> node )
+ {
+ if ( node == null )
+ {
+ return false;
+ }
+
+ if ( node.hasElement() )
+ {
+ return true;
+ }
+
+ for ( DnNode<N> child : node.getChildren().values() )
+ {
+ if ( hasDescendantElement( child ) )
+ {
+ return true;
+ }
+ }
+
+ // Nothing found ...
+ return false;
+ }
+
+
+ /**
+ * @return True if one of the node below the current node has one element,
+ * False otherwise
+ * @param dn The DN we want to get the element for
+ */
+ public boolean hasDescendantElement( DN dn )
+ {
+ DnNode<N> node = getNode( dn );
+
+ if ( node == null )
+ {
+ return false;
+ }
+
+ // We must be at the right place in the tree
+ if ( node.getDn().size() != dn.size() )
+ {
+ return false;
+ }
+
+ if ( node.hasChildren() )
+ {
+ for ( DnNode<N> child : node.getChildren().values() )
+ {
+ if ( hasDescendantElement( child ) )
+ {
+ return true;
+ }
+ }
+ }
+
+ return false;
+ }
+
+
+ /**
+ * recursively get all the elements from nodes havig an element
+ */
+ private void getDescendantElements( DnNode<N> node, List<N> descendants )
+ {
+ if ( node == null )
+ {
+ return;
+ }
+
+ if ( node.hasElement() )
+ {
+ descendants.add( node.getElement() );
+
+ // Stop here
+ return;
+ }
+
+ for ( DnNode<N> child : node.getChildren().values() )
+ {
+ getDescendantElements( child, descendants );
+ }
+
+ return;
+ }
+
+
+ /**
+ * @return True if one of the node below the current node has one element,
+ * False otherwise
+ * @param dn The DN we want to get the element for
+ */
+ public List<N> getDescendantElements( DN dn )
+ {
+ List<N> descendants = new ArrayList<N>();
+
+ DnNode<N> node = getNode( dn );
+
+ if ( node == null )
+ {
+ return descendants;
+ }
+
+ // We must be at the right place in the tree
+ if ( node.getDn().size() != dn.size() )
+ {
+ return descendants;
+ }
+
+ if ( node.hasChildren() )
+ {
+ for ( DnNode<N> child : node.getChildren().values() )
+ {
+ getDescendantElements( child, descendants );
+ }
+ }
+
+ return descendants;
+ }
+
/**
* Tells if the current DnNode has some children or not
@@ -438,17 +575,34 @@ public class DnNode<N> implements Clonea
if ( nbRdns == 0 )
{
- // That means the added DN is already present.
- String message = "Cannot add a node with a DN already existing in the tree";
- LOG.error( message );
- throw new LdapUnwillingToPerformException( ResultCodeEnum.UNWILLING_TO_PERFORM, message );
+ // That means the added DN is already present. Check if it already has an element
+ if ( parent.hasElement() )
+ {
+ String message = "Cannot add a node to a node already having an element";
+ LOG.error( message );
+ throw new LdapUnwillingToPerformException( ResultCodeEnum.UNWILLING_TO_PERFORM, message );
+ }
+ // We may try to add twice the same DN, without any element
+ else if ( element == null )
+ {
+ String message = "Cannot add a node with no element if it already exists";
+ LOG.error( message );
+ throw new LdapUnwillingToPerformException( ResultCodeEnum.UNWILLING_TO_PERFORM, message );
+ }
+ // All is fine : we are just injecting some data into an existing node
+ else
+ {
+ parent.setElement( element );
+ }
+ }
+ else
+ {
+ DnNode<N> rootNode = createNode( dn, element, nbRdns );
+
+ // done. now, add the newly created tree to the parent node
+ rootNode.parent = parent;
+ parent.children.put( rootNode.rdn, rootNode );
}
-
- DnNode<N> rootNode = createNode( dn, element, nbRdns );
-
- // done. now, add the newly created tree to the parent node
- rootNode.parent = parent;
- parent.children.put( rootNode.rdn, rootNode );
}
}
@@ -536,82 +690,77 @@ public class DnNode<N> implements Clonea
/**
- * Get the parent element of a given DN, if present in the tree. This parent should be a
- * subset of the given dn.<br>
+ * Get the Node for a given DN, if present in the tree.<br>
* For instance, if we have stored dc=acme, dc=org into the tree,
* the DN: ou=example, dc=acme, dc=org will have a parent, and
* dc=acme, dc=org will be returned.
* <br>For the DN ou=apache, dc=org, there is no parent, so null will be returned.
*
* @param dn the normalized distinguished name to resolve to a parent
- * @return the parent associated with the normalized dn
- *
- public N getParentElement( DN dn )
+ * @return the Node associated with the normalized dn
+ */
+ public DnNode<N> getNode( DN dn )
{
List<RDN> rdns = dn.getRdns();
DnNode<N> currentNode = this;
DnNode<N> parent = null;
+ boolean hasAP = false;
// Iterate through all the RDN until we find the associated partition
for ( int i = rdns.size() - 1; i >= 0; i-- )
{
- if ( currentNode == null )
- {
- // We can stop here : there is no more node in the tree
- break;
- }
-
RDN rdn = rdns.get( i );
- if ( currentNode.rdn.equals( rdn ) )
+ if ( currentNode.hasChildren() )
{
+ currentNode = currentNode.children.get( rdn );
+
+ if ( currentNode == null )
+ {
+ break;
+ }
+
+ if ( currentNode.hasElement() )
+ {
+ hasAP = true;
+ }
+
parent = currentNode;
- currentNode = children.get( rdn );
- continue;
}
-
- break;
+ else
+ {
+ break;
+ }
}
- if ( parent != null )
- {
- return parent.getElement();
- }
- else
- {
- return null;
- }
+ return parent;
}
/**
- * Get the Node for a given DN, if present in the tree.<br>
+ * Get the closest Node for a given DN which has an element, if present in the tree.<br>
* For instance, if we have stored dc=acme, dc=org into the tree,
* the DN: ou=example, dc=acme, dc=org will have a parent, and
- * dc=acme, dc=org will be returned.
+ * dc=acme, dc=org will be returned if it has an associated element.
* <br>For the DN ou=apache, dc=org, there is no parent, so null will be returned.
*
* @param dn the normalized distinguished name to resolve to a parent
* @return the Node associated with the normalized dn
*/
- public DnNode<N> getNode( DN dn )
+ public boolean hasParentElement( DN dn )
{
List<RDN> rdns = dn.getRdns();
DnNode<N> currentNode = this;
- DnNode<N> parent = null;
+ boolean hasElement = false;
// Iterate through all the RDN until we find the associated partition
for ( int i = rdns.size() - 1; i >= 0; i-- )
{
RDN rdn = rdns.get( i );
- if ( rdn.equals( currentNode.rdn ) )
- {
- parent = currentNode;
- }
- else if ( currentNode.hasChildren() )
+ if ( currentNode.hasChildren() )
{
currentNode = currentNode.children.get( rdn );
@@ -620,6 +769,11 @@ public class DnNode<N> implements Clonea
break;
}
+ if ( currentNode.hasElement() )
+ {
+ hasElement = true;
+ }
+
parent = currentNode;
}
else
@@ -628,17 +782,10 @@ public class DnNode<N> implements Clonea
}
}
- if ( parent != null )
- {
- return parent;
- }
- else
- {
- return null;
- }
+ return hasElement;
}
-
+
/**
* {@inheritDoc}
*/
Modified: directory/shared/trunk/ldap/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java
URL: http://svn.apache.org/viewvc/directory/shared/trunk/ldap/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java?rev=1002287&r1=1002286&r2=1002287&view=diff
==============================================================================
--- directory/shared/trunk/ldap/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java (original)
+++ directory/shared/trunk/ldap/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java Tue Sep 28 17:39:09 2010
@@ -25,6 +25,7 @@ import static org.junit.Assert.assertNot
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
+import java.util.List;
import java.util.Map;
import org.apache.directory.junit.tools.Concurrent;
@@ -749,4 +750,56 @@ public class TestDnNode
assertFalse( dnLookupTree.hasParent( new DN( "dc=nothing,dc=empty" ) ) );
assertFalse( dnLookupTree.hasParent( new DN( "dc=directory,dc=apache,dc=root" ) ) );
}
+
+
+ //---------------------------------------------------------------------------
+ // Test the hasParentElement(DN) method
+ //---------------------------------------------------------------------------
+ @Test
+ public void testHasParentElement() throws Exception
+ {
+ DnNode<DN> dnLookupTree = new DnNode<DN>();
+ DN dn1 = new DN( "dc=directory,dc=apache,dc=org" );
+ DN dn2 = new DN( "dc=mina,dc=apache,dc=org" );
+ DN dn3 = new DN( "dc=test,dc=com" );
+ DN dn4 = new DN( "dc=acme,dc=com" );
+ DN dn5 = new DN( "dc=acme,c=us,dc=com" );
+ DN dn6 = new DN( "dc=empty" );
+
+ DN org = new DN( "dc=org" );
+
+ dnLookupTree.add( dn1, dn1 );
+ dnLookupTree.add( dn2, dn2 );
+ dnLookupTree.add( dn3, dn3 );
+ dnLookupTree.add( dn4, dn4 );
+ dnLookupTree.add( dn5 );
+ dnLookupTree.add( dn6, dn6 );
+
+ // Inject some intermediary nodes
+ dnLookupTree.add( org, org );
+
+ assertTrue( dnLookupTree.hasParentElement( new DN( "dc=apache,dc=org" ) ) );
+
+ // Check that org has at least one descendant containing an element
+ assertTrue( dnLookupTree.hasDescendantElement( org ) );
+
+ // check that for one node which has no children with any element, we get false
+ assertFalse( dnLookupTree.hasDescendantElement( new DN( "c=us,dc=com" ) ) );
+
+ // Check that we correctly get back all the children
+ DN dn7 = new DN( "dc=elem,dc=mina,dc=apache,dc=org" );
+ dnLookupTree.add( dn7, dn7 );
+
+ // With dc=org, we should get back dn1 and dn3
+ List<DN> dns = dnLookupTree.getDescendantElements( org );
+
+ assertNotNull( dns );
+ assertEquals( 2, dns.size() );
+ assertTrue( dns.contains( dn1 ) );
+ assertTrue( dns.contains( dn2 ) );
+
+ // Same, with a node not having any descendants
+ dns = dnLookupTree.getDescendantElements( dn6 );
+ assertEquals( 0, dns.size() );
+ }
}