//@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 SortedLongLongArrayMap
{
	private long[] _keys;
	private long[] _values;
	public final long NULL;
	
	public SortedLongLongArrayMap()
	{
		this(LONG_NULL);
	}
	
	public SortedLongLongArrayMap(long nullValue)
	{
		this(nullValue, LONG_EMPTY, LONG_EMPTY);
	}
	
	public SortedLongLongArrayMap(long[] keys, long[] values)
	{
		this(LONG_NULL, keys, values);
	}
	
	public SortedLongLongArrayMap(long nullValue, long[] keys, long[] values)
	{
		NULL = nullValue;
		_keys = keys;
		_values = values;
		sort();
	}
	
	public SortedLongLongArrayMap(Map<Long, Long> t)
	{
		this(LONG_NULL, t);
	}
	
	public SortedLongLongArrayMap(long nullValue, Map<Long, Long> t)
	{
		NULL = nullValue;
		int length = t.size();
		long[] _keys = new long[length];
		long[] _values = new long[length];
		
		Long w;
		int index = 0;
		for (Entry<Long, Long> e : t.entrySet())
		{
			_keys[index] = e.getKey();
			_values[index] = (w = e.getValue()) == null ? NULL : w;
			++index;
		}
		sort();
	}
	
	public void clear()
	{
		_keys = LONG_EMPTY;
		_values = LONG_EMPTY;
	}
	
	public boolean containsKey(long key)
	{
		return Arrays.binarySearch(_keys, key) >= 0;
	}
	
	public boolean containsValue(long value)
	{
		for (int i = 0, length = _values.length; i < length; ++i)
			if (_values[i] == value)
				return true;
		return false;
	}
	
	public long get(long key)
	{
		return get(key, NULL);
	}
	
	public long get(long key, long 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 long put(long key, long value)
	{
		int index = Arrays.binarySearch(_keys, key);
		if (index >= 0) {
			long prev = _values[index];
			_values[index] = value;
			return prev;
		} else {
			return insertEntry(-(index + 1), key, value);
		}
	}
	
	public long putIfAbsent(long key, long 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, Long> t)
	{
		for (Entry<Long, Long> e : t.entrySet())
			put(e.getKey(), e.getValue());
	}
	
	public long 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 long[] values()
	{
		return _values;
	}
	
	public SortedLongLongArrayMap append(long key, long value)
	{
		long prev = put(key, value);
		if (prev != NULL) throw new RuntimeException("Duplicate key:" + key + " value:" + value + " previus:" + prev);
		return this;
	}
	
	private long deleteEntry(int index)
	{
		final int length = _keys.length - 1;
		if (length < 0)
			return NULL;
		long[] tmpKeys = new long[length];
		long[] tmpValues = new long[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);
		}
		long prev = _values[index];
		_keys = tmpKeys;
		_values = tmpValues;
		return prev;
	}
	
	public int indexOf(long key)
	{
		return Arrays.binarySearch(_keys, key);
	}
	
	private long insertEntry(int index, long key, long value)
	{
		final int length = _keys.length;
		long[] tmpKeys = new long[length + 1];
		long[] tmpValues = new long[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 long valueAt(int index)
	{
		return _values[index];
	}
	
	public long getKey(int index)
	{
		return keyAt(index);
	}
	
	public long getValue(int index)
	{
		return valueAt(index);
	}
	
	public long setValue(int index, long value)
	{
		long prev = _values[index];
		_values[index] = value;
		return prev;
	}
	
	public void fill(long 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;
			long value = _values[i]; _values[i] = _values[j]; _values[j] = value;
			++i;
			--j;
		}
		sort(left,  i - 1);
		sort(j + 1, right);
	}
}
