/*************************************
*
*  (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);
}
}