TwistyPuzzleLib

  MitmTable(int numCubits, int numQuats)

    double tmp = Math.log(numQuats) / Math.log(2);

    double numBytes = numCubits*tmp/8;

    mBytesPerEntry = (int)Math.ceil(numBytes);  // this many bytes will be needed to store one position

    int branchingFactor = object.getBranchingFactor();

    buildRecursive(object,branchingFactor,-1,len);

  int[][] tryReaching(SolvedObject object, int[][] endQuats, int len)

    int numQuats = endQuats.length;

    int[] indices = new int[numQuats];

    boolean thereIsNext;

    do

      {

      int[][] ret = tryReachingRecursive(object,endQuats,indices,len);

      if( ret!=null ) return ret;

      thereIsNext = getNext(endQuats,indices);

      }

    while( thereIsNext );

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

  int[][] tryReachingRecursive(SolvedObject object, int[][] endQuats, int[] indices, int len)

    {

    object.setUpStartingQuats(endQuats,indices);

    }

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

  private void buildRecursive(SolvedObject object, int branching, int previousMove, int len)

    {

    int[] quats = object.getCubitQuats();

    byte[] signature = computeSignature(quats);

    mData.add(signature);

    if( len>0 )

      for(int m=0; m<branching; m++)

        if( object.movesDontClash(m,previousMove) )

          {

          object.makeMove(m);

          buildRecursive(object,branching,m,len-1);

          object.backMove(m);

          }

    }

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

  private boolean getNext(int[][] quats, int[] indices)

    {

    }

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

  private byte[] computeSignature(int[] quats)

    {

    byte[] ret = new byte[mBytesPerEntry];

    // TODO

    return ret;

    }

    mTable = new MitmTable(numCubits, numQuats);

  private int[][] solution(int[][] endQuats, int maxlen)

    return mTable.tryReaching(mObject,endQuats,tmpBackward);

  private int[][] findSol(int[][] endQuats, int maxlen)

    int[][] s = solution(endQuats,maxlen);

  int[][] findSolution(int[][] endQuats)

    return findSol(endQuats,mForwardDepth+mBackwardDepth);

      boolean success = solveAnySubphase(endQuats,solved,sub,numSubphases,tmp,solution,whichSubphase);

                                   int[][][] solution, int[] whichSubphase)

          solution[sub] = findSol(endQuats,l);

  private final int mBranchingFactor;

  private final int[][] mMoveTable;

    int[] numL       = object.getNumLayers();

    mQuats           = object.getQuats();

    mOrigPos         = object.getCubitPositions(numL);

    mAxis            = object.getRotationAxis();

    mBasicAngles     = object.getBasicAngles();

    mRotateable      = object.getLayerRotatable(numL);

    mNumQuats        = mQuats.length;

    mBranchingFactor = computeBranchingFactor();

    mMoveTable       = computeMoveTable();

    int[] quatF     = computeQuatForward();

    int[] quatB     = computeQuatBackward();

    mCubits = new SolvedObjectCubit(mOrigPos,mAxis,object.getCuts(numL),mQuats,mQuatMult,mMoveTable,quatF,quatB);

  void setUpStartingQuats(int[] quats)

    mCubits.setUpQuats(quats);

    }

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

  void rotateAllCubits(int axisIndex, int rowBitmap, int angle)

    {

    int quatIndex = makeQuaternionIndex(mAxis[axisIndex],angle);

    mCubits.rotateAllCubits(axisIndex,rowBitmap,quatIndex);

    }

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

  void makeMove(int moveIndex)

    {

    mCubits.makeMove(moveIndex);

    }

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

  void backMove(int moveIndex)

    {

    mCubits.backMove(moveIndex);

  int[] getCubitQuats()

    return mCubits.getRotQuats();

  int getBranchingFactor()

    return mBranchingFactor;

// moves clash iff they are both along the same axis and the same row

  boolean movesDontClash(int move1, int move2)

    if( move1>=0 && move2>=0 )

      {

      int[] m1 = mMoveTable[move1];

      int[] m2 = mMoveTable[move2];

      return ( m1[0]!=m2[0] || m1[1]!=m2[1] );

      }

    return true;

  private int[][] computeMoveTable()

    int[][] ret = new int[mBranchingFactor][];

    int numAxis = mAxis.length;

    int index = 0;

    for(int a=0; a<numAxis; a++)

      {

      int numL = mRotateable[a].length;

      for(int l=0; l<numL; l++)

        if( mRotateable[a][l] )

          {

          int basicAngle = mBasicAngles[a][l];

          int rowBitmap = (1<<l);

          for(int b=1; b<basicAngle; b++)

            {

            ret[index] = new int[] { a,rowBitmap,b };

            index++;

            }

          }

      }

    return ret;

  private int[] computeQuatForward()

    {

    int[] ret = new int[mBranchingFactor];

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

      {

      int[] move = mMoveTable[i];

      int axis   = move[0];

      int angle  = move[2];

      ret[i] = makeQuaternionIndex(mAxis[axis],angle);

      }

    return ret;

    }

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

  private int[] computeQuatBackward()

    {

    int[] ret = new int[mBranchingFactor];

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

      {

      int[] move = mMoveTable[i];

      int axis   = move[0];

      int angle  =-move[2];

      ret[i] = makeQuaternionIndex(mAxis[axis],angle);

      }

    return ret;

    }

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

  private int computeBranchingFactor()

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

// remember about the double cover of unit quaternions!

  private int mulQuat(int q1, int q2)

    {

    Static4D result = QuatHelper.quatMultiply( mQuats[q1], mQuats[q2] );

    float rX = result.get0();

    float rY = result.get1();

    float rZ = result.get2();

    float rW = result.get3();

    final float MAX_ERROR = 0.1f;

    float dX,dY,dZ,dW;

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

      {

      dX = mQuats[i].get0() - rX;

      dY = mQuats[i].get1() - rY;

      dZ = mQuats[i].get2() - rZ;

      dW = mQuats[i].get3() - rW;

      if( dX<MAX_ERROR && dX>-MAX_ERROR &&

          dY<MAX_ERROR && dY>-MAX_ERROR &&

          dZ<MAX_ERROR && dZ>-MAX_ERROR &&

          dW<MAX_ERROR && dW>-MAX_ERROR  ) return i;

      dX = mQuats[i].get0() + rX;

      dY = mQuats[i].get1() + rY;

      dZ = mQuats[i].get2() + rZ;

      dW = mQuats[i].get3() + rW;

      if( dX<MAX_ERROR && dX>-MAX_ERROR &&

          dY<MAX_ERROR && dY>-MAX_ERROR &&

          dZ<MAX_ERROR && dZ>-MAX_ERROR &&

          dW<MAX_ERROR && dW>-MAX_ERROR  ) return i;

      }

    return -1;

    }

  private final int[][] mQuatMult;

  private final int[] mRotQuats;

  private final int[][] mMoveTable;

  private final int[] mQuatForwardTable;

  private final int[] mQuatBackwardTable;

    int[] jumpIndices;      // size=mNumQuats. This cubit, when rotated with Nth quat, moves to

                            // position jumpIndices[N]. Its rotRowBitmaps are then in CubitData[jumpIndices[N]]

    int[] rotRowBitmaps;    // size=mNumAxis. Bitmaps of rows this cubit is at according to each rot ax.

    CubitData(int[] ji, int[] rb)

      jumpIndices   = ji;

      rotRowBitmaps = rb;

  SolvedObjectCubit( float[][] pos, Static3D[] axis, float[][] cuts, Static4D[] quats, int[][] quatMult,

                     int[][] moveTable, int[] quatForwardTable, int[] quatBackwardTable )

    mQuatMult  = quatMult;

    mRotQuats  = new int[mNumCubits];

    mMoveTable = moveTable;

    mQuatForwardTable = quatForwardTable;

    mQuatBackwardTable= quatBackwardTable;

  void rotateAllCubits(int axisIndex, int rowBitmap, int quatIndex)

    {

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

      {

      int q = mRotQuats[c];

      int ji = mData[c].jumpIndices[q];

      int bitmap = mData[ji].rotRowBitmaps[axisIndex];

      if( (bitmap&rowBitmap) != 0 ) mRotQuats[c] = mQuatMult[quatIndex][q];

      }

    }

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

  void makeMove(int moveIndex)

    int quatIndex = mQuatForwardTable[moveIndex];

    int[] move    = mMoveTable[moveIndex];

    int axisIndex = move[0];

    int rowBitmap = move[1];

    rotateAllCubits(axisIndex,rowBitmap,quatIndex);

  void backMove(int moveIndex)

    int quatIndex = mQuatBackwardTable[moveIndex];

    int[] move    = mMoveTable[moveIndex];

    int axisIndex = move[0];

    int rowBitmap = move[1];

    rotateAllCubits(axisIndex,rowBitmap,quatIndex);

    for(int c=0; c<mNumCubits; c++) mRotQuats[c] = quats[c];

  int[] getRotQuats()

    return mRotQuats;

  private int computeRow(Static3D axis, float[] cuts, float[] pos)

      mData[c] = new CubitData(jumpTable[c],rd.bitmaps);