1 /*
2 * Copyright (c) 2002, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 package gc.gctests.gctest03;
25
26 class DataNodeException extends Exception
27 {
28 }
29
30
31 class DataNode {
32 int key;
33 int buf[];
34 static int dataNodeCount = 0;
35 static int dataNodeLimit;
36
37 static synchronized void incDataNodeCount()
38 {
39 dataNodeCount++;
40 }
41
42 static synchronized int getDataNodeCount()
43 {
44 return dataNodeCount;
45 }
46
47 static synchronized void setDataNodeLimit(int newLimit)
48 {
49 dataNodeLimit = newLimit;
50 }
51
52 static synchronized int getDataNodeLimit()
53 {
54 return dataNodeLimit;
55 }
56
57 static synchronized void clearDataNodeCount()
58 {
59 dataNodeCount = 0;
60 }
61 DataNode(int key) throws DataNodeException
62 {
63
64 incDataNodeCount();
65 if (getDataNodeCount() > getDataNodeLimit())
66 {
67 throw (new DataNodeException());
68 }
69
70 this.key = key;
71 try {
72 buf = new int[key];
73 }
74 catch ( OutOfMemoryError e )
75 {
76 System.out.println(Thread.currentThread().getName() + " : outofmemory");
77 }
78 }
79
80 public void print()
81 {
82 System.out.println(key);
83 }
84
85 public boolean equals(DataNode d)
86 {
87 int k = d.getkey();
88
89 return ( key == k);
90 }
91
92 public boolean large(DataNode d)
93 {
94 int k = d.getkey();
95
96 return ( key > k);
97 }
98
99 public boolean less(DataNode d)
100
101 {
102 int k = d.getkey();
103
104 return ( key < k);
105 }
106
107 public int getkey()
108 { return key; }
109 }
110
111
112 class TreeNode {
113 DataNode data;
114 TreeNode parent;
115 TreeNode left;
116 TreeNode right;
117
118 TreeNode(DataNode key)
119 {
120 this.data = key;
121 parent = null;
122 left = null;
123 right = null;
124 }
125
126 public void print()
127 {
128 data.print();
129 }
130
131 public TreeNode getleft()
132 {
133 return left;
134 }
135
136 public TreeNode getright()
137 {
138 return right;
139 }
140
141 public TreeNode getparent()
142 {
143 return parent;
144 }
145
146 public synchronized void setleft(TreeNode left)
147 {
148 this.left = left;
149 }
150
151 public synchronized void setright(TreeNode right)
152 {
153 this.right = right;
154 }
155
156 public synchronized void setparent(TreeNode parent)
157 {
158 this.parent = parent;
159 }
160
161 public DataNode getData()
162 {
163 return data;
164 }
165
166 // print it out in order of a large one first
167 public void sprint()
168 {
169 //print itself
170 if ( left != null ) left.sprint();
171 System.out.println(data.getkey());
172 if ( right != null ) right.sprint();
173 }
174
175 // print it out in order of a small one first
176 public void lprint()
177 {
178 if (right != null ) right.lprint();
179 System.out.println(data.getkey());
180 if ( left != null ) left.lprint();
181 }
182
183 public synchronized TreeNode duplicate()
184 {
185 TreeNode tp = new TreeNode(data);
186
187 if ( left != null )
188 {
189 tp.left = left.duplicate();
190 }
191 if ( right != null )
192 {
193 tp.right = right.duplicate();
194 }
195 return tp;
196 }
197
198 public TreeNode search(DataNode d)
199 {
200 TreeNode tp = this;
201 DataNode k;
202
203 while ( tp != null )
204 {
205 k = tp.getData();
206 if ( k.equals(d) )
207 {
208 return tp;
209 }
210 else
211 if ( d.large(k) )
212 tp = tp.getright();
213 else
214 tp = tp.getleft();
215 }
216 return null;
217 }
218
219 public synchronized void insert(TreeNode t)
220 {
221 DataNode d = t.getData();
222
223 TreeNode tp = this;
224 TreeNode tp1 = tp;
225 DataNode d0;
226
227 while ( true )
228 {
229 d0 = tp.getData();
230
231 if ( d.large(d0) )
232 {
233 tp1 = tp;
234 tp = tp.getright();
235 if ( tp == null )
236 {
237 tp1.setright(t);
238 t.setparent(tp1);
239 break;
240 }
241 }
242 else
243 {
244 tp1 = tp;
245 tp = tp.getleft();
246 if (tp == null )
247 {
248 tp1.setleft(t);
249 t.setparent(tp1);
250 break;
251 }
252 }
253 }
254
255 }
256
257
258 }
259
260
261 class Tree {
262 TreeNode root = null;
263
264 Tree()
265 {
266 root = null;
267 }
268
269 Tree(TreeNode root)
270 {
271 this.root = root;
272 }
273
274 public synchronized void insert(TreeNode t)
275 {
276 if ( root == null )
277 {
278 root = t;
279 return;
280 }
281
282 root.insert(t);
283 }
284
285
286 public void sort1()
287 {
288 root.sprint();
289 }
290
291 public void sort2()
292 {
293 root.lprint();
294 }
295
296 public TreeNode search(DataNode d)
297 {
298 if ( root == null ) return null;
299 else return root.search(d);
300 }
301
302 public synchronized boolean remove(DataNode d)
303 {
304 if ( root == null ) return false;
305
306 TreeNode t = root.search(d);
307
308 // data is not in a heap
309 if ( t == null ) return false;
310
311 /*
312 if ( d.equals(t.getData()) == false )
313 {
314 System.out.println("failed");
315 return false;
316 }
317 */
318
319 TreeNode p = t.getparent();
320 TreeNode l = t.getleft();
321 TreeNode r = t.getright();
322
323 // the removed node is a root
324 if ( p == null )
325 {
326 if ( l == null && r != null )
327 {
328 r.setparent(null);
329 root = r;
330 return true;
331 }
332 if ( l != null && r == null )
333 {
334 l.setparent(null);
335 root = l;
336 return true;
337 }
338 if ( l == null && r == null )
339 {
340 root = null;
341 return true;
342 }
343
344 if ( l != null && r != null )
345 {
346 r.setparent(null);
347 r.insert(l);
348 root = r;
349 return true;
350 }
351 }
352
353 // a leaf
354 if ( r == null && l == null )
355 {
356 if ( p.getright() == t )
357 {
358 /* right child */
359 p.setright(null);
360 }
361 else
362 p.setleft(null);
363 return true;
364 }
365
366 // a node without left child
367 if ( r != null && l == null )
368 {
369 r.setparent(p);
370 if ( t == p.getright() ) p.setright(r);
371 if ( t == p.getleft() ) p.setleft(r);
372 return true;
373 }
374
375 if ( r == null && l != null )
376 {
377 l.setparent(p);
378 if ( t == p.getright() ) p.setright(l);
379 if ( t == p.getleft() ) p.setleft(l);
380 return true;
381 }
382
383 // a node with two children
384 r.insert(l);
385 r.setparent(p);
386 if ( t == p.getright() ) p.setright(r);
387 if ( t == p.getleft() ) p.setleft(r);
388 return true;
389 }
390
391 public synchronized Tree copy()
392 {
393 if ( root == null ) return null;
394
395 return(new Tree(root.duplicate()));
396 }
397
398 public synchronized boolean isempty()
399 {
400 return ( root == null );
401 }
402
403
404 }