1 package fr.ove.openmath.jome.model;
2
3 import java.util.*;
4 import java.io.Serializable;
5
6
7 /***
8 * Definition of a N-ary tree structure.
9 *
10 * @author © 1999 DIRAT Laurent
11 * @version 2.0 23/06/1999
12 */
13 public abstract class Node implements Serializable, Cloneable {
14 /***
15 * The father of the instance in the tree structure
16 */
17 private Node father;
18
19 /***
20 * The children of the instance in the tree structure
21 */
22 private Vector children;
23
24 /***
25 * The rank of the instance in the set of its father's children
26 */
27 private int rank;
28
29 /***
30 * The strahler number of the node
31 */
32 private int nbStrahler;
33
34 /***
35 * The depth of the node in the tree structure.
36 * It corresponds in fact at the number of its ancestors. (so root.depth == 0)
37 */
38 private int depth;
39
40
41 /***
42 * The Constructor.
43 */
44 public Node() {
45 father = null;
46 rank = 0;
47 nbStrahler = 1;
48 depth = 0;
49 }
50
51
52
53 /***
54 * Returns the father of the instance.
55 *
56 * @return the father of the node.
57 */
58 public Node getFather() {
59 return father;
60 }
61
62 /***
63 * Returns the rank of the instance in the set of its father's children
64 *
65 * @return the rank of the node.
66 */
67 public int getRank() {
68 return rank;
69 }
70
71 /***
72 * Returns the child of the instance at the specified rank.
73 *
74 * @param rank the specified rank.
75 * @return the child at the specified rank.
76 */
77 public Node getChild(int rank) {
78 Node child = null;
79
80 if (children != null) {
81 try {
82 child = (Node) children.elementAt(rank);
83 }
84 catch (ArrayIndexOutOfBoundsException e) {
85 return null;
86 }
87 }
88
89 return child;
90 }
91
92 /***
93 * Returns the number of children of the instance.
94 */
95 public int getNbChildren() {
96 int size = 0;
97
98 if (children != null)
99 size = children.size();
100
101 return size;
102 }
103
104 /***
105 * Returns the list of children of the instance.
106 *
107 * @return the list of children
108 */
109 public Vector getChildren() {
110 return children;
111 }
112
113
114
115 /***
116 * Sets a father to instance.
117 *
118 * @param father the father to set
119 */
120 public void setFather(Node father) {
121 this.father = father;
122 depth = father.depth + 1;
123
124
125 if (children != null)
126 adjustChildrenDepth();
127 }
128
129 /***
130 * Adds a child to the instance.<BR>
131 * The child added is the last of the list.
132 *
133 * @param child the child to add.
134 */
135 public void addChild(Node child) {
136 if (children == null)
137 children = new Vector(0, 1);
138
139 children.addElement(child);
140 child.setFather(this);
141 adjustRank();
142 }
143
144 /***
145 * Adds a child to the instance.<BR>
146 * The child is added at the specified rank.
147 *
148 * @param child the child to add.
149 * @param rank the specified rank.
150 */
151 public void addChild(Node child, int rank) {
152 if (children == null)
153 children = new Vector(0, 1);
154
155 children.insertElementAt(child, rank);
156 child.setFather(this);
157 adjustRank();
158 }
159
160 /***
161 * Removes the child of the current node at the specified rank.
162 *
163 * @param rank the rank of the child to remove.
164 */
165 public void removeChild(int rank) {
166 if (children != null) {
167 children.removeElementAt(rank);
168 adjustRank();
169 }
170 }
171
172 /***
173 * Removes the specified child of the instance.
174 *
175 * @param node the child to remove.
176 */
177 public void removeChild(Node node) {
178 if (children != null) {
179 children.removeElement(node);
180 adjustRank();
181 }
182 }
183
184 /***
185 * Remove all the children of the instance.
186 */
187 public void removeAll() {
188 if (children != null) {
189 int count = children.size();
190 for (int i = 0; i < count; i++)
191 ((Node) children.elementAt(rank)).father = null;
192
193 children.setSize(0);
194 children.trimToSize();
195 }
196 }
197
198 /***
199 * Sets the rank of the children of the instance.
200 */
201 private void adjustRank() {
202 int i = 0;
203
204 for (Enumeration e = children.elements(); e.hasMoreElements(); i++)
205 ((Node) e.nextElement()).rank = i;
206 }
207
208 /***
209 * Changes the rank of the instance.
210 *
211 * @param rank the new rank.
212 */
213 private void changeRank(int rank) {
214 int oldRank = this.rank;
215
216
217 if (rank > father.getNbChildren()) {
218 rank = father.getNbChildren() + 1;
219 father.addChild(this);
220 }
221 else {
222 if (rank < 0)
223 rank = 0;
224 father.addChild(this, rank);
225 }
226
227
228 if (rank < oldRank)
229 father.removeChild(oldRank + 1);
230 else
231 father.removeChild(oldRank);
232 }
233
234 /***
235 * Moves the specified list of the instance children to the specified
236 * rank. The first child in the list has its rank setted to the specified
237 * one, the second to the first+1, ...and so on.
238 * @param list the list of the instance children.
239 * @param rank the specified rank.
240 */
241 public void moveChildren(Vector list, int rank) {
242
243
244 int NbChildren = children.size();
245 Node child = null;
246 Node first = null;
247
248 for (int i = 0; i < list.size(); i++) {
249 child = (Node) list.elementAt(i);
250 if (i == 0)
251 first = child;
252 if (rank > NbChildren)
253 child.changeRank(rank + (i+1));
254 else {
255 child.changeRank(rank);
256 rank = first.getRank() + (i+1);
257 }
258 }
259 }
260
261 /***
262 * Checks if the specified node is a child of the current instance.
263 * @param node the specified node.
264 * @return <CODE>true</CODE> if the specified node is a child of the current
265 * instance. <CODE>false</CODE> otherwise.
266 */
267 public boolean hasChild(Node node) {
268 boolean hasChild = false;
269
270 if (children != null)
271 hasChild = children.contains(node);
272
273 return hasChild;
274 }
275
276 /***
277 * Clones (copies) the instance.<BR>
278 * Make a deep clone, i.e. the children of the instance are also cloned.<BR>
279 * Nevertheless, the father of the clone is set to <CODE>null</CODE>.
280 */
281 public synchronized Object clone(){
282 Node theClone = null;
283 try {
284
285
286
287 theClone = (Node) super.clone();
288
289 theClone.father = null;
290 if (children != null) {
291
292 Vector theChildren = new Vector();
293 int count = children.size();
294 for (int i = 0; i < count; i++)
295 theChildren.addElement(((Node) children.elementAt(i)).clone());
296 theClone.children = theChildren;
297 }
298
299 } catch (CloneNotSupportedException e) {
300 System.out.println("clone failed !!");
301 }
302
303 return theClone;
304 }
305
306 /***
307 * Duplicates (copies) the instance.<BR>
308 * The difference with clone, is a deep copy is not performed.<BR>
309 * The father of the duplicate is set to <CODE>null</CODE>.
310 */
311 public synchronized Object duplicate(){
312 Node theClone = null;
313 try {
314
315 theClone = (Node) super.clone();
316
317 theClone.father = null;
318
319 theClone.children = new Vector();
320 } catch (CloneNotSupportedException e) {
321 System.out.println("duplicate failed !!");
322 }
323
324 return theClone;
325 }
326
327
328
329
330
331
332
333
334
335
336
337
338 /***
339 * Returns the depth of the node.
340 */
341 public int getDepth() {
342 return depth;
343 }
344
345 /***
346 * Compute the depth of the node.
347 */
348 public void computeDepth() {
349 int theDepth = 0;
350 Node theFather = father;
351
352 while (theFather != null) {
353 theDepth++;
354 theFather = theFather.father;
355 }
356
357 depth = theDepth;
358
359
360 if (children != null)
361 adjustChildrenDepth();
362 }
363
364 /***
365 * Adjusts the depth of the children of the node.
366 */
367 private void adjustChildrenDepth() {
368 Node child = null;
369 int count = children.size();
370 for (int i = 0; i < count; i++) {
371 child = (Node) children.elementAt(i);
372
373 child.depth = depth + 1;
374
375
376 if (child.children != null)
377 child.adjustChildrenDepth();
378 }
379 }
380
381
382
383
384
385 /***
386 * Returns the strahler number of the node.
387 */
388 public int getNbStrahler() {
389 return nbStrahler;
390 }
391
392 /***
393 * Sets the Strahler number of the instance.<BR>
394 * !!! ATTENTION !!! : should not be called at any time.
395 * Just specific cases only, above all, when you know what you are doing.
396 * @param nbStrahler the Strahler number value to set.
397 */
398 public void setNbStrahler(int nbStrahler) {
399 this.nbStrahler = nbStrahler;
400 }
401
402 /***
403 * Computes the strahler number of the node.
404 * Prerequisite : the strahler number of the children of the instance are computed.
405 */
406 private void computeNodeNbStrahler() {
407
408
409 if (children != null) {
410 int count = children.size();
411 if (count == 0)
412
413 nbStrahler = 1;
414 else if (count == 1)
415 nbStrahler = ((Node) children.elementAt(0)).nbStrahler;
416 else {
417 int max = 0;
418 int min = Integer.MAX_VALUE;
419
420 int tmpStrahler;
421
422 for (int i = 0; i < count; i++) {
423 tmpStrahler = ((Node) children.elementAt(i)).nbStrahler;
424 min = (min < tmpStrahler) ? min : tmpStrahler;
425 max = (max > tmpStrahler) ? max : tmpStrahler;
426 }
427
428 int tabLength = max - min + 1;
429 int tabValue[] = new int[tabLength];
430
431 for (int i = 0; i < tabLength; i++)
432 tabValue[i] = 0;
433
434 for (int i = 0; i < count; i++)
435 tabValue[((Node) children.elementAt(i)).nbStrahler - min] += 1;
436
437 int free = max - 1;
438 tmpStrahler = max + tabValue[tabLength - 1] - 1;
439
440 int requiered;
441 for (int i = tabLength - 2; i >= 0; i--) {
442 if (tabValue[i] == 0)
443 continue;
444
445 requiered = i + min + tabValue[i] - 1;
446
447 if (free > requiered)
448 free -= tabValue[i];
449 else {
450 tmpStrahler += requiered - free;
451 free = i + min - 1;
452 }
453 }
454
455 nbStrahler = tmpStrahler;
456 }
457 }
458 }
459
460 /***
461 * Computes the strahler number of the tree whose the instance is the root
462 */
463 public void computeNbStrahler() {
464 if (children != null) {
465 int count = children.size();
466 for (int i = 0; i < count; i++)
467 ((Node) children.elementAt(i)).computeNbStrahler();
468
469 computeNodeNbStrahler();
470 }
471 }
472 }