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.BinaryForest;
029 import ch.bfh.algo.Position;
030 import ch.bfh.algo.core.forest.GenericBinaryForestGraph;
031
032 public class DefaultBinaryForest<E> extends GenericBinaryForestGraph<E,BinaryNode<E>>{
033
034 private static class DefaultBinaryForestFactory<E> implements ForestFactory<BinaryNode<E>>{
035 public BinaryNode<E> createVertex(){ return new BinaryNode<E>(); }
036 public BinaryNode<E> castVertex(Position<?> position){ return (BinaryNode<E>)position; }
037 }
038
039 public DefaultBinaryForest(){
040 super(new DefaultBinaryForestFactory<E>());
041 }
042
043 public DefaultBinaryForest(ForestFactory<BinaryNode<E>> factory){
044 super(factory);
045 }
046
047 public DefaultBinaryForest(Collection<? extends E> c){
048 this();
049 this.addAll(c);
050 }
051
052 public DefaultBinaryForest(BinaryForest<E> f){
053 this();
054 this.addBinaryForest(f);
055 }
056
057 public DefaultBinaryForest(DefaultBinaryForest<E> f){
058 this(f.getFactory());
059 this.addBinaryForest(f);
060 }
061
062 public DefaultBinaryForest(ForestFactory<BinaryNode<E>> factory,BinaryForest<? extends E> f){
063 this(factory);
064 this.addBinaryForest(f);
065 }
066
067 private <EE extends E> Map<Position<EE>,Position<E>> addBinaryForest(BinaryForest<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(),posl=f.childLeft(pos),posr=f.childRight(pos);
073 Position<E> parent=map.get(pos);
074 if(posl!=null){
075 nodes.add(posl);
076 Position<E> child=this.insert(posl.element());
077 map.put(posl,child);
078 this.linkLeft(parent,child);
079
080 }
081 if(posr!=null){
082 nodes.add(posr);
083 Position<E> child=this.insert(posr.element());
084 map.put(posr,child);
085 this.linkRight(parent,child);
086
087 }
088 }
089 return map;
090 }
091
092 }