0001: /*
0002: * Licensed to the Apache Software Foundation (ASF) under one or more
0003: * contributor license agreements. See the NOTICE file distributed with
0004: * this work for additional information regarding copyright ownership.
0005: * The ASF licenses this file to You under the Apache License, Version 2.0
0006: * (the "License"); you may not use this file except in compliance with
0007: * the License. You may obtain a copy of the License at
0008: *
0009: * http://www.apache.org/licenses/LICENSE-2.0
0010: *
0011: * Unless required by applicable law or agreed to in writing, software
0012: * distributed under the License is distributed on an "AS IS" BASIS,
0013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014: * See the License for the specific language governing permissions and
0015: * limitations under the License.
0016: *
0017: */
0018:
0019: package org.apache.jorphan.collections;
0020:
0021: import java.io.IOException;
0022: import java.io.ObjectInputStream;
0023: import java.io.ObjectOutputStream;
0024: import java.io.Serializable;
0025: import java.util.Arrays;
0026: import java.util.Collection;
0027: import java.util.HashMap;
0028: import java.util.Iterator;
0029: import java.util.LinkedList;
0030: import java.util.Map;
0031: import java.util.Set;
0032:
0033: /**
0034: * This class is used to create a tree structure of objects. Each element in the
0035: * tree is also a key to the next node down in the tree. It provides many ways
0036: * to add objects and branches, as well as many ways to retrieve.
0037: * <p>
0038: * HashTree implements the Map interface for convenience reasons. The main
0039: * difference between a Map and a HashTree is that the HashTree organizes the
0040: * data into a recursive tree structure, and provides the means to manipulate
0041: * that structure.
0042: * <p>
0043: * Of special interest is the {@link #traverse(HashTreeTraverser)} method, which
0044: * provides an expedient way to traverse any HashTree by implementing the
0045: * {@link HashTreeTraverser} interface in order to perform some operation on the
0046: * tree, or to extract information from the tree.
0047: *
0048: * @author Michael Stover (mstover1 at apache.org)
0049: * @see HashTreeTraverser
0050: * @see SearchByClass
0051: * @version $Revision: 571988 $ Updated on: $Date: 2007-09-02 15:19:10 +0100 (Sun, 02 Sep 2007) $
0052: */
0053: public class HashTree implements Serializable, Map {
0054: // GetLoggerForClass() uses ClassContext, which
0055: // causes a Security violation in RemoteJMeterImpl
0056: // Currently log is only used by test code, so moved there.
0057: // N.B. Can still add logging, but would beed to use getLoggerFor() instead
0058: // private static Logger log =
0059: // LoggingManager.getLoggerForClass();
0060:
0061: /**
0062: * Creates an empty new HashTree.
0063: */
0064: public HashTree() {
0065: data = new HashMap();
0066: }
0067:
0068: /**
0069: * Creates a new HashTree and adds the given object as a top-level node.
0070: *
0071: * @param key
0072: */
0073: public HashTree(Object key) {
0074: data = new HashMap();
0075: data.put(key, new HashTree());
0076: }
0077:
0078: /**
0079: * The Map given must also be a HashTree, otherwise an
0080: * UnsupportedOperationException is thrown. If it is a HashTree, this is
0081: * like calling the add(HashTree) method.
0082: *
0083: * @see #add(HashTree)
0084: * @see java.util.Map#putAll(Map)
0085: */
0086: public void putAll(Map map) {
0087: if (map instanceof HashTree) {
0088: this .add((HashTree) map);
0089: } else {
0090: throw new UnsupportedOperationException(
0091: "can only putAll other HashTree objects");
0092: }
0093: }
0094:
0095: /**
0096: * Exists to satisfy the Map interface.
0097: *
0098: * @see java.util.Map#entrySet()
0099: */
0100: public Set entrySet() {
0101: return data.entrySet();
0102: }
0103:
0104: /**
0105: * Implemented as required by the Map interface, but is not very useful
0106: * here. All 'values' in a HashTree are HashTree's themselves.
0107: *
0108: * @param value
0109: * Object to be tested as a value.
0110: * @return True if the HashTree contains the value, false otherwise.
0111: * @see java.util.Map#containsValue(Object)
0112: */
0113: public boolean containsValue(Object value) {
0114: return data.containsValue(value);
0115: }
0116:
0117: /**
0118: * This is the same as calling HashTree.add(key,value).
0119: *
0120: * @param key
0121: * to use
0122: * @param value
0123: * to store against key
0124: * @see java.util.Map#put(Object, Object)
0125: */
0126: public Object put(Object key, Object value) {
0127: Object previous = data.get(key);
0128: add(key, value);
0129: return previous;
0130: }
0131:
0132: /**
0133: * Clears the HashTree of all contents.
0134: *
0135: * @see java.util.Map#clear()
0136: */
0137: public void clear() {
0138: data.clear();
0139: }
0140:
0141: /**
0142: * Returns a collection of all the sub-trees of the current tree.
0143: *
0144: * @see java.util.Map#values()
0145: */
0146: public Collection values() {
0147: return data.values();
0148: }
0149:
0150: /**
0151: * Adds a key as a node at the current level and then adds the given
0152: * HashTree to that new node.
0153: *
0154: * @param key
0155: * key to create in this tree
0156: * @param subTree
0157: * sub tree to add to the node created for the first argument.
0158: */
0159: public void add(Object key, HashTree subTree) {
0160: add(key);
0161: getTree(key).add(subTree);
0162: }
0163:
0164: /**
0165: * Adds all the nodes and branches of the given tree to this tree. Is like
0166: * merging two trees. Duplicates are ignored.
0167: *
0168: * @param newTree
0169: */
0170: public void add(HashTree newTree) {
0171: Iterator iter = newTree.list().iterator();
0172: while (iter.hasNext()) {
0173: Object item = iter.next();
0174: add(item);
0175: getTree(item).add(newTree.getTree(item));
0176: }
0177: }
0178:
0179: /**
0180: * Creates a new HashTree and adds all the objects in the given collection
0181: * as top-level nodes in the tree.
0182: *
0183: * @param keys
0184: * a collection of objects to be added to the created HashTree.
0185: */
0186: public HashTree(Collection keys) {
0187: data = new HashMap();
0188: Iterator it = keys.iterator();
0189: while (it.hasNext()) {
0190: data.put(it.next(), new HashTree());
0191: }
0192: }
0193:
0194: /**
0195: * Creates a new HashTree and adds all the objects in the given array as
0196: * top-level nodes in the tree.
0197: */
0198: public HashTree(Object[] keys) {
0199: data = new HashMap();
0200: for (int x = 0; x < keys.length; x++) {
0201: data.put(keys[x], new HashTree());
0202: }
0203: }
0204:
0205: /**
0206: * If the HashTree contains the given object as a key at the top level, then
0207: * a true result is returned, otherwise false.
0208: *
0209: * @param o
0210: * Object to be tested as a key.
0211: * @return True if the HashTree contains the key, false otherwise.
0212: * @see java.util.Map#containsKey(Object)
0213: */
0214: public boolean containsKey(Object o) {
0215: return data.containsKey(o);
0216: }
0217:
0218: /**
0219: * If the HashTree is empty, true is returned, false otherwise.
0220: *
0221: * @return True if HashTree is empty, false otherwise.
0222: */
0223: public boolean isEmpty() {
0224: return data.isEmpty();
0225: }
0226:
0227: /**
0228: * Sets a key and it's value in the HashTree. It actually sets up a key, and
0229: * then creates a node for the key and sets the value to the new node, as a
0230: * key. Any previous nodes that existed under the given key are lost.
0231: *
0232: * @param key
0233: * key to be set up
0234: * @param value
0235: * value to be set up as a key in the secondary node
0236: */
0237: public void set(Object key, Object value) {
0238: data.put(key, createNewTree(value));
0239: }
0240:
0241: /**
0242: * Sets a key into the current tree and assigns it a HashTree as its
0243: * subtree. Any previous entries under the given key are removed.
0244: *
0245: * @param key
0246: * key to be set up
0247: * @param t
0248: * HashTree that the key maps to
0249: */
0250: public void set(Object key, HashTree t) {
0251: data.put(key, t);
0252: }
0253:
0254: /**
0255: * Sets a key and it's values in the HashTree. It sets up a key in the
0256: * current node, and then creates a node for that key, and sets all the
0257: * values in the array as keys in the new node. Any keys previously held
0258: * under the given key are lost.
0259: *
0260: * @param key
0261: * Key to be set up
0262: * @param values
0263: * Array of objects to be added as keys in the secondary node
0264: */
0265: public void set(Object key, Object[] values) {
0266: data.put(key, createNewTree(Arrays.asList(values)));
0267: }
0268:
0269: /**
0270: * Sets a key and its values in the HashTree. It sets up a key in the
0271: * current node, and then creates a node for that key, and set all the
0272: * values in the array as keys in the new node. Any keys previously held
0273: * under the given key are removed.
0274: *
0275: * @param key
0276: * key to be set up
0277: * @param values
0278: * Collection of objects to be added as keys in the secondary
0279: * node
0280: */
0281: public void set(Object key, Collection values) {
0282: data.put(key, createNewTree(values));
0283: }
0284:
0285: /**
0286: * Sets a series of keys into the HashTree. It sets up the first object in
0287: * the key array as a key in the current node, recurses into the next
0288: * HashTree node through that key and adds the second object in the array.
0289: * Continues recursing in this manner until the end of the first array is
0290: * reached, at which point all the values of the second array are set as
0291: * keys to the bottom-most node. All previous keys of that bottom-most node
0292: * are removed.
0293: *
0294: * @param treePath
0295: * array of keys to put into HashTree
0296: * @param values
0297: * array of values to be added as keys to bottom-most node
0298: */
0299: public void set(Object[] treePath, Object[] values) {
0300: if (treePath != null && values != null) {
0301: set(Arrays.asList(treePath), Arrays.asList(values));
0302: }
0303: }
0304:
0305: /**
0306: * Sets a series of keys into the HashTree. It sets up the first object in
0307: * the key array as a key in the current node, recurses into the next
0308: * HashTree node through that key and adds the second object in the array.
0309: * Continues recursing in this manner until the end of the first array is
0310: * reached, at which point all the values of the Collection of values are
0311: * set as keys to the bottom-most node. Any keys previously held by the
0312: * bottom-most node are lost.
0313: *
0314: * @param treePath
0315: * array of keys to put into HashTree
0316: * @param values
0317: * Collection of values to be added as keys to bottom-most node
0318: */
0319: public void set(Object[] treePath, Collection values) {
0320: if (treePath != null) {
0321: set(Arrays.asList(treePath), values);
0322: }
0323: }
0324:
0325: /**
0326: * Sets a series of keys into the HashTree. It sets up the first object in
0327: * the key list as a key in the current node, recurses into the next
0328: * HashTree node through that key and adds the second object in the list.
0329: * Continues recursing in this manner until the end of the first list is
0330: * reached, at which point all the values of the array of values are set as
0331: * keys to the bottom-most node. Any previously existing keys of that bottom
0332: * node are removed.
0333: *
0334: * @param treePath
0335: * collection of keys to put into HashTree
0336: * @param values
0337: * array of values to be added as keys to bottom-most node
0338: */
0339: public void set(Collection treePath, Object[] values) {
0340: HashTree tree = addTreePath(treePath);
0341: tree.set(Arrays.asList(values));
0342: }
0343:
0344: /**
0345: * Sets the nodes of the current tree to be the objects of the given
0346: * collection. Any nodes previously in the tree are removed.
0347: *
0348: * @param values
0349: * Collection of objects to set as nodes.
0350: */
0351: public void set(Collection values) {
0352: clear();
0353: this .add(values);
0354: }
0355:
0356: /**
0357: * Sets a series of keys into the HashTree. It sets up the first object in
0358: * the key list as a key in the current node, recurses into the next
0359: * HashTree node through that key and adds the second object in the list.
0360: * Continues recursing in this manner until the end of the first list is
0361: * reached, at which point all the values of the Collection of values are
0362: * set as keys to the bottom-most node. Any previously existing keys of that
0363: * bottom node are lost.
0364: *
0365: * @param treePath
0366: * list of keys to put into HashTree
0367: * @param values
0368: * collection of values to be added as keys to bottom-most node
0369: */
0370: public void set(Collection treePath, Collection values) {
0371: HashTree tree = addTreePath(treePath);
0372: tree.set(values);
0373: }
0374:
0375: /**
0376: * Adds an key into the HashTree at the current level.
0377: *
0378: * @param key
0379: * key to be added to HashTree
0380: */
0381: public HashTree add(Object key) {
0382: if (!data.containsKey(key)) {
0383: HashTree newTree = createNewTree();
0384: data.put(key, newTree);
0385: return newTree;
0386: } else {
0387: return getTree(key);
0388: }
0389: }
0390:
0391: /**
0392: * Adds all the given objects as nodes at the current level.
0393: *
0394: * @param keys
0395: * Array of Keys to be added to HashTree.
0396: */
0397: public void add(Object[] keys) {
0398: for (int x = 0; x < keys.length; x++) {
0399: add(keys[x]);
0400: }
0401: }
0402:
0403: /**
0404: * Adds a bunch of keys into the HashTree at the current level.
0405: *
0406: * @param keys
0407: * Collection of Keys to be added to HashTree.
0408: */
0409: public void add(Collection keys) {
0410: Iterator it = keys.iterator();
0411: while (it.hasNext()) {
0412: add(it.next());
0413: }
0414: }
0415:
0416: /**
0417: * Adds a key and it's value in the HashTree. The first argument becomes a
0418: * node at the current level, and the second argument becomes a node of it.
0419: *
0420: * @param key
0421: * key to be added
0422: * @param value
0423: * value to be added as a key in the secondary node
0424: */
0425: public HashTree add(Object key, Object value) {
0426: add(key);
0427: return getTree(key).add(value);
0428: }
0429:
0430: /**
0431: * Adds a key and it's values in the HashTree. The first argument becomes a
0432: * node at the current level, and adds all the values in the array to the
0433: * new node.
0434: *
0435: * @param key
0436: * key to be added
0437: * @param values
0438: * array of objects to be added as keys in the secondary node
0439: */
0440: public void add(Object key, Object[] values) {
0441: add(key);
0442: getTree(key).add(values);
0443: }
0444:
0445: /**
0446: * Adds a key as a node at the current level and then adds all the objects
0447: * in the second argument as nodes of the new node.
0448: *
0449: * @param key
0450: * key to be added
0451: * @param values
0452: * Collection of objects to be added as keys in the secondary
0453: * node
0454: */
0455: public void add(Object key, Collection values) {
0456: add(key);
0457: getTree(key).add(values);
0458: }
0459:
0460: /**
0461: * Adds a series of nodes into the HashTree using the given path. The first
0462: * argument is an array that represents a path to a specific node in the
0463: * tree. If the path doesn't already exist, it is created (the objects are
0464: * added along the way). At the path, all the objects in the second argument
0465: * are added as nodes.
0466: *
0467: * @param treePath
0468: * an array of objects representing a path
0469: * @param values
0470: * array of values to be added as keys to bottom-most node
0471: */
0472: public void add(Object[] treePath, Object[] values) {
0473: if (treePath != null) {
0474: add(Arrays.asList(treePath), Arrays.asList(values));
0475: }
0476: }
0477:
0478: /**
0479: * Adds a series of nodes into the HashTree using the given path. The first
0480: * argument is an array that represents a path to a specific node in the
0481: * tree. If the path doesn't already exist, it is created (the objects are
0482: * added along the way). At the path, all the objects in the second argument
0483: * are added as nodes.
0484: *
0485: * @param treePath
0486: * an array of objects representing a path
0487: * @param values
0488: * collection of values to be added as keys to bottom-most node
0489: */
0490: public void add(Object[] treePath, Collection values) {
0491: if (treePath != null) {
0492: add(Arrays.asList(treePath), values);
0493: }
0494: }
0495:
0496: public HashTree add(Object[] treePath, Object value) {
0497: return add(Arrays.asList(treePath), value);
0498: }
0499:
0500: /**
0501: * Adds a series of nodes into the HashTree using the given path. The first
0502: * argument is a List that represents a path to a specific node in the tree.
0503: * If the path doesn't already exist, it is created (the objects are added
0504: * along the way). At the path, all the objects in the second argument are
0505: * added as nodes.
0506: *
0507: * @param treePath
0508: * a list of objects representing a path
0509: * @param values
0510: * array of values to be added as keys to bottom-most node
0511: */
0512: public void add(Collection treePath, Object[] values) {
0513: HashTree tree = addTreePath(treePath);
0514: tree.add(Arrays.asList(values));
0515: }
0516:
0517: /**
0518: * Adds a series of nodes into the HashTree using the given path. The first
0519: * argument is a List that represents a path to a specific node in the tree.
0520: * If the path doesn't already exist, it is created (the objects are added
0521: * along the way). At the path, the object in the second argument is added
0522: * as a node.
0523: *
0524: * @param treePath
0525: * a list of objects representing a path
0526: * @param value
0527: * Object to add as a node to bottom-most node
0528: */
0529: public HashTree add(Collection treePath, Object value) {
0530: HashTree tree = addTreePath(treePath);
0531: return tree.add(value);
0532: }
0533:
0534: /**
0535: * Adds a series of nodes into the HashTree using the given path. The first
0536: * argument is a SortedSet that represents a path to a specific node in the
0537: * tree. If the path doesn't already exist, it is created (the objects are
0538: * added along the way). At the path, all the objects in the second argument
0539: * are added as nodes.
0540: *
0541: * @param treePath
0542: * a SortedSet of objects representing a path
0543: * @param values
0544: * Collection of values to be added as keys to bottom-most node
0545: */
0546: public void add(Collection treePath, Collection values) {
0547: HashTree tree = addTreePath(treePath);
0548: tree.add(values);
0549: }
0550:
0551: protected HashTree addTreePath(Collection treePath) {
0552: HashTree tree = this ;
0553: Iterator iter = treePath.iterator();
0554: while (iter.hasNext()) {
0555: Object temp = iter.next();
0556: tree.add(temp);
0557: tree = tree.getTree(temp);
0558: }
0559: return tree;
0560: }
0561:
0562: /**
0563: * Gets the HashTree mapped to the given key.
0564: *
0565: * @param key
0566: * Key used to find appropriate HashTree()
0567: */
0568: public HashTree getTree(Object key) {
0569: return (HashTree) data.get(key);
0570: }
0571:
0572: /**
0573: * Returns the HashTree object associated with the given key. Same as
0574: * calling {@link #getTree(Object)}.
0575: *
0576: * @see java.util.Map#get(Object)
0577: */
0578: public Object get(Object key) {
0579: return getTree(key);
0580: }
0581:
0582: /**
0583: * Gets the HashTree object mapped to the last key in the array by recursing
0584: * through the HashTree structure one key at a time.
0585: *
0586: * @param treePath
0587: * array of keys.
0588: * @return HashTree at the end of the recursion.
0589: */
0590: public HashTree getTree(Object[] treePath) {
0591: if (treePath != null) {
0592: return getTree(Arrays.asList(treePath));
0593: } else {
0594: return this ;
0595: }
0596: }
0597:
0598: /**
0599: * Create a clone of this HashTree. This is not a deep clone (ie, the
0600: * contents of the tree are not cloned).
0601: *
0602: */
0603: public Object clone() {
0604: HashTree newTree = new HashTree();
0605: cloneTree(newTree);
0606: return newTree;
0607: }
0608:
0609: protected void cloneTree(HashTree newTree) {
0610: Iterator iter = list().iterator();
0611: while (iter.hasNext()) {
0612: Object key = iter.next();
0613: newTree.set(key, (HashTree) getTree(key).clone());
0614: }
0615: }
0616:
0617: /**
0618: * Creates a new tree. This method exists to allow inheriting classes to
0619: * generate the appropriate types of nodes. For instance, when a node is
0620: * added, it's value is a HashTree. Rather than directly calling the
0621: * HashTree() constructor, the createNewTree() method is called. Inheriting
0622: * classes should override these methods and create the appropriate subclass
0623: * of HashTree.
0624: *
0625: * @return HashTree
0626: */
0627: protected HashTree createNewTree() {
0628: return new HashTree();
0629: }
0630:
0631: /**
0632: * Creates a new tree. This method exists to allow inheriting classes to
0633: * generate the appropriate types of nodes. For instance, when a node is
0634: * added, it's value is a HashTree. Rather than directly calling the
0635: * HashTree() constructor, the createNewTree() method is called. Inheriting
0636: * classes should override these methods and create the appropriate subclass
0637: * of HashTree.
0638: *
0639: * @return HashTree
0640: */
0641: protected HashTree createNewTree(Object key) {
0642: return new HashTree(key);
0643: }
0644:
0645: /**
0646: * Creates a new tree. This method exists to allow inheriting classes to
0647: * generate the appropriate types of nodes. For instance, when a node is
0648: * added, it's value is a HashTree. Rather than directly calling the
0649: * HashTree() constructor, the createNewTree() method is called. Inheriting
0650: * classes should override these methods and create the appropriate subclass
0651: * of HashTree.
0652: *
0653: * @return HashTree
0654: */
0655: protected HashTree createNewTree(Collection values) {
0656: return new HashTree(values);
0657: }
0658:
0659: /**
0660: * Gets the HashTree object mapped to the last key in the SortedSet by
0661: * recursing through the HashTree structure one key at a time.
0662: *
0663: * @param treePath
0664: * Collection of keys
0665: * @return HashTree at the end of the recursion
0666: */
0667: public HashTree getTree(Collection treePath) {
0668: return getTreePath(treePath);
0669: }
0670:
0671: /**
0672: * Gets a Collection of all keys in the current HashTree node. If the
0673: * HashTree represented a file system, this would be like getting a
0674: * collection of all the files in the current folder.
0675: *
0676: * @return Set of all keys in this HashTree
0677: */
0678: public Collection list() {
0679: return data.keySet();
0680: }
0681:
0682: /**
0683: * Gets a Set of all keys in the HashTree mapped to the given key of the
0684: * current HashTree object (in other words, one level down. If the HashTree
0685: * represented a file system, this would like getting a list of all files in
0686: * a sub-directory (of the current directory) specified by the key argument.
0687: *
0688: * @param key
0689: * key used to find HashTree to get list of
0690: * @return Set of all keys in found HashTree.
0691: */
0692: public Collection list(Object key) {
0693: HashTree temp = (HashTree) data.get(key);
0694: if (temp != null) {
0695: return temp.list();
0696: } else {
0697: return new LinkedList();
0698: }
0699: }
0700:
0701: /**
0702: * Removes the entire branch specified by the given key.
0703: *
0704: * @see java.util.Map#remove(Object)
0705: */
0706: public Object remove(Object key) {
0707: return data.remove(key);
0708: }
0709:
0710: /**
0711: * Recurses down into the HashTree stucture using each subsequent key in the
0712: * array of keys, and returns the Set of keys of the HashTree object at the
0713: * end of the recursion. If the HashTree represented a file system, this
0714: * would be like getting a list of all the files in a directory specified by
0715: * the treePath, relative from the current directory.
0716: *
0717: * @param treePath
0718: * Array of keys used to recurse into HashTree structure
0719: * @return Set of all keys found in end HashTree
0720: */
0721: public Collection list(Object[] treePath) {
0722: if (treePath != null) {
0723: return list(Arrays.asList(treePath));
0724: } else {
0725: return list();
0726: }
0727: }
0728:
0729: /**
0730: * Recurses down into the HashTree stucture using each subsequent key in the
0731: * List of keys, and returns the Set of keys of the HashTree object at the
0732: * end of the recursion. If the HashTree represented a file system, this
0733: * would be like getting a list of all the files in a directory specified by
0734: * the treePath, relative from the current directory.
0735: *
0736: * @param treePath
0737: * List of keys used to recurse into HashTree structure
0738: * @return Set of all keys found in end HashTree
0739: */
0740: public Collection list(Collection treePath) {
0741: HashTree tree = getTreePath(treePath);
0742: if (tree != null)
0743: return tree.list();
0744: return new LinkedList();
0745: }
0746:
0747: /**
0748: * Finds the given current key, and replaces it with the given new key. Any
0749: * tree structure found under the original key is moved to the new key.
0750: */
0751: public void replace(Object currentKey, Object newKey) {
0752: HashTree tree = getTree(currentKey);
0753: data.remove(currentKey);
0754: data.put(newKey, tree);
0755: }
0756:
0757: /**
0758: * Gets an array of all keys in the current HashTree node. If the HashTree
0759: * represented a file system, this would be like getting an array of all the
0760: * files in the current folder.
0761: *
0762: * @return array of all keys in this HashTree.
0763: */
0764: public Object[] getArray() {
0765: return data.keySet().toArray();
0766: }
0767:
0768: /**
0769: * Gets an array of all keys in the HashTree mapped to the given key of the
0770: * current HashTree object (in other words, one level down). If the HashTree
0771: * represented a file system, this would like getting a list of all files in
0772: * a sub-directory (of the current directory) specified by the key argument.
0773: *
0774: * @param key
0775: * key used to find HashTree to get list of
0776: * @return array of all keys in found HashTree
0777: */
0778: public Object[] getArray(Object key) {
0779: HashTree t = getTree(key);
0780: if (t != null)
0781: return t.getArray();
0782: else
0783: return null;
0784: }
0785:
0786: /**
0787: * Recurses down into the HashTree stucture using each subsequent key in the
0788: * array of keys, and returns an array of keys of the HashTree object at the
0789: * end of the recursion. If the HashTree represented a file system, this
0790: * would be like getting a list of all the files in a directory specified by
0791: * the treePath, relative from the current directory.
0792: *
0793: * @param treePath
0794: * array of keys used to recurse into HashTree structure
0795: * @return array of all keys found in end HashTree
0796: */
0797: public Object[] getArray(Object[] treePath) {
0798: if (treePath != null) {
0799: return getArray(Arrays.asList(treePath));
0800: } else {
0801: return getArray();
0802: }
0803: }
0804:
0805: /**
0806: * Recurses down into the HashTree stucture using each subsequent key in the
0807: * treePath argument, and returns an array of keys of the HashTree object at
0808: * the end of the recursion. If the HashTree represented a file system, this
0809: * would be like getting a list of all the files in a directory specified by
0810: * the treePath, relative from the current directory.
0811: *
0812: * @param treePath
0813: * list of keys used to recurse into HashTree structure
0814: * @return array of all keys found in end HashTree
0815: */
0816: public Object[] getArray(Collection treePath) {
0817: HashTree tree = getTreePath(treePath);
0818: return (tree != null) ? tree.getArray() : null;
0819: }
0820:
0821: protected HashTree getTreePath(Collection treePath) {
0822: HashTree tree = this ;
0823: Iterator iter = treePath.iterator();
0824: while (iter.hasNext()) {
0825: if (tree == null)
0826: return null;
0827: Object temp = iter.next();
0828: tree = tree.getTree(temp);
0829: }
0830: return tree;
0831: }
0832:
0833: /**
0834: * Returns a hashcode for this HashTree.
0835: *
0836: * @see java.lang.Object#hashCode()
0837: */
0838: public int hashCode() {
0839: return data.hashCode() * 7;
0840: }
0841:
0842: /**
0843: * Compares all objects in the tree and verifies that the two trees contain
0844: * the same objects at the same tree levels. Returns true if they do, false
0845: * otherwise.
0846: *
0847: * @param o
0848: * Object to be compared against
0849: * @see java.lang.Object#equals(Object)
0850: */
0851: public boolean equals(Object o) {
0852: if (!(o instanceof HashTree))
0853: return false;
0854: HashTree oo = (HashTree) o;
0855: if (oo.size() != this .size())
0856: return false;
0857: return data.equals(oo.data);
0858:
0859: // boolean flag = true;
0860: // if (o instanceof HashTree)
0861: // {
0862: // HashTree oo = (HashTree) o;
0863: // Iterator it = data.keySet().iterator();
0864: // while (it.hasNext())
0865: // {
0866: // if (!oo.containsKey(it.next()))
0867: // {
0868: // flag = false;
0869: // break;
0870: // }
0871: // }
0872: // if (flag)
0873: // {
0874: // it = data.keySet().iterator();
0875: // while (it.hasNext())
0876: // {
0877: // Object temp = it.next();
0878: // flag = get(temp).equals(oo.get(temp));
0879: // if (!flag)
0880: // {
0881: // break;
0882: // }
0883: // }
0884: // }
0885: // }
0886: // else
0887: // {
0888: // flag = false;
0889: // }
0890: // return flag;
0891: }
0892:
0893: /**
0894: * Returns a Set of all the keys in the top-level of this HashTree.
0895: *
0896: * @see java.util.Map#keySet()
0897: */
0898: public Set keySet() {
0899: return data.keySet();
0900: }
0901:
0902: /**
0903: * Searches the HashTree structure for the given key. If it finds the key,
0904: * it returns the HashTree mapped to the key. If it finds nothing, it
0905: * returns null.
0906: *
0907: * @param key
0908: * Key to search for
0909: * @return HashTree mapped to key, if found, otherwise <code>null</code>
0910: */
0911: public HashTree search(Object key) {
0912: HashTree result = getTree(key);
0913: if (result != null) {
0914: return result;
0915: }
0916: TreeSearcher searcher = new TreeSearcher(key);
0917: try {
0918: traverse(searcher);
0919: } catch (Exception e) {
0920: // do nothing - means object is found
0921: }
0922: return searcher.getResult();
0923: }
0924:
0925: /**
0926: * Method readObject.
0927: */
0928: private void readObject(ObjectInputStream ois)
0929: throws ClassNotFoundException, IOException {
0930: ois.defaultReadObject();
0931: }
0932:
0933: private void writeObject(ObjectOutputStream oos) throws IOException {
0934: oos.defaultWriteObject();
0935: }
0936:
0937: /**
0938: * Returns the number of top-level entries in the HashTree.
0939: *
0940: * @see java.util.Map#size()
0941: */
0942: public int size() {
0943: return data.size();
0944: }
0945:
0946: /**
0947: * Allows any implementation of the HashTreeTraverser interface to easily
0948: * traverse (depth-first) all the nodes of the HashTree. The Traverser
0949: * implementation will be given notification of each node visited.
0950: *
0951: * @see HashTreeTraverser
0952: */
0953: public void traverse(HashTreeTraverser visitor) {
0954: Iterator iter = list().iterator();
0955: while (iter.hasNext()) {
0956: Object item = iter.next();
0957: visitor.addNode(item, getTree(item));
0958: getTree(item).traverseInto(visitor);
0959: }
0960: }
0961:
0962: /**
0963: * The recursive method that accomplishes the tree-traversal and performs
0964: * the callbacks to the HashTreeTraverser.
0965: */
0966: private void traverseInto(HashTreeTraverser visitor) {
0967:
0968: if (list().size() == 0) {
0969: visitor.processPath();
0970: } else {
0971: Iterator iter = list().iterator();
0972: while (iter.hasNext()) {
0973: Object item = iter.next();
0974: visitor.addNode(item, getTree(item));
0975: getTree(item).traverseInto(visitor);
0976: }
0977: }
0978: visitor.subtractNode();
0979: }
0980:
0981: public String toString() {
0982: ConvertToString converter = new ConvertToString();
0983: traverse(converter);
0984: return converter.toString();
0985: }
0986:
0987: protected Map data;
0988:
0989: private static class TreeSearcher implements HashTreeTraverser {
0990: Object target;
0991:
0992: HashTree result;
0993:
0994: public TreeSearcher(Object t) {
0995: target = t;
0996: }
0997:
0998: public HashTree getResult() {
0999: return result;
1000: }
1001:
1002: /*
1003: * (non-Javadoc)
1004: *
1005: * @see org.apache.jorphan.collections.HashTreeTraverser#addNode(java.lang.Object,
1006: * org.apache.jorphan.collections.HashTree)
1007: */
1008: public void addNode(Object node, HashTree subTree) {
1009: result = subTree.getTree(target);
1010: if (result != null) {
1011: throw new RuntimeException("found"); // short circuit
1012: // traversal when found
1013: }
1014: }
1015:
1016: /*
1017: * (non-Javadoc)
1018: *
1019: * @see org.apache.jorphan.collections.HashTreeTraverser#processPath()
1020: */
1021: public void processPath() {
1022: // TODO Auto-generated method stub
1023:
1024: }
1025:
1026: /*
1027: * (non-Javadoc)
1028: *
1029: * @see org.apache.jorphan.collections.HashTreeTraverser#subtractNode()
1030: */
1031: public void subtractNode() {
1032: // TODO Auto-generated method stub
1033:
1034: }
1035: }
1036:
1037: private static class ConvertToString implements HashTreeTraverser {
1038: StringBuffer string = new StringBuffer(getClass().getName()
1039: + "{");
1040:
1041: StringBuffer spaces = new StringBuffer();
1042:
1043: int depth = 0;
1044:
1045: public void addNode(Object key, HashTree subTree) {
1046: depth++;
1047: string.append("\n" + getSpaces() + key + " {");
1048: }
1049:
1050: public void subtractNode() {
1051: string.append("\n" + getSpaces() + "}");
1052: depth--;
1053: }
1054:
1055: public void processPath() {
1056: }
1057:
1058: public String toString() {
1059: string.append("\n}");
1060: return string.toString();
1061: }
1062:
1063: private String getSpaces() {
1064: if (spaces.length() < depth * 2) {
1065: while (spaces.length() < depth * 2) {
1066: spaces.append(" ");
1067: }
1068: } else if (spaces.length() > depth * 2) {
1069: spaces.setLength(depth * 2);
1070: }
1071: return spaces.toString();
1072: }
1073: }
1074: }
|