org.eclipse.osbp.xtext.datainterchange/src/org/eclipse/osbp/xtext/datainterchange/jvmmodel/ManageJoins.java

/*
 *                                                                            
 *  Copyright (c) 2011 - 2018 - Loetz GmbH & Co KG, 69115 Heidelberg, Germany 
 *                                                                            
 *  All rights reserved. This program and the accompanying materials           
 *  are made available under the terms of the Eclipse Public License 2.0        
 *  which accompanies this distribution, and is available at                  
 *  https://www.eclipse.org/legal/epl-2.0/                                 
 *                                 
 *  SPDX-License-Identifier: EPL-2.0                                 
 *                                                                            
 *  Initial contribution:                                                      
 *     Loetz GmbH & Co. KG                              
 * 
 */
package org.eclipse.osbp.xtext.datainterchange.jvmmodel;

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * The Class ManageJoins finds all paths of a directed graph.
 *
 * @param <T> the generic type
 */
public class ManageJoins<T> {
	
	/** The graph. */
	private final JoinGraph<T> graph;

    /**
     * Instantiates a new manage joins.
     *
     * @param graphFindAllPaths the graph find all paths
     */
    public ManageJoins(JoinGraph<T> graphFindAllPaths) {
        if (graphFindAllPaths == null) {
            throw new NullPointerException("input graph must not be null.");
        }
        graph = graphFindAllPaths;
    }

    /**
     * Gets the all paths to destination node.
     *
     * @param source the source
     * @param destination the destination
     * @return the all paths
     */
    public List<List<T>> getAllPathsToDestination(T source, T destination) {
        List<List<T>> paths = new ArrayList<>();
        recursive(source, destination, paths, new LinkedHashSet<T>());
        return paths;
    }

    /**
     * Gets the all join names.
     *
     * @param source the source
     * @param destination the destination
     * @return all joins
     */
    public List<List<String>> getAllJoinsToDestination(T source, T destination) {
    	List<List<T>> paths = getAllPathsToDestination(source, destination);
        List<List<String>> joins = new ArrayList<>();
        for(List<T> outer:paths) {
        	List<String> list = new ArrayList<>();
        	joins.add(list);
        	T previous = null;
        	for(T inner:outer) {
        		if(previous != null) {
        			list.add(graph.joinsFrom(previous).get(inner));
        		}
       			previous = inner;
        	}
        }
        return joins;
    }

    /**
     * Gets the all join names.
     *
     * @param source the source
     * @return all joins
     */
    public List<List<String>> getAllJoins(T source) {
    	List<List<T>> paths = getAllPathsToDestination(source, null);
    	List<List<String>> joins = new ArrayList<>();
    	for(List<T> outer:paths) {
    		List<String> list = new ArrayList<>();
    		joins.add(list);
    		T previous = null;
    		for(T inner:outer) {
    			if(previous != null) {
    				list.add(graph.joinsFrom(previous).get(inner));
    			}
    			previous = inner;
    		}
    	}
    	return joins;
    }
    
    /**
     * Gets the all paths.
     *
     * @param source the source
     * @return the all paths until the end
     */
    public List<List<T>> getAllPaths(T source) {
    	List<List<T>> paths = new ArrayList<>();
    	recursive(source, null, paths, new LinkedHashSet<T>());
    	return paths;
    }

    /**
     * Recursive.
     *
     * @param current the current
     * @param paths the paths
     * @param path the path
     */
    // cycles are ignored
    private void recursive (T current, T destination, List<List<T>> paths, LinkedHashSet<T> path) {
        path.add(current);

        // cut path if destination is reached
        if (destination != null && current == destination) {
            paths.add(new ArrayList<T>(path));
            path.remove(current);
            return;
        }
        
        Set<T> joins = graph.joinsFrom(current).keySet();

        boolean hadRecursion = false;
        for (T t : joins) {
            if (!path.contains(t)) {
                recursive (t, destination, paths, path);
                hadRecursion = true;
            }
        }
        // prefer longest paths
        if(destination == null && !hadRecursion) {
        	paths.add(new ArrayList<T>(path));
        }
        path.remove(current);
    }    
}