package com;
import java.util.Collection;
/**
 * Interface for a primitive map that uses {@code int}s as keys.
 *
 * @param <V> the value type stored in the map.
 */
public interface IntObjectMap<V> {
  /**
   * An Entry in the map.
   *
   * @param <V> the value type stored in the map.
   */
  interface Entry<V> {
    /**
     * Gets the key for this entry.
     */
    int key();
    /**
     * Gets the value for this entry.
     */
    V value();
    /**
     * Sets the value for this entry.
     */
    void setValue(V value);
  }
  /**
   * Gets the value in the map with the specified key.
   *
   * @param key the key whose associated value is to be returned.
   * @return the value or {@code null} if the key was not found in the map.
   */
  V get(int key);
  /**
   * Puts the given entry into the map.
   *
   * @param key   the key of the entry.
   * @param value the value of the entry.
   * @return the previous value for this key or {@code null} if there was no
   *         previous mapping.
   */
  V put(int key, V value);
  /**
   * Puts all of the entries from the given map into this map.
   */
  void putAll(IntObjectMap<V> sourceMap);
  /**
   * Removes the entry with the specified key.
   *
   * @param key the key for the entry to be removed from this map.
   * @return the previous value for the key, or {@code null} if there was no
   *         mapping.
   */
  V remove(int key);
  /**
   * Returns the number of entries contained in this map.
   */
  int size();
  /**
   * Indicates whether or not this map is empty (i.e {@link #size()} ==
   * {@code 0]).
   */
  boolean isEmpty();
  /**
   * Clears all entries from this map.
   */
  void clear();
  /**
   * Indicates whether or not this map contains a value for the specified key.
   */
  boolean containsKey(int key);
  /**
   * Indicates whether or not the map contains the specified value.
   */
  boolean containsValue(V value);
  /**
   * Gets an iterable collection of the entries contained in this map.
   */
  Iterable<Entry<V>> entries();
  /**
   * Gets the keys contained in this map.
   */
  int[] keys();
  /**
   * Gets the values contained in this map.
   */
  V[] values(Class<V> clazz);
  /**
   * Gets the values contatins in this map as a {@link Collection}.
   */
  Collection<V> values();
}

package com;
/*
 * Copyright 2014 The Netty Project
 *
 * The Netty Project 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.
 */
import java.lang.reflect.Array;
import java.util.AbstractCollection;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
 * A hash map implementation of {@link IntObjectMap} that uses open addressing
 * for keys. To minimize the memory footprint, this class uses open addressing
 * rather than chaining. Collisions are resolved using linear probing. Deletions
 * implement compaction, so cost of remove can approach O(N) for full maps,
 * which makes a small loadFactor recommended.
 *
 * @param <V> The value type stored in the map.
 */
public class IntObjectHashMap<V> implements IntObjectMap<V>, Iterable<IntObjectMap.Entry<V>> {
  /** Default initial capacity. Used if not specified in the constructor */
  private static final int DEFAULT_CAPACITY = 11;
  /** Default load factor. Used if not specified in the constructor */
  private static final float DEFAULT_LOAD_FACTOR = 0.5f;
  /**
   * Placeholder for null values, so we can use the actual null to mean available.
   * (Better than using a placeholder for available: less references for GC
   * processing.)
   */
  private static final Object NULL_VALUE = new Object();
  /** The maximum number of elements allowed without allocating more space. */
  private int maxSize;
  /** The load factor for the map. Used to calculate {@link #maxSize}. */
  private final float loadFactor;
  private int[] keys;
  private V[] values;
  private Collection<V> valueCollection;
  private int size;
  public IntObjectHashMap() {
    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
  }
  public IntObjectHashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }
  public IntObjectHashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 1) {
      throw new IllegalArgumentException("initialCapacity must be >= 1");
    }
    if (loadFactor <= 0.0f || loadFactor > 1.0f) {
      // Cannot exceed 1 because we can never store more than capacity elements;
      // using a bigger loadFactor would trigger rehashing before the desired load is
      // reached.
      throw new IllegalArgumentException("loadFactor must be > 0 and <= 1");
    }
    this.loadFactor = loadFactor;
    // Adjust the initial capacity if necessary.
    int capacity = adjustCapacity(initialCapacity);
    // Allocate the arrays.
    keys = new int[capacity];
    @SuppressWarnings({ "unchecked", "SuspiciousArrayCast" })
    V[] temp = (V[]) new Object[capacity];
    values = temp;
    // Initialize the maximum size value.
    maxSize = calcMaxSize(capacity);
  }
  private static <T> T toExternal(T value) {
    return value == NULL_VALUE ? null : value;
  }
  @SuppressWarnings("unchecked")
  private static <T> T toInternal(T value) {
    return value == null ? (T) NULL_VALUE : value;
  }
  @Override
  public V get(int key) {
    int index = indexOf(key);
    return index == -1 ? null : toExternal(values[index]);
  }
  @Override
  public V put(int key, V value) {
    int startIndex = hashIndex(key);
    int index = startIndex;
    for (;;) {
      if (values[index] == null) {
        // Found empty slot, use it.
        keys[index] = key;
        values[index] = toInternal(value);
        growSize();
        return null;
      }
      if (keys[index] == key) {
        // Found existing entry with this key, just replace the value.
        V previousValue = values[index];
        values[index] = toInternal(value);
        return toExternal(previousValue);
      }
      // Conflict, keep probing ...
      if ((index = probeNext(index)) == startIndex) {
        // Can only happen if the map was full at MAX_ARRAY_SIZE and couldn't grow.
        throw new IllegalStateException("Unable to insert");
      }
    }
  }
  private int probeNext(int index) {
    return index == values.length - 1 ? 0 : index + 1;
  }
  @Override
  public void putAll(IntObjectMap<V> sourceMap) {
    if (sourceMap instanceof IntObjectHashMap) {
      // Optimization - iterate through the arrays.
      IntObjectHashMap<V> source = (IntObjectHashMap<V>) sourceMap;
      for (int i = 0; i < source.values.length; ++i) {
        V sourceValue = source.values[i];
        if (sourceValue != null) {
          put(source.keys[i], sourceValue);
        }
      }
      return;
    }
    // Otherwise, just add each entry.
    for (Entry<V> entry : sourceMap.entries()) {
      put(entry.key(), entry.value());
    }
  }
  @Override
  public V remove(int key) {
    int index = indexOf(key);
    if (index == -1) {
      return null;
    }
    V prev = values[index];
    removeAt(index);
    return toExternal(prev);
  }
  @Override
  public int size() {
    return size;
  }
  @Override
  public boolean isEmpty() {
    return size == 0;
  }
  @Override
  public void clear() {
    Arrays.fill(keys, 0);
    Arrays.fill(values, null);
    size = 0;
  }
  @Override
  public boolean containsKey(int key) {
    return indexOf(key) >= 0;
  }
  @Override
  public boolean containsValue(V value) {
    V v1 = toInternal(value);
    for (V v2 : values) {
      // The map supports null values; this will be matched as
      // NULL_VALUE.equals(NULL_VALUE).
      if (v2 != null && v2.equals(v1)) {
        return true;
      }
    }
    return false;
  }
  @Override
  public Iterable<Entry<V>> entries() {
    return this;
  }
  @Override
  public Iterator<Entry<V>> iterator() {
    return new IteratorImpl();
  }
  @Override
  public int[] keys() {
    int[] outKeys = new int[size()];
    int targetIx = 0;
    for (int i = 0; i < values.length; ++i) {
      if (values[i] != null) {
        outKeys[targetIx++] = keys[i];
      }
    }
    return outKeys;
  }
  @Override
  public V[] values(Class<V> clazz) {
    @SuppressWarnings("unchecked")
    V[] outValues = (V[]) Array.newInstance(clazz, size());
    int targetIx = 0;
    for (V value : values) {
      if (value != null) {
        outValues[targetIx++] = value;
      }
    }
    return outValues;
  }
  @Override
  public Collection<V> values() {
    Collection<V> valueCollection = this.valueCollection;
    if (valueCollection == null) {
      this.valueCollection = valueCollection = new AbstractCollection<V>() {
        @Override
        public Iterator<V> iterator() {
          return new Iterator<V>() {
            final Iterator<Entry<V>> iter = IntObjectHashMap.this.iterator();
            @Override
            public boolean hasNext() {
              return iter.hasNext();
            }
            @Override
            public V next() {
              return iter.next().value();
            }
            @Override
            public void remove() {
              throw new UnsupportedOperationException();
            }
          };
        }
        @Override
        public int size() {
          return size;
        }
      };
    }
    return valueCollection;
  }
  @Override
  public int hashCode() {
    // Hashcode is based on all non-zero, valid keys. We have to scan the whole keys
    // array, which may have different lengths for two maps of same size(), so the
    // capacity cannot be used as input for hashing but the size can.
    int hash = size;
    for (int key : keys) {
      // 0 can be a valid key or unused slot, but won't impact the hashcode in either
      // case.
      // This way we can use a cheap loop without conditionals, or hard-to-unroll
      // operations,
      // or the devastatingly bad memory locality of visiting value objects.
      // Also, it's important to use a hash function that does not depend on the
      // ordering
      // of terms, only their values; since the map is an unordered collection and
      // entries can end up in different positions in different maps that have the
      // same
      // elements, but with different history of puts/removes, due to conflicts.
      hash ^= key;
    }
    return hash;
  }
  @Override
  public boolean equals(Object obj) {
    if (this == obj) {
      return true;
    }
    if (!(obj instanceof IntObjectMap)) {
      return false;
    }
    @SuppressWarnings("rawtypes")
    IntObjectMap other = (IntObjectMap) obj;
    if (size != other.size()) {
      return false;
    }
    for (int i = 0; i < values.length; ++i) {
      V value = values[i];
      if (value != null) {
        int key = keys[i];
        Object otherValue = other.get(key);
        if (value == NULL_VALUE) {
          if (otherValue != null) {
            return false;
          }
        } else if (!value.equals(otherValue)) {
          return false;
        }
      }
    }
    return true;
  }
  /**
   * Locates the index for the given key. This method probes using double hashing.
   *
   * @param key the key for an entry in the map.
   * @return the index where the key was found, or {@code -1} if no entry is found
   *         for that key.
   */
  private int indexOf(int key) {
    int startIndex = hashIndex(key);
    int index = startIndex;
    for (;;) {
      if (values[index] == null) {
        // It's available, so no chance that this value exists anywhere in the map.
        return -1;
      }
      if (key == keys[index]) {
        return index;
      }
      // Conflict, keep probing ...
      if ((index = probeNext(index)) == startIndex) {
        return -1;
      }
    }
  }
  /**
   * Returns the hashed index for the given key.
   */
  private int hashIndex(int key) {
    // Allowing for negative keys by adding the length after the first mod
    // operation.
    return (key % keys.length + keys.length) % keys.length;
  }
  /**
   * Grows the map size after an insertion. If necessary, performs a rehash of the
   * map.
   */
  private void growSize() {
    size++;
    if (size > maxSize) {
      // Need to grow the arrays. We take care to detect integer overflow,
      // also limit array size to ArrayList.MAX_ARRAY_SIZE.
      rehash(adjustCapacity((int) Math.min(keys.length * 2.0, Integer.MAX_VALUE - 8)));
    } else if (size == keys.length) {
      // Open addressing requires that we have at least 1 slot available. Need to
      // refresh
      // the arrays to clear any removed elements.
      rehash(keys.length);
    }
  }
  /**
   * Adjusts the given capacity value to ensure that it's odd. Even capacities can
   * break probing.
   */
  private static int adjustCapacity(int capacity) {
    return capacity | 1;
  }
  /**
   * Removes entry at the given index position. Also performs opportunistic,
   * incremental rehashing if necessary to not break conflict chains.
   *
   * @param index the index position of the element to remove.
   */
  private void removeAt(int index) {
    --size;
    // Clearing the key is not strictly necessary (for GC like in a regular
    // collection),
    // but recommended for security. The memory location is still fresh in the cache
    // anyway.
    keys[index] = 0;
    values[index] = null;
    // In the interval from index to the next available entry, the arrays may have
    // entries
    // that are displaced from their base position due to prior conflicts. Iterate
    // these
    // entries and move them back if possible, optimizing future lookups.
    // Knuth Section 6.4 Algorithm R, also used by the JDK's IdentityHashMap.
    int nextFree = index;
    for (int i = probeNext(index); values[i] != null; i = probeNext(i)) {
      int bucket = hashIndex(keys[i]);
      if (i < bucket && (bucket <= nextFree || nextFree <= i) || bucket <= nextFree && nextFree <= i) {
        // Move the displaced entry "back" to the first available position.
        keys[nextFree] = keys[i];
        values[nextFree] = values[i];
        // Put the first entry after the displaced entry
        keys[i] = 0;
        values[i] = null;
        nextFree = i;
      }
    }
  }
  /**
   * Calculates the maximum size allowed before rehashing.
   */
  private int calcMaxSize(int capacity) {
    // Clip the upper bound so that there will always be at least one available
    // slot.
    int upperBound = capacity - 1;
    return Math.min(upperBound, (int) (capacity * loadFactor));
  }
  /**
   * Rehashes the map for the given capacity.
   *
   * @param newCapacity the new capacity for the map.
   */
  private void rehash(int newCapacity) {
    int[] oldKeys = keys;
    V[] oldVals = values;
    keys = new int[newCapacity];
    @SuppressWarnings({ "unchecked", "SuspiciousArrayCast" })
    V[] temp = (V[]) new Object[newCapacity];
    values = temp;
    maxSize = calcMaxSize(newCapacity);
    // Insert to the new arrays.
    for (int i = 0; i < oldVals.length; ++i) {
      V oldVal = oldVals[i];
      if (oldVal != null) {
        // Inlined put(), but much simpler: we don't need to worry about
        // duplicated keys, growing/rehashing, or failing to insert.
        int oldKey = oldKeys[i];
        int index = hashIndex(oldKey);
        for (;;) {
          if (values[index] == null) {
            keys[index] = oldKey;
            values[index] = toInternal(oldVal);
            break;
          }
          // Conflict, keep probing. Can wrap around, but never reaches startIndex again.
          index = probeNext(index);
        }
      }
    }
  }
  /**
   * Iterator for traversing the entries in this map.
   */
  private final class IteratorImpl implements Iterator<Entry<V>>, Entry<V> {
    private int prevIndex = -1;
    private int nextIndex = -1;
    private int entryIndex = -1;
    private void scanNext() {
      for (;;) {
        if (++nextIndex == values.length || values[nextIndex] != null) {
          break;
        }
      }
    }
    @Override
    public boolean hasNext() {
      if (nextIndex == -1) {
        scanNext();
      }
      return nextIndex < keys.length;
    }
    @Override
    public Entry<V> next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      prevIndex = nextIndex;
      scanNext();
      // Always return the same Entry object, just change its index each time.
      entryIndex = prevIndex;
      return this;
    }
    @Override
    public void remove() {
      if (prevIndex < 0) {
        throw new IllegalStateException("next must be called before each remove.");
      }
      removeAt(prevIndex);
      prevIndex = -1;
    }
    // Entry implementation. Since this implementation uses a single Entry, we
    // coalesce that
    // into the Iterator object (potentially making loop optimization much easier).
    @Override
    public int key() {
      return keys[entryIndex];
    }
    @Override
    public V value() {
      return toExternal(values[entryIndex]);
    }
    @Override
    public void setValue(V value) {
      values[entryIndex] = toInternal(value);
    }
  }
  @Override
  public String toString() {
    if (size == 0) {
      return "{}";
    }
    StringBuilder sb = new StringBuilder(4 * size);
    for (int i = 0; i < values.length; ++i) {
      V value = values[i];
      if (value != null) {
        sb.append(sb.length() == 0 ? "{" : ", ");
        sb.append(keyToString(keys[i])).append('=').append(value == this ? "(this Map)" : value);
      }
    }
    return sb.append('}').toString();
  }
  /**
   * Helper method called by {@link #toString()} in order to convert a single map
   * key into a string.
   */
  protected String keyToString(int key) {
    return Integer.toString(key);
  }
}