KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > objectweb > proactive > examples > binarytree > BinaryTree


1 /*
2 * ################################################################
3 *
4 * ProActive: The Java(TM) library for Parallel, Distributed,
5 * Concurrent computing with Security and Mobility
6 *
7 * Copyright (C) 1997-2002 INRIA/University of Nice-Sophia Antipolis
8 * Contact: proactive-support@inria.fr
9 *
10 * This library is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU Lesser General Public
12 * License as published by the Free Software Foundation; either
13 * version 2.1 of the License, or any later version.
14 *
15 * This library is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * Lesser General Public License for more details.
19 *
20 * You should have received a copy of the GNU Lesser General Public
21 * License along with this library; if not, write to the Free Software
22 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
23 * USA
24 *
25 * Initial developer(s): The ProActive Team
26 * http://www.inria.fr/oasis/ProActive/contacts.html
27 * Contributor(s):
28 *
29 * ################################################################
30 */
31 package org.objectweb.proactive.examples.binarytree;
32
33 import org.apache.log4j.Logger;
34
35 /**
36  * A standard implementation of a node in a binary tree.
37  */
38 public class BinaryTree {
39     
40     static Logger logger = Logger.getLogger(BinaryTree.class.getName());
41
42   protected int key; // The key for accessing the value contained in this node
43 protected Object JavaDoc value; // The actual value contained in this node
44
45   // Convenience instance variable. One could prove this class invariant:
46 // (this.isLeaf == ((this.leftTree==null) && (this.rightTree==null)))
47 protected boolean isLeaf;
48   // The two subtrees
49 protected BinaryTree leftTree;
50   protected BinaryTree rightTree;
51
52
53   /**
54    * Creates an empty node
55    */
56   public BinaryTree() {
57     this.isLeaf = true; // On creation, the node does not yet have any child
58 }
59
60
61   /**
62    * Inserts a (key, value) pair in the subtree that has this node as its root
63    * If this node is a leaf
64    */
65   public void put(int key, Object JavaDoc value) {
66     // This node is empty, let's use it
67 if (this.isLeaf) {
68       this.key = key;
69       this.value = value;
70       this.isLeaf = false;
71       this.createChildren();
72     } else if (key == this.key) {
73       // Replaces the current value with a new one
74 this.value = value;
75     } else if (key < this.key) {
76       // smaller keys are on the left,
77 this.leftTree.put(key, value);
78     } else {
79       // greater keys on the right,
80 this.rightTree.put(key, value);
81     }
82   }
83
84
85   public ObjectWrapper get(int key) {
86     //System.out.println("Get of " + key + " in node " + this.key);
87 if (this.isLeaf) {
88       // We have reached a leaf of the tree and no key matching the parameter 'key'
89 // has been found. This is a miss.
90 return new ObjectWrapper ("null");
91     }
92     if (key == this.key) {
93       // We have found the node that contains the value we're looking for
94 return new ObjectWrapper(this.value);
95     }
96     if (key < this.key) {
97       // The current key is greater than the search key, let's continue on the left
98 ObjectWrapper res = this.leftTree.get(key);
99       return res;
100     }
101     // The current key is smaller than the search key, let's continue on the right
102 ObjectWrapper res = this.rightTree.get(key);
103     return res;
104   }
105
106
107   /**
108    * Creates two empty leaves as children
109    */
110   protected void createChildren() {
111     this.leftTree = new BinaryTree();
112     this.rightTree = new BinaryTree();
113   }
114 }
115
Popular Tags