/*
 * Tree.java
 *
 * Created on May 18, 2004, 9:22 PM
 */

package spamfilter.decisiontree;

import spamfilter.email.*;
import java.util.Stack;
import java.util.Vector;

/**
 *
 * @author  AaronStJ
 */
public class Tree implements Cloneable {
    
    private static final double CHANCE_OF_INTERNAL_NODE = 1/3;
    
    private Corpus spamCorpus;
    private Corpus nonSpamCorpus;
    
    private Node head;
    
    public Tree(Tree p1, Tree p2) {                
        
        spamCorpus = p1.spamCorpus;
        nonSpamCorpus = p2.nonSpamCorpus;        
        
        //flip the parents half of the time
        if(Math.random() > 0.50) {
            Tree temp = p1;
            p1 = p2;
            p2 = temp;
        }
        
        //make this node a clone of p1
        head = (InternalNode)p1.head.clone();                
        
        //get lists of the nodes in this and p2 for the enxt step
        Vector childNodes = this.getInternalNodes();
        Vector p2Nodes = p2.getAllNodes();                               
        
        //figure out which node from p2 to swap into which node of this
        InternalNode childNodeToSwap = (InternalNode)childNodes.get((int)Math.floor(Math.random() * childNodes.size()));        
        
        Node p2NodeToSwap = (Node)p2Nodes.get((int)Math.floor(Math.random() * p2Nodes.size()));                        
        
        Node clone = (Node)p2NodeToSwap.clone();                
        
        
        //swap it in 
        
        if(Math.random() > 0.50)
            childNodeToSwap.setFalseChild(clone);
        else
            childNodeToSwap.setTrueChild(clone);                
        
        optimize();
                
   }
          
    public Tree(Corpus spam, Corpus nonSpam) {
        spamCorpus = spam;
        nonSpamCorpus = nonSpam;
        
        int size = 0;
        
        Stack s = new Stack();
        if(Math.random() > 0.5)
            head = new InternalNode(spamCorpus.getRandomWord());
        else;
            head = new InternalNode(nonSpamCorpus.getRandomWord());
        
        s.push(head);
        
        while(!s.empty()) {
            InternalNode n = (InternalNode)s.pop();
            
            //set the false child
            if(Math.random() < this.CHANCE_OF_INTERNAL_NODE && size < 500) {
                if(Math.random() > 0.5)
                    n.setFalseChild(new InternalNode(spamCorpus.getRandomWord()));
                else
                    n.setFalseChild(new InternalNode(nonSpamCorpus.getRandomWord()));
                s.push(n.getFalseChild());
                size++;
            }
            else {
                if(Math.random() > 0.5)
                    n.setFalseChild(new LeafNode(true));
                else
                    n.setFalseChild(new LeafNode(false));
                
            }
            
            //set the true child
            if(Math.random() < this.CHANCE_OF_INTERNAL_NODE) {
                if(Math.random() > 0.5)
                    n.setTrueChild(new InternalNode(spamCorpus.getRandomWord()));
                else
                    n.setTrueChild(new InternalNode(nonSpamCorpus.getRandomWord()));
                s.push(n.getTrueChild());
            }
            else {
                if(Math.random() > 0.5)
                    n.setTrueChild(new LeafNode(true));
                else
                    n.setTrueChild(new LeafNode(false));
                
            }
        }
        
        optimize();
        
        
    }

    public void mutate() {
        Vector v = getAllNodes();
        Node n = (Node)v.get((int)Math.floor(Math.random() * v.size())); 
        
        if(n.isLeaf()) {
            //simply flip the value
            ((LeafNode)n).setValue(!((LeafNode)n).getValue());
        }
        else
        {
            //replace the word here with a new random word
            if(Math.random() > 0.50)
                ((InternalNode)n).setWord(spamCorpus.getRandomWord());
            else
                ((InternalNode)n).setWord(nonSpamCorpus.getRandomWord());
        }
        optimize();
    }
    
    public boolean isEmailSpam(Email e) {
        Node n = head;
        
        while(!n.isLeaf()) {
            if(e.constainsWord(((InternalNode)n).getWord()))
                n = ((InternalNode)n).getTrueChild();
            else
                n = ((InternalNode)n).getFalseChild();
        }
        
        return ((LeafNode)n).getValue();
        
    }

    private Vector getAllNodes() {
        Vector v = new Vector();
        Stack s = new Stack();
        s.push(head);
        
        while(!s.empty()) {
            Node n = (Node)s.pop();
            
            v.add(n);
            
            if(!n.isLeaf())
            {
                s.push(((InternalNode)n).getFalseChild());
                s.push(((InternalNode)n).getTrueChild());
            }
        }
        
        return v;
    }
    
    private Vector getInternalNodes() {
        Vector v = new Vector();
        Stack s = new Stack();
        s.push(head);
        
        while(!s.empty()) {
            Node n = (Node)s.pop();
            
            if(!n.isLeaf())
            {
                v.add(n);
                s.push(((InternalNode)n).getFalseChild());
                s.push(((InternalNode)n).getTrueChild());
            }
        }
        
        return v;
    }
    
    public int getSize() {
        int size=0;
        Stack s = new Stack();
        s.push(head);
        
        while(!s.empty()) {
            Node n = (Node)s.pop();               
            if(!n.isLeaf())
            {
                s.push(((InternalNode)n).getFalseChild());
                s.push(((InternalNode)n).getTrueChild());
            }
            size++;
        }
        
        return size;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        Stack nodes = new Stack();
        Stack levels = new Stack();
        
        nodes.push(head);
        levels.push(new Integer(0));              
        
        while(!nodes.empty()) {
            Node n = (Node)nodes.pop();
            int level = ((Integer)levels.pop()).intValue();
            
            if(n.isLeaf()) {
                for(int i = 0; i < level; i++) sb.append(" ");
                if(((LeafNode)n).getValue())
                    sb.append("* 1\n");                
                else
                    sb.append("* 0\n");
            }
            else
            {
                for(int i = 0; i < level; i++) sb.append(" ");
                    sb.append("[" + ((InternalNode)n).getWord() + "]\n");
                
                nodes.push(((InternalNode)n).getFalseChild());
                levels.push(new Integer(level + 1));                

                nodes.push(((InternalNode)n).getTrueChild());
                levels.push(new Integer(level + 1));
            }
            
        }
        
        return new String(sb);
    }
    
    public double trueLeafNodesRatio()  {
        Stack s = new Stack();
        s.push(head);
        int trueLeafNodes = 0;
        int falseLeafNodes = 0;
        
        while(!s.empty()) {
            Node n = (Node)s.pop();
            
            if(!n.isLeaf())
            {
                s.push(((InternalNode)n).getFalseChild());
                s.push(((InternalNode)n).getTrueChild());                               
            }
            else {
                if(((LeafNode)n).getValue())
                    trueLeafNodes++;
                else
                    falseLeafNodes++;                    
            }
            
        }
        
        return (double)trueLeafNodes / (double)(trueLeafNodes + falseLeafNodes);
    
    }
    
    public void optimize() {
        boolean keepGoing;
        do {
            keepGoing = false;

            Stack s = new Stack();
            Stack parents = new Stack();
            s.push(head);

            while(!s.empty()) {
                Node n = (Node)s.pop();
                InternalNode parent = null;
                if(n != head)
                    parent = (InternalNode)parents.pop();                          

                if(!n.isLeaf())
                {
                    InternalNode in = (InternalNode)n;
                    
                    s.push(in.getFalseChild());
                    parents.push(n);
                    s.push(in.getTrueChild());                               
                    parents.push(n);
                    
                    
                    if(!in.getFalseChild().isLeaf() && 
                        ((InternalNode)in.getFalseChild()).getWord().compareToIgnoreCase(in.getWord()) == 0) {
                            in.setFalseChild(((InternalNode)in.getFalseChild()).getFalseChild());
                            keepGoing = true;
                            break;
                    }

                    if(!in.getTrueChild().isLeaf() && 
                        ((InternalNode)in.getTrueChild()).getWord().compareToIgnoreCase(in.getWord()) == 0) {
                            in.setTrueChild(((InternalNode)in.getTrueChild()).getTrueChild());
                            keepGoing = true;
                            break;
                    }
                     

                    if(in.getFalseChild().isLeaf() && in.getTrueChild().isLeaf()) {                        
                        if(((LeafNode)in.getFalseChild()).getValue() == 
                        ((LeafNode)in.getTrueChild()).getValue()) {
                            if(parent == null) {
                                keepGoing = false;
                                break;
                            }
                            if(parent.getFalseChild() == n) {
                                parent.setFalseChild(new LeafNode(((LeafNode)in.getFalseChild()).getValue()));
                                keepGoing = true;
                                break;
                            }
                            else {
                                parent.setTrueChild(new LeafNode(((LeafNode)in.getFalseChild()).getValue()));
                                keepGoing = true;
                                break;
                            }
                        }
                    }

                }

            }
        } while (keepGoing);

    }
    
    public Object clone() {
        Tree t = null;
        try {
            t = (Tree)super.clone();
            t.head = (InternalNode)this.head.clone();
        } catch (Exception e) { }
        return t;
    }   
    
}
