Tree


1   /***
2    * Julia: France Telecom's implementation of the Fractal API
3    * Copyright (C) 2001-2002 France Telecom R&D
4    *
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2 of the License, or (at your option) any later version.
9    *
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   *
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   *
19   * Contact: Eric.Bruneton@rd.francetelecom.com
20   *
21   * Author: Eric Bruneton
22   */
23  
24  package org.objectweb.fractal.julia.loader;
25  
26  /**
27   * An immutable string tree.
28   */
29  
30  public class Tree {
31  
32    /**
33     * The value of this leaf node, or <tt>null</tt> for a "normal" node.
34     */
35  
36    private final String   leaf;
37  
38    /**
39     * The subtrees of this node, or <tt>null</tt> for a leaf node.
40     */
41  
42    private final Tree[] subTrees;
43  
44    // -----------------------------------------------------------------------
45    // Constructor
46    // -----------------------------------------------------------------------
47  
48    /**
49     * Constructs a new {@link Tree} instance.
50     *
51     * @param leaf the value of the node to be created.
52     */
53  
54    public Tree (final String   leaf) {
55      this.leaf = leaf;
56      this.subTrees = null;
57    }
58    /**
59     * Constructs a new {@link Tree} instance.
60     *
61     * @param subTrees the subtrees of the node to be created, or <tt>null</tt>
62     *      for a leaf node.
63     */
64  
65    public Tree (final Tree[] subTrees) {
66      this.leaf = null;
67      this.subTrees = subTrees;
68    }
69  
70    // -----------------------------------------------------------------------
71    // Accessors
72    // -----------------------------------------------------------------------
73  
74    /**
75     * Returns the number of sub trees of this tree.
76     *
77     * @return the number of sub trees of this tree.
78     */
79  
80    public int getSize () {
81      return (subTrees == null ? 0 : subTrees.length);
82    }
83  
84    /**
85     * Returns the sub tree of this tree whose index is given.
86     *
87     * @param index the index of the sub tree to be returned.
88     * @return the sub tree of this tree whose index is given.
89     * @throws java.lang.ArrayIndexOutOfBoundsException if <tt>index</tt> is
90     *      negative or strictly greater than {@link #getSize getSize}.
91     */
92  
93    public Tree getSubTree (final int index) {
94      if (subTrees == null) {
95        throw new ArrayIndexOutOfBoundsException  (index);
96      } else {
97        return subTrees[index];
98      }
99    }
100 
101   /**
102    * Returns the sub trees of this tree.
103    *
104    * @return the sub trees of this tree.
105    */
106 
107   public Tree[] getSubTrees () {
108     if (subTrees == null) {
109       return new Tree[0];
110     } else {
111       return subTrees;
112     }
113   }
114 
115   /**
116    * Return the value associated to the given key. This method supposes that 
117    * this tree is of the form "((key1 value1) ... (keyN valueN))".
118    * 
119    * @param key a key
120    * @return the value returned to this key, or <tt>null</tt>.
121    */
122   
123   public Tree getValue (final String   key) {
124     Tree[] t = getSubTrees();
125     for (int i = 0; i < t.length; ++i) {
126       if (t[i].getSize() == 2) {
127         if (t[i].getSubTree(0).equals(key)) {
128           return t[i].getSubTree(1);
129         }
130       }
131     }
132     return null;
133   }
134   
135   // -----------------------------------------------------------------------
136   // Overriden Object methods
137   // -----------------------------------------------------------------------
138 
139   /**
140    * Tests if this tree is equal to the given object.
141    *
142    * @param o the object to be compared to this tree.
143    * @return <tt>true</tt> if <tt>o</tt> is a tree that is equal to this tree,
144    *      or if <tt>o</tt> is a String that is equal to the String
145    *      representation of this tree.
146    */
147 
148   public boolean equals (final Object   o) {
149     if (o instanceof String  ) {
150       String   s = (String  )o;
151       // instead of converting this tree to a String, and then comparing the two
152       // Strings, it is MUCH MORE EFFICIENT to compare the tree directly to the
153       // given String, without doing any String manipulation:
154       return equals(s, 0, s.length()) == 0;
155     } else {
156       throw new RuntimeException  ("Not yet implemented");
157     }
158   }
159 
160   /**
161    * Returns the hashcode of this tree.
162    *
163    * @return the hashcode of this tree.
164    */
165 
166   public int hashCode () {
167     // instead of converting this tree to a String, and then computing the
168     // hashcode of this String, it is MUCH MORE EFFICIENT to compute the
169     // hashcode directly, without doing any String manipulation:
170     return hashCode(0);
171   }
172 
173   /**
174    * Returns a string representation of this tree.
175    *
176    * @return a string representation of this tree, with a LISP like syntax, as
177    *      in the following example: "(foo (bar foo))".
178    */
179 
180   public String   toString () {
181     if (leaf != null) {
182       return leaf;
183     }
184     if (subTrees.length == 0) {
185       return "()";
186     }
187     StringBuffer   buf = new StringBuffer  ();
188     toString(buf);
189     return buf.toString();
190   }
191 
192   // -----------------------------------------------------------------------
193   // Utility methods
194   // -----------------------------------------------------------------------
195 
196   /**
197    * Computes the hashcode of this tree based on an initial hashcode value.
198    *
199    * @param hc an initial hashcode value.
200    * @return the hashcode of this tree based on the given initial value.
201    */
202 
203   private int hashCode (int hc) {
204     if (leaf != null) {
205       hc = 17 * (hc + leaf.hashCode());
206     } else {
207       int l = subTrees.length;
208       hc = 17 * (hc + '(');
209       for (int i = 0; i < l; ++i) {
210         if (i > 0) {
211           hc = 17 * (hc + ' ');
212         }
213         hc = subTrees[i].hashCode(hc);
214       }
215       hc = 17 * (hc + ')');
216     }
217     return hc;
218   }
219 
220   /**
221    * Test if the String representation of this tree is equal to the given
222    * String.
223    *
224    * @param str a String.
225    * @param off the start index of the String to be compared to this tree in
226    *      <tt>str</tt>;
227    * @param len the length of the String to be compared to this tree.
228    * @return the number of remaining characters in <tt>str</tt>, once the prefix
229    *      corresponding to the String representation of this tree is removed, or
230    *      -1 if the given String does not starts with the String representation
231    *      of this tree.
232    */
233 
234   public int equals (final String   str, int off, int len) {
235     if (leaf != null) {
236       int l = leaf.length();
237       if (len < l || !str.regionMatches(false, off, leaf, 0, l)) {
238         return -1;
239       }
240       return len - l;
241     } else {
242       int l = subTrees.length;
243       if (len == 0 || str.charAt(off) != '(') {
244         return -1;
245       }
246       ++off;
247       --len;
248       for (int i = 0; i < l; ++i) {
249         if (i > 0) {
250           if (len == 0 || str.charAt(off) != ' ') {
251             return -1;
252           }
253           ++off;
254           --len;
255         }
256         int newLen = subTrees[i].equals(str, off, len);
257         if (newLen == -1) {
258           return -1;
259         }
260         off += len - newLen;
261         len = newLen;
262       }
263       if (len == 0 || str.charAt(off) != ')') {
264         return -1;
265       }
266       return len - 1;
267     }
268   }
269 
270   /**
271    * Appends the string representation of this tree to the given string buffer.
272    *
273    * @param buf the string buffer into which the string description of this
274    *      tree must be appened.
275    */
276 
277   private void toString (final StringBuffer   buf) {
278     if (subTrees == null) {
279       buf.append(leaf);
280     } else {
281       int l = subTrees.length;
282       buf.append('(');
283       for (int i = 0; i < l; ++i) {
284         if (i > 0) {
285           buf.append(' ');
286         }
287         subTrees[i].toString(buf);
288       }
289       buf.append(')');
290     }
291   }
292 }
293
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags