/********************************************************************
 * COPYRIGHT:
 * Copyright (c) 2001-2006, International Business Machines Corporation and
 * others. All Rights Reserved.
 ********************************************************************/

package com.ibm.icu.text;

import java.util.List;
import java.util.HashSet;
import java.util.Set;

import com.ibm.icu.impl.Assert;

/**
 *   This class represents a node in the parse tree created by the RBBI Rule compiler.
 * @internal
 *
 */
class RBBINode {

    
 //   enum NodeType {
     static final int    setRef = 0;
     static final int    uset = 1;
     static final int    varRef = 2;
     static final int    leafChar = 3;
     static final int    lookAhead = 4;
     static final int    tag = 5;
     static final int    endMark = 6;
     static final int    opStart = 7;
     static final int    opCat = 8;
     static final int    opOr = 9;
     static final int    opStar = 10;
     static final int    opPlus = 11;
     static final int    opQuestion = 12;
     static final int    opBreak = 13;
     static final int    opReverse = 14;
     static final int    opLParen = 15;
     static final int    nodeTypeLimit = 16;    //  For Assertion checking only.
     
     static String []  nodeTypeNames = {
         "setRef",
         "uset",
         "varRef",
         "leafChar",
         "lookAhead",
         "tag",
         "endMark",
         "opStart",
         "opCat",
         "opOr",
         "opStar",
         "opPlus",
         "opQuestion",
         "opBreak",
         "opReverse",
         "opLParen"
};

//    enum OpPrecedence {      
    static final int    precZero   = 0;
    static final int    precStart  = 1;
    static final int    precLParen = 2;
    static final int    precOpOr   = 3;
    static final int    precOpCat  = 4;
        
    int          fType;   // enum NodeType
    RBBINode      fParent;
    RBBINode      fLeftChild;
    RBBINode      fRightChild;
    UnicodeSet    fInputSet;           // For uset nodes only.
    int          fPrecedence = precZero;   // enum OpPrecedence, For binary ops only.
    
    String       fText;                 // Text corresponding to this node.
                                        //   May be lazily evaluated when (if) needed
                                        //   for some node types.
    int           fFirstPos;            // Position in the rule source string of the
                                        //   first text associated with the node.
                                        //   If there's a left child, this will be the same
                                        //   as that child's left pos.
    int           fLastPos;             //  Last position in the rule source string
                                        //    of any text associated with this node.
                                        //    If there's a right child, this will be the same
                                        //    as that child's last postion.

    boolean      fNullable;            //  See Aho DFA table generation algorithm
    int           fVal;                 // For leafChar nodes, the value.
                                        //   Values are the character category,
                                        //   corresponds to columns in the final
                                        //   state transition table.

    boolean      fLookAheadEnd;        // For endMark nodes, set TRUE if
                                        //   marking the end of a look-ahead rule.

    Set           fFirstPosSet;         // See Aho DFA table generation algorithm
    Set           fLastPosSet;          // See Aho.       
    Set           fFollowPos;           // See Aho.
    
    int           fSerialNum;           //  Debugging aids.  Each node gets a unique serial number.
    static int    gLastSerial;

    RBBINode(int t) {
        Assert.assrt(t<nodeTypeLimit);
        fSerialNum    = ++gLastSerial;
        fType         = t;

        fFirstPosSet  = new HashSet(); 
        fLastPosSet   = new HashSet();
        fFollowPos    = new HashSet();
        if      (t==opCat)    {fPrecedence = precOpCat;}
        else if (t==opOr)     {fPrecedence = precOpOr;}
        else if (t==opStart)  {fPrecedence = precStart;}
        else if (t==opLParen) {fPrecedence = precLParen;}
        else fPrecedence   = precZero;
    }


    RBBINode(RBBINode other)  {
        fSerialNum   = ++gLastSerial;
        fType        = other.fType;
        fInputSet    = other.fInputSet;
        fPrecedence  = other.fPrecedence;
        fText        = other.fText;
        fFirstPos    = other.fFirstPos;
        fLastPos     = other.fLastPos;
        fNullable    = other.fNullable;
        fVal         = other.fVal;
        fFirstPosSet = new HashSet(other.fFirstPosSet);
        fLastPosSet  = new HashSet(other.fLastPosSet);
        fFollowPos   = new HashSet(other.fFollowPos);
    }


//-------------------------------------------------------------------------
//
//        cloneTree     Make a copy of the subtree rooted at this node.
//                      Discard any variable references encountered along the way,
//                      and replace with copies of the variable's definitions.
//                      Used to replicate the expression underneath variable
//                      references in preparation for generating the DFA tables.
//
//-------------------------------------------------------------------------
    RBBINode cloneTree() {
        RBBINode    n;

        if (fType == RBBINode.varRef) {
            // If the current node is a variable reference, skip over it
            //   and clone the definition of the variable instead.
            n = fLeftChild.cloneTree();
        } else if (fType == RBBINode.uset) {
            n = this;
        } else {
            n = new RBBINode(this);
            if (fLeftChild != null) {
                n.fLeftChild          = fLeftChild.cloneTree();
                n.fLeftChild.fParent = n;
            }
            if (fRightChild != null) {
                n.fRightChild          = fRightChild.cloneTree();
                n.fRightChild.fParent = n;
            }
        }
        return n;
    }


//-------------------------------------------------------------------------
//
//       flattenVariables   Walk a parse tree, replacing any variable
//                          references with a copy of the variable's definition.
//                          Aside from variables, the tree is not changed.
//
//                          Return the root of the tree.  If the root was not a variable
//                          reference, it remains unchanged - the root we started with
//                          is the root we return.  If, however, the root was a variable
//                          reference, the root of the newly cloned replacement tree will
//                          be returned, and the original tree deleted.
//
//                          This function works by recursively walking the tree
//                          without doing anything until a variable reference is
//                          found, then calling cloneTree() at that point.  Any
//                          nested references are handled by cloneTree(), not here.
//
//-------------------------------------------------------------------------
    RBBINode flattenVariables() {
        if (fType == varRef) {
            RBBINode retNode = fLeftChild.cloneTree();
            // delete this;
            return retNode;
        }

        if (fLeftChild != null) {
            fLeftChild = fLeftChild.flattenVariables();
            fLeftChild.fParent  = this;
        }
        if (fRightChild != null) {
            fRightChild = fRightChild.flattenVariables();
            fRightChild.fParent = this;
        }
        return this;
    }


//-------------------------------------------------------------------------
//
//      flattenSets    Walk the parse tree, replacing any nodes of type setRef
//                     with a copy of the expression tree for the set.  A set's
//                     equivalent expression tree is precomputed and saved as
//                     the left child of the uset node.
//
//-------------------------------------------------------------------------
    void flattenSets() {
        Assert.assrt(fType != setRef);

        if (fLeftChild != null) {
            if (fLeftChild.fType==setRef) {
                RBBINode setRefNode = fLeftChild;
                RBBINode usetNode   = setRefNode.fLeftChild;
                RBBINode replTree   = usetNode.fLeftChild;
                fLeftChild          = replTree.cloneTree();
                fLeftChild.fParent  = this;
             } else {
                fLeftChild.flattenSets();
            }
        }

        if (fRightChild != null) {
            if (fRightChild.fType==setRef) {
                RBBINode setRefNode = fRightChild;
                RBBINode usetNode   = setRefNode.fLeftChild;
                RBBINode replTree   = usetNode.fLeftChild;
                fRightChild           = replTree.cloneTree();
                fRightChild.fParent  = this;
                // delete setRefNode;
            } else {
                fRightChild.flattenSets();
            }
        }
    }


//-------------------------------------------------------------------------
//
//       findNodes()     Locate all the nodes of the specified type, starting
//                       at the specified root.
//
//-------------------------------------------------------------------------
    void   findNodes(List dest, int kind) {
        if (fType == kind) {
            dest.add(this);
        }
        if (fLeftChild != null) {
            fLeftChild.findNodes(dest, kind);
        }
        if (fRightChild != null) {
            fRightChild.findNodes(dest, kind);
        }
    }

    
    //-------------------------------------------------------------------------
    //
    //        print.         Print out a single node, for debugging.
    //
    //-------------------------------------------------------------------------
    static void printNode(RBBINode n) {

        if (n==null) {
            System.out.print (" -- null --\n");
        } else {
            RBBINode.printInt( n.fSerialNum, 10);
            RBBINode.printString(nodeTypeNames[n.fType], 11);
            RBBINode.printInt(n.fParent==null? 0     : n.fParent.fSerialNum, 11);
            RBBINode.printInt(n.fLeftChild==null? 0  : n.fLeftChild.fSerialNum, 11);
            RBBINode.printInt(n.fRightChild==null? 0 : n.fRightChild.fSerialNum, 12);
            RBBINode.printInt(n.fFirstPos, 12);
            RBBINode.printInt(n.fVal, 7);
            
            if (n.fType == varRef) {
                System.out.print(" " + n.fText);
            }
        }
        System.out.println("");
    }
 

    // Print a String in a fixed field size.
    // Debugging function.
    static void printString(String s, int minWidth)
    {
        for (int i=minWidth; i<0; i++) {
            // negative width means pad leading spaces, not fixed width.
            System.out.print(' ');
        }
        for (int i=s.length(); i<minWidth; i++) {
            System.out.print(' ');
        }
        System.out.print(s);
    }
    
     //
     //  Print an int in a fixed size field.
     //  Debugging function.
     //
     static void printInt(int i, int minWidth) {
         String s = Integer.toString(i);
         printString(s, Math.max(minWidth, s.length()+1));
     }
     
     static void printHex(int i, int minWidth) {
         String s = Integer.toString(i, 16);
         String leadingZeroes = "00000".substring(0, Math.max(0, 5-s.length()));
         s = leadingZeroes+s;
         printString(s, minWidth);
     }
 

     // -------------------------------------------------------------------------
     //
     //        print.         Print out the tree of nodes rooted at "this"
     //
     // -------------------------------------------------------------------------
    void printTree(boolean printHeading) {
        if (printHeading) {
            System.out.println( "-------------------------------------------------------------------");
            System.out.println("    Serial       type     Parent  LeftChild  RightChild    position  value");
        }
        printNode(this);
            // Only dump the definition under a variable reference if asked to.
            // Unconditinally dump children of all other node types.
            if (fType != varRef) {
                if (fLeftChild != null) {
                    fLeftChild.printTree(false);
                }
                
                if (fRightChild != null) {
                    fRightChild.printTree(false);
                }
            }
    }

}