TwistyPuzzleLib

  private static final float[] mCanonical = new float[] {0.343f,0.509f,0.789f};

      str.append("\n  ");

      for(int f=0; f<numFaces; f++)

        int[][] multigonIndex = mMultigonIndices[f];

        for(int[] mulIndex : multigonIndex)

          int len = mulIndex.length;

          for(int v=0; v<len; v++)

            str.append( v==0 ? " " : ", ");

            str.append(mulIndex[v]);

        if( mFaceIsOuter!=null ) str.append( mFaceIsOuter[f] ? " outer" : " inner");

        else                     str.append(" mFaceIsOuter is null");

        str.append("\n  ");

      str.append("numFaces: ");

      str.append("\n  ");

      for(int f=0; f<numFaces; f++)

        int[] vertIndex = mVertIndices[f];

        if( mFaceIsOuter!=null ) str.append( mFaceIsOuter[f] ? " outer" : " inner");

        else                     str.append(" mFaceIsOuter is null");

        str.append("\n  ");

///////////////////////////////////////////////////////////////////////////////////////////////////

// Return 1 if arr1>arr2, 0 if arr1==arr2, -1 if arr1<arr2.

// if arr1.length > arr2.length, then arr1>arr2.

// if arr1.length==arr2.lenght, then treat individual integers of arrays as digits in a 2^32-mal

// system and compare those two 2^32-mal numbers.

  private int compare(int[] arr1, int[] arr2)

    {

    int len1 = arr1.length;

    int len2 = arr2.length;

    if( len1>len2 ) return 1;

    if( len1<len2 ) return -1;

    for(int i=0; i<len1; i++)

      {

      int diff = arr1[i]-arr2[i];

      if( diff>0 ) return 1;

      if( diff<0 ) return -1;

      }

    return 0;

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// return the same array, but rotate it so that its smallest value is first.

// (the values in the array are guaranteed to not repeat)

  private int[] rotateSmallestValueToFirstIndex(int[] indices)

    {

    int smallest = Integer.MAX_VALUE;

    int smallestIndex = -1;

    int len = indices.length;

    for(int i=0; i<len; i++)

      if( indices[i]<smallest )

        {

        smallest = indices[i];

        smallestIndex = i;

        }

    int[] ret = new int[len];

    for(int i=0; i<len; i++) ret[i] = indices[(smallestIndex+i)%len];

    return ret;

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// Canonical form. The point: we want to be able to quickly see if two instances of ObjectShape are

// in fact the same shape. (the 'equals' function)

//

// Multigon not supported (rationale: this is only needed in TwistyCutSolid - i.e. for objects which

// are created by cutting a solid along a number of planes. This will never result in multigon shapes)

//

//   1. Sort the vertices from left to right according to the order they are on the mCanonical vector

//      (here first compute the 'auxiliary' and 'permutation' arrays so that we don't have to keep

//       rearranging the indices in the VertIndices multiarrays every time we swap two vertices)

//   2. Then, sort the indices on every every face by placing the lowest index first.

//   3. Then, sort the faces (and correspondingly the mFaceIsOuters).

//      Each face contains a list of indices (I1,I2,...,IN). Sort by those lists by treating each

//      integer in it as a digit in 2^32-mal number system and thus as if the whole list were a single

//      2^32-mal integer.

  public void toCanonicalForm()

    {

    int numVertices = mVertices.length;

    int[] permutation = new int[numVertices];

    float[] auxiliary = new float[numVertices];

    for(int v=0; v<numVertices; v++)

      {

      float[] vert = mVertices[v];

      auxiliary[v] = mCanonical[0]*vert[0] + mCanonical[1]*vert[1] + mCanonical[2]*vert[2];

      permutation[v] = v;

      }

    // insertion sort auxiliary[] and permutation[]

    int sortedAlready = 1;

    while( sortedAlready<numVertices )

      {

      float x = auxiliary[sortedAlready];

      int n = permutation[sortedAlready];

      int i = sortedAlready;

      while( i>0 && auxiliary[i-1]>x )

        {

        auxiliary[i]   = auxiliary[i-1];

        permutation[i] = permutation[i-1];

        i--;

        }

      auxiliary[i]  = x;

      permutation[i]= n;

      sortedAlready++;

      }

    // now 'permutation' is in a form which is slow to use when we rename mVerIndices. Change it to

    // another form where map[i]=j means 'index which used to be i must be changed to j'

    int[] perm = new int[numVertices];

    for(int i=0; i<numVertices; i++) perm[permutation[i]] = i;

    if( mFacesMultigon )

      {

      android.util.Log.e("D", "error in ObjectShape.toCanonicalForm: multigon unsupported!");

      }

    else

      {

      float[][] tmpVertices = new float[numVertices][];

      for(int i=0; i<numVertices; i++) tmpVertices[i] = mVertices[permutation[i]];

      for(int i=0; i<numVertices; i++) mVertices[i] = tmpVertices[i];

      int numFaces = mVertIndices.length;

      for(int f=0; f<numFaces; f++)

        {

        int[] indices = mVertIndices[f];

        int len = indices.length;

        for(int i=0; i<len; i++) indices[i] = perm[indices[i]];

        mVertIndices[f] = rotateSmallestValueToFirstIndex(indices);

        }

      // insertion sort mVertIndices and mFaceIsOuter

      sortedAlready = 1;

      while( sortedAlready<numFaces )

        {

        int[] x = mVertIndices[sortedAlready];

        boolean n = mFaceIsOuter[sortedAlready];

        int i = sortedAlready;

        while( i>0 && compare(mVertIndices[i-1],x)>0 )

          {

          mVertIndices[i] = mVertIndices[i-1];

          mFaceIsOuter[i] = mFaceIsOuter[i-1];

          i--;

          }

        mVertIndices[i] = x;

        mFaceIsOuter[i] = n;

        sortedAlready++;

        }

      }

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// both shapes already in canonical form!

  public boolean equals(ObjectShape shape)

    {

    int len1 = mFaceIsOuter.length;

    int len2 = shape.mFaceIsOuter.length;

    if( len1 != len2 ) return false;

    for(int f=0; f<len1; f++)

      if( mFaceIsOuter[f] != shape.mFaceIsOuter[f] ) return false;

    if( mFacesMultigon != shape.mFacesMultigon ) return false;

    if( mFacesMultigon )

      {

      int numIndices1 = mMultigonIndices.length;

      int numIndices2 = shape.mMultigonIndices.length;

      if( numIndices1 != numIndices2 ) return false;

      for(int i=0; i<numIndices1; i++)

        {

        int[][] indi1 = mMultigonIndices[i];

        int[][] indi2 = shape.mMultigonIndices[i];

        int ilen1 = indi1.length;

        int ilen2 = indi2.length;

        if( ilen1 != ilen2 ) return false;

        for(int j=0; j<ilen1; j++)

          {

          int[] ind1 = indi1[j];

          int[] ind2 = indi2[j];

          int l1     = ind1.length;

          int l2     = ind2.length;

          if( l1 != l2 ) return false;

          for(int k=0; k<l1; k++)

            if( ind1[k] != ind2[k] ) return false;

          }

        }

      }

    else

      {

      int numIndices1 = mVertIndices.length;

      int numIndices2 = shape.mVertIndices.length;

      if( numIndices1 != numIndices2 ) return false;

      for(int i=0; i<numIndices1; i++)

        {

        int[] ind1 = mVertIndices[i];

        int[] ind2 = shape.mVertIndices[i];

        int ilen1 = ind1.length;

        int ilen2 = ind2.length;

        if( ilen1 != ilen2 ) return false;

        for(int j=0; j<ilen1; j++)

            if( ind1[j] != ind2[j] ) return false;

        }

      }

    float MIN_ERR = 0.001f;

    int numv1 = mVertices.length;

    int numv2 = shape.mVertices.length;

    if( numv1 != numv2 ) return false;

    for(int v=0; v<numv1; v++)

      {

      float[] v1 = mVertices[v];

      float[] v2 = shape.mVertices[v];

      float dx = v1[0]-v2[0];

      float dy = v1[1]-v2[1];

      float dz = v1[2]-v2[2];

      if( dx*dx+dy*dy+dz*dz > MIN_ERR ) return false;

      }

    return true;

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

  public ObjectShape rotate(Static4D quat)

    {

    float[] tmp = new float[4];

    int numVertices = mVertices.length;

    float[][] verts = new float[numVertices][];

    float qx = quat.get0();

    float qy = quat.get1();

    float qz = quat.get2();

    float qw = quat.get3();

    float[] q = new float[] {qx,qy,qz,qw};

    for(int v=0; v<numVertices; v++)

      {

      float[] vert = mVertices[v];

      QuatHelper.rotateVectorByQuat(tmp,vert[0],vert[1],vert[2],1,q);

      verts[v] = new float[] {tmp[0],tmp[1],tmp[2]};

      }

    int numOuter = mFaceIsOuter.length;

    boolean[] outer= new boolean[numOuter];

    for(int f=0; f<numOuter; f++) outer[f] = mFaceIsOuter[f];

    if( mFacesMultigon )

      {

      int numIndices = mMultigonIndices.length;

      int[][][] indices = new int[numIndices][][];

      for(int i=0; i<numIndices; i++)

        {

        int[][] indi = mMultigonIndices[i];

        int len = indi.length;

        indices[i] = new int[len][];

        for(int j=0; j<len; j++)

          {

          int[] ind = indi[j];

          int l     = ind.length;

          int[] t   = new int[l];

          for(int k=0; k<l; k++) t[k] = ind[k];

          indices[i][j] = t;

          }

        }

      ObjectShape ret = new ObjectShape(verts,indices);

      ret.setFaceOuter(outer);

      return ret;

      }

    else

      {

      int numIndices = mVertIndices.length;

      int[][] indices = new int[numIndices][];

      for(int i=0; i<numIndices; i++)

        {

        int[] ind = mVertIndices[i];

        int len = ind.length;

        int[] t = new int[len];

        for(int j=0; j<len; j++) t[j] = ind[j];

        indices[i] = t;

        }

      ObjectShape ret = new ObjectShape(verts,indices);

      ret.setFaceOuter(outer);

      return ret;

      }

    }

    float fy = faceAxis.get1();

    float fz = faceAxis.get2();

    Static4D[] quats = getQuats();

    float[][] pos = getCubitPositions();

    Static3D[] faceAxis = getFaceAxis();

    float[] dist = getDist3D();

    float[][] potentialVertices = FactoryShape.computePotentialVertices(mCutPlanes);

    ObjectShape[] shapes = new ObjectShape[mNumCubits];

    for(int c=0; c<mNumCubits; c++)

      {

      shapes[c] = FactoryShape.createShape(mCutPlanes,potentialVertices,pos[c],pos[c]);

      shapes[c].computeFaceOuter(pos[c],faceAxis,dist);

      shapes[c].debug();

      shapes[c].toCanonicalForm();

      }

    mCubitToVariantQuatMap = new int[mNumCubits][2];

    for(int c=0; c<mNumCubits; c++) mCubitToVariantQuatMap[c][0] = -1;

    int variant = 0;

    for(int c=0; c<mNumCubits; c++)

      if( mCubitToVariantQuatMap[c][0]<0 )

        {

        mCubitToVariantQuatMap[c][0] = variant++;

        for(int q=0; q<mNumQuats; q++)

          {

          ObjectShape rotShape = shapes[c].rotate(quats[q]);

          rotShape.toCanonicalForm();

          for(int d=c+1; d<mNumCubits; d++)

            if( rotShape.equals(shapes[d]) )

              {

              mCubitToVariantQuatMap[d][0] = variant-1;

              mCubitToVariantQuatMap[d][1] = q;

              }

          }

        }

    mShapes = new ObjectShape[variant];

    for(int c=0; c<mNumCubits; c++)

      {

      int v = mCubitToVariantQuatMap[c][0];

      if( mShapes[v]==null ) mShapes[v] = shapes[c];

      }

    android.util.Log.e("D", "shape variants: "+variant);

    for(int v=0; v<variant; v++) mShapes[v].debug();