/**
 * Copyright 2010-2013 Jingjing Li.
 *
 * This file is part of jplot2d.
 *
 * jplot2d is free software: you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or any later version.
 *
 * jplot2d is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Lesser Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with jplot2d. If not, see .
 */
package org.jplot2d.util;

/**
 * SparseArrays map integers to Objects. Unlike a normal array of Objects, there can be gaps in the indices. It is
 * intended to be more efficient than using a HashMap to map Integers to Objects.
 */
public class SparseArray implements Cloneable {

	private static final Object DELETED = new Object();
	private boolean mGarbage = false;

	private int[] mKeys;
	private Object[] mValues;
	private int mSize;

	/**
	 * Creates a new SparseArray containing no mappings.
	 */
	public SparseArray() {
		this(10);
	}

	/**
	 * Creates a new SparseArray containing no mappings that will not require any additional memory allocation to store
	 * the specified number of mappings.
	 */
	public SparseArray(int initialCapacity) {
		initialCapacity = idealIntArraySize(initialCapacity);

		mKeys = new int[initialCapacity];
		mValues = new Object[initialCapacity];
		mSize = 0;
	}

	protected SparseArray(SparseArray sa) {
		mSize = sa.mSize;
		mGarbage = sa.mGarbage;
		mKeys = mKeys.clone();
		mValues = mValues.clone();
	}

	public SparseArray copy() {
		return new SparseArray(this);
	}

	/**
	 * Gets the Object mapped from the specified key, or null if no such mapping has been made.
	 */
	@SuppressWarnings("unchecked")
	public E get(int key) {
		int i = binarySearch(mKeys, 0, mSize, key);

		if (i < 0 || mValues[i] == DELETED) {
			return null;
		} else {
			return (E) mValues[i];
		}
	}

	/**
	 * Removes the mapping from the specified key, if there was any.
	 */
	public void remove(int key) {
		int i = binarySearch(mKeys, 0, mSize, key);

		if (i >= 0) {
			if (mValues[i] != DELETED) {
				mValues[i] = DELETED;
				mGarbage = true;
			}
		}
	}

	private void gc() {
		int n = mSize;
		int o = 0;
		int[] keys = mKeys;
		Object[] values = mValues;

		for (int i = 0; i < n; i++) {
			Object val = values[i];

			if (val != DELETED) {
				if (i != o) {
					keys[o] = keys[i];
					values[o] = val;
					values[i] = null;
				}

				o++;
			}
		}

		mGarbage = false;
		mSize = o;
	}

	/**
	 * Adds a mapping from the specified key to the specified value, replacing the previous mapping from the specified
	 * key if there was one.
	 */
	public void put(int key, E value) {
		int i = binarySearch(mKeys, 0, mSize, key);

		if (i >= 0) {
			mValues[i] = value;
		} else {
			i = ~i;

			if (i < mSize && mValues[i] == DELETED) {
				mKeys[i] = key;
				mValues[i] = value;
				return;
			}

			if (mGarbage && mSize >= mKeys.length) {
				gc();

				// Search again because indices may have changed.
				i = ~binarySearch(mKeys, 0, mSize, key);
			}

			if (mSize >= mKeys.length) {
				int n = idealIntArraySize(mSize + 1);

				int[] nkeys = new int[n];
				Object[] nvalues = new Object[n];

				// Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
				System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
				System.arraycopy(mValues, 0, nvalues, 0, mValues.length);

				mKeys = nkeys;
				mValues = nvalues;
			}

			if (mSize - i != 0) {
				// Log.e("SparseArray", "move " + (mSize - i));
				System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
				System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
			}

			mKeys[i] = key;
			mValues[i] = value;
			mSize++;
		}
	}

	/**
	 * Returns the number of key-value mappings that this SparseArray currently stores.
	 */
	public int size() {
		if (mGarbage) {
			gc();
		}

		return mSize;
	}

	/**
	 * Removes all key-value mappings from this SparseArray.
	 */
	public void clear() {
		int n = mSize;
		Object[] values = mValues;

		for (int i = 0; i < n; i++) {
			values[i] = null;
		}

		mSize = 0;
		mGarbage = false;
	}

	private static int binarySearch(int[] a, int start, int len, int key) {
		int high = start + len, low = start - 1, guess;

		while (high - low > 1) {
			guess = (high + low) / 2;

			if (a[guess] < key)
				low = guess;
			else
				high = guess;
		}

		if (high == start + len)
			return ~(start + len);
		else if (a[high] == key)
			return high;
		else
			return ~high;
	}

	private static int idealIntArraySize(int need) {
		for (int i = 4; i < 32; i++) {
			if (need <= (1 << i) - 3) {
				return (1 << i) - 3;
			}
		}
		return need;
	}

}