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

{

  private static final int HEADER_SIZE = 5;

  private byte[] mData;

  private int mNumBits;

  private int mBucketBytes;

  private int mNumBuckets;

  private int mLevel;

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

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

    mData[4] = (byte)(mNumBuckets%256);

    }

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

  private int getBucketOffset(int bucket)

    {

    if( bucket>=mNumBuckets ) return mData.length;

    int ret = 0;

    int start = HEADER_SIZE + bucket*mBucketBytes;

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

      {

      ret<<=8;

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

      }

    return HEADER_SIZE+mNumBuckets*mBucketBytes+ret;

    }

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

  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;

    int ret=0;

    switch(mNumBits)

      {

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

               break;

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

               break;

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

               break;

      case 16: ret = (mData[bytes]&0xff)*256 + (mData[bytes+1]&0xff);

               break;

      }

    return ret;

    }

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

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

      }

    }

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

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

    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 actually supported

  PruningTable(Tablebase table, int level, int numBits)

    {

    construct(table,level,numBits);

    }

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

  PruningTable(Tablebase table, int level)

    {

    int[] supported = {4,8,12,16};

    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)*256 + ((int)mData[4])&0xff;

    }

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

  byte[] getPacked()

    {

    return mData;

    }

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

  int getLevel()

    {

    return mLevel;

    }

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

  boolean belongs(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;

    while( upper>=lower )

      {

      int mid = (lower+upper)/2;

      int value = retrieveData(offset1,mid);

      value += (bucket<<mNumBits);

      if( value==number ) return true;

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

      else               lower = mid+1;

      }

    return false;

    }

}