/* TreeGenerator.java
 * =========================================================================
 * This file is part of the GrInvIn project - http://www.grinvin.org
 * 
 * Copyright (C) 2005-2008 Universiteit Gent
 * 
 * This program 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 of the License, or (at
 * your option) any later version.
 * 
 * This program 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.
 * 
 * A copy of the GNU General Public License can be found in the file
 * LICENSE.txt provided with the source distribution of this program (see
 * the META-INF directory in the source jar). This license can also be
 * found on the GNU website at http://www.gnu.org/licenses/gpl.html.
 * 
 * If you did not receive a copy of the GNU General Public License along
 * with this program, contact the lead developer, or write to the Free
 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 */

package org.grinvin.conjecture.engine.apengine;

/**
 *
 * @author adpeeter
 */
public class TreeGenerator<T extends BinaryTree> {
    
    //
    protected T workingTree = null;

    //
    protected boolean completeWorkingTree = false;
    
    //
    protected int currentUnaryOperators;
    
    //
    protected int currentBinaryOperators;
    
    //
    protected TreeGeneratorStateStack stateStack;
    
    //
    protected TreeFactory<T> treeFactory;
    
    public TreeGenerator(TreeFactory<T> treeFactory) {
        this(0, 0, treeFactory);
    }
    
    //
    public TreeGenerator(int unaryOperators, int binaryOperators, TreeFactory<T> treeFactory) {
        stateStack = new TreeGeneratorStateStack();
        stateStack.pushNewDepthState(unaryOperators, binaryOperators);
        workingTree = null;
        this.treeFactory = treeFactory;
    }
    
    /**
     * Private class to represent the stack of the {@link TreeGenerator}. Handling this
     * manually improves computation speed.
     */
    protected static class TreeGeneratorStateStack extends StateStack<TreeGeneratorState> {
        
        //
        public TreeGeneratorState emptyState() {
            return new TreeGeneratorState(null, 0, 0, 0);
        }
        
        //
        public TreeGeneratorState[] createArray(int size) {
            return new TreeGeneratorState[size];
        }
        
        //
        private final void push(StateType type, int a, int b, int c) {
            if(top >= size) {
                super.extend();
            }
            TreeGeneratorState state = peek();
            top++;
            state.type = type;
            state.a = a;
            state.b = b;
            state.c = c;
        }
        
        /**
         * Push a new state that upon execution will remove the node with the given coordinates.
         * @param depth depth in the tree
         * @param leftrightpos position relative to the {@code parent}: {@code 0} for left, {@code 1} for right
         * @param parent parent of the node to be removed
         */
        public final void pushRemoveState(int depth, int leftrightpos, int parent) {
            push(StateType.REMOVE, depth, leftrightpos, parent);
        }
        
        //
        public void pushRecurseState(int depth, int pos, int endpos) {
            push(StateType.RECURSE, depth, pos, endpos);
        }
        
        /**
         * Push a new state that upon execution will start working with new unary and binary count.
         */
        public void pushNewDepthState(int unaryCount, int binaryCount) {
            push(StateType.NEWDEPTH, 0, unaryCount, binaryCount);
        }
        
    }
    
    //
    private enum StateType {
        RECURSE,
        REMOVE,
        NEWDEPTH
    }
    
    //
    private static class TreeGeneratorState {
        
        private TreeGeneratorState(StateType type, int a, int b, int c) {
            this.type = type;
            this.a = a;
            this.b = b;
            this.c = c;
        }
        
        public StateType type;
        public int a;
        public int b;
        public int c;
        
        //
        private int getRemoveDepth() {
            assert StateType.REMOVE == this.type;
            return this.a;
        }
        
        //
        private int getRemovePos() {
            assert StateType.REMOVE == this.type;
            return this.b;
        }
        
        //
        private int getRemoveParent() {
            assert StateType.REMOVE == this.type;
            return this.c;
        }
        
        //
        private int getRecurseDepth() {
            assert StateType.RECURSE == this.type;
            return this.a;
        }
        
        //
        private int getRecursePos() {
            assert StateType.RECURSE == this.type;
            return this.b;
        }
        
        //
        private int getRecurseEndPos() {
            assert StateType.RECURSE == this.type;
            return this.c;
        }
        
        //
        private int getDepthUnaryCount() {
            assert StateType.NEWDEPTH == this.type;
            return this.b;
        }
        
        //
        private int getDepthBinaryCount() {
            assert StateType.NEWDEPTH == this.type;
            return this.c;
        }
        
    }
    
    /**
     * Return the next {@link LabeledBinaryTree}.
     */
    public T nextTree() {
        
        completeWorkingTree = false;
        
        while(!completeWorkingTree) {
            extend();
        }
        
        return workingTree;
        
    }
    
    /**
     * Push a new depthstate on the stack with the next number of unary and binary operators.
     * The operators are added as follows:
     * <table>
     * <tr><th>unary</th><th<binary</th></tr>
     * <tr><td>0</td><td>0</td></tr>
     * <tr><td>1</td><td>0</td></tr>
     * <tr><td>0</td><td>1</td></tr>
     * <tr><td>2</td><td>0</td></tr>
     * <tr><td>1</td><td>1</td></tr>
     * <tr><td>3</td><td>0</td></tr>
     * <tr><td>0</td><td>2</td></tr>
     * </table>
     */
    protected void pushNextOperatorCount() {
        if (currentBinaryOperators > 0) {
            stateStack.pushNewDepthState(currentUnaryOperators + 2, currentBinaryOperators - 1);
        } else {
            if ((currentUnaryOperators % 2) > 0) {
                stateStack.pushNewDepthState(0, (currentUnaryOperators + 1) / 2);
            } else {
                stateStack.pushNewDepthState(1, currentUnaryOperators / 2);
            }
        }
    }
    
    /**
     * Try to extend the workingTree.
     */
    protected void extend() {
        
        TreeGeneratorState state = stateStack.pop();
        
        switch (state.type) {
            case RECURSE:
                int depth = state.getRecurseDepth();
                int pos = state.getRecursePos();
                int endpos = state.getRecurseEndPos();
                
                if(pos < endpos) {
                    stateStack.pushRecurseState(depth, pos + 1, endpos);
                    
                    int parent = workingTree.extendOn(depth, pos);
                    if(parent != -1) {
                        if(correct(workingTree)) {
                            if(complete(workingTree)) {
                                stateStack.pushRemoveState(depth, pos % 2, parent);
                                // we have a finished working tree
                                completeWorkingTree = true;
                            } else {
                                stateStack.pushRemoveState(depth, pos % 2, parent);
                                stateStack.pushRecurseState(depth, pos + 1, endpos);
                                stateStack.pushRecurseState(depth + 1, 0, workingTree.nodesonlevel(depth) * 2);
                            }
                        } else {
                            workingTree.removeOn(depth, pos % 2, parent);
                        }
                    }
                }
                break;
            case REMOVE:
                workingTree.removeOn(state.getRemoveDepth(), state.getRemovePos(), state.getRemoveParent());
                break;
            case NEWDEPTH:
                currentUnaryOperators = state.getDepthUnaryCount();
                currentBinaryOperators = state.getDepthBinaryCount();
                workingTree = treeFactory.createTree(currentUnaryOperators, currentBinaryOperators);
                pushNextOperatorCount();
                if (complete(workingTree)) {
                    // we have a finished working tree
                    completeWorkingTree = true;
                } else {
                    stateStack.pushRecurseState(1,0,2);
                }
                break;
            default:
                assert false : "Unexpected case: " + state.type;
        }

    }
    
    /**
     * Is the given {@link LabeledBinaryTree} complete? A tree is complete if its
     * amount of unary and binary operators matches the current unary and
     * binary operator count respectively.
     */
    public boolean complete(T tree) {
        return (tree.getUnaryCount() == currentUnaryOperators ) && (tree.getBinaryCount() == currentBinaryOperators);
    }
    
    /**
     * Is the given {@link LabeledBinaryTree} correct? A tree is correct if it is still
     * possible to extend it to a complete tree.
     */
    public boolean correct(T tree) {
        int unaryCount = tree.getUnaryCount();
        int binaryCount = tree.getBinaryCount();
        return (unaryCount <= currentUnaryOperators + 1) && (binaryCount <= currentBinaryOperators) && ((unaryCount + binaryCount) <= (currentUnaryOperators + currentBinaryOperators));
    }
    
}