Return-Path: 
 <directory-cvs-return-1005-apmail-incubator-directory-cvs-archive=incubator.apache.org@incubator.apache.org>
Delivered-To: apmail-incubator-directory-cvs-archive@www.apache.org
Received: (qmail 16361 invoked from network); 14 Jun 2004 07:21:57 -0000
Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199)
  by minotaur-2.apache.org with SMTP; 14 Jun 2004 07:21:57 -0000
Received: (qmail 67105 invoked by uid 500); 14 Jun 2004 07:21:59 -0000
Delivered-To: apmail-incubator-directory-cvs-archive@incubator.apache.org
Received: (qmail 67060 invoked by uid 500); 14 Jun 2004 07:21:58 -0000
Mailing-List: contact directory-cvs-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: directory-dev@incubator.apache.org
list-help: <mailto:directory-cvs-help@incubator.apache.org>
list-unsubscribe: <mailto:directory-cvs-unsubscribe@incubator.apache.org>
list-post: <mailto:directory-cvs@incubator.apache.org>
Delivered-To: mailing list directory-cvs@incubator.apache.org
Received: (qmail 67041 invoked by uid 99); 14 Jun 2004 07:21:57 -0000
Received: from [209.237.227.194] (HELO minotaur.apache.org) (209.237.227.194)
  by apache.org (qpsmtpd/0.27.1) with SMTP; Mon, 14 Jun 2004 00:21:57 -0700
Received: (qmail 16308 invoked by uid 65534); 14 Jun 2004 07:21:46 -0000
Date: 14 Jun 2004 07:21:46 -0000
Message-ID: <20040614072146.16307.qmail@minotaur.apache.org>
From: akarasulu@apache.org
To: directory-cvs@incubator.apache.org
Subject: svn commit: rev 21191 - in incubator/directory/ldap/trunk/common/src:
 java/org/apache/ldap/common/filter test test/org test/org/apache
 test/org/apache/ldap test/org/apache/ldap/common
 test/org/apache/ldap/common/filter
X-Virus-Checked: Checked
X-Spam-Rating: minotaur-2.apache.org 1.6.2 0/1000/N

Author: akarasulu
Date: Mon Jun 14 00:21:45 2004
New Revision: 21191

Added:
   incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/filter/BranchNormalizedVisitor.java   (contents, props changed)
   incubator/directory/ldap/trunk/common/src/test/
   incubator/directory/ldap/trunk/common/src/test/org/
   incubator/directory/ldap/trunk/common/src/test/org/apache/
   incubator/directory/ldap/trunk/common/src/test/org/apache/ldap/
   incubator/directory/ldap/trunk/common/src/test/org/apache/ldap/common/
   incubator/directory/ldap/trunk/common/src/test/org/apache/ldap/common/filter/
   incubator/directory/ldap/trunk/common/src/test/org/apache/ldap/common/filter/BranchNormalizedVisitorTest.java   (contents, props changed)
Modified:
   incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/filter/BranchNode.java
   incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/filter/FilterVisitor.java
Log:
Added visitor implementation that normalizes the order of AND'ed and 
OR'ed terms in branch nodes.  This is very useful for testing expressions
while being ignorant of order.


Modified: incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/filter/BranchNode.java
==============================================================================
--- incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/filter/BranchNode.java	(original)
+++ incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/filter/BranchNode.java	Mon Jun 14 00:21:45 2004
@@ -202,336 +202,356 @@
  *   limitations under the License.
  *
  */
-
-/*
- * $Id: BranchNode.java,v 1.14 2003/10/14 04:59:23 akarasulu Exp $
- *
- * -- (c) LDAPd Group                                                    --
- * -- Please refer to the LICENSE.txt file in the root directory of      --
- * -- any LDAPd project for copyright and distribution information.      --
- * 
- */
-
-package org.apache.ldap.common.filter ;
-
-
-import java.util.ArrayList ;
-import java.math.BigInteger ;
-
-
-/**
- * Node representing branches within the expression tree corresponding to 
- * logical operators within the filter expression.
- * 
- * @author <a href="mailto:aok123@bellsouth.net">Alex Karasulu</a>
- * @author $Author: akarasulu $
- * @version $Revision: 1.14 $
- */
-public class BranchNode
-    extends AbstractExprNode
-{
-    /** logical operator for this branch node */ 
-    private final int m_operator ;
-    /** child node list for this branch node */
-    private ArrayList m_children = null ;
-
-
-    /**
-     * Creates a BranchNode using a logical operator and a list of children.
-     *
-     * @param an_operator the logical operator to use for this branch node.
-     * @param a_childList the child nodes under this branch node.
-     */
-    public BranchNode( int an_operator, ArrayList a_childList )
-    {
-        super ( an_operator ) ;
-        
-        if ( null == a_childList ) 
-        {
-            m_children = new ArrayList( 2 ) ;
-        } 
-        else  
-        {
-            m_children = a_childList ;
-        }
-
-        m_operator = an_operator ;
-
-        switch( m_operator ) 
-        {
-        case( AND ):
-            break ;
-        case( NOT ):
-            break ;
-        case( OR ):
-            break ;
-        default:
-            throw new IllegalArgumentException(
-                "Logical operator argument in constructor is undefined." ) ;
-        }
-    }
-
-
-    /**
-     * Creates a BranchNode using a logical operator.
-     *
-     * @param an_operator the logical operator to use for this branch node.
-     */
-    public BranchNode( int an_operator )
-    {
-        this( an_operator, null ) ;
-    }
-
-
-    /**
-     * Adds a child node to this branch node if it allows it.  Some branch nodes
-     * like the negation node does not allow more than one child.  An attempt to
-     * add more than one node to a negation branch node will result in an 
-     * IllegalStateException.
-     *
-     * @param a_node the child expression to add to this branch node
-     */
-    public void addNode( ExprNode a_node )
-    {
-        if ( NOT == m_operator && m_children.size() >= 1 )
-        {
-            throw new IllegalStateException( "Cannot add more than one element"
-                + " to a negation node." ) ;
-        }
-        
-        m_children.add( a_node ) ;
-    }
-
-
-    /**
-     * @see org.apache.ldap.common.filter.ExprNode#isLeaf()
-     * @return false all the time.
-     */
-    public final boolean isLeaf()
-    {
-        return false ;
-    }
-
-
-    /**
-     * Gets the children below this BranchNode.
-     * We purposefully do not clone the array list so that backends can sort the
-     * order of children using their own search optimization algorithms.  We
-     * want backends and other parts of the system to be able to induce side
-     * effects on the tree structure.
-     * 
-     * @return the list of child nodes under this branch node.
-     */
-    public ArrayList getChildren()
-    {
-        return m_children ;
-    }
-    
-    
-    /**
-     * Convenience method that gets the first child in the children array.  Its
-     * very useful for NOT nodes since they only have one child by avoiding code
-     * that looks like: <code> ( ExprNode ) m_children.get( 0 ) </code> 
-     *
-     * @return the first child
-     */
-    public ExprNode getChild()
-    {
-        return ( ExprNode ) m_children.get( 0 ) ;
-    }
-
-
-    /**
-     * Sets the list of children under this node.
-     * 
-     * @param a_list the list of children to set.
-     */
-    void setChildren( ArrayList a_list )
-    {
-        m_children = a_list ;
-    }
-
-
-    /**
-     * Gets the operator for this branch node.
-     *
-     * @return the operator constant.
-     */
-    public int getOperator()
-    {
-        return m_operator ;
-    }
-
-
-    /**
-     * Tests whether or not this node is a disjunction (a OR'ed branch).
-     *
-     * @return true if the operation is a OR, false otherwise.
-     */
-    public boolean isDisjunction()
-    {
-        return OR == m_operator ;
-    }
-
-
-    /**
-     * Tests whether or not this node is a conjunction (a AND'ed branch).
-     *
-     * @return true if the operation is a AND, false otherwise.
-     */
-    public boolean isConjunction()
-    {
-        return AND == m_operator ;
-    }
-
-
-    /**
-     * Tests whether or not this node is a negation (a NOT'ed branch).
-     *
-     * @return true if the operation is a NOT, false otherwise.
-     */
-    public final boolean isNegation()
-    {
-        return NOT == m_operator ;
-    }
-
-
-    /**
-     * Recursively prints the String representation of this node and all its 
-     * descendents to a buffer.  
-     *
-     * @see org.apache.ldap.common.filter.ExprNode#printToBuffer(java.lang.StringBuffer)
-     */
-    public void printToBuffer( StringBuffer a_buf )
-    {
-        a_buf.append( '(' ) ;
-
-        switch( m_operator ) 
-        {
-        case( AND ):
-            a_buf.append( "& " ) ;
-            break ;
-        case( NOT ):
-            a_buf.append( "! " ) ;
-            break ;
-        case( OR ):
-            a_buf.append( "| " ) ;
-            break ;
-        default:
-            a_buf.append( "UNKNOWN" ) ;
-        }
-
-        for ( int ii = 0; ii < m_children.size(); ii++ ) 
-        {
-            ( ( ExprNode ) m_children.get( ii ) ).printToBuffer( a_buf ) ;
-        }
-
-        a_buf.append( ')' ) ;
-        if ( null != getAnnotations() 
-            && getAnnotations().containsKey( "count" ) ) 
-        {
-            a_buf.append( '[' ) ;
-            a_buf.append( ( ( BigInteger ) 
-                getAnnotations().get( "count" ) ).toString() ) ;
-            a_buf.append( "] " ) ;
-        } 
-        else 
-        {
-            a_buf.append( ' ' ) ;
-        }
-    }
-
-
-    /**
-     * Gets a human readable representation for the operators: AND for '&', OR
-     * for '|' and NOT for '!'.
-     *
-     * @param a_operator the operator constant.
-     * @return one of the strings AND, OR, or NOT. 
-     */
-    public static String getOperatorString( int a_operator )
-    {
-        String l_opstr = null ;
-
-        switch( a_operator ) 
-        {
-        case( AND ):
-            l_opstr = "AND" ;
-            break ;
-        case( NOT ):
-            l_opstr = "NOT" ;
-            break ;
-        case( OR ):
-            l_opstr = "OR" ;
-            break ;
-        default:
-            l_opstr = "UNKNOWN" ;
-        }
-
-        return l_opstr ;
-    }
-
-
-    /**
-     * Gets the recursive prefix string represent of the filter from this node
-     * down.
-     *
-     * @see java.lang.Object#toString()
-     */
-    public String toString()
-    {
-        StringBuffer l_buf = new StringBuffer() ;
-        l_buf.append( getOperatorString( m_operator ) ) ;
-        if ( null != getAnnotations() 
-            && getAnnotations().containsKey( "count" ) ) 
-        {
-            l_buf.append( '[' ) ;
-            l_buf.append( ( ( BigInteger ) 
-                getAnnotations().get( "count" ) ).toString() ) ;
-            l_buf.append( "] " ) ;
-        } 
-        else 
-        {
-            l_buf.append( ' ' ) ;
-        }
-
-        return l_buf.toString() ;
-    }
-    
-
-    /**
-     * @see org.apache.ldap.common.filter.ExprNode#accept(
-     * org.apache.ldap.common.filter.FilterVisitor)
-     */
-    public void accept( FilterVisitor a_visitor )
-    {
-        if ( a_visitor.isPrefix() )
-        {
-            ArrayList l_children = a_visitor.getOrder( this, m_children ) ;
-            
-            if ( a_visitor.canVisit( this ) ) 
-            {
-                a_visitor.visit( this ) ;
-            }
-
-            for ( int ii = 0; ii < l_children.size(); ii++ )
-            {
-                ( ( ExprNode ) l_children.get( ii ) ).accept( a_visitor ) ;
-            }
-        }
-        else 
-        {
-            ArrayList l_children = a_visitor.getOrder( this, m_children ) ;
-            
-            for ( int ii = 0; ii < l_children.size(); ii++ )
-            {
-                ( ( ExprNode ) l_children.get( ii ) ).accept( a_visitor ) ;
-            }
-            
-            if ( a_visitor.canVisit( this ) )
-            {
-                a_visitor.visit( this ) ;
-            }
-        }
-    }
-}
+
+/*
+ * $Id: BranchNode.java,v 1.14 2003/10/14 04:59:23 akarasulu Exp $
+ *
+ * -- (c) LDAPd Group                                                    --
+ * -- Please refer to the LICENSE.txt file in the root directory of      --
+ * -- any LDAPd project for copyright and distribution information.      --
+ * 
+ */
+
+package org.apache.ldap.common.filter ;
+
+
+import java.util.ArrayList ;
+import java.math.BigInteger ;
+
+
+/**
+ * Node representing branches within the expression tree corresponding to 
+ * logical operators within the filter expression.
+ * 
+ * @author <a href="mailto:aok123@bellsouth.net">Alex Karasulu</a>
+ * @author $Author: akarasulu $
+ * @version $Revision: 1.14 $
+ */
+public class BranchNode
+    extends AbstractExprNode
+{
+    /** logical operator for this branch node */ 
+    private final int m_operator ;
+    /** child node list for this branch node */
+    private ArrayList m_children = null ;
+
+
+    /**
+     * Creates a BranchNode using a logical operator and a list of children.
+     *
+     * @param an_operator the logical operator to use for this branch node.
+     * @param a_childList the child nodes under this branch node.
+     */
+    public BranchNode( int an_operator, ArrayList a_childList )
+    {
+        super ( an_operator ) ;
+        
+        if ( null == a_childList ) 
+        {
+            m_children = new ArrayList( 2 ) ;
+        } 
+        else  
+        {
+            m_children = a_childList ;
+        }
+
+        m_operator = an_operator ;
+
+        switch( m_operator ) 
+        {
+        case( AND ):
+            break ;
+        case( NOT ):
+            break ;
+        case( OR ):
+            break ;
+        default:
+            throw new IllegalArgumentException(
+                "Logical operator argument in constructor is undefined." ) ;
+        }
+    }
+
+
+    /**
+     * Creates a BranchNode using a logical operator.
+     *
+     * @param an_operator the logical operator to use for this branch node.
+     */
+    public BranchNode( int an_operator )
+    {
+        this( an_operator, null ) ;
+    }
+
+
+    /**
+     * Adds a child node to this branch node if it allows it.  Some branch nodes
+     * like the negation node does not allow more than one child.  An attempt to
+     * add more than one node to a negation branch node will result in an 
+     * IllegalStateException.
+     *
+     * @param a_node the child expression to add to this branch node
+     */
+    public void addNode( ExprNode a_node )
+    {
+        if ( NOT == m_operator && m_children.size() >= 1 )
+        {
+            throw new IllegalStateException( "Cannot add more than one element"
+                + " to a negation node." ) ;
+        }
+        
+        m_children.add( a_node ) ;
+    }
+
+
+    /**
+     * Adds a child node to this branch node if it allows it at the head rather
+     * than the tail.  Some branch nodes like the negation node does not allow
+     * more than one child.  An attempt to add more than one node to a negation
+     * branch node will result in an IllegalStateException.
+     *
+     * @param a_node the child expression to add to this branch node
+     */
+    public void addNodeToHead( ExprNode a_node )
+    {
+        if ( NOT == m_operator && m_children.size() >= 1 )
+        {
+            throw new IllegalStateException( "Cannot add more than one element"
+                + " to a negation node." ) ;
+        }
+
+        m_children.add( 0, a_node ) ;
+    }
+
+
+    /**
+     * @see org.apache.ldap.common.filter.ExprNode#isLeaf()
+     * @return false all the time.
+     */
+    public final boolean isLeaf()
+    {
+        return false ;
+    }
+
+
+    /**
+     * Gets the children below this BranchNode.
+     * We purposefully do not clone the array list so that backends can sort the
+     * order of children using their own search optimization algorithms.  We
+     * want backends and other parts of the system to be able to induce side
+     * effects on the tree structure.
+     * 
+     * @return the list of child nodes under this branch node.
+     */
+    public ArrayList getChildren()
+    {
+        return m_children ;
+    }
+    
+    
+    /**
+     * Convenience method that gets the first child in the children array.  Its
+     * very useful for NOT nodes since they only have one child by avoiding code
+     * that looks like: <code> ( ExprNode ) m_children.get( 0 ) </code> 
+     *
+     * @return the first child
+     */
+    public ExprNode getChild()
+    {
+        return ( ExprNode ) m_children.get( 0 ) ;
+    }
+
+
+    /**
+     * Sets the list of children under this node.
+     * 
+     * @param a_list the list of children to set.
+     */
+    void setChildren( ArrayList a_list )
+    {
+        m_children = a_list ;
+    }
+
+
+    /**
+     * Gets the operator for this branch node.
+     *
+     * @return the operator constant.
+     */
+    public int getOperator()
+    {
+        return m_operator ;
+    }
+
+
+    /**
+     * Tests whether or not this node is a disjunction (a OR'ed branch).
+     *
+     * @return true if the operation is a OR, false otherwise.
+     */
+    public boolean isDisjunction()
+    {
+        return OR == m_operator ;
+    }
+
+
+    /**
+     * Tests whether or not this node is a conjunction (a AND'ed branch).
+     *
+     * @return true if the operation is a AND, false otherwise.
+     */
+    public boolean isConjunction()
+    {
+        return AND == m_operator ;
+    }
+
+
+    /**
+     * Tests whether or not this node is a negation (a NOT'ed branch).
+     *
+     * @return true if the operation is a NOT, false otherwise.
+     */
+    public final boolean isNegation()
+    {
+        return NOT == m_operator ;
+    }
+
+
+    /**
+     * Recursively prints the String representation of this node and all its 
+     * descendents to a buffer.  
+     *
+     * @see org.apache.ldap.common.filter.ExprNode#printToBuffer(java.lang.StringBuffer)
+     */
+    public void printToBuffer( StringBuffer a_buf )
+    {
+        a_buf.append( '(' ) ;
+
+        switch( m_operator ) 
+        {
+        case( AND ):
+            a_buf.append( "& " ) ;
+            break ;
+        case( NOT ):
+            a_buf.append( "! " ) ;
+            break ;
+        case( OR ):
+            a_buf.append( "| " ) ;
+            break ;
+        default:
+            a_buf.append( "UNKNOWN" ) ;
+        }
+
+        for ( int ii = 0; ii < m_children.size(); ii++ ) 
+        {
+            ( ( ExprNode ) m_children.get( ii ) ).printToBuffer( a_buf ) ;
+        }
+
+        a_buf.append( ')' ) ;
+        if ( null != getAnnotations() 
+            && getAnnotations().containsKey( "count" ) ) 
+        {
+            a_buf.append( '[' ) ;
+            a_buf.append( ( ( BigInteger ) 
+                getAnnotations().get( "count" ) ).toString() ) ;
+            a_buf.append( "] " ) ;
+        } 
+        else 
+        {
+            a_buf.append( ' ' ) ;
+        }
+    }
+
+
+    /**
+     * Gets a human readable representation for the operators: AND for '&', OR
+     * for '|' and NOT for '!'.
+     *
+     * @param a_operator the operator constant.
+     * @return one of the strings AND, OR, or NOT. 
+     */
+    public static String getOperatorString( int a_operator )
+    {
+        String l_opstr = null ;
+
+        switch( a_operator ) 
+        {
+        case( AND ):
+            l_opstr = "AND" ;
+            break ;
+        case( NOT ):
+            l_opstr = "NOT" ;
+            break ;
+        case( OR ):
+            l_opstr = "OR" ;
+            break ;
+        default:
+            l_opstr = "UNKNOWN" ;
+        }
+
+        return l_opstr ;
+    }
+
+
+    /**
+     * Gets the recursive prefix string represent of the filter from this node
+     * down.
+     *
+     * @see java.lang.Object#toString()
+     */
+    public String toString()
+    {
+        StringBuffer l_buf = new StringBuffer() ;
+        l_buf.append( getOperatorString( m_operator ) ) ;
+        if ( null != getAnnotations() 
+            && getAnnotations().containsKey( "count" ) ) 
+        {
+            l_buf.append( '[' ) ;
+            l_buf.append( ( ( BigInteger ) 
+                getAnnotations().get( "count" ) ).toString() ) ;
+            l_buf.append( "] " ) ;
+        } 
+        else 
+        {
+            l_buf.append( ' ' ) ;
+        }
+
+        return l_buf.toString() ;
+    }
+    
+
+    /**
+     * @see org.apache.ldap.common.filter.ExprNode#accept(
+     * org.apache.ldap.common.filter.FilterVisitor)
+     */
+    public void accept( FilterVisitor a_visitor )
+    {
+        if ( a_visitor.isPrefix() )
+        {
+            ArrayList l_children = a_visitor.getOrder( this, m_children ) ;
+            
+            if ( a_visitor.canVisit( this ) ) 
+            {
+                a_visitor.visit( this ) ;
+            }
+
+            for ( int ii = 0; ii < l_children.size(); ii++ )
+            {
+                ( ( ExprNode ) l_children.get( ii ) ).accept( a_visitor ) ;
+            }
+        }
+        else 
+        {
+            ArrayList l_children = a_visitor.getOrder( this, m_children ) ;
+            
+            for ( int ii = 0; ii < l_children.size(); ii++ )
+            {
+                ( ( ExprNode ) l_children.get( ii ) ).accept( a_visitor ) ;
+            }
+            
+            if ( a_visitor.canVisit( this ) )
+            {
+                a_visitor.visit( this ) ;
+            }
+        }
+    }
+}

Added: incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/filter/BranchNormalizedVisitor.java
==============================================================================
--- (empty file)
+++ incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/filter/BranchNormalizedVisitor.java	Mon Jun 14 00:21:45 2004
@@ -0,0 +1,114 @@
+/*
+ *   Copyright 2004 The Apache Software Foundation
+ *
+ *   Licensed 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.ldap.common.filter;
+
+
+import java.util.TreeSet;
+import java.util.ArrayList;
+import java.util.Comparator;
+
+
+/**
+ * Visitor which traverses a filter tree while normalizing the branch node
+ * order.  Filter expressions can change the order of expressions in branch
+ * nodes without effecting the logical meaning of the expression.  This visitor
+ * orders the children of expression tree branch nodes consistantly.  It is
+ * really useful for comparing expression trees which may be altered for
+ * performance or altered because of codec idiosyncracies: for example the
+ * SNACC4J codec uses a hashmap to store expressions in a sequence which
+ * rearranges the order of children based on object hashcodes.  We need this
+ * visitor to remove such inconsitancies in order hence normalizing the branch
+ * node's child order.
+ * 
+ * @author <a href="mailto:directory-dev@incubator.apache.org">Apache Directory
+ *         Project</a>
+ * @version $Rev$
+ */
+public class BranchNormalizedVisitor implements FilterVisitor
+{
+    public void visit( ExprNode node )
+    {
+        if ( ! ( node instanceof BranchNode ) )
+        {
+            return;
+        }
+
+        BranchNode branch = ( BranchNode ) node;
+
+        if ( branch.getOperator() == AbstractExprNode.NOT )
+        {
+            return;
+        }
+
+
+        Comparator strComp = new Comparator()
+        {
+            StringBuffer buf = new StringBuffer() ;
+
+            public int compare( Object o1, Object o2 )
+            {
+                ExprNode n1 = ( ExprNode ) o1;
+                ExprNode n2 = ( ExprNode ) o2;
+
+                buf.setLength( 0 );
+                String s1 = null;
+                n1.printToBuffer( buf );
+                s1 = buf.toString();
+
+                buf.setLength( 0 );
+                String s2 = null;
+                n2.printToBuffer( buf );
+                s2 = buf.toString();
+
+                return s1.compareTo( s2 );
+            }
+        };
+
+        TreeSet set = new TreeSet( strComp ) ;
+        ArrayList children = branch.getChildren();
+        for( int ii = 0; ii < children.size(); ii++ )
+        {
+            set.add( children.get( ii ) ) ;
+        }
+
+        children.clear();
+        children.addAll( set ) ;
+    }
+
+
+    public boolean canVisit( ExprNode node )
+    {
+        if ( node instanceof BranchNode )
+        {
+            return true;
+        }
+
+        return false;
+    }
+
+
+    public boolean isPrefix()
+    {
+        return false;
+    }
+
+
+    public ArrayList getOrder( BranchNode node, ArrayList children )
+    {
+        return children;
+    }
+}

Modified: incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/filter/FilterVisitor.java
==============================================================================
--- incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/filter/FilterVisitor.java	(original)
+++ incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/filter/FilterVisitor.java	Mon Jun 14 00:21:45 2004
@@ -202,75 +202,75 @@
  *   limitations under the License.
  *
  */
-
-/*
- * $Id: FilterVisitor.java,v 1.3 2003/10/14 04:59:23 akarasulu Exp $
- *
- * -- (c) LDAPd Group                                                    --
- * -- Please refer to the LICENSE.txt file in the root directory of      --
- * -- any LDAPd project for copyright and distribution information.      --
- *
- * Created on Oct 13, 2003
- */
-package org.apache.ldap.common.filter ;
-
-
-import java.util.ArrayList ;
-
-
-/**
- * Filter expression tree node visitor interface.  Note that this is a variation
- * of the extrinsic visitor variation.  It has the following advantages over the
- * standard visitor pattern:
- * <ul>
- *  <li>Visitor takes responsibility that a visitor can visit a node</li>
- *  <li>Each visitor knows which types of concrete classes it can visit</li>
- *  <li>New visitors can be created without changing the node class</li>
- *  <li>New node classes can be added without having to change old visitors</li>
- *  <li>Visitation order can be controled in every respect:</li>
- *  <ul>
- *      <li>Visitation rejection with canVisit() and/or getOrder()</li>
- *      <li>Recursive visitation ordering with isPrefix()</li>
- *      <li>Child visitation ordering with getOrder()</li>
- *  </ul>
- * </ul>
- * 
- * @author <a href="mailto:aok123@bellsouth.net">Alex Karasulu</a>
- * @author $Author: akarasulu $
- * @version $Revision: 1.3 $
- */
-public interface FilterVisitor
-{
-    /**
-     * Visits a filter expression AST using a specific visitation order.
-     * 
-     * @param a_node the node to visit
-     */
-    void visit( ExprNode a_node ) ;
-    
-    /**
-     * Checks to see if a node can be visited.
-     * 
-     * @param a_node the node to be visited
-     * @return whether or node the node should be visited
-     */
-    boolean canVisit( ExprNode a_node ) ;
-
-    /**
-     * Determines whether the visitation order is prefix or postfix.
-     * 
-     * @return true if the visitation is in prefix order, false otherwise.
-     */
-    boolean isPrefix() ;
-    
-    /**
-     * Get the array of children to visit sequentially to determine the order of
-     * child visitations.  Some children may not be returned at all if 
-     * canVisit() returns false on them.
-     * 
-     * @param a_parent the parent node
-     * @param a_children the child node array
-     * @return the new reordered array of children
-     */
-    ArrayList getOrder( ExprNode a_parent, ArrayList a_children ) ;
-}
+
+/*
+ * $Id: FilterVisitor.java,v 1.3 2003/10/14 04:59:23 akarasulu Exp $
+ *
+ * -- (c) LDAPd Group                                                    --
+ * -- Please refer to the LICENSE.txt file in the root directory of      --
+ * -- any LDAPd project for copyright and distribution information.      --
+ *
+ * Created on Oct 13, 2003
+ */
+package org.apache.ldap.common.filter ;
+
+
+import java.util.ArrayList ;
+
+
+/**
+ * Filter expression tree node visitor interface.  Note that this is a variation
+ * of the extrinsic visitor variation.  It has the following advantages over the
+ * standard visitor pattern:
+ * <ul>
+ *  <li>Visitor takes responsibility that a visitor can visit a node</li>
+ *  <li>Each visitor knows which types of concrete classes it can visit</li>
+ *  <li>New visitors can be created without changing the node class</li>
+ *  <li>New node classes can be added without having to change old visitors</li>
+ *  <li>Visitation order can be controled in every respect:</li>
+ *  <ul>
+ *      <li>Visitation rejection with canVisit() and/or getOrder()</li>
+ *      <li>Recursive visitation ordering with isPrefix()</li>
+ *      <li>Child visitation ordering with getOrder()</li>
+ *  </ul>
+ * </ul>
+ * 
+ * @author <a href="mailto:aok123@bellsouth.net">Alex Karasulu</a>
+ * @author $Author: akarasulu $
+ * @version $Revision: 1.3 $
+ */
+public interface FilterVisitor
+{
+    /**
+     * Visits a filter expression AST using a specific visitation order.
+     * 
+     * @param a_node the node to visit
+     */
+    void visit( ExprNode a_node ) ;
+    
+    /**
+     * Checks to see if a node can be visited.
+     * 
+     * @param a_node the node to be visited
+     * @return whether or node the node should be visited
+     */
+    boolean canVisit( ExprNode a_node ) ;
+
+    /**
+     * Determines whether the visitation order is prefix or postfix.
+     * 
+     * @return true if the visitation is in prefix order, false otherwise.
+     */
+    boolean isPrefix() ;
+    
+    /**
+     * Get the array of children to visit sequentially to determine the order of
+     * child visitations.  Some children may not be returned at all if 
+     * canVisit() returns false on them.
+     * 
+     * @param node the parent branch node
+     * @param a_children the child node array
+     * @return the new reordered array of children
+     */
+    ArrayList getOrder( BranchNode node, ArrayList a_children ) ;
+}

Added: incubator/directory/ldap/trunk/common/src/test/org/apache/ldap/common/filter/BranchNormalizedVisitorTest.java
==============================================================================
--- (empty file)
+++ incubator/directory/ldap/trunk/common/src/test/org/apache/ldap/common/filter/BranchNormalizedVisitorTest.java	Mon Jun 14 00:21:45 2004
@@ -0,0 +1,108 @@
+/*
+ *   Copyright 2004 The Apache Software Foundation
+ *
+ *   Licensed 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.ldap.common.filter;
+
+
+import junit.framework.TestCase;
+
+
+/**
+ * Tests the BranchNormalizedVisitor.
+ * 
+ * @author <a href="mailto:directory-dev@incubator.apache.org">Apache Directory
+ *         Project</a>
+ * @version $Rev$
+ */
+public class BranchNormalizedVisitorTest extends TestCase
+{
+    public void testBranchNormalizedVisitor0() throws Exception
+    {
+        FilterParserImpl parser = new FilterParserImpl();
+        String filter = "( ou = Human Resources )" ;
+        ExprNode ori = parser.parse( filter );
+        ExprNode altered = parser.parse( filter );
+        BranchNormalizedVisitor visitor = new BranchNormalizedVisitor();
+        visitor.visit( altered );
+
+        StringBuffer oriBuf = new StringBuffer();
+        ori.printToBuffer( oriBuf );
+        StringBuffer alteredBuf = new StringBuffer();
+        altered.printToBuffer( alteredBuf );
+
+        assertEquals( oriBuf.toString(), alteredBuf.toString() );
+    }
+
+
+    public void testBranchNormalizedVisitor1() throws Exception
+    {
+        FilterParserImpl parser = new FilterParserImpl();
+        String filter = "( & ( ou = Human Resources ) ( uid = akarasulu ) )" ;
+        ExprNode ori = parser.parse( filter );
+        ExprNode altered = parser.parse( filter );
+        BranchNormalizedVisitor visitor = new BranchNormalizedVisitor();
+        visitor.visit( altered );
+
+        StringBuffer oriBuf = new StringBuffer();
+        ori.printToBuffer( oriBuf );
+        StringBuffer alteredBuf = new StringBuffer();
+        altered.printToBuffer( alteredBuf );
+
+        assertEquals( oriBuf.toString(), alteredBuf.toString() );
+    }
+
+
+    public void testBranchNormalizedVisitor2() throws Exception
+    {
+        FilterParserImpl parser = new FilterParserImpl();
+        String filter = "( & ( uid = akarasulu ) ( ou = Human Resources ) " ;
+        filter += "(| ( uid = akarasulu ) ( ou = Human Resources ) ) ) " ;
+        ExprNode ori = parser.parse( filter );
+        ExprNode altered = parser.parse( filter );
+        BranchNormalizedVisitor visitor = new BranchNormalizedVisitor();
+        visitor.visit( altered );
+
+        StringBuffer oriBuf = new StringBuffer();
+        ori.printToBuffer( oriBuf );
+        System.out.println( "ori: " + oriBuf.toString() );
+        StringBuffer alteredBuf = new StringBuffer();
+        altered.printToBuffer( alteredBuf );
+        System.out.println( "altered: " + alteredBuf.toString() );
+
+        assertFalse( oriBuf.toString().equals( alteredBuf.toString() ) );
+    }
+
+
+    public void testBranchNormalizedVisitor3() throws Exception
+    {
+        FilterParserImpl parser = new FilterParserImpl();
+        String filter = "( & ( ou = Human Resources ) ( uid = akarasulu ) " ;
+        filter += "(| ( ou = Human Resources ) ( uid = akarasulu ) ) ) " ;
+        ExprNode ori = parser.parse( filter );
+        ExprNode altered = parser.parse( filter );
+        BranchNormalizedVisitor visitor = new BranchNormalizedVisitor();
+        visitor.visit( altered );
+
+        StringBuffer oriBuf = new StringBuffer();
+        ori.printToBuffer( oriBuf );
+        System.out.println( "ori: " + oriBuf.toString() );
+        StringBuffer alteredBuf = new StringBuffer();
+        altered.printToBuffer( alteredBuf );
+        System.out.println( "altered: " + alteredBuf.toString() );
+
+        assertTrue( oriBuf.toString().equals( alteredBuf.toString() ) );
+    }
+}