//@formatter:off
/*
 * Auther: tukune
 * 
 * DON'T CODE FORMAT!
 * DON'T CONVERT TAB <---> SPACE
 * DON'T STRIP TRAILING BLANKS FROM END OF LINE
 */
package jp.sf.l2j.arrayMaps;

import static jp.sf.l2j.arrayMaps.SortedArrayMap.*;

import java.util.Arrays;
import java.util.Map;
import java.util.Map.Entry;

/*
 * @auther JOJO
 */
public class SortedLongObjectArrayMap<V>
{
	private long[] _keys;
	private V[] _values;
	
	@SuppressWarnings("unchecked")
	public SortedLongObjectArrayMap(V... values)
	{
		this(LONG_EMPTY, values.length == 0 ? values : Arrays.copyOf(values, 0));
	}
	
	public SortedLongObjectArrayMap(long[] keys, V[] values)
	{
		_keys = keys;
		_values = values;
		sort();
	}
	
	public SortedLongObjectArrayMap(Map<Long, V> t, @SuppressWarnings("unchecked") V... values)
	{
		int length = t.size();
		long[] tmpKeys = new long[length];
		V[] tmpValues = Arrays.copyOf(values, length);
		int index = 0;
		for (Entry<Long, V> e : t.entrySet())
		{
			tmpKeys[index] = e.getKey();
			tmpValues[index] = e.getValue();
			++index;
		}
		_keys = tmpKeys;
		_values = tmpValues;
		sort();
	}
	
	public void clear()
	{
		_keys = LONG_EMPTY;
		_values = Arrays.copyOf(_values, 0);
	}
	
	public boolean containsKey(long key)
	{
		return Arrays.binarySearch(_keys, key) >= 0;
	}
	
	public boolean containsValue(V value)
	{
		for (int i = 0, length = _values.length; i < length; ++i)
			if (_values[i] == value)
				return true;
		return false;
	}
	
	public V get(long key)
	{
		return get(key, null);
	}
	
	public V get(long key, V defaultValue)
	{
		int i = Arrays.binarySearch(_keys, key);
		if (i >= 0)
			return _values[i];
		else
			return defaultValue;
	}
	
	public boolean isEmpty()
	{
		return _keys.length == 0;
	}
	
	public long[] keySet()
	{
		return _keys;
	}
	
	public long[] keys()
	{
		return _keys;
	}
	
	public V put(long key, V value)
	{
		int index = Arrays.binarySearch(_keys, key);
		if (index >= 0) {
			V prev = _values[index];
			_values[index] = value;
			return prev;
		} else {
			return insertEntry(-(index + 1), key, value);
		}
	}
	
	public V putIfAbsent(long key, V value)
	{
		int index = Arrays.binarySearch(_keys, key);
		if (index >= 0)
			return _values[index];
		else
			return insertEntry(-(index + 1), key, value);
	}
	
	public void putAll(Map<Long, V> t)
	{
		for (Entry<Long, V> e : t.entrySet())
			put(e.getKey(), e.getValue());
	}
	
	public V remove(long key)
	{
		int index = Arrays.binarySearch(_keys, key);
		if (index >= 0)
			return deleteEntry(index);
		else
			return null;
	}
	
	public int size()
	{
		return _keys.length;
	}
	
	public V[] values()
	{
		return _values;
	}
	
	public SortedLongObjectArrayMap<V> append(long key, V value)
	{
		V prev = put(key, value);
		if (prev != null) throw new RuntimeException("Duplicate key:" + key + " value:" + value + " previus:" + prev);
		return this;
	}
	
	private V deleteEntry(int index)
	{
		final int length = _keys.length - 1;
		if (length < 0)
			return null;
		long[] tmpKeys = new long[length];
		V[] tmpValues = Arrays.copyOf(_values, length);
		if (index > 0) {
			System.arraycopy(_keys, 0, tmpKeys, 0, index);
			System.arraycopy(_values, 0, tmpValues, 0, index);
		}
		int n;
		if ((n = length - index) > 0) {
			System.arraycopy(_keys, index + 1, tmpKeys, index, n);
			System.arraycopy(_values, index + 1, tmpValues, index, n);
		}
		V prev = _values[index];
		_keys = tmpKeys;
		_values = tmpValues;
		return prev;
	}
	
	public int indexOf(long key)
	{
		return Arrays.binarySearch(_keys, key);
	}
	
	private V insertEntry(int index, long key, V value)
	{
		final int length = _keys.length;
		long[] tmpKeys = new long[length + 1];
		V[] tmpValues = Arrays.copyOf(_values, length + 1);
		if (index > 0) {
			System.arraycopy(_keys, 0, tmpKeys, 0, index);
			System.arraycopy(_values, 0, tmpValues, 0, index);
		}
		tmpKeys[index] = key;
		tmpValues[index] = value;
		int n;
		if ((n = length - index) > 0) {
			System.arraycopy(_keys, index, tmpKeys, index + 1, n);
			System.arraycopy(_values, index, tmpValues, index + 1, n);
		}
		_keys = tmpKeys;
		_values = tmpValues;
		return null;
	}
	
	public long keyAt(int index)
	{
		return _keys[index];
	}
	
	public V valueAt(int index)
	{
		return _values[index];
	}
	
	public long getKey(int index)
	{
		return keyAt(index);
	}
	
	public V getValue(int index)
	{
		return valueAt(index);
	}
	
	public V setValue(int index, V value)
	{
		V prev = _values[index];
		_values[index] = value;
		return prev;
	}
	
	public void fill(V value)
	{
		Arrays.fill(_values, value);
	}
	
	public void sort()
	{
		sort(0, _keys.length - 1);
	}
	
	private void sort(int left, int right)
	{
		if (left >= right) return;
		long pivot = _keys[(left + right) / 2];
		int i = left;
		int j = right;
		for (;;) {
			while (_keys[i] < pivot) ++i;
			while (pivot < _keys[j]) --j;
			if (i >= j) break;
			long key = _keys[i]; _keys[i] = _keys[j]; _keys[j] = key;
			V value = _values[i]; _values[i] = _values[j]; _values[j] = value;
			++i;
			--j;
		}
		sort(left,  i - 1);
		sort(j + 1, right);
	}
}
