/*
 * Java
 *
 * Copyright 2018-2020 MicroEJ Corp. All rights reserved.
 * This library is provided in source code for use, modification and test, subject to license terms.
 * Any modification of the source code will break MicroEJ Corp. warranties on the whole library.
 */
package ej.basictool.map;

import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;

import ej.annotation.NonNull;
import ej.basictool.ArrayTools;

/**
 * An object that maps keys to values. A packed map cannot contain duplicate keys; each key can map to at most one
 * value.
 * <p>
 * The main goal of this implementation, compared to a standard {@link java.util.Map}, is to have a small heap
 * footprint. For instance, it doesn't provide direct access to {@code (key,value)} entries. This allows to simplify the
 * implementation.
 * <p>
 * It uses a single array containing both keys and values that is fitted to the content (enlarged when an entry is
 * added, shrunk when an entry is removed). The array contains first all the keys then all the values. The keys are
 * sorted by their hashcode value. A key is retrieved first using a dichotomic search on its hashcode, then using a
 * linear search within keys having the same hashcode.
 *
 * @param <K>
 *            the type of keys maintained by this map.
 * @param <V>
 *            the type of mapped values.
 */
public abstract class AbstractPackedMap<K, V> {

	/**
	 * Keys and values of the map.
	 */
	@NonNull
	protected Object[] keysValues;

	/**
	 * Constructs an empty map.
	 */
	public AbstractPackedMap() {
		this.keysValues = new Object[0];
	}

	/**
	 * Constructs a map with the same mappings as the specified map.
	 *
	 * @param map
	 *            the map whose mappings are to be placed in this map.
	 * @throws NullPointerException
	 *             if the specified map is {@code null}.
	 */
	public AbstractPackedMap(@NonNull AbstractPackedMap<K, V> map) {
		this.keysValues = map.keysValues.clone();
	}

	/**
	 * Removes all of the mappings from this map. The map will be empty after this call returns.
	 *
	 * @throws UnsupportedOperationException
	 *             if the {@code clear} operation is not supported by this map
	 */
	public void clear() {
		this.keysValues = new Object[0];
	}

	/**
	 * Returns a shallow copy of this map instance: the keys and values themselves are not cloned.
	 *
	 * @return a shallow copy of this map
	 */
	@Override
	public abstract Object clone();

	/**
	 * Returns {@code true} if this map contains a mapping for the specified key. More formally, returns {@code true} if
	 * and only if this map contains a mapping for a key same than the given key (see {@link #isSame(Object, Object)}).
	 * (There can be at most one such mapping.)
	 *
	 * @param key
	 *            key whose presence in this map is to be tested.
	 * @return {@code true} if this map contains a mapping for the specified key.
	 * @throws NullPointerException
	 *             if the specified key is {@code null}.
	 */
	public boolean containsKey(@NonNull Object key) {
		return findExactIndex(this.keysValues, key) != -1;
	}

	/**
	 * Returns {@code true} if this map maps one or more keys to the specified value. More formally, returns
	 * {@code true} if and only if this map contains at least one mapping to a value {@code v} such that
	 * {@code (value==null ? v==null : value.equals(v))}. This operation requires time linear in the map size.
	 *
	 * @param value
	 *            value whose presence in this map is to be tested.
	 * @return {@code true} if this map maps one or more keys to the specified value.
	 * @throws NullPointerException
	 *             if the specified key is {@code null}.
	 */
	public boolean containsValue(@NonNull Object value) {
		Object[] keysValues = this.keysValues;
		int keysValuesLength = keysValues.length;
		int size = keysValuesLength / 2;
		for (int i = size - 1; ++i < keysValuesLength;) {
			Object candidateValue = keysValues[i];
			if (candidateValue == null ? value == null : candidateValue.equals(value)) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Compares the specified object with this map for equality. Returns {@code true} if the given object is also a map
	 * and the two maps represent the same mappings.
	 *
	 * @param o
	 *            object to be compared for equality with this map
	 * @return {@code true} if the specified object is equal to this map
	 */
	@Override
	public boolean equals(Object o) {
		if (o == this) {
			return true;
		}
		// Check if the two maps are the same class because the equals may be not symmetric.
		// When comparing an IdentityPackedMap and a PackedMap, depending which one is the receiver, the result may be
		// different because containsKey() method is not implemented with the same comparison.
		if (o == null || getClass() != o.getClass()) {
			return false;
		}
		@SuppressWarnings("unchecked")
		AbstractPackedMap<K, V> other = (AbstractPackedMap<K, V>) o;
		Object[] keysValues = this.keysValues;
		int size = keysValues.length / 2;
		if (other.size() != size) {
			return false;
		}

		for (int i = -1; ++i < size;) {
			Object key = unwrapKey(keysValues[i]);
			if (!other.containsKey(key)) {
				return false;
			}
			Object value = keysValues[size + i];
			Object otherValue = other.get(key);
			if (!(value == null ? otherValue == null : value.equals(otherValue))) {
				return false;
			}
		}
		return true;
	}

	/**
	 * Returns the value to which the specified key is mapped, or {@code null} if this map contains no mapping for the
	 * key.
	 *
	 * <p>
	 * More formally, if this map contains a mapping from a key {@code k} to a value {@code v} such that key is the same
	 * as k (see {@link #isSame(Object, Object)}), then this method returns {@code v} otherwise it returns {@code null}.
	 * (There can be at most one such mapping.)
	 *
	 * <p>
	 * A return value of {@code null} does not <i>necessarily</i> indicate that the map contains no mapping for the key:
	 * it is also possible that the map explicitly maps the key to {@code null}. The {@link #containsKey(Object)
	 * containsKey(key)} operation may be used to distinguish these two cases.
	 *
	 * @param key
	 *            the key whose associated value is to be returned.
	 * @return the value to which the specified key is mapped, or {@code null} if this map contains no mapping for the
	 *         key.
	 * @throws NullPointerException
	 *             if the specified key is {@code null}.
	 */
	public V get(@NonNull Object key) {
		Object[] keysValues = this.keysValues;
		int index = findExactIndex(keysValues, key);
		if (index == -1) {
			return null;
		} else {
			V value = getValue(keysValues, index);
			return value;
		}
	}

	/**
	 * Returns the hash code value for this map. The hash code of a map is defined to be the sum of the hash codes of
	 * each entry (key-value mapping) in the map. This ensures that {@code m1.equals(m2)} implies that
	 * {@code m1.hashCode()==m2.hashCode()} for any two maps {@code m1} and {@code m2}, as required by the general
	 * contract of {@link Object#hashCode}.
	 *
	 * @return the hash code value for this map.
	 * @see Object#equals(Object)
	 * @see #equals(Object)
	 */
	@Override
	public int hashCode() {
		int hashCode = 0;
		Object[] keysValues = this.keysValues;
		int size = keysValues.length / 2;
		for (int i = 0; i < size; i++) {
			hashCode += getWrappedKeyHashCode(keysValues[i]);
		}
		for (int i = size; i < size * 2; i++) {
			Object object = keysValues[i];
			hashCode += object != null ? object.hashCode() : 0;
		}
		return hashCode;
	}

	/**
	 * Returns {@code true} if this map contains no key-value mappings.
	 *
	 * @return {@code true} if this map contains no key-value mappings
	 */
	public boolean isEmpty() {
		return this.keysValues.length == 0;
	}

	/**
	 * Returns an unmodifiable {@link Set} view of the keys contained in this map. The set is backed by the map, so
	 * changes to the map are reflected in the set. If the map is modified while an iteration over the set is in
	 * progress, the results of the iteration are undefined. The set cannot be modified and attempts to modify the
	 * returned collection, whether direct or via its iterator, result in an {@code UnsupportedOperationException}.
	 *
	 * @return a set view of the keys contained in this map.
	 */
	@NonNull
	public Set<K> keySet() {
		return new PackedMapKeySet(this);
	}

	class PackedMapKeySet implements Set<K> {

		final AbstractPackedMap<K, V> map;

		public PackedMapKeySet(AbstractPackedMap<K, V> map) {
			this.map = map;
		}

		@Override
		public boolean add(Object e) {
			throw new UnsupportedOperationException();
		}

		@Override
		public boolean addAll(Collection<? extends K> c) {
			throw new UnsupportedOperationException();
		}

		@Override
		public void clear() {
			throw new UnsupportedOperationException();
		}

		@Override
		public boolean contains(Object o) {
			return AbstractPackedMap.this.containsKey(o);
		}

		@Override
		public boolean containsAll(Collection<?> c) {
			for (Object object : c) {
				if (!this.map.containsKey(object)) {
					return false;
				}
			}
			return true;
		}

		@SuppressWarnings("rawtypes")
		@Override
		public boolean equals(Object obj) {
			if (obj == this) {
				return true;
			}
			if (obj == null || !(obj instanceof AbstractPackedMap.PackedMapKeySet)) {
				return false;
			}
			return this.map.equals(((AbstractPackedMap.PackedMapKeySet) obj).map);
		}

		@Override
		public int hashCode() {
			int hashCode = 0;
			Object[] keysValues = AbstractPackedMap.this.keysValues;
			int keysLength = keysValues.length / 2;
			for (int i = -1; ++i < keysLength;) {
				hashCode += getWrappedKeyHashCode(keysValues[i]);
			}
			return hashCode;
		}

		@Override
		public boolean isEmpty() {
			return AbstractPackedMap.this.isEmpty();
		}

		@Override
		public Iterator<K> iterator() {
			return new Iterator<K>() {
				int cursor = 0;
				Object[] keysValues = PackedMapKeySet.this.map.keysValues;

				@Override
				public boolean hasNext() {
					return this.cursor != this.keysValues.length / 2;
				}

				@Override
				public K next() {
					int i = this.cursor;
					int keysValuesLength = this.keysValues.length / 2;
					if (i < keysValuesLength) {
						K next = unwrapKey(this.keysValues[i]);
						this.cursor = i + 1;
						return next;
					} else {
						throw new NoSuchElementException();
					}
				}

				@Override
				public void remove() {
					throw new UnsupportedOperationException();
				}

			};
		}

		@Override
		public boolean remove(Object o) {
			throw new UnsupportedOperationException();
		}

		@Override
		public boolean removeAll(Collection<?> c) {
			throw new UnsupportedOperationException();
		}

		@Override
		public boolean retainAll(Collection<?> c) {
			throw new UnsupportedOperationException();
		}

		@Override
		public int size() {
			return AbstractPackedMap.this.size();
		}

		@Override
		public Object[] toArray() {
			Object[] keysValues = this.map.keysValues;
			int size = keysValues.length / 2;
			return ArrayTools.copy(keysValues, size - 1);
		}

		@Override
		public <T> T[] toArray(T[] a) {
			Object[] keysValues = this.map.keysValues;
			int size = keysValues.length / 2;
			T[] result;
			if (a.length <= size) {
				result = a;
			} else {
				result = ArrayTools.createNewArray(a, size);
			}
			System.arraycopy(keysValues, 0, result, 0, size);
			return result;
		}

	}

	/**
	 * Associates the specified value with the specified key in this map. If the map previously contained a mapping for
	 * the key, the old value is replaced by the specified value. (A map {@code m} is said to contain a mapping for a
	 * key {@code k} if and only if {@link #containsKey(Object) m.containsKey(k)} would return {@code true}.)
	 *
	 * @param key
	 *            key with which the specified value is to be associated.
	 * @param value
	 *            value to be associated with the specified key.
	 * @return the previous value associated with {@code key}, or {@code null} if there was no mapping for {@code key}.
	 *         (A {@code null} return can also indicate that the map previously associated {@code null} with
	 *         {@code key}.)
	 * @throws NullPointerException
	 *             if the specified key is {@code null}.
	 */
	public V put(@NonNull K key, V value) {
		int hashCode = getKeyHashCode(key);

		int minIndex = 0;
		Object[] keysValues = this.keysValues;
		int keysLength = keysValues.length / 2;
		if (keysLength == 0) {
			this.keysValues = insertAt(keysValues, 0, key, value);
			return null;
		}
		int maxIndex = keysLength - 1;
		while (minIndex <= maxIndex) {
			int currentIndex = (maxIndex - minIndex) / 2 + minIndex;
			int candidateHashCode = getWrappedKeyHashCode(keysValues[currentIndex]);
			if (hashCode == candidateHashCode) {
				int index = linearSearchSameHashCode(keysValues, key, hashCode, currentIndex);
				if (index != -1) {
					return replaceAt(keysValues, index, value);
				} else {
					minIndex = currentIndex;
					break;
				}
			} else if (hashCode > candidateHashCode) {
				minIndex = currentIndex + 1;
			} else {
				maxIndex = currentIndex - 1;
			}
		}

		this.keysValues = insertAt(keysValues, minIndex, key, value);

		return null;
	}

	@NonNull
	private Object[] insertAt(@NonNull Object[] keysValues, int index, @NonNull K key, V value) {
		int arrayLength = keysValues.length;
		Object[] newArray = new Object[arrayLength + 2];
		newArray[index] = wrapKey(key);
		int valueIndex = getValueIndex(newArray, index);
		newArray[valueIndex] = value;
		System.arraycopy(keysValues, 0, newArray, 0, index);
		System.arraycopy(keysValues, index, newArray, index + 1, valueIndex - index - 1);
		System.arraycopy(keysValues, valueIndex - 1, newArray, valueIndex + 1, arrayLength - valueIndex + 1);
		return newArray;
	}

	private V replaceAt(@NonNull Object[] keysValues, int index, V value) {
		int valueIndex = getValueIndex(keysValues, index);
		@SuppressWarnings("unchecked")
		V oldValue = (V) keysValues[valueIndex];
		keysValues[valueIndex] = value;
		return oldValue;
	}

	/**
	 * Gets the hash code of a key.
	 * <p>
	 * By default, returns the hash code of the given object.
	 *
	 * @param key
	 *            the key.
	 * @return the hash code.
	 */
	protected int getKeyHashCode(@NonNull Object key) {
		return key.hashCode();
	}

	/**
	 * Gets the hash code of a key stored in the packed map. The given object may not be the actual key because it has
	 * been wrapped by {@link #wrapKey(Object)}.
	 * <p>
	 * By default, the given parameter is unwrapped using {@link #unwrapKey(Object)} then the hash code is computed
	 * using {@link #getKeyHashCode(Object)}.
	 *
	 * @param wrappedKey
	 *            the wrapped key.
	 * @return the hash code.
	 */
	protected int getWrappedKeyHashCode(@NonNull Object wrappedKey) {
		return getKeyHashCode(unwrapKey(wrappedKey));
	}

	/**
	 * Wraps a key. The result of this method will be stored in the packed map.
	 * <p>
	 * By default, the key is returned.
	 *
	 * @param key
	 *            the key to wrap.
	 * @return the wrapped key.
	 */
	@NonNull
	protected Object wrapKey(@NonNull K key) {
		return key;
	}

	/**
	 * Unwraps a wrapped key. The given wrapper is an object stored in the packed map (see {@link #wrapKey(Object)}).
	 * The result is the key contained by this wrapper.
	 * <p>
	 * By default, the given object is returned (casted in the right type).
	 * <p>
	 * Beware that the returned key may be <code>null</code>, for instance if the key is wrapped in a weak reference. In
	 * this case, to avoid throwing {@link NullPointerException}, the subclass must at least check the <code>null</code>
	 * parameters in {@link #isSame(Object, Object)}, {@link #containsKey(Object)} and {@link #getKeyHashCode(Object)}.
	 *
	 * @param wrappedKey
	 *            the object to unwrap.
	 * @return the key.
	 */
	@SuppressWarnings("unchecked")
	protected K unwrapKey(@NonNull Object wrappedKey) {
		return (K) wrappedKey;
	}

	/**
	 * Removes the mapping for a key from this map if it is present. More formally, if this map contains a mapping for a
	 * key that is the same as the given key (see {@link #isSame(Object, Object)}), that mapping is removed. (The map
	 * can contain at most one such mapping.)
	 *
	 * <p>
	 * Returns the value to which this map previously associated the key, or {@code null} if the map contained no
	 * mapping for the key.
	 *
	 * <p>
	 * A return value of {@code null} does not <i>necessarily</i> indicate that the map contained no mapping for the key
	 * it's also possible that the map explicitly mapped the key to {@code null}.
	 *
	 * <p>
	 * The map will not contain a mapping for the specified key once the call returns.
	 *
	 * @param key
	 *            key whose mapping is to be removed from the map.
	 * @return the previous value associated with {@code key}, or {@code null} if there was no mapping for {@code key}.
	 * @throws NullPointerException
	 *             if the specified key is {@code null}.
	 */
	public V remove(@NonNull Object key) {
		Object[] keysValues = this.keysValues;
		int index = findExactIndex(keysValues, key);
		if (index == -1) {
			return null;
		} else {
			int valueIndex = getValueIndex(keysValues, index);
			@SuppressWarnings("unchecked")
			V result = (V) keysValues[valueIndex];
			int arrayLength = keysValues.length;
			Object[] newArray = new Object[arrayLength - 2];
			System.arraycopy(keysValues, 0, newArray, 0, index);
			System.arraycopy(keysValues, index + 1, newArray, index, valueIndex - index - 1);
			System.arraycopy(keysValues, valueIndex + 1, newArray, valueIndex - 1, arrayLength - valueIndex - 1);
			this.keysValues = newArray;
			return result;
		}
	}

	/**
	 * Returns the number of key-value mappings in this map. If the map contains more than {@code Integer.MAX_VALUE}
	 * elements, returns {@code Integer.MAX_VALUE}.
	 *
	 * @return the number of key-value mappings in this map
	 */
	public int size() {
		return this.keysValues.length / 2;
	}

	/**
	 * Returns an unmodifiable {@link Collection} view of the values contained in this map. The collection is backed by
	 * the map, so changes to the map are reflected in the collection. If the map is modified while an iteration over
	 * the collection is in progress, the results of the iteration are undefined. The collection cannot be modified and
	 * attempts to modify the returned collection, whether direct or via its iterator, result in an
	 * {@code UnsupportedOperationException}.
	 *
	 * @return a collection view of the values contained in this map
	 */
	@NonNull
	public Collection<V> values() {
		return new PackedMapValues(this);
	}

	class PackedMapValues implements Collection<V> {

		final AbstractPackedMap<K, V> map;

		public PackedMapValues(AbstractPackedMap<K, V> map) {
			this.map = map;
		}

		@Override
		public boolean add(Object e) {
			throw new UnsupportedOperationException();
		}

		@Override
		public boolean addAll(Collection<? extends V> c) {
			throw new UnsupportedOperationException();
		}

		@Override
		public void clear() {
			throw new UnsupportedOperationException();
		}

		@Override
		public boolean contains(Object o) {
			return AbstractPackedMap.this.containsValue(o);
		}

		@Override
		public boolean containsAll(Collection<?> c) {
			for (Object object : c) {
				if (!this.map.containsValue(object)) {
					return false;
				}
			}
			return true;
		}

		@SuppressWarnings("rawtypes")
		@Override
		public boolean equals(Object obj) {
			if (obj == this) {
				return true;
			}
			if (obj == null || !(obj instanceof AbstractPackedMap.PackedMapValues)) {
				return false;
			}
			return this.map.equals(((AbstractPackedMap.PackedMapValues) obj).map);
		}

		@Override
		public int hashCode() {
			int hashCode = 0;
			Object[] keysValues = AbstractPackedMap.this.keysValues;
			int keysValuesLength = keysValues.length;
			int keysLength = keysValuesLength / 2;
			for (int i = keysLength - 1; ++i < keysValuesLength;) {
				Object value = keysValues[i];
				hashCode += value == null ? 0 : value.hashCode();
			}
			return hashCode;
		}

		@Override
		public boolean isEmpty() {
			return AbstractPackedMap.this.isEmpty();
		}

		@Override
		public Iterator<V> iterator() {
			return new Iterator<V>() {
				int cursor = PackedMapValues.this.map.keysValues.length / 2;
				Object[] keysValues = PackedMapValues.this.map.keysValues;

				@Override
				public boolean hasNext() {
					return this.cursor != this.keysValues.length;
				}

				@Override
				public V next() {
					int i = this.cursor;
					int keysValuesLength = this.keysValues.length;
					if (i < keysValuesLength) {
						@SuppressWarnings("unchecked")
						V next = (V) this.keysValues[i];
						this.cursor = i + 1;
						return next;
					} else {
						throw new NoSuchElementException();
					}
				}

				@Override
				public void remove() {
					throw new UnsupportedOperationException();
				}

			};
		}

		@Override
		public boolean remove(Object o) {
			throw new UnsupportedOperationException();
		}

		@Override
		public boolean removeAll(Collection<?> c) {
			throw new UnsupportedOperationException();
		}

		@Override
		public boolean retainAll(Collection<?> c) {
			throw new UnsupportedOperationException();
		}

		@Override
		public int size() {
			return AbstractPackedMap.this.size();
		}

		@Override
		public Object[] toArray() {
			Object[] keysValues = this.map.keysValues;
			int size = keysValues.length / 2;
			Object[] result = new Object[size];
			System.arraycopy(keysValues, size, result, 0, size);
			return result;
		}

		@Override
		public <T> T[] toArray(T[] a) {
			Object[] keysValues = this.map.keysValues;
			int size = keysValues.length / 2;
			T[] result;
			if (a.length <= size) {
				result = a;
			} else {
				result = ArrayTools.createNewArray(a, size);
			}
			System.arraycopy(keysValues, size, result, 0, size);
			return result;
		}

	}

	private static <V> V getValue(Object[] keysValues, int i) {
		@SuppressWarnings("unchecked")
		V value = (V) keysValues[getValueIndex(keysValues, i)];
		return value;
	}

	/**
	 * Gets the index of the value in {@link #keysValues} matching the key at the given index.
	 *
	 * @param i
	 *            the index of the key.
	 * @return the index of the value.
	 * @see #keysValues
	 */
	private static int getValueIndex(Object[] keysValues, int i) {
		return (keysValues.length / 2) + i;
	}

	private int findExactIndex(Object[] keysValues, Object key) {
		int hashCode = getKeyHashCode(key);

		int keysLength = keysValues.length / 2;
		if (keysLength == 0) {
			return -1;
		}

		int minIndex = 0;
		int maxIndex = keysLength - 1;
		while (minIndex <= maxIndex) {
			int currentIndex = (maxIndex - minIndex) / 2 + minIndex;
			int candidateHashCode = getWrappedKeyHashCode(keysValues[currentIndex]);
			if (candidateHashCode == hashCode) {
				return linearSearchSameHashCode(keysValues, key, hashCode, currentIndex);
			} else if (hashCode > candidateHashCode) {
				minIndex = currentIndex + 1;
			} else {
				maxIndex = currentIndex - 1;
			}
		}
		return -1;
	}

	private int linearSearchSameHashCode(Object[] keysValues, Object key, int hashCode, int fromIndex) {
		int keysLength = keysValues.length / 2;
		int index = fromIndex;
		Object candidateKey = keysValues[index];
		do {
			if (isSame(key, unwrapKey(candidateKey))) {
				return index;
			}
			if (index == 0) {
				break;
			}
			candidateKey = keysValues[--index];
		} while (getWrappedKeyHashCode(candidateKey) == hashCode);
		index = fromIndex + 1;
		while (index < keysLength) {
			candidateKey = keysValues[index];
			if (getWrappedKeyHashCode(candidateKey) != hashCode) {
				break;
			}
			if (isSame(key, unwrapKey(candidateKey))) {
				return index;
			}
			++index;
		}
		return -1;
	}

	/**
	 * Checks whether two keys are equal or not. The key must not be <code>null</code>.
	 *
	 * @param key
	 *            the key searched in the map.
	 * @param candidateKey
	 *            the key in the map to compare with.
	 * @return {@code true} if the two keys are equal, {@code false} otherwise.
	 */
	protected abstract boolean isSame(@NonNull Object key, Object candidateKey);

}