001 /*
002 * www.ti.bfh.ch
003 *
004 * Copyright 2007, Berne University of Applied Sciences,
005 * School of Engineering and Information Technology
006 * and individual contributors as indicated by the @authors tag.
007 *
008 * This is free software; you can redistribute it and/or modify it under the terms of the
009 * GNU Lesser General Public License as published by the Free Software Foundation;
010 * either version 3 of the License, or (at your option) any later version.
011 *
012 * This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
013 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
014 * See the GNU Lesser General Public License for more details.
015 *
016 * You should have received a copy of the GNU Lesser General Public License along with this software;
017 * if not, see <http://www.gnu.org/licenses/>.
018 *
019 */
020 package ch.bfh.algo.example;
021 import ch.bfh.algo.BinaryForest;
022 import ch.bfh.algo.Forest;
023 import ch.bfh.algo.Position;
024 import ch.bfh.algo.Sequence;
025 import ch.bfh.algo.forest.DefaultBinaryForest;
026 import ch.bfh.algo.forest.DefaultForest;
027 import ch.bfh.algo.sequence.LinkedSequence;
028
029
030
031 /**
032 * This file contains some examples of the use of the
033 * <code>Forest</code> and the <code>BinaryForest</code> interfaces.
034 *
035 *
036 * @author <a href="mailto:">Emmanuel Benoist</a>
037 * @version 1.0
038 */
039 public class TreeExample{
040
041 /**
042 * This method creates a <code>String</code> composed with
043 * <code>x</code> spaces. It is used for displaying a given number
044 * of spaces before a given string.
045 *
046 * @param x an <code>int</code> value for the number of spaces
047 * @return a <code>String</code> value that contains <code>x</code> spaces
048 */
049 private static String createXSpaces(int x){
050 String s= "";
051 for(int i=0;i<x;i++){
052 s+=" ";
053 }
054 return s;
055 }
056
057 /**
058 * This method displays all the nodes of a forests <code>f</code>
059 * This function contains a loop on all the roots of the
060 * forest. Once a root is visited, all its subtree is displayed
061 * (preorder-traversal).
062 *
063 * @param f Forest the forest to be displayed.
064 *
065 */
066 public static void displayForest(Forest<String> f){
067 Sequence<Position<String>> s =
068 new LinkedSequence<Position<String>>();
069 Sequence<Integer> depthList = new LinkedSequence<Integer>();
070 int depth=0;
071 for(Position<String> root : f.roots()){
072 depth=0;
073 s.add(root);
074 depthList.add(depth);
075 while(!s.isEmpty()){
076 Position<String> tmpNode = s.delete(s.last());
077 depth = depthList.delete(depthList.last());
078 System.out.println(createXSpaces(depth)+tmpNode.element());
079 for(Position<String> child : f.children(tmpNode)){
080 s.add(child);
081 depthList.add(depth+1);
082
083 }
084 }
085 }
086 }
087
088
089 /**
090 * This method creates a new node containing the value given as
091 * the <code>root</code>. Then all the root nodes of the forest
092 * <code>f</code> are branched as children of this new node. The
093 * result is a forest containing only one single tree whose root
094 * is the new node.
095 *
096 * @param f a <code>Forest</code>
097 * @param root a <code>String</code> value that will label the new
098 * node to be created.
099 */
100 public static void branchAllRoots(Forest<String> f, String root){
101 Position<String> newRoot = f.insert(root);
102 for(Position<String> oldRoot : f.roots()){
103 if(oldRoot!= newRoot){
104 f.link(newRoot,oldRoot);
105 }
106 }
107 return;
108
109 }
110
111 /**
112 * This method transfers all the children from the node <code>p1</code> to the node <code>p2</code>. This means we transfer all the subtrees whose roots are children of <code>p1</code> under <code>p2</code>.
113 *
114 * @param f <code>Forest</code> The forest in which the nodes are. All node need to be in the same forest.
115 * @param p1 The <code>Position</code> (i.e. node) that has children
116 * @param p2 the second node, that will receive the children of
117 * <code>p1</code>.
118 */
119 public static void transferChildren(Forest<String> f,
120 Position<String> p1,
121 Position<String> p2){
122 for(Position<String> child : f.children(p1)){
123 f.cut(child);
124 f.link(p2,child);
125 }
126 return;
127 }
128
129 /**
130 * This method creates and initialize a Forest. The resulting
131 * forest contains already some nodes that form some trees.
132 *
133 * This method creates a new <code>DefaultForest</code>, but
134 * manipulates and returns only a <code>Forest</code>.
135 *
136 * @return a new <code>Forest</code>
137 */
138 public static Forest<String> initForest(){
139 Forest<String> f = new DefaultForest<String>();
140 // Insert a new root
141 Position<String> pA = f.insert("A");
142 Position<String> pB = f.insert("B");
143 Position<String> pC = f.insert("C");
144 Position<String> pD = f.insert("D");
145 Position<String> pE = f.insert("E");
146 Position<String> pF = f.insert("F");
147 Position<String> pG = f.insert("G");
148 Position<String> pH = f.insert("H");
149 Position<String> pI = f.insert("I");
150 Position<String> pJ = f.insert("J");
151 Position<String> pK = f.insert("K");
152 Position<String> pL = f.insert("L");
153 Position<String> pM = f.insert("M");
154
155 f.link(pA,pC);
156 f.link(pA,pD);
157 f.link(pD,pE);
158 f.link(pD,pF);
159 f.link(pD,pG);
160 f.link(pB,pH);
161 f.link(pB,pI);
162 f.link(pB,pJ);
163 f.link(pK,pL);
164 f.link(pL,pM);
165 transferChildren(f,pA,pM);
166 return f;
167 }
168
169
170 static void displayRecBinaryForest(BinaryForest<String> f,Position<String> p, int depth){
171 if(f.childLeft(p)!= null){
172 displayRecBinaryForest(f,f.childLeft(p),depth+1);
173 }
174 System.out.println(createXSpaces(depth)+p.element());
175 if(f.childRight(p)!= null){
176 displayRecBinaryForest(f,f.childRight(p),depth+1);
177 }
178 }
179
180 /**
181 * The <code>displayBinaryForest</code> method implements a
182 * recursive in-order traversal.
183
184 * The aim of this method is to display the binary trees in a way
185 * that is familiar to us (with the root in the middle).
186 *
187 * @param f the <code>BinaryForest</code> that has to be displayed.
188 */
189 public static void displayBinaryForest(BinaryForest<String> f){
190 System.out.println("--------");
191 for(Position<String> root : f.roots()){
192 displayRecBinaryForest(f,root,0);
193 System.out.println("--------");
194 }
195 }
196
197
198 /**
199 * The <code>initBinaryForest</code> method is used to create a new binary forest. That forest contains some nodes and they are grouped into different binary trees.
200 *
201 * @return a newly created <code>BinaryForest</code>.
202 */
203 public static BinaryForest<String> initBinaryForest(){
204 BinaryForest<String> f = new DefaultBinaryForest<String>();
205
206 Position<String> pA = f.insert("A");
207 Position<String> pB = f.insert("B");
208 Position<String> pC = f.insert("C");
209 Position<String> pD = f.insert("D");
210 Position<String> pE = f.insert("E");
211 Position<String> pF = f.insert("F");
212 Position<String> pG = f.insert("G");
213 Position<String> pH = f.insert("H");
214 Position<String> pI = f.insert("I");
215 Position<String> pJ = f.insert("J");
216 Position<String> pK = f.insert("K");
217 Position<String> pL = f.insert("L");
218 Position<String> pM = f.insert("M");
219
220 f.linkLeft(pA,pB);
221 f.linkRight(pA,pC);
222 f.linkLeft(pB,pD);
223 f.linkRight(pB,pE);
224 f.linkLeft(pC,pF);
225 f.linkRight(pC,pG);
226 f.linkRight(pG,pH);
227 f.linkRight(pH,pI);
228
229 f.linkLeft(pJ,pK);
230 f.linkRight(pJ,pL);
231
232 return f;
233
234
235 }
236
237 /**
238 * The <code>ex1</code> method executes all tests concerning the <code>Forest</code>.
239 *
240 */
241 public static void ex1(){
242
243 Forest<String> forest = initForest();
244 displayForest(forest);
245 branchAllRoots(forest,"Root");
246 displayForest(forest);
247 }
248
249
250 /**
251 * The <code>ex2</code> method contains the tests about the <code>BinaryForest</code>.
252 *
253 */
254 public static void ex2(){
255 BinaryForest<String> forest = initBinaryForest();
256 displayBinaryForest(forest);
257 }
258
259 public static void main(String[] args){
260 System.out.println("***************");
261 System.out.println("Example of use of a Tree (it is a Forest indeed).");
262 System.out.println("");
263 ex1();
264 System.out.println("***************");
265 System.out.println("Example of use of a Binary Tree.");
266 System.out.println("");
267 ex2();
268 System.out.println("");
269 System.out.println("***************");
270
271 }
272
273
274 }