/*
 * @(#)PathRegistry.java      0.9.0 04/26/2000 - 13:39:11
 *
 * Copyright (C) 2000,,2003 2002 Matt Albrecht
 * groboclown@users.sourceforge.net
 * http://groboutils.sourceforge.net
 *
 *  Permission is hereby granted, free of charge, to any person obtaining a
 *  copy of this software and associated documentation files (the "Software"),
 *  to deal in the Software without restriction, including without limitation
 *  the rights to use, copy, modify, merge, publish, distribute, sublicense,
 *  and/or sell copies of the Software, and to permit persons to whom the 
 *  Software is furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice shall be included in 
 *  all copies or substantial portions of the Software. 
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
 *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL 
 *  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
 *  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
 *  DEALINGS IN THE SOFTWARE.
 */

package net.sourceforge.groboutils.util.datastruct.v1;


import java.util.Vector;
import java.util.Enumeration;


/**
 * A path-tree registry for storing and retrieving objects.  Objects can
 * be registered at any point along the tree, but no more than one object
 * may be at each node.  A <code>null</code> entry at a point indicates
 * a non-registered node.
 * <P>
 * Synchronization needs to be hauled-over to increase speed and minimize
 * read interference with writes.
 *
 * @author    Matt Albrecht <a href="mailto:groboclown@users.sourceforge.net">groboclown@users.sourceforge.net</a>
 * @since     April 26, 2000 (0.9.0 Alpha)
 * @version   $Date: 2003/02/10 22:52:44 $
 */
public class PathRegistry
{
    //----------------------------
    // Public data
    
    //----------------------------
    // Private data

    class TreeNode
    {
        Object value;
        boolean isRecursive; // true = no children, but uses children
        boolean isCaseSensitive;
        String nodeName;
        TreeNode nextSibling;
        TreeNode firstChild;
    }
    
    
    private char m_separator;
    private boolean m_ignoreDuplicateSeparators;
    private TreeNode m_root; // doesn't contain anything in value, and has no name
    
    
    //----------------------------
    // constructors

    
    
    /**
     * Users must specify all variables without corresponding defaults.  This
     * prevents the class from implementing defaults, which have a habit of
     * randomly changing.
     */
    public PathRegistry( char separator, boolean ignoreDuplicateSeparators )
    {
        this.m_separator = separator;
        this.m_ignoreDuplicateSeparators = ignoreDuplicateSeparators;
        
        // root tree node:
        m_root = new TreeNode();
        //   ALWAYS:
        //   null nodename, not recursive, no siblings, empty fullname
        m_root.nodeName = null;
        m_root.nextSibling = null;
        m_root.isRecursive = false;
        m_root.isCaseSensitive = true;
        
        //   INITIALLY:
        //   no children
        m_root.firstChild = null;
    }

    
    //----------------------------
    // Public methods

    
    /**
     * Register the given object at the given path.  If the nodes leading
     * up to this end node do not exist, then they will be created.
     * <P>
     * For future use, we will need to re-do synchronization, so that
     * we synch on the tree node parent being worked on.
     *
     * @param path the path under which the given value will be registered.
     * @param value the object to store under the given path.
     * @param isRecursive set to <code>true</code> to notify the tree that
     *     this particular node also covers any sub-paths.  If this is
     *     <code>false</code>, then queries will only retrieve this
     *     node if the exact path is given.
     * @param isCaseSensitive set to <code>true</code> if the given node is
     *     to be case sensitive in searches.  If the nodes leading to this
     *     new node do not exist, then the newly created nodes will have the
     *     same case sensitivity as this end node.
     * @exception IllegalArgumentException thrown if the value is
     *    <code>null</code>, or the given path is not well formed.
     * @exception PathAlreadyRegisteredException thrown if the given path
     *    has already been registered to another object.
     */
    public synchronized void register( String path, Object value,
            boolean isRecursive, boolean isCaseSensitive )
            throws PathAlreadyRegisteredException
    {
        if (path == null || value == null)
        {
            throw new IllegalArgumentException(
                "nulls are not allowed for insertion");
        }
        
        Enumeration enum = parsePath( path );
        if (!enum.hasMoreElements())
        {
            throw new IllegalArgumentException(
                "path must have at least one element");
        }
        
        TreeNode parent = this.m_root;
        
        String current = (String)enum.nextElement();
//System.out.println("Full path = "+path);
        boolean addedNode = false;

        while (true)
        {
            addedNode = false;
//System.out.println("Path part = "+current);
            TreeNode nextNode = findSibling( parent, current );
            if (nextNode == null)
            {
//System.out.println(" -- needs to be added");
                // add the node
                nextNode = new TreeNode();
                nextNode.value = null;
                nextNode.nodeName = current;
                nextNode.isCaseSensitive = isCaseSensitive;
                nextNode.isRecursive = false;
                nextNode.nextSibling = null;
                nextNode.firstChild = null;
                addChildNode( parent, nextNode );
                addedNode = true;
            }
            else
            if (nextNode.isRecursive)
            {
//System.out.println("Node "+current+" is recursive - can't add under it");
                // can't add to a recursive path
                throw new PathAlreadyRegisteredException( path );
            }

            if (enum.hasMoreElements())
            {
                current = (String)enum.nextElement();
            }
            else
            {
//System.out.println(" -- On the last node, and it matches node "+nextNode.nodeName );
                // last node
                if (!addedNode)
                {
                    throw new PathAlreadyRegisteredException( path );
                }
                nextNode.value = value;
                nextNode.isRecursive = isRecursive;
                
                return;
            }
            
            parent = nextNode;
        }
    }
    
    
    /**
     * Remove the object at the given path.  It only removes nodes
     * if the node no longer has any children.  The siblings
     * are automatically compressed.
     * <P>
     * For future use, we will need to re-do synchronization, so that
     * we synch on the tree node parent being worked on.
     *
     * @param path the tree path specifying which node to remove.  If the
     *     given node does not exist, or has not been registered, then a
     *     NotRegisteredException is thrown.
     * @exception IllegalArgumentException thrown if the value is
     *    <code>null</code>, or the given path is not well formed.
     * @exception NoRegisteredComponentException thrown if the given path node
     *     has not yet been registered.
     */
    public synchronized void remove( String path )
            throws NoRegisteredComponentException
    {
        if (path.charAt( path.length()-1 ) != this.m_separator)
        {
            path += this.m_separator;
        }
        Enumeration enum = parsePath( path );
        if (!enum.hasMoreElements())
        {
            throw new IllegalArgumentException(
                "path must have at least one element");
        }

        TreeNode parent = this.m_root;
        String current = (String)enum.nextElement();
        
        while (true)
        {
            TreeNode nextNode = findSibling( parent, current );
            if (nextNode == null)
            {
                // node doesn't exist
                throw new NoRegisteredComponentException( path );
            }

            if (enum.hasMoreElements())
            {
                current = (String)enum.nextElement();
            }
            else
            {
                // last node
                if (nextNode.value == null)
                {
                    // node doesn't exist
                    throw new NoRegisteredComponentException( path );
                }
                
                nextNode.value = null;
                if (nextNode.isRecursive || nextNode.firstChild == null)
                {
                    removeChild( parent, nextNode );
                }
                
                return;
            }
            
            parent = nextNode;
        }
    }

    
    /**
     * Retrieve the object stored at the given path.
     * <P>
     * Need to synchronize better so that reads don't collide with writes,
     * but reads can be done asynchronously.
     *
     * @param path the path which specifies the object to retrieve.
     * @return the object which was registered at the given path, or
     *    <code>null</code> if nothing is registered there.
     */
    public synchronized Object get( String path )
    {
        TreeNode node = findNode( path );
        if (node == null) return null;
        
        return node.value;
    }
    
    
    
    //----------------------------
    // Protected methods
    
    
    /**
     * Parses the given path into node elements.  The last item in the list is
     * ignored, unless the path ends with the path separator character.
     */
    protected Enumeration parsePath( String path )
    {
        if (path == null) return null;

        if (path.charAt( path.length()-1 ) != this.m_separator)
        {
            path += this.m_separator;
        }
        
        char cpath[] = path.toCharArray();
        int len = cpath.length;
        Vector v = new Vector( len >> 2 );
        int start = 0, next, count;
        
        while (start < len)
        {
            count = 0;
            for (next = start;
                next < len && cpath[ next ] != this.m_separator;
                next++)
            {
                count++;
            }
            // ignore last element in list
            if (next < len)
            {
                v.addElement( new String( cpath, start, count ) );
            }
            start = next+1;
            if (this.m_ignoreDuplicateSeparators)
            {
                for (; start < len && cpath[ start ] == this.m_separator;
                    start++ )
                {
                    // do nothing
                }
            }
        }
        
        return v.elements();
    }
    
    
    
    /**
     * Find the sibling with the given node name part.
     */
    protected TreeNode findSibling( TreeNode parent, String namePart )
    {
//System.out.println("findSibling: name to find = "+namePart);
        if (parent == null || namePart == null) return null;
        TreeNode child = parent.firstChild;
        while (child != null)
        {
//System.out.println(" - child name = "+child.nodeName+"; is case sensitive? "+
//child.isCaseSensitive);
            if (child.isCaseSensitive)
            {
                if (namePart.equals( child.nodeName ))
                {
                    return child;
                }
            }
            else
            {
                if (namePart.equalsIgnoreCase( child.nodeName ))
                {
                    return child;
                }
            }
            child = child.nextSibling;
        }
        return null;
    }
    
    
    /**
     * Find the node with the given name.
     */
    protected TreeNode findNode( String name )
    {
//System.out.println("findNode( "+name+" )");
        Enumeration enum = parsePath( name );
        
        TreeNode parent = this.m_root;
        while (parent != null)
        {
            if (parent.isRecursive || !enum.hasMoreElements())
            {
//System.out.println(" -- found node");
                return parent;
            }
            String partName = (String)enum.nextElement();
//System.out.println(" -- checking part "+partName);
            parent = findSibling( parent, partName );
//System.out.println(" -- parent = "+parent);
        }
        return null;
    }
    
    /**
     * Find the sibling with the given node name part.
     */
    protected void removeChild( TreeNode parent, TreeNode child )
    {
        if (parent == null || child == null) return;
        TreeNode sibling = parent.firstChild;
        if (child.isCaseSensitive)
        {
            if (child.nodeName.equals( sibling.nodeName ))
            {
                parent.firstChild = child.nextSibling;
                return;
            }
        }
        else
        {
            if (child.nodeName.equalsIgnoreCase( child.nodeName ))
            {
                parent.firstChild = child.nextSibling;
                return;
            }
        }
        
        while (sibling.nextSibling != null)
        {
            if (child.isCaseSensitive)
            {
                if (child.nodeName.equals( sibling.nextSibling.nodeName ))
                {
                    sibling.nextSibling = child.nextSibling;
                    return;
                }
            }
            else
            {
                if (child.nodeName.equalsIgnoreCase(
                    sibling.nextSibling.nodeName ))
                {
                    sibling.nextSibling = child.nextSibling;
                    return;
                }
            }
            sibling = sibling.nextSibling;
        }
        
        // couldn't find child
        return;
    }
    
    
    /**
     * Child must already be initialized correctly.
     */
    protected void addChildNode( TreeNode parent, TreeNode child )
            throws PathAlreadyRegisteredException
    {
        if (parent == null || child == null)
        {
            throw new IllegalArgumentException( "parent or child is null" );
        }
        
        TreeNode sibling = parent.firstChild;

        if (sibling == null)
        {
            parent.firstChild = child;
            return;
        }
        

        // loop through all siblings, checking if we can insert the child
        // for each member, then when the end of the list is found, we
        // add the child to it.
        while (true)
        {
            // check if we can insert new child
            if (sibling.isCaseSensitive || child.isCaseSensitive)
            {
                if (sibling.nodeName.equals( child.nodeName ))
                {
                    throw new PathAlreadyRegisteredException();
                }
            }
            if (sibling.nextSibling == null)
            {
                sibling.nextSibling = child;
                return;
            }
            sibling = sibling.nextSibling;
        }
        
        // this point should never be reached.
//        throw new IllegalStateException( "point never reached" );
    }
    
    //----------------------------
    // Private methods
}