package zemberek.core.collections;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.util.Arrays;

/**
 * A bit vector backed by a long array
 */
public class LongBitVector {

  // maximum size for the backing long array.
  public static final long MAX_ARRAY_SIZE = (Integer.MAX_VALUE - 1) * 64L;
  // for fast modulo 64 calculation of longs, n mod 64 = n and 0011 1111
  private static final long mod64Mask = 0x3FL;
  private static final long[] longSetMasks = new long[64];
  private static final long[] longResetMasks = new long[64];
  private static final int[] intSetMasks = new int[32];
  private static final long[] cutMasks = new long[64];

  static {
    for (int i = 0; i < 64; i++) {
      longSetMasks[i] = 0x1L << i;
      longResetMasks[i] = ~longSetMasks[i];
      if (i < 32) {
        intSetMasks[i] = 0x1 << i;
      }
      cutMasks[i] = ~(0xfffffffffffffffeL << i);
    }
  }

  private final int capacityInterval;
  private long[] words;
  private long size;

  /**
   * creates an empty bit vector.
   */
  public LongBitVector() {
    this(128);
  }

  /**
   * Creates an empty bit vector with initial bit capacity of initialCapcity.
   *
   * @param initialCapcity initial
   */
  public LongBitVector(long initialCapcity) {
    this(initialCapcity, 7);
  }

  /**
   * Creates a bit vector with the bit values from words with size of size.
   *
   * @param words long values carrying bits.
   * @param size vector size.
   */
  public LongBitVector(long[] words, long size) {
    if (size < 0 || size > words.length * 64) {
      throw new IllegalArgumentException("Cannot create vector with size:" + size);
    }
    this.size = size;
    this.words = words.clone();
    this.capacityInterval = 7;
  }

  /**
   * creates an empty bit vector with determined initial capacity and capacity interval.
   *
   * @param initialCapcity initial bit capacity.
   * @param capacityInterval amount of long values to add when capacity is not enough.
   */
  public LongBitVector(long initialCapcity, int capacityInterval) {
    if (capacityInterval < 0) {
      throw new IllegalArgumentException(
          "Cannot create vector with capacityInterval:" + capacityInterval);
    }
    this.capacityInterval = capacityInterval;
    ensureSize(initialCapcity);
    words = new long[(int) (initialCapcity >>> 6) + capacityInterval];
    this.size = 0;
  }

  /**
   * Used only for test purposes.
   *
   * @param bits bit string. It can contain space characters
   * @return bit vector equivalent.
   */
  static LongBitVector fromBinaryString(String bits) {
    bits = bits.replaceAll(" ", "");
    LongBitVector vector = new LongBitVector(bits.length());

    for (int i = 0; i < bits.length(); i++) {
      if (bits.charAt(i) == '1') {
        vector.addFast(true);
      } else {
        vector.addFast(false);
      }
    }
    return vector;
  }

  /**
   * Custom deserializer. It generates a LongBitVector from the stream. Method does not closes the
   * input Stream.
   *
   * @param dis input stream
   * @return a new LongbotVector loaded from the data input stream.
   */
  public static LongBitVector deserialize(DataInputStream dis) throws IOException {
    int length = dis.readInt();
    long size = dis.readLong();
    long[] words = new long[length];
    for (int i = 0; i < words.length; i++) {
      words[i] = dis.readLong();
    }
    return new LongBitVector(words, size);
  }

  /**
   * retrieves the index of the last bit in the vector with the value of bitValue.
   *
   * @param bitValue value of the bit to search.
   * @return the index of the last bit with the specified value. -1 if there is not such bit.
   */
  public long getLastBitIndex(boolean bitValue) {
    for (long i = size - 1; i >= 0; i--) {
      if (get(i) == bitValue) {
        return i;
      }
    }
    return -1;
  }

  /**
   * Fills all bits with the value.
   *
   * @param bitValue bit value to fill.
   */
  public void fill(boolean bitValue) {
    if (bitValue) {
      Arrays.fill(words, 0xffffffffffffffffL);
      int last = (int) (size / 64);
      words[last] &= cutMasks[(int) (size & mod64Mask)] >>> 1;
    } else {
      Arrays.fill(words, 0);
    }
  }

  // TODO: can be optimized for almost filled with 1 vectors.

  /**
   * retrieves the long array carrying the bit values.
   *
   * @return word array.
   */
  public long[] getLongArray() {
    return words.clone();
  }

  /**
   * creates a long array containing 0 bit indexes.
   *
   * @return zero bit indexes.
   */
  public long[] zeroIndexes() {
    long[] zeroIndexes = new long[(int) numberOfZeros()];

    int j = 0;
    for (long i = 0; i < size; i++) {
      if (!get(i)) {
        zeroIndexes[j++] = i;
      }
    }
    return zeroIndexes;
  }

  /**
   * creates a long array containing 0 bit indexes.
   *
   * @return zero bit indexes.
   */
  public int[] zeroIntIndexes() {
    int[] zeroIndexes = new int[(int) numberOfZeros()];

    int j = 0;
    for (int i = 0; i < size; i++) {
      if (!get(i)) {
        zeroIndexes[j++] = i;
      }
    }
    return zeroIndexes;
  }

  private void ensureSize(long _size) {
    if (_size < 0 || _size > MAX_ARRAY_SIZE) {
      throw new IllegalArgumentException("Cannot create vector with size:" + size);
    }
  }

  /**
   * vector size.
   *
   * @return size
   */
  public long size() {
    return size;
  }

  /**
   * appends a bit to the vector. it expads the vector capacity if there is no space left.
   *
   * @param b bit value
   */
  public void add(boolean b) {
    if (words.length << 6 == size + 1) {
      ensureCapacity(capacityInterval);
    }
    if (b) {
      set(size);
    }
    size++;
  }

  /**
   * appends a bit to the vector. it does not expad the vector capacity if there is no space left.
   * So user must be sure there is space left in the vector before calling this method.
   *
   * @param b bit value.
   */
  public void addFast(boolean b) {
    if (b) {
      set(size);
    }
    size++;
  }

  public long getLong(long start, int bitAmount) {
    final int startInd = (int) (start >>> 6);
    final int endInd = (int) ((start + bitAmount) >>> 6);
    final long startMod = start & mod64Mask;
    if (startInd == endInd) {
      return (words[startInd] >>> startMod) & cutMasks[bitAmount - 1];
    } else {
      long first = words[startInd] >>> startMod;
      long second = words[endInd] << (64 - startMod);
      return (first | second) & cutMasks[bitAmount - 1];
    }
  }

  public void add(int a, int bitLength) {
    if (bitLength < 0 || bitLength > 32) {
      throw new IllegalArgumentException(
          "Bit length cannot be negative or larger than 32:" + bitLength);
    }
    if (words.length << 6 < size + 1) {
      ensureCapacity(7);
    }
    for (int i = 0; i < bitLength; i++) {
      if ((a & intSetMasks[i]) != 0) {
        set(size);
      }
      size++;
    }
  }

  public void add(int amount, boolean bit) {
    if (amount < 0) {
      throw new IllegalArgumentException("Amount cannot be negative:" + amount);
    }
    if (words.length << 6 < size + 1 + amount >> 6) {
      ensureCapacity(capacityInterval + amount >> 6);
    }
    for (int i = 0; i < amount; i++) {
      if (bit) {
        set(size);
      }
      size++;
    }
  }

  public void add(long a, int bitLength) {
    if (bitLength < 0 || bitLength > 64) {
      throw new IllegalArgumentException(
          "Bit length cannot be negative or lareger than 64:" + bitLength);
    }
    if (words.length << 6 < size + 1) {
      ensureCapacity(capacityInterval);
    }
    for (int i = 0; i < bitLength; i++) {
      if ((a & longSetMasks[i]) != 0) {
        set(size);
      }
      size++;
    }
  }

  public long numberOfOnes() {
    long count = 0;
    for (long word : words) {
      count += Long.bitCount(word);
    }
    return count;
  }

  public long numberOfZeros() {
    return size - numberOfOnes();
  }

  private void ensureCapacity(int longsToExpand) {
    long[] newData = new long[words.length + longsToExpand];
    System.arraycopy(words, 0, newData, 0, words.length);
    words = newData;
  }

  /**
   * checks if there is enough free space for bitAmount of space in the vector. if not, it extends
   * capacity.
   *
   * @param bitAmount keyAmount of bits to check.
   */
  public void checkAndEnsureCapacity(int bitAmount) {
    if (words.length << 6 < size + bitAmount + 1) {
      ensureCapacity(capacityInterval);
    }
  }

  /**
   * returns the n.th bit value.This is an unsafe method. it does not check argument limits so it
   * can throw an ArrayIndexOutOfBound exception if n is equal or larger than size value or smaller
   * than zero.
   *
   * @param n bit index.
   * @return bit value.
   */
  public boolean get(long n) {
    return (words[(int) (n >>> 6)] & longSetMasks[(int) (n & mod64Mask)]) != 0L;
  }

  /**
   * eliminates the long values that do not carry actual bits.
   */
  void compress() {
    long[] newData = new long[(int) (size >> 6) + 1];
    System.arraycopy(words, 0, newData, 0, (int) (size >> 6) + 1);
    words = newData;
  }

  /**
   * sets the n.th bit. This is an unsafe method. it does not check argument limits so it can throw
   * an ArrayIndexOutOfBound exception if n is equal or larger than size value or smaller than
   * zero.
   *
   * @param n bit index
   */
  public void set(long n) {
    words[(int) (n >>> 6)] |= longSetMasks[(int) (n & mod64Mask)];
  }

  /**
   * sets the bit indexes from the an array .This is an unsafe method. it does not check argument
   * limits so it can throw an ArrayIndexOutOfBound exception if one of the value is equal or larger
   * than size value or smaller than zero.
   *
   * @param n bit index array
   */
  public void set(long[] n) {
    for (long l : n) {
      words[(int) (l >>> 6)] |= longSetMasks[(int) (l & mod64Mask)];
    }
  }

  /**
   * resets the n.th bit. This is an unsafe method. it does not check argument limits so it can
   * throw an ArrayIndexOutOfBound exception if n is equal or larger than size value or smaller than
   * zero.
   *
   * @param n bit index
   */
  public void clear(long n) {
    words[(int) (n >>> 6)] &= longResetMasks[(int) (n & mod64Mask)];
  }

  /**
   * resets the bit indexes from the an array .This is an unsafe method. it does not check argument
   * limits so it can throw an ArrayIndexOutOfBound exception if one of the value is equal or larger
   * than size value or smaller than zero.
   *
   * @param n bit index array
   */
  public void clear(long[] n) {
    for (long l : n) {
      words[(int) (l >>> 6)] &= longResetMasks[(int) (l & mod64Mask)];
    }
  }

  /**
   * Custom serializer. Method does not closes the output stream.
   *
   * @param dos data output stream to write.
   */
  public void serialize(DataOutputStream dos) throws IOException {
    dos.writeInt(words.length);
    dos.writeLong(size);
    for (long word : words) {
      dos.writeLong(word);
    }
  }
}
