/*
 *   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 java.util.ArrayList;
import java.util.Comparator;
import java.util.List;


/**
 * An AvlTreeMap implementation with support to store both key and value.
 * This implementation also supports duplicate keys. The values of a same key
 * will be stored in a AvlTree.
 *
 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
 * @version $Rev$, $Date$
 */
public class AvlTreeMapImpl<K,V> implements AvlTreeMap<K, V>
{
    /** the root of the tree */
    private LinkedAvlMapNode<K,V> root;

    /** The Comparator used for comparing the keys */
    private Comparator<K> keyComparator;

    /** The Comparator used for comparing the values */
    private Comparator<V> valueComparator;
    
    /** node representing the start of the doubly linked list formed with the tree nodes */
    private LinkedAvlMapNode<K,V> first;
    
    /** node representing the end of the doubly linked list formed with the tree nodes */
    private LinkedAvlMapNode<K,V> last;
    
    /** flag to allow storing duplicate keys */
    private boolean allowDuplicates;

    /** size of the map */
    private int size;

    /**
     * Creates a new instance of AVLTreeMap without support for duplicate keys.
     *
     * @param comparator1 the comparator to be used for comparing keys
     */
    public AvlTreeMapImpl( Comparator<K> keyComparator, Comparator<V> valueComparator )
    {
        this( keyComparator, valueComparator, false );
    }
    

    public AvlTreeMapImpl( Comparator<K> keyComparator, Comparator<V> valueComparator, boolean allowDuplicates )
    {
        this.keyComparator = keyComparator;
        this.valueComparator = valueComparator;
        this.allowDuplicates = allowDuplicates;
    }

    
    /**
     * {@inheritDoc}
     */
    public Comparator<K> getKeyComparator()
    {
        return keyComparator;
    }
    

    /**
     * {@inheritDoc}
     */
    public Comparator<V> getValueComparator()
    {
        return valueComparator;
    }
    
    
    /**
     * {@inheritDoc}
     */
    public V insert( K key, V value )
    {
        LinkedAvlMapNode<K,V> node, temp;
        LinkedAvlMapNode<K,V> parent = null;
        int c;
        
        if ( root == null )
        {
          root = new LinkedAvlMapNode<K,V>( key, value );
          first = root;
          last = root;
          size++;
          return null;
        }
        
        node = new LinkedAvlMapNode<K,V>( key, value );
        
        temp = root;
        
        List<LinkedAvlMapNode<K,V>> treePath = new ArrayList<LinkedAvlMapNode<K,V>>();

        while( temp != null )
        {
            treePath.add(0, temp ); // last node first, for the sake of balance factor computation
            parent = temp;
            
            c = keyComparator.compare( key, temp.getKey() );
            
            if( c == 0 )
            {
                if( allowDuplicates )
                {
                    return insertDupKey( key, value, temp ); // key already exists add another value
                }
                else
                {
                    // replace the existing value with the new value
                    return temp.value.setSingleton( value );
                }
            }
            
            if( c < 0 )
            {
                temp.isLeft = true;
                temp = temp.getLeft();
            }
            else
            {
                temp.isLeft = false;
                temp = temp.getRight();
            }
        }
        
        if( ( c = keyComparator.compare( key, parent.getKey() ) ) < 0 )
        {
            parent.setLeft( node );
        }
        else
        {
            parent.setRight( node );
        }
        
        insertInList( node, parent, c );
        
        treePath.add( 0, node );
        balance(treePath);
        
        size++;
        return null;
    }
    
    
    private V insertDupKey( K key, V value, LinkedAvlMapNode<K,V> existingNode )
    {
        AvlTree<V> dupsTree = null;
        
        if( existingNode.value.isOrderedSet() )
        {
            dupsTree = existingNode.value.getOrderedSet();
        }
        else
        {
            // create avlTree, insert singleton into it, then switch modes 
            dupsTree = new AvlTreeImpl<V>( valueComparator );
            dupsTree.insert( existingNode.value.getSingleton() );
            existingNode.value.switchToOrderedSet( dupsTree );
        }
        
        // check if value already exists
        if( dupsTree.find( value ) != null )
        {
        	return value;
        }
        
        // insert value into duplicate key holder
        dupsTree.insert( value );
        
        return null;
    }
    
    
    private void removeFromList(LinkedAvlMapNode<K,V> node)
    {
        if( node.next == null && node.previous == null ) // should happen in case of tree having single node
        {
            first = last = null;
        }
        else if( node.next == null ) // last node
        {
            node.previous.next = null;
            last = node.previous;
        }
        else if( node.previous == null ) // first node
        {
            node.next.previous = null;
            first = node.next;
        }
        else // somewhere in middle
        {
            node.previous.next = node.next;
            node.next.previous = node.previous;
        }
        
    }
    
    
    private void insertInList(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode, int pos)
    {

        if( pos < 0 )
        {
            if( last == null )
            {
              last = parentNode;  
            }
            
            if( parentNode.previous == null )
            {
                first = node;
            }
            else
            {
                parentNode.previous.next = node ;
                node.previous = parentNode.previous;
            }
            
            node.next = parentNode;
            parentNode.previous = node;
        }
        else if( pos > 0 )
        {
            if( parentNode.next == null )
            {
                last = node;
            }
            else
            {
                parentNode.next.previous = node;
                node.next = parentNode.next;
            }
            node.previous = parentNode;
            parentNode.next = node;
         }
        
    }
    
    
    /**
     * {@inheritDoc}
     */
    public SingletonOrOrderedSet<V> remove( K key )
    {
        if( key == null )
        {
            throw new IllegalArgumentException( "key cannot be null" );
        }
        
        LinkedAvlMapNode<K,V> temp = null;
        
        List<LinkedAvlMapNode<K,V>> treePath = new ArrayList<LinkedAvlMapNode<K,V>>();
        
        treePath = find( key, root, treePath);
        
        if( treePath == null )
        {
            return null;
        }
        
        temp = treePath.remove( 0 );
       
        if( temp.isLeaf() && ( temp == root ) )
        {
            root = null;
        }
        else
        {
            balanceNodesAfterRemove( treePath, temp );
        }
        
        size--;
       return temp.value;
    }
    
    
    /**
     * {@inheritDoc}
     */
    public V remove( K key, V value )
    {
        if( key == null || value == null )
        {
            throw new IllegalArgumentException( "key or value cannot be null" );
        }
        
        LinkedAvlMapNode<K,V> temp = null;
        
        List<LinkedAvlMapNode<K,V>> treePath = new ArrayList<LinkedAvlMapNode<K,V>>();
        
        treePath = find( key, root, treePath);
        
        if( treePath == null )
        {
            return null;
        }
        
        temp = treePath.remove( 0 );

        // check if the value matches
        if( allowDuplicates )
        {
            if( temp.value.isOrderedSet() )
            {
                AvlTree<V> dupsTree = temp.value.getOrderedSet();
                V removedVal = dupsTree.remove( value );
                
                // if the removal is successful and the tree is not empty
                // we don't need to balance the tree, cause just one value
                // of the same key was removed
                // if the tree is empty because of the removal, the entire 
                // node will be removed which might require balancing, so we continue
                // further down in this function
                if( ( removedVal != null ) && ! dupsTree.isEmpty() )
                {
                    return removedVal;//no need to balance
                }
                 /* 
                  * if the value is not found then we should return
                  */
                else if ( removedVal == null ) 
                {
                    return removedVal;//no need to balance
                }
            }
            else
            {
                if( valueComparator.compare( temp.value.getSingleton(), value ) != 0 )
                {
                    return null;// no need to balance
                }
            }
        }

        if( temp.isLeaf() && ( temp == root ) )
        {
            if( allowDuplicates )
            {
                if( temp.value.isSingleton() || temp.value.getOrderedSet().isEmpty() )
                {
                    root = null;
                }
            }
            else // if dups are not allowed set root to null
            {
                root = null;
            }
       
            size--;
            return value;
        }

       balanceNodesAfterRemove( treePath, temp );

       size--;
       return value;
    }

    
    /**
     * changes the order of nodes after a delete operation and then 
     * balances the tree
     *
     * @param treePath the path traversed to find the node temp 
     * @param delNode the node to be deleted
     */
    private void balanceNodesAfterRemove( List<LinkedAvlMapNode<K,V>> treePath, LinkedAvlMapNode<K,V> delNode )
    {
        LinkedAvlMapNode<K,V> y = null;
        
        // remove from the doubly linked
        removeFromList( delNode );        

        if( delNode.isLeaf() )
        {
            if( !treePath.isEmpty() )
            {
                detachNodes( delNode, treePath.get( 0 ) );
            }
        }
        else
        {
            if( delNode.left != null )
            {
                List<LinkedAvlMapNode<K,V>> leftTreePath = findMax( delNode.left );
                y = leftTreePath.remove( 0 );
                
                if( leftTreePath.isEmpty() ) // y is the left child of root and y is a leaf
                {
                    detachNodes( y, delNode );
                }
                else
                {
                    detachNodes( y, leftTreePath.remove( 0 ) );
                }
                
                leftTreePath.addAll( treePath );
                treePath = leftTreePath;
                
                y.right = delNode.right; // assign the right here left will be assigned in replaceNode()

                if( delNode == root )
                {
                    y.left = delNode.left;
                    root = y;
                }
                else
                {
                    replaceNode( delNode, y, treePath.get( 0 ) );
                }
            }
            else if( delNode.right != null )
            {
                List<LinkedAvlMapNode<K,V>> rightTreePath = findMin( delNode.right );
                y = rightTreePath.remove( 0 );
                
                if( rightTreePath.isEmpty() )
                {
                    detachNodes( y, delNode ); // y is the right child of root and y is a leaf
                }
                else
                {
                    detachNodes( y, rightTreePath.remove( 0 ) );
                }
                
                rightTreePath.addAll( treePath );
                treePath = rightTreePath;
                
                y.right = delNode.right; // assign the right here left will be assigned in replaceNode()
                
                if( delNode == root )
                {
                    y.right = delNode.right;
                    root = y;
                }
                else
                {
                    replaceNode( delNode, y, treePath.get( 0 ) );
                }
            }
        }
       
       treePath.add( 0, y ); // y can be null but getBalance returns 0 so np
       balance( treePath );
    }
    
    
    /**
     * Balances the tree by visiting the nodes present in the List of nodes present in the
     * treePath parameter.<br><br>
     *
     * This really does the balancing if the height of the tree is greater than 2 and the<br> 
     * balance factor is greater than +1 or less than -1.<br><br>
     * For an excellent info please read the 
     * <a href="http://en.wikipedia.org/wiki/Avl_tree">Wikipedia article on AVL tree</a>.
     * 
     * @param treePath the traversed list of LinkedAvlMapNodes after performing an insert/delete operation.
     */
    private void balance( List<LinkedAvlMapNode<K,V>> treePath )
    {
        LinkedAvlMapNode<K,V> parentNode = null;
        
        int size = treePath.size();
        
        for( LinkedAvlMapNode<K,V> node: treePath )
        {
            int balFactor = getBalance( node );

            if( node != root )
            {
                if( treePath.indexOf( node ) < ( size - 1 ) )
                {
                    parentNode = treePath.get( treePath.indexOf( node ) + 1 );
                }
            }

            if( balFactor > 1 )
            {
                if( getBalance( node.right ) <= -1)
                {
                    //------rotate double-left--------
                    rotateSingleRight( node.right, node );
                    rotateSingleLeft( node, parentNode );
                }
                else // rotate single-left
                {
                   rotateSingleLeft( node, parentNode );
                }
            }
            else if( balFactor < -1 )
            {
                if( getBalance( node.left ) >= 1)
                {
                   //------rotate double-right--------
                   rotateSingleLeft( node.left, node ); 
                   rotateSingleRight( node, parentNode );
                }
                else
                {
                    rotateSingleRight( node, parentNode );
                }
            }
        }
    }
    

    /**
     * {@inheritDoc}
     */
    public boolean isEmpty()
    {
      return root == null;   
    }

    
    /**
     * {@inheritDoc}
     */
    //NOTE: This method is internally used by AVLTreeMarshaller
    public int getSize()
    {
        return size;
    }
    
    
    /**
     * Set the root of the tree.
     * 
     * Note : this method is used by the deserialization method
     *
     * @param root the root of the tree
     */
    /* no protection */ void setRoot( LinkedAvlMapNode<K,V> root )
    {
        this.root = root;
    }

    
    /**
     * Set the first element of the tree
     * 
     * Note : this method is used by the deserialization method
     *
     * @param first the first element to be added
     */
    /* no protection */  void setFirst( LinkedAvlMapNode<K,V> first )
    {
        this.first = first;
    }

    
    /**
     * Set the last element of the tree
     * 
     * Note : this method is used by the deserialization method
     *
     * @param last the last element to be added
     */
    /* no protection */  void setLast( LinkedAvlMapNode<K,V> last )
    {
        this.last = last;
    }


    /**
     * {@inheritDoc}
     */
    public LinkedAvlMapNode<K,V> getRoot()
    {
        return root;
    }
    
    
    /**
     * {@inheritDoc}
     */
    public List<K> getKeys()
    {
        List<K> keys = new ArrayList<K>();
        LinkedAvlMapNode<K,V> node = first;
        
        while( node != null )
        {
            keys.add( node.key );
            node = node.next;
        }
        
        return keys;
    }

    /**
     * {@inheritDoc}
     */
    public void printTree() 
    {
        if( isEmpty() )
        {
            System.out.println( "Tree is empty" );
            return;
        }
        
        getRoot().setDepth( 0 );

        System.out.println( getRoot() );
        
        visit( getRoot().getRight(), getRoot() );
        
        visit( getRoot().getLeft(), getRoot() );
    }
    

    /**
     * {@inheritDoc}
     */
    public LinkedAvlMapNode<K,V> getFirst()
    {
        return first;
    }

    
    /**
     * {@inheritDoc}
     */
    public LinkedAvlMapNode<K,V> getLast()
    {
        return last;
    }

    
    /**
     * Rotate the node left side once.
     *
     * @param node the LinkedAvlMapNode to be rotated
     * @param parentNode parent LinkedAvlMapNode of node
     */
    private void rotateSingleLeft(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode)
    {
        LinkedAvlMapNode<K,V> temp;
        //------rotate single-left--------
        
        temp = node.right;
        node.right = temp.left;
        temp.left = node;
        
        if( node == root )
        {
          root = temp;  
        }
        else if( parentNode != null )
        {
            if( parentNode.left == node )
            {
                parentNode.left = temp;
            }
            else if( parentNode.right == node )
            {
                parentNode.right = temp;
            }
        }
    }
    
    
    /**
     * Rotate the node right side once.
     *
     * @param node the LinkedAvlMapNode to be rotated
     * @param parentNode parent LinkedAvlMapNode of node
     */
    private void rotateSingleRight(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode)
    {
        LinkedAvlMapNode<K,V> temp;
        //------rotate single-right--------
        
        temp = node.left;
        node.left = temp.right;
        temp.right = node;
       
        if( node == root )
        {
          root = temp;  
        }
        else if( parentNode != null )
        {
            if( parentNode.left == node )
            {
                parentNode.left = temp;
            }
            else if( parentNode.right == node )
            {
                parentNode.right = temp;
            }
        }
        /*
         when the 'parentNode' param is null then the node under rotation is a child of ROOT.
         Most likely this condition executes when the root node is deleted and balancing is required.
         */
        else if( root != null )
        {
            if( root.left == node )
            {
                root.left = temp;
            }
            // no need to check for right node
        }
    }
        

    /**
     * Detach a LinkedAvlMapNode from its parent
     *
     * @param node the LinkedAvlMapNode to be detached
     * @param parentNode the parent LinkedAvlMapNode of the node
     */
    private void detachNodes(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode)
    {
        if( parentNode != null )
        {
            if( node == parentNode.left )
            {
                parentNode.left = node.left;
            }
            else if( node == parentNode.right )
            {
                parentNode.right = node.left;
            }
        }
    }


    /**
     * 
     * Replace a LinkedAvlMapNode to be removed with a new existing LinkedAvlMapNode 
     *
     * @param deleteNode the LinkedAvlMapNode to be deleted
     * @param replaceNode the LinkedAvlMapNode to replace the deleteNode
     * @param parentNode the parent LinkedAvlMapNode of deleteNode
     */
    private void replaceNode(LinkedAvlMapNode<K,V> deleteNode, LinkedAvlMapNode<K,V> replaceNode, LinkedAvlMapNode<K,V> parentNode)
    {
        if( parentNode != null )
        {
            replaceNode.left = deleteNode.left;
            
            if( deleteNode == parentNode.left )
            {
                parentNode.left = replaceNode;
            }
            else if( deleteNode == parentNode.right )
            {
                parentNode.right = replaceNode;
            }
        }
    }
    
    
    /**
     * 
     * Find a LinkedAvlMapNode with the given key value in the tree starting from the startNode.
     *
     * @param key the key to find
     * @param startNode starting node of a subtree/tree
     * @param path the list to be filled with traversed nodes
     * @return the list of traversed LinkedAvlMapNodes.
     */
    private List<LinkedAvlMapNode<K,V>> find( K key, LinkedAvlMapNode<K,V> startNode, List<LinkedAvlMapNode<K,V>> path )
    {
        int c;
        
        if( startNode == null )
        {
            return null;
        }
        
        path.add( 0, startNode );
        c = keyComparator.compare( key, startNode.key );
        
        if( c == 0 )
        {
            return path;
        }
        else if( c > 0 )
        {
            return find( key, startNode.right, path );
        }
        else if( c < 0 )
        {
            return find( key, startNode.left, path );
        }
        
        return null;
    }


    /**
     * {@inheritDoc}
     */
    public LinkedAvlMapNode<K,V> findGreater( K key )
    {
        LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root);

        if( result == null )
        {
            return null;
        }
        else if( keyComparator.compare( key, result.key ) < 0 )
        {
            return result;
        }

        return result.next;
    }


    /**
     * {@inheritDoc}
     */
    public LinkedAvlMapNode<K,V> findGreaterOrEqual( K key )
    {
        LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root);

        if( result == null )
        {
            return null;
        }
        else if( keyComparator.compare( key, result.key ) <= 0 )
        {
            return result;
        }

        return result.next;
    }


    /**
     * {@inheritDoc}
     */
    public LinkedAvlMapNode<K,V> findLess( K key )
    {
        LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root);

        if( result == null )
        {
            return null;
        }
        else if( keyComparator.compare( key, result.key ) > 0 )
        {
            return result;
        }

        return result.previous;
    }


    /**
     * {@inheritDoc}
     */
    public LinkedAvlMapNode<K,V> findLessOrEqual( K key )
    {
        LinkedAvlMapNode<K,V> result = fetchNonNullNode( key, root, root);

        if( result == null )
        {
            return null;
        }
        else if( keyComparator.compare( key, result.key ) >= 0 )
        {
            return result;
        }

        return result.previous;
    }


    /*
     * This method returns the last visited non-null node in case if the node with the given key
     * is not present. This method should not be used as general purpose lookup method.
     * This is written to assist the findGreater, findLess methods. 
     */
    private LinkedAvlMapNode<K,V> fetchNonNullNode( K key, LinkedAvlMapNode<K,V> startNode, LinkedAvlMapNode<K,V> parent )
    {
        
        if( startNode == null )
        {
            return parent;
        }
        
        int c = keyComparator.compare( key, startNode.key );
        
        parent = startNode;

        if( c > 0 )
        {
            return fetchNonNullNode( key, startNode.right, parent );
        }
        else if( c < 0 )
        {
            return fetchNonNullNode( key, startNode.left, parent );
        }
        
        return startNode;
    }
    
    /**
     * {@inheritDoc}
     */
    public LinkedAvlMapNode<K,V> find( K key )
    {
        return find( key, root);
    }
    

    /**
     * {@inheritDoc}
     */
    public LinkedAvlMapNode<K,V> find( K key, V value )
    {
        if( key == null || value == null )
        {
            return null;
        }
        
        LinkedAvlMapNode<K,V> node = find( key, root );
        
        if( node == null )
        {
            return null;
        }
        
        if( node.value.isOrderedSet() )
        {
            AvlTree<V> dupsTree = node.value.getOrderedSet();
            
            if( dupsTree.find( value ) == null )
            {
                return null;
            }
        }
        else
        {
            if( valueComparator.compare( node.value.getSingleton(), value ) != 0 )
            {
                return null;
            }
        }

        return node;
    }

    
    private LinkedAvlMapNode<K,V> find( K key, LinkedAvlMapNode<K,V> startNode)
    {
        int c;
        
        if( startNode == null )
        {
            return null;
        }
        
        c = keyComparator.compare( key, startNode.key );
        
        if( c > 0 )
        {
            startNode.isLeft = false;
            return find( key, startNode.right );
        }
        else if( c < 0 )
        {
            startNode.isLeft = true;
            return find( key, startNode.left );
        }
        
        return startNode;
    }
    
    
    /**
     * Find the LinkedAvlMapNode having the max key value in the tree starting from the startNode.
     *
     * @param startNode starting node of a subtree/tree
     * @return the list of traversed LinkedAvlMapNodes.
     */
    private List<LinkedAvlMapNode<K,V>> findMax( LinkedAvlMapNode<K,V> startNode )
    {
        LinkedAvlMapNode<K,V> x = startNode;
        LinkedAvlMapNode<K,V> y = null;
        List<LinkedAvlMapNode<K,V>> path;
        
        if( x == null )
        {
            return null;
        }
        
        while( x.right != null )
        {
            x.isLeft = false;
            y = x;
            x = x.right;
        }
        
        path = new ArrayList<LinkedAvlMapNode<K,V>>(2);
        path.add( x );
        
        if ( y != null )
        {
          path.add( y );  
        }
        
        return path;
    }

    
    /**
     * Find the LinkedAvlMapNode having the min key value in the tree starting from the startNode.
     *
     * @param startNode starting node of a subtree/tree
     * @return the list of traversed LinkedAvlMapNodes.
     */
    private List<LinkedAvlMapNode<K,V>> findMin( LinkedAvlMapNode<K,V> startNode )
    {
        LinkedAvlMapNode<K,V> x = startNode;
        LinkedAvlMapNode<K,V> y = null;
        List<LinkedAvlMapNode<K,V>> path;
       
        if( x == null )
        {
            return null;
        }
       
        while( x.left != null )
        {
            x.isLeft = true;
            y = x;
            x = x.left;
        }
        
        path = new ArrayList<LinkedAvlMapNode<K,V>>(2);
        path.add( x );
        
        if ( y != null )
        {
          path.add( y );  
        }
        
        return path;
    }
   
    
    /**
     * Get balance-factor of the given LinkedAvlMapNode.
     *
     * @param node a LinkedAvlMapNode 
     * @return balance-factor of the node
     */
    private int getBalance( LinkedAvlMapNode<K,V> node )
    {
        if( node == null)
        {
            return 0;
        }
        
        return node.getBalance();
    }
    
    
    private void visit( LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode ) 
    {
        if( node == null )
        {
            return;
        }
        
        if( !node.isLeaf() )
        {
            node.setDepth( parentNode.getDepth() + 1 );
        }
        
        for( int i=0; i < parentNode.getDepth(); i++ )
        {
            System.out.print( "|  " );
        }

        String type = "";
        if( node == parentNode.left )
        {
            type = "L";
        }
        else if( node == parentNode.right )
        {
            type = "R";
        }
        
        System.out.println( "|--" + node + type );
        
        if ( node.getRight() != null )
        {
            visit( node.getRight(), node );
        }
        
        if( node.getLeft() != null )
        {
            visit( node.getLeft(), node );
        }
    }


    /**
     * {@inheritDoc}
     */
    public boolean isDupsAllowed()
    {
        return allowDuplicates;
    }
}
