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