package common.graph;

import common.Sets;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Stream;

/**
 * <p>A base class for implementations of the Graph interface.</p>
 * @author fiveham
 * @author fiveham
 *
 * @param <T> the type of the vertices of this Graph
 * @param <T> the type of the vertices of this Graph@param <T> the type of the vertices of this
 * @param <T> the type of the vertices of this GraphGraph
 */
public abstract class AbstractGraph<T extends Vertex<T>> implements Graph<T>{
	
    /**
     * <p>The backing collection of vertices in this Graph.</p>
     */
	protected final ArrayList<T> nodes;
	
    /**
     * <p>Constructs an AbstractGraph with an empty list of vertices and an empty list of
     * connected-component contraction event-listeners.</p>
     */
	public AbstractGraph() {
		nodes = new ArrayList<>();
	}
	
    /**
     * <p>Constructs an AbstractGraph whose backing collection of vertices is initialized empty but
     * with a capacity of {@code size}.</p>
     * @param size the capacity which the backing collection of vertices will have
     */
	public AbstractGraph(int size) {
		nodes = new ArrayList<>(size);
	}
	
    /**
     * <p>Constructs an AbstractGraph having the elements of {@code coll} as vertices.</p>
     * @param coll vertices for this Graph
     */
	public AbstractGraph(Collection<? extends T> coll){
		nodes = new ArrayList<>(coll);
	}
	
    /**
     * <p>Constructs an AbstractGraph having the elements of {@code coll} as vertices and having all
     * the elements of {@code factories} as event-listener sources.</p>
     * @param coll vertices for this Graph
     * @param factories connected-component contraction event-listers for this Graph
     */
	public AbstractGraph(Collection<? extends T> coll, List<Supplier<Consumer<Set<T>>>> factories) {
		nodes = new ArrayList<>(coll);
	}
	
	@Override
	public int size(){
		return nodes.size();
	}
	
	@Override
	public Iterator<T> iterator(){
		return nodes.iterator();
	}
	
	@Override
	public Stream<T> nodeStream(){
		return nodes.stream();
	}
	
	@Override
	public Collection<Graph<T>> connectedComponents(Function<List<T>,T> seedSrc){
		
		List<Graph<T>> result = new ArrayList<>();
		
		List<T> unassignedNodes = new ArrayList<>(nodes);
		
		while( !unassignedNodes.isEmpty() ){
			Graph<T> component = component(unassignedNodes, seedSrc);
			result.add(component);
		}
		
		return result;
	}
	
	public Graph<T> component(List<T> unassignedNodes, Function<List<T>,T> seedSrc){
		
		ConnectedComponent<T> newComponent = new ConnectedComponent<T>(nodes.size(), unassignedNodes);
		{
			int initUnassignedCount = unassignedNodes.size();
			T seed = seedSrc.apply(unassignedNodes);
			
			if(unassignedNodes.size() == initUnassignedCount){
				unassignedNodes.remove(seed);
			}
			
			newComponent.add(seed); //seed now in cuttingEdge
		}
		
		while( !newComponent.cuttingEdgeIsEmpty() ){
			newComponent.contract();	//move cuttingEdge into edge and old edge into core
			newComponent.grow();		//add unincorporated nodes to cuttingEdge
		}
		
		return new BasicGraph<T>(newComponent.contract());
	}
	
  private Graph<T> component2(List<T> unassignedNodes, Function<List<T>,T> seedSrc){
    Set<T> core = new HashSet<>();
    Set<T> edge = new HashSet<>();
    Set<T> cuttingEdge = new HashSet<>();
    cuttingEdge.add(seedSrc.apply(unassignedNodes));
    
    while(!cuttingEdge.isEmpty()){
      core.addAll(edge);
      edge = cuttingEdge;
      cuttingEdge = edge.stream()
          .map(Vertex::neighbors)
          .map(HashSet<T>::new)
          .reduce(new HashSet<T>(), Sets::mergeCollections);
      
      for(Iterator<T> iterator = cuttingEdge.iterator(); iterator.hasNext();){
        T element = iterator.next();
        if(unassignedNodes.contains(element)){
          unassignedNodes.remove(element);
        } else{
          iterator.remove();
        }
      }
    }
    core.addAll(edge);
    
    return new BasicGraph<T>(core);
  }
	
	@Override
	public int hashCode(){
		return nodeStream()
				.map(Object::hashCode)
				.reduce(0, Integer::sum);
	}
	
	@Override
	public String toString(){
		StringBuilder out = new StringBuilder();
		out.append(getClass()).append(" size ").append(size()).append(System.lineSeparator()).append(nodes).append(System.lineSeparator());
		
		for(T node : nodes){
			out.append(node).append(": ").append(System.lineSeparator()).append(node.neighbors()).append(System.lineSeparator());
		}
		
		return out.toString();
	}
}

@@ -36,16 +36,40 @@
 n.Sets;%0A
+import common.Universe;%0A
 import j
@@ -2385,32 +2385,32 @@
 ts(Function%3C
-Lis
+Se
 t%3CT%3E,
+ 
 T%3E seedSrc)%7B
@@ -2467,912 +2467,233 @@
 %09%0A%09%09
-List%3CT%3E unassignedNodes = new ArrayList%3C%3E(nodes);%0A%09%09%0A%09%09while( !unassignedNodes.isEmpty() )%7B%0A%09%09%09Graph%3CT%3E component = component(unassignedNodes, seedSrc);%0A%09%09%09result.add(component
+Universe%3CT%3E u = new Universe%3C%3E(nodes);%0A%09%09Set%3CT%3E unassignedNodes = u.back(
 );%0A%09%09
-%7D
 %0A%09%09
-%0A%09%09return result;%0A%09%7D%0A%09%0A%09public Graph%3CT%3E component(List%3CT%3E unassignedNodes, Function%3CList%3CT%3E,T%3E seedSrc)%7B%0A%09%09%0A%09%09ConnectedComponent%3CT%3E newComponent = new ConnectedComponent%3CT%3E(nodes.size(), unassignedNodes);%0A%09%09%7B%0A%09%09%09int initUnassignedCount = unassignedNodes.size();%0A%09%09%09T seed = seedSrc.apply(unassignedNodes);%0A%09%09%09%0A%09%09%09if(unassignedNodes.size() == initUnassignedCount)%7B%0A%09%09%09%09unassignedNodes.remove(seed);%0A%09%09%09%7D%0A%09%09%09%0A%09%09%09newComponent.add(seed); //seed now in cuttingEdge%0A%09%09%7D%0A%09%09%0A%09%09while( !newComponent.cuttingEdgeIsEmpty() )%7B%0A%09%09%09newComponent.contract();%09//move cuttingEdge into edge and old edge into core%0A%09%09%09newComponent.grow();%09%09//add unincorporated nodes to cuttingEdge%0A%09%09%7D%0A%09%09%0A%09%09return new BasicGraph%3CT%3E(newComponent.contract())
+while(!unassignedNodes.isEmpty())%7B%0A%09%09%09Graph%3CT%3E component = component(unassignedNodes, seedSrc);%0A%09%09%09result.add(component);%0A%09%09%7D%0A%09%09%0A%09%09return result
 ;%0A%09%7D
@@ -2727,13 +2727,11 @@
 nent
-2(Lis
+(Se
 t%3CT%3E
@@ -2761,16 +2761,16 @@
 ion%3C
-Lis
+Se
 t%3CT%3E,
+ 
 T%3E s

use component2 implementation for component()