/*************************************
 *
 *  Main.java :: Bryan Chadwick
 *  (One possible) Solution for the Extra Credit, Leaf Covering Problem
 *
 *  See trees.cd/trees.beh for structures and a bit of other code.
 *
 *************************************/
import trees.*;
import edu.neu.ccs.demeterf.*;
import edu.neu.ccs.demeterf.demfgen.lib.*;
import java.io.FileInputStream;

/** Main class for Leaf Covering check */
public class Main{
    /** Shorter print method...*/
    static void p(String s){ System.out.println(s); }

    /** Main Program... */
    public static void main(String[] args) throws Exception{
        if(args.length != 1){
            p(" usage: java Main <fileName>");
            return;
        }
        Problem pr = Problem.parse(new FileInputStream(args[0]));
        
        List<Tuple> not = uncovered(pr.ms, pr.ts);
        p(" Covered? == "+not.isEmpty());

        /* Print the uncovered Leafs... */
        if(!not.isEmpty())
            p(" UnCovered Leafs:\n"+not.toString("\n","     "));
    }

    /** Return the List of leaf Tuples implied by the Trees 
     *    'ts' that are not covered by a Tuple in 'm'
     */
    static List<Tuple> uncovered(final List<Tuple> m, final List<Tree> ts){
        final List<Tuple> leafs = leafTuples(ts);
        
        return leafs.filterout(new List.Pred<Tuple>(){
                public boolean huh(final Tuple l){
                    return m.fold(new List.Fold<Tuple,Boolean>(){
                            public Boolean fold(Tuple n, Boolean r){
                                return r || covers(ts,n,l);
                            }
                        }, false);
                }
            });
    }

    /** In the given list of Trees, are all the elements of 'a' ancestors
     *    of corresponding elements of 'b'? */
    static boolean covers(List<Tree> ts, Tuple a, Tuple b){
        if(ts.isEmpty())return true;
        return (covers(ts.top(),a.first(),b.first()) &&
                covers(ts.pop(),a.rest(),b.rest()));
        
    }
    
    /** In the given Tree, is 'a' an ancestor of the Leaf 'b'? */
    static boolean covers(Tree t, ident a, ident b){
        return leafs(find(t,a)).contains(""+b);
    }
    
    /** Class used to traverse the Tree, and find a matching subtree
     *  
     *  The basic idea is to search the whole tree.  If a leaf matches
     *    then we return it. If the subtree exist below a Node, we return
     *    it. Otherwise we check the current Node name, and return the
     *    current Node or None. Everything happens bottom up.
     */
    static class Finder extends ID{
        Option<Tree> combine(Leaf t, ident n, ident f){
            return (n.equals(f))?Option.<Tree>some(t):Option.<Tree>none();
        }
        Option<Tree> combine(Node t, ident n, Option<Tree> ch, ident f){
            if(ch.isSome())return ch;
            return (n.equals(f))?Option.<Tree>some(t):Option.<Tree>none();
        }
        Option<Tree> combine(Empty<Tree> t){ return Option.none(); }
        Option<Tree> combine(Cons<Tree> t, Some<Tree> s){ return s; }
        Option<Tree> combine(Cons<Tree> t, None<Tree> s, Option<Tree> o){
            return o;
        }
    } 

    /** Find the subtree that is tagged with the identifier 'f' */
    static Tree find(Tree t, ident f){
        return new Traversal(new Finder())
            .<Option<Tree>>traverse(t,f).inner();
    }
    
    /** Find all possible tuple combinations of the leafs from the trees */
    static List<Tuple> leafTuples(List<Tree> ts){
        final List<List<String>> leafs =
            ts.map(new List.Map<Tree,List<String>>(){
                    public List<String> map(Tree t){ return leafs(t); }
                });
        return leafs.foldr(new List.Fold<List<String>, List<Tuple>>(){
                public List<Tuple> fold(final List<String> ss, final List<Tuple> tl){
                    return ss.foldr(new List.Fold<String, List<Tuple>>(){
                            public List<Tuple> fold(final String s, List<Tuple> fl){
                                return tl.map(new List.Map<Tuple,Tuple>(){           
                                        public Tuple map(Tuple t){
                                            return t.push(s);
                                        }
                                    }).append(fl);
                            }
                        }, List.<Tuple>create());
                }
            }, List.<Tuple>create(new Tuple(List.<ident>create())));
    }

    /** Function Class to grab all the Leaf labels in a Tree */
    static class Leafs extends ID{
        String combine(ident i){ return ""+i; }
        List<String> combine(Tree t, String n){ return List.<String>create(n); }
        List<String> combine(Tree t, String n, List<String> l){ return l; }
        List<String> combine(Empty<Tree> e){ return List.<String>create(); }
        List<String> combine(Cons<Tree> c, List<String> f, List<String> r){
            return f.append(r);
        }
    }

    /** Find all the Leafs of the given Tree */
    static List<String> leafs(Tree t){
        return new Traversal(new Leafs()).traverse(t);
    }
    
    /** Find all immediate children of the given Tree */
    static List<Tree> children(Tree t){
        return Traversal.onestep(new ID(){
                List<Tree> combine(Tree t){ return List.<Tree>create(); }
                List<Tree> combine(Tree t, ident n, List<Tree> l){ return l; }
            }).traverse(t);
    }
}