001: /*
002: * Copyright (c) 2001 Silvere Martin-Michiellot All Rights Reserved.
003: *
004: * Silvere Martin-Michiellot grants you ("Licensee") a non-exclusive,
005: * royalty free, license to use, modify and redistribute this
006: * software in source and binary code form,
007: * provided that i) this copyright notice and license appear on all copies of
008: * the software; and ii) Licensee does not utilize the software in a manner
009: * which is disparaging to Silvere Martin-Michiellot.
010: *
011: * This software is provided "AS IS," without a warranty of any kind. ALL
012: * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING ANY
013: * IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE OR
014: * NON-INFRINGEMENT, ARE HEREBY EXCLUDED. Silvere Martin-Michiellot
015: * AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY DAMAGES
016: * SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING
017: * OR DISTRIBUTING THE SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL
018: * Silvere Martin-Michiellot OR ITS LICENSORS BE LIABLE
019: * FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT,
020: * INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER
021: * CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF
022: * OR INABILITY TO USE SOFTWARE, EVEN IF Silvere Martin-Michiellot HAS BEEN
023: * ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
024: *
025: * This software is not designed or intended for use in on-line control of
026: * aircraft, air traffic, aircraft navigation or aircraft communications; or in
027: * the design, construction, operation or maintenance of any nuclear
028: * facility. Licensee represents and warrants that it will not use or
029: * redistribute the Software for such purposes.
030: *
031: * @Author: Silvere Martin-Michiellot
032: *
033: */
034:
035: package com.db.utils.tree;
036:
037: /**
038: * Implements the basic algorithmic Tree. Children are stored in a HashSet. Different Tree nodes in the same Tree can reference the same element. A Tree can have a Tree stored as element in its node. This kind of internal Tree won't be considered as a sub Tree. Tree is not synchronized (beware on multiple additions for example which could lead a node to be the child a more than one node).
039: */
040:
041: import java.util.*;
042:
043: public class Tree extends Object {
044:
045: Tree parent;
046: Object element;
047: HashSet children;
048:
049: public Tree(Object element) {
050:
051: if (element != null) {
052: this .element = element;
053: this .children = new HashSet();
054: } else {
055: throw new java.lang.IllegalArgumentException(
056: "Tree node must contain an element.");
057: }
058:
059: }
060:
061: public Object getElement() {
062:
063: return element;
064:
065: }
066:
067: public void setElement(Object element) {
068:
069: if (element != null) {
070: this .element = element;
071: } else {
072: throw new java.lang.IllegalArgumentException(
073: "Tree node must contain an element.");
074: }
075:
076: }
077:
078: //returns the parent Tree of this Tree if one exists or null (if this is the top node).
079: public Tree getParent() {
080:
081: if (this .parent != null) {
082: return this .parent;
083: } else {
084: return null;
085: }
086:
087: }
088:
089: public Tree[] getParents() {
090:
091: Tree[] parents;
092: Tree aTree;
093: int i;
094:
095: i = 0;
096: aTree = this .getParent();
097:
098: while (aTree != null) {
099: aTree = aTree.getParent();
100: i++;
101: }
102:
103: parents = new Tree[i];
104: aTree = this .getParent();
105:
106: while (aTree != null) {
107: aTree = aTree.getParent();
108: parents[i] = aTree;
109: }
110:
111: return parents;
112:
113: }
114:
115: public Tree getTopNode() {
116:
117: Tree aTree;
118: Tree anotherTree;
119:
120: aTree = this .getParent();
121: anotherTree = null;
122:
123: while (aTree != null) {
124: anotherTree = aTree;
125: aTree = aTree.getParent();
126: }
127:
128: return anotherTree;
129:
130: }
131:
132: //see also reParent (Tree newParent)
133: private void setParent(Tree parent) {
134:
135: this .parent = parent;
136:
137: }
138:
139: public boolean isParent(Tree parent) {
140:
141: return (this .getParent() == parent);
142:
143: }
144:
145: //checks if parent is a direct or indirect parent of this Tree node
146: public boolean isDistantParent(Tree parent) {
147:
148: Tree aTree;
149: boolean found;
150:
151: aTree = this .getParent();
152: found = (aTree == parent);
153:
154: while ((aTree != null) && (!found)) {
155: aTree = aTree.getParent();
156: found = (aTree == parent);
157: }
158:
159: return found;
160:
161: }
162:
163: public boolean canReparent(Tree newParent) {
164:
165: return ((this != newParent) && (!isDistantChild(newParent)));
166:
167: }
168:
169: //moves the Tree (with its children) somewhere else in the hierarchy.
170: //newParent mustn't be one of the children of this Tree (or Tree itself)
171: public void reParent(Tree newParent) throws CyclicTreeException {
172:
173: if (canReparent(newParent)) {
174: this .parent = newParent;
175: } else {
176: throw new CyclicTreeException(
177: "Can't reParent newParent because it is a child of this Tree node or this Tree node itself.");
178: }
179:
180: }
181:
182: public boolean isPeer(Tree aTree) {
183:
184: Tree[] peers;
185: int i;
186: boolean found;
187:
188: peers = this .getPeers();
189: found = false;
190: i = 0;
191:
192: while ((i < peers.length) && (!found)) {
193: found = (peers[i] == aTree);
194: i++;
195: }
196:
197: return found;
198:
199: }
200:
201: public Tree[] getPeers() {
202:
203: Tree[] parents;
204:
205: parents = this .getParents();
206:
207: return getTreesAtLevel(parents.length);
208:
209: }
210:
211: //level 0 for top Node
212: //i>=0
213: private Tree[] getTreesAtLevel(int i) {
214:
215: Iterator iterator;
216: Tree[] aTreeArray;
217: Tree[] anotherTreeArray;
218: Tree aTree;
219: int j, k, l;
220:
221: aTree = this .getTopNode();
222: anotherTreeArray = new Tree[0];
223: anotherTreeArray[0] = aTree;
224:
225: while (i > 0) {
226: aTreeArray = anotherTreeArray;
227: k = 0;
228: for (j = 0; j < aTreeArray.length; j++) {
229: k = k + aTreeArray[j].getNumChildren();
230: }
231: anotherTreeArray = new Tree[k];
232: k = 0;
233: for (j = 0; j < aTreeArray.length; j++) {
234: iterator = aTreeArray[j].getChildren();
235: for (l = 0; l < aTreeArray[j].getNumChildren(); l++) {
236: k = k + 1;
237: anotherTreeArray[k] = (Tree) iterator.next();
238: }
239: k = k + aTreeArray[j].getNumChildren();
240:
241: }
242: i = i - 1;
243: }
244:
245: return anotherTreeArray;
246:
247: }
248:
249: //hasChildren == !isLeaf() (not implemented for this reason)
250: public boolean hasChildren() {
251:
252: return !(this .children.isEmpty());
253:
254: }
255:
256: public Iterator getChildren() {
257:
258: return this .children.iterator();
259:
260: }
261:
262: public int getNumChildren() {
263:
264: //Iterator iterator;
265: //int i;
266: //Object object;
267:
268: //iterator = this.children.iterator();
269: //i=0;
270:
271: //while (iterator.hasNext()) {
272: //object = iterator.next();
273: //i++;
274: //}
275:
276: //return i;
277:
278: return this .children.size();
279:
280: }
281:
282: //child must not be a parent
283: //child must not be a direct or indirect children
284: public void addChild(Tree child) throws CyclicTreeException {
285:
286: if ((this != child) && (!isDistantChild(child))) {
287: this .children.add(child);
288: child.setParent(this );
289: } else {
290: throw new CyclicTreeException(
291: "Can't addChild to this Tree because it is a child of this Tree node or this Tree node itself.");
292: }
293:
294: }
295:
296: //checks if child is a direct child of this Tree node
297: public boolean isChild(Tree child) {
298:
299: return this .children.contains(child);
300:
301: }
302:
303: //checks if child is a direct child of this Tree node
304: //isChild is always true when isDistantChild is true
305: public boolean isDistantChild(Tree child) {
306:
307: Tree aTree;
308: Iterator iterator;
309: boolean found;
310:
311: found = false;
312: iterator = this .getChildren();
313:
314: while (iterator.hasNext() && (!found)) {
315: aTree = (Tree) iterator.next();
316: found = ((aTree == child) || (aTree.isDistantChild(child)));
317: }
318:
319: return found;
320:
321: }
322:
323: //child must be one of the direct children (if not nothing happens)
324: //child is deleted and ressources are freed (if you don't want to free the ressources, then you probably want to use the reParent method).
325: public void removeChild(Tree child) {
326:
327: this .children.remove(child);
328:
329: }
330:
331: //all the children of node are removed
332: //including the node
333: public static void removeTreeBranch(Tree node) {
334:
335: Tree parent;
336:
337: parent = node.getParent();
338: node.removeAllChildren();
339: if (parent != null) {
340: parent.removeChild(node);
341: }
342: //node.finalize();
343:
344: }
345:
346: //recursively delete all direct and indirect children of this Tree thus free some ressources
347: public void removeAllChildren() {
348:
349: Tree aTree;
350: Iterator iterator;
351:
352: iterator = this .getChildren();
353:
354: while (iterator.hasNext()) {
355: aTree = (Tree) iterator.next();
356: aTree.removeAllChildren();
357: //aTree.finalize();
358: }
359:
360: }
361:
362: }
|