/*
 * Copyright 2012-2015 Red Hat, Inc.
 *
 * This file is part of Thermostat.
 *
 * Thermostat is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published
 * by the Free Software Foundation; either version 2, or (at your
 * option) any later version.
 *
 * Thermostat is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Thermostat; see the file COPYING.  If not see
 * <http://www.gnu.org/licenses/>.
 *
 * Linking this code with other modules is making a combined work
 * based on this code.  Thus, the terms and conditions of the GNU
 * General Public License cover the whole combination.
 *
 * As a special exception, the copyright holders of this code give
 * you permission to link this code with independent modules to
 * produce an executable, regardless of the license terms of these
 * independent modules, and to copy and distribute the resulting
 * executable under terms of your choice, provided that you also
 * meet, for each linked independent module, the terms and conditions
 * of the license of that module.  An independent module is a module
 * which is not derived from or based on this code.  If you modify
 * this code, you may extend this exception to your version of the
 * library, but you are not obligated to do so.  If you do not wish
 * to do so, delete this exception statement from your version.
 */

package com.redhat.thermostat.vm.heap.analysis.command;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Enumeration;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import com.sun.tools.hat.internal.model.JavaHeapObject;

public class FindRoot {

    private Set<JavaHeapObject> visitedObjects;

    public Collection<HeapPath<JavaHeapObject>> findShortestPathsToRoot(JavaHeapObject obj, boolean findAll) {
        HeapPath<JavaHeapObject> path = new HeapPath<>(obj);
        List<HeapPath<JavaHeapObject>> pathsSoFar = new LinkedList<>();
        pathsSoFar.add(path);
        visitedObjects = new HashSet<>();
        return findShortestPathToRoot(pathsSoFar, findAll);
    }

    private Collection<HeapPath<JavaHeapObject>> findShortestPathToRoot(List<HeapPath<JavaHeapObject>> pathsSoFar, boolean findAll) {
        List<HeapPath<JavaHeapObject>> newPaths = new LinkedList<>();
        Collection<HeapPath<JavaHeapObject>> roots = new ArrayList<>();
        for (HeapPath<JavaHeapObject> path : pathsSoFar) {
            JavaHeapObject last = path.getNode();
            if (visitedObjects.contains(last)) {
                continue;
            }
            @SuppressWarnings("rawtypes")
            Enumeration referrers = last.getReferers();
            while (referrers.hasMoreElements()) {
                JavaHeapObject referrer = (JavaHeapObject) referrers.nextElement();
                HeapPath<JavaHeapObject> newPath = new HeapPath<>(referrer, path);
                newPaths.add(newPath);
                if (referrer.getRoot() != null) {
                    roots.add(newPath);
                    if (! findAll) {
                        return roots;
                    }
                }
            }
            visitedObjects.add(last);
        }
        if (newPaths.isEmpty()) {
            return roots;
        } else {
            Collection<HeapPath<JavaHeapObject>> foundRoots = findShortestPathToRoot(newPaths, findAll);
            roots.addAll(foundRoots);
            return roots;
        }
    }


}