directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject 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
Date Tue, 28 Sep 2010 17:39:10 GMT
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() );
+    }
 }



Mime
View raw message