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 org.distorted.objectlib.main.ObjectType;

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

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

public class ObjectSignature implements Comparable<ObjectSignature>

{

  public static final int SIZE = computeNum();

  private long[] mSignature;

  private int[] mLayer;

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

  private float[][] mCubitTouch;

  private int mNumCubitTouches;

  private int[] mNumLeftCyclesPerLayer;

  private int[] mNumCentCyclesPerLayer;

  private int[] mNumInneCyclesPerLayer;

  private String mName=null;

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

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

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

        }

      }

    }

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

// built-in objects

  public ObjectSignature(ObjectType type)

    {

    mSignature = new long[SIZE];

    mSignature[SIZE-1] = type.ordinal();

    }

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

  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;

    mName       = sig.mName;

    mNumCubitTouches       = sig.mNumCubitTouches;

    mNumCentCyclesPerLayer = sig.mNumCentCyclesPerLayer;

    mNumLeftCyclesPerLayer = sig.mNumLeftCyclesPerLayer;

    mNumInneCyclesPerLayer = sig.mNumInneCyclesPerLayer;

    }

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

// built-in bandaged 3x3s; 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)

  public ObjectSignature(String shortName, long[] signature)

    {

    setUpSignature(signature);

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

    }

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

// BAN*** objects when read from JSON

  public ObjectSignature(int size, long[] signature)

    {

    setUpSignature(signature);

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

    prepareCubitTouch();

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

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

          {

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

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

    {

    int sigIndex = SIZE-1-(index/64);

    return (mSignature[sigIndex]>>(index%64))&0x1;

    }

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

  private void setBit(int index, long bit)

    {

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

    int sigIndex = SIZE-1-(index/64);

    if( bit!=0 ) mSignature[sigIndex] |= diff;

    else         mSignature[sigIndex] &=~diff;

    }

}