////////////////// class BitOutputStream //////////////////////////////

package bitio;

import java.io.ByteArrayInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.Objects;

/**
 * A BitOutputStream is a buffered stream designed to write an arbitrary
 * (up to limit of 32) number of bits. The bits are first written to an
 * internal bit buffer (an int) and then copied into an internal byte
 * buffer if the bit buffer is full. The bits in the byte buffer are
 * written to the underlying stream whenever the byte buffer reaches its
 * capacity, the BitOutputStream is closed, or is explicitly flushed.
 * Since BitOutputStream is already buffered, there is no need for
 * a BufferedOutputStream.
 *
 * It should be noticed that BitInputStream is not thread-safe. None of
 * the methods are synchronized.
 *
 * @author Ulf Uttersrud, Oslo Metropolitan University
 * @version 2.5  12.09.2017
 */

public class BitOutputStream extends OutputStream
{
  private static final int DEFAULT_BUFFER_SIZE = 4096;

  /**
   * The internal byte array where the bytes are temporarily stored.
   */
  private byte buf[];

  /**
   * The size of the internal byte array.
   */
  private int bufSize;

  /**
   * The current position in the byte buffer. That is the position in
   * the byte array buf where the next byte will be written. The value
   * is always in the range 0 through buf.length and elements buf[0]
   * through buf[pos-1] contain valid bytes. The byte array is full,
   * and hence has to be emptied, if pos >= buf.length.
   */
  private int pos;

  /**
   * An int used as an internal bit buffer.
   */
  private int bits;

  /**
   * The number of valid (the rightmost) bits in the bit buffer.
   */
  private int bitSize;

  /**
   * The underlying output stream.
   */
  private OutputStream out;

  /**
   * Creates a BitOutputStream with the specified size as the length of
   * the internal byte array and saves its other argument, the output
   * stream, for later use.
   *
   * @param out
   *          the underlying output stream.
   * @param size
   *          the length of the byte buffer.
   * @exception IllegalArgumentException
   *              if size <= 0.
   * @exception NullPointerException
   *              if the output stream is not defined.
   */
  public BitOutputStream(OutputStream out, int size)
  {
    if (out == null) throw
      new NullPointerException("The stream out is null");

    if (size <= 0) throw
      new IllegalArgumentException("The size(" + size + ") <= 0");

    buf = new byte[bufSize = size];
    this.out = out;
  }

  /**
   * Creates a BitOutputStream and saves its argument, the output stream,
   * for later use. A default value DEFAULT_BUFFER_SIZE is used as
   * a buffer length.
   *
   * @param out
   *          the underlying output stream.
   * @exception NullPointerException
   *              if the the output stream is not defined.
   */
  public BitOutputStream(OutputStream out)
  {
    this(out, DEFAULT_BUFFER_SIZE);
  }

  /**
   * Creates a BitOutputStream with the specified file name and with
   * size as the length of the internal byte array.
   *
   * @param fileName
   *          the name of the file.
   * @param size
   *          the length of the internal byte array.
   * @exception FileNotFoundException
   *              if the file does not exist.
   * @exception IllegalArgumentException
   *              if size <= 0.
   */
  public BitOutputStream(String fileName, int size)
      throws FileNotFoundException
  {
    this(new FileOutputStream(fileName), size);
  }

  /**
   * Creates a BitOutputStream with the specified file name. A default
   * value DEFAULT_BUFFER_SIZE is used as the length of the internal
   * byte array.
   *
   * @param fileName
   *          the name of the file.
   * @exception FileNotFoundException
   *              if the file does not exist.
   */
  public BitOutputStream(String fileName) throws FileNotFoundException
  {
    this(new FileOutputStream(fileName), DEFAULT_BUFFER_SIZE);
  }

  /**
   * A method that creates and returns a BitOutputStream with
   * the specified file name and a default value as a buffer length.
   *
   * @param fileName
   *          the name of the file.
   * @exception FileNotFoundException
   *          if the file can not be created.
   * @return
   *          the created BitOutputStream
   */
  public static BitOutputStream toFile(String fileName)
      throws FileNotFoundException
  {
    return new BitOutputStream(new FileOutputStream(fileName));
  }

  /**
   * A factory method that creates and returns a BitOutputStream with
   * the specified filename. If the second argument append is true, then
   * bits will be written to the end of the file rather than the beginning.
   * A default value is used as a buffer length.
   *
   * @param fileName
   *          the name of the file.
   * @param append
   *          if true, then bits will be written to the end of the file rather
   *          than the beginning.
   * @exception FileNotFoundException
   *              if the file cannot be created or opened.
   * @return
   *          the created BitOutputStream
   */
  public static BitOutputStream toFile(String fileName, boolean append)
      throws FileNotFoundException
  {
    return new BitOutputStream(new FileOutputStream(fileName, append));
  }

  /** Flushes the internal byte buffer */
  private void flushBuffer() throws IOException
  {
    if (out == null)
      throw new IOException("The stream is closed!");

    if (pos > 0)
    {
      out.write(buf, 0, pos);
      pos = 0;
    }
  } // end flushBuffer

  /**
   * Writes one bit (i.e. the rightmost bit of the argument bit) to
   * the output stream.
   *
   * @param bit
   *          containing the bit
   * @exception IOException
   *              if an I/O error occurs.
   */
  public void writeBit(int bit) throws IOException
  {
    bits <<= 1;         // a bit can now be added
    bits |= (bit & 1);  // the last bit of the parameter bit is added
    bitSize++;          // bitSize is updated

    if (bitSize >= 8)   // a byte can be moved to the byte buffer
    {
      bitSize = 0;

      // the byte buffer is flushed if it is full
      if (pos >= bufSize) flushBuffer();

      buf[pos++] = (byte) bits;  // a byte is moved
    }
  } // end writeBit

  /**
   * Writes a 0-bit to the output stream.
   *
   * @exception IOException
   *              if an I/O error occurs.
   */
  public void write0Bit() throws IOException
  {
    bits <<= 1;        // adds a 0-bit
    bitSize++;         // bitSize is updated

    if (bitSize >= 8)  // a byte can be moved to the byte buffer
    {
      bitSize = 0;

      // the byte buffer is flushed if it is full
      if (pos >= bufSize) flushBuffer();

      buf[pos++] = (byte) bits;  // a byte is moved
    }
  } // end write0Bit

  /**
   * Writes a 1-bit to the output stream.
   *
   * @exception IOException
   *              if an I/O error occurs.
   */
  public void write1Bit() throws IOException
  {
    bits <<= 1;   // a bit can now be added
    bits |= 1;    // adds a 1-bit
    bitSize++;    // bitSize is updated

    if (bitSize >= 8)  // a byte can be moved to the byte buffer
    {
      bitSize = 0;

      // the byte buffer is flushed if it is full
      if (pos >= bufSize) flushBuffer();

      buf[pos++] = (byte) bits;  // a byte is moved
    }
  } // end write1Bit

  /**
   * Writes 8 bits (a byte) (i.e. the rightmost 8 bits of the argument b) to the
   * output stream.
   *
   * @param b
   *          containing the byte
   * @exception IOException
   *              if an I/O error occurs.
   */
  @Override
  public void write(int b) throws IOException
  {
    bits <<= 8;          // 8 bits can now be added
    bits |= (b & 0xff);  // adds the 8 rightmost bits of b

    // the byte buffer is flushed if it is full
    if (pos >= bufSize) flushBuffer();

    buf[pos++] = (byte) (bits >> bitSize);  // a byte is moved

  } // end write

  /**
   * Writes the requested (rightmost) numberOfBits from the argument value to
   * the output stream. An IllegalArgumentException is thrown if the requested
   * number of bits is is not in the range [0,32]. No bits are written if
   * numberOfBits is equal to 0.
   *
   * @param value
   *          containing the bits
   * @param numberOfBits
   *          the (rightmost) number of bits from value to be written
   * @exception IOException
   *              if an I/O error occurs.
   * @exception IllegalArgumentException
   *              if numberOfBits is not in the range [0,32]
   */
  public void writeBits(int value, int numberOfBits) throws IOException
  {
    if (numberOfBits < 0)
      throw new IllegalArgumentException("Cannot write " + numberOfBits
          + " bits!");

    if (numberOfBits <= 25)   // the most common case
    {
      bits <<= numberOfBits;  // will not create overflow

      bits |= (value & ((1 << numberOfBits) - 1));  // the bits are added
      bitSize += numberOfBits;  // the bitsize is updated

      while (bitSize >= 8)
      {
        bitSize -= 8;

        // the byte buffer is flushed if it is full
        if (pos >= bufSize) flushBuffer();

        buf[pos++] = (byte) (bits >> bitSize);  // a byte is moved
      }
    }
    else if (numberOfBits <= 32)
    {
      int k = numberOfBits - 25;          // 1 <= k <= 7
      bits <<= 25;                        // 25 bits can now be added
      bits |= (value >> k) & 0x1ffffff;   // 25 bits are added
      bitSize += 25;                      // bitSize is updated

      // the bit buffer contains at least 25 bits,
      // 24 of them are moved to the byte buffer

      bitSize -= 8;
      if (pos >= bufSize) flushBuffer();
      buf[pos++] = (byte) (bits >> bitSize);

      bitSize -= 8;
      if (pos >= bufSize) flushBuffer();
      buf[pos++] = (byte) (bits >> bitSize);

      bitSize -= 8;
      if (pos >= bufSize) flushBuffer();
      buf[pos++] = (byte) (bits >> bitSize);

      bits <<= k;                         // k bits can now be added
      bits |= (value & ((1 << k) - 1));   // the rightmost k bits of value
      bitSize += k;                       // bitSize is updated

      if (bitSize >= 8)                   // 2 <= bitSize <= 15
      {
        bitSize -= 8;
        if (pos >= bufSize) flushBuffer();
        buf[pos++] = (byte) (bits >> bitSize);  // a byte is moved
      }
    }
    else
      throw new IllegalArgumentException("Cannot write " + numberOfBits
          + " bits!");

  } // end writeBits

  /**
   * Writes the significant binary digits (bits) of <code>value</code>
   * to the output stream. All 32 digits are written if <code>value</code>
   * is negative. If value is equal to 0, then a 0-digit is written. This
   * coincides with the "digits/bits" returned by the method
   * <code>Integer.toBinaryString(value)</code>.
   *
   * @param value
   *          containing the bits
   * @exception IOException
   *              if an I/O error occurs.
   */
  public void writeBits(int value) throws IOException
  {
    // must find the number of significant bits of value

    int signifcantBits = 31, v = value;

    if (v >>> 16 == 0) { signifcantBits -= 16; v <<= 16; }
    if (v >>> 24 == 0) { signifcantBits -=  8; v <<=  8; }
    if (v >>> 28 == 0) { signifcantBits -=  4; v <<=  4; }
    if (v >>> 30 == 0) { signifcantBits -=  2; v <<=  2; }

    signifcantBits += v >>> 31;

    bitSize += signifcantBits;

    if (bitSize <= 32)
    {
      bits <<= signifcantBits;  // will not create overflow
      bits |= value;            // the signifcantBits are added

      while (bitSize >= 8)
      {
        bitSize -= 8;
        if (pos >= bufSize) flushBuffer();
        buf[pos++] = (byte) (bits >> bitSize);
      }
    }
    else
    {
      int k = bitSize - 32;
      bits <<= signifcantBits - k;
      bits |= value >>> k;

      if (pos >= bufSize) flushBuffer();
      buf[pos++] = (byte) (bits >> 24);

      if (pos >= bufSize) flushBuffer();
      buf[pos++] = (byte) (bits >> 16);

      if (pos >= bufSize) flushBuffer();
      buf[pos++] = (byte) (bits >> 8);

      if (pos >= bufSize) flushBuffer();
      buf[pos++] = (byte) bits;

      bits = value;
      bitSize = k;
    }

  } // end writeBits

  /**
   * Writes the requested (leftmost) numberOfBits from the argument value to
   * the output stream. An IllegalArgumentException is thrown if the requested
   * number of bits is outside the range [0,32]. No bits are written if
   * numberOfBits is equal to 0.
   *
   * @param value
   *          containing the bits
   * @param numberOfBits
   *          the (leftmost) number of bits from value to be written
   * @exception IOException
   *              if an I/O error occurs.
   * @exception IllegalArgumentException
   *              if numberOfBits is outside the range [0,32]
   */
  public void writeLeftBits(int value, int numberOfBits) throws IOException
  {
    if (numberOfBits < 0)
      throw new IllegalArgumentException("Cannot write  a negative ("
        + numberOfBits + ") number of bits!");

    if (numberOfBits <= 25)   // the most common case
    {
      bits <<= numberOfBits;  // will not create overflow

      bits |= (value >>> (32 - numberOfBits));  // the bits are added
      bitSize += numberOfBits;  // the bitsize is updated

      while (bitSize >= 8)
      {
        bitSize -= 8;

        // the byte buffer is flushed if it is full
        if (pos >= bufSize) flushBuffer();

        buf[pos++] = (byte) (bits >> bitSize);  // a byte is moved
      }
    }
    else if (numberOfBits <= 32)
    {
      bits <<= 25;                        // 25 bits can now be added
      bits |= (value >>> 7);              // 25 bits are added
      bitSize += 25;                      // bitSize is updated

      // the bit buffer contains at least 25 bits,
      // 24 of them are moved to the byte buffer

      bitSize -= 8;
      if (pos >= bufSize) flushBuffer();
      buf[pos++] = (byte) (bits >> bitSize);

      bitSize -= 8;
      if (pos >= bufSize) flushBuffer();
      buf[pos++] = (byte) (bits >> bitSize);

      bitSize -= 8;
      if (pos >= bufSize) flushBuffer();
      buf[pos++] = (byte) (bits >> bitSize);

      int k = numberOfBits - 25;        // 1 <= k <= 7
      bits <<= k;                       // the missing k bits can now be added
      bits |= ((value >>> (32 - numberOfBits)) & ((1 << k) - 1));
      bitSize += k;                     // bitSize is updated

      if (bitSize >= 8)                 // 2 <= bitSize <= 15
      {
        bitSize -= 8;
        if (pos >= bufSize) flushBuffer();
        buf[pos++] = (byte) (bits >> bitSize);  // a byte is moved
      }
    }
    else
      throw new IllegalArgumentException("Cannot write " + numberOfBits
          + " bits!");

  } // end writeBits 

  /**
   * Writes the leftmost significant bits of the argument value (the bits
   * to the left of the trailing zeros) to the output stream. If value is
   * equal to 0, nothing is written.
   *
   * @param value
   *          containing the bits
   * @exception IOException
   *              if an I/O error occurs.
   */
  public void writeLeftBits(int value) throws IOException
  {
    writeLeftBits(value, 32 - Integer.numberOfTrailingZeros(value));

  } // end writeBits 

  /**
   * Flushes this buffered output stream. This forces any buffered output
   * bits to be written to the underlying output stream. If the number of
   * buffered output bits is not a multiple of 8, then a sufficient number
   * of 0-bits are added.
   *
   * @exception IOException
   *              if an I/O error occurs.
   */
  @Override
  public void flush() throws IOException
  {
    if (bitSize > 0)
    {
      // the byte buffer is written to the ouput stream if it is full
      if (pos >= bufSize) flushBuffer();

      // 0-bits are added to create a full byte
      buf[pos++] = (byte) (bits <<= (8 - bitSize));
      bitSize = 0;
    }

    flushBuffer();
    out.flush();

  } // end flush()

  /**
   * Returns the number of bits missing in order to fill the last byte.
   * If the method is called previous to a close (or a flush), the return
   * value tells how many 0-bits are shifted into the last byte.
   *
   * @throws IOException
   *              if an I/O error occurs.
   *
   * @return the number of bits missing in order to fill the last byte.
   */
  public int missingBits() throws IOException
  {
    if (out == null)
      throw new IOException("The stream is closed!");
    return bitSize == 0 ? 0 : 8 - bitSize;
  }

  /**
   * Closes the underlying output stream and releases any system resources
   * associated with the stream. The internal buffers are emptied (the method
   * flush() is called) before the underlying stream is closed. Any method call
   * subsequent to a close will result in an IOException with the message "The
   * stream is closed!".
   *
   * @exception IOException
   *              if an I/O error occurs.
   */
  @Override
  public void close() throws IOException
  {
    // a second call to close will have no effect
    if (out == null) return;
    flush();
    out.close();

    // The variables out and buf are set to null, pos and bufSize to -1
    // and bitSize to 8. This will prevent any method call subsequent to
    // a close. Such an effort will result in an IOException with
    // the message "The stream is closed!".
    out = null;
    buf = null;
    pos = bufSize = -1;
    bitSize = 8;

  } // end close()

  /**
   * Converts a byte array b to a string of '0'- and '1'-characters.
   * The boolean parameter space decides if there will be a space
   * between to bytes or not.
   *
   * An example: the byte array {-1, 15} has "11111111 00001111" as
   * a result. The purpose of the method is give the programmer an
   * opportunity to observe the behavior of the write methods
   * by for instance using a ByteArrayOutputStream as the
   * underlying stream.
   *
   * @param b the byte array
   * @param space decides space or not between groups
   * @return the byte array turned into a string of
   *         characters ('0' or '1')
   */
  public static String toBitStringWithSpace(byte... b)
  {
    StringBuilder builder = new StringBuilder();

    String[] fourBits =
    {"0000","0001","0010","0011","0100","0101","0110","0111",
     "1000","1001","1010","1011","1100","1101","1110","1111"};

    if (b.length > 0)
    {
      builder.append(fourBits[(b[0] & 255) >> 4]);
      builder.append(fourBits[b[0] & 15]);
    }

    for (int i = 1; i < b.length; i++)
    {
      builder.append(' ');
      builder.append(fourBits[(b[i] & 255) >> 4]);
      builder.append(fourBits[b[i] & 15]);
    }

    return builder.toString();
  }

  /**
   * Converts a byte array b to a string of '0'- and  '1'-characters.
   * An example: the byte array {-1, 15} will be converted
   * to the string "1111111100001111". The purpose of this method
   * is give the programmer an opportunity to observe the behavior of
   * the write methods by for instance using a ByteArrayOutputStream
   * as the underlying stream.
   *
   * @param b the byte array
   * @return the byte array turned into a string of
   *         characters ('0' or '1')
   */
  public static String toBitString(byte... b)
  {
    StringBuilder builder = new StringBuilder();

    String[] fourBits =
    {"0000","0001","0010","0011","0100","0101","0110","0111",
     "1000","1001","1010","1011","1100","1101","1110","1111"};

    if (b.length > 0)
    {
      builder.append(fourBits[(b[0] & 255) >> 4]);
      builder.append(fourBits[b[0] & 15]);
    }

    for (int i = 1; i < b.length; i++)
    {
      builder.append(fourBits[(b[i] & 255) >> 4]);
      builder.append(fourBits[b[i] & 15]);
    }

    return builder.toString();
  }

  /**
   * Converts a byte array b to a partitioned string of '0'- 
   * and '1'-characters. Each element of the array partition
   * must be in the interval [1,31].
   * 
   * An example: (byte)-1 = 11111111 and (byte)15 = 00001111.
   * Let the byte array b be given by {(byte)-1,(byte)15} and
   * the partition array part by {4,4,4,4}. Then
   * toBitString(b, part) will return the partitioned string
   * "1111 1111 0000 1111". If instead part = {1,2,3,4,5,6},
   * then we get the string  "1 11 111 1100 00111 1" (ending
   * with only one bit since there are 16 bits all together).
   * 
   * The method can, by using a ByteArrayOutputStream as the
   * underlying stream, "visualize" the behavior of the write
   * methods. Example:
   *   ByteArrayOutputStream buf = new ByteArrayOutputStream();
   *   BitOutputStream out = new BitOutputStream(buf);
   *   out.writeBits(5,3);     // 101
   *   out.writeBits(0,2);     // 00
   *   out.writeBits(6,3);     // 110
   *   out.close();
   *   int[] part = {3,2,3};
   *   String s = 
   *     BitOutputStream.toBitString(buf.toByteArray(),part);
   *   System.out.println(s);  // 101 00 110
   *
   * @param b the byte array
   * @param part the partition array
   * @return the byte array turned into a  partitioned
   *         string of characters ('0' or '1') 
   * @throws java.lang.NullPointerException if b is null
   * @throws java.lang.NullPointerException if part is null
   */
  public static String toBitString(byte[] b, int[] part)
  {
    Objects.requireNonNull(b, "Argument b is null!");
    Objects.requireNonNull(part, "Argument part is null!");

    StringBuilder build = new StringBuilder();
    try (BitInputStream in = new BitInputStream(new ByteArrayInputStream(b)))
    {
      for (int i = 0; i < part.length; i++)
      {
        int numberOfBits = part[i];
        int bits = in.readBits(numberOfBits);
        if (bits == -1)  // fewer than numberOfBits left in the stream
        {
          numberOfBits = in.availableBits();
          if (numberOfBits == 0) break;
          bits = in.readBits(numberOfBits);  // the rest of the bits          
        }

        for (int filter = 1 << (numberOfBits - 1); filter > 0; filter >>= 1)
        {
          build.append((filter & bits) != 0 ? '1' : '0');
        }

        if (numberOfBits > 0) build.append(' ');
      }

      in.close();
    }
    catch (IOException io) {}

    // removes an unnecessary space at the end
    if (build.length() > 0) build.deleteCharAt(build.length() - 1);

    return build.toString();
  }

  /**
   * Converts a byte array b to a partitioned string of '0'- 
   * and '1'-characters. The parameter numberOfBits gives
   * the size of each part. The value must be from 1 to 31.
   * 
   * An example: (byte)-1 = 11111111 and (byte)15 = 00001111.
   * Let the byte array b be given by b = {(byte)-1,(byte)15} 
   * and numberOfBits = 5. Then toBitString(b, numberOfBits)
   * will return the partitioned string "11111 11100 00111 1"
   * (ending with only one bit since there are 16 = 3*5 + 1 bits).

   * The purpose of the method is give the programmer a mean to
   * study the behavior of the write methods by for instance using
   * a ByteArrayOutputStream as the underlying stream.
   *
   * @param b the byte array
   * @param numberOfBits the length of each group
   * @return the byte array turned into a partitioned string of
   *         characters ('0' or '1')
   * @throws java.lang.NullPointerException if b is null
   * @throws java.lang.IllegalArgumentException
   *         if numberOfBits is outside [1,31]
   */
  public static String toBitString(byte[] b, int numberOfBits)
  {
    if (numberOfBits < 1 || numberOfBits > 31)
      throw new IllegalArgumentException("NumberOfBits is illegal!");

    Objects.requireNonNull(b, "Argument b is null!");

    int n = 8 * b.length, q = n / numberOfBits;

    int[] part = q * numberOfBits == n ? new int[q] : new int[q + 1];

    Arrays.fill(part, numberOfBits);

    return toBitString(b, part);
  }

} // End of class BitOutputStream