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.core.forest;
021
022 import ch.bfh.algo.BoundaryViolationException;
023 import ch.bfh.algo.Direction;
024 import ch.bfh.algo.InvalidAccessorException;
025 import ch.bfh.algo.Position;
026 import ch.bfh.algo.core.GenericForest;
027 import ch.bfh.algo.core.graph.GenericAdjacencyListGraph;
028 import ch.bfh.algo.core.position.PositionIterator;
029 import ch.bfh.algo.core.position.PositionList;
030 import ch.bfh.algo.core.position.PositionListAdapter;
031 import ch.bfh.algo.forest.ForestFactory;
032 import ch.bfh.algo.graph.GraphFactory;
033 import ch.bfh.algo.sequence.LinkedPosition;
034 import ch.bfh.algo.sequence.LinkedSequence;
035
036 public class GenericForestGraph<E,P extends GenericNode<E,P>> extends GenericAdjacencyListGraph<Object,E,GenericLink<E,P>,P> implements GenericForest<E,P>{
037
038 private final LinkedSequence<P> roots=new LinkedSequence<P>();
039
040 public GenericForestGraph(final ForestFactory<P> factory){
041 super(
042 new GraphFactory<GenericLink<E,P>,P>(){
043 public P createVertex(){ return factory.createVertex(); }
044 public P castVertex(Position<?> vertex){ return factory.castVertex(vertex); }
045 public GenericLink<E,P> createEdge(){ return new GenericLink<E,P>(); }
046 public GenericLink<E,P> castEdge(Position<?> edge){ return (GenericLink<E,P>)edge; }
047 },
048 true
049 );
050 }
051
052 protected P insertBetween(P previous, P next, E element, P position){
053 P node=super.insertBetween(previous,next,element,position);
054 node.markRoot(this.roots);
055 return node;
056 }
057
058 public E deleteVertex(P node){
059 PositionIterator<E,P> children=this.children(node).iterator();
060 while(children.hasNext()) children.next().markRoot(this.roots);
061 for(Position<Object> e: this.incidentEdges(node,Direction.ALL)) this.deleteEdge(e);
062 node.unmarkRoot();
063 return super.deleteVertex(node);
064 }
065
066 public void link(Position<?> parent, Position<?> child){
067 try{this.link(this.factory.castVertex(parent),this.factory.castVertex(child));}
068 catch(ClassCastException e){ throw new InvalidAccessorException(); }
069 }
070
071 public void link(P parent, P child){
072 this.validate(parent);
073 for(Position<Object> e: this.incidentEdges(child,Direction.IN)) this.deleteEdge(e);
074 child.unmarkRoot();
075 GenericLink<E,P> e=this.insertEdge(null);
076 this.setDestination(e,child);
077 LinkedPosition<GenericLink<E,P>> p=this.setOrigin(e,parent);
078 child.setLinkPosition(p);
079 }
080
081 public void linkAfter(Position<?> sibling, Position<?> node) {
082 try{this.linkAfter(this.factory.castVertex(sibling),this.factory.castVertex(node));}
083 catch(ClassCastException e){ throw new InvalidAccessorException(); }
084 }
085
086 public void linkAfter(P sibling, P node){
087 if(sibling==node) return;
088 P parent=this.parent(sibling);
089 if(parent==null) throw new BoundaryViolationException();
090 this.linkAfter(parent,node,sibling.getLinkPosition());
091 }
092
093 private void linkAfter(P parent, P child, LinkedPosition<GenericLink<E,P>> position){
094 for(Position<Object> e: this.incidentEdges(child,Direction.IN)) this.deleteEdge(e);
095 child.unmarkRoot();
096 GenericLink<E,P> e=this.insertEdge(null);
097 this.setDestination(e,child);
098 LinkedPosition<GenericLink<E,P>> p=this.setOriginAfter(e,parent,position);
099 child.setLinkPosition(p);
100 }
101
102 public void linkBefore(Position<?> sibling, Position<?> node) {
103 try{this.linkBefore(this.factory.castVertex(sibling),this.factory.castVertex(node));}
104 catch(ClassCastException e){ throw new InvalidAccessorException(); }
105 }
106
107 public void linkBefore(P sibling, P node) {
108 if(sibling==node) return;
109 P parent=this.parent(sibling);
110 if(parent==null) throw new BoundaryViolationException();
111 this.linkBefore(parent,node,sibling.getLinkPosition());
112 }
113
114 private void linkBefore(P parent, P child, LinkedPosition<GenericLink<E,P>> position){
115 for(Position<Object> e: this.incidentEdges(child,Direction.IN)) this.deleteEdge(e);
116 child.unmarkRoot();
117 GenericLink<E,P> e=this.insertEdge(null);
118 this.setDestination(e,child);
119 LinkedPosition<GenericLink<E,P>> p=this.setOriginBefore(e,parent,position);
120 child.setLinkPosition(p);
121 }
122
123 public void cut(Position<?> child) {
124 try{this.cut(this.factory.castVertex(child));}
125 catch(ClassCastException e){ throw new InvalidAccessorException(); }
126 }
127
128 public void cut(P child){
129 for(Position<Object> e: this.incidentEdges(child,Direction.IN)) this.deleteEdge(e);
130 child.markRoot(this.roots);
131 child.setLinkPosition(null);
132 }
133
134 public PositionList<E,P> roots(){
135 return new PositionListAdapter<E,P>(this.roots);
136 }
137
138 public P parent(Position<?> child){
139 PositionIterator<E,P> parent=this.adjacentVertices(child,Direction.IN).iterator();
140 if(parent.hasNext()) return parent.next();
141 else return null;
142 }
143
144 public PositionList<E,P> children(Position<?> parent){
145 return this.adjacentVertices(parent,Direction.OUT);
146 }
147 }