TwistyPuzzleLib

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

// Copyright 2023 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.tablebases;

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

class PruningTable

{

  static final int[] SUPPORTED = {4,8,12,16,20,24};

  private static final int HEADER_SIZE = 6;

  private byte[] mData;

  private int mNumBits;

  private int mBucketBytes;

  private int mNumBuckets;

  private int mLevel;

  private int[] mBucketOffsets;

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

  private static String printByte(byte b)

    {

    return String.format("%8s", Integer.toBinaryString(b & 0xFF)).replace(' ', '0');

    }

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

  private int numBytesForIndices(int total)

    {

    int bytes = 0;

    while(total!=0)

      {

      total>>=8;

      bytes++;

      }

    return bytes;

    }

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

  private void writeHeader()

    {

    mData[0] = (byte)mLevel;

    mData[1] = (byte)mBucketBytes;

    mData[2] = (byte)mNumBits;

    mData[3] = (byte)(mNumBuckets>>>16);

    mData[4] = (byte)(mNumBuckets>>> 8);

    mData[5] = (byte)(mNumBuckets&0xff);

    }

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

  private int getBucketOffset(int bucket)

    {

    if( mBucketOffsets[bucket]==0 )

      {

      if( bucket>=mNumBuckets ) mBucketOffsets[bucket] = mData.length;

      else

        {

        int ret = 0;

        int start = HEADER_SIZE + bucket*mBucketBytes;

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

          {

          ret<<=8;

          ret += ( ((int)(mData[start+i]))&0xff);

          }

        mBucketOffsets[bucket] = HEADER_SIZE+mNumBuckets*mBucketBytes+ret;

        }

      }

    return mBucketOffsets[bucket];

    }

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

  private void writeBucketPointers(int[] bucket)

    {

    int start=HEADER_SIZE;

    for( int b : bucket )

      {

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

        {

        mData[start+mBucketBytes-1-i] = (byte)(b%256);

        b>>=8;

        }

      start += mBucketBytes;

      }

    }

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

  private int retrieveData(int index, int entryInBucket)

    {

    int bits = entryInBucket*mNumBits;

    int bytes = index + bits/8;

    switch(mNumBits)

      {

      case  4: return (bits%8)!=0 ? (mData[bytes]&0xf) : ((mData[bytes]>>>4)&0xf);

      case  8: return (mData[bytes]&0xff);

      case 12: return (bits%8)!=0 ? (((mData[bytes]&0xf)<<8) + (mData[bytes+1]&0xff)) : (((mData[bytes]&0xff)<<4) + ((mData[bytes+1]>>>4)&0xf));

      case 16: return ((mData[bytes]&0xff)<<8) + (mData[bytes+1]&0xff);

      case 20: if( (bits%8) !=0 ) return (((mData[bytes]&0x0f)<<16) + ((mData[bytes+1]&0xff)<<8) + ( mData[bytes+2]     &0xff));

               else               return (((mData[bytes]&0xff)<<12) + ((mData[bytes+1]&0xff)<<4) + ((mData[bytes+2]>>>4)&0x0f));

      case 24: return ((mData[bytes]&0xff)<<16) + ((mData[bytes+1]&0xff)<<8) + (mData[bytes+2]&0xff);

      }

    return 0;

    }

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

  private void insertData(int index, int entryInBucket, int value)

    {

    int bits = entryInBucket*mNumBits;

    int bytes = index + bits/8;

    switch(mNumBits)

      {

      case  4: if( (bits%8) !=0 ) mData[bytes] = (byte)((mData[bytes]&(~0xf)) + value  );

               else               mData[bytes] = (byte)((value<<4) + (mData[bytes]&0xf));

               break;

      case  8: mData[bytes] = (byte)value;

               break;

      case 12: if( (bits%8) !=0 )

                 {

                 mData[bytes]  = (byte)((mData[bytes]&(~0xf)) + (value>>>8));

                 mData[bytes+1]= (byte)value;

                 }

               else

                 {

                 mData[bytes]  = (byte)(value>>>4);

                 mData[bytes+1]= (byte)((byte)(value<<4) + (mData[bytes+1]&0xf));

                 }

               break;

      case 16: mData[bytes]   = (byte)(value>>>8);

               mData[bytes+1] = (byte)(value&(0xff));

               break;

      case 20: if( (bits%8) !=0 )

                 {

                 mData[bytes]  = (byte)((mData[bytes]&(~0xf)) + (value>>>16));

                 mData[bytes+1]= (byte)(value>>>8);

                 mData[bytes+2]= (byte)(value&(0xff));

                 }

               else

                 {

                 mData[bytes]  = (byte)(value>>>12);

                 mData[bytes+1]= (byte)(value>>>4);

                 mData[bytes+2]= (byte)((byte)(value<<4) + (mData[bytes+2]&0xf));

                 }

               break;

      case 24: mData[bytes]   = (byte)(value>>>16);

               mData[bytes+1] = (byte)(value>>>8);

               mData[bytes+2] = (byte)(value&(0xff));

               break;

      }

    }

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

  private void writeBuckets(Tablebase table)

    {

    int mask = (1<<mNumBits);

    int prevBucket = -1;

    int entryInBucket = 0;

    int index = 0;

    int size = table.getSize();

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

      if( table.retrieveUnpacked(i)==mLevel )

        {

        int toBeWritten = (i%mask);

        int currBucket = (i>>mNumBits);

        if( currBucket!=prevBucket )

          {

          index = getBucketOffset(currBucket);

          entryInBucket = 0;

          }

        else

          {

          entryInBucket ++;

          }

        prevBucket = currBucket;

        insertData(index,entryInBucket,toBeWritten);

        }

    }

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

  private int retNumPositions(Tablebase table, int level)

    {

    int size=0, tableSize = table.getSize();

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

      if( table.retrieveUnpacked(i)==level ) size++;

    return size;

    }

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

  private int computeApproximateSize(int tableSize, int positionSize, int numBits)

    {

    int entrySize = (1<<numBits);

    int numBuckets = (tableSize+entrySize-1)/entrySize;

    int overhang = (numBits==4 || numBits==12) ? numBuckets/4 : 0;

    int totalBytesForTable = (positionSize*numBits)/8 + overhang;

    int bucketBytes = numBytesForIndices(totalBytesForTable);

    int totalBytesForBuckets = numBuckets*bucketBytes;

    return HEADER_SIZE + totalBytesForBuckets + totalBytesForTable;

    }

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

  private void construct(Tablebase table, int level, int numBits)

    {

    mNumBits = numBits;

    mLevel = level;

    int size = table.getSize();

    int entrySize = (1<<numBits);

    mNumBuckets = (size+entrySize-1)/entrySize;

    int[] bucket = new int[mNumBuckets];

    mBucketOffsets = new int[mNumBuckets+1];

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

      if( table.retrieveUnpacked(i)==level )

        {

        int currBucket = i/entrySize;

        bucket[currBucket]++;

        }

    int totalBytesForTable = 0;

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

      {

      int numBytes = (bucket[i]*numBits+7)/8;

      bucket[i] = totalBytesForTable;

      totalBytesForTable+=numBytes;

      }

    mBucketBytes = numBytesForIndices(totalBytesForTable);

    int totalBytesForBuckets = mNumBuckets*mBucketBytes;

    int totalSize = HEADER_SIZE + totalBytesForBuckets + totalBytesForTable;

    mData = new byte[totalSize];

    android.util.Log.e("D", "Constructing a pruningTable, numBits="+numBits+" size "+totalSize);

    writeHeader();

    writeBucketPointers(bucket);

    writeBuckets(table);

    }

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

// PUBLIC API

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

// only numBits = 4,8,12,16,20,24 actually supported

  PruningTable(Tablebase table, int level, int numBits)

    {

    construct(table,level,numBits);

    }

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

  PruningTable(Tablebase table, int level)

    {

    int minimum = 0, chosen =  0;

    int size = retNumPositions(table,level);

    int tableSize = table.getSize();

    android.util.Log.e("D", "----- PRUNING TABLE LEVEL "+level+" ------");

    for(int i=0; i<SUPPORTED.length; i++)

      {

      int approx = computeApproximateSize( tableSize, size, SUPPORTED[i]);

      if( i==0 || approx<minimum )

        {

        minimum = approx;

        chosen  = i;

        }

      android.util.Log.e("D", "trying numBits: "+SUPPORTED[i]+" approx size: "+approx);

      }

    construct(table,level,SUPPORTED[chosen]);

    }

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

  PruningTable(byte[] data)

    {

    mData = data;

    mLevel       =  ((int)mData[0])&0xff;

    mBucketBytes =  ((int)mData[1])&0xff;

    mNumBits     =  ((int)mData[2])&0xff;

    mNumBuckets  =((((int)mData[3])&0xff)<<16) + ((((int)mData[4])&0xff)<<8) + (((int)mData[5])&0xff);

    mBucketOffsets = new int[mNumBuckets+1];

    }

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

  byte[] getPacked()

    {

    return mData;

    }

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

  int getLevel()

    {

    return mLevel;

    }

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

  boolean contains(int number)

    {

    int bucket = (number>>mNumBits);

    int offset1 = getBucketOffset(bucket);

    int offset2 = getBucketOffset(bucket+1);

    int numBytesInBucket = offset2-offset1;

    int numEntriesInBucket = (8*numBytesInBucket)/mNumBits;

    if( mNumBits==4 && numBytesInBucket>0 )

      {

      byte val = mData[offset2-1];

      if( (val/16)*16 == val ) numEntriesInBucket--;

      }

    int lower = 0;

    int upper = numEntriesInBucket-1;

    int rem = (bucket<<mNumBits);

    while( upper>=lower )

      {

      int mid = (lower+upper)/2;

      int value = retrieveData(offset1,mid) + rem;

      if( value==number ) return true;

      if( value>number ) upper = mid-1;

      else               lower = mid+1;

      }

    return false;

    }

}