1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/clojure/lang/PersistentArrayMap.java	Sat Aug 21 06:25:44 2010 -0400
     1.3 @@ -0,0 +1,367 @@
     1.4 +/**
     1.5 + *   Copyright (c) Rich Hickey. All rights reserved.
     1.6 + *   The use and distribution terms for this software are covered by the
     1.7 + *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
     1.8 + *   which can be found in the file epl-v10.html at the root of this distribution.
     1.9 + *   By using this software in any fashion, you are agreeing to be bound by
    1.10 + * 	 the terms of this license.
    1.11 + *   You must not remove this notice, or any other, from this software.
    1.12 + **/
    1.13 +
    1.14 +package clojure.lang;
    1.15 +
    1.16 +import java.io.Serializable;
    1.17 +import java.util.Arrays;
    1.18 +import java.util.Iterator;
    1.19 +import java.util.Map;
    1.20 +
    1.21 +/**
    1.22 + * Simple implementation of persistent map on an array
    1.23 + * <p/>
    1.24 + * Note that instances of this class are constant values
    1.25 + * i.e. add/remove etc return new values
    1.26 + * <p/>
    1.27 + * Copies array on every change, so only appropriate for _very_small_ maps
    1.28 + * <p/>
    1.29 + * null keys and values are ok, but you won't be able to distinguish a null value via valAt - use contains/entryAt
    1.30 + */
    1.31 +
    1.32 +public class PersistentArrayMap extends APersistentMap implements IObj, IEditableCollection {
    1.33 +
    1.34 +final Object[] array;
    1.35 +static final int HASHTABLE_THRESHOLD = 16;
    1.36 +
    1.37 +public static final PersistentArrayMap EMPTY = new PersistentArrayMap();
    1.38 +private final IPersistentMap _meta;
    1.39 +
    1.40 +static public IPersistentMap create(Map other){
    1.41 +	ITransientMap ret = EMPTY.asTransient();
    1.42 +	for(Object o : other.entrySet())
    1.43 +		{
    1.44 +		Map.Entry e = (Entry) o;
    1.45 +		ret = ret.assoc(e.getKey(), e.getValue());
    1.46 +		}
    1.47 +	return ret.persistent();
    1.48 +}
    1.49 +
    1.50 +protected PersistentArrayMap(){
    1.51 +	this.array = new Object[]{};
    1.52 +	this._meta = null;
    1.53 +}
    1.54 +
    1.55 +public PersistentArrayMap withMeta(IPersistentMap meta){
    1.56 +	return new PersistentArrayMap(meta, array);
    1.57 +}
    1.58 +
    1.59 +PersistentArrayMap create(Object... init){
    1.60 +	return new PersistentArrayMap(meta(), init);
    1.61 +}
    1.62 +
    1.63 +IPersistentMap createHT(Object[] init){
    1.64 +	return PersistentHashMap.create(meta(), init);
    1.65 +}
    1.66 +
    1.67 +static public PersistentArrayMap createWithCheck(Object[] init){
    1.68 +	for(int i=0;i< init.length;i += 2)
    1.69 +		{
    1.70 +		for(int j=i+2;j<init.length;j += 2)
    1.71 +			{
    1.72 +			if(equalKey(init[i],init[j]))
    1.73 +				throw new IllegalArgumentException("Duplicate key: " + init[i]);
    1.74 +			}
    1.75 +		}
    1.76 +	return new PersistentArrayMap(init);
    1.77 +}
    1.78 +/**
    1.79 + * This ctor captures/aliases the passed array, so do not modify later
    1.80 + *
    1.81 + * @param init {key1,val1,key2,val2,...}
    1.82 + */
    1.83 +public PersistentArrayMap(Object[] init){
    1.84 +	this.array = init;
    1.85 +	this._meta = null;
    1.86 +}
    1.87 +
    1.88 +
    1.89 +public PersistentArrayMap(IPersistentMap meta, Object[] init){
    1.90 +	this._meta = meta;
    1.91 +	this.array = init;
    1.92 +}
    1.93 +
    1.94 +public int count(){
    1.95 +	return array.length / 2;
    1.96 +}
    1.97 +
    1.98 +public boolean containsKey(Object key){
    1.99 +	return indexOf(key) >= 0;
   1.100 +}
   1.101 +
   1.102 +public IMapEntry entryAt(Object key){
   1.103 +	int i = indexOf(key);
   1.104 +	if(i >= 0)
   1.105 +		return new MapEntry(array[i],array[i+1]);
   1.106 +	return null;
   1.107 +}
   1.108 +
   1.109 +public IPersistentMap assocEx(Object key, Object val) throws Exception{
   1.110 +	int i = indexOf(key);
   1.111 +	Object[] newArray;
   1.112 +	if(i >= 0)
   1.113 +		{
   1.114 +		throw new Exception("Key already present");
   1.115 +		}
   1.116 +	else //didn't have key, grow
   1.117 +		{
   1.118 +		if(array.length > HASHTABLE_THRESHOLD)
   1.119 +			return createHT(array).assocEx(key, val);
   1.120 +		newArray = new Object[array.length + 2];
   1.121 +		if(array.length > 0)
   1.122 +			System.arraycopy(array, 0, newArray, 2, array.length);
   1.123 +		newArray[0] = key;
   1.124 +		newArray[1] = val;
   1.125 +		}
   1.126 +	return create(newArray);
   1.127 +}
   1.128 +
   1.129 +public IPersistentMap assoc(Object key, Object val){
   1.130 +	int i = indexOf(key);
   1.131 +	Object[] newArray;
   1.132 +	if(i >= 0) //already have key, same-sized replacement
   1.133 +		{
   1.134 +		if(array[i + 1] == val) //no change, no op
   1.135 +			return this;
   1.136 +		newArray = array.clone();
   1.137 +		newArray[i + 1] = val;
   1.138 +		}
   1.139 +	else //didn't have key, grow
   1.140 +		{
   1.141 +		if(array.length > HASHTABLE_THRESHOLD)
   1.142 +			return createHT(array).assoc(key, val);
   1.143 +		newArray = new Object[array.length + 2];
   1.144 +		if(array.length > 0)
   1.145 +			System.arraycopy(array, 0, newArray, 2, array.length);
   1.146 +		newArray[0] = key;
   1.147 +		newArray[1] = val;
   1.148 +		}
   1.149 +	return create(newArray);
   1.150 +}
   1.151 +
   1.152 +public IPersistentMap without(Object key){
   1.153 +	int i = indexOf(key);
   1.154 +	if(i >= 0) //have key, will remove
   1.155 +		{
   1.156 +		int newlen = array.length - 2;
   1.157 +		if(newlen == 0)
   1.158 +			return empty();
   1.159 +		Object[] newArray = new Object[newlen];
   1.160 +		for(int s = 0, d = 0; s < array.length; s += 2)
   1.161 +			{
   1.162 +			if(!equalKey(array[s], key)) //skip removal key
   1.163 +				{
   1.164 +				newArray[d] = array[s];
   1.165 +				newArray[d + 1] = array[s + 1];
   1.166 +				d += 2;
   1.167 +				}
   1.168 +			}
   1.169 +		return create(newArray);
   1.170 +		}
   1.171 +	//don't have key, no op
   1.172 +	return this;
   1.173 +}
   1.174 +
   1.175 +public IPersistentMap empty(){
   1.176 +	return (IPersistentMap) EMPTY.withMeta(meta());
   1.177 +}
   1.178 +
   1.179 +final public Object valAt(Object key, Object notFound){
   1.180 +	int i = indexOf(key);
   1.181 +	if(i >= 0)
   1.182 +		return array[i + 1];
   1.183 +	return notFound;
   1.184 +}
   1.185 +
   1.186 +public Object valAt(Object key){
   1.187 +	return valAt(key, null);
   1.188 +}
   1.189 +
   1.190 +public int capacity(){
   1.191 +	return count();
   1.192 +}
   1.193 +
   1.194 +private int indexOf(Object key){
   1.195 +	for(int i = 0; i < array.length; i += 2)
   1.196 +		{
   1.197 +		if(equalKey(array[i], key))
   1.198 +			return i;
   1.199 +		}
   1.200 +	return -1;
   1.201 +}
   1.202 +
   1.203 +static boolean equalKey(Object k1, Object k2){
   1.204 +	if(k1 == null)
   1.205 +		return k2 == null;
   1.206 +	return k1.equals(k2);
   1.207 +}
   1.208 +
   1.209 +public Iterator iterator(){
   1.210 +	return new Iter(array);
   1.211 +}
   1.212 +
   1.213 +public ISeq seq(){
   1.214 +	if(array.length > 0)
   1.215 +		return new Seq(array, 0);
   1.216 +	return null;
   1.217 +}
   1.218 +
   1.219 +public IPersistentMap meta(){
   1.220 +	return _meta;
   1.221 +}
   1.222 +
   1.223 +static class Seq extends ASeq implements Counted{
   1.224 +	final Object[] array;
   1.225 +	final int i;
   1.226 +
   1.227 +	Seq(Object[] array, int i){
   1.228 +		this.array = array;
   1.229 +		this.i = i;
   1.230 +	}
   1.231 +
   1.232 +	public Seq(IPersistentMap meta, Object[] array, int i){
   1.233 +		super(meta);
   1.234 +		this.array = array;
   1.235 +		this.i = i;
   1.236 +	}
   1.237 +
   1.238 +	public Object first(){
   1.239 +		return new MapEntry(array[i],array[i+1]);
   1.240 +	}
   1.241 +
   1.242 +	public ISeq next(){
   1.243 +		if(i + 2 < array.length)
   1.244 +			return new Seq(array, i + 2);
   1.245 +		return null;
   1.246 +	}
   1.247 +
   1.248 +	public int count(){
   1.249 +		return (array.length - i) / 2;
   1.250 +	}
   1.251 +
   1.252 +	public Obj withMeta(IPersistentMap meta){
   1.253 +		return new Seq(meta, array, i);
   1.254 +	}
   1.255 +}
   1.256 +
   1.257 +static class Iter implements Iterator{
   1.258 +	Object[] array;
   1.259 +	int i;
   1.260 +
   1.261 +	//for iterator
   1.262 +	Iter(Object[] array){
   1.263 +		this(array, -2);
   1.264 +	}
   1.265 +
   1.266 +	//for entryAt
   1.267 +	Iter(Object[] array, int i){
   1.268 +		this.array = array;
   1.269 +		this.i = i;
   1.270 +	}
   1.271 +
   1.272 +	public boolean hasNext(){
   1.273 +		return i < array.length - 2;
   1.274 +	}
   1.275 +
   1.276 +	public Object next(){
   1.277 +		i += 2;
   1.278 +		return new MapEntry(array[i],array[i+1]);
   1.279 +	}
   1.280 +
   1.281 +	public void remove(){
   1.282 +		throw new UnsupportedOperationException();
   1.283 +	}
   1.284 +
   1.285 +}
   1.286 +
   1.287 +public ITransientMap asTransient(){
   1.288 +	return new TransientArrayMap(array);
   1.289 +}
   1.290 +
   1.291 +static final class TransientArrayMap extends ATransientMap {
   1.292 +	int len;
   1.293 +	final Object[] array;
   1.294 +	Thread owner;
   1.295 +
   1.296 +	public TransientArrayMap(Object[] array){
   1.297 +		this.owner = Thread.currentThread();
   1.298 +		this.array = new Object[Math.max(HASHTABLE_THRESHOLD, array.length)];
   1.299 +		System.arraycopy(array, 0, this.array, 0, array.length);
   1.300 +		this.len = array.length;
   1.301 +	}
   1.302 +	
   1.303 +	private int indexOf(Object key){
   1.304 +		for(int i = 0; i < len; i += 2)
   1.305 +			{
   1.306 +			if(equalKey(array[i], key))
   1.307 +				return i;
   1.308 +			}
   1.309 +		return -1;
   1.310 +	}
   1.311 +
   1.312 +	ITransientMap doAssoc(Object key, Object val){
   1.313 +		int i = indexOf(key);
   1.314 +		if(i >= 0) //already have key,
   1.315 +			{
   1.316 +			if(array[i + 1] != val) //no change, no op
   1.317 +				array[i + 1] = val;
   1.318 +			}
   1.319 +		else //didn't have key, grow
   1.320 +			{
   1.321 +			if(len >= array.length)
   1.322 +				return PersistentHashMap.create(array).asTransient().assoc(key, val);
   1.323 +			array[len++] = key;
   1.324 +			array[len++] = val;
   1.325 +			}
   1.326 +		return this;
   1.327 +	}
   1.328 +
   1.329 +	ITransientMap doWithout(Object key) {
   1.330 +		int i = indexOf(key);
   1.331 +		if(i >= 0) //have key, will remove
   1.332 +			{
   1.333 +			if (len >= 2)
   1.334 +				{
   1.335 +					array[i] = array[len - 2];
   1.336 +					array[i + 1] = array[len - 1];
   1.337 +				}
   1.338 +			len -= 2;
   1.339 +			}
   1.340 +		return this;
   1.341 +	}
   1.342 +
   1.343 +	Object doValAt(Object key, Object notFound) {
   1.344 +		int i = indexOf(key);
   1.345 +		if (i >= 0)
   1.346 +			return array[i + 1];
   1.347 +		return notFound;
   1.348 +	}
   1.349 +
   1.350 +	int doCount() {
   1.351 +		return len / 2;
   1.352 +	}
   1.353 +	
   1.354 +	IPersistentMap doPersistent(){
   1.355 +		ensureEditable();
   1.356 +		owner = null;
   1.357 +		Object[] a = new Object[len];
   1.358 +		System.arraycopy(array,0,a,0,len);
   1.359 +		return new PersistentArrayMap(a);
   1.360 +	}
   1.361 +
   1.362 +	void ensureEditable(){
   1.363 +		if(owner == Thread.currentThread())
   1.364 +			return;
   1.365 +		if(owner != null)
   1.366 +			throw new IllegalAccessError("Transient used by non-owner thread");
   1.367 +		throw new IllegalAccessError("Transient used after persistent! call");
   1.368 +	}
   1.369 +}
   1.370 +}