public class Analyzer {

    private Set< Root > roots;

    private final Revisions revisions;

    public Analyzer(final Revisions revisions) {

        roots = new HashSet<>();
        this.revisions = revisions;
    }

    int compacted = 0;

    public void markInteresting(final String rootPath) {

        addRoots(roots, revisions.getLast().getRevisionNumber(), rootPath, true);

        final List< Revision > revisionsReversed = new ArrayList<>(revisions.getAll());
        Collections.reverse(revisionsReversed);
        for (final Revision revision : revisionsReversed) {
            compact(revision);
            if (revision.getRevisionNumber() % 500 == 0) {
                System.out.println("R: " + revision.getRevisionNumber() + ", Roots: " + roots.size()
                    + ", Compacted: " + compacted);
                compacted = 0;
            }

            final List< Change > changesReversed = new ArrayList<>(revision.getChanges());
            Collections.reverse(changesReversed);
            for (Change change : changesReversed) {
                final Set< Root > newRoots = new HashSet<>();
                newRoots.addAll(roots);
                for (final Root root : roots) {
                    if (revision.getRevisionNumber() <= root.revision) {
                        if (change.getNodePath().equals(root.path)) {

                            // The root we are watching is identical to the change path.
                            change.setInclude(true);
                            // We are copied from somewhere, so start watching the copy source.
                            if (change.getNodeCopyfromPath() != null) {
                                addRoots(newRoots, change, root.interestedInContent);
                            }
                            if (change.getNodeAction() == NodeAction.ADD
                                || change.getNodeAction() == NodeAction.REPLACE) {
                                // This is when/where this root got added, so no longer track it.
                                newRoots.remove(root);
                            }
                        } else if (root.path.startsWith(change.getNodePath() + "/")) {
                            // The root we are watching falls under the change path.
                            change.setInclude(true);
                            // If the parent is copied from somewhere, so are we.
                            // Start watching our source.
                            if (change.getNodeCopyfromPath() != null) {
                                final String newRootPath =
                                    change.getNodeCopyfromPath()
                                        + root.path.substring(change.getNodePath().length(),
                                            root.path.length());
                                addRoots(newRoots, change.getNodeCopyfromRev(), newRootPath,
                                    root.interestedInContent);
                            }
                            if (change.getNodeAction() == NodeAction.ADD
                                || change.getNodeAction() == NodeAction.REPLACE) {
                                // This is when/where this root got added, so no longer track it.
                                newRoots.remove(root);
                            }
                        } else if (root.interestedInContent
                            && change.getNodePath().startsWith(root.path + "/")) {
                            // The change path lives under a root we are watching with content.
                            change.setInclude(true);
                            if (change.getNodeCopyfromPath() != null) {
                                addRoots(newRoots, change, true);
                            }
                        }
                    }
                }
                roots = newRoots;
            }
        }

        // Always include revision 0, which just sets up the root node and has no changes.
        revisions.get(0).setInclude(true);
    }

    private void compact(final Revision revision) {

        final Set< Root > cleanup = new HashSet< Root >();
        for (Root root : roots) {
            if (root.revision > revision.getRevisionNumber()) {
                final Root newRoot =
                    new Root(revision.getRevisionNumber(), root.path, root.interestedInContent);
                cleanup.add(newRoot);
            } else {
                cleanup.add(root);
            }
        }
        compacted += roots.size() - cleanup.size();

        roots = cleanup;
    }

    private void addRoots(final Set< Root > roots, Change change, final boolean interestedInContent) {

        addRoots(roots, change.getNodeCopyfromRev(), change.getNodeCopyfromPath(), interestedInContent);
    }

    private void addRoots(final Set< Root > roots, final Integer rev, final String path,
        final boolean interestedInContent) {

        final Root newRoot = new Root(rev, path, interestedInContent);
        if (roots.contains(newRoot)) {
            // This exact root is already included. So it's should be too.
            return;
        }
        roots.add(newRoot);

        String subPath = path;
        while (subPath.lastIndexOf('/') != -1) {
            subPath = subPath.substring(0, subPath.lastIndexOf('/'));
            final Root newPathRoot = new Root(rev, subPath, false);
            if (roots.contains(newPathRoot)) {
                // This exact root is already included. So it's should be too.
                return;
            }
            roots.add(newPathRoot);
        }
    }

}