package ee.ttu.algoritmid.friends;

import java.util.*;
import java.util.AbstractMap.SimpleEntry;

public class AL06 {
    public UndirectedGraph graph = new UndirectedGraph();

    public class UndirectedGraph {
        private HashMap<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
        private ArrayList<Integer> shortPath = new ArrayList<Integer>();

        /**
         * Add undirected edge to the graph.
         *
         * @param one    one element of the edge
         * @param other  the other element of edge
         */
        public void addEdge(Integer one, Integer other) {
            if (!graph.containsKey(one)) {
                List<Integer> edges = new ArrayList<Integer>();
                edges.add(other);
                graph.put(one, edges);
            } else {
                if (!graph.get(one).contains(other)) {
                    graph.get(one).add(other);
                }
            }
            if (!graph.containsKey(other)) {
                List<Integer> edges = new ArrayList<Integer>();
                edges.add(one);
                graph.put(other, edges);
            } else {
                if (!graph.get(other).contains(one)) {
                    graph.get(other).add(one);
                }
            }
        }

        /**
         * Return the graph.
         * @return  the internal graph structure.
         */
        public HashMap<Integer, List<Integer>> getGraph() {
            return graph;
        }

        /**
         * Perform breadth first search.
         *
         * @param start   the vertex to start the search from
         * @param goal    the goal vertex to find
         *
         * @return        the number of vertices of the path from start to goal including start and goal (e.g.,
         *                start = A, goal = C, path = A, B, C => 3) and the path itself as a list of integers.
         *                NB! You can return null as path and only return the number of nodes
         *                    that connect the start and goal vertices for partial credit
         *                    (some tests only check for number of nodes)
         */
        public SimpleEntry<Integer, List<Integer>> breadthFirstSearch(Integer start, Integer goal) {
            shortPath.clear();
            HashMap<Integer, List<Integer>> currentGraph = this.getGraph();

            ArrayList<Integer> path = new ArrayList<>();

            if (start.equals(goal) && currentGraph.containsKey(start)) {
                path.add(start);
                return new SimpleEntry<Integer, List<Integer>>(1, path);
            }

            ArrayDeque<Integer> queue = new ArrayDeque<>();

            ArrayDeque<Integer> visitedVertexes = new ArrayDeque<>();

            queue.offer(start);

            while (!queue.isEmpty()) {
                Integer vertex = queue.poll();
                visitedVertexes.offer(vertex);

                ArrayList<Integer> neighbours = findNeighbours(vertex);

                for (int i = 0; i < neighbours.size(); i++) {
                    Integer neighbour = neighbours.get(i);

                    path.add(neighbour);
                    path.add(vertex);

                    if (neighbour.equals(goal)) {
                        ArrayList<Integer> goalPath = findShortPath(start, goal, path);
                        return new SimpleEntry<Integer, List<Integer>>(goalPath.size(), goalPath);
                    } else {
                        if (!visitedVertexes.contains(neighbour)) {
                            queue.offer(neighbour);
                        }
                    }
                }

            }
            return null;
        }

        private ArrayList<Integer> findNeighbours(Integer vertex) {
            List<Integer> neighbours;
            Set<Integer> keys = graph.keySet();
            for (Integer key : keys) {
                if (key.equals(vertex)) {
                    neighbours = graph.get(key);
                    return new ArrayList<Integer>(neighbours);
                }
            }
            return new ArrayList<Integer>();
        }

        private ArrayList<Integer> findShortPath(Integer start, Integer goal, ArrayList<Integer> path) {
            Integer s = path.get(path.indexOf(goal) + 1);

            shortPath.add(0, goal);

            if (s.equals(start)) {
                shortPath.add(0, start);
                return shortPath;
            } else {
                return findShortPath(start, s, path);
            }
        }
    }

    /**
     * Use buildGraphAndFindLink to build a graph using the UndirectedGraph class and then use its breadthFirstSearch to
     * return the links.
     *
     * @param  friends  the list of friends as pairs (people are denoted as integers)
     *                  (e.g., [[2, 7], [9, 5]] means that 2 is friends with 7 and 9 is friends with 5)
     * @param  pair     the pair to be searched
     * @return          the number of people that connect the searched pair including the pair itself (e.g., if pair is
     *                  = [1, 4] and path is [1, 2, 3, 4], the number of people is 4) the list of people that connect
     *                  the searched pair (e.g., pair = [1, 4] => result = [1, 7, 11, 3, 2, 4])
     */
    public SimpleEntry<Integer, List<Integer>> buildGraphAndFindLink(List<SimpleEntry<Integer, Integer>> friends,
                                                                     SimpleEntry<Integer, Integer> pair) {
        UndirectedGraph graph = new UndirectedGraph();

        for (int i = 0; i < friends.size(); i++) {
            SimpleEntry<Integer, Integer> friendsPair = friends.get(i);
            graph.addEdge(friendsPair.getKey(), friendsPair.getValue());
        }

        return graph.breadthFirstSearch(pair.getKey(), pair.getValue());
    }
}


package ee.ttu.algoritmid.friends;

/**
 *
 */
public class Main {
    public static void main(String[] args) {
        AL06 impl = new AL06();
        impl.graph.addEdge(1, 2);
        impl.graph.addEdge(1, 2);
        impl.graph.addEdge(3, 2);
        System.out.println(impl.graph.getGraph());
        System.out.println(impl.graph.breadthFirstSearch(1, 3));
    }
}