TwistyPuzzleLib

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

// Copyright 2022 Leszek Koltunski                                                               //

//                                                                                               //

// This file is part of Magic Cube.                                                              //

//                                                                                               //

// Magic Cube 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.                                                           //

//                                                                                               //

// Magic Cube 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.                                                  //

//                                                                                               //

// You should have received a copy of the GNU General Public License                             //

// along with Magic Cube.  If not, see <http://www.gnu.org/licenses/>.                           //

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

package org.distorted.objectlib.helpers;

import org.distorted.objectlib.main.ObjectType;

import java.util.ArrayList;

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

public class ObjectSignature

{

  private long mSignature1, mSignature2, mSignature3;

  private int[] mLayer;

  private int[][][][] mCycles;

  private float[][] mCubitTouch;

  private int mNumCubitTouches;

  private int[] mNumLeftCyclesPerLayer;

  private int[] mNumCentCyclesPerLayer;

  private int[] mNumInneCyclesPerLayer;

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

// built-in objects

  public ObjectSignature(ObjectType type)

    {

    mSignature1 = 0;

    mSignature2 = 0;

    mSignature3 = type.ordinal();

    }

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

  public ObjectSignature(ObjectSignature sig)

    {

    mSignature1 = sig.mSignature1;

    mSignature2 = sig.mSignature2;

    mSignature3 = sig.mSignature3;

    mLayer      = sig.mLayer;

    mCycles     = sig.mCycles;

    mCubitTouch = sig.mCubitTouch;

    mNumCubitTouches       = sig.mNumCubitTouches;

    mNumCentCyclesPerLayer = sig.mNumCentCyclesPerLayer;

    mNumLeftCyclesPerLayer = sig.mNumLeftCyclesPerLayer;

    }

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

// built-in bandaged 3x3s; objects created from JSON (version1)

  public ObjectSignature(long signature)

    {

    mSignature1 = 0;

    mSignature2 = 0;

    mSignature3 = signature;

    }

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

// locally created bandaged cuboids created from JSON (version2)

  public ObjectSignature(String shortName, long signature1, long signature2, long signature3)

    {

    mSignature1 = signature1;

    mSignature2 = signature2;

    mSignature3 = signature3;

    int x = shortName.charAt(0) - '0';

    int y = shortName.charAt(1) - '0';

    int z = shortName.charAt(2) - '0';

    mLayer = new int[] {x,y,z};

    prepareCubitTouch();

    prepareAllCycles();

    }

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

// other objects created from JSON (version2)

  public ObjectSignature(long signature1, long signature2, long signature3)

    {

    mSignature1 = signature1;

    mSignature2 = signature2;

    mSignature3 = signature3;

    }

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

// Locally created bandaged cuboids 1<=N,M,K<=5

// This is the 'Andreas signature' of a bandaged cube.

// https://twistypuzzles.com/forum/viewtopic.php?p=415466#p415466

  public ObjectSignature(int lenx, int leny, int lenz, float[][] position)

    {

    mLayer = new int[] {lenx,leny,lenz};

    prepareCubitTouch();

    prepareAllCycles();

    for(float[] pos : position)

      {

      int numCenters = pos.length/3;

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

        {

        float xi = pos[3*i  ];

        float yi = pos[3*i+1];

        float zi = pos[3*i+2];

        for(int j=i+1; j<numCenters; j++)

          {

          float xj = pos[3*j  ];

          float yj = pos[3*j+1];

          float zj = pos[3*j+2];

          if(areNeighbours(xi-xj,yi-yj,zi-zj))

            {

            float xc = (xi+xj)/2;

            float yc = (yi+yj)/2;

            float zc = (zi+zj)/2;

            int bitIndex = getIndexOfCubitTouch(xc,yc,zc);

            setBit(bitIndex,1);

            }

          }

        }

      }

    }

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

  public void setSignature(ObjectSignature sig)

    {

    mSignature1 = sig.mSignature1;

    mSignature2 = sig.mSignature2;

    mSignature3 = sig.mSignature3;

    }

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

  public void setSignature(int sig)

    {

    mSignature1 = 0;

    mSignature2 = 0;

    mSignature3 = sig;

    }

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

  public boolean isEqual(ObjectSignature sig)

    {

    return mSignature1==sig.mSignature1 && mSignature2==sig.mSignature2 && mSignature3==sig.mSignature3;

    }

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

  public long getLong1()

    {

    return mSignature1;

    }

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

  public long getLong2()

    {

    return mSignature2;

    }

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

  public long getLong3()

    {

    return mSignature3;

    }

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

  public String getString()

    {

    String sig1 = String.format("0x%016X", mSignature1);

    String sig2 = String.format("0x%016X", mSignature2);

    String sig3 = String.format("0x%016X", mSignature3);

    return sig1+"_"+sig2+"_"+sig3;

    }

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

  public boolean isUnblockedFromLeft(int axis, int layer)

    {

    if(layer>0)

      for(int index=0; index<mNumCubitTouches; index++)

        if( getBit(index)!=0 )

          {

          float[] touch = getCubitTouchOfIndex(index);

          if( belongsLeft(touch,axis,layer) ) return false;

          }

    return true;

    }

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

  public ObjectSignature turn(int axis, int layer, int turn)

    {

    ObjectSignature ret = new ObjectSignature(this);

    int[][] cycles = mCycles[axis][layer];

    // it can happen that there are no cycles: 2x1x2 axis 0 layer 0.

    if( cycles!=null && cycles.length>0 && cycles[0]!=null )

      {

      if( cycles[0].length==4 ) for(int[] cyc : cycles) ret.cycle4(turn,cyc);

      else                      for(int[] cyc : cycles) ret.cycle2(cyc);

      }

    return ret;

    }

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

  private boolean belongsLeft(float[] point, int axis, int layer)

    {

    return 2*point[axis]+mLayer[axis] == 2*layer;

    }

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

  private void cycle2(int[] cyc)

    {

    int index0 = cyc[0];

    int index1 = cyc[1];

    long b0 = getBit(index0);

    long b1 = getBit(index1);

    setBit(index1,b0);

    setBit(index0,b1);

    }

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

  private void cycle4(int turn, int[] cyc)

    {

    int index0 = cyc[0];

    int index1 = cyc[1];

    int index2 = cyc[2];

    int index3 = cyc[3];

    long b0 = getBit(index0);

    long b1 = getBit(index1);

    long b2 = getBit(index2);

    long b3 = getBit(index3);

    switch(turn)

      {

      case 1: setBit(index0,b3);

              setBit(index1,b0);

              setBit(index2,b1);

              setBit(index3,b2);

              break;

      case 2: setBit(index0,b2);

              setBit(index1,b3);

              setBit(index2,b0);

              setBit(index3,b1);

              break;

      case 3: setBit(index0,b1);

              setBit(index1,b2);

              setBit(index2,b3);

              setBit(index3,b0);

              break;

      }

    }

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

  private void prepareCubitTouch()

    {

    int numCenters = mLayer[0]*mLayer[1]*mLayer[2];

    if( mLayer[0]>1 && mLayer[1]>1 && mLayer[2]>1 ) numCenters -= (mLayer[0]-2)*(mLayer[1]-2)*(mLayer[2]-2);

    float[][] centers = new float[numCenters][];

    int index = 0;

    for(int i=0; i<mLayer[0]; i++)

      for(int j=0; j<mLayer[1]; j++)

        for(int k=0; k<mLayer[2]; k++)

          if( (i==0) || (i==mLayer[0]-1) || (j==0) || (j==mLayer[1]-1) || (k==0) || (k==mLayer[2]-1) )

            {

            centers[index++] = new float[] { i+0.5f*(1-mLayer[0]), j+0.5f*(1-mLayer[1]), k+0.5f*(1-mLayer[2]) };

            }

    ArrayList<float[]> mTouch = new ArrayList<>();

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

      for(int j=i+1; j<numCenters; j++)

        {

        float[] c0 = centers[i];

        float[] c1 = centers[j];

        float x1 = c0[0];

        float y1 = c0[1];

        float z1 = c0[2];

        float x2 = c1[0];

        float y2 = c1[1];

        float z2 = c1[2];

        if( areNeighbours(x1-x2,y1-y2,z1-z2) )

          {

          float xc = (x1+x2)/2;

          float yc = (y1+y2)/2;

          float zc = (z1+z2)/2;

          float[] touch = new float[] {xc,yc,zc};

          mTouch.add(touch);

          }

        }

    mNumCubitTouches = mTouch.size();

    mCubitTouch = new float[mNumCubitTouches][];

    for(int i=0; i<mNumCubitTouches; i++) mCubitTouch[i] = mTouch.remove(0);

    // now sort the touches so that the order agrees with 'Andreas signature' as defined here:

    // https://twistypuzzles.com/forum/viewtopic.php?p=415466#p415466

    // i.e. we need to sort by Y first (increasing) then by Z (decreasing) then by X (decreasing)

    // i.e. we need to sort by 100Y-10Z-X (increasing)

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

      {

      float[] ci = mCubitTouch[i];

      float val_i = 100*ci[1]-10*ci[2]-ci[0];

      for(int j=i+1; j<mNumCubitTouches; j++)

        {

        float[] cj = mCubitTouch[j];

        float val_j = 100*cj[1]-10*cj[2]-cj[0];

        if( val_j<val_i )

          {

          mCubitTouch[i] = cj;

          mCubitTouch[j] = ci;

          val_i = val_j;

          ci = cj;

          }

        }

      }

    }

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

  private void prepareAllCycles()

    {

    ArrayList<float[][]> cycles0 = new ArrayList<>();

    ArrayList<float[][]> cycles1 = new ArrayList<>();

    ArrayList<float[][]> cycles2 = new ArrayList<>();

    mNumLeftCyclesPerLayer = new int[3];

    mNumCentCyclesPerLayer = new int[3];

    mNumInneCyclesPerLayer = new int[3];

    if( mLayer[1]==mLayer[2] ) generate4Cycles(cycles0,0);

    else                       generate2Cycles(cycles0,0);

    if( mLayer[0]==mLayer[2] ) generate4Cycles(cycles1,1);

    else                       generate2Cycles(cycles1,1);

    if( mLayer[0]==mLayer[1] ) generate4Cycles(cycles2,2);

    else                       generate2Cycles(cycles2,2);

    mCycles = new int[3][][][];

    mCycles[0] = fillUpCycles(cycles0,0,mLayer[0]);

    mCycles[1] = fillUpCycles(cycles1,1,mLayer[1]);

    mCycles[2] = fillUpCycles(cycles2,2,mLayer[2]);

    }

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

  private void generate4Cycles(ArrayList<float[][]> cycles, int axis)

    {

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

      {

      int i0 = rotateIndex(axis,i);

      if( i0<=i ) continue;

      int i1 = rotateIndex(axis,i0);

      if( i1<=i ) continue;

      int i2 = rotateIndex(axis,i1);

      if( i2<=i ) continue;

      float[] f0 = getCubitTouchOfIndex(i);

      float[] f1 = getCubitTouchOfIndex(i0);

      float[] f2 = getCubitTouchOfIndex(i1);

      float[] f3 = getCubitTouchOfIndex(i2);

      int l = (int)(2*f0[axis]+mLayer[axis]);

      if( l==2 ) mNumLeftCyclesPerLayer[axis]++;

      if( l==1 ) mNumCentCyclesPerLayer[axis]++;

      if( mLayer[axis]>2 && l==3 ) mNumInneCyclesPerLayer[axis]++;

      float[][] cycle = new float[][] { f0,f1,f2,f3 };

      cycles.add(cycle);

      }

    }

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

  private void generate2Cycles(ArrayList<float[][]> cycles, int axis)

    {

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

      {

      int i0 = rotateIndex2(axis,i);

      if( i0<=i ) continue;

      float[] f0 = getCubitTouchOfIndex(i);

      float[] f1 = getCubitTouchOfIndex(i0);

      int l = (int)(2*f0[axis]+mLayer[axis]);

      if( l==2 ) mNumLeftCyclesPerLayer[axis]++;

      if( l==1 ) mNumCentCyclesPerLayer[axis]++;

      if( mLayer[axis]>2 && l==3 ) mNumInneCyclesPerLayer[axis]++;

      float[][] cycle = new float[][] { f0,f1 };

      cycles.add(cycle);

      }

    }

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

  private int[][][] fillUpCycles(ArrayList<float[][]> cyc, int axis, int numLayers)

    {

    int numCycles = cyc.size();

    int[] index = new int[numLayers];

    int numFirst = mNumCentCyclesPerLayer[axis];

    int numNext  = mNumLeftCyclesPerLayer[axis] + mNumInneCyclesPerLayer[axis];

    int numLast  = mNumLeftCyclesPerLayer[axis] + numFirst;

    int[][][] ret = new int[numLayers][][];

    ret[          0] = new int[numFirst][];

    ret[numLayers-1] = new int[numLast][];

    for(int i=1; i<numLayers-1; i++) ret[i] = new int[numNext][];

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

      {

      float[][] cycle = cyc.remove(0);

      int layer = (int)(cycle[0][axis]+numLayers*0.5f);

      if( cycle.length==4 )

        {

        int i0 = getIndexOfCubitTouch(cycle[0][0],cycle[0][1],cycle[0][2]);

        int i1 = getIndexOfCubitTouch(cycle[1][0],cycle[1][1],cycle[1][2]);

        int i2 = getIndexOfCubitTouch(cycle[2][0],cycle[2][1],cycle[2][2]);

        int i3 = getIndexOfCubitTouch(cycle[3][0],cycle[3][1],cycle[3][2]);

        ret[layer][index[layer]] = new int[] {i0,i1,i2,i3};

        index[layer]++;

        }

      else

        {

        int i0 = getIndexOfCubitTouch(cycle[0][0],cycle[0][1],cycle[0][2]);

        int i1 = getIndexOfCubitTouch(cycle[1][0],cycle[1][1],cycle[1][2]);

        ret[layer][index[layer]] = new int[] {i0,i1};

        index[layer]++;

        }

      }

    return ret;

    }

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

  private int rotateIndex(int axis, int index)

    {

    float[] touch = getCubitTouchOfIndex(index);

    switch(axis)

      {

      case 0: return getIndexOfCubitTouch(+touch[0],+touch[2],-touch[1]);

      case 1: return getIndexOfCubitTouch(-touch[2],+touch[1],+touch[0]);

      case 2: return getIndexOfCubitTouch(+touch[1],-touch[0],+touch[2]);

      }

    return -1;

    }

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

  private int rotateIndex2(int axis, int index)

    {

    float[] touch = getCubitTouchOfIndex(index);

    switch(axis)

      {

      case 0: return getIndexOfCubitTouch(+touch[0],-touch[1],-touch[2]);

      case 1: return getIndexOfCubitTouch(-touch[0],+touch[1],-touch[2]);

      case 2: return getIndexOfCubitTouch(-touch[0],-touch[1],+touch[2]);

      }

    return -1;

    }

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

  private int getIndexOfCubitTouch(float x, float y, float z)

    {

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

      {

      float[] touch = mCubitTouch[i];

      if( touch[0]==x && touch[1]==y && touch[2]==z ) return i;

      }

    return -1;

    }

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

  private float[] getCubitTouchOfIndex(int index)

    {

    return mCubitTouch[index];

    }

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

  private boolean areNeighbours(float dx, float dy, float dz)

    {

    return dx*dx+dy*dy+dz*dz<1.1f;

    }

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

  private long getBit(int index)

    {

    switch(index/64)

      {

      case 0: return (mSignature3>>(index%64))&0x1;

      case 1: return (mSignature2>>(index%64))&0x1;

      case 2: return (mSignature1>>(index%64))&0x1;

      default: android.util.Log.e("D", "error in getBit, index="+index);

      }

    return 0L;

    }

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

  private void setBit(int index, long bit)

    {

    long diff = (1L<<(index%64));

    switch(index/64)

      {

      case 0: if( bit!=0 ) mSignature3 |= diff;

              else         mSignature3 &=~diff;

              break;

      case 1: if( bit!=0 ) mSignature2 |= diff;

              else         mSignature2 &=~diff;

              break;

      case 2: if( bit!=0 ) mSignature1 |= diff;

              else         mSignature1 &=~diff;

              break;

      default: android.util.Log.e("D", "error in setBit, index="+index);

      }

    }

}