Java > Open Source Codes > org > apache > jorphan > collections > HashTree


1 // $Header: /home/cvs/jakarta-jmeter/src/jorphan/org/apache/jorphan/collections/HashTree.java,v 1.14.2.2 2004/10/11 00:44:40 sebb Exp $
2 /*
3  * Copyright 2001-2004 The Apache Software Foundation.
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  *
17 */
18
19 package org.apache.jorphan.collections;
20
21 import java.io.IOException ;
22 import java.io.ObjectInputStream ;
23 import java.io.ObjectOutputStream ;
24 import java.io.Serializable ;
25 import java.util.Arrays ;
26 import java.util.Collection ;
27 import java.util.HashMap ;
28 import java.util.Iterator ;
29 import java.util.Map ;
30 import java.util.Set ;
31
32 import junit.framework.TestCase;
33
34 import org.apache.jorphan.logging.LoggingManager;
35 import org.apache.log.Logger;
36
37 /**
38  * This class is used to create a tree structure of objects. Each element in
39  * the tree is also a key to the next node down in the tree. It provides many
40  * ways to add objects and branches, as well as many ways to retrieve.
41  * <p>
42  * HashTree implements the Map interface for convenience reasons. The main
43  * difference between a Map and a HashTree is that the HashTree organizes the
44  * data into a recursive tree structure, and provides the means to manipulate
45  * that structure.
46  * <p>
47  * Of special interest is the {@link #traverse(HashTreeTraverser)} method,
48  * which provides an expedient way to traverse any HashTree by implementing the
49  * {@link HashTreeTraverser} interface in order to perform some operation on
50  * the tree, or to extract information from the tree.
51  *
52  * @author Michael Stover (mstover1 at apache.org)
53  * @see HashTreeTraverser
54  * @see SearchByClass
55  * @version $Revision: 1.14.2.2 $ Updated on: $Date: 2004/10/11 00:44:40 $
56  */
57 public class HashTree implements Serializable , Map
58 {
59 // GetLoggerForClass() uses ClassContext, which
60 // causes a Security violation in RemoteJMeterImpl
61 // Currently log is only used by test code, so moved there.
62 // N.B. Can still add logging, but would beed to use getLoggerFor() instead
63 // private static Logger log =
64 // LoggingManager.getLoggerForClass();
65
66     /**
67      * Creates an empty new HashTree.
68      */
69     public HashTree()
70     {
71         data = new HashMap ();
72     }
73     
74     /**
75      * Creates a new HashTree and adds the given object as a top-level node.
76      * @param key
77      */
78     public HashTree(Object key)
79     {
80         data = new HashMap ();
81         data.put(key, new HashTree());
82     }
83     
84     /**
85      * The Map given must also be a HashTree, otherwise an
86      * UnsupportedOperationException is thrown. If it is a HashTree, this is
87      * like calling the add(HashTree) method.
88      * @see #add(HashTree)
89      * @see java.util.Map#putAll(Map)
90      */
91     public void putAll(Map map)
92     {
93         if (map instanceof HashTree)
94         {
95             this.add((HashTree) map);
96         }
97         else
98         {
99             throw new UnsupportedOperationException (
100                     "can only putAll other HashTree objects");
101         }
102     }
103
104     /**
105      * Exists to satisfy the Map interface.
106      * @see java.util.Map#entrySet()
107      */
108     public Set entrySet()
109     {
110         return data.entrySet();
111     }
112
113     /**
114      * Implemented as required by the Map interface, but is not very useful
115      * here. All 'values' in a HashTree are HashTree's themselves.
116      *
117      * @param value Object to be tested as a value.
118      * @return True if the HashTree contains the value, false otherwise.
119      * @see java.util.Map#containsValue(Object)
120      */
121     public boolean containsValue(Object value)
122     {
123         return data.containsValue(value);
124     }
125
126     /**
127      * This is the same as calling HashTree.add(key,value).
128      * @param key to use
129      * @param value to store against key
130      * @see java.util.Map#put(Object, Object)
131      */
132     public Object put(Object key, Object value)
133     {
134         Object previous = data.get(key);
135         add(key, value);
136         return previous;
137     }
138
139     /**
140      * Clears the HashTree of all contents.
141      * @see java.util.Map#clear()
142      */
143     public void clear()
144     {
145         data.clear();
146     }
147
148     /**
149      * Returns a collection of all the sub-trees of the current tree.
150      * @see java.util.Map#values()
151      */
152     public Collection values()
153     {
154         return data.values();
155     }
156
157     /**
158      * Adds a key as a node at the current level and then adds the given
159      * HashTree to that new node.
160      *
161      * @param key key to create in this tree
162      * @param subTree sub tree to add to the node created for the first
163      * argument.
164      */
165     public void add(Object key, HashTree subTree)
166     {
167         add(key);
168         getTree(key).add(subTree);
169     }
170
171     /**
172      * Adds all the nodes and branches of the given tree to this tree. Is like
173      * merging two trees. Duplicates are ignored.
174      * @param newTree
175      */
176     public void add(HashTree newTree)
177     {
178         Iterator iter = newTree.list().iterator();
179         while (iter.hasNext())
180         {
181             Object item = iter.next();
182             add(item);
183             getTree(item).add(newTree.getTree(item));
184         }
185     }
186     
187     /**
188      * Creates a new HashTree and adds all the objects in the given collection
189      * as top-level nodes in the tree.
190      *
191      * @param keys a collection of objects to be added to the created HashTree.
192      */
193     public HashTree(Collection keys)
194     {
195         data = new HashMap ();
196         Iterator it = keys.iterator();
197         while (it.hasNext())
198         {
199             data.put(it.next(), new HashTree());
200         }
201     }
202     
203     /**
204      * Creates a new HashTree and adds all the objects in the given array as
205      * top-level nodes in the tree.
206      */
207     public HashTree(Object [] keys)
208     {
209         data = new HashMap ();
210         for (int x = 0; x < keys.length; x++)
211         {
212             data.put(keys[x], new HashTree());
213         }
214     }
215
216     /**
217      * If the HashTree contains the given object as a key at the top level,
218      * then a true result is returned, otherwise false.
219      *
220      * @param o Object to be tested as a key.
221      * @return True if the HashTree contains the key, false otherwise.
222      * @see java.util.Map#containsKey(Object)
223      */
224     public boolean containsKey(Object o)
225     {
226         return data.containsKey(o);
227     }
228     
229     /**
230      * If the HashTree is empty, true is returned, false otherwise.
231      * @return True if HashTree is empty, false otherwise.
232      */
233     public boolean isEmpty()
234     {
235         return data.isEmpty();
236     }
237     
238     /**
239      * Sets a key and it's value in the HashTree. It actually sets up a key,
240      * and then creates a node for the key and sets the value to the new node,
241      * as a key. Any previous nodes that existed under the given key are lost.
242      *
243      * @param key key to be set up
244      * @param value value to be set up as a key in the secondary node
245      */
246     public void set(Object key, Object value)
247     {
248         data.put(key, createNewTree(value));
249     }
250     
251     /**
252      * Sets a key into the current tree and assigns it a HashTree as its
253      * subtree. Any previous entries under the given key are removed.
254      *
255      * @param key key to be set up
256      * @param t HashTree that the key maps to
257      */
258     public void set(Object key, HashTree t)
259     {
260         data.put(key, t);
261     }
262     
263     /**
264      * Sets a key and it's values in the HashTree. It sets up a key in the
265      * current node, and then creates a node for that key, and sets all the
266      * values in the array as keys in the new node. Any keys previously held
267      * under the given key are lost.
268      *
269      * @param key Key to be set up
270      * @param values Array of objects to be added as keys in the secondary node
271      */
272     public void set(Object key, Object [] values)
273     {
274         data.put(key, createNewTree(Arrays.asList(values)));
275     }
276     
277     /**
278      * Sets a key and its values in the HashTree. It sets up a key in the
279      * current node, and then creates a node for that key, and set all the
280      * values in the array as keys in the new node. Any keys previously held
281      * under the given key are removed.
282      *
283      * @param key key to be set up
284      * @param values Collection of objects to be added as keys in the secondary
285      * node
286      */
287     public void set(Object key, Collection values)
288     {
289         data.put(key, createNewTree(values));
290     }
291     
292     /**
293      * Sets a series of keys into the HashTree. It sets up the first object in
294      * the key array as a key in the current node, recurses into the next
295      * HashTree node through that key and adds the second object in the array.
296      * Continues recursing in this manner until the end of the first array is
297      * reached, at which point all the values of the second array are set as
298      * keys to the bottom-most node. All previous keys of that bottom-most
299      * node are removed.
300      *
301      * @param treePath array of keys to put into HashTree
302      * @param values array of values to be added as keys to bottom-most node
303      */
304     public void set(Object [] treePath, Object [] values)
305     {
306         if (treePath != null && values != null)
307         {
308             set(Arrays.asList(treePath), Arrays.asList(values));
309         }
310     }
311     
312     /**
313      * Sets a series of keys into the HashTree. It sets up the first object in
314      * the key array as a key in the current node, recurses into the next
315      * HashTree node through that key and adds the second object in the array.
316      * Continues recursing in this manner until the end of the first array is
317      * reached, at which point all the values of the Collection of values are
318      * set as keys to the bottom-most node. Any keys previously held by the
319      * bottom-most node are lost.
320      *
321      * @param treePath array of keys to put into HashTree
322      * @param values Collection of values to be added as keys to bottom-most
323      * node
324      */
325     public void set(Object [] treePath, Collection values)
326     {
327         if (treePath != null)
328         {
329             set(Arrays.asList(treePath), values);
330         }
331     }
332     
333     /**
334      * Sets a series of keys into the HashTree. It sets up the first object in
335      * the key list as a key in the current node, recurses into the next
336      * HashTree node through that key and adds the second object in the list.
337      * Continues recursing in this manner until the end of the first list is
338      * reached, at which point all the values of the array of values are set as
339      * keys to the bottom-most node. Any previously existing keys of that
340      * bottom node are removed.
341      *
342      * @param treePath collection of keys to put into HashTree
343      * @param values array of values to be added as keys to bottom-most node
344      */
345     public void set(Collection treePath, Object [] values)
346     {
347         HashTree tree = addTreePath(treePath);
348         tree.set(Arrays.asList(values));
349     }
350     
351     /**
352      * Sets the nodes of the current tree to be the objects of the given
353      * collection. Any nodes previously in the tree are removed.
354      *
355      * @param values Collection of objects to set as nodes.
356      */
357     public void set(Collection values)
358     {
359         clear();
360         this.add(values);
361     }
362     
363     /**
364      * Sets a series of keys into the HashTree. It sets up the first object in
365      * the key list as a key in the current node, recurses into the next
366      * HashTree node through that key and adds the second object in the list.
367      * Continues recursing in this manner until the end of the first list is
368      * reached, at which point all the values of the Collection of values are
369      * set as keys to the bottom-most node. Any previously existing keys of
370      * that bottom node are lost.
371      *
372      * @param treePath list of keys to put into HashTree
373      * @param values collection of values to be added as keys to bottom-most
374      * node
375      */
376     public void set(Collection treePath, Collection values)
377     {
378         HashTree tree = addTreePath(treePath);
379         tree.set(values);
380     }
381     
382     /**
383      * Adds an key into the HashTree at the current level.
384      *
385      * @param key key to be added to HashTree
386      */
387     public HashTree add(Object key)
388     {
389         if (!data.containsKey(key))
390         {
391             HashTree newTree = createNewTree();
392             data.put(key, newTree);
393             return newTree;
394         }
395         else
396         {
397             return getTree(key);
398         }
399     }
400     
401     /**
402      * Adds all the given objects as nodes at the current level.
403      *
404      * @param keys Array of Keys to be added to HashTree.
405      */
406     public void add(Object [] keys)
407     {
408         for (int x = 0; x < keys.length; x++)
409         {
410             add(keys[x]);
411         }
412     }
413     
414     /**
415      * Adds a bunch of keys into the HashTree at the current level.
416      *
417      * @param keys Collection of Keys to be added to HashTree.
418      */
419     public void add(Collection keys)
420     {
421         Iterator it = keys.iterator();
422         while (it.hasNext())
423         {
424             add(it.next());
425         }
426     }
427     
428     /**
429      * Adds a key and it's value in the HashTree. The first argument becomes a
430      * node at the current level, and the second argument becomes a node of it.
431      *
432      * @param key key to be added
433      * @param value value to be added as a key in the secondary node
434      */
435     public HashTree add(Object key, Object value)
436     {
437         add(key);
438         return getTree(key).add(value);
439     }
440     
441     /**
442      * Adds a key and it's values in the HashTree. The first argument becomes
443      * a node at the current level, and adds all the values in the array to
444      * the new node.
445      *
446      * @param key key to be added
447      * @param values array of objects to be added as keys in the secondary node
448      */
449     public void add(Object key, Object [] values)
450     {
451         add(key);
452         getTree(key).add(values);
453     }
454     
455     /**
456      * Adds a key as a node at the current level and then adds all the objects
457      * in the second argument as nodes of the new node.
458      *
459      * @param key key to be added
460      * @param values Collection of objects to be added as keys in the secondary
461      * node
462      */
463     public void add(Object key, Collection values)
464     {
465         add(key);
466         getTree(key).add(values);
467     }
468     
469     /**
470      * Adds a series of nodes into the HashTree using the given path. The
471      * first argument is an array that represents a path to a specific node in
472      * the tree. If the path doesn't already exist, it is created (the objects
473      * are added along the way). At the path, all the objects in the second
474      * argument are added as nodes.
475      *
476      * @param treePath an array of objects representing a path
477      * @param values array of values to be added as keys to bottom-most node
478      */
479     public void add(Object [] treePath, Object [] values)
480     {
481         if (treePath != null)
482         {
483             add(Arrays.asList(treePath), Arrays.asList(values));
484         }
485     }
486     
487     /**
488      * Adds a series of nodes into the HashTree using the given path. The
489      * first argument is an array that represents a path to a specific node in
490      * the tree. If the path doesn't already exist, it is created (the objects
491      * are added along the way). At the path, all the objects in the second
492      * argument are added as nodes.
493      *
494      * @param treePath an array of objects representing a path
495      * @param values collection of values to be added as keys to bottom-most
496      * node
497      */
498     public void add(Object [] treePath, Collection values)
499     {
500         if (treePath != null)
501         {
502             add(Arrays.asList(treePath), values);
503         }
504     }
505     
506     public HashTree add(Object [] treePath,Object value)
507     {
508         return add(Arrays.asList(treePath),value);
509     }
510     
511     /**
512      * Adds a series of nodes into the HashTree using the given path. The
513      * first argument is a List that represents a path to a specific node in
514      * the tree. If the path doesn't already exist, it is created (the objects
515      * are added along the way). At the path, all the objects in the second
516      * argument are added as nodes.
517      *
518      * @param treePath a list of objects representing a path
519      * @param values array of values to be added as keys to bottom-most node
520      */
521     public void add(Collection treePath, Object [] values)
522     {
523         HashTree tree = addTreePath(treePath);
524         tree.add(Arrays.asList(values));
525     }
526     
527     /**
528      * Adds a series of nodes into the HashTree using the given path. The
529      * first argument is a List that represents a path to a specific node in
530      * the tree. If the path doesn't already exist, it is created (the objects
531      * are added along the way). At the path, the object in the second
532      * argument is added as a node.
533      *
534      * @param treePath a list of objects representing a path
535      * @param value Object to add as a node to bottom-most node
536      */
537     public HashTree add(Collection treePath, Object value)
538     {
539         HashTree tree = addTreePath(treePath);
540         return tree.add(value);
541     }
542     
543     /**
544      * Adds a series of nodes into the HashTree using the given path. The
545      * first argument is a SortedSet that represents a path to a specific node
546      * in the tree. If the path doesn't already exist, it is created (the
547      * objects are added along the way). At the path, all the objects in the
548      * second argument are added as nodes.
549      *
550      * @param treePath a SortedSet of objects representing a path
551      * @param values Collection of values to be added as keys to bottom-most
552      * node
553      */
554     public void add(Collection treePath, Collection values)
555     {
556         HashTree tree = addTreePath(treePath);
557         tree.add(values);
558     }
559
560     protected HashTree addTreePath(Collection treePath)
561     {
562         HashTree tree = this;
563         Iterator iter = treePath.iterator();
564         while (iter.hasNext())
565         {
566             Object temp = iter.next();
567             tree.add(temp);
568             tree = tree.getTree(temp);
569         }
570         return tree;
571     }
572     
573     /**
574      * Gets the HashTree mapped to the given key.
575      * @param key Key used to find appropriate HashTree()
576      */
577     public HashTree getTree(Object key)
578     {
579         return (HashTree) data.get(key);
580     }
581
582     /**
583      * Returns the HashTree object associated with the given key. Same as
584      * calling {@link #getTree(Object)}.
585      *
586      * @see java.util.Map#get(Object)
587      */
588     public Object get(Object key)
589     {
590         return getTree(key);
591     }
592     
593     /**
594      * Gets the HashTree object mapped to the last key in the array by
595      * recursing through the HashTree structure one key at a time.
596      *
597      * @param treePath array of keys.
598      * @return HashTree at the end of the recursion.
599      */
600     public HashTree getTree(Object [] treePath)
601     {
602         if (treePath != null)
603         {
604             return getTree(Arrays.asList(treePath));
605         }
606         else
607         {
608             return this;
609         }
610     }
611
612     /**
613      * Create a clone of this HashTree. This is not a deep clone (ie, the
614      * contents of the tree are not cloned).
615      * @see java.lang.Object#clone()
616      */
617     public Object clone()
618     {
619         HashTree newTree = new HashTree();
620         cloneTree(newTree);
621         return newTree;
622     }
623     
624     protected void cloneTree(HashTree newTree)
625     {
626         Iterator iter = list().iterator();
627         while (iter.hasNext())
628         {
629             Object key = iter.next();
630             newTree.set(key, (HashTree) getTree(key).clone());
631         }
632     }
633
634     /**
635      * Creates a new tree. This method exists to allow inheriting classes to
636      * generate the appropriate types of nodes. For instance, when a node is
637      * added, it's value is a HashTree. Rather than directly calling the
638      * HashTree() constructor, the createNewTree() method is called.
639      * Inheriting classes should override these methods and create the
640      * appropriate subclass of HashTree.
641      *
642      * @return HashTree
643      */
644     protected HashTree createNewTree()
645     {
646         return new HashTree();
647     }
648
649     /**
650      * Creates a new tree. This method exists to allow inheriting classes to
651      * generate the appropriate types of nodes. For instance, when a node is
652      * added, it's value is a HashTree. Rather than directly calling the
653      * HashTree() constructor, the createNewTree() method is called.
654      * Inheriting classes should override these methods and create the
655      * appropriate subclass of HashTree.
656      *
657      * @return HashTree
658      */
659     protected HashTree createNewTree(Object key)
660     {
661         return new HashTree(key);
662     }
663
664     /**
665      * Creates a new tree. This method exists to allow inheriting classes to
666      * generate the appropriate types of nodes. For instance, when a node is
667      * added, it's value is a HashTree. Rather than directly calling the
668      * HashTree() constructor, the createNewTree() method is called.
669      * Inheriting classes should override these methods and create the
670      * appropriate subclass of HashTree.
671      *
672      * @return HashTree
673      */
674     protected HashTree createNewTree(Collection values)
675     {
676         return new HashTree(values);
677     }
678
679     /**
680      * Gets the HashTree object mapped to the last key in the SortedSet by
681      * recursing through the HashTree structure one key at a time.
682      *
683      * @param treePath Collection of keys
684      * @return HashTree at the end of the recursion
685      */
686     public HashTree getTree(Collection treePath)
687     {
688         return getTreePath(treePath);
689     }
690     
691     /**
692      * Gets a Collection of all keys in the current HashTree node. If the
693      * HashTree represented a file system, this would be like getting a
694      * collection of all the files in the current folder.
695      *
696      * @return Set of all keys in this HashTree
697      */
698     public Collection list()
699     {
700         return data.keySet();
701     }
702     
703     /**
704      * Gets a Set of all keys in the HashTree mapped to the given key of the
705      * current HashTree object (in other words, one level down. If the HashTree
706      * represented a file system, this would like getting a list of all files in
707      * a sub-directory (of the current directory) specified by the key argument.
708      *
709      * @param key key used to find HashTree to get list of
710      * @return Set of all keys in found HashTree.
711      */
712     public Collection list(Object key)
713     {
714         HashTree temp = (HashTree) data.get(key);
715         if (temp != null)
716         {
717             return temp.list();
718         }
719         else
720         {
721             return null;
722         }
723     }
724     
725     /**
726      * Removes the entire branch specified by the given key.
727      * @see java.util.Map#remove(Object)
728      */
729     public Object remove(Object key)
730     {
731         return data.remove(key);
732     }
733     
734     
735     /**
736      * Recurses down into the HashTree stucture using each subsequent key in the
737      * array of keys, and returns the Set of keys of the HashTree object at the
738      * end of the recursion. If the HashTree represented a file system, this
739      * would be like getting a list of all the files in a directory specified by
740      * the treePath, relative from the current directory.
741      *
742      * @param treePath Array of keys used to recurse into HashTree structure
743      * @return Set of all keys found in end HashTree
744      */
745     public Collection list(Object [] treePath)
746     {
747         if (treePath != null)
748         {
749             return list(Arrays.asList(treePath));
750         }
751         else
752         {
753             return list();
754         }
755     }
756     
757     /**
758      * Recurses down into the HashTree stucture using each subsequent key in
759      * the List of keys, and returns the Set of keys of the HashTree object at
760      * the end of the recursion. If the HashTree represented a file system,
761      * this would be like getting a list of all the files in a directory
762      * specified by the treePath, relative from the current directory.
763      *
764      * @param treePath List of keys used to recurse into HashTree structure
765      * @return Set of all keys found in end HashTree
766      */
767     public Collection list(Collection treePath)
768     {
769         return getTreePath(treePath).list();
770     }
771     
772     /**
773      * Finds the given current key, and replaces it with the given new key.
774      * Any tree structure found under the original key is moved to the new key.
775      */
776     public void replace(Object currentKey, Object newKey)
777     {
778         HashTree tree = getTree(currentKey);
779         data.remove(currentKey);
780         data.put(newKey, tree);
781     }
782     
783     /**
784      * Gets an array of all keys in the current HashTree node. If the HashTree
785      * represented a file system, this would be like getting an array of all
786      * the files in the current folder.
787      *
788      * @return array of all keys in this HashTree.
789      */
790     public Object [] getArray()
791     {
792         return data.keySet().toArray();
793     }
794     
795     /**
796      * Gets an array of all keys in the HashTree mapped to the given key of the
797      * current HashTree object (in other words, one level down). If the
798      * HashTree represented a file system, this would like getting a list of
799      * all files in a sub-directory (of the current directory) specified by the
800      * key argument.
801      *
802      * @param key key used to find HashTree to get list of
803      * @return array of all keys in found HashTree
804      */
805     public Object [] getArray(Object key)
806     {
807         return getTree(key).getArray();
808     }
809     
810     /**
811      * Recurses down into the HashTree stucture using each subsequent key in
812      * the array of keys, and returns an array of keys of the HashTree object
813      * at the end of the recursion. If the HashTree represented a file system,
814      * this would be like getting a list of all the files in a directory
815      * specified by the treePath, relative from the current directory.
816      *
817      * @param treePath array of keys used to recurse into HashTree structure
818      * @return array of all keys found in end HashTree
819      */
820     public Object [] getArray(Object [] treePath)
821     {
822         if (treePath != null)
823         {
824             return getArray(Arrays.asList(treePath));
825         }
826         else
827         {
828             return getArray();
829         }
830     }
831     
832     /**
833      * Recurses down into the HashTree stucture using each subsequent key in
834      * the treePath argument, and returns an array of keys of the HashTree
835      * object at the end of the recursion. If the HashTree represented a file
836      * system, this would be like getting a list of all the files in a
837      * directory specified by the treePath, relative from the current
838      * directory.
839      *
840      * @param treePath list of keys used to recurse into HashTree structure
841      * @return array of all keys found in end HashTree
842      */
843     public Object [] getArray(Collection treePath)
844     {
845         HashTree tree = getTreePath(treePath);
846         return tree.getArray();
847     }
848     
849     protected HashTree getTreePath(Collection treePath)
850     {
851         HashTree tree = this;
852         Iterator iter = treePath.iterator();
853         while (iter.hasNext())
854         {
855             Object temp = iter.next();
856             tree = tree.getTree(temp);
857         }
858         return tree;
859     }
860     
861     /**
862      * Returns a hashcode for this HashTree.
863      * @see java.lang.Object#hashCode()
864      */
865     public int hashCode()
866     {
867         return data.hashCode() * 7;
868     }
869     
870     /**
871      * Compares all objects in the tree and verifies that the two trees contain
872      * the same objects at the same tree levels. Returns true if they do,
873      * false otherwise.
874      *
875      * @param o Object to be compared against
876      * @see java.lang.Object#equals(Object)
877      */
878     public boolean equals(Object o)
879     {
880        if (!(o instanceof HashTree)) return false;
881        HashTree oo = (HashTree) o;
882        if (oo.size() != this.size()) return false;
883        return data.equals(oo.data);
884
885 // boolean flag = true;
886 // if (o instanceof HashTree)
887 // {
888 // HashTree oo = (HashTree) o;
889 // Iterator it = data.keySet().iterator();
890 // while (it.hasNext())
891 // {
892 // if (!oo.containsKey(it.next()))
893 // {
894 // flag = false;
895 // break;
896 // }
897 // }
898 // if (flag)
899 // {
900 // it = data.keySet().iterator();
901 // while (it.hasNext())
902 // {
903 // Object temp = it.next();
904 // flag = get(temp).equals(oo.get(temp));
905 // if (!flag)
906 // {
907 // break;
908 // }
909 // }
910 // }
911 // }
912 // else
913 // {
914 // flag = false;
915 // }
916 // return flag;
917 }
918     
919     /**
920      * Returns a Set of all the keys in the top-level of this HashTree.
921      * @see java.util.Map#keySet()
922      */
923     public Set keySet()
924     {
925         return data.keySet();
926     }
927     
928     /**
929      * Searches the HashTree structure for the given key. If it finds the key,
930      * it returns the HashTree mapped to the key. If it finds nothing, it
931      * returns null.
932      *
933      * @param key Key to search for
934      * @return HashTree mapped to key, if found, otherwise <code>null</code>
935      */
936     public HashTree search(Object key)
937     {
938         HashTree result = getTree(key);
939         if(result != null)
940         {
941             return result;
942         }
943         TreeSearcher searcher = new TreeSearcher(key);
944         try
945         {
946             traverse(searcher);
947         }
948         catch(Exception e){
949             //do nothing - means object is found
950 }
951         return searcher.getResult();
952     }
953     /**
954      * Method readObject.
955      */
956     void readObject(ObjectInputStream ois)
957         throws ClassNotFoundException , IOException
958     {
959         ois.defaultReadObject();
960     }
961
962     void writeObject(ObjectOutputStream oos) throws IOException
963     {
964         oos.defaultWriteObject();
965     }
966
967     /**
968      * Returns the number of top-level entries in the HashTree.
969      * @see java.util.Map#size()
970      */
971     public int size()
972     {
973         return data.size();
974     }
975
976     /**
977      * Allows any implementation of the HashTreeTraverser interface to
978      * easily traverse (depth-first) all the nodes of the HashTree. The
979      * Traverser implementation will be given notification of each node visited.
980      *
981      * @see HashTreeTraverser
982      */
983     public void traverse(HashTreeTraverser visitor)
984     {
985         Iterator iter = list().iterator();
986         while (iter.hasNext())
987         {
988             Object item = iter.next();
989             visitor.addNode(item, getTree(item));
990             getTree(item).traverseInto(visitor);
991         }
992     }
993
994     /**
995      * The recursive method that accomplishes the tree-traversal and performs
996      * the callbacks to the HashTreeTraverser.
997      */
998     private void traverseInto(HashTreeTraverser visitor)
999     {
1000
1001        if (list().size() == 0)
1002        {
1003            visitor.processPath();
1004        }
1005        else
1006        {
1007            Iterator iter = list().iterator();
1008            while (iter.hasNext())
1009            {
1010                Object item = iter.next();
1011                visitor.addNode(item, getTree(item));
1012                getTree(item).traverseInto(visitor);
1013            }
1014        }
1015        visitor.subtractNode();
1016    }
1017
1018    public String toString()
1019    {
1020        ConvertToString converter = new ConvertToString();
1021        traverse(converter);
1022        return converter.toString();
1023    }
1024
1025    protected Map data;
1026    
1027    private class TreeSearcher implements HashTreeTraverser
1028    {
1029        Object target;
1030        HashTree result;
1031        
1032        public TreeSearcher(Object t)
1033        {
1034            target = t;
1035        }
1036        
1037        public HashTree getResult()
1038        {
1039            return result;
1040        }
1041            /* (non-Javadoc)
1042         * @see org.apache.jorphan.collections.HashTreeTraverser#addNode(java.lang.Object, org.apache.jorphan.collections.HashTree)
1043         */
1044        public void addNode(Object node, HashTree subTree) {
1045            result = subTree.getTree(target);
1046            if(result != null)
1047            {
1048                throw new RuntimeException ("found"); //short circuit traversal when found
1049 }
1050        }
1051        /* (non-Javadoc)
1052         * @see org.apache.jorphan.collections.HashTreeTraverser#processPath()
1053         */
1054        public void processPath() {
1055            // TODO Auto-generated method stub
1056
1057        }
1058        /* (non-Javadoc)
1059         * @see org.apache.jorphan.collections.HashTreeTraverser#subtractNode()
1060         */
1061        public void subtractNode() {
1062            // TODO Auto-generated method stub
1063
1064        }
1065}
1066
1067    private class ConvertToString implements HashTreeTraverser
1068    {
1069        StringBuffer string = new StringBuffer (getClass().getName() + "{");
1070        StringBuffer spaces = new StringBuffer ();
1071        int depth = 0;
1072        public void addNode(Object key, HashTree subTree)
1073        {
1074            depth++;
1075            string.append("\n" + getSpaces() + key + " {");
1076        }
1077
1078        public void subtractNode()
1079        {
1080            string.append("\n" + getSpaces() + "}");
1081            depth--;
1082        }
1083
1084        public void processPath()
1085        {
1086        }
1087
1088        public String toString()
1089        {
1090            string.append("\n}");
1091            return string.toString();
1092        }
1093
1094        private String getSpaces()
1095        {
1096            if (spaces.length() < depth * 2)
1097            {
1098                while (spaces.length() < depth * 2)
1099                {
1100                    spaces.append(" ");
1101                }
1102            }
1103            else if (spaces.length() > depth * 2)
1104            {
1105                spaces.setLength(depth * 2);
1106            }
1107            return spaces.toString();
1108        }
1109    }
1110
1111    public static class Test extends TestCase
1112    {
1113        public Test(String name)
1114        {
1115            super(name);
1116        }
1117
1118        public void testAdd1() throws Exception
1119        {
1120            Logger log =
1121                LoggingManager.getLoggerForClass();
1122            Collection treePath =
1123                Arrays.asList(new String [] { "1", "2", "3", "4" });
1124            HashTree tree = new HashTree();
1125            log.debug("treePath = " + treePath);
1126            tree.add(treePath, "value");
1127            log.debug("Now treePath = " + treePath);
1128            log.debug(tree.toString());
1129            assertEquals(1, tree.list(treePath).size());
1130            assertEquals("value", tree.getArray(treePath)[0]);
1131        }
1132        
1133        public void testEqualsAndHashCode() throws Exception
1134        {
1135            HashTree tree1 = new HashTree("abcd");
1136            HashTree tree2 = new HashTree("abcd");
1137            HashTree tree3 = new HashTree("abcde");
1138            HashTree tree4 = new HashTree("abcde");
1139            
1140            assertTrue(tree1.equals(tree1));
1141            assertTrue(tree1.equals(tree2));
1142            assertTrue(tree2.equals(tree1));
1143            assertTrue(tree2.equals(tree2));
1144            assertTrue(tree1.hashCode()==tree2.hashCode());
1145
1146            assertTrue(tree3.equals(tree3));
1147            assertTrue(tree3.equals(tree4));
1148            assertTrue(tree4.equals(tree3));
1149            assertTrue(tree4.equals(tree4));
1150            assertTrue(tree3.hashCode()==tree4.hashCode());
1151
1152            assertNotSame(tree1,tree2);
1153            assertNotSame(tree1,tree3);
1154            assertNotSame(tree1,tree4);
1155            assertNotSame(tree2,tree3);
1156            assertNotSame(tree2,tree4);
1157            
1158            assertFalse(tree1.equals(tree3));
1159            assertFalse(tree1.equals(tree4));
1160            assertFalse(tree2.equals(tree3));
1161            assertFalse(tree2.equals(tree4));
1162            
1163            assertNotNull(tree1);
1164            assertNotNull(tree1);
1165            assertNotNull(tree2);
1166            assertNotNull(tree2);
1167
1168            tree1.add("abcd",tree3);
1169            assertFalse(tree1.equals(tree2));
1170            assertFalse(tree2.equals(tree1));// Check reflexive
1171 if (tree1.hashCode()==tree2.hashCode())
1172            {
1173                // This is not a requirement
1174 System.out.println("WARN: unequal HashTrees should not have equal hashCodes");
1175            }
1176            tree2.add("abcd",tree4);
1177            assertTrue(tree1.equals(tree2));
1178            assertTrue(tree2.equals(tree1));
1179            assertTrue(tree1.hashCode()==tree2.hashCode());
1180        }
1181    }
1182}
1183

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags