Coverage Report

Coverage Report - org.kuali.student.core.statement.ui.client.widgets.table.Node

Classes in this File

Line Coverage

Branch Coverage

Complexity

Node

0/154

0/86

2.5

 /**
  * Copyright 2010 The Kuali Foundation Licensed under the
  * Educational Community License, Version 2.0 (the "License"); you may
  * not use this file except in compliance with the License. You may
  * obtain a copy of the License at
  *
  * http://www.osedu.org/licenses/ECL-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an "AS IS"
  * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
  * or implied. See the License for the specific language governing
  * permissions and limitations under the License.
  */
 
 package org.kuali.student.core.statement.ui.client.widgets.table;
 
 import java.util.ArrayList;
 import java.util.List;
 
 import org.kuali.student.core.statement.ui.client.widgets.rules.Token;
 /**
  * A generic tree node. 
  * */
 public class Node<T> implements Cloneable{
     /** Children are stored in a list*/
     List<Node> childrenList = new ArrayList<Node>();
     /** Parent Node. null if node has no parent*/
     Node parent;
     /** User Object*/
     T userObject;
     String id;
     /**
      * Empty, default constructor
      * */
     public Node() {}
     /**
      * Constructor of Node which accepts the user object
      * 
      * @param obj user object
      * */
     public Node(T obj) {
         userObject = obj;
     }
     /**
      * Get the user object from node
      * 
      * @return T returns the user object. User object must by type T 
      * */
     public T getUserObject() {
         return userObject;
     }
     /**
      * Set the user object to this node
      * 
      * @param obj obj must be an instanceo of type T
      * */
     public void setUserObject(T obj) {
         userObject = obj;
     }
     /**
      * Set the Parent node for current node
      * 
      * @param parent new parent
      * */
     public void setParent(Node parent) {
         this.parent = parent;
     }
 
     /**
      * Get the parent of current node
      * @return the parent
      * */
     public Node getParent() {
         return parent;
     }
     /**
      * Add one child and set child's parent to current node
      * 
      * @param node new child
      * 
      * */
     public void addNode(Node node) {
         childrenList.add(node);
         node.setParent(this);
     }
     /** If it has no children, it is a leaf
      * 
      * @return boolean is it a leaf
      * 
      * */
     public boolean isLeaf() {
         return getChildCount() == 0;
     }
     /** 
      * Return the child count 
      * 
      * @retrun int the child count
      * */
     public int getChildCount() {
         return childrenList.size();
     }
     /** 
      * Get the child at index
      *
      * @param index the index of the child
      * @return the child
      * */
     public Node getChildAt(int index) {
         return childrenList.get(index);
     }
     /** Remove child from parent*/
     public void removeFromParent() {
         Node parent = this.getParent();
         if (parent == null) {
             return;
         } else {
             parent.children().remove(this);
             this.setParent(null);
         }
     }
     /** Remove child at childIndex
      * 
      * @param childIndex child indexs
      * */
     public void remove(int childIndex) {
         Node child = getChildAt(childIndex);
         childrenList.remove(childIndex);
         child.setParent(null);
     }
     /** Remove child from children list
      * 
      * @param child 
      * */
     public void remove(Node child) {
         childrenList.remove(child);
         child.setParent(null);
     }
     public void removeAllChildren(){
         childrenList.clear();
     }
     /** 
      * Is passed node a child of current node
      *  
      *  @param aNode 
      * 
      * */
     public boolean isNodeChild(Node aNode) {
         boolean retval;
         if (aNode == null) {
             retval = false;
         } else {
             if (getChildCount() == 0) {
                 retval = false;
             } else {
                 retval = (aNode.getParent() == this);
             }
         }
         return retval;
     }
     
     public int getIndex(Node aChild) {
         if (!isNodeChild(aChild)) {
             return -1;
         }
         return childrenList.indexOf(aChild); // linear search
     }
     /** Is parsed in node a sibling */
     public boolean isNodeSibling(Node anotherNode) {
         boolean retval;
 
         if (anotherNode == null) {
             retval = false;
         } else if (anotherNode == this) {
             retval = true;
         } else {
             Node myParent = getParent();
             retval = (myParent != null && myParent == anotherNode.getParent());
 
             if (retval && !((Node) getParent()).isNodeChild(anotherNode)) {
                 throw new Error("sibling has different parent");
             }
         }
         return retval;
     }
 
     /**
      * Returns the total number of leaves that are descendants of this node.
      * 
      * @return the number of leaves beneath this node
      */
     public int getAllLeafCount() {
         int count = 0;
         List<Node<T>> nodeList = getAllChildren();
         for (Node<T> node : nodeList) {
             if (node.isLeaf()) {
                 count++;
             }
         }
 
         return count;
     }
     /** Return all children and grand children*/
     public List<Node<T>> getAllChildren() {
         List<Node<T>> nodeList = new ArrayList<Node<T>>();
         for (Node<T> child : childrenList) {
             nodeList.add(child);
             if (!child.isLeaf()) {
                 nodeList.addAll(child.getAllChildren());
             }
         }
         return nodeList;
     }
     /** Get the first leaf among all its children*/
     public Node<T> getFirstLeafDescendant() {
         List<Node<T>> list = getAllChildren();
         for (Node<T> node : list) {
             if (node.isLeaf()) {
                 return node;
             }
         }
         return null;
 
     }
     /** Return all non-leaf children 
      * 
      * @return List<Node> list of non-leaf children
      * */
     public List<Node> getNonLeafChildren() {
         List<Node> list = new ArrayList<Node>();
         for (Node n : children()) {
             if (n.isLeaf() == false) {
                 list.add(n);
             }
         }
         return list;
     }
     
     public List<Node> getLeafChildren() {
         List<Node> list = new ArrayList<Node>();
         for (Node n : children()) {
             if (n.isLeaf()) {
                 list.add(n);
             }
         }
         return list;
     }
 
     public List<Node> getSiblings() {
         Node parent = this.getParent();
         List<Node> list = new ArrayList<Node>();
         if (parent != null) {
 
             for (int i = 0; i < parent.getChildCount(); i++) {
                 if (parent.getChildAt(i) != this) {
                     list.add(parent.getChildAt(i));
                 }
             }
             return list;
         }
         return list;
 
     }
 
     public List<Node> getLeafSiblings() {
         List<Node> list = new ArrayList<Node>();
         List<Node> siblings = getSiblings();
         for (Node n : siblings) {
             if (n.isLeaf()) {
                 list.add(n);
             }
         }
 
         return list;
     }
 
     public List<Node> children() {
         if (childrenList == null) {
             return new ArrayList<Node>();
         } else {
             return childrenList;
         }
     }
 
     // root is the level one
     // results contain current node
     public List<List<Node>> toLevel() {
         List<List<Node>> levelList = new ArrayList<List<Node>>();
 
         List<Node> level = new ArrayList<Node>();
         level.add(this);
         levelList.add(level);
 
         int maxDistance = getMaxLevelDistance();
 
         List<Node<T>> nodeList = getAllChildren();
         for (int levelIndex = 1; levelIndex <= maxDistance; levelIndex++) {
             level = new ArrayList<Node>();
             for (Node node : nodeList) {
                 int d = getDistance(node);
                 if (levelIndex == d) {
                     level.add(node);
                 }
             }
             levelList.add(level);
         }
 
         return levelList;
     }
 
     public List<Node> deepTrans(Node root) {
         List<Node> list = new ArrayList<Node>();
         for (int i = 0; i < root.getChildCount(); i++) {
             Node n = root.getChildAt(i);
             if (n.isLeaf()) {
                 list.add(n);
             } else {
                 list.addAll(deepTrans(n));
             }
 
         }
         list.add(root);
         return list;
     }
 
     public int getMaxLevelDistance() {
         List<Node<T>> nodeList = getAllChildren();
         int maxDistance = 0;
         for (Node<T> node : nodeList) {
             int d = getDistance(node);
             if (maxDistance < d) {
                 maxDistance = d;
             }
         }
         return maxDistance;
     }
 
     // return the level distance to the current node
     public int getDistance(Node node) {
         Node myParent = node.getParent();
         int level = 1;
         while (myParent != null && myParent != this) {
             level++;
             myParent = myParent.getParent();
         }
         return level;
     }
 
     public String toString() {
         if (userObject == null) {
             return "no user object";
         }
 
         StringBuilder sb = new StringBuilder(userObject.toString());
         if (this.getChildCount() == 0) {
             return sb.toString();
         }
         sb.append("{");
         for (int i = 0; i < this.getChildCount(); i++) {
             if (this.getChildAt(i).getParent() == this) {
                 sb.append(this.getChildAt(i).toString() + ",");
             }
 
         }
         sb.append("}");
         return sb.toString();
     }
 
     public Node<T> clone() {
         Node<T> newNode = new Node<T>();
         newNode.setUserObject(this.getUserObject());
         if (this.isLeaf() == false) {
             for (Node<T> n : this.childrenList) {
                 newNode.addNode(n.clone());
             }
         }
         return newNode;
     }
 
     public static void main(String[] argv) {
 /*        Node root = new Node();
         root.setUserObject("root");
         Node r = new Node();
         r.setUserObject("r");
         Node q = new Node();
         q.setUserObject("q");
         root.addNode(q);
         root.addNode(r);
 
         Node a = new Node();
         a.setUserObject("a");
         q.addNode(a);
 
 //        System.out.println(root.deepTrans(root));
   //      System.out.println(root.deepTrans(root.clone()));
         
         Node x = new Node();
         x.setUserObject("x");
 
         Node y = new Node();
         y.setUserObject("y");
 
         Node z = new Node();
         z.setUserObject("z");
         
         x.addNode(y);
         x.addNode(z);
         System.out.println(x.deepTrans(x.clone()));
 */        
         ExpressionParser p = new ExpressionParser();
         Node<Token> n = p.parse("(a or b) and c or d and f");
         System.out.println(n);
         System.out.println(ExpressionParser.getExpressionString(n));
     }
 }   

1		/**
2		* Copyright 2010 The Kuali Foundation Licensed under the
3		* Educational Community License, Version 2.0 (the "License"); you may
4		* not use this file except in compliance with the License. You may
5		* obtain a copy of the License at
6		*
7		* http://www.osedu.org/licenses/ECL-2.0
8		*
9		* Unless required by applicable law or agreed to in writing,
10		* software distributed under the License is distributed on an "AS IS"
11		* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
12		* or implied. See the License for the specific language governing
13		* permissions and limitations under the License.
14		*/
15
16		package org.kuali.student.core.statement.ui.client.widgets.table;
17
18		import java.util.ArrayList;
19		import java.util.List;
20
21		import org.kuali.student.core.statement.ui.client.widgets.rules.Token;
22		/**
23		* A generic tree node.
24		* */
25	0	public class Node<T> implements Cloneable{
26		/** Children are stored in a list*/
27	0	List<Node> childrenList = new ArrayList<Node>();
28		/** Parent Node. null if node has no parent*/
29		Node parent;
30		/** User Object*/
31		T userObject;
32		String id;
33		/**
34		* Empty, default constructor
35		* */
36	0	public Node() {}
37		/**
38		* Constructor of Node which accepts the user object
39		*
40		* @param obj user object
41		* */
42	0	public Node(T obj) {
43	0	userObject = obj;
44	0	}
45		/**
46		* Get the user object from node
47		*
48		* @return T returns the user object. User object must by type T
49		* */
50		public T getUserObject() {
51	0	return userObject;
52		}
53		/**
54		* Set the user object to this node
55		*
56		* @param obj obj must be an instanceo of type T
57		* */
58		public void setUserObject(T obj) {
59	0	userObject = obj;
60	0	}
61		/**
62		* Set the Parent node for current node
63		*
64		* @param parent new parent
65		* */
66		public void setParent(Node parent) {
67	0	this.parent = parent;
68	0	}
69
70		/**
71		* Get the parent of current node
72		* @return the parent
73		* */
74		public Node getParent() {
75	0	return parent;
76		}
77		/**
78		* Add one child and set child's parent to current node
79		*
80		* @param node new child
81		*
82		* */
83		public void addNode(Node node) {
84	0	childrenList.add(node);
85	0	node.setParent(this);
86	0	}
87		/** If it has no children, it is a leaf
88		*
89		* @return boolean is it a leaf
90		*
91		* */
92		public boolean isLeaf() {
93	0	return getChildCount() == 0;
94		}
95		/**
96		* Return the child count
97		*
98		* @retrun int the child count
99		* */
100		public int getChildCount() {
101	0	return childrenList.size();
102		}
103		/**
104		* Get the child at index
105		*
106		* @param index the index of the child
107		* @return the child
108		* */
109		public Node getChildAt(int index) {
110	0	return childrenList.get(index);
111		}
112		/** Remove child from parent*/
113		public void removeFromParent() {
114	0	Node parent = this.getParent();
115	0	if (parent == null) {
116	0	return;
117		} else {
118	0	parent.children().remove(this);
119	0	this.setParent(null);
120		}
121	0	}
122		/** Remove child at childIndex
123		*
124		* @param childIndex child indexs
125		* */
126		public void remove(int childIndex) {
127	0	Node child = getChildAt(childIndex);
128	0	childrenList.remove(childIndex);
129	0	child.setParent(null);
130	0	}
131		/** Remove child from children list
132		*
133		* @param child
134		* */
135		public void remove(Node child) {
136	0	childrenList.remove(child);
137	0	child.setParent(null);
138	0	}
139		public void removeAllChildren(){
140	0	childrenList.clear();
141	0	}
142		/**
143		* Is passed node a child of current node
144		*
145		* @param aNode
146		*
147		* */
148		public boolean isNodeChild(Node aNode) {
149		boolean retval;
150	0	if (aNode == null) {
151	0	retval = false;
152		} else {
153	0	if (getChildCount() == 0) {
154	0	retval = false;
155		} else {
156	0	retval = (aNode.getParent() == this);
157		}
158		}
159	0	return retval;
160		}
161
162		public int getIndex(Node aChild) {
163	0	if (!isNodeChild(aChild)) {
164	0	return -1;
165		}
166	0	return childrenList.indexOf(aChild); // linear search
167		}
168		/** Is parsed in node a sibling */
169		public boolean isNodeSibling(Node anotherNode) {
170		boolean retval;
171
172	0	if (anotherNode == null) {
173	0	retval = false;
174	0	} else if (anotherNode == this) {
175	0	retval = true;
176		} else {
177	0	Node myParent = getParent();
178	0	retval = (myParent != null && myParent == anotherNode.getParent());
179
180	0	if (retval && !((Node) getParent()).isNodeChild(anotherNode)) {
181	0	throw new Error("sibling has different parent");
182		}
183		}
184	0	return retval;
185		}
186
187		/**
188		* Returns the total number of leaves that are descendants of this node.
189		*
190		* @return the number of leaves beneath this node
191		*/
192		public int getAllLeafCount() {
193	0	int count = 0;
194	0	List<Node<T>> nodeList = getAllChildren();
195	0	for (Node<T> node : nodeList) {
196	0	if (node.isLeaf()) {
197	0	count++;
198		}
199		}
200
201	0	return count;
202		}
203		/** Return all children and grand children*/
204		public List<Node<T>> getAllChildren() {
205	0	List<Node<T>> nodeList = new ArrayList<Node<T>>();
206	0	for (Node<T> child : childrenList) {
207	0	nodeList.add(child);
208	0	if (!child.isLeaf()) {
209	0	nodeList.addAll(child.getAllChildren());
210		}
211		}
212	0	return nodeList;
213		}
214		/** Get the first leaf among all its children*/
215		public Node<T> getFirstLeafDescendant() {
216	0	List<Node<T>> list = getAllChildren();
217	0	for (Node<T> node : list) {
218	0	if (node.isLeaf()) {
219	0	return node;
220		}
221		}
222	0	return null;
223
224		}
225		/** Return all non-leaf children
226		*
227		* @return List<Node> list of non-leaf children
228		* */
229		public List<Node> getNonLeafChildren() {
230	0	List<Node> list = new ArrayList<Node>();
231	0	for (Node n : children()) {
232	0	if (n.isLeaf() == false) {
233	0	list.add(n);
234		}
235		}
236	0	return list;
237		}
238
239		public List<Node> getLeafChildren() {
240	0	List<Node> list = new ArrayList<Node>();
241	0	for (Node n : children()) {
242	0	if (n.isLeaf()) {
243	0	list.add(n);
244		}
245		}
246	0	return list;
247		}
248
249		public List<Node> getSiblings() {
250	0	Node parent = this.getParent();
251	0	List<Node> list = new ArrayList<Node>();
252	0	if (parent != null) {
253
254	0	for (int i = 0; i < parent.getChildCount(); i++) {
255	0	if (parent.getChildAt(i) != this) {
256	0	list.add(parent.getChildAt(i));
257		}
258		}
259	0	return list;
260		}
261	0	return list;
262
263		}
264
265		public List<Node> getLeafSiblings() {
266	0	List<Node> list = new ArrayList<Node>();
267	0	List<Node> siblings = getSiblings();
268	0	for (Node n : siblings) {
269	0	if (n.isLeaf()) {
270	0	list.add(n);
271		}
272		}
273
274	0	return list;
275		}
276
277		public List<Node> children() {
278	0	if (childrenList == null) {
279	0	return new ArrayList<Node>();
280		} else {
281	0	return childrenList;
282		}
283		}
284
285		// root is the level one
286		// results contain current node
287		public List<List<Node>> toLevel() {
288	0	List<List<Node>> levelList = new ArrayList<List<Node>>();
289
290	0	List<Node> level = new ArrayList<Node>();
291	0	level.add(this);
292	0	levelList.add(level);
293
294	0	int maxDistance = getMaxLevelDistance();
295
296	0	List<Node<T>> nodeList = getAllChildren();
297	0	for (int levelIndex = 1; levelIndex <= maxDistance; levelIndex++) {
298	0	level = new ArrayList<Node>();
299	0	for (Node node : nodeList) {
300	0	int d = getDistance(node);
301	0	if (levelIndex == d) {
302	0	level.add(node);
303		}
304	0	}
305	0	levelList.add(level);
306		}
307
308	0	return levelList;
309		}
310
311		public List<Node> deepTrans(Node root) {
312	0	List<Node> list = new ArrayList<Node>();
313	0	for (int i = 0; i < root.getChildCount(); i++) {
314	0	Node n = root.getChildAt(i);
315	0	if (n.isLeaf()) {
316	0	list.add(n);
317		} else {
318	0	list.addAll(deepTrans(n));
319		}
320
321		}
322	0	list.add(root);
323	0	return list;
324		}
325
326		public int getMaxLevelDistance() {
327	0	List<Node<T>> nodeList = getAllChildren();
328	0	int maxDistance = 0;
329	0	for (Node<T> node : nodeList) {
330	0	int d = getDistance(node);
331	0	if (maxDistance < d) {
332	0	maxDistance = d;
333		}
334	0	}
335	0	return maxDistance;
336		}
337
338		// return the level distance to the current node
339		public int getDistance(Node node) {
340	0	Node myParent = node.getParent();
341	0	int level = 1;
342	0	while (myParent != null && myParent != this) {
343	0	level++;
344	0	myParent = myParent.getParent();
345		}
346	0	return level;
347		}
348
349		public String toString() {
350	0	if (userObject == null) {
351	0	return "no user object";
352		}
353
354	0	StringBuilder sb = new StringBuilder(userObject.toString());
355	0	if (this.getChildCount() == 0) {
356	0	return sb.toString();
357		}
358	0	sb.append("{");
359	0	for (int i = 0; i < this.getChildCount(); i++) {
360	0	if (this.getChildAt(i).getParent() == this) {
361	0	sb.append(this.getChildAt(i).toString() + ",");
362		}
363
364		}
365	0	sb.append("}");
366	0	return sb.toString();
367		}
368
369		public Node<T> clone() {
370	0	Node<T> newNode = new Node<T>();
371	0	newNode.setUserObject(this.getUserObject());
372	0	if (this.isLeaf() == false) {
373	0	for (Node<T> n : this.childrenList) {
374	0	newNode.addNode(n.clone());
375		}
376		}
377	0	return newNode;
378		}
379
380		public static void main(String[] argv) {
381		/* Node root = new Node();
382		root.setUserObject("root");
383		Node r = new Node();
384		r.setUserObject("r");
385		Node q = new Node();
386		q.setUserObject("q");
387		root.addNode(q);
388		root.addNode(r);
389
390		Node a = new Node();
391		a.setUserObject("a");
392		q.addNode(a);
393
394		// System.out.println(root.deepTrans(root));
395		// System.out.println(root.deepTrans(root.clone()));
396
397		Node x = new Node();
398		x.setUserObject("x");
399
400		Node y = new Node();
401		y.setUserObject("y");
402
403		Node z = new Node();
404		z.setUserObject("z");
405
406		x.addNode(y);
407		x.addNode(z);
408		System.out.println(x.deepTrans(x.clone()));
409		*/
410	0	ExpressionParser p = new ExpressionParser();
411	0	Node<Token> n = p.parse("(a or b) and c or d and f");
412	0	System.out.println(n);
413	0	System.out.println(ExpressionParser.getExpressionString(n));
414	0	}
415		}