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.forest;
021    
022    import java.util.Collection;
023    import java.util.HashMap;
024    import java.util.LinkedList;
025    import java.util.Map;
026    import java.util.Queue;
027    
028    import ch.bfh.algo.Forest;
029    import ch.bfh.algo.Position;
030    import ch.bfh.algo.core.forest.GenericForestGraph;
031    
032    public class DefaultForest<E> extends GenericForestGraph<E,Node<E>>{
033    
034            private static class DefaultForestFactory<E> implements ForestFactory<Node<E>>{       
035                    public Node<E> createVertex(){ return new Node<E>(); }
036                    public Node<E> castVertex(Position<?> position){ return (Node<E>)position; }  
037            }
038            
039            public DefaultForest(){
040                    super(new DefaultForestFactory<E>());
041            }
042    
043            public DefaultForest(ForestFactory<Node<E>> factory){
044                    super(factory);
045            }
046    
047            public DefaultForest(Collection<? extends E> c){
048                    this();
049                    this.addAll(c);
050            }
051    
052            public DefaultForest(Forest<E> f){
053                    this();
054                    this.addForest(f);
055            }
056            
057            public DefaultForest(DefaultForest<E> f){
058                    this(f.getFactory());
059                    this.addForest(f);
060            }
061            
062            public DefaultForest(ForestFactory<Node<E>> factory,Forest<? extends E> f){
063                    this(factory);
064                    this.addForest(f);
065            }
066    
067            private <EE extends E> Map<Position<EE>,Position<E>> addForest(Forest<EE> f){
068                    Queue<Position<EE>> nodes=new LinkedList<Position<EE>>(f.roots());
069                    Map<Position<EE>,Position<E>> map=new HashMap<Position<EE>,Position<E>>(f.size());
070                    for(Position<EE> pos:nodes) map.put(pos,this.insert(pos.element()));
071                    while(!nodes.isEmpty()){
072                            Position<EE> pos=nodes.remove();
073                            Position<E> parent=map.get(pos);
074                            for(Position<EE> posc:f.children(pos)){
075                                    nodes.add(posc);
076                                    Position<E> child=this.insert(posc.element());
077                                    map.put(posc,child);
078                                    this.link(parent,child);
079                            }
080                    }
081                    return map;
082            }
083    
084    }