1 salcianu 1.1.2.1 // LightMap.java, created Sun Mar 19 15:46:56 2000 by salcianu
2 cananian 1.1.2.6 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
3 salcianu 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1.2.1 package harpoon.Util.DataStructs;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.1 import java.util.Set;
7 salcianu 1.1.2.1 import java.util.HashSet;
8 salcianu 1.1.2.1 import java.util.Map;
9 salcianu 1.1.2.1 import java.util.Collection;
10 salcianu 1.1.2.1 import java.util.Collections;
11 salcianu 1.1.2.3 import java.util.Iterator;
12 salcianu 1.1.2.3 import java.util.LinkedList;
13 salcianu 1.1.2.1
14 salcianu 1.1.2.1 import harpoon.Util.Util;
15 salcianu 1.1.2.1
16 salcianu 1.1.2.1 /**
17 salcianu 1.1.2.1 * <code>LightMap</code> is a very lightweight implementation of
18 salcianu 1.1.2.1 the <code>java.util.Map</code> interface.
19 salcianu 1.1.2.1 *
20 cananian 1.1.2.6 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
21 cananian 1.3 * @version $Id: LightMap.java,v 1.3 2004/02/08 03:21:50 cananian Exp $
22 salcianu 1.1.2.1 */
23 salcianu 1.1.2.5 public class LightMap implements Map, Cloneable, java.io.Serializable {
24 salcianu 1.1.2.1 // the number of mappings in this map
25 salcianu 1.1.2.1 private int size = 0;
26 salcianu 1.1.2.1 // the root of the binary tree used to store the mapping
27 salcianu 1.1.2.1 private BinTreeNode root = null;
28 salcianu 1.1.2.1
29 salcianu 1.1.2.1 /** Creates a <code>LightMap</code>. */
30 salcianu 1.1.2.1 public LightMap() {}
31 cananian 1.1.2.7 /** Creates a <code>LightMap</code> with the same mappings as the
32 cananian 1.1.2.7 * given map. */
33 cananian 1.1.2.7 public LightMap(Map m) {
34 cananian 1.1.2.7 this();
35 cananian 1.1.2.7 putAll(m);
36 cananian 1.1.2.7 }
37 salcianu 1.1.2.1
38 salcianu 1.1.2.1 public final int size(){
39 salcianu 1.1.2.1 return size;
40 salcianu 1.1.2.1 }
41 salcianu 1.1.2.1
42 salcianu 1.1.2.1 public final boolean isEmpty(){
43 salcianu 1.1.2.1 return size != 0;
44 salcianu 1.1.2.1 }
45 salcianu 1.1.2.1
46 salcianu 1.1.2.1 /** Returns <code>true</code> if this map contains a mapping
47 salcianu 1.1.2.1 for the specified key. */
48 salcianu 1.1.2.1 public final boolean containsKey(Object key){
49 salcianu 1.1.2.1 return get(key) != null;
50 salcianu 1.1.2.1 }
51 salcianu 1.1.2.1
52 salcianu 1.1.2.1 /** Unsupported yet. */
53 salcianu 1.1.2.3 public final boolean containsValue(Object value) {
54 salcianu 1.1.2.1 throw new UnsupportedOperationException();
55 salcianu 1.1.2.1 }
56 salcianu 1.1.2.1
57 salcianu 1.1.2.1 /** Returns the value to which this map maps the specified key. */
58 salcianu 1.1.2.1 public final Object get(Object key){
59 salcianu 1.1.2.1 BinTreeNode p = root;
60 salcianu 1.1.2.1 int key_hash_code = key.hashCode();
61 salcianu 1.1.2.1
62 salcianu 1.1.2.1 while(p != null)
63 salcianu 1.1.2.1 if(key_hash_code < p.keyHashCode)
64 salcianu 1.1.2.1 p = p.left;
65 salcianu 1.1.2.1 else
66 salcianu 1.1.2.1 if(key_hash_code > p.keyHashCode)
67 salcianu 1.1.2.1 p = p.right;
68 salcianu 1.1.2.1 else
69 salcianu 1.1.2.1 if(p.key.equals(key))
70 salcianu 1.1.2.1 return p.value;
71 salcianu 1.1.2.1 else p = p.right;
72 salcianu 1.1.2.1
73 salcianu 1.1.2.1 return null;
74 salcianu 1.1.2.1 }
75 salcianu 1.1.2.1
76 salcianu 1.1.2.3
77 salcianu 1.1.2.1 /** Associates the specified value with the specified key in this map. */
78 salcianu 1.1.2.1 public final Object put(Object key, Object value){
79 salcianu 1.1.2.1 BinTreeNode prev = null;
80 salcianu 1.1.2.3 BinTreeNode node = root;
81 salcianu 1.1.2.1 int key_hash_code = key.hashCode();
82 salcianu 1.1.2.2
83 salcianu 1.1.2.3 while(node != null) {
84 salcianu 1.1.2.3 prev = node;
85 salcianu 1.1.2.3 if(key_hash_code < node.keyHashCode)
86 salcianu 1.1.2.3 node = node.left;
87 salcianu 1.1.2.3 else
88 salcianu 1.1.2.3 if((key_hash_code > node.keyHashCode) || !node.key.equals(key))
89 salcianu 1.1.2.3 node = node.right;
90 salcianu 1.1.2.3 else {
91 salcianu 1.1.2.3 Object temp = node.value;
92 salcianu 1.1.2.3 node.value = value;
93 salcianu 1.1.2.3 return temp;
94 salcianu 1.1.2.3 }
95 salcianu 1.1.2.1 }
96 salcianu 1.1.2.1
97 salcianu 1.1.2.1 size++;
98 salcianu 1.1.2.3 hash_code = -1; // invalidate the cached hash code
99 salcianu 1.1.2.1
100 salcianu 1.1.2.3 BinTreeNode new_node = new BinTreeNode(key, value);
101 salcianu 1.1.2.1 if(prev == null){
102 salcianu 1.1.2.3 root = new_node;
103 salcianu 1.1.2.1 return null;
104 salcianu 1.1.2.1 }
105 salcianu 1.1.2.1
106 salcianu 1.1.2.2 if(key_hash_code < prev.keyHashCode)
107 salcianu 1.1.2.3 prev.left = new_node;
108 salcianu 1.1.2.3 else
109 salcianu 1.1.2.3 prev.right = new_node;
110 salcianu 1.1.2.1 return null;
111 salcianu 1.1.2.1 }
112 salcianu 1.1.2.1
113 salcianu 1.1.2.3
114 salcianu 1.1.2.3 /** Removes the mapping previously attached to <code>key</code>.
115 salcianu 1.1.2.3 Returns the old mapping if any, or <code>null</code> otherwise. */
116 salcianu 1.1.2.3 public final Object remove(Object key) {
117 salcianu 1.1.2.3
118 salcianu 1.1.2.3 if(key == null) return null;
119 salcianu 1.1.2.3
120 salcianu 1.1.2.3 int key_hash_code = key.hashCode();
121 salcianu 1.1.2.3 BinTreeNode prev = null;
122 salcianu 1.1.2.3 int son = 0;
123 salcianu 1.1.2.3 BinTreeNode node = root;
124 salcianu 1.1.2.3
125 salcianu 1.1.2.3 while(node != null)
126 salcianu 1.1.2.3 if(key_hash_code < node.keyHashCode) {
127 salcianu 1.1.2.3 prev = node;
128 salcianu 1.1.2.3 node = node.left;
129 salcianu 1.1.2.3 son = 0;
130 salcianu 1.1.2.3 }
131 salcianu 1.1.2.3 else
132 salcianu 1.1.2.3 if((key_hash_code > node.keyHashCode) ||
133 salcianu 1.1.2.3 !node.key.equals(key)) {
134 salcianu 1.1.2.3 prev = node;
135 salcianu 1.1.2.3 node = node.right;
136 salcianu 1.1.2.3 son = 1;
137 salcianu 1.1.2.3 }
138 salcianu 1.1.2.3 else {
139 salcianu 1.1.2.3 size--;
140 salcianu 1.1.2.3 hash_code = -1; // invalidate the cached hash code
141 salcianu 1.1.2.3 return remove_node(node, prev, son);
142 salcianu 1.1.2.3 }
143 salcianu 1.1.2.3 return null;
144 salcianu 1.1.2.3 }
145 salcianu 1.1.2.3
146 salcianu 1.1.2.3 // Remove the BinTreeNode pointed to by node. prev is supposed to be the
147 salcianu 1.1.2.3 // parent node, pointing to node through his left (son == 0) respectively
148 salcianu 1.1.2.3 // right (son == 1) link. Returns the old value attached to node.
149 salcianu 1.1.2.3 private final Object remove_node(BinTreeNode node, BinTreeNode prev,
150 salcianu 1.1.2.3 int son) {
151 salcianu 1.1.2.3 if(node.left == null)
152 salcianu 1.1.2.3 return remove_semi_leaf(node, prev, son, node.right);
153 salcianu 1.1.2.3 if(node.right == null)
154 salcianu 1.1.2.3 return remove_semi_leaf(node, prev, son, node.left);
155 salcianu 1.1.2.3
156 salcianu 1.1.2.3 // The BinTreeNode to replace node in the tree. This is either the
157 salcianu 1.1.2.3 // next or the precedend node (in the order of the hashCode's.
158 salcianu 1.1.2.3 // We decide a bit randomly, to gain some balanceness.
159 salcianu 1.1.2.3 BinTreeNode m =
160 salcianu 1.1.2.3 (node.keyHashCode % 2 == 0) ?
161 salcianu 1.1.2.3 extract_next(node) : extract_prev(node);
162 salcianu 1.1.2.3
163 salcianu 1.1.2.3 return finish_removal(node, prev, son, m);
164 salcianu 1.1.2.3 }
165 salcianu 1.1.2.3
166 salcianu 1.1.2.3
167 salcianu 1.1.2.3 // Remove a [semi]-leaf (a node with at least one of its sons absent.
168 salcianu 1.1.2.3 // In this case, we simply "bypass" the link from the predecessor (if any)
169 salcianu 1.1.2.3 // to the only predecessor of node that could exist.
170 salcianu 1.1.2.3 private final Object remove_semi_leaf(BinTreeNode node, BinTreeNode prev,
171 salcianu 1.1.2.3 int son, BinTreeNode m) {
172 salcianu 1.1.2.3 if(prev == null)
173 salcianu 1.1.2.3 root = m;
174 salcianu 1.1.2.3 else
175 salcianu 1.1.2.3 if(son == 0)
176 salcianu 1.1.2.3 prev.left = m;
177 salcianu 1.1.2.3 else
178 salcianu 1.1.2.3 prev.right = m;
179 salcianu 1.1.2.3
180 salcianu 1.1.2.3 return node.value;
181 salcianu 1.1.2.1 }
182 salcianu 1.1.2.1
183 salcianu 1.1.2.3
184 salcianu 1.1.2.3 // Terminal phase of the node removal. Returns the old value attached to
185 salcianu 1.1.2.3 // node. node, prev and son are as for remove_node; m points to the
186 salcianu 1.1.2.3 // BinTreeNode that should replace node in the tree.
187 salcianu 1.1.2.3 private final Object finish_removal(BinTreeNode node, BinTreeNode prev,
188 salcianu 1.1.2.3 int son, BinTreeNode m) {
189 salcianu 1.1.2.3 if(m != null) { // set up the links for m
190 salcianu 1.1.2.3 m.left = node.left;
191 salcianu 1.1.2.3 m.right = node.right;
192 salcianu 1.1.2.3 }
193 salcianu 1.1.2.3 if(prev == null)
194 salcianu 1.1.2.3 root = m;
195 salcianu 1.1.2.3 else
196 salcianu 1.1.2.3 if(son == 0)
197 salcianu 1.1.2.3 prev.left = m;
198 salcianu 1.1.2.3 else
199 salcianu 1.1.2.3 prev.right = m;
200 salcianu 1.1.2.3
201 salcianu 1.1.2.3 return node.value;
202 salcianu 1.1.2.3 }
203 salcianu 1.1.2.3
204 salcianu 1.1.2.3 // Finds the leftmost BinTreeNode from the right subtree of node;
205 salcianu 1.1.2.3 // removes it from that subtree and returns it.
206 salcianu 1.1.2.3 private final BinTreeNode extract_next(BinTreeNode node) {
207 salcianu 1.1.2.3 BinTreeNode prev = node.right;
208 salcianu 1.1.2.3 BinTreeNode curr = prev.left;
209 salcianu 1.1.2.3
210 salcianu 1.1.2.3 if(curr == null) {
211 salcianu 1.1.2.3 node.right = node.right.right;
212 salcianu 1.1.2.3 return prev;
213 salcianu 1.1.2.3 }
214 salcianu 1.1.2.3
215 salcianu 1.1.2.3 while(curr.left != null) {
216 salcianu 1.1.2.3 prev = curr;
217 salcianu 1.1.2.3 curr = curr.left;
218 salcianu 1.1.2.3 }
219 salcianu 1.1.2.3
220 salcianu 1.1.2.3 prev.left = curr.right;
221 salcianu 1.1.2.3 return curr;
222 salcianu 1.1.2.3 }
223 salcianu 1.1.2.3
224 salcianu 1.1.2.3 // Finds the rightmost BinTreeNode from the left subtree of node;
225 salcianu 1.1.2.3 // removes it from that subtree and returns it.
226 salcianu 1.1.2.3 private final BinTreeNode extract_prev(BinTreeNode node) {
227 salcianu 1.1.2.3 BinTreeNode prev = node.left;
228 salcianu 1.1.2.3 BinTreeNode curr = prev.right;
229 salcianu 1.1.2.3
230 salcianu 1.1.2.3 if(curr == null) {
231 salcianu 1.1.2.3 node.left = node.left.left;
232 salcianu 1.1.2.3 return prev;
233 salcianu 1.1.2.3 }
234 salcianu 1.1.2.3
235 salcianu 1.1.2.3 while(curr.right != null) {
236 salcianu 1.1.2.3 prev = curr;
237 salcianu 1.1.2.3 curr = curr.right;
238 salcianu 1.1.2.3 }
239 salcianu 1.1.2.3
240 salcianu 1.1.2.3 prev.right = curr.left;
241 salcianu 1.1.2.3 return curr;
242 salcianu 1.1.2.3 }
243 salcianu 1.1.2.3
244 salcianu 1.1.2.3
245 salcianu 1.1.2.3 /** Copies all of the mappings from the specified map to this map. */
246 salcianu 1.1.2.1 public final void putAll(Map map) throws UnsupportedOperationException{
247 cananian 1.3 for(Object entryO : map.entrySet()) {
248 cananian 1.3 Map.Entry entry = (Map.Entry) entryO;
249 salcianu 1.1.2.3 put(entry.getKey(), entry.getValue());
250 salcianu 1.1.2.3 }
251 salcianu 1.1.2.1 }
252 salcianu 1.1.2.1
253 salcianu 1.1.2.3
254 salcianu 1.1.2.3 /** Removes all mappings from this map. */
255 salcianu 1.1.2.1 public final void clear() throws UnsupportedOperationException{
256 salcianu 1.1.2.3 size = 0;
257 salcianu 1.1.2.3 hash_code = -1;
258 salcianu 1.1.2.3 root = null;
259 salcianu 1.1.2.1 }
260 salcianu 1.1.2.1
261 salcianu 1.1.2.1 /** Returns a collection view of the values contained in this map. */
262 salcianu 1.1.2.1 public final Collection values(){
263 salcianu 1.1.2.3 final Collection vals = new LinkedList();
264 salcianu 1.1.2.3 get_values(root, vals);
265 salcianu 1.1.2.3 return vals;
266 salcianu 1.1.2.1 }
267 salcianu 1.1.2.1
268 salcianu 1.1.2.1 // recursively explore the tree of mappings and gather all the
269 salcianu 1.1.2.1 // values in the set vset
270 salcianu 1.1.2.1 private static final void get_values(final BinTreeNode node,
271 salcianu 1.1.2.3 final Collection vals){
272 salcianu 1.1.2.1 if(node == null) return;
273 salcianu 1.1.2.3 vals.add(node.value);
274 salcianu 1.1.2.3 get_values(node.left, vals);
275 salcianu 1.1.2.3 get_values(node.right, vals);
276 salcianu 1.1.2.1 }
277 salcianu 1.1.2.1
278 salcianu 1.1.2.2 /** Returns the set of entries of this map. The result is a
279 salcianu 1.1.2.2 <code>Set</code> of <code>Map.Entry</code>. */
280 salcianu 1.1.2.3 public final Set entrySet() throws UnsupportedOperationException {
281 salcianu 1.1.2.1 final Set eset = new HashSet();
282 salcianu 1.1.2.2 get_entries(root, eset);
283 salcianu 1.1.2.1 return eset;
284 salcianu 1.1.2.1 }
285 salcianu 1.1.2.1
286 salcianu 1.1.2.1 // recursively explore the tree of mappings and gather all the
287 salcianu 1.1.2.1 // entries in the set eset
288 salcianu 1.1.2.1 private static final void get_entries(final BinTreeNode node,
289 salcianu 1.1.2.3 final Set eset) {
290 salcianu 1.1.2.1 if(node == null) return;
291 salcianu 1.1.2.3 eset.add(new Entry(node));
292 salcianu 1.1.2.1 get_entries(node.left, eset);
293 salcianu 1.1.2.1 get_entries(node.right, eset);
294 salcianu 1.1.2.1 }
295 salcianu 1.1.2.1
296 salcianu 1.1.2.3 private static class Entry implements Map.Entry {
297 salcianu 1.1.2.1 Object key;
298 salcianu 1.1.2.1 Object value;
299 salcianu 1.1.2.3 BinTreeNode node; // the node behind this entry
300 salcianu 1.1.2.1
301 salcianu 1.1.2.3 Entry(BinTreeNode node){
302 salcianu 1.1.2.3 this.node = node;
303 salcianu 1.1.2.3 this.key = node.key;
304 salcianu 1.1.2.3 this.value = node.value;
305 salcianu 1.1.2.1 }
306 salcianu 1.1.2.1
307 salcianu 1.1.2.3 public Object getKey() { return node.key; }
308 salcianu 1.1.2.3 public Object getValue() { return node.value; }
309 salcianu 1.1.2.1
310 salcianu 1.1.2.3 public Object setValue(Object value) {
311 salcianu 1.1.2.3 Object old_value = node.value;
312 salcianu 1.1.2.3 node.value = value;
313 salcianu 1.1.2.3 this.value = value;
314 salcianu 1.1.2.3 return old_value;
315 salcianu 1.1.2.1 }
316 salcianu 1.1.2.1
317 salcianu 1.1.2.1 public boolean equals(Object o){
318 salcianu 1.1.2.3 if(this == o) return true;
319 salcianu 1.1.2.3 if(!(o instanceof Map.Entry)) return false;
320 salcianu 1.1.2.3
321 salcianu 1.1.2.3 Map.Entry e2 = (Map.Entry) o;
322 salcianu 1.1.2.3 return
323 salcianu 1.1.2.3 key.equals(e2.getKey()) &&
324 salcianu 1.1.2.3 value.equals(e2.getValue());
325 salcianu 1.1.2.1 }
326 salcianu 1.1.2.1
327 salcianu 1.1.2.1 public int hashCode(){
328 salcianu 1.1.2.1 return key.hashCode() + value.hashCode();
329 salcianu 1.1.2.1 }
330 salcianu 1.1.2.3
331 salcianu 1.1.2.3 public String toString() {
332 salcianu 1.1.2.3 return "<" + key + "," + value + ">";
333 salcianu 1.1.2.3 }
334 salcianu 1.1.2.1 }
335 salcianu 1.1.2.1
336 salcianu 1.1.2.3
337 salcianu 1.1.2.3 /** Returns a set view of the keys contained in this map. Unlike the
338 salcianu 1.1.2.3 <code>java.util</code> maps, this set is NOT backed by the map
339 salcianu 1.1.2.3 (<i>eg</i> removing a key from the returned set has no effect on
340 salcianu 1.1.2.3 the map). */
341 salcianu 1.1.2.3 public final Set keySet() {
342 salcianu 1.1.2.3 final Set kset = new HashSet();
343 salcianu 1.1.2.3 get_keys(root, kset);
344 salcianu 1.1.2.3 return kset;
345 salcianu 1.1.2.3 }
346 salcianu 1.1.2.3
347 salcianu 1.1.2.3 // recursively explore the tree of mappings and gather all the
348 salcianu 1.1.2.3 // keys in the set kset
349 salcianu 1.1.2.3 private static final void get_keys(final BinTreeNode node,
350 salcianu 1.1.2.3 final Set kset) {
351 salcianu 1.1.2.3 if(node == null) return;
352 salcianu 1.1.2.3 kset.add(node.key);
353 salcianu 1.1.2.3 get_keys(node.left, kset);
354 salcianu 1.1.2.3 get_keys(node.right, kset);
355 salcianu 1.1.2.3 }
356 salcianu 1.1.2.3
357 salcianu 1.1.2.3
358 salcianu 1.1.2.3 private BinTreeNode copy_tree(BinTreeNode node) {
359 salcianu 1.1.2.3 if(node == null) return null;
360 salcianu 1.1.2.3 BinTreeNode newnode = new BinTreeNode(node.key, node.value);
361 salcianu 1.1.2.3
362 salcianu 1.1.2.3 newnode.left = copy_tree(node.left);
363 salcianu 1.1.2.3 newnode.right = copy_tree(node.right);
364 salcianu 1.1.2.3
365 salcianu 1.1.2.3 return newnode;
366 salcianu 1.1.2.3 }
367 salcianu 1.1.2.3
368 salcianu 1.1.2.3
369 salcianu 1.1.2.3 public Object clone() {
370 salcianu 1.1.2.3 try {
371 salcianu 1.1.2.3 LightMap newmap = (LightMap) super.clone();
372 salcianu 1.1.2.3 newmap.root = copy_tree(root);
373 salcianu 1.1.2.3 return newmap;
374 salcianu 1.1.2.3 } catch(CloneNotSupportedException e) {
375 salcianu 1.1.2.3 throw new InternalError();
376 salcianu 1.1.2.3 }
377 salcianu 1.1.2.1 }
378 salcianu 1.1.2.1
379 salcianu 1.1.2.1
380 salcianu 1.1.2.3 public boolean equals(Object o) {
381 salcianu 1.1.2.3 if(this == o) return true;
382 salcianu 1.1.2.4 if(!(o instanceof Map))
383 salcianu 1.1.2.3 return false;
384 salcianu 1.1.2.3
385 salcianu 1.1.2.3 Map m2 = (Map) o;
386 salcianu 1.1.2.3
387 salcianu 1.1.2.3 Set set1 = this.entrySet();
388 salcianu 1.1.2.3 Set set2 = m2.entrySet();
389 salcianu 1.1.2.3
390 salcianu 1.1.2.3 // two maps are equal if they have the same set of entries
391 salcianu 1.1.2.3 return set1.equals(set2);
392 salcianu 1.1.2.3 }
393 salcianu 1.1.2.1
394 salcianu 1.1.2.3
395 salcianu 1.1.2.3 public int hashCode() {
396 salcianu 1.1.2.3 if(hash_code == -1)
397 salcianu 1.1.2.3 hash_code = compute_hash_code(root);
398 salcianu 1.1.2.3 return hash_code;
399 salcianu 1.1.2.3 }
400 salcianu 1.1.2.3
401 salcianu 1.1.2.3 private int hash_code = -1;
402 salcianu 1.1.2.3
403 salcianu 1.1.2.3 private int compute_hash_code(BinTreeNode node) {
404 salcianu 1.1.2.3 if(node == null) return 0;
405 salcianu 1.1.2.3
406 salcianu 1.1.2.3 return
407 salcianu 1.1.2.3 node.keyHashCode +
408 salcianu 1.1.2.3 compute_hash_code(node.left) +
409 salcianu 1.1.2.3 compute_hash_code(node.right);
410 salcianu 1.1.2.3 }
411 salcianu 1.1.2.3
412 salcianu 1.1.2.5 private static class BinTreeNode implements java.io.Serializable {
413 salcianu 1.1.2.1 final Object key;
414 salcianu 1.1.2.3 Object value;
415 salcianu 1.1.2.1 final int keyHashCode;
416 salcianu 1.1.2.1
417 salcianu 1.1.2.1 BinTreeNode left;
418 salcianu 1.1.2.1 BinTreeNode right;
419 salcianu 1.1.2.1
420 salcianu 1.1.2.3 BinTreeNode(final Object key, final Object value) {
421 salcianu 1.1.2.1 this.key = key;
422 salcianu 1.1.2.1 this.value = value;
423 salcianu 1.1.2.1 keyHashCode = key.hashCode();
424 salcianu 1.1.2.1 left = null;
425 salcianu 1.1.2.1 right = null;
426 salcianu 1.1.2.1 }
427 salcianu 1.1.2.3
428 salcianu 1.1.2.3 public String toString() {
429 salcianu 1.1.2.3 return "<" + key + "," + value + ">";
430 salcianu 1.1.2.3 }
431 salcianu 1.1.2.3 }
432 salcianu 1.1.2.3
433 salcianu 1.1.2.3
434 salcianu 1.1.2.3 public String toString() {
435 salcianu 1.1.2.3 StringBuffer buffer = new StringBuffer();
436 salcianu 1.1.2.3 buffer.append("[");
437 salcianu 1.1.2.3 build_str(root, buffer);
438 salcianu 1.1.2.3 buffer.append(" ]");
439 salcianu 1.1.2.3 return buffer.toString();
440 salcianu 1.1.2.3 }
441 salcianu 1.1.2.3
442 salcianu 1.1.2.3 private void build_str(final BinTreeNode node, final StringBuffer buffer) {
443 salcianu 1.1.2.3 if(node == null) return;
444 salcianu 1.1.2.3 build_str(node.left, buffer);
445 salcianu 1.1.2.3 buffer.append(" <" + node.key + "," + node.value + ">");
446 salcianu 1.1.2.3 build_str(node.right, buffer);
447 salcianu 1.1.2.1 }
448 salcianu 1.1.2.1
449 cananian 1.2 }