import java.util.*;
import java.awt.Color;

// The class defined below holds some logic that should be spun off to other
// classes.  Howewer, we decline to define those other classes because we
// wish to reduce the number of internet transactions (one per class) that
// occur during this application's download.

public class Polytope extends GeometricObject
{
    // Indices into an array of flag bits.
    private static final int    TRAVERSED   = 0;

    private double[]    centerOfGravity;
    private Polytope[]  children;
    private Color       color;
    private int         dimension;
    private int         flags;
    private double[][]  localBasis;
    private double[]    outwardNormal;
    private Polytope[]  parents;
    private Polytope[]  points;
    private Polytope    rootPolytope;

    public Polytope ()
    {
        centerOfGravity = null; // may or may not be set.
        children        = null;
        color           = null;
        dimension       = -2;   // dimension of subpolytope (-2 means "null")
        flags           = 0;
        localBasis      = null;
        outwardNormal   = null; // meaningful only if dim == dim(root) - 1.
        parents         = null;
        points          = null;
        rootPolytope    = null; // ptr to the topmost d-dimensional cube.
    }

    public boolean getFlag (int i)
    {
        return ((flags & (1 << i)) != 0);
    }

    public void setFlag (int i, boolean value)
    {
        flags = (value ? (flags | (1 << i)) : (flags & ~(1 << i)));
    }

    public int getDimension ()
    {
        return dimension;
    }

    public double[] getCenterOfGravity ()
    {
        return centerOfGravity;
    }

    public double[] getCenter ()
    {
        return getCenterOfGravity ();
    }

    public int getNumChildren ()
    {
        return children != null ? children . length : 0;
    }

    public int getNumParents ()
    {
        return parents != null ? parents . length : 0;
    }

    public Polytope otherChildOf (Polytope parent)
    {
        if (parent == null || parent . getNumChildren () <= 1) return null;
        return  parent . children [(parent . children [0] == this) ? 1 : 0];
    }

    public Polytope otherParentOf (Polytope child)
    {
        if (child  == null || child  . getNumParents  () <= 1) return null;
        return  child  . parents  [(child  . parents  [0] == this) ? 1 : 0];
    }

    public void draw (PolytopeDisplay display, double[] viewerCoords,
                      boolean facesFlag, boolean shadingFlag)
    {
        if (facesFlag)
            drawHierarchyFaces (display, viewerCoords, shadingFlag);
        else
            drawHierarchyEdges (display, viewerCoords,
                                true /* hide back edges */,
                                display.getForegroundColor() /*edgeColor*/);

        clearTraversalFlags ();
    }

    private void drawHierarchyFaces (PolytopeDisplay display,
                                     double[]        viewerCoords,
                                     boolean         shadingFlag)
    {
        if (! getFlag (TRAVERSED)) {
            setFlag (TRAVERSED, true);

            if      (dimension <= 1)
                return;
            else if (dimension == rootPolytope . dimension - 1) {
                // Do not show the back faces.
                double m_dotProduct = 0.0;
                for (int i = rootPolytope . dimension; --i >= 0 ;)
                    m_dotProduct += (viewerCoords[i] - centerOfGravity[i]) *
                                    outwardNormal [i];

                if (m_dotProduct < 0.0) return;
            }

            if (dimension == 2) {
                int numPoints = points . length;
                double[] xCoords = new double [numPoints];
                double[] yCoords = new double [numPoints];
                for (int p = numPoints; --p >= 0 ;) {
                    double[] m_2DPoint = intersectionWithImagePlane (
                        points [p] . centerOfGravity, viewerCoords, 2);
                    xCoords [p] = m_2DPoint [0];
                    yCoords [p] = m_2DPoint [1];
                }

                Color   shadedColor;
                if (shadingFlag) {
                    double  brightness = display . shading (outwardNormal);
                    shadedColor = new Color (
                        (int) (brightness * (double) color . getRed ()),
                        (int) (brightness * (double) color . getGreen ()),
                        (int) (brightness * (double) color . getBlue ()));
                }
                else {
                    shadedColor = color;
                }

                display . fillPolygon(shadedColor,xCoords,yCoords,numPoints);
            }
            else  {
                for (int i = getNumChildren (); --i >= 0 ;)
                    children [i] . drawHierarchyFaces (display,viewerCoords,
                                                       shadingFlag);
            }
        }
    }

    private void drawHierarchyEdges (PolytopeDisplay display,
                                     double[]        viewerCoords,
                                     boolean         hideBackEdges,
                                     Color           edgeColor)
    {
        if (! getFlag (TRAVERSED)) {
            setFlag (TRAVERSED, true);

            if      (dimension <= 0)
                return;
            else if (dimension == 1) {
                double[] m_pointA = intersectionWithImagePlane (
                            children [0] . centerOfGravity, viewerCoords, 2);
                double[] m_pointB = intersectionWithImagePlane (
                            children [1] . centerOfGravity, viewerCoords, 2);

                display . drawLine (edgeColor, m_pointA [0], m_pointA [1],
                                               m_pointB [0], m_pointB [1]);
            }
            else  {
                if (dimension == rootPolytope.dimension-1 && hideBackEdges) {
                    // Do not show the back egdes.
                    double m_dotProduct = 0.0;
                    for (int i = rootPolytope . dimension; --i >= 0 ;)
                        m_dotProduct +=
                            (viewerCoords [i] - centerOfGravity [i]) *
                             outwardNormal [i];

                    if (m_dotProduct < 0.0) return;
                }
    
                for (int i = getNumChildren (); --i >= 0 ;)
                    children[i].drawHierarchyEdges (display,viewerCoords,
                                                    hideBackEdges,edgeColor);
            }
        }
    }

    public void translate (double[] translation)
    {
        if (translation == null) return;
        translateHierarchy (translation);
        clearTraversalFlags ();
    }

    private void translateHierarchy (double[] translation)
    {
        if (! getFlag (TRAVERSED)) {
            setFlag (TRAVERSED, true);

            if (centerOfGravity != null)
                for (int i = rootPolytope . dimension; --i >= 0 ;)
                    centerOfGravity [i] += translation [i];

            for (int i = getNumChildren (); --i >= 0 ;)
                children [i] . translateHierarchy (translation);
        }
    }

    public void rotate (double[][] rotationMatrix)
    {
        if (rotationMatrix == null) return;
        rotateHierarchy (rotationMatrix, cloneVector (centerOfGravity));
        clearTraversalFlags ();
    }

    private void rotateHierarchy (double[][] rotationMatrix,
                                  double[]   centerOfRotation)
    {
        if (! getFlag (TRAVERSED)) {
            setFlag (TRAVERSED, true);
            int m_rootDimension = rootPolytope . dimension;
            double[] m_tempVector = new double [m_rootDimension];

            if (centerOfGravity != null) {
                for (int i = m_rootDimension; --i >= 0 ;)
                    m_tempVector [i] = centerOfGravity [i] -
                                       centerOfRotation [i];
                matrixVectorMultiply (rotationMatrix, m_tempVector,
                                      centerOfGravity);
                for (int i = m_rootDimension; --i >= 0 ;)
                    centerOfGravity [i] += centerOfRotation [i];
            }

            if (localBasis != null) {
                for (int v = localBasis . length; --v >= 0 ;) {
                    double[] basisVector = localBasis [v];
                    for (int i = m_rootDimension; --i >= 0 ;)
                        m_tempVector [i] = basisVector [i];
                    matrixVectorMultiply (rotationMatrix, m_tempVector,
                                          basisVector);
                }
            }

            if (outwardNormal != null) {
                for (int i = m_rootDimension; --i >= 0 ;)
                    m_tempVector [i] = outwardNormal [i];
                matrixVectorMultiply (rotationMatrix, m_tempVector,
                                      outwardNormal);
            }

            for (int i = getNumChildren (); --i >= 0 ;)
                children[i].rotateHierarchy(rotationMatrix,centerOfRotation);
        }
    }

    public void clearTraversalFlags ()
    {
        if (getFlag (TRAVERSED)) {
            setFlag (TRAVERSED, false);
            for (int i = getNumChildren (); --i >= 0 ;)
                children [i] . clearTraversalFlags ();
        }
    }

    public void clearAllFlags ()
    {
        if (getFlag (TRAVERSED)) {
            flags = 0;
            for (int i = getNumChildren (); --i >= 0 ;)
                children [i] . clearTraversalFlags ();
        }
    }

    //
    // Return with the Grunbaum graph representation of a d-dimensional cube.
    //
    public static Polytope newCube (int      m_dimension,
                                    double   m_edgeLength,
                                    double[] m_cubeCenterOfGravity)
    {
        int m_powerOf3 = 1;
        for (int i = m_dimension; --i >= 0; m_powerOf3 *= 3);

        // A temporary array which will hold the hierarchy's subcubes:
        Polytope [] m_subcubes = new Polytope [m_powerOf3 + 1];
        for (int i = m_powerOf3+1; --i >= 0; m_subcubes[i] = new Polytope());

        Polytope    m_root = m_subcubes [m_powerOf3-1]; // root cube

        // A dummy (-1)-dimensional subcube is a child of all the
        // 0-dimensional subcubes:
        Polytope m_bottomSubcube = m_subcubes [m_powerOf3];
        m_bottomSubcube . centerOfGravity = null;
        m_bottomSubcube . children        = null;
        m_bottomSubcube . color           = null;
        m_bottomSubcube . dimension       = -1;
        m_bottomSubcube . flags           = 0;
        m_bottomSubcube . localBasis      = null;
        m_bottomSubcube . outwardNormal   = null;
        m_bottomSubcube . parents         = new Polytope [1 << m_dimension];
        m_bottomSubcube . points          = null;
        m_bottomSubcube . rootPolytope    = m_root;

        // Prepare to gather the bottom subcube's 0-dimensional parents.
        int m_bottomSubcubeParentsIndex = 0;

        // Initialize the subcubes.
        for (int i = 0; i < m_powerOf3; i++) {  /* Index must go upward, */
                                                /* from pts to polytope. */
            // Let the base-3 decomposition of index i be
            //           0           1           2
            //   (t_0 * 3  +  t_1 * 3  +  t_2 * 3  +  ...).
            //
            // For each j,
            //   if digit t_j = 0, let set S_j = {0};
            //   if digit t_j = 1, let set S_j = {1};
            //   if digit t_j = 2, let set S_j = the open interval (0,1).
            //
            // In the code below, the index i will represent the
            // subcube defined by the cartesian product
            //
            //   S_0 x S_1 x S_2 x ...
            //
            // For example, if dimension = 4 and i = 47, then
            //                 0         1         2         3
            //   i = 47 = 2 * 3  +  0 * 3  +  2 * 3  +  1 * 3
            //
            // will represent the subcube (0,1) x {0} x (0,1) x {1}.
            //

            // Determine the number of dimensions k spanned by subcube i.
            int k = 0;
            for (int divisor = 1; divisor < m_powerOf3; divisor *= 3)
                if (i / divisor % 3 == 2) k++;

            double[] m_centerOfGravity =
                (k >= 0) ? new double [m_dimension] : null;
            double[] m_outwardNormal =
                (k == m_dimension - 1) ? new double [m_dimension] : null;

            int         m_parentIndex = m_dimension - k;
            Polytope[]  m_parents = (m_parentIndex > 0)
                                        ? new Polytope[m_parentIndex] : null;
            int         m_childIndex  = (k > 0) ? (2 * k) : 1;
            Polytope[]  m_children = new Polytope [m_childIndex];

            for (int divisor=1, j=0; divisor < m_powerOf3; divisor *= 3, j++)
            {
                int t_j = i / divisor % 3; // jth base-3 digit

                // Determine jth coordinate for subcube's center of gravity.
                m_centerOfGravity [j] = m_cubeCenterOfGravity [j] +
                    m_edgeLength * ((t_j==0) ? -0.5 : (t_j==1) ? 0.5 : 0.0);

                // If subcube is (d-1)-dimensional, determine outward normal.
                if (k == m_dimension - 1)
                    m_outwardNormal [j] =
                        (t_j == 0) ? -1.0 : (t_j == 1) ? 1.0 : 0.0;

                switch (t_j) {
                        // If t_j != 2, let S_j = (0,1) to determine parent.
                case 0: m_parents[--m_parentIndex] = m_subcubes[i+2*divisor];
                        break;
                case 1: m_parents[--m_parentIndex] = m_subcubes[i+  divisor];
                        break;

                case 2: // Collapse interval set S_j = (0,1) into {0} and {1}
                        // to determine 2 (k-1)-dimensional subsubcubes.
                        m_children[--m_childIndex] = m_subcubes[i-  divisor];
                        m_children[--m_childIndex] = m_subcubes[i-2*divisor];
                        break;
                }
            }

            // (-1)-dimensional subcube is child of 0-dimensional subcubes.
            if (k == 0) {
                m_children [0] = m_bottomSubcube;
                m_bottomSubcube . parents [m_bottomSubcubeParentsIndex++] =
                    m_subcubes [i];
            }

            Polytope[] m_points = null;
            Color      m_color  = null;

            if (k == 2) {
                // Put the 1-d subcubes in circular order.
                Polytope temp = m_children [1];
                m_children [1] = m_children [2];
                m_children [2] = temp;

                // Determine points in circular order; used for polygon fills.
                m_points = new Polytope [4];
                for (int m = 2; --m >= 0 ;) {
                    for (int n = 2; --n >= 0 ;) {
                        if (m_children [0] . children [m] ==
                            m_children [1] . children [n]    )
                        {
                            m_points [0] = m_children [0] . children [m];
                        }
                    }
                }
                for (int m = 1; m <= 3; m++) {
                    Polytope[] pts = m_children [m] . children;
                    m_points [m] = pts [(pts [0] != m_points [m-1]) ? 0 : 1];
                }
                if (m_dimension == 3) {
                    if      (m_outwardNormal[0] !=0.0) m_color = Color.red;
                    else if (m_outwardNormal[1] !=0.0) m_color = Color.green;
                    else if (m_outwardNormal[2] !=0.0) m_color = Color.blue;
                }
            }

            double[][] m_localBasis = null;
            if (k == m_dimension) {
                m_localBasis = new double [m_dimension][m_dimension];
                for (int m = m_dimension; --m >= 0 ;) {
                    for (int n = m_dimension; --n >= 0 ;)
                        m_localBasis [m][n] = 0.0;
                    m_localBasis [m][m] = 1.0;
                }
            }

            Polytope m_currentSubcube = m_subcubes [i];
            m_currentSubcube . centerOfGravity = m_centerOfGravity;
            m_currentSubcube . color           = m_color;
            m_currentSubcube . children        = m_children;
            m_currentSubcube . dimension       = k;
            m_currentSubcube . flags           = 0;
            m_currentSubcube . localBasis      = m_localBasis;
            m_currentSubcube . outwardNormal   = m_outwardNormal;
            m_currentSubcube . parents         = m_parents;
            m_currentSubcube . points          = m_points;
            m_currentSubcube . rootPolytope    = m_root;
        }

        return m_root;
    }
}