View Javadoc

1   /***
2    *  The contents of this file are subject to the Mozilla Public
3    *  License Version 1.1 (the "License"); you may not use this file
4    *  except in compliance with the License. You may obtain a copy of
5    *  the License at http://www.mozilla.org/MPL/
6    *
7    *  Software distributed under the License is distributed on an "AS
8    *  IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
9    *  implied. See the License for the specific language governing
10   *  rights and limitations under the License.
11   *
12   *  The Original Code is pow2toolkit library.
13   *
14   *  The Initial Owner of the Original Code is
15   *  particle (www.theparticle.com)
16   *
17   *  Portions created by Power Of Two S.R.L. are
18   *  Copyright (C) Power Of Two S.R.L.
19   *  All Rights Reserved.
20   *
21   * Contributor(s):
22   */
23  
24  package com.pow2.structures.tree;
25  
26  
27  import org.apache.log4j.Category;
28  
29  /***
30   *  Binary tree abstract class.
31   *  <br>
32   *  Extend this class and implement the {@link #build() build} method.
33   *
34   * @author  <a mailto="particle@theparticle.com">particle</a>
35   *             (<a href="http://www.theparticle.com/">www.theparticle.com</a>)
36   * @author  Luca Fossato
37   * @created  06 July 2002
38   */
39  public abstract class BinaryTree
40  {
41    /***   Build the tree. */
42    public abstract void build();
43  
44  
45    /*** use this value to specify the pre-traverse algorithm */
46    public final static int PRETRAVERSE = 0;
47  
48    /*** use this value to specify the in-traverse algorithm */
49    public final static int INTRAVERSE = 1;
50  
51    /*** use this value to specify the post-traverse algorithm */
52    public final static int POSTRAVERSE = 2;
53  
54    /*** Log4j category */
55    protected Category cat = Category.getInstance(BinaryTree.class.getName());
56  
57    /*** The root node of the tree */
58    protected Node root;
59  
60    /***
61     * Specify the tree traverse mode.
62     * <br>
63     * It can have one of the following values:
64     * <ul>
65     *   <li>BynaryTree.PRETRAVERSE - use the pre-traverse algorithm</li>
66     *   <li>BynaryTree.INTRAVERSE  - use the in-traverse algorithm</li>
67     *   <li>BynaryTree.POSTRAVERSE - use the post-traverse algorithm</li>
68     * </ul>
69     */
70    protected int traverseMode;
71  
72    /*** the nodeVisitor reference */
73    protected NodeVisitorInterface nodeVisitor;
74  
75  
76    /***
77     *  Default constructor for the BinaryTree object.
78     *  <br>
79     *  Set the traverse mode to <code>PRETRAVERSE</code>.
80     */
81    public BinaryTree()
82    {
83      root = null;
84      nodeVisitor = null;
85      traverseMode = PRETRAVERSE;
86    }
87  
88  
89    /***
90     *  Constructor for BinaryTree object.
91     *  <br>
92     *  Set the input {@link java.lang.Object#Object() object} as the data object
93     *  related to the root {@link Node#Node(Object) node} of the tree.
94     *
95     * @param  o the data object to relate to the tree root node
96     */
97    public BinaryTree(Object o)
98    {
99      root = new Node(o);
100     root.setDepth(0);
101   }
102 
103 
104   /***
105    *  Sets the data object of the tree root node.
106    *  <br>
107    *  If the tree root node is null, instance a new root node and set its
108    *  data property.
109    *
110    * @param  o The new root node data object
111    */
112   public void setData(Object o)
113   {
114     if (isEmpty())
115       root = new Node();
116     root.setData(o);
117   }
118 
119 
120   /***
121    *  Sets the nodeVisitor attribute of the BinaryTree object
122    *
123    * @param  nodeVisitor The new nodeVisitor value
124    */
125   public void setNodeVisitor(NodeVisitorInterface nodeVisitor)
126   {
127     this.nodeVisitor = nodeVisitor;
128   }
129 
130 
131   /***
132    *  Set the root node of the BinaryTree object
133    *
134    * @param  r The new root value
135    */
136   public void setRoot(Node r)
137   {
138     root = r;
139   }
140 
141 
142   /***
143    *  Set the traverseMode attribute of the BinaryTree object.
144    *  <code>traverseMode</code> can have one of the following values:
145    *  <ul>
146    *    <li>{@link #PRETRAVERSE BynaryTree.PRETRAVERSE} to use the pre-traverse algorithm</li>
147    *    <li>{@link #INTRAVERSE  BynaryTree.INTRAVERSE}  to use the in-traverse algorithm</li>
148    *    <li>{@link #POSTRAVERSE BynaryTree.POSTRAVERSE} to use the post-traverse algorithm</li>
149    *  </ul>
150    *
151    * @param  traverseMode the traversing mode.
152    */
153   public void setTraverseMode(int traverseMode)
154   {
155     this.traverseMode = traverseMode;
156   }
157 
158 
159   /***
160    *  Test if the Binary Tree is empty.
161    *  <br>
162    *  A binary tree is empty if the root element of the tree is null.
163    *
164    * @return  true if the the root element of the tree is null;
165    *            false otherwise.
166    */
167   public boolean isEmpty()
168   {
169     return (root == null);
170   }
171 
172 
173   /***
174    *  Gets the data object of the tree root node
175    *
176    * @return  The data object of the tree root node,
177    *            or null if the root node is null
178    */
179   public Object getData()
180   {
181     return (!isEmpty()) ? root.getData() : null;
182   }
183 
184 
185   /***
186    *  Gets the nodeVisitor attribute of the BinaryTree object
187    *
188    * @return  The nodeVisitor value
189    */
190   public NodeVisitorInterface getNodeVisitor()
191   {
192     return nodeVisitor;
193   }
194 
195 
196   /***
197    *  Gets the left node of the root node
198    *
199    * @return  The left node of the root node, or null if the
200    *            root node is null
201    */
202   public Node getLeft()
203   {
204     return (!isEmpty()) ? root.getLeft() : null;
205   }
206 
207 
208   /***
209    *  Get the root node of the BinaryTree object
210    *
211    * @return  The root value
212    */
213   public Node getRoot()
214   {
215     return root;
216   }
217 
218 
219   /***
220    *  Gets the right node of the root node
221    *
222    * @return  The right node of the root node, or null if the root node
223    *            is empty
224    */
225   public Node getRight()
226   {
227     return (!isEmpty()) ? root.getRight() : null;
228   }
229 
230 
231   /***
232    *  Get the traverse mode attribute of the BinaryTree object.
233    *
234    * @return  the traverse mode attribute of the BinaryTree object
235    */
236   public int getTraverseMode()
237   {
238     return traverseMode;
239   }
240 
241 
242   /***
243    *  Insert a new left node into the tree.
244    *
245    * @param  p the parent node where to insert the new left node
246    * @param  c the new left node to add to the parent node
247    * @return  true  if the insertion is successfull;
248    *            false otherwise
249    */
250   public boolean insertLeft(Node p, Node c)
251   {
252     // cannot overwrite the parent left node;
253     if ((p == null) || (p.getLeft() != null))
254       return false;
255 
256     p.setLeft(c);
257     c.setParent(p);
258     c.setDepth(p.getDepth() + 1);
259 
260     return true;
261   }
262 
263 
264   /***
265    *  Insert a new right node into the tree.
266    *
267    * @param  p the parent node where to insert the new right node
268    * @param  c the new right node to add to the parent node
269    * @return  true  if the insertion is successfull;
270    *            false otherwise
271    */
272   public boolean insertRight(Node p, Node c)
273   {
274     // cannot overwrite the parent right node;
275     if ((p == null) || (p.getRight() != null))
276       return false;
277 
278     p.setRight(c);
279     c.setParent(p);
280     c.setDepth(p.getDepth());
281 
282     return true;
283   }
284 
285 
286   /***
287    *  Add a new left node to the parent node left node list.
288    *
289    * @param  p the parent node
290    * @param  c the left node to add to the parent node left node list
291    * @return  true  if the addition is successfull;
292    *            false otherwise
293    */
294   public boolean addLeft(Node p, Node c)
295   {
296     if (p == null)
297       return false;
298 
299     // if the parent node have a left node:
300     //   c node is inserted with the same deep level than the parent left node;
301     // else create the first left node.
302     if (p.getLeft() != null)
303       return addRight(p.getLeft(), c);
304     else
305       return insertLeft(p, c);
306   }
307 
308 
309   /***
310    *  Add a new right node to the parent node right node list.
311    *
312    * @param  p the parent node
313    * @param  c the node to add to the the parent node right node list
314    * @return  true  if the addition is successfull;
315    *           false otherwise
316    */
317   public boolean addRight(Node p, Node c)
318   {
319     if (p == null)
320       return false;
321 
322     // get the last right node of the list;
323     while (p.getRight() != null)
324     {
325       p = p.getRight();
326     }
327 
328     p.setRight(c);
329     c.setParent(p);
330     c.setDepth(p.getDepth());
331 
332     return true;
333   }
334 
335 
336   /***
337    *  Move the input <code>c</code> node
338    *  over the new parent <code>p</code> node.
339    *
340    * @param  p the new parent node for <code>c</code> node
341    * @param  c the node to move
342    * @param  isLeft true  if <code>c</code> must be inserted
343    *                       as a left node of <code>p</code>;
344    *                 false if <code>c</code> must be inserted as right
345    *                       node of <code>p</code>
346    */
347   public void move(Node p, Node c, boolean isLeft)
348   {
349     // detach the input node from the tree, and
350     // reinsert the input node over the input parent node,
351     // as a new left or right node;
352     detachNode(c);
353 
354     // 0 is the id of the root node;
355     if (p.getId().equals("0"))
356     {
357        addLeft(p, c);
358        //cat.info("::move - move node [" + c.getId() + "] over [" + p.getId() + "]");
359     }
360     else
361     {
362       if (isLeft)
363         addLeft(p, c);
364 
365       else
366         addRight(p, c);
367     }
368   }
369 
370 
371   /***
372    *  Remove the input node from the tree.
373    *
374    * @param  n the node to remove
375    * @param  recursive true   to remove all the input node children;
376    *                   false  otherwise
377    */
378   public void remove(Node n, boolean recursive)
379   {
380     if (n == null)
381       return;
382 
383     Node  l  = n.getLeft();
384     Node  r  = n.getRight();
385 
386     remove(n);
387     n.finalize();
388 
389     // should be synchronized ...
390     if (recursive)
391     {
392       remove(l, recursive);
393       remove(r, recursive);
394     }
395   }
396 
397 
398   /***
399    *  Remove the input node from the tree, rearranging
400    *  the parent and the child nodes references.
401    *
402    * @param  n the node to remove
403    */
404   protected void remove(Node n)
405   {
406     detachNode(n);
407     n.finalize();
408   }
409 
410 
411   /***
412    *  Detach the input node from the tree, rearranging
413    *  the parent and the child nodes references.
414    *
415    * @param  n the node to remove
416    */
417   private void detachNode(Node n)
418   {
419     Node parent = n.getParent();
420     Node right  = n.getRight();
421     Node left   = n.getLeft();
422 
423     // the input node is the parent's left node ?
424     // set the parent left node -> node.right;
425     if ((parent != null) && (n == parent.getLeft()))
426       parent.setLeft(right);
427 
428     // right node ?
429     // set parent right node -> node.right;
430     else if ((parent != null) && (n == parent.getRight()))
431       parent.setRight(right);
432 
433     if (right != null)
434       right.setParent(parent);
435 
436     n.setRight  (null);
437     n.setParent (null);
438   }
439 
440 
441   /***
442    *  Traverse the tree, using the traverse algorithm
443    *  specified using {@link #setTraverseMode(int) setTraverseMode}.
444    *
445    * @exception  Exception if any error occurs
446    */
447   public void traverse() throws Exception
448   {
449     switch (traverseMode)
450     {
451         // data, left nodes, right nodes
452         case PRETRAVERSE:
453           pretrav(root);
454           break;
455         // right nodes, data, left nodes
456         case INTRAVERSE:
457           intrav(root);
458           break;
459         // left nodes, right nodes, data
460         case POSTRAVERSE:
461           postrav(root);
462           break;
463     }
464   }
465 
466 
467   /***
468    *  Traverse the tree, using pre-order algorithm,
469    *  starting from the input node.
470    *  <br>
471    *  pre-order traversal: first looks at the data (of the current node),
472    *  then the left nodes, and then the right nodes.
473    *
474    * @param  p the node where to start the tree traversing
475    * @exception  Exception if any error occurs
476    */
477   protected void pretrav(Node p) throws Exception
478   {
479     if (p == null)
480       return;
481 
482     visit(p);
483     pretrav(p.getLeft());
484     pretrav(p.getRight());
485   }
486 
487 
488   /***
489    *  Traverse the tree, using in-order algorithm, starting from the input node.
490    *  <br>
491    *  in-order traversal: first look at the right nodes, then the nodes data,
492    *  and then the left nodes.
493    *
494    * @param  p the node where to start the tree traversing.
495    * @exception  Exception if any error occurs
496    */
497   protected void intrav(Node p) throws Exception
498   {
499     if (p == null)
500       return;
501 
502     intrav(p.getRight());
503     visit(p);
504     intrav(p.getLeft());
505   }
506 
507 
508   /***
509    *  Traverse the tree, using post-order algorithm, starting from the input node.
510    *  <br>
511    *  post-order traversal: looks at the left child, then right child,
512    *  and only then data.
513    *
514    * @param  p the node where to start the tree traversing.
515    * @exception  Exception if any error occurs
516    */
517   protected void postrav(Node p) throws Exception
518   {
519     if (p == null)
520       return;
521 
522     postrav(p.getLeft());
523     postrav(p.getRight());
524     visit(p);
525   }
526 
527 
528   /***
529    *  Visit the content of the input node.
530    *
531    * @param  n the node to visit
532    * @exception  Exception if any error occurs
533    */
534   public void visit(Node n) throws Exception
535   {
536     nodeVisitor.visit(n);
537   }
538 }