/* BinaryTree.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;

import java.util.Arrays;

/**
 * This class represents a binary tree. It is implemented as an array with
 * pointers to the children.
 */
public class BinaryTree implements Cloneable {
    
    //
    private static final int UNDEFINED = Integer.MAX_VALUE;
    
    //
    protected int[] contents;
    
    //
    private int[][] nodelist;
    
    //
    private int[] nodesonlevel;
    
    //
    protected int firstfreepos;
    
    //
    protected int unaryCount;
    
    //
    protected int binaryCount;
    
    /**
     * Create a new binary tree with {@code unaryOperators} unary operators and
     * {@code binaryOperators} binary operators.
     */
    public BinaryTree(int unaryOperators, int binaryOperators) {
        contents = new int[(unaryOperators + (2 * binaryOperators) + 1) * 2];
        nodelist = new int[unaryOperators + binaryOperators + 2][(unaryOperators + (2 * binaryOperators) + 1) * 2];
        nodesonlevel = new int[unaryOperators + binaryOperators + 2];
        
        
        firstfreepos = 2;
        unaryCount = 0;
        binaryCount = 0;
        nodelist[0][nodesonlevel[0]] = 0;
        nodesonlevel[0] = 1;
        
        Arrays.fill(contents, UNDEFINED);
    }
    
    /**
     * Create a new binary tree. This constructor is used by the {@link BinaryTree#clone} method.
     */
    protected BinaryTree(int[] newcontents, int firstfreeposition, int unaryCount, int binaryCount) {
        //TODO: nodelist, nodesonlevel
        contents = new int[newcontents.length];
        System.arraycopy(newcontents, 0, contents, 0, newcontents.length);
        firstfreepos = firstfreeposition;
        this.unaryCount = unaryCount;
        this.binaryCount = binaryCount;
    }

    //
    public BinaryTree clone() {
        return new BinaryTree(contents, firstfreepos, unaryCount, binaryCount);
    }
    
    //
    public String toString() {
        return toString(0);
    }
    
    //
    protected String toString(int parent) {
        StringBuilder result = new StringBuilder();
        if (childCount(parent) > 0) {
            result.append("( ");
            for (int child : children(parent))
                result.append(toString(child));
            result.append(") ");
        } else {
            result.append("inv ");
        }
        return result.toString();
    }
    
    /**
     * Return the number of children for the given node.
     * @param parent the parent to start counting
     * @return the number of children for the given node
     */
    public final int childCount(int parent) {
        if (hasLeftChild(parent)) {
            if (hasRightChild(parent)) {
                return 2;
            } else {
                return 1;
            }
        } else {
            return 0;
        }
    }
    
    /**
     * Return the children of the given node.
     * @param parent the parent of the children
     * @return an array of size <= 2 containing the left and the right child
     */
    public final int[] children(int parent) {
        int left = leftChild(parent);
        int right = rightChild(parent);
        if (left != UNDEFINED) {
            if (right != UNDEFINED) {
                return new int[] { left, right };
            } else {
                return new int[] { left };
            }
        } else {
            return new int[] {};
        }
    }
    
    /**
     * Does the node have a left child?
     * @param parent parent node nummber
     * @return {@code true} when {@code parent} has a left child or false otherwise
     */
    public final boolean hasLeftChild(int parent) {
        return leftChild(parent) != UNDEFINED;
    }
    
    /**
     * Does the node have a right child?
     * @param parent parent node nummber
     * @return {@code true} when {@code parent} has a right child or false otherwise
     */
    public final boolean hasRightChild(int parent) {
        return rightChild(parent) != UNDEFINED;
    }
    
    /**
     * Return the left child of the given node.
     * @param parent the parent of the child
     * @return the left child of the parent
     */
    public final int leftChild(int parent) {
        return contents[parent];
    }
    
    /**
     * Return the right child of the given node.
     * @param parent the parent of the child
     * @return the right child of the parent
     */
    public final int rightChild(int parent) {
        return contents[parent + 1];
    }
    
    /**
     * Return the current number of unary operators.
     */
    public final int getUnaryCount() {
        return unaryCount;
    }
    
    /**
     * Return the current number of binary operators.
     */
    public final int getBinaryCount() {
        return binaryCount;
    }
    
    /**
     * Return the current number of nodes, this equals: {@code binaryCount * 2 + unaryCount + 1}.
     */
    public final int getNodeCount() {
        return getBinaryCount() * 2 + getUnaryCount() + 1;
    }
    
    /**
     * Return the number of nodes on the given depth.
     * @param depth the depth of the tree
     * @return the number of nodes on the given depth
     */
    public final int nodesonlevel(int depth) {
        return nodesonlevel[depth];
    }
    
    /**
     * Add a new node on depth {@code depth} and position {@code pos}.
     * @param depth the depth to add a new node
     * @param pos the position to add a new node
     * @return the parent of the new node, or {@code -1} when no node could be added
     */
    public final int extendOn(int depth, int pos) {
        //make sure the given pos is possible
        if(nodesonlevel[depth-1] * 2 > pos) {
            int parent = nodelist[depth-1][pos/2];
            int child;
            if (pos % 2 == 0) { //even
                child = newLeftChild(parent);
            } else { //odd
                child = newRightChild(parent);
            }
            if (child != -1) {
                nodelist[depth][nodesonlevel[depth]] = child;
                nodesonlevel[depth]++;
                return parent;
            } else {
                return -1;
            }
            
        } else {
            return -1;
        }
    }
    
    /**
     * Remove the node on the given {@code depth} and {@code pos} with the given {@code parent}.
     */
    public final void removeOn(int depth, int pos, int parent) {
        if(pos == 0) {
            removeLeftChild(parent);
        } else { // pos == 1
            removeRightChild(parent);
        }
        nodesonlevel[depth]--;
    }
    
    /**
     * Create a new left child for the given node.
     * @param parent the node that will get a new left child
     * @return the new child
     */
    public final int newLeftChild(int parent) {
        int result = firstfreepos++;
        firstfreepos++;
        contents[parent] = result;
        unaryCount++;
        //binaryCount does not change
        return result;
    }
    
    /**
     * Create a new right child for the given node.
     * @param parent the node that will get a new right child
     * @return the new child or {@code -1} if there is no left child
     */
    public final int newRightChild(int parent) {
        if (!hasLeftChild(parent)) {
            //throw new IllegalStateException("Cannot create right child: no left child exists.");
            return -1;
        } else {
            int result = firstfreepos++;
            firstfreepos++;
            contents[parent + 1] = result;
            unaryCount--;
            binaryCount++;
            return result;
        }
    }
    
    /**
     * Remove the left child of the given node.
     * @param parent the parent of which the left child should be removed
     */
    public final void removeLeftChild(int parent) {
        contents[parent] = UNDEFINED;
        firstfreepos -= 2;
        unaryCount--;
        //binaryCount does not change
    }
    
    /**
     * Remove the right child of the given node.
     * @param parent the parent of which the right child should be removed
     */
    public final void removeRightChild(int parent) {
        contents[parent + 1] = UNDEFINED;
        firstfreepos -= 2;
        unaryCount++;
        binaryCount--;
    }
    
    
}