/*
    * License : The MIT License
    * Copyright(c) 2020 Olyutorskii
    */
   
   package io.github.olyutorskii.aletojio;
   
   /**
    * Bit pool.
   *
   * <p>Pushing any size of bits to bit-queue tail.
   *
   * <p>Chopping any size of bits from bit-queue head.
   *
   * <p>From MSB to LSB.
   */
  public class BitPool {
  
      /**
       * Default bit size.
       */
      public static final int DEFAULT_BITS = 512;
  
      private static final long MASK_LONGINT = (1L << Integer.SIZE) - 1L;
  
      private static final int BOOLEAN_SIZE = 1;
      private static final int ELEM_SIZE = Integer.SIZE;
  
      private static final int RSFT_DIV_E;
      private static final int MASK_MOD_E;
  
      static {
          assert Integer.bitCount(ELEM_SIZE) == 1;
  
          RSFT_DIV_E = Integer.numberOfTrailingZeros(ELEM_SIZE);
          MASK_MOD_E = (1 << RSFT_DIV_E) - 1;
  
          int testVal = ELEM_SIZE * 3 + (0x5555_5555 & MASK_MOD_E);
          assert  testVal >> RSFT_DIV_E  == testVal / ELEM_SIZE;
          assert (testVal &  MASK_MOD_E) == testVal % ELEM_SIZE;
      }
  
      // pushing and chopping bits from MSB to LSB.
      // pushing and chopping bits from lower to higher array index if not overlapping.
      private final int[] buf;
  
      private final int bufCapa;
  
      private int bufSize;
      private int headRawBitPos;
      private int tailRawBitPos;
  
  
      /**
       * Constructor.
       *
       * <p>bit size is 512.
       */
      public BitPool() {
          this(DEFAULT_BITS);
          return;
      }
  
      /**
       * Constructor.
       *
       * @param bitLength bit length
       * @throws IllegalArgumentException length is not positive value
       */
      public BitPool(int bitLength) throws IllegalArgumentException {
          super();
  
          if (bitLength <= 0) throw new IllegalArgumentException();
  
          this.bufCapa = bitLength;
  
          int bufLen = (this.bufCapa - 1) / ELEM_SIZE + 1;
          this.buf = new int[bufLen];
  
          this.bufSize = 0;
          this.headRawBitPos = 0;
          this.tailRawBitPos = 0;
  
          return;
      }
  
  
      /**
       * Return contiguous bitmask pattern from LSB.
       *
       * <p>Result is 0b111 if 3.
       *
       * <p>Result is -1 if 32 or larger.
       *
       * @param lowerBits mask length
       * @return bitmask
       */
      static int getMaskInt(int lowerBits) {
          if (lowerBits >= Integer.SIZE) return -1;
         int result = (1 << lowerBits) - 1;
         return result;
     }
 
     /**
      * Return contiguous bitmask pattern from LSB.
      *
      * <p>Result is 0b111L if 3.
      *
      * <p>Result is -1L if 64 or larger.
      *
      * @param lowerBits mask length
      * @return bitmask
      */
     static long getMaskLong(int lowerBits) {
         if (lowerBits >= Long.SIZE) return -1L;
         long result = (1L << lowerBits) - 1L;
         return result;
     }
 
 
     /**
      * Resturn bit size.
      *
      * @return bit size
      */
     public int size() {
         return this.bufSize;
     }
 
     /**
      * Return max available size.
      *
      * @return capacity size
      */
     public int capacity() {
         return this.bufCapa;
     }
 
     /**
      * Return true if empty.
      *
      * @return true if empty
      */
     public boolean isEmpty() {
         boolean result = this.bufSize <= 0;
         return result;
     }
 
     /**
      * Return remaining spaces.
      *
      * @return remaining spaces.
      */
     public int remaining() {
         int result = this.bufCapa - this.bufSize;
         return result;
     }
 
     /**
      * Return true if has remaining spaces.
      *
      * @return true if has remaining spaces
      */
     public boolean hasRemaining() {
         boolean result = this.bufCapa > this.bufSize;
         return result;
     }
 
     /**
      * clear bit pool.
      */
     public void clear() {
         this.headRawBitPos = 0;
         this.tailRawBitPos = 0;
         this.bufSize = 0;
         return;
     }
 
     /**
      * check push bits argument.
      *
      * @param bits push bits
      * @param max bits max
      * @throws IndexOutOfBoundsException no more space or bits is not positive or over max size
      */
     private void checkPushSize(int bits, int max) throws IndexOutOfBoundsException {
         if (bits <= 0 || remaining() < bits || max < bits) {
             throw new IndexOutOfBoundsException();
         }
         return;
     }
 
     /**
      * check chop bits argument.
      *
      * @param bits chop bits
      * @param max bits max
      * @throws IndexOutOfBoundsException not enough bits or bits is not positive or over max size
      */
     private void checkChopSize(int bits, int max) throws IndexOutOfBoundsException {
         if (bits <= 0 || this.bufSize < bits || max < bits) {
             throw new IndexOutOfBoundsException();
         }
         return;
     }
 
     /**
      * Push boolean value to tail of queue.
      *
      * @param bool boolean value
      * @throws IndexOutOfBoundsException no more space
      */
     public void pushBoolean(boolean bool) throws IndexOutOfBoundsException {
         checkPushSize(BOOLEAN_SIZE, BOOLEAN_SIZE);
 
         int bufIndex = this.tailRawBitPos >> RSFT_DIV_E; // / ELEM_SIZE;
         int bposInInt = this.tailRawBitPos & MASK_MOD_E; // % ELEM_SIZE;
         int lsft = ELEM_SIZE - 1 - bposInInt;
 
         int mask = 1 << lsft;
 
         int elem = this.buf[bufIndex];
         if (bool) {
             elem |=   mask;
         } else {
             elem &=  ~mask;
         }
         this.buf[bufIndex] = elem;
 
         this.bufSize++;
         this.tailRawBitPos++;
         if (this.tailRawBitPos >= this.bufCapa) {
             this.tailRawBitPos -= this.bufCapa;
         }
 
         return;
     }
 
     /**
      * Chop boolean value from head of queue.
      *
      * @return boolean value
      * @throws IndexOutOfBoundsException not enough bits
      */
     public boolean chopBoolean() throws IndexOutOfBoundsException {
         checkChopSize(BOOLEAN_SIZE, BOOLEAN_SIZE);
 
         int bufIndex = this.headRawBitPos >> RSFT_DIV_E; // / ELEM_SIZE;
         int bposInInt = this.headRawBitPos & MASK_MOD_E; // % ELEM_SIZE;
         int lsft = ELEM_SIZE - 1 - bposInInt;
 
         int mask = 1 << lsft;
         int elem = this.buf[bufIndex];
         boolean result = (elem & mask) != 0;
 
         this.bufSize--;
         this.headRawBitPos++;
         if (this.headRawBitPos >= this.bufCapa) {
             this.headRawBitPos -= this.bufCapa;
         }
 
         return result;
     }
 
     /**
      * Push int value to tail of queue.
      *
      * @param iArg int value
      * @throws IndexOutOfBoundsException no more space
      */
     public void pushInt(int iArg) throws IndexOutOfBoundsException {
         pushInt(iArg, Integer.SIZE);
         return;
     }
 
     /**
      * Push lower bits of int value to tail of queue.
      *
      * @param iArg int value
      * @param bitCt bits from LSB
      * @throws IndexOutOfBoundsException bits is not positive or no more space or over 32
      */
     public void pushInt(int iArg, int bitCt) throws IndexOutOfBoundsException {
         checkPushSize(bitCt, Integer.SIZE);
 
         int bits1st = this.bufCapa - this.tailRawBitPos;
 
         if (bitCt <= bits1st) {
             pushIntImpl(iArg, bitCt);
         } else {
             // Overlapping end of array
             int bits2nd = bitCt - bits1st;
             int highArg = iArg >> bits2nd;
             pushIntImpl(highArg, bits1st);
             pushIntImpl(iArg,    bits2nd);
         }
 
         return;
     }
 
     /**
      * Push lower bits of int value to tail of queue.
      *
      * <p>No bits bound argument checking.
      *
      * <p>Pushing over last of array elements is not supported.
      *
      * @param iArg int value
      * @param bitCt bits from LSB
      */
     private void pushIntImpl(int iArg, int bitCt) {
         int bposInLastElem = this.tailRawBitPos & MASK_MOD_E; // % ELEM_SIZE;
         int restInLastElem  = ELEM_SIZE - bposInLastElem;
 
         if (restInLastElem < bitCt) {
             // Overlapping array elements
             int bits2nd = bitCt - restInLastElem;
             int highArg = iArg >> bits2nd;
             pushIntImpl(highArg, restInLastElem);
             pushIntImpl(iArg,    bits2nd);
             return;
         }
 
         int bufIndex = this.tailRawBitPos >> RSFT_DIV_E; // / ELEM_SIZE;
 
         int gap = restInLastElem - bitCt;
         int mask = getMaskInt(bitCt) << gap;
         int bits = (iArg << gap) & mask;
 
         int elem = this.buf[bufIndex];
         elem &= ~mask;
         elem |=  bits;
         this.buf[bufIndex] = elem;
 
         this.bufSize += bitCt;
         this.tailRawBitPos += bitCt;
         if (this.tailRawBitPos >= this.bufCapa) {
             this.tailRawBitPos -= this.bufCapa;
         }
 
         return;
     }
 
     /**
      * Chop int value from head of queue.
      *
      * @return int value
      * @throws IndexOutOfBoundsException not enough bits
      */
     public int chopInt() throws IndexOutOfBoundsException {
         return chopInt(Integer.SIZE);
     }
 
     /**
      * Chop bits and store to lower bits of int value from head of queue.
      *
      * @param bitCt bits
      * @return lower bits filled int value
      * @throws IndexOutOfBoundsException not enough bits or bits is not positive or over 32
      */
     public int chopInt(int bitCt) throws IndexOutOfBoundsException {
         checkChopSize(bitCt, Integer.SIZE);
 
         int result;
 
         if (this.headRawBitPos + bitCt <= this.bufCapa) {
             result = chopIntImpl(bitCt);
         } else {
             // Overlapping end of array
             int bits1st = this.bufCapa - this.headRawBitPos;
             int bits2nd = bitCt - bits1st;
             int highVal = chopIntImpl(bits1st);
             int lowVal  = chopIntImpl(bits2nd);
             result  = (highVal << bits2nd) | lowVal;
         }
 
         return result;
     }
 
     /**
      * Chop bits and store to lower bits of int value from head of queue.
      *
      * <p>No bits bound argument checking.
      *
      * <p>Chopping over last of array elements is not supported.
      *
      * @param bitCt bits
      * @return lower bits filled int value
      */
     private int chopIntImpl(int bitCt) {
         int bposInLastElem = this.headRawBitPos & MASK_MOD_E; // % ELEM_SIZE;
         int restInLastElem = ELEM_SIZE - bposInLastElem;
 
         if (restInLastElem < bitCt) {
             // Overlapping array elements
             int bits2nd = bitCt - restInLastElem;
             int highVal = chopIntImpl(restInLastElem);
             int lowVal  = chopIntImpl(bits2nd);
             int result = (highVal << bits2nd) | lowVal;
             return result;
         }
 
         int bufIndex = this.headRawBitPos >> RSFT_DIV_E; // / ELEM_SIZE;
 
         int elem = this.buf[bufIndex];
         int gap = restInLastElem - bitCt;
         int result = (elem >> gap) & getMaskInt(bitCt);
 
         this.bufSize -= bitCt;
         this.headRawBitPos += bitCt;
         if (this.headRawBitPos >= this.bufCapa) {
             this.headRawBitPos -= this.bufCapa;
         }
 
         return result;
     }
 
     /**
      * Push long value to tail of queue.
      *
      * @param lArg long value
      * @throws IndexOutOfBoundsException no more space
      */
     public void pushLong(long lArg) throws IndexOutOfBoundsException {
         pushLong(lArg, Long.SIZE);
         return;
     }
 
     /**
      * Push lower bits of long value to tail of queue.
      *
      * @param lArg long value
      * @param bitCt bits from LSB
      * @throws IndexOutOfBoundsException bits is not positive or no more space or over 64
      */
     public void pushLong(long lArg, int bitCt) throws IndexOutOfBoundsException {
         checkPushSize(bitCt, Long.SIZE);
 
         if (bitCt <= Integer.SIZE) {
             pushInt((int) lArg, bitCt);
             return;
         }
 
         int bits1st = bitCt - Integer.SIZE;
         int bits2nd = Integer.SIZE;
 
         int highArg = (int) (lArg >> Integer.SIZE);
         int lowArg  = (int) lArg;
 
         pushInt(highArg, bits1st);
         pushInt(lowArg,  bits2nd);
 
         return;
     }
 
     /**
      * Chop long value from head of queue.
      *
      * @return long value
      * @throws IndexOutOfBoundsException not enough bits
      */
     public long chopLong() throws IndexOutOfBoundsException {
         return chopLong(Long.SIZE);
     }
 
     /**
      * Chop bits and store to lower bits of long value from head of queue.
      *
      * @param bitCt bits
      * @return lower bits filled long value
      * @throws IndexOutOfBoundsException not enough bits or bits is not positive or over 64
      */
     public long chopLong(int bitCt) throws IndexOutOfBoundsException {
         checkChopSize(bitCt, Long.SIZE);
 
         if (bitCt <= Integer.SIZE) {
             long result = (long) chopInt(bitCt);
             result &= getMaskLong(bitCt);
             return result;
         }
 
         int bits1st = bitCt - Integer.SIZE;
 
         long highVal = (long) chopInt(bits1st);
         long lowVal  = (long) chopInt(Integer.SIZE);
 
         highVal &= getMaskLong(bits1st);
         lowVal  &= MASK_LONGINT;
 
         long result = (highVal << Integer.SIZE) | lowVal;
 
         return result;
     }
 
     /**
      * Push byte value to tail of queue.
      *
      * @param bArg byte value
      * @throws IndexOutOfBoundsException no more space
      */
     public void pushByte(byte bArg) throws IndexOutOfBoundsException {
         pushInt(bArg, Byte.SIZE);
         return;
     }
 
     /**
      * Chop byte value from head of queue.
      *
      * @return byte value
      * @throws IndexOutOfBoundsException not enough bits
      */
     public byte chopByte() throws IndexOutOfBoundsException {
         byte result = (byte) chopInt(Byte.SIZE);
         return result;
     }
 
 }