TwistyPuzzleLib

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

// Copyright 2022 Leszek Koltunski                                                               //

//                                                                                               //

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

//                                                                                               //

// Magic Cube is proprietary software licensed under an EULA which you should have received      //

// along with the code. If not, check https://distorted.org/magic/License-Magic-Cube.html        //

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

package org.distorted.objectlib.helpers;

import java.util.ArrayList;

import static org.distorted.objectlib.main.TwistyObject.SQ2;

import static org.distorted.objectlib.main.TwistyObject.SQ3;

import static org.distorted.objectlib.main.TwistyObject.SQ6;

import static org.distorted.objectlib.scrambling.ScrambleStateLocallyBandaged.MAX_SUPPORTED_SIZE;

import org.distorted.library.helpers.QuatHelper;

import org.distorted.objectlib.bandaged.FactoryBandagedPyraminx;

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

public class ObjectSignature implements Comparable<ObjectSignature>

{

  public static final int SIZE = computeNum();

  private static final float[][] mRotAxisPyraminx =

        {

                {     0, -SQ3/3, -SQ6/3},

                {     0, -SQ3/3,  SQ6/3},

                { SQ6/3,  SQ3/3,      0},

                {-SQ6/3,  SQ3/3,      0},

        };

  private static final float[][] mQuatsPyraminx =

        {

                {     0, -0.5f, -SQ2/2, 0.5f },

                {     0, -0.5f,  SQ2/2, 0.5f },

                { SQ2/2,  0.5f,      0, 0.5f },

                {-SQ2/2,  0.5f,      0, 0.5f },

        };

  private long[] mSignature;

  private int[] mLayer;

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

  private float[][] mCubitTouch;

  private int[][] mTouchRows;

  private int mNumCubitTouches;

  private int[] mNumLeftCyclesPerLayer;

  private int[] mNumCentCyclesPerLayer;

  private int[] mNumInneCyclesPerLayer;

  private String mName=null;

  private float[] mTmp;

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

// a cube of size N has 12*(N-1)^2 possible places two adjacent cubies can be 'glued'; therefore

// the signature must contain ceil( 12*(N-1)^2 / 64 ) bytes.

// a pyraminx of size N has 4 + 6*(N-1)(N-2) places two adjacent cubies can be 'glued' so much less.

  private static int computeNum()

    {

    int max = MAX_SUPPORTED_SIZE-1;

    return (int)(0.95f + (3*max*max)/16.0f);

    }

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

  private void setUpSignature(long[] signature)

    {

    int size = signature.length;

    int diff = SIZE-size;

    if( diff==0 ) mSignature = signature;

    else

      {

      mSignature = new long[SIZE];

      for(int i=0; i<size; i++) mSignature[diff+i] = signature[i];

      }

    }

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

  public ObjectSignature(ObjectSignature sig)

    {

    int len = sig.mSignature.length;

    mSignature = new long[len];

    for(int i=0; i<len; i++) mSignature[i] = sig.mSignature[i];

    mLayer      = sig.mLayer;

    mCycles     = sig.mCycles;

    mCubitTouch = sig.mCubitTouch;

    mTouchRows  = sig.mTouchRows;

    mName       = sig.mName;

    mTmp        = sig.mTmp;

    mNumCubitTouches       = sig.mNumCubitTouches;

    mNumCentCyclesPerLayer = sig.mNumCentCyclesPerLayer;

    mNumLeftCyclesPerLayer = sig.mNumLeftCyclesPerLayer;

    mNumInneCyclesPerLayer = sig.mNumInneCyclesPerLayer;

    }

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

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

  public ObjectSignature(long signature)

    {

    mSignature = new long[SIZE];

    mSignature[SIZE-1] = signature;

    }

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

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

// or locally created bandaged pyraminxes.

// How to tell apart: pyraminx's shortName starts with a 'P'.

  public ObjectSignature(String shortName, long[] signature)

    {

    setUpSignature(signature);

    if( shortName.charAt(0) != 'P' )

      {

      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();

      prepareTouchRows();

      prepareAllCycles();

      }

    else

      {

      mTmp = new float[4];

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

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

      prepareCubitTouchPyraminx();

      prepareTouchRowsPyraminx();

      prepareAllCyclesPyraminx();

      }

    }

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

// BAN*** objects when read from JSON

  public ObjectSignature(int size, long[] signature)

    {

    setUpSignature(signature);

    mLayer = new int[] {size,size,size};

    prepareCubitTouch();

    prepareTouchRows();

    prepareAllCycles();

    }

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

// other objects created from JSON (version2)

  public ObjectSignature(long[] signature)

    {

    setUpSignature(signature);

    }

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

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

// 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};

    mSignature = new long[SIZE];

    prepareCubitTouch();

    prepareTouchRows();

    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);

            }

          }

        }

      }

    }

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

// Locally created bandaged pyraminxes 1<=N<=7

  public ObjectSignature(int len, float[][] position)

    {

    mTmp = new float[4];

    mLayer = new int[] {len,len,len,len};

    mSignature = new long[SIZE];

    prepareCubitTouchPyraminx();

    prepareTouchRowsPyraminx();

    prepareAllCyclesPyraminx();

    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( areNeighboursPyraminx(xi-xj,yi-yj,zi-zj) )

            {

            boolean octa = FactoryBandagedPyraminx.isOctahedron(len,yi);

            float xc,yc,zc;

            if( octa )

              {

              xc = (xi+2*xj)/3;

              yc = (yi+2*yj)/3;

              zc = (zi+2*zj)/3;

              }

            else

              {

              xc = (2*xi+xj)/3;

              yc = (2*yi+yj)/3;

              zc = (2*zi+zj)/3;

              }

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

            setBit(bitIndex,1);

            }

          }

        }

      }

    }

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

  public void setSignature(int signature)

    {

    for(int i=0; i<SIZE-1; i++) mSignature[i]=0;

    mSignature[SIZE-1] = signature;

    }

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

  public int compareTo(ObjectSignature sig)

    {

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

      {

      long diff = mSignature[i] - sig.mSignature[i];

           if( diff>0 ) return +1;

      else if( diff<0 ) return -1;

      }

    return 0;

    }

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

  public boolean isEqual(ObjectSignature sig)

    {

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

      {

      if( mSignature[i] != sig.mSignature[i] ) return false;

      }

    return true;

    }

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

  public long[] getArray()

    {

    return mSignature;

    }

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

  public String getString()

    {

    if( mName==null )

      {

      StringBuilder sb = new StringBuilder();

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

        {

        String sig = String.format("0x%016X", mSignature[i]);

        if( i>0 ) sb.append('_');

        sb.append(sig);

        }

      mName = sb.toString();

      }

    return mName;

    }

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

  public boolean isUnblockedFromLeft(int axis, int layer)

    {

    if(layer>0)

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

        if( getBit(index)!=0 && mTouchRows[index][axis]==layer ) return false;

    return true;

    }

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

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

    {

    ObjectSignature ret = new ObjectSignature(this);

    // I don't understand it, but Firebase shows mCycles is occasionally null here.

    if( mCycles!=null && mCycles[axis]!=null )

      {

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

      // it can happen that there are no cycles in this layer: 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 if( cycles[0].length==3 ) for(int[] cyc : cycles) ret.cycle3(turn,cyc);

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

        }

      }

    return ret;

    }

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

  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 cycle3(int turn, int[] cyc)

    {

    int index0 = cyc[0];

    int index1 = cyc[1];

    int index2 = cyc[2];

    long b0 = getBit(index0);

    long b1 = getBit(index1);

    long b2 = getBit(index2);

    switch(turn)

      {

      case 1: setBit(index0,b2);

              setBit(index1,b0);

              setBit(index2,b1);

              break;

      case 2: setBit(index0,b1);

              setBit(index1,b2);

              setBit(index2,b0);

              break;

      }

    }

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

  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 prepareTouchRows()

    {

    mTouchRows = new int[mNumCubitTouches][3];

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

      {

      float[] touch = mCubitTouch[i];

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

        {

        int l = (int)(2*touch[a] + mLayer[a] + 0.01f);

        mTouchRows[i][a] = ( (l%2)==0 ) ? l/2 : -1;

        }

      }

    }

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

  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 = rotateIndex4(axis,i);

      if( i0<=i ) continue;

      int i1 = rotateIndex4(axis,i0);

      if( i1<=i ) continue;

      int i2 = rotateIndex4(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 + 0.01f);

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

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

      if( cycle.length==4 )

        {

        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};

        }

      else

        {

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

        }

      index[layer]++;

      }

    return ret;

    }

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

  private int rotateIndex4(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 void prepareCubitTouchPyraminx()

    {

    float[][][] centers = FactoryBandagedPyraminx.createPositions(mLayer[0]);

    float[][] octs = centers[0];

    float[][] tets = centers[1];

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

    for(float[] oct : octs)

      for(float[] tet : tets)

        {

        float ox=oct[0];

        float oy=oct[1];

        float oz=oct[2];

        float tx=tet[0];

        float ty=tet[1];

        float tz=tet[2];

        if( areNeighboursPyraminx(ox-tx, oy-ty, oz-tz) )

          {

          float xc=(2*tx+ox)/3;

          float yc=(2*ty+oy)/3;

          float zc=(2*tz+oz)/3;

          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);

    }

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

  private void prepareTouchRowsPyraminx()

    {

    mTouchRows = new int[mNumCubitTouches][4];

    int num = mLayer[0];

    final int N = 10;

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

      {

      float[] touch = mCubitTouch[i];

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

        {

        float[] ax = mRotAxisPyraminx[a];

        float l = whichLayerPyraminx(touch,ax,num);

        int ll = (int)(N*l);

        mTouchRows[i][a] = ( (ll%N)==0 ) ? ll/N : -1;

        }

      }

    }

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

  private void prepareAllCyclesPyraminx()

    {

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

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

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

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

    generate3CyclesPyraminx(cycles0,0);

    generate3CyclesPyraminx(cycles1,1);

    generate3CyclesPyraminx(cycles2,2);

    generate3CyclesPyraminx(cycles3,3);

    mCycles = new int[4][][][];

    int numLayers = mLayer[0];

    mCycles[0] = fillUpCyclesPyraminx(cycles0,0,numLayers);

    mCycles[1] = fillUpCyclesPyraminx(cycles1,1,numLayers);

    mCycles[2] = fillUpCyclesPyraminx(cycles2,2,numLayers);

    mCycles[3] = fillUpCyclesPyraminx(cycles3,3,numLayers);

    }

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

  private void generate3CyclesPyraminx(ArrayList<float[][]> cycles, int ax)

    {

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

      {

      int i0 = rotateIndex3(ax,i);

      if( i0<=i ) continue;

      int i1 = rotateIndex3(ax,i0);