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;
021
022
023 /**
024 * The <code>BinaryForest</code> interface extends the <code>Forest</code>
025 * interface. It defines a forest which contains only binary trees. In this
026 * implementation. A node can have 0 children (it is called a leaf), 1 child
027 * or 2 children. To each child is assigned a position, left or right, so for
028 * each node, we have one or zero left child and one or zero right child.
029 *
030 * Here is an example of use of a binary forest. We have a recursive algorithm
031 * for displaying all the trees of a binary forest.
032 *
033 <pre>
034 static void displayRecBinaryForest(BinaryForest<String> f,Position<String> p, int depth){
035 if(f.childLeft(p)!= null){
036 displayRecBinaryForest(f,f.childLeft(p),depth+1);
037 }
038 System.out.println(createXSpaces(depth)+p.element());
039 if(f.childRight(p)!= null){
040 displayRecBinaryForest(f,f.childRight(p),depth+1);
041 }
042 }
043
044 public static void displayBinaryForest(BinaryForest<String> f){
045 System.out.println("--------");
046 for(Position<String> root : f.roots()){
047 displayRecBinaryForest(f,root,0);
048 System.out.println("--------");
049 }
050 }
051 </pre>
052 *
053 * All implementations of that interface should throw an
054 * <code>UnsupportedOperationException</code> when the following methods are
055 * executed: <code>link</code>, <code>linkAfter</code> and
056 * <code>linkBefore</code>.
057 *
058 * @author <a href="http://www.iam.unibe.ch/til/staff/kraehenbuehl">Juerg
059 * Kraehenbuehl</a> (code) and <a href="http://prof.hti.bfh.ch/bie1">Emmanuel
060 * Benoist</a> (Javadoc)
061 * @version 1.0
062 */
063 public interface BinaryForest<E> extends Forest<E>{
064
065 /**
066 * Access the left child of a given node (the <code>parent</code>).
067 *
068 * @param parent the node of which we want the left child
069 * @return the left child of the <code>parent</code>
070 * @throws InvalidAccessorException if the position is not a
071 * valid node of this forest.
072 */
073 public Position<E> childLeft(Position<?> parent) throws InvalidAccessorException;
074
075 /**
076 * Access the right child of a given node (the <code>parent</code>).
077 *
078 * @param parent the node of which we want the right child
079 * @return the right child of the <code>parent</code>
080 * @throws InvalidAccessorException if the position is not a
081 * valid node of this forest.
082 */
083 public Position<E> childRight(Position<?> parent) throws InvalidAccessorException;
084
085 /**
086 * Creates a link (parent-child relationship) between a node, the
087 * <code>parent</code>, and another node, the <code>child</code>
088 *
089 * The child should not have any parent, i.e. it is a root.
090 *
091 * @param parent The node receiving a new left child
092 * @param child The node becoming the new left child
093 * @throws InvalidAccessorException if the position is not a
094 * valid node of this forest.
095 */
096 public void linkLeft(Position<?> parent, Position<?> child) throws InvalidAccessorException;
097
098 /**
099 * Creates a link (parent-child relationship) between a node, the
100 * <code>parent</code>, and another node, the <code>child</code>
101 *
102 * The child should not have any parent, i.e. it is a root.
103 *
104 * @param parent The node receiving a new left child
105 * @param child The node becoming the new left child
106 * @throws InvalidAccessorException if the position is not a
107 * valid node of this forest.
108 */
109 public void linkRight(Position<?> parent, Position<?> child) throws InvalidAccessorException;
110
111 }