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 import java.util.List;
023
024 /**
025 * The <code>Forest</code> interface is used to store any type of
026 * arborescence. A forest contains many nodes. Some of them have one
027 * parent. They are internal nodes if they have at least one child and
028 * are leaves if they do not have any child. The nodes without parents
029 * are the roots. A forest (unlike a tree) can have many roots.
030 *
031 * The nodes of the trees can be handled using <code>Position</code>s.
032 *
033 * The following example presents a program for displaying the content of a given forest.
034 * <pre>
035 public static void displayForest(Forest<String> f){
036 LinkedSequence<Position<String>> s =
037 new LinkedSequence<Position<String>>();
038 LinkedSequence<Integer> depthList = new LinkedSequence<Integer>();
039 int depth=0;
040 for(Position<String> root : f.roots()){
041 depth=0;
042 s.add(root);
043 depthList.add(depth);
044 while(!s.isEmpty()){
045 Position<String> tmpNode = s.delete(s.last());
046 depth = depthList.delete(depthList.last());
047 System.out.println(createXSpaces(depth)+tmpNode.element());
048 for(Position<String> child : f.children(tmpNode)){
049 s.add(child);
050 depthList.add(depth+1);
051
052 }
053 }
054 }
055 }
056 * </pre>
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 Forest<E> extends Container<E>{
064
065 /**
066 * Returns the list of the roots contained in the forest. I.e. all the nodes without parent.
067 *
068 * @return the list containing all roots.
069 */
070 public List<Position<E>> roots();
071
072
073 /**
074 * Returns the parent of the given node.
075 *
076 * We get a <code>child</code> and return its parent
077 *
078 * @param child the node we are looking at
079 * @return the parent of <code>child</code>.
080 * @throws InvalidAccessorException if the position is not a
081 * valid node of this forest.
082 */
083 public Position<E> parent(Position<?> child) throws InvalidAccessorException;
084
085 /**
086 * Returns the list of the children of a given node.
087 *
088 * We receive a <code>parent</code> node and return the list of its children.
089 *
090 * @param parent the node we are looking at
091 * @return the list of all the children of <code>parent</code>.
092 * @throws InvalidAccessorException if the position is not a
093 * valid node of this forest.
094 */
095 public List<Position<E>> children(Position<?> parent) throws InvalidAccessorException;
096
097
098 /**
099 * Creates a link between <code>parent</code> and
100 * <code>child</code>. <code>child</code> is inserted in the list
101 * of children of <code>parent</code> and <code>parent</code>
102 * becomes its parent.
103 *
104 * @param parent the node that will be the parent
105 * @param child the node that will be the child
106 * @throws InvalidAccessorException if the positions are not
107 * valid nodes of this forest.
108 */
109 public void link(Position<?> parent, Position<?> child) throws InvalidAccessorException;
110
111
112
113 /**
114 * Inserts <code>node</code> in the list of children of the parent
115 * of <code>sibling</code>. <code>node</code> is inserted just
116 * after <code>sibling</code> in the list. The parent of
117 * <code>sibling</code> becomes the new parent of
118 * <code>node</code>.
119 *
120 * @param sibling the future sibling of <code>node</code>
121 * @param node the node that will be inserted
122 * @throws InvalidAccessorException if the positions are not
123 * valid nodes of this forest.
124 * @throws BoundaryViolationException
125 */
126 public void linkAfter(Position<?> sibling, Position<?> node) throws BoundaryViolationException, InvalidAccessorException;
127
128 /**
129 * Inserts <code>node</code> in the list of children of the parent
130 * of <code>sibling</code>. <code>node</code> is inserted just
131 * before <code>sibling</code> in the list. The parent of
132 * <code>sibling</code> becomes the new parent of
133 * <code>node</code>.
134 *
135 * @param sibling the future sibling of <code>node</code>
136 * @param node the node that will be inserted
137 * @throws InvalidAccessorException if the positions are not
138 * valid nodes of this forest.
139 * @throws BoundaryViolationException
140 */
141 public void linkBefore(Position<?> sibling, Position<?> node) throws BoundaryViolationException, InvalidAccessorException;
142
143 /**
144 * Removes the relation between the given node
145 * (<code>child</code>) and its parent. <code>child</code> becomes
146 * a new root of the forest.
147 *
148 * @param child the node to be transformed into a root.
149 * @throws InvalidAccessorException if the position is not
150 * valid node of this forest.
151 */
152 public void cut(Position<?> child) throws InvalidAccessorException;
153 }