//@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.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Map;
import java.util.Map.Entry;

/*
 * @auther JOJO
 */
public class SortedIntArrayListMap<V>
{
	private int[] _keys;
	private ArrayList<V> _values;
	
	public SortedIntArrayListMap()
	{
		this(INT_EMPTY, new ArrayList<V>());
	}
	
	public SortedIntArrayListMap(int[] keys, ArrayList<V> values)
	{
		_keys = keys;
		_values = values;
		sort();
	}
	
	public SortedIntArrayListMap(int[] keys, V[] values)
	{
		int length = keys.length;
		_keys = keys;
		_values = new ArrayList<V>(length);
		for (int index = 0; index < length; ++index)
			_values.add(values[index]);
		sort();
	}
	
	public SortedIntArrayListMap(Map<Integer, V> t)
	{
		int length = t.size();
		int[] tmpKeys = new int[length];
		ArrayList<V> tmpValues = new ArrayList<V>(length);
		int index = 0;
		for (Entry<Integer, V> e : t.entrySet())
		{
			tmpKeys[index] = e.getKey();
			tmpValues.add(index, e.getValue());
			++index;
		}
		_keys = tmpKeys;
		_values = tmpValues;
		sort();
	}
	
	public void clear()
	{
		_keys = INT_EMPTY;
		_values.clear();
	}
	
	public boolean containsKey(int key)
	{
		return Arrays.binarySearch(_keys, key) >= 0;
	}
	
	public boolean containsValue(V value)
	{
		return _values.contains(value);
	}
	
	public V get(int key)
	{
		return get(key, null);
	}
	
	public V get(int key, V defaultValue)
	{
		int i = Arrays.binarySearch(_keys, key);
		if (i >= 0)
			return _values.get(i);
		else
			return defaultValue;
	}
	
	public boolean isEmpty()
	{
		return _keys.length == 0;
	}
	
	public int[] keySet()
	{
		return _keys;
	}
	
	public int[] keys()
	{
		return _keys;
	}
	
	public V put(int key, V value)
	{
		int index = Arrays.binarySearch(_keys, key);
		if (index >= 0)
			return _values.set(index, value);
		else
			return insertEntry(-(index + 1), key, value);
	}
	
	public V putIfAbsent(int key, V value)
	{
		int index = Arrays.binarySearch(_keys, key);
		if (index >= 0)
			return _values.get(index);
		else
			return insertEntry(-(index + 1), key, value);
	}
	
	public void putAll(Map<Integer, V> t)
	{
		for (Entry<Integer, V> e : t.entrySet())
			put(e.getKey(), e.getValue());
	}
	
	public V remove(int key)
	{
		int index = Arrays.binarySearch(_keys, key);
		if (index >= 0)
			return deleteEntry(index);
		else
			return null;
	}
	
	public int size()
	{
		return _keys.length;
	}
	
	public ArrayList<V> values()
	{
		return _values;
	}
	
	public SortedIntArrayListMap<V> append(int 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;
		int[] tmpKeys = new int[length];
		if (index > 0)
			System.arraycopy(_keys, 0, tmpKeys, 0, index);
		int n;
		if ((n = length - index) > 0)
			System.arraycopy(_keys, index + 1, tmpKeys, index, n);
		_keys = tmpKeys;
		return _values.remove(index);
	}
	
	public int indexOf(int key)
	{
		return Arrays.binarySearch(_keys, key);
	}
	
	private V insertEntry(int index, int key, V value)
	{
		final int length = _keys.length;
		int[] tmpKeys = new int[length + 1];
		if (index > 0)
			System.arraycopy(_keys, 0, tmpKeys, 0, index);
		tmpKeys[index] = key;
		int n;
		if ((n = length - index) > 0)
			System.arraycopy(_keys, index, tmpKeys, index + 1, n);
		_keys = tmpKeys;
		_values.add(index, value);
		return null;
	}
	
	public int keyAt(int index)
	{
		return _keys[index];
	}
	
	public V valueAt(int index)
	{
		return _values.get(index);
	}
	
	public int getKey(int index)
	{
		return keyAt(index);
	}
	
	public V getValue(int index)
	{
		return valueAt(index);
	}
	
	public V setValue(int index, V value)
	{
		return _values.set(index, value);
	}
	
	public void fill(V value)
	{
		Collections.fill(_values, value);
	}
	
	public void sort()
	{
		sort(0, _keys.length - 1);
	}
	
	private void sort(int left, int right)
	{
		if (left >= right) return;
		int 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;
			int key = _keys[i]; _keys[i] = _keys[j]; _keys[j] = key;
			V value = _values.get(i); _values.set(i, _values.get(j)); _values.set(j, value);
			++i;
			--j;
		}
		sort(left,  i - 1);
		sort(j + 1, right);
	}
}
