/**
 *   Copyright (c) Rich Hickey. All rights reserved.
 *   The use and distribution terms for this software are covered by the
 *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
 *   which can be found in the file epl-v10.html at the root of this distribution.
 *   By using this software in any fashion, you are agreeing to be bound by
 * 	 the terms of this license.
 *   You must not remove this notice, or any other, from this software.
 **/

package clojure.lang;

import java.io.Serializable;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Map;

/**
 * Simple implementation of persistent map on an array
 * <p/>
 * Note that instances of this class are constant values
 * i.e. add/remove etc return new values
 * <p/>
 * Copies array on every change, so only appropriate for _very_small_ maps
 * <p/>
 * null keys and values are ok, but you won't be able to distinguish a null value via valAt - use contains/entryAt
 */

public class PersistentArrayMap extends APersistentMap implements IObj, IEditableCollection {

final Object[] array;
static final int HASHTABLE_THRESHOLD = 16;

public static final PersistentArrayMap EMPTY = new PersistentArrayMap();
private final IPersistentMap _meta;

static public IPersistentMap create(Map other){
	ITransientMap ret = EMPTY.asTransient();
	for(Object o : other.entrySet())
		{
		Map.Entry e = (Entry) o;
		ret = ret.assoc(e.getKey(), e.getValue());
		}
	return ret.persistent();
}

protected PersistentArrayMap(){
	this.array = new Object[]{};
	this._meta = null;
}

public PersistentArrayMap withMeta(IPersistentMap meta){
	return new PersistentArrayMap(meta, array);
}

PersistentArrayMap create(Object... init){
	return new PersistentArrayMap(meta(), init);
}

IPersistentMap createHT(Object[] init){
	return PersistentHashMap.create(meta(), init);
}

static public PersistentArrayMap createWithCheck(Object[] init){
	for(int i=0;i< init.length;i += 2)
		{
		for(int j=i+2;j<init.length;j += 2)
			{
			if(equalKey(init[i],init[j]))
				throw new IllegalArgumentException("Duplicate key: " + init[i]);
			}
		}
	return new PersistentArrayMap(init);
}
/**
 * This ctor captures/aliases the passed array, so do not modify later
 *
 * @param init {key1,val1,key2,val2,...}
 */
public PersistentArrayMap(Object[] init){
	this.array = init;
	this._meta = null;
}


public PersistentArrayMap(IPersistentMap meta, Object[] init){
	this._meta = meta;
	this.array = init;
}

public int count(){
	return array.length / 2;
}

public boolean containsKey(Object key){
	return indexOf(key) >= 0;
}

public IMapEntry entryAt(Object key){
	int i = indexOf(key);
	if(i >= 0)
		return new MapEntry(array[i],array[i+1]);
	return null;
}

public IPersistentMap assocEx(Object key, Object val) throws Exception{
	int i = indexOf(key);
	Object[] newArray;
	if(i >= 0)
		{
		throw new Exception("Key already present");
		}
	else //didn't have key, grow
		{
		if(array.length > HASHTABLE_THRESHOLD)
			return createHT(array).assocEx(key, val);
		newArray = new Object[array.length + 2];
		if(array.length > 0)
			System.arraycopy(array, 0, newArray, 2, array.length);
		newArray[0] = key;
		newArray[1] = val;
		}
	return create(newArray);
}

public IPersistentMap assoc(Object key, Object val){
	int i = indexOf(key);
	Object[] newArray;
	if(i >= 0) //already have key, same-sized replacement
		{
		if(array[i + 1] == val) //no change, no op
			return this;
		newArray = array.clone();
		newArray[i + 1] = val;
		}
	else //didn't have key, grow
		{
		if(array.length > HASHTABLE_THRESHOLD)
			return createHT(array).assoc(key, val);
		newArray = new Object[array.length + 2];
		if(array.length > 0)
			System.arraycopy(array, 0, newArray, 2, array.length);
		newArray[0] = key;
		newArray[1] = val;
		}
	return create(newArray);
}

public IPersistentMap without(Object key){
	int i = indexOf(key);
	if(i >= 0) //have key, will remove
		{
		int newlen = array.length - 2;
		if(newlen == 0)
			return empty();
		Object[] newArray = new Object[newlen];
		for(int s = 0, d = 0; s < array.length; s += 2)
			{
			if(!equalKey(array[s], key)) //skip removal key
				{
				newArray[d] = array[s];
				newArray[d + 1] = array[s + 1];
				d += 2;
				}
			}
		return create(newArray);
		}
	//don't have key, no op
	return this;
}

public IPersistentMap empty(){
	return (IPersistentMap) EMPTY.withMeta(meta());
}

final public Object valAt(Object key, Object notFound){
	int i = indexOf(key);
	if(i >= 0)
		return array[i + 1];
	return notFound;
}

public Object valAt(Object key){
	return valAt(key, null);
}

public int capacity(){
	return count();
}

private int indexOf(Object key){
	for(int i = 0; i < array.length; i += 2)
		{
		if(equalKey(array[i], key))
			return i;
		}
	return -1;
}

static boolean equalKey(Object k1, Object k2){
	if(k1 == null)
		return k2 == null;
	return k1.equals(k2);
}

public Iterator iterator(){
	return new Iter(array);
}

public ISeq seq(){
	if(array.length > 0)
		return new Seq(array, 0);
	return null;
}

public IPersistentMap meta(){
	return _meta;
}

static class Seq extends ASeq implements Counted{
	final Object[] array;
	final int i;

	Seq(Object[] array, int i){
		this.array = array;
		this.i = i;
	}

	public Seq(IPersistentMap meta, Object[] array, int i){
		super(meta);
		this.array = array;
		this.i = i;
	}

	public Object first(){
		return new MapEntry(array[i],array[i+1]);
	}

	public ISeq next(){
		if(i + 2 < array.length)
			return new Seq(array, i + 2);
		return null;
	}

	public int count(){
		return (array.length - i) / 2;
	}

	public Obj withMeta(IPersistentMap meta){
		return new Seq(meta, array, i);
	}
}

static class Iter implements Iterator{
	Object[] array;
	int i;

	//for iterator
	Iter(Object[] array){
		this(array, -2);
	}

	//for entryAt
	Iter(Object[] array, int i){
		this.array = array;
		this.i = i;
	}

	public boolean hasNext(){
		return i < array.length - 2;
	}

	public Object next(){
		i += 2;
		return new MapEntry(array[i],array[i+1]);
	}

	public void remove(){
		throw new UnsupportedOperationException();
	}

}

public ITransientMap asTransient(){
	return new TransientArrayMap(array);
}

static final class TransientArrayMap extends ATransientMap {
	int len;
	final Object[] array;
	Thread owner;

	public TransientArrayMap(Object[] array){
		this.owner = Thread.currentThread();
		this.array = new Object[Math.max(HASHTABLE_THRESHOLD, array.length)];
		System.arraycopy(array, 0, this.array, 0, array.length);
		this.len = array.length;
	}
	
	private int indexOf(Object key){
		for(int i = 0; i < len; i += 2)
			{
			if(equalKey(array[i], key))
				return i;
			}
		return -1;
	}

	ITransientMap doAssoc(Object key, Object val){
		int i = indexOf(key);
		if(i >= 0) //already have key,
			{
			if(array[i + 1] != val) //no change, no op
				array[i + 1] = val;
			}
		else //didn't have key, grow
			{
			if(len >= array.length)
				return PersistentHashMap.create(array).asTransient().assoc(key, val);
			array[len++] = key;
			array[len++] = val;
			}
		return this;
	}

	ITransientMap doWithout(Object key) {
		int i = indexOf(key);
		if(i >= 0) //have key, will remove
			{
			if (len >= 2)
				{
					array[i] = array[len - 2];
					array[i + 1] = array[len - 1];
				}
			len -= 2;
			}
		return this;
	}

	Object doValAt(Object key, Object notFound) {
		int i = indexOf(key);
		if (i >= 0)
			return array[i + 1];
		return notFound;
	}

	int doCount() {
		return len / 2;
	}
	
	IPersistentMap doPersistent(){
		ensureEditable();
		owner = null;
		Object[] a = new Object[len];
		System.arraycopy(array,0,a,0,len);
		return new PersistentArrayMap(a);
	}

	void ensureEditable(){
		if(owner == Thread.currentThread())
			return;
		if(owner != null)
			throw new IllegalAccessError("Transient used by non-owner thread");
		throw new IllegalAccessError("Transient used after persistent! call");
	}
}
}