package zemberek.core.collections;

import java.util.Arrays;

public class LongUIntMap {

  public static final int EMPTY_VALUE = -1;
  public static final int DELETED_VALUE = -2;
  static final int INITIAL_SIZE = 8;
  static final double DEFAULT_LOAD_FACTOR = 0.55;
  // Key array.
  long[] keys;
  // Carries unsigned int values.
  int[] values;
  int keyCount;
  int removeCount;
  // When structure has this amount of keys, it expands the key and count arrays.
  int threshold = (int) (INITIAL_SIZE * DEFAULT_LOAD_FACTOR);
  // This is the size-1 of the key and value array length. Array length is a value power of two
  private int modulo = INITIAL_SIZE - 1;

  public LongUIntMap() {
    this(INITIAL_SIZE);
  }

  public LongUIntMap(int size) {
    if (size < 1) {
      throw new IllegalArgumentException("Size must be a positive value. But it is " + size);
    }
    int k = 1;
    while (k < size) {
      k <<= 1;
    }
    keys = new long[k];
    values = new int[k];
    Arrays.fill(values, -1);
    threshold = (int) (k * DEFAULT_LOAD_FACTOR);
    modulo = k - 1;
  }

  private int hash(long key) {
    return Long.hashCode(key);
  }


  private int locate(long key) {
    int slot = hash(key) & modulo;
    int pointer = -1;
    while (true) {
      final int t = values[slot];
      if (t == EMPTY_VALUE) {
        return pointer < 0 ? (-slot - 1) : (-pointer - 1);
      }
      if (t == DELETED_VALUE) {
        if (pointer < 0) {
          pointer = slot;
        }
        slot = (slot + 1) & modulo;
        continue;
      }
      if (key == keys[slot]) {
        return slot;
      }
      slot = (slot + 1) & modulo;
    }
  }

  /**
   * If key does not exist, it adds it with count value 1. Otherwise, it increments the count value
   * by 1.
   *
   * @param key key
   * @return the new count value after addOrIncrement
   */
  public int increment(long key) {
    return incrementByAmount(key, 1);
  }

  /**
   * Returns the count of the key. If key does not exist, returns 0.
   *
   * @param key key
   * @return count of the key
   */
  public int get(long key) {
    int slot = hash(key) & modulo;

    while (true) {
      final int t = values[slot];
      if (t == EMPTY_VALUE) {
        return -1;
      }
      if (t == DELETED_VALUE) {
        slot = (slot + 1) & modulo;
        continue;
      }
      if (keys[slot] == key) {
        return values[slot];
      }
      slot = (slot + 1) & modulo;
    }
  }

  public int decrement(long key) {
    return incrementByAmount(key, -1);
  }

  public boolean containsKey(long key) {
    return locate(key) >= 0;
  }

  /**
   * addOrIncrement the value by "amount". If value does not exist, it a applies set() operation.
   *
   * @param key key
   * @param amount amount to addOrIncrement
   * @return incremented value
   */
  public int incrementByAmount(long key, int amount) {
    if (keyCount + removeCount == threshold) {
      expand();
    }
    int l = locate(key);
    if (l < 0) {
      l = -l - 1;
      values[l] = amount;
      keys[l] = key;
      keyCount++;
      return values[l];
    } else {
      values[l] += amount;
      if (values[l] < 0) {
        throw new IllegalStateException(
            "Negative Value calculated after incrementing with " + amount);
      }
      return values[l];
    }
  }

  public void remove(long key) {
    int k = locate(key);
    if (k < 0) {
      return;
    }
    values[k] = DELETED_VALUE; // mark deletion
    keyCount--;
    removeCount++;
  }

  private void expand() {
    LongUIntMap h = new LongUIntMap(values.length * 2);
    for (int i = 0; i < keys.length; i++) {
      if (values[i] != EMPTY_VALUE && values[i] != DELETED_VALUE) {
        h.put(keys[i], values[i]);
      }
    }
    assert (h.keyCount == keyCount);
    this.values = h.values;
    this.keys = h.keys;
    this.keyCount = h.keyCount;
    this.modulo = h.modulo;
    this.threshold = h.threshold;
    this.removeCount = 0;
  }

  public void put(long key, int value) {
    if (value < 0) {
      throw new IllegalArgumentException("Cannot put negative value = " + value);
    }
    if (keyCount + removeCount == threshold) {
      expand();
    }
    int loc = locate(key);
    if (loc >= 0) {
      values[loc] = value;
    } else {
      loc = -loc - 1;
      keys[loc] = key;
      values[loc] = value;
      keyCount++;
    }
  }

  /**
   * @return amount of keys
   */
  public int size() {
    return keyCount;
  }

  /**
   * @return a clone of value array.
   */
  public int[] copyOfValues() {
    return values.clone();
  }

  public long[] keyArray() {
    long[] keys = new long[size()];
    int j = 0;
    for (int i = 0; i < keys.length; i++) {
      if (values[i] != EMPTY_VALUE || values[i] != DELETED_VALUE) {
        keys[j++] = keys[i];
      }
    }
    return keys;
  }
}
