/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.apache.uima.internal.util;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * A Map from non-null Objects of type T to ints int value 0 reserved to mean object is not in the
 * table.
 * 
 * This impl is for use in a single thread case only, for table updates Multiple reader threads are
 * OK if there's no writing.
 * 
 * Supports shrinking (reallocating the big table)
 * 
 * Removed objects replaced with special marker object in the table so find operations continue to
 * work (they can't stop upon finding this object).
 *
 */
public class Obj2IntIdentityHashMap<T> extends Common_hash_support {

  private final T removedMarker;

  private final Class<T> componentType; // for rieifying the T type

  // private final float loadFactor = DEFAULT_LOAD_FACTOR;

  // private final int initialCapacity;

  // private int sizeWhichTriggersExpansion;
  // private int size; // number of elements in the table
  // private int nbrRemoved; // number of removed elements (coded as removed)

  // the actual Object table
  private T[] keys;
  private int[] values;

  // private boolean secondTimeShrinkable = false;

  public Obj2IntIdentityHashMap(Class<T> clazz, T removedMarker) {
    this(12, clazz, removedMarker); // default initial size
  }

  /**
   * @param initialCapacity
   *          - you can add this many before expansion
   * @param clazz
   *          - a superclass of the stored items
   * @param removedMarker
   *          - a unique value never stored in the table, used to mark removed items
   */
  public Obj2IntIdentityHashMap(int initialCapacity, Class<T> clazz, T removedMarker) {
    super(initialCapacity);
    this.componentType = clazz;
    this.removedMarker = removedMarker;
    newTable(this.initialCapacity);
  }

  // private void newTableKeepSize(int capacity) {
  // keys = (T[]) Array.newInstance(componentType, capacity);
  // values = new int[capacity];
  // sizeWhichTriggersExpansion = (int)(capacity * loadFactor);
  // nbrRemoved = 0;
  // }
  //
  // private void incrementSize() {
  // if (size + nbrRemoved >= sizeWhichTriggersExpansion) {
  // increaseTableCapacity();
  // }
  // size++;
  // }
  //
  // public boolean wontExpand() {
  // return wontExpand(1);
  // }
  //
  // public boolean wontExpand(int n) {
  // return (size + nbrRemoved + n) < sizeWhichTriggersExpansion;
  // }
  //
  // public int getCapacity() {
  // return keys.length;
  // }
  //
  // /**
  // * This may not increase the table capacity, but may just
  // * clean out the REMOVED items
  // */
  // private void increaseTableCapacity() {
  // final int oldCapacity = getCapacity();
  // // keep same capacity if just removing the "removed" markers would
  // // shrink the used slots to the same they would have been had there been no removed, and
  // // the capacity was doubled.
  // final int newCapacity = (nbrRemoved > size) ? oldCapacity : oldCapacity << 1;
  //
  // final T [] oldKeys = keys;
  // final int [] oldValues = values;
  // if (TUNE) {System.out.println("Capacity increasing from " + oldCapacity + " to " +
  // newCapacity);}
  // newTableKeepSize(newCapacity);
  // for (int i = 0; i < oldKeys.length; i++) {
  // T key = oldKeys[i];
  // if (key != null && key != removedMarker) {
  // putInner(key, oldValues[i]);
  // }
  // }
  // }
  //
  // // called by clear
  // private void newTable(int capacity) {
  // newTableKeepSize(capacity);
  // resetTable();
  // }
  //
  // private void resetHistogram() {
  // if (TUNE) {
  // histogram = new int[200];
  // Arrays.fill(histogram, 0);
  // maxProbe = 0;
  // }
  // }
  //
  // private void resetArray() {
  // Arrays.fill(keys, null);
  // Arrays.fill(values, 0);
  // resetTable();
  // }
  //
  // private void resetTable() {
  // resetHistogram();
  // size = 0;
  // }
  //
  // public void clear() {
  // secondTimeShrinkable = Misc.maybeShrink(
  // secondTimeShrinkable, size, getCapacity(), 2, initialCapacity,
  // newCapacity -> newTable(newCapacity),
  // () -> resetArray());
  // }

  /**
   * returns a position in the key/value table if the key is not found, then the position will be to
   * the place where the key would be put upon adding (without reusing REMOVED, and the current
   * internal value of keys[position] would be 0.
   * 
   * if the key is found, then keys[position] == key
   * 
   * @param obj
   *          the object to find
   * @return the probeAddr in keys array - might reference a slot holding null, or the key value if
   *         found
   */
  private int findPosition(final T obj) {
    if (obj == null) {
      throw new IllegalArgumentException("null is an invalid key");
    }

    return findPosition(

            // key hash
            Misc.hashInt(System.identityHashCode(obj)),

            // is_eq_or_is_not_present
            i -> keys[i] == null || keys[i] == obj,

            // is_removed_key
            i -> keys[i] == removedMarker);

  }

  // private int findPosition(final T obj, final boolean includeRemoved) {
  // if (obj == null) {
  // throw new IllegalArgumentException("null is an invalid key");
  // }
  //
  // final int hash = Misc.hashInt(System.identityHashCode(obj)); // identity hash map
  // int nbrProbes = 1;
  // int probeDelta = 1;
  // int probeAddr;
  //
  // final T[] localKeys = keys;
  // final int bitMask = localKeys.length - 1;
  // probeAddr = hash & bitMask;
  // while (true) {
  // final T testKey = localKeys[probeAddr];
  // if (testKey == null || testKey == obj || (includeRemoved && testKey == removedMarker)) {
  // break;
  // }
  //
  // nbrProbes++;
  // probeAddr = bitMask & (probeAddr + (probeDelta++));
  // }
  //
  // if (TUNE) {
  // final int pv = histogram[nbrProbes];
  //
  // histogram[nbrProbes] = 1 + pv;
  // if (maxProbe < nbrProbes) {
  // maxProbe = nbrProbes;
  // }
  // }
  //
  // return probeAddr;
  // }

  public boolean contains(Object obj) { // arg must be Object to fit Collection API
    return (componentType.isAssignableFrom(obj.getClass())) ? (find((T) obj) != -1) : false;
  }

  /**
   * @param obj
   *          the object to find in the table (if it is there)
   * @return the position of obj in the table, or -1 if not in the table
   */
  public int find(T obj) {
    if (obj == null || size() == 0) {
      return -1;
    }

    final int pos = findPosition(obj);
    return (obj == keys[pos]) ? pos : -1; // == because identity hash map
  }

  public int get(T obj) {
    if (obj == null || size() == 0) {
      return 0;
    }
    int pos = findPosition(obj);
    return values[pos];
  }

  /**
   * 
   * @param obj
   *          the key
   * @param value
   *          the value
   * @return the previous value, or 0 if this map did not already contain the specified key
   */
  public int put(T obj, int value) {
    int i = findPosition(obj);
    if (keys[i] == obj) { // identityHashMap
      int prevValue = values[i];
      values[i] = value;
      return prevValue;
    }

    if (found_removed != -1) {
      i = found_removed;
    }
    keys[i] = obj;
    values[i] = value;
    commonPutOrAddNotFound();
    return 0;
  }

  /**
   * used for increasing table size
   * 
   * @param rawKey
   */
  private void putInner(T obj, int value) {
    final int i = findPosition(obj);
    assert (keys[i] == null);
    keys[i] = obj;
    values[i] = value;
  }

  /**
   * Can't replace the item with a null because other keys that were stored in the table which
   * previously collided with the removed item won't be found. UIMA-4204
   * 
   * @param rawKey
   *          the value to remove
   * @return the value previously associated with the key, or 0 if none
   */

  public int remove(Object rawKey) {
    if (rawKey == null) {
      return 0;
    }

    final int pos = findPosition((T) rawKey); // null or equal obj
    int r = values[pos];

    if (rawKey == keys[pos]) {
      values[pos] = 0;
      keys[pos] = removedMarker;
      commonRemove();
    }

    return r;

  }

  // private int removeAtPosition(int pos) {
  // // found, remove it
  // keys[pos] = (T) removedMarker; // at runtime, this cast is a no-op
  // int r = values[pos];
  // values[pos] = 0;
  // size--;
  // nbrRemoved ++;
  // return r;
  // }
  //
  // public int size() {
  // return size;
  // }
  //
  // public void showHistogram() {
  // if (TUNE) {
  // int sumI = 0;
  // for (int i : histogram) {
  // sumI += i;
  // }
  //
  // System.out.format(
  // "Histogram of number of probes, loadfactor = %.1f, maxProbe=%,d nbr of find operations at last
  // table size=%,d%n",
  // loadFactor, maxProbe, sumI);
  // for (int i = 0; i <= maxProbe; i++) {
  // if (i == maxProbe && histogram[i] == 0) {
  // System.out.println("huh?");
  // }
  // System.out.println(i + ": " + histogram[i]);
  // }
  //
  // System.out.println("bytes / entry = " + (float) (keys.length) * 4 / size());
  // System.out.format("size = %,d, prevExpansionTriggerSize = %,d, next = %,d%n",
  // size(),
  // (int) ((keys.length >>> 1) * loadFactor),
  // (int) (keys.length * loadFactor));
  // }
  // }

  // /**
  // */
  // /**
  // * For iterator use
  // * @param index - a magic number returned by the internal find
  // * @return the T at that spot, or null if nothing there
  // */
  // public int get(int index) {
  // T obj = keys[index];
  // if (obj == null || obj == removedMarker) {
  // return 0; // not present
  // }
  // return values[index];
  // }
  //
  // /**
  // * advance pos until it points to a non 0 or is 1 past end
  // * @param pos -
  // * @return updated pos
  // */
  // public int moveToNextFilled(int pos) {
  // if (pos < 0) {
  // pos = 0;
  // }
  //
  // final int max = getCapacity();
  // while (true) {
  // if (pos >= max) {
  // return pos;
  // }
  // Object v = keys[pos];
  // if (v != null && v != removedMarker) {
  // return pos;
  // }
  // pos ++;
  // }
  // }
  //
  // /**
  // * decrement pos until it points to a non 0 or is -1
  // * @param pos -
  // * @return updated pos
  // */
  // public int moveToPreviousFilled(int pos) {
  // final int max = getCapacity();
  // if (pos > max) {
  // pos = max - 1;
  // }
  //
  // while (true) {
  // if (pos < 0) {
  // return pos;
  // }
  // T v = keys[pos];
  // if (v != null && v != removedMarker) {
  // return pos;
  // }
  // pos --;
  // }
  // }
  //
  private class Obj2IntIdentityHashMapIterator implements IntListIterator {

    /** always keep at valid position */
    private int curPosition;
    private final int firstPosition;

    private Obj2IntIdentityHashMapIterator() {
      this.curPosition = moveToNextFilled(0);
      this.firstPosition = this.curPosition;
    }

    @Override
    public final boolean hasNext() {
      return curPosition < keys_length() && curPosition >= 0;
    }

    @Override
    public final int next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      int r = values[curPosition];
      curPosition = moveToNextFilled(curPosition + 1);
      return r;
    }

    // if uncomment this, need to add it to the IntListIterator Interface
    // public void remove() {
    // int pos = moveToPrevious(curPosition - 1);
    // if (pos >= 0) {
    // removeAtPosition(pos);
    // }
    // }

    @Override
    public final int nextNvc() {
      int r = values[curPosition];
      curPosition = moveToNextFilled(curPosition + 1);
      return r;
    }

    @Override
    public boolean hasPrevious() {
      throw new UnsupportedOperationException();
    }

    @Override
    public int previous() {
      throw new UnsupportedOperationException();
    }

    @Override
    public int previousNvc() {
      throw new UnsupportedOperationException();
    }

    @Override
    public void moveToStart() {
      this.curPosition = firstPosition;
    }

    @Override
    public void moveToEnd() {
      this.curPosition = moveToPreviousFilled(getCapacity() - 1);
    }
  }

  public T[] getKeys() {
    T[] r = (T[]) Array.newInstance(componentType, size());
    int i = 0;
    for (T key : keys) {
      if (key != null && key != removedMarker) {
        r[i++] = key;
      }
    }
    return r;
  }

  public IntListIterator iterator() {
    return new Obj2IntIdentityHashMapIterator();
  }

  // public int moveToFirst() {
  // return (size() == 0) ? -1 : moveToNextFilled(0);
  // }
  //
  // public int moveToLast() {
  // return (size() == 0) ? -1 : moveToPreviousFilled(getCapacity() -1);
  // }
  //
  // public int moveToNext(int position) {
  // if (position < 0) {
  // return position;
  // }
  // final int n = moveToNextFilled(position + 1);
  // return (n >= getCapacity()) ? -1 : n;
  // }
  //
  // public int moveToPrevious(int position) {
  // if (position >= getCapacity()) {
  // return -1;
  // }
  // return moveToPreviousFilled(position - 1);
  // }
  //
  // public boolean isValid(int position) {
  // return (position >= 0) && (position < getCapacity());
  // }
  //
  // /**
  // * if the fs is in the set, the iterator should return it.
  // * if not, move to the first - just to return something.
  // * @param fs position to this fs
  // * @return the index if present, otherwise moveToNextFileed(0);
  // */
  // public int moveTo(FeatureStructure fs) {
  // if (componentType.isAssignableFrom(fs.getClass())) {
  // int pos = find((T)fs);
  // if (pos >= 0) {
  // return pos;
  // }
  // }
  // return moveToFirst();
  // }

  /*
   * (non-Javadoc)
   * 
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString() {
    return String.format(
            "%s [loadFactor=%s, initialCapacity=%s, sizeWhichTriggersExpansion=%s, size=%s, secondTimeShrinkable=%s%n keys=%s]",
            this.getClass().getName(), loadFactor, initialCapacity, sizeWhichTriggersExpansion,
            size(), secondTimeShrinkable, Arrays.toString(keys));
  }

  @Override
  protected boolean is_valid_key(int pos) {
    return keys[pos] != null && keys[pos] != removedMarker;
  }

  @Override
  protected int keys_length() {
    return keys.length;
  }

  @Override
  protected void newKeysAndValues(int capacity) {
    keys = (T[]) Array.newInstance(componentType, capacity);
    values = new int[capacity];

  }

  @Override
  protected void clearKeysAndValues() {
    Arrays.fill(keys, null);
    Arrays.fill(values, 0);
  }

  @Override
  protected void copy_to_new_table(/* ignored */int newCapacity, /* ignored */int oldCapacity,
          CommonCopyOld2New commonCopy) {

    final T[] oldKeys = keys;
    final int[] oldValues = values;
    commonCopy.apply(

            // copyToNew
            i -> putInner(oldKeys[i], oldValues[i]),

            // is_valid_old_key
            i -> oldKeys[i] != null && oldKeys[i] != removedMarker);
  }

  // public boolean isEmpty() {
  // return size() == 0;
  // }

}
