/*
 * ====================================================================
 * The Apache Software License, Version 1.1
 *
 * Copyright (c) 2001 The Apache Software Foundation.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in
 * the documentation and/or other materials provided with the
 * distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 * if any, must include the following acknowledgment:
 * "This product includes software developed by the
 * Apache Software Foundation (http://www.apache.org/)."
 * Alternately, this acknowledgment may appear in the software itself,
 * if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Apache" and "Apache Software Foundation" and
 * "Apache JMeter" must not be used to endorse or promote products
 * derived from this software without prior written permission. For
 * written permission, please contact apache@apache.org.
 *
 * 5. Products derived from this software may not be called "Apache",
 * "Apache JMeter", nor may "Apache" appear in their name, without
 * prior written permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */
 


package org.apache.jorphan.collections;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import junit.framework.TestCase;

import org.apache.log.Logger;
import org.apache.jorphan.logging.LoggingManager;
/**********************************************************************
This class is used to create a tree structure of objects.  Each element in the tree
is also a key to the next node down in the tree.  It provides many ways to add objects and 
branches, as well as many ways to retrieve. 
<p>
HashTree implements the Map interface for convenience reasons.  The main difference between 
a Map and a HashTree is that the HashTree organizes the data into a recursive tree structure,
and provides the means to manipulate that structure.
<p>
Of special interest is the 
{@link traverse(HashTreeTraverser)} method, which provides an expedient way to 
traverse any HashTree by implementing the
{@link HashTreeTraverser} interface in order to perform some operation on the tree, or to extract
information from the tree.

@author Michael Stover (mstover1 at apache.org)
@see HashTreeTraverser
@see SearchByClass
***********************************************************************/
public class HashTree implements Serializable,Map
{
	private static Logger log = LoggingManager.getLoggerFor("jorphan.collections");
	/**
	 * Creates an empty new HashTree
	 */
	public HashTree()
	{
		data = new HashMap();
	}
	/**
	 * Creates a new HashTree and adds the given object as a top-level node.
	 * @param key
	 */
	public HashTree(Object key)
	{
		data = new HashMap();
		data.put(key, new HashTree());
	}
	/**
	 * The Map given must also be a HashTree, otherwise an UnsupportedOperationException
	 * is thrown.  If it is a HashTree, this is like calling the add(HashTree) method.
	 * @see add(HashTree)
	 * @see java.util.Map#putAll(Map)
	 */
	public void putAll(Map map)
	{
		if(map instanceof HashTree)
		{
			this.add((HashTree)map);
		}
		else
		{
			throw new UnsupportedOperationException("can only putAll other HashTree objects");
		}
	}
	
	/**
	 * Exists to satisfy the Map interface.  
	 * @see java.util.Map#entrySet()
	 */
	public Set entrySet()
	{
		return data.entrySet();
	}
	
	/**
	 * Implemented as required by the Map interface, but is not very useful here. All
	 * 'values' in a HashTree are HashTree's themselves. 
	 * @param obj Object to be tested as a value.
	 * @return True if the HashTree contains the value, false otherwise.
	 * @see java.util.Map#containsValue(Object)
	 */
	public boolean containsValue(Object value)
	{
		return data.containsValue(value);
	}
	
	/**
	 * This is the same as calling HashTree.add(key,value).
	 * @see java.util.Map#put(Object, Object)
	 */
	public Object put(Object key,Object value)
	{
		Object previous = data.get(key);
		add(key,value);
		return previous;
	}
	
	/**
	 * Clears the HashTree of all contents.
	 * @see java.util.Map#clear()
	 */
	public void clear()
	{
		data.clear();
	}
	
	/**
	 * Returns a collection of all the sub-trees of the current tree.
	 * @see java.util.Map#values()
	 */
	public Collection values()
	{
		return data.values();
	}
	
	/****************************************
	 * Adds a key as a node at the current level and then adds the
	 * given HashTree to that new node.
	 *
	 *@param key      Key to create in this tree
	 *@param subTree  Sub tree to add to the node created for the first argument.
	 ***************************************/
	public void add(Object key,HashTree subTree)
	{
		add(key);
		getTree(key).add(subTree);
	}
	
	/**
	 * Adds all the nodes and branches of the given tree to this tree.  Is like merging
	 * two trees.  Duplicates are ignored.
	 * @param newTree
	 */
	public void add(HashTree newTree)
	{
		Iterator iter = newTree.list().iterator();
		while(iter.hasNext())
		{
			Object item = iter.next();
			add(item);
			getTree(item).add(newTree.getTree(item));
		}
	}
	/**
	 * Creates a new HashTree and adds all the objects in the given collection as top-level
	 * nodes in the tree.
	 * @param keys A collection of objects to be added to the created HashTree.
	 */
	public HashTree(Collection keys)
	{
		data = new HashMap();
		Iterator it = keys.iterator();
		while (it.hasNext())
			data.put(it.next(), new HashTree());
	}
	/**
	 * Creates a new HashTree and adds all the objects in the given array as top-level
	 * nodes in the tree.
	 * @param keys
	 */
	public HashTree(Object[] keys)
	{
		data = new HashMap();
		for (int x = 0; x < keys.length; x++)
			data.put(keys[x], new HashTree());
	}
	/************************************************************
	  If the HashTree contains the given object as a key at the top level, then a
	  true result is returned, otherwise false.
	@param obj Object to be tested as a key.
	@return True if the HashTree contains the key, false otherwise.
	@see java.util.Map#containsKey()
	***************************************************************/
	public boolean containsKey(Object o)
	{
		return data.containsKey(o);
	}
	/*****************************************************************
	  If the HashTree is empty, true is returned, false otherwise.
	@return True if HashTree is empty, false otherwise.
	***************************************************************/
	public boolean isEmpty()
	{
		return data.isEmpty();
	}
	/************************************************************************
	  Sets a key and it's value in the HashTree.  It actually sets up a key, and then
	  creates a node for the key and sets the value to the new node, as a key.  Any
	  previous nodes that existed under the given key are lost.
	@param key Key to be set up.
	@param value Value to be set up as a key in the secondary node.
	*************************************************************************/
	public void set(Object key, Object value)
	{
		data.put(key, createNewTree(value));
	}
	/********************************************************************
	 Sets a key into the current tree and assigns it a HashTree as its subtree.  Any
	 previous entries under the given key are removed.
	@param key Key to be set up.
	@param tree HashTree that the key maps to.
	**************************************************************************/
	public void set(Object key, HashTree t)
	{
		data.put(key, t);
	}
	/************************************************************************
	Sets a key and it's values in the HashTree.  It sets up a key in the current node, and
	then creates a node for that key, and sets all the values in the array as keys in
	 the new node.  Any keys previously held under the given key are lost.
	@param key Key to be set up.
	@param values Array of objects to be added as keys in the secondary node.
	********************************************************************/
	public void set(Object key, Object[] values)
	{
		data.put(key, createNewTree(Arrays.asList(values)));
	}
	/********************************************************************
	 Sets a key and its values in the HashTree.  It sets up a key in the current node, and
	 then creates a node for that key, and set all the values in the array as keys in
	 the new node.  Any keys previously held under the given key are removed.
	@param key Key to be set up.
	@param values Collection of objects to be added as keys in the secondary node.
	**************************************************************************/
	public void set(Object key, Collection values)
	{
		data.put(key, createNewTree(values));
	}
	/********************************************************************
	  Sets a series of keys into the HashTree.  It sets up the first object in the
	  key array as a key in the current node, recurses into the next HashTree node through
	  that key and adds the second object in the array.  Continues recursing in this
	  manner until the end of the first array is reached, at which point all the
	  values of the second array are set as keys to the bottom-most node.  All previous
	  keys of that bottom-most node are removed.
	@param treePath Array of keys to put into HashTree.
	@param values Array of values to be added as keys to bottom-most node.
	********************************************************************/
	public void set(Object[] treePath, Object[] values)
	{
		if(treePath != null && values != null)
		{
			set(Arrays.asList(treePath),Arrays.asList(values));
		}
	}
	/********************************************************************
	  Sets a series of keys into the HashTree.  It sets up the first object in the
	  key array as a key in the current node, recurses into the next HashTree node through
	  that key and adds the second object in the array.  Continues recursing in this
	  manner until the end of the first array is reached, at which point all the
	  values of the Collection of values are set as keys to the bottom-most node.  Any
	  keys previously held by the bottom-most node are lost.
	@param key Array of keys to put into HashTree.
	@param values Collection of values to be added as keys to bottom-most node.
	********************************************************************/
	public void set(Object[] treePath, Collection values)
	{
		if(treePath != null)
		{
			set(Arrays.asList(treePath),values);
		}
	}
	/********************************************************************
	  Sets a series of keys into the HashTree.  It sets up the first object in the
	  key list as a key in the current node, recurses into the next HashTree node through
	  that key and adds the second object in the list.  Continues recursing in this
	  manner until the end of the first list is reached, at which point all the
	  values of the array of values are set as keys to the bottom-most node.  Any
	  previously existing keys of that bottom node are removed.
	@param treePath List of keys to put into HashTree.
	@param values Array of values to be added as keys to bottom-most node.
	********************************************************************/
	public void set(Collection treePath, Object[] values)
	{
		HashTree tree = addTreePath(treePath);
		tree.set(Arrays.asList(values));
	}
	/****************************************
	 * Sets the nodes of the current tree to be the objects of the given collection.  
	 * Any nodes previously in the tree are removed.
	 *
	 *@param values  Collection of objects to set as nodes.
	 ***************************************/
	public void set(Collection values)
	{
		Iterator iter = this.list().iterator();
		while(iter.hasNext())
		{
			this.remove(iter.next());
		}
		this.add(values);
	}
	/********************************************************************
	  Sets a series of keys into the HashTree.  It sets up the first object in the
	  key list as a key in the current node, recurses into the next HashTree node through
	  that key and adds the second object in the list.  Continues recursing in this
	  manner until the end of the first list is reached, at which point all the
	  values of the Collection of values are set as keys to the bottom-most node.  Any
	  previously existing keys of that bottom node are lost.
	@param key List of keys to put into HashTree.
	@param values Collection of values to be added as keys to bottom-most node.
	********************************************************************/
	public void set(Collection treePath, Collection values)
	{
		HashTree tree = addTreePath(treePath);
		tree.set(values);
	}
	/*********************************************************************
	Adds an key into the HashTree at the current level.
	@param key Key to be added to HashTree.
	*****************************************************************/
	public void add(Object key)
	{
		if (!data.containsKey(key))
			data.put(key, createNewTree());
	}
	/*******************************************************************
	Adds all the given objects as nodes at the current level.
	@param keys Array of Keys to be added to HashTree.
	*******************************************************************/
	public void add(Object[] keys)
	{
		for (int x = 0; x < keys.length; x++)
			add(keys[x]);
	}
	/*******************************************************************
	Adds a bunch of keys into the HashTree at the current level.
	@param keys Collection of Keys to be added to HashTree.
	*******************************************************************/
	public void add(Collection keys)
	{
		Iterator it = keys.iterator();
		while (it.hasNext())
			add(it.next());
	}
	/************************************************************************
	* Adds a key and it's value in the HashTree.  The first argument becomes a node 
	* at the current level, and the second argument becomes a node of it.
	@param key Key to be added.
	@param value Value to be added as a key in the secondary node.
	*************************************************************************/
	public void add(Object key, Object value)
	{
		add(key);
		getTree(key).add(value);
	}
	/************************************************************************
	Adds a key and it's values in the HashTree.  The first argument becomes a 
	node at the current level, and adds all the values in the array to
	 the new node.
	@param key Key to be added.
	@param values Array of objects to be added as keys in the secondary node.
	********************************************************************/
	public void add(Object key, Object[] values)
	{
		add(key);
		getTree(key).add(values);
	}
	/************************************************************************
	Adds a key as a node at the current level and then adds all the objects in the
	second argument as nodes of the new node. 
	@param key Key to be added.
	@param values Collection of objects to be added as keys in the secondary node.
	********************************************************************/
	public void add(Object key, Collection values)
	{
		add(key);
		getTree(key).add(values);
	}
	/********************************************************************
	* Adds a series of nodes into the HashTree using the given path.  The
	* first argument is an array that represents a path to a specific node in the
	* tree.  If the path doesn't already exist, it is created (the objects are added 
	* along the way).  At the path, all the objects in the second argument are added
	* as nodes.
	@param treePath An array of objects representing a path.
	@param values Array of values to be added as keys to bottom-most node.
	********************************************************************/
	public void add(Object[] treePath, Object[] values)
	{
		if(treePath != null)
		{
			add(Arrays.asList(treePath), Arrays.asList(values));
		}
	}
	/********************************************************************
	* Adds a series of nodes into the HashTree using the given path.  The
	* first argument is an array that represents a path to a specific node in the
	* tree.  If the path doesn't already exist, it is created (the objects are added 
	* along the way).  At the path, all the objects in the second argument are added
	* as nodes.
	@param treePath An array of objects representing a path.
	@param values Collection of values to be added as keys to bottom-most node.
	********************************************************************/
	public void add(Object[] treePath, Collection values)
	{
		if(treePath != null)
		{
			add(Arrays.asList(treePath), values);
		}
	}
	/********************************************************************
	*  Adds a series of nodes into the HashTree using the given path.  The
	* first argument is a List that represents a path to a specific node in the
	* tree.  If the path doesn't already exist, it is created (the objects are added 
	* along the way).  At the path, all the objects in the second argument are added
	* as nodes.
	@param treePath A list of objects representing a path.
	@param values Array of values to be added as keys to bottom-most node.
	********************************************************************/
	public void add(Collection treePath, Object[] values)
	{
		HashTree tree = addTreePath(treePath);
		tree.add(Arrays.asList(values));
	}
	/****************************************
	 * Adds a series of nodes into the HashTree using the given path.  The
	* first argument is a List that represents a path to a specific node in the
	* tree.  If the path doesn't already exist, it is created (the objects are added 
	* along the way).  At the path, the object in the second argument is added
	* as a node.
	 *
	 *@param key     A list of objects representing a path.
	 *@param value   Object to add as a node to bottom-most node.
	 ***************************************/
	public void add(Collection treePath, Object value)
	{
		HashTree tree = addTreePath(treePath);
		tree.add(value);
	}
	/********************************************************************
	* Adds a series of nodes into the HashTree using the given path.  The
	* first argument is a SortedSet that represents a path to a specific node in the
	* tree.  If the path doesn't already exist, it is created (the objects are added 
	* along the way).  At the path, all the objects in the second argument are added
	* as nodes.
	@param treePath A SortedSet of objects representing a path.
	@param values Collection of values to be added as keys to bottom-most node.
	********************************************************************/
	public void add(Collection treePath, Collection values)
	{
		HashTree tree = addTreePath(treePath);
		tree.add(values);
	}

	protected HashTree addTreePath(Collection treePath)
	{
		HashTree tree = this;
		Iterator iter = treePath.iterator();
		while(iter.hasNext())
		{
			Object temp = iter.next();
			tree.add(temp);
			tree = tree.getTree(temp);
		}
		return tree;
	}
	/*********************************************************************
	Gets the HashTree mapped to the given key.
	@param key Key used to find appropriate HashTree()
	********************************************************************/
	public HashTree getTree(Object key)
	{
		return (HashTree) data.get(key);
	}
	
	/**
	 * Returns the HashTree object associated with the given key.  Same as calling
	 * getTree(key).
	 * @see org.apache.jorphan.collections.HashTree#getTree(Object)
	 * @see java.util.Map#get(Object)
	 */
	public Object get(Object key)
	{
		return getTree(key);
	}
	/*************************************************************
	Gets the HashTree object mapped to the last key in the array by recursing through
	the HashTree structure one key at a time.
	@param treePath Array of keys.
	@return HashTree at the end of the recursion.
	**************************************************************/
	public HashTree getTree(Object[] treePath)
	{
		if(treePath != null)
		{
			return getTree(Arrays.asList(treePath));
		}
		else
		{
			return this;
		}
	}
	
	/**
	 * Create a clone of this HashTree.  This is not a deep clone (ie, the contents of 
	 * the tree are not cloned).
	 * @see java.lang.Object#clone()
	 */
	public Object clone()
	{
		HashTree newTree = new HashTree();
		newTree.data = (Map)((HashMap)data).clone();
		return newTree;
	}
	
	/**
	 * Creates a new tree.  This method exists to allow inheriting classes to generate the
	 * appropriate types of nodes.  For instance, when a node is added, it's value is a HashTree.
	 * Rather than directly calling the HashTree() constructor, the createNewTree() method is
	 * called.  Inheriting classes should override these methods and create the appropriate
	 * subclass of HashTree.
	 * @return HashTree
	 */
	protected HashTree createNewTree()
	{
		return new HashTree();
	}
	
	/**
	 * Creates a new tree.  This method exists to allow inheriting classes to generate the
	 * appropriate types of nodes.  For instance, when a node is added, it's value is a HashTree.
	 * Rather than directly calling the HashTree() constructor, the createNewTree() method is
	 * called.  Inheriting classes should override these methods and create the appropriate
	 * subclass of HashTree.
	 * @return HashTree
	 */
	protected HashTree createNewTree(Object key)
	{
		return new HashTree(key);
	}
	
	/**
	 * Creates a new tree.  This method exists to allow inheriting classes to generate the
	 * appropriate types of nodes.  For instance, when a node is added, it's value is a HashTree.
	 * Rather than directly calling the HashTree() constructor, the createNewTree() method is
	 * called.  Inheriting classes should override these methods and create the appropriate
	 * subclass of HashTree.
	 * @return HashTree
	 */
	protected HashTree createNewTree(Collection values)
	{
		return new HashTree(values);
	}
	
	/*************************************************************
	Gets the HashTree object mapped to the last key in the SortedSet by recursing through
	the HashTree structure one key at a time.
	@param treePath SortedSet of keys.
	@return HashTree at the end of the recursion.
	**************************************************************/
	public HashTree getTree(Collection treePath)
	{
		return getTreePath(treePath);
	}
	/****************************************************************
	Gets a Collection of all keys in the current HashTree node.  If the HashTree represented
	a file system, this would be like getting a collection of all the files in the current
	folder.
	@return Set of all keys in this HashTree.
	*****************************************************************/
	public Collection list()
	{
		return data.keySet();
	}
	/***************************************************************
	  Gets a Set of all keys in the HashTree mapped to the given key of the
	  current HashTree object (in other words, one level down.  If the HashTree
	  represented a file system, this would like getting a list of all files in
	  a sub-directory (of the current directory) specified by the key argument
	@param key Key used to find HashTree to get list of.
	@return Set of all keys in found HashTree.
	***************************************************************/
	public Collection list(Object key)
	{
		HashTree temp = (HashTree) data.get(key);
		if (temp != null)
			return temp.list();
		else
			return null;
	}
	/**
	 * Removes the entire branch specified by the given key.
	 * @see java.util.Map#remove(Object)
	 */
	public Object remove(Object key)
	{
		return data.remove(key);
	}
	/*************************************************************
	Recurses down into the HashTree stucture using each subsequent key in the
	array of keys, and returns the Set of keys of the HashTree object at the
	end of the recursion.  If the HashTree represented a file system, this would
	be like getting a list of all the files in a directory specified by
	the treePath, relative from the current directory.
	@param treePath Array of keys used to recurse into HashTree structure.
	@return Set of all keys found in end HashTree.
	**************************************************************/
	public Collection list(Object[] treePath)
	{
		if(treePath != null)
		{
			return list(Arrays.asList(treePath));
		}
		else
		{
			return list();
		}
	}
	/*************************************************************
	Recurses down into the HashTree stucture using each subsequent key in the
	List of keys, and returns the Set of keys of the HashTree object at the
	end of the recursion.  If the HashTree represented a file system, this would
	be like getting a list of all the files in a directory specified by
	the treePath, relative from the current directory.
	@param treePath List of keys used to recurse into HashTree structure.
	@return Set of all keys found in end HashTree.
	**************************************************************/
	public Collection list(Collection treePath)
	{
		return getTreePath(treePath).list();
	}
	/****************************************
	 * Finds the given current key, and replaces it with the given new key.  Any 
	 * tree structure found under the original key is moved to the new key.
	 *
	 *@param currentKey  !ToDo (Parameter description)
	 *@param newKey      !ToDo (Parameter description)
	 ***************************************/
	public void replace(Object currentKey, Object newKey)
	{
		HashTree tree = getTree(currentKey);
		data.remove(currentKey);
		data.put(newKey, tree);
	}
	/****************************************************************
	Gets an array of all keys in the current HashTree node.  If the HashTree represented
	a file system, this would be like getting an array of all the files in the current
	folder.
	@return Array of all keys in this HashTree.
	*****************************************************************/
	public Object[] getArray()
	{
		return data.keySet().toArray();
	}
	/***************************************************************
	  Gets an array of all keys in the HashTree mapped to the given key of the
	  current HashTree object (in other words, one level down).  If the HashTree
	  represented a file system, this would like getting a list of all files in
	  a sub-directory (of the current directory) specified by the key argument
	@param key Key used to find HashTree to get list of.
	@return Array of all keys in found HashTree.
	***************************************************************/
	public Object[] getArray(Object key)
	{
		return getTree(key).getArray();
	}
	/*************************************************************
	Recurses down into the HashTree stucture using each subsequent key in the
	array of keys, and returns an array of keys of the HashTree object at the
	end of the recursion.  If the HashTree represented a file system, this would
	be like getting a list of all the files in a directory specified by
	the treePath, relative from the current directory.
	@param keys Array of keys used to recurse into HashTree structure.
	@return Array of all keys found in end HashTree.
	**************************************************************/
	public Object[] getArray(Object[] treePath)
	{
		if(treePath != null)
		{
			return getArray(Arrays.asList(treePath));
		}
		else
		{
			return getArray();
		}
	}
	/*************************************************************
	Recurses down into the HashTree stucture using each subsequent key in the
	treePath argument, and returns an array of keys of the HashTree object at the
	end of the recursion.  If the HashTree represented a file system, this would
	be like getting a list of all the files in a directory specified by
	the treePath, relative from the current directory.
	@param treePath List of keys used to recurse into HashTree structure.
	@return Array of all keys found in end HashTree.
	**************************************************************/
	public Object[] getArray(Collection treePath)
	{
		HashTree tree = getTreePath(treePath);
		return tree.getArray();
	}
	protected HashTree getTreePath(Collection treePath)
	{
		HashTree tree = this;
		Iterator iter = treePath.iterator();
		while(iter.hasNext())
		{
			Object temp = iter.next();
			log.debug("Getting tree for " +temp);
			tree = tree.getTree(temp);
		}
		return tree;
	}
	/**
	 * Returns a hashcode for this HashTree.
	 * @see java.lang.Object#hashCode()
	 */
	public int hashCode()
	{
		return data.hashCode() * 7;
	}
	/**
	 * Compares all objects in the tree and verifies that the two trees contain
	 * the same objects at the same tree levels.  Returns true if they do, false otherwise.
	 * @see java.lang.Object#equals(Object)
	 */
	public boolean equals(Object o)
	{
		boolean flag = true;
		if (o instanceof HashTree)
		{
			HashTree oo = (HashTree) o;
			Iterator it = data.keySet().iterator();
			while (it.hasNext())
			{
				if (!oo.containsKey(it.next()))
				{
					flag = false;
					break;
				}
			}
			if (flag)
			{
				it = data.keySet().iterator();
				while (it.hasNext())
				{
					Object temp = it.next();
					flag = get(temp).equals(oo.get(temp));
					if (!flag)
						break;
				}
			}
		}
		else
			flag = false;
		return flag;
	}
	/**
	 * Returns a Set of all the keys in the top-level of this HashTree.
	 * @see java.util.Map#keySet()
	 */
	public Set keySet()
	{
		return data.keySet();
	}
	/*****************************************************
	Searches the HashTree structure for the given key.  If it finds the key,
	it returns the HashTree mapped to the key.  If it finds nothing, it returns
	null.
	@param key Key to search for.
	@return HashTree mapped to key, if found, otherwise <B>null</B>.
	**********************************************************/
	public HashTree search(Object key)
	{
		HashTree temp = null;
		if (data.containsKey(key))
			temp = (HashTree) data.get(key);
		else
		{
			Iterator it = list().iterator();
			while (it.hasNext())
			{
				if (temp == null)
				{
					temp = ((HashTree) it.next()).search(key);
					break;
				}
				else
					break;
			}
		}
		return temp;
	}
	/**
	 * Method readObject.
	 * @param ois
	 * @throws ClassNotFoundException
	 * @throws IOException
	 */
	void readObject(ObjectInputStream ois)
		throws ClassNotFoundException, IOException
	{
		ois.defaultReadObject();
	}
	void writeObject(ObjectOutputStream oos) throws IOException
	{
		oos.defaultWriteObject();
	}
	/**
	 * Returns the number of top-level entries in the HashTree.
	 * @see java.util.Map#size()
	 */
	public int size()
	{
		return data.size();
	}
		/****************************************
	 * Allows any implementation of the HashTreeTraverser interface to 
	 * easily traverse (depth-first) all the nodes of the HashTree.  The
	 * Traverser implementation will be given notification of each node visited.
	 *
	 *@param visitor  !ToDo (Parameter description)
	 * @see org.apache.jorphan.collections.HashTreeTraverser
	 ***************************************/
	public void traverse(HashTreeTraverser visitor)
	{
		Iterator iter = list().iterator();
		while(iter.hasNext())
		{
			Object item = iter.next();
			visitor.addNode(item, getTree(item));
			getTree(item).traverseInto(visitor);
		}
	}

	/**
	 * The recursive method that accomplishes the tree-traversal and performs the 
	 * callbacks to the HashTreeTraverser.
	 * @param visitor
	 */
	private void traverseInto(HashTreeTraverser visitor)
	{
		Iterator iter = list().iterator();
		while(iter.hasNext())
		{
			Object item = iter.next();
			visitor.addNode(item, getTree(item));
			getTree(item).traverseInto(visitor);
		}
		if(list().size() == 0)
		{
			visitor.processPath();
		}
		visitor.subtractNode();
	}
	
	public String toString()
	{
		ConvertToString converter = new ConvertToString();
		traverse(converter);
		return converter.toString();
	}
	
	protected java.util.Map data;
	
	private class ConvertToString implements HashTreeTraverser
	{
		StringBuffer string = new StringBuffer(getClass().getName());
		StringBuffer spaces = new StringBuffer();
		int depth = 0;
		public void addNode(Object key,HashTree subTree)
		{
			depth++;
			string.append("\n"+getSpaces()+"{"+key);
		}
		
		public void subtractNode()
		{
			depth--;
			string.append("\n"+getSpaces()+"}");
		}
		
		public void processPath()
		{
		}
		
		public String toString()
		{
			return string.toString();
		}
		
		private String getSpaces()
		{
			if(spaces.length() < depth * 2)
			{
				while(spaces.length() < depth * 2)
				{
					spaces.append("  ");
				}
			}
			else if(spaces.length() > depth * 2)
			{
				spaces.setLength(depth * 2);
			}
			return spaces.toString();
		}
	}
	
	public static class Test extends TestCase
	{
		public Test(String name)
		{
			super(name);
		}
		
		public void testAdd1() throws Exception
		{
			Collection treePath = Arrays.asList(new String[]{"1","2","3","4"});
			HashTree tree = new HashTree();
			log.debug("treePath = "+treePath);
			tree.add(treePath,new String("value"));
			log.debug("Now treePath = "+treePath);
			log.debug(tree.toString());
			assertEquals(1,tree.list(treePath).size());
			assertEquals("value",tree.getArray(treePath)[0]);
		}
	}
}
