hashtree.java

测试工具

/*
 * 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.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.LinkedList;
import java.util.Map;
import java.util.Set;

/**
 * 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
 * @version $Revision: 571988 $ Updated on: $Date: 2007-09-02 15:19:10 +0100 (Sun, 02 Sep 2007) $
 */
public class HashTree implements Serializable, Map {
	// GetLoggerForClass() uses ClassContext, which
	// causes a Security violation in RemoteJMeterImpl
	// Currently log is only used by test code, so moved there.
	// N.B. Can still add logging, but would beed to use getLoggerFor() instead
	// private static Logger log =
	// LoggingManager.getLoggerForClass();

	/**
	 * 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 value
	 *            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).
	 * 
	 * @param key
	 *            to use
	 * @param value
	 *            to store against key
	 * @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.
	 */
	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 o
	 *            Object to be tested as a key.
	 * @return True if the HashTree contains the key, false otherwise.
	 * @see java.util.Map#containsKey(Object)
	 */
	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 t
	 *            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 treePath
	 *            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
	 *            collection 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) {
		clear();
		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.