/*
 * 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.util.Arrays;
import java.util.NoSuchElementException;

import org.apache.uima.util.impl.Constants;

//@formatter:off
/**
 * An set of non-zero integers, ability to iterate over them (possibly in a sorted way),
 * with O(1) operations for adding, removing, and testing for contains.
 * 
 * Optimized for adding mostly increasing integers (with some space for less-than-first-one-added).
 *   - major uses: indexes of Feature Structures.
 * Optimize for small sets 
 * 
 * Graceful degradation for completely random integer operations on large sets; 
 *   keep O(1) operations, at the expense of extra space (&lt; 3 x size).
 * 
 *   Uses several different representations depending on the range of ints stored and the total number of ints stored.
 * 
 *     Sizes:  Tiny, medium, large 
 *     Ranges: semi-knowable, unknowable;  
 *               if semi-knowable, dense, small-range (&lt; 65K), large-range
 * 
 *     For all sizes, 
 *       if dense, use IntBitSet (with offset)
 * 
 *     else 
 *       For large, (implies large-range, too) use IntHashSet  
 * 
 *       For medium,
 *         if small-range &lt; 65K, use IntHashSet with offset 
 *         else use IntHashSet 
 * 
 *   Arrange switching between representations
 *     to occur infrequently, especially as cost of switching (size) grows
 *   Arrange checking for switching to occur infrequently, taking into account how underlying data structures grow
 *     (which is often by doubling)
 *   Switch when adding new member(s) if alternative representation is sufficiently smaller
 */
//@formatter:on
public class PositiveIntSet_impl implements PositiveIntSet {

  // number of words a inthashset has to be better than intbitset to cause switch
  private static final int HYSTERESIS = 16;

  private static final int INT_SET_MAX_SIZE = 16;

  private static final int HASH_SET_SHORT_MAX_SIZE = (1 << 16) - 1; // 65535

  // Extra space in bitset for expansion - can add an int (- offset) up to that size
  // Initial space = 2 words = 1 long.
  // 64 *4 is 8 words, = 256.
  private static final int BIT_SET_OVERALLOCATE = 64 * 4; // 8 words minimum

  // Extra space in hashset for initial capacity - when creating from bitmap set - multiplier of
  // existing size
  private static final int HASH_SET_OVERALLOCATE_DIVIDER_SHIFT = 1; // bit shift right = divide by 2
                                                                    // = 50% of existing capacity

  private PositiveIntSet intSet; // one of 3 representations: IntBitSet, IntHashSet, IntSet (based
                                 // on IntVector)

  // package private for test case
  boolean isBitSet = false;
  boolean isIntSet = false;
  boolean isHashSet = false;

  boolean secondTimeShrinkable = false;

  /**
   * Set false once we find we have to reduce the bit offset
   */
  // package private for test case
  boolean useOffset = true;

  public PositiveIntSet_impl() {
    this(0, 0, 0);
  }

  /**
   * Set up a Positive Bit Set
   * 
   * @param initialSize
   *          - if 0, don't allocate yet, wait for first add. If isBitSetDense, then this number is
   *          interpreted as the first int to be added, typically with an offset. The next two
   *          params are used only if initialSize is not 0.
   * @param estMin
   *          - the estimated minimum int value to be added
   * @param estMax
   *          - the estimated max int value to be added
   */
  public PositiveIntSet_impl(int initialSize, int estMin, int estMax) {
    if (initialSize == 0) {
      isBitSet = true; // try first as bit set with offset perhaps
      return; // delay allocation until we know what the 1st int will be
    }

    if ((initialSize < 0) || (estMin < 0) || (estMax < estMin)) {
      throw new IllegalArgumentException();
    }

    estMax = Math.max(initialSize, estMax); // because its a positive int set

    // offsets are different for bit set and hash set
    // for bit set, it's set to the estMin - capped 12.5% from the estMin (cap is 16 words)
    // for hash set, if the size > 65K, it's ignored
    // it's set to 3/4 up the "range" of est max - est min

    int offsetBitSet = estimatedBitSetOffset(estMin, -1);

    int offsetHashSet = getHashSetOffset(estMax, estMin);

    int bitSetWordsNeeded = getBitSetSpaceFromRange(estMax - offsetBitSet, 0);
    int hashSetWordsNeeded = getHashSetSpace(initialSize, estMax, estMin);

    // no HYSTERESIS in test below - pick absolute smaller for initial alloc
    if (bitSetWordsNeeded < hashSetWordsNeeded) {
      allocateIntBitSet(estMax, estMin, offsetBitSet);
      isBitSet = true;
      return;
    }

    // choose between IntHashSet and IntSet based on size
    if (initialSize <= INT_SET_MAX_SIZE) {
      intSet = new IntSet(initialSize);
      isIntSet = true;
      return;
    }

    intSet = new IntHashSet(initialSize, offsetHashSet);
    isHashSet = true;

  }

  @Override
  public IntListIterator iterator() {
    return getUnorderedIterator();
  }

  public IntListIterator getUnorderedIterator() {
    if (null == intSet) {
      intSet = new IntSet(0);
    }
    return intSet.iterator();
  }

  public IntListIterator getOrderedIterator() {
    if (isBitSet) {
      if (null == intSet) {
        return new IntListIteratorOverArray(Constants.EMPTY_INT_ARRAY);
      }
      return intSet.iterator();
    }

    int[] allValues = new int[size()];
    IntListIterator it = intSet.iterator();
    int i = 0;
    while (it.hasNext()) {
      allValues[i++] = it.nextNvc();
    }
    Arrays.sort(allValues);
    return new IntListIteratorOverArray(allValues);
  }

  private class IntListIteratorOverArray implements IntListIterator {
    private int[] a;
    private int pos;

    IntListIteratorOverArray(int[] a) {
      this.a = a;
      pos = 0;
    }

    @Override
    public boolean hasNext() {
      return pos >= 0 && pos < a.length;
    }

    @Override
    public int nextNvc() {
      return a[pos++];
    }

    @Override
    public boolean hasPrevious() {
      return pos > 0 && pos < a.length;
    }

    @Override
    public int previousNvc() {
      return a[--pos]; // decrement first!
    }

    @Override
    public void moveToStart() {
      pos = 0;
    }

    @Override
    public void moveToEnd() {
      pos = a.length - 1;
    }
  }

  /*
   * (non-Javadoc)
   * 
   * @see org.apache.uima.internal.util.PositiveIntSetI#clear()
   */
  @Override
  public void clear() {
    if (null != intSet) {
      if (isBitSet) {
        if (secondTimeShrinkable) {
          secondTimeShrinkable = false;
          IntBitSet ib = (IntBitSet) intSet;
          int max = ib.getLargestMenber();
          int offset = ib.getOffset();
          intSet = new IntBitSet((max - offset) >> 1, offset);
        } else {
          intSet.clear();
          secondTimeShrinkable = true;
        }
      } else {
        intSet.clear();
      }
    }
  }

  /*
   * (non-Javadoc)
   * 
   * @see org.apache.uima.internal.util.PositiveIntSetI#contains(int)
   */
  @Override
  public boolean contains(int key) {
    return (null != intSet) ? intSet.contains(key) : false;
  }

  @Override
  public int find(int element) {
    return (null != intSet) ? intSet.find(element) : -1;
  }

  /*
   * (non-Javadoc)
   * 
   * @see org.apache.uima.internal.util.PositiveIntSetI#add(int)
   */
  @Override
  public boolean add(int key) {
    maybeSwitchRepresentation(key);
    return intSet.add(key);
  }

  /*
   * (non-Javadoc)
   * 
   * @see org.apache.uima.internal.util.PositiveIntSetI#remove(int)
   */
  @Override
  public boolean remove(int key) {
    return (null != intSet) ? intSet.remove(key) : false;
  }

  /*
   * (non-Javadoc)
   * 
   * @see org.apache.uima.internal.util.PositiveIntSetI#size()
   */
  @Override
  public int size() {
    return (null != intSet) ? intSet.size() : 0;
  }

  // public void add(int[] vs) {
  // for (int i : vs) {
  // add(i);
  // }
  // }

  /**
   * When a key is added which is lower than the offset, we need to adjust the whole int set table.
   * Although an array copy could do this, we don't have access to the bitset impl.
   * 
   * So we just set the offset to 0, and either convert the whole thing to a inthashset or copy all
   * the bits to a new bit set.
   * 
   * @param key
   */
  private void adjustBitSetForLowerOffset(int key) {
    final IntBitSet intBitSet = (IntBitSet) intSet;
    final int size = intBitSet.size() + 1;
    final int largestInt = intBitSet.getLargestMenber(); // not called if key > largest member
    final int bitSetSpaceNeeded = getBitSetSpaceFromRange(largestInt, 0); // doesn't use offset
    final int hashSetSpaceNeeded = getHashSetSpace(size, largestInt, key); // computes using load
                                                                           // factor,
    useOffset = false; // stop using because we have evidence it isn't appropriate

    if (hashSetSpaceNeeded < (bitSetSpaceNeeded - HYSTERESIS)) {
      int offset = getHashSetOffset(largestInt, key);
      switchFromBitSet(size, offset);

      // keep as bit set - it's smaller, but drop the offset
    } else {
      IntListIterator it = intSet.iterator();
      allocateIntBitSet(largestInt, key, 0);
      while (it.hasNext()) {
        intSet.add(it.nextNvc());
      }
    }
  }

  private static int getHashSetOffset(int estMax, int estMin) {
    int range = estMax - estMin;
    assert (range >= 0);
    return (range > HASH_SET_SHORT_MAX_SIZE) ? Integer.MIN_VALUE : // signal to force use of 4 byte
                                                                   // ints
    // make the offset such that the 0 point is 3/4 of the way
    // toward the top of the range, because there's more likelyhood
    // of expansion in that direction
            estMax - (range >> 2);
  }

  public int[] toUnorderedIntArray() {
    final int[] a = new int[size()];
    IntListIterator it = getUnorderedIterator();
    int i = 0;
    while (it.hasNext()) {
      a[i++] = it.nextNvc();
    }
    return a;
  }

  public int[] toOrderedIntArray() {
    int[] a = toUnorderedIntArray();
    if (isBitSet) {
      return a;
    }
    Arrays.sort(a);
    return a;
  }

  /**
   * Only called if key won't fit in existing IntHashSet, IntSet or IntBitSet allocation
   * 
   * If IntBitSet (spaceUsed != 0) compute what its size() (capacity) would be if the key were added
   * (causing doubling); include the overhead of the intbitset class.
   * 
   * long words required = larger of double the current size, or the number of long words required
   * 
   * @param adjKey
   *          - the range of bits needed
   * @param spaceUsed
   *          - the number of bits currently allocated (if currently a bit set), else 0
   * @return number of words needed to store the range,
   */
  private static int getBitSetSpaceFromRange(int adjKey, int spaceUsed) {
    int w64 = 1 + (adjKey >> 6); // 64 bits per long, add one because 0 to 63 takes one word)
    spaceUsed = spaceUsed >> (6 - 1); // in # of long words, * 2 because the alloc doubles the space

    int newSpace = Math.max(spaceUsed, w64) << 1; // <<1 to convert to # of words from # of longs
    // e.g., 31 key => 1 word, 32 key => 2 words
    return newSpace + 2; // 2 more for IntBitSet object overhead
  }

  /**
   * 
   * @param size
   *          including new element to be added
   * @return number of words including overhead to store that many elements unless is bigger than
   *         INT_SET_MAX_SIZE, then return MAX_VALUE
   */
  private static int getIntSetSpace(int size) {
    return (size < INT_SET_MAX_SIZE) ? size + 4 : Integer.MAX_VALUE;
  }

  /**
   * Only called if key won't fit in existing allocation
   * 
   * returns new hash table size ( usually double) + overhead
   * 
   * @param numberOfEntries
   * @return new hash table size ( usually double) + overhead
   */
  private int getHashSetSpace() {
    return ((IntHashSet) intSet).getSpaceUsedInWords() * 2 + IntHashSet.getSpaceOverheadInWords();
  }

  /**
   * For the case where the intHashSet doesn't yet exist
   * 
   * @param numberOfElements
   *          -
   * @param estMax
   *          - the largest int to be stored
   * @param estMin
   *          - the smallest int to be stored
   * @return the size in words
   */
  private static int getHashSetSpace(int numberOfElements, int estMax, int estMin) {
    boolean isShort;
    if (numberOfElements > HASH_SET_SHORT_MAX_SIZE) {
      isShort = false;
    } else {
      isShort = (estMax - estMin) < HASH_SET_SHORT_MAX_SIZE;
    }
    int numberOfTableElements = IntHashSet.tableSpace(numberOfElements);
    return (numberOfTableElements >> ((isShort) ? 1 : 0)) + IntHashSet.getSpaceOverheadInWords();
  }

  /**
   * When converting from bitset to hash set, the initial hash set should be big enough so that it
   * takes a while before it is doubled-expanded.
   * 
   * Reduce overallocation for small sizes because the cost to switch is low, and the % overallocate
   * could be a large.
   * 
   * @param existingSize
   * @return overallocate size
   */
  private static int getHashSetOverAllocateSize(int existingSize) {
    return existingSize + (existingSize >> HASH_SET_OVERALLOCATE_DIVIDER_SHIFT);
  }

//@formatter:off
  /**
   * logic for switching representation
   * 
   * BitSet preferred - is faster, can be more compact, and permits ordered iteration HashSet used
   * when BitSet is too space inefficient.
   * 
   * Avoid switching if the new key being added won't increase the representation size
   *   - for hash: if number of elements +1 won't cause doubling of the hash table
   *   - for bitset: if key will fit in existing "capacity"
   * 
   * Compute space needed after adding
   *   - bitset:  array doubles
   *   - hashset: array doubles
   *
   * Preventing jitters back and forth:
   *   - removes don't cause switching
   *   - compare against other size including its non-linear space jumps.   
   */
//@formatter:on
  private void maybeSwitchRepresentation(int newKey) {
    if (isBitSet) {
      handleBitSet(newKey);
      return;
    }
    if (isIntSet) {
      handleIntSet(newKey);
      return;
    }
    handleHashSet(newKey);
  }

  /********************
   * Bit Set
   ********************/
  private void handleBitSet(int newKey) {
    IntBitSet intBitSet = (IntBitSet) intSet;

    if (intBitSet == null) {
      /*********
       * Size is 0, use this opportunity to set the offset unless that has been a bad strategy for
       * this instance already
       ********/
      boolean guaranteedFits = allocateIntBitSet(newKey, newKey, -1);
      intBitSet = (IntBitSet) intSet;
      if (guaranteedFits) {
        return;
      }
    }

    final int offset = intBitSet.getOffset();

    if (newKey < offset) {
      // may change representation; always abandons this bit set
      adjustBitSetForLowerOffset(newKey);
      return;
    }

    // return if newKey fits in existing allocation
    final int spaceUsed = intBitSet.getSpaceUsed_in_bits_no_overhead();
    final int adjKey = newKey - offset;
    if (adjKey < spaceUsed) {
      return;
    }

    // this newKey doesn't fit in existing bit set allocation; it's too large
    // figure out if we should expand this bit set or switch representations

    final int bitSetSpaceNeeded = getBitSetSpaceFromRange(adjKey, spaceUsed); // in 32 bit words
    final int sizeNeeded = intBitSet.size() + 1;

    if (getIntSetSpace(sizeNeeded) < bitSetSpaceNeeded) {
      switchToIntSet(sizeNeeded);
      return;
    }

    // when computing hashset size, overallocate by 50% to avoid immediately doubling
    final int hashSetOverAllocateSize = getHashSetOverAllocateSize(sizeNeeded);
    final int hashSetOverAllocateSpace = getHashSetSpace(hashSetOverAllocateSize, newKey, offset);
    // switch if hashmap space plus hysteresis would be < bitmap space
    if (hashSetOverAllocateSpace < (bitSetSpaceNeeded - HYSTERESIS)) {
      switchToHashSet(hashSetOverAllocateSize, getHashSetOffset(newKey, offset));
    }
    return;
  }

  /********************
   * IntSet *
   ********************/
  private void handleIntSet(int newKey) {
    IntSet is = (IntSet) intSet;
    final int size = is.size() + 1;
    if (size <= INT_SET_MAX_SIZE) {
      return;
    }

    // switch to bit or IntHash

    // first, compute max and min values
    int mostPos = Integer.MIN_VALUE;
    int mostNeg = Integer.MAX_VALUE;
    for (int i = 0; i < size - 1; i++) {
      final int v = is.get(i);
      if (v > mostPos) {
        mostPos = v;
      }
      if (v < mostNeg) {
        mostNeg = v;
      }
    }
    // include the newKey in the computation of these
    if (newKey > mostPos) {
      mostPos = newKey;
    }
    if (newKey < mostNeg) {
      mostNeg = newKey;
    }

    // make a bit set or hash set.
    // have 16 members, so the hash set is approx 32 + 11 words = 43.
    // bit set is approx 2 + range / 32
    final int bitSetSpace = getBitSetSpaceFromRange(mostPos - mostNeg, 0);
    final int hashSetOverAllocSize = getHashSetOverAllocateSize(size);
    final int hashSetSpace = getHashSetSpace(hashSetOverAllocSize, mostPos, mostNeg);
    if (bitSetSpace < hashSetSpace) {
      switchToBitSet(mostPos, mostNeg, estimatedBitSetOffset(mostNeg, -1));
      return;
    }
    switchToHashSet(hashSetOverAllocSize, getHashSetOffset(mostPos, mostNeg));
  }

  /********************
   * Hash Set
   ********************/
  private void handleHashSet(int newKey) {
    // maybe switch to IntBitSet
    // space used in words (32 bit words)
    // don't bother to include the new element - it might not be "added"
    // if it was already there, and only serves to decrease hysteresis a bit
    final IntHashSet intHashSet = (IntHashSet) intSet;
    if (intHashSet.wontExpand()) {
      return;
    }

    final int hashSetSpaceNeeded = getHashSetSpace(); // computes the doubling of space

    final int maxInt = intHashSet.getMostPositive();
    // https://issues.apache.org/jira/browse/UIMA-4159
    final int offset = useOffset ? Math.min(intHashSet.getMostNegative(), newKey) : 0;
    final int bitSetSpaceNeeded = getBitSetSpaceFromRange(BIT_SET_OVERALLOCATE + maxInt - offset,
            0);

    if (bitSetSpaceNeeded < (hashSetSpaceNeeded - HYSTERESIS)) {
      switchToBitSet(maxInt, intHashSet.getMostNegative(), offset);
    }
  }

  /**
   * Allocate a new IntBitSet
   * 
   * @param estMax
   *          the largest int to store in the bit set - determines the initial size
   * @param estMin
   *          this is a lower bound on the value that can be in the bit set
   * @param offsetSpec
   *          this is the offset to use, or -1, to calculate the offset from the initial_size
   *          (assuming a small amount of adds will be for ints somewhat less than the initial_size
   *          entry (being treated as the first int to be added)
   * @return true if allocated with offset, implying guarantee the estMax key fits.
   */
  private boolean allocateIntBitSet(int estMax, int estMin, int offsetSpec) {
    isBitSet = true;
    isHashSet = isIntSet = false;
    if (useOffset) {

      // initialize bitSetOffset to the key, minus some amount to allow some storage of previous
      // values
      // a minimum of 63, a maximum of 512 == 16 words, when key is > 4K (128 words)
      final int offset = estimatedBitSetOffset(estMin, offsetSpec);
      intSet = new IntBitSet(BIT_SET_OVERALLOCATE + estMax - offset, offset);
      // because of offset, won't have to switch to hash for this key
      return true;
    } else {
      intSet = new IntBitSet(BIT_SET_OVERALLOCATE + estMax);
      return false;
    }
  }

  private static int estimatedBitSetOffset(int estMin, int offsetSpec) {
    return // initialize bitSetOffset to the key, minus some amount to allow some storage of
           // previous values
           // a minimum of 63, a maximum of 512 == 16 words, when key is > 4K (128 words)
    (offsetSpec == -1) ? Math.max(0, estMin - Math.min(1023, Math.max(63, estMin >> 3)))
            : offsetSpec;
  }

  /**
   * switching from bit set to either IntSet or IntHashSet
   * 
   * @param size
   *          - space needed including new item
   * @param offset
   *          - for IntHashSet values kept as short, the offset subtracted from values before
   *          storing them offset == Integer.MIN_VALUE means use 4 byte ints
   */
  private void switchFromBitSet(int size, int offset) {
    if (size < INT_SET_MAX_SIZE) {
      switchToIntSet(size);
      return;
    }
    switchToHashSet(size, offset);
  }

  /**
   * switch to IntSet
   * 
   * @param size
   *          number of elements to be able to store without expanding
   */
  private void switchToIntSet(int size) {
    IntListIterator it = intSet.iterator();

    intSet = new IntSet(size);
    isIntSet = true;
    isBitSet = isHashSet = false;

    while (it.hasNext()) {
      intSet.add(it.nextNvc());
    }
    return;
  }

  /**
   * Switch from any intSet impl to Hash Set
   * 
   * @param size
   *          - the capacity - this many elements could be stored before swtiching
   * @param offset
   *          - used only when the size < 65K, and is a value subtracted from elements before
   *          storing them, in an attempt to fit the results into just "short"s instead of "int"s if
   *          == MIN_VALUE, then force 4 byte ints
   */
  private void switchToHashSet(int size, int offset) {
    IntListIterator it = intSet.iterator();

    intSet = new IntHashSet(size, offset);
    isIntSet = isBitSet = false;
    isHashSet = true;

    while (it.hasNext()) {
      intSet.add(it.nextNvc());
    }
  }

  private void switchToBitSet(int estMax, int estMin, int offset) {
    final IntListIterator it = intSet.iterator();

    allocateIntBitSet(estMax, estMin, offset);

    while (it.hasNext()) {
      intSet.add(it.nextNvc());
    }
  }

  @Override
  public int get(int position) {
    if (null == intSet) {
      throw new NoSuchElementException();
    }
    return intSet.get(position);
  }

  @Override
  public int moveToFirst() {
    return (null == intSet) ? -1 : intSet.moveToFirst();
  }

  @Override
  public int moveToLast() {
    return (null == intSet) ? -1 : intSet.moveToLast();
  }

  @Override
  public int moveToNext(int position) {
    return (null == intSet) ? -1 : intSet.moveToNext(position);
  }

  @Override
  public int moveToPrevious(int position) {
    return (null == intSet) ? -1 : intSet.moveToPrevious(position);
  }

  @Override
  public boolean isValid(int position) {
    return (null == intSet) ? false : intSet.isValid(position);
  }

  @Override
  public void bulkAddTo(IntVector v) {
    if (null != intSet) {
      intSet.bulkAddTo(v);
    }
  }

  @Override
  public int[] toIntArray() {
    if (null != intSet) {
      return intSet.toIntArray();
    }
    return Constants.EMPTY_INT_ARRAY;
  }

  /*
   * (non-Javadoc)
   * 
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString() {
    return String.format(
            "PositiveIntSet_impl [%n  intSet=%s%n secondTimeShrinkable=%s, useOffset=%s]", intSet,
            secondTimeShrinkable, useOffset);
  }

  // for testing
  boolean isOffsetBitSet() {
    return (isBitSet && ((IntBitSet) intSet).getOffset() != 0);
  }

  // for testing
  boolean isShortHashSet() {
    return (isHashSet && ((IntHashSet) intSet).isShortHashSet());
  }

}
