package jas2.util.tree;

import java.util.*;

/**
 * A simple node represents a node in a tree. Each node has a number of properties:
 * 

 * 
Name: The name of the node
 * 
Type: The type of the node
 * 
Flags: A set of flags associated with the node
 * 
Object: An object associated with the node
 * 
 * SimpleNode contains a number of methods for making it easy to use TreeItems to 
 * build the tree. It is also possible to add a NodeListener to any node of the tree,
 * and this will be informed of all changes (additions and deletions) below that node.
 * Within a node, children are kept in a OrderedHashmap, which keeps items ordered by
 * insertion order, and also enables nodes to be rapidly looked up by name.
 * 
 * 
 */

public class SimpleNode
{
	/**
	 * Create a root node, with no name, type or flag
	 */
	public SimpleNode() // create a root node
	{
		flags = 0;
		type = null;
		parent = null;
		name = null;
	}
	/**
	 * Create a root node
	 * @param name The name of the node
	 * @param type The type of the node
	 * @param object The Object associated with the node
	 */
	public SimpleNode(String name, String type, int flags, Object object)
	{
		this.parent = null;
		this.name = name;
		this.type = type;
		this.flags = flags;
		this.object = object;
	}
	/**
	 * Create a node
	 * @param parent The parent of this node
	 * @param name The name of the node
	 * @param type The type of the node
	 * @param object The Object associated with the node
	 */
	public SimpleNode(SimpleNode parent, String name, String type, int flags, Object object)
	{
		this.parent = parent;
		this.name = name;
		this.type = type;
		this.flags = flags;
		this.object = object;

		parent.addChild(this);
	}
	/**
	 * Called to create a node when adding a TreeItem to the tree. Can be overriden
	 * by subclasses to create their own type of SimpleNode.
	 */
	protected SimpleNode createNode(SimpleNode parent, String name, String type, int flags, Object object)
	{
		return new SimpleNode(parent,name,type,flags,object);
	}
	protected void addChild(SimpleNode child)
	{
		// BUG: What if a child with this name already exists??
		// Is the caller responsible for removing it first, in which case this class
		// should throw an exception, or should this class treat add as replace if the name
		// is already is use??
		if (children == null) children = new FlashVector();
		children.put(child);
		child.treeChanged(0);
	}
	protected void removeChild(SimpleNode child)
	{
		child.treeChanged(TreeItem.DELETED);
		children.remove(child);
	}
	protected void renameChild(SimpleNode child, String newName)
	{
		// TODO: Need more informative message for this to work in remote case
		// The messages which are currently sent to update the slave tree are
		// instances of TreeItem. This is inadequate because items are only 
		// specified by name, meaning
		//  a) There is no way to have two items with the same name
		//  b) No way to perform a rename operation
		// For now rename is represented as a remove followed by an add
		child.treeChanged(TreeItem.DELETED);
		children.remove(child);
		child.name = newName;
		children.put(child);
		child.treeChanged(0); 
	}
	protected void treeChanged(int extraFlags)
	{
		SimpleNode n = this.parent;
		for (int depth=1; n != null ; depth++)
		{
			if (n.listener != null) 
			{
				String[] path = new String[depth];
				SimpleNode c = this;
				for (int j=depth-1; j>=0; j--)
				{
					path[j] = c.name;
					c = c.parent;
				}
				n.fireTreeChanged(new TreeItem(path,type,flags | extraFlags));
			}
			n = n.parent;
		}
	}
	/**
	 * Get a TreeItem describing this node, relative to a base node
	 * @param base The base node
	 * @return The TreeItem describing the relative path
	 */
	public TreeItem getTreeItem(SimpleNode base)
	{
		int depth;
		SimpleNode n = this;
		for (depth = 0; n != base; depth++) n = n.parent;
		String[] path = new String[depth];

		n = this;
		for (int j=depth-1; j>=0; j--)
		{
			path[j] = n.name;
			n = n.parent;
		}
		return new TreeItem(path,type,flags);
	}
	/**
	 * Find a child node with a given name
	 * @param name The name to search for
	 * @return The child node, or null of no node was found by the given name
	 */
	public SimpleNode findChild(String name)
	{
		if (children == null) return null;
		return children.get(name);
	}
	/**
	 * Destroy a node (remove it from its parents list of children)
	 * No further use of a node or its chilren should be made after it has been destroyed
	 */
	public void destroy()
	{
		parent.removeChild(this);
		children = null; //help garbage collector
		// Maybe we should also destroy our children, to help out the gc even more?
	}
	/**
	 * Add a node specified by a TreeItem. The path in the TreeItem is interpreted
	 * as relavive to the current node, and any intervening nodes specified by the 
	 * path are created automatically as needed.
	 * @param item The subnode to add
	 * @return The leaf node created
	 */
	public SimpleNode add(TreeItem item)
	{
		return add(item,null);
	}
	/**
	 * Add a node specified by a TreeItem, with an associated object. The path in the TreeItem is interpreted
	 * as relavive to the current node, and any intervening nodes specified by the 
	 * path are created automatically as needed.
	 * @param item The subnode to add
	 * @param object The associated object
	 * @return The leaf node created
	 */
	public SimpleNode add(TreeItem item, Object object)
	{
		SimpleNode parent = this;
		int l = item.path.length;
		for (int i=0; i=0; j--)
					{
						path[j] = c.name;
						c = c.parent;
					}
					TreeItem item = new TreeItem(path,type,flags);
					object = tos.getItem(new TreeItem(path,type,flags));
					break;
				}
				n = n.parent;
			}
		}
		return object;
	}
	public void setFlags(int mask)
	{
		int newFlags = flags | mask;
		if (newFlags != flags)
		{
			flags = newFlags;
			treeChanged(0);
		}
	}
	public void clearFlags(int mask)
	{
		int newFlags = flags & ~mask;
		if (newFlags != flags)
		{
			flags = newFlags;
			treeChanged(0);
		}
	}
	public boolean isAncestorOf(SimpleNode root)
	{
		for (SimpleNode search = this; search != null; search = search.parent) 
			if (search == root) return true;
		
		return false;
	}
	public String getType()
	{
		return type;
	}
	public int getFlags()
	{
		return flags;
	}
	public String getName()
	{
		return name;
	}
	public SimpleNode getParent()
	{
		return parent;
	}
	public void addNodeListener(SimpleNodeListener l)
	{
		if (listener == null) listener = new java.util.Vector();
		listener.addElement(l);
	}
	public void removeNodeListener(SimpleNodeListener l)
	{
		if (listener != null) listener.removeElement(l);
	}
	private void fireTreeChanged(TreeItem item)
	{
		Enumeration e = listener.elements();
		while (e.hasMoreElements())
		{
			SimpleNodeListener l = (SimpleNodeListener) e.nextElement();
			l.treeChanged(item);
		}
	}
	public String toString()
	{
		return name;
	}
	private java.util.Vector listener;
	private int flags;
	private String name;
	private String type;
	private SimpleNode parent;
	/**
	 * Note, since many nodes are leaves, the children map is not created until
	 * at least one child is added.
	 */
	protected FlashVector children;
	protected Object object;
	protected final static Enumeration nullEnumeration = new java.util.Vector().elements();
	
	/**
	 * The FlashVector class is used to keep children in insertion order, but also to 
	 * allow them to be looked up efficiently by name. It also provides an efficient
	 * implementation of indexOf() 
	 */
	static class FlashVector
	{
		void put(SimpleNode node)
		{
			vector.add(node);
			if (flash != null) flash.put(node.name,vector.size()-1);
		}
		void remove(SimpleNode node)
		{
			if (flash != null) vector.remove(flash.get(node.name));
			else vector.remove(node);
			flash = null;
		}
		SimpleNode get(String name)
		{
			if (flash == null) fillFlash();
			int index = flash.get(name);
			return index<0 ? null : (SimpleNode) vector.get(index);
		}
		SimpleNode elementAt(int index)
		{
			return (SimpleNode) vector.get(index);
		}
		int indexOf(SimpleNode node)
		{
			if (flash == null) fillFlash();
			return flash.get(node.name);
		}
		int size()
		{
			return vector.size();
		}
		//Enumeration elements()
		//{
		//	return vector.elements();
		//}
		Collection elements()
		{
			return Collections.unmodifiableCollection(vector);
		}
		private void fillFlash()
		{
			int s = vector.size();
			flash = new Flash(s);
			for (int i=0; i threshold) rehash();
				int hash = Math.abs(name.hashCode())%array.length;
				while (array[hash] != 0) hash = (hash+1)%array.length;
				array[hash] = index+1; // Add one to avoid 0, which is used for empty node
			}
			private void rehash()
			{
				int newLength = array.length*2 + 1;
				int[] newArray = new int[newLength];
				threshold = newLength/2;
				
				for (int i=0; i