hashtree.java

测试工具

	 *            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) {
		HashTree tree = getTreePath(treePath);
		if (tree != null)
			return tree.list();
		return new LinkedList();
	}

	/**
	 * 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.
	 */
	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) {
		HashTree t = getTree(key);
		if (t != null)
			return t.getArray();
		else
			return null;
	}

	/**
	 * 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 treePath
	 *            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 != null) ? tree.getArray() : null;
	}

	protected HashTree getTreePath(Collection treePath) {
		HashTree tree = this;
		Iterator iter = treePath.iterator();
		while (iter.hasNext()) {
			if (tree == null)
				return null;
			Object temp = iter.next();
			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.
	 * 
	 * @param o
	 *            Object to be compared against
	 * @see java.lang.Object#equals(Object)
	 */
	public boolean equals(Object o) {
		if (!(o instanceof HashTree))
			return false;
		HashTree oo = (HashTree) o;
		if (oo.size() != this.size())
			return false;
		return data.equals(oo.data);

		// 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 <code>null</code>
	 */
	public HashTree search(Object key) {
		HashTree result = getTree(key);
		if (result != null) {
			return result;
		}
		TreeSearcher searcher = new TreeSearcher(key);
		try {
			traverse(searcher);
		} catch (Exception e) {
			// do nothing - means object is found
		}
		return searcher.getResult();
	}

	/**
	 * Method readObject.
	 */
	private void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException {
		ois.defaultReadObject();
	}

	private 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.
	 * 
	 * @see 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.
	 */
	private void traverseInto(HashTreeTraverser visitor) {

		if (list().size() == 0) {
			visitor.processPath();
		} else {
			Iterator iter = list().iterator();
			while (iter.hasNext()) {
				Object item = iter.next();
				visitor.addNode(item, getTree(item));
				getTree(item).traverseInto(visitor);
			}
		}
		visitor.subtractNode();
	}

	public String toString() {
		ConvertToString converter = new ConvertToString();
		traverse(converter);
		return converter.toString();
	}

	protected Map data;

	private static class TreeSearcher implements HashTreeTraverser {
		Object target;

		HashTree result;

		public TreeSearcher(Object t) {
			target = t;
		}

		public HashTree getResult() {
			return result;
		}

		/*
		 * (non-Javadoc)
		 * 
		 * @see org.apache.jorphan.collections.HashTreeTraverser#addNode(java.lang.Object,
		 *      org.apache.jorphan.collections.HashTree)
		 */
		public void addNode(Object node, HashTree subTree) {
			result = subTree.getTree(target);
			if (result != null) {
				throw new RuntimeException("found"); // short circuit
														// traversal when found
			}
		}

		/*
		 * (non-Javadoc)
		 * 
		 * @see org.apache.jorphan.collections.HashTreeTraverser#processPath()
		 */
		public void processPath() {
			// TODO Auto-generated method stub

		}

		/*
		 * (non-Javadoc)
		 * 
		 * @see org.apache.jorphan.collections.HashTreeTraverser#subtractNode()
		 */
		public void subtractNode() {
			// TODO Auto-generated method stub

		}
	}

	private static 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() {
			string.append("\n" + getSpaces() + "}");
			depth--;
		}

		public void processPath() {
		}

		public String toString() {
			string.append("\n}");
			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();
		}
	}
}