1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/clojure/lang/APersistentVector.java	Sat Aug 21 06:25:44 2010 -0400
     1.3 @@ -0,0 +1,568 @@
     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 +/* rich Dec 18, 2007 */
    1.15 +
    1.16 +package clojure.lang;
    1.17 +
    1.18 +import java.io.Serializable;
    1.19 +import java.util.*;
    1.20 +
    1.21 +public abstract class APersistentVector extends AFn implements IPersistentVector, Iterable,
    1.22 +                                                               List,
    1.23 +                                                               RandomAccess, Comparable,
    1.24 +                                                               Serializable {
    1.25 +int _hash = -1;
    1.26 +
    1.27 +public String toString(){
    1.28 +	return RT.printString(this);
    1.29 +}
    1.30 +
    1.31 +public ISeq seq(){
    1.32 +	if(count() > 0)
    1.33 +		return new Seq(this, 0);
    1.34 +	return null;
    1.35 +}
    1.36 +
    1.37 +public ISeq rseq(){
    1.38 +	if(count() > 0)
    1.39 +		return new RSeq(this, count() - 1);
    1.40 +	return null;
    1.41 +}
    1.42 +
    1.43 +static boolean doEquals(IPersistentVector v, Object obj){
    1.44 +	if(v == obj) return true;
    1.45 +	if(obj instanceof List || obj instanceof IPersistentVector)
    1.46 +		{
    1.47 +		Collection ma = (Collection) obj;
    1.48 +		if(ma.size() != v.count() || ma.hashCode() != v.hashCode())
    1.49 +			return false;
    1.50 +		for(Iterator i1 = ((List) v).iterator(), i2 = ma.iterator();
    1.51 +		    i1.hasNext();)
    1.52 +			{
    1.53 +			if(!Util.equals(i1.next(), i2.next()))
    1.54 +				return false;
    1.55 +			}
    1.56 +		return true;
    1.57 +		}
    1.58 +//	if(obj instanceof IPersistentVector)
    1.59 +//		{
    1.60 +//		IPersistentVector ma = (IPersistentVector) obj;
    1.61 +//		if(ma.count() != v.count() || ma.hashCode() != v.hashCode())
    1.62 +//			return false;
    1.63 +//		for(int i = 0; i < v.count(); i++)
    1.64 +//			{
    1.65 +//			if(!Util.equal(v.nth(i), ma.nth(i)))
    1.66 +//				return false;
    1.67 +//			}
    1.68 +//		}
    1.69 +	else
    1.70 +		{
    1.71 +		if(!(obj instanceof Sequential))
    1.72 +			return false;
    1.73 +		ISeq ms = RT.seq(obj);
    1.74 +		for(int i = 0; i < v.count(); i++, ms = ms.next())
    1.75 +			{
    1.76 +			if(ms == null || !Util.equals(v.nth(i), ms.first()))
    1.77 +				return false;
    1.78 +			}
    1.79 +		if(ms != null)
    1.80 +			return false;
    1.81 +		}
    1.82 +
    1.83 +	return true;
    1.84 +
    1.85 +}
    1.86 +
    1.87 +static boolean doEquiv(IPersistentVector v, Object obj){
    1.88 +	if(obj instanceof List || obj instanceof IPersistentVector)
    1.89 +		{
    1.90 +		Collection ma = (Collection) obj;
    1.91 +		if(ma.size() != v.count())
    1.92 +			return false;
    1.93 +		for(Iterator i1 = ((List) v).iterator(), i2 = ma.iterator();
    1.94 +		    i1.hasNext();)
    1.95 +			{
    1.96 +			if(!Util.equiv(i1.next(), i2.next()))
    1.97 +				return false;
    1.98 +			}
    1.99 +		return true;
   1.100 +		}
   1.101 +//	if(obj instanceof IPersistentVector)
   1.102 +//		{
   1.103 +//		IPersistentVector ma = (IPersistentVector) obj;
   1.104 +//		if(ma.count() != v.count() || ma.hashCode() != v.hashCode())
   1.105 +//			return false;
   1.106 +//		for(int i = 0; i < v.count(); i++)
   1.107 +//			{
   1.108 +//			if(!Util.equal(v.nth(i), ma.nth(i)))
   1.109 +//				return false;
   1.110 +//			}
   1.111 +//		}
   1.112 +	else
   1.113 +		{
   1.114 +		if(!(obj instanceof Sequential))
   1.115 +			return false;
   1.116 +		ISeq ms = RT.seq(obj);
   1.117 +		for(int i = 0; i < v.count(); i++, ms = ms.next())
   1.118 +			{
   1.119 +			if(ms == null || !Util.equiv(v.nth(i), ms.first()))
   1.120 +				return false;
   1.121 +			}
   1.122 +		if(ms != null)
   1.123 +			return false;
   1.124 +		}
   1.125 +
   1.126 +	return true;
   1.127 +
   1.128 +}
   1.129 +
   1.130 +public boolean equals(Object obj){
   1.131 +	return doEquals(this, obj);
   1.132 +}
   1.133 +
   1.134 +public boolean equiv(Object obj){
   1.135 +	return doEquiv(this, obj);
   1.136 +}
   1.137 +
   1.138 +public int hashCode(){
   1.139 +	if(_hash == -1)
   1.140 +		{
   1.141 +		int hash = 1;
   1.142 +		Iterator i = iterator();
   1.143 +		while(i.hasNext())
   1.144 +			{
   1.145 +			Object obj = i.next();
   1.146 +			hash = 31 * hash + (obj == null ? 0 : obj.hashCode());
   1.147 +			}
   1.148 +//		int hash = 0;
   1.149 +//		for(int i = 0; i < count(); i++)
   1.150 +//			{
   1.151 +//			hash = Util.hashCombine(hash, Util.hash(nth(i)));
   1.152 +//			}
   1.153 +		this._hash = hash;
   1.154 +		}
   1.155 +	return _hash;
   1.156 +}
   1.157 +
   1.158 +public Object get(int index){
   1.159 +	return nth(index);
   1.160 +}
   1.161 +
   1.162 +public Object nth(int i, Object notFound){
   1.163 +	if(i >= 0 && i < count())
   1.164 +		return nth(i);
   1.165 +	return notFound;
   1.166 +}
   1.167 +
   1.168 +public Object remove(int i){
   1.169 +	throw new UnsupportedOperationException();
   1.170 +}
   1.171 +
   1.172 +public int indexOf(Object o){
   1.173 +	for(int i = 0; i < count(); i++)
   1.174 +		if(Util.equiv(nth(i), o))
   1.175 +			return i;
   1.176 +	return -1;
   1.177 +}
   1.178 +
   1.179 +public int lastIndexOf(Object o){
   1.180 +	for(int i = count() - 1; i >= 0; i--)
   1.181 +		if(Util.equiv(nth(i), o))
   1.182 +			return i;
   1.183 +	return -1;
   1.184 +}
   1.185 +
   1.186 +public ListIterator listIterator(){
   1.187 +	return listIterator(0);
   1.188 +}
   1.189 +
   1.190 +public ListIterator listIterator(final int index){
   1.191 +	return new ListIterator(){
   1.192 +		int nexti = index;
   1.193 +
   1.194 +		public boolean hasNext(){
   1.195 +			return nexti < count();
   1.196 +		}
   1.197 +
   1.198 +		public Object next(){
   1.199 +			return nth(nexti++);
   1.200 +		}
   1.201 +
   1.202 +		public boolean hasPrevious(){
   1.203 +			return nexti > 0;
   1.204 +		}
   1.205 +
   1.206 +		public Object previous(){
   1.207 +			return nth(--nexti);
   1.208 +		}
   1.209 +
   1.210 +		public int nextIndex(){
   1.211 +			return nexti;
   1.212 +		}
   1.213 +
   1.214 +		public int previousIndex(){
   1.215 +			return nexti - 1;
   1.216 +		}
   1.217 +
   1.218 +		public void remove(){
   1.219 +			throw new UnsupportedOperationException();
   1.220 +		}
   1.221 +
   1.222 +		public void set(Object o){
   1.223 +			throw new UnsupportedOperationException();
   1.224 +		}
   1.225 +
   1.226 +		public void add(Object o){
   1.227 +			throw new UnsupportedOperationException();
   1.228 +		}
   1.229 +	};
   1.230 +}
   1.231 +
   1.232 +public List subList(int fromIndex, int toIndex){
   1.233 +	return (List) RT.subvec(this, fromIndex, toIndex);
   1.234 +}
   1.235 +
   1.236 +
   1.237 +public Object set(int i, Object o){
   1.238 +	throw new UnsupportedOperationException();
   1.239 +}
   1.240 +
   1.241 +public void add(int i, Object o){
   1.242 +	throw new UnsupportedOperationException();
   1.243 +}
   1.244 +
   1.245 +public boolean addAll(int i, Collection c){
   1.246 +	throw new UnsupportedOperationException();
   1.247 +}
   1.248 +
   1.249 +
   1.250 +public Object invoke(Object arg1) throws Exception{
   1.251 +	if(Util.isInteger(arg1))
   1.252 +		return nth(((Number) arg1).intValue());
   1.253 +	throw new IllegalArgumentException("Key must be integer");
   1.254 +}
   1.255 +
   1.256 +public Iterator iterator(){
   1.257 +	//todo - something more efficient
   1.258 +	return new Iterator(){
   1.259 +		int i = 0;
   1.260 +
   1.261 +		public boolean hasNext(){
   1.262 +			return i < count();
   1.263 +		}
   1.264 +
   1.265 +		public Object next(){
   1.266 +			return nth(i++);
   1.267 +		}
   1.268 +
   1.269 +		public void remove(){
   1.270 +			throw new UnsupportedOperationException();
   1.271 +		}
   1.272 +	};
   1.273 +}
   1.274 +
   1.275 +public Object peek(){
   1.276 +	if(count() > 0)
   1.277 +		return nth(count() - 1);
   1.278 +	return null;
   1.279 +}
   1.280 +
   1.281 +public boolean containsKey(Object key){
   1.282 +	if(!(Util.isInteger(key)))
   1.283 +		return false;
   1.284 +	int i = ((Number) key).intValue();
   1.285 +	return i >= 0 && i < count();
   1.286 +}
   1.287 +
   1.288 +public IMapEntry entryAt(Object key){
   1.289 +	if(Util.isInteger(key))
   1.290 +		{
   1.291 +		int i = ((Number) key).intValue();
   1.292 +		if(i >= 0 && i < count())
   1.293 +			return new MapEntry(key, nth(i));
   1.294 +		}
   1.295 +	return null;
   1.296 +}
   1.297 +
   1.298 +public IPersistentVector assoc(Object key, Object val){
   1.299 +	if(Util.isInteger(key))
   1.300 +		{
   1.301 +		int i = ((Number) key).intValue();
   1.302 +		return assocN(i, val);
   1.303 +		}
   1.304 +	throw new IllegalArgumentException("Key must be integer");
   1.305 +}
   1.306 +
   1.307 +public Object valAt(Object key, Object notFound){
   1.308 +	if(Util.isInteger(key))
   1.309 +		{
   1.310 +		int i = ((Number) key).intValue();
   1.311 +		if(i >= 0 && i < count())
   1.312 +			return nth(i);
   1.313 +		}
   1.314 +	return notFound;
   1.315 +}
   1.316 +
   1.317 +public Object valAt(Object key){
   1.318 +	return valAt(key, null);
   1.319 +}
   1.320 +
   1.321 +// java.util.Collection implementation
   1.322 +
   1.323 +public Object[] toArray(){
   1.324 +	return RT.seqToArray(seq());
   1.325 +}
   1.326 +
   1.327 +public boolean add(Object o){
   1.328 +	throw new UnsupportedOperationException();
   1.329 +}
   1.330 +
   1.331 +public boolean remove(Object o){
   1.332 +	throw new UnsupportedOperationException();
   1.333 +}
   1.334 +
   1.335 +public boolean addAll(Collection c){
   1.336 +	throw new UnsupportedOperationException();
   1.337 +}
   1.338 +
   1.339 +public void clear(){
   1.340 +	throw new UnsupportedOperationException();
   1.341 +}
   1.342 +
   1.343 +public boolean retainAll(Collection c){
   1.344 +	throw new UnsupportedOperationException();
   1.345 +}
   1.346 +
   1.347 +public boolean removeAll(Collection c){
   1.348 +	throw new UnsupportedOperationException();
   1.349 +}
   1.350 +
   1.351 +public boolean containsAll(Collection c){
   1.352 +	for(Object o : c)
   1.353 +		{
   1.354 +		if(!contains(o))
   1.355 +			return false;
   1.356 +		}
   1.357 +	return true;
   1.358 +}
   1.359 +
   1.360 +public Object[] toArray(Object[] a){
   1.361 +	if(a.length >= count())
   1.362 +		{
   1.363 +		ISeq s = seq();
   1.364 +		for(int i = 0; s != null; ++i, s = s.next())
   1.365 +			{
   1.366 +			a[i] = s.first();
   1.367 +			}
   1.368 +		if(a.length > count())
   1.369 +			a[count()] = null;
   1.370 +		return a;
   1.371 +		}
   1.372 +	else
   1.373 +		return toArray();
   1.374 +}
   1.375 +
   1.376 +public int size(){
   1.377 +	return count();
   1.378 +}
   1.379 +
   1.380 +public boolean isEmpty(){
   1.381 +	return count() == 0;
   1.382 +}
   1.383 +
   1.384 +public boolean contains(Object o){
   1.385 +	for(ISeq s = seq(); s != null; s = s.next())
   1.386 +		{
   1.387 +		if(Util.equiv(s.first(), o))
   1.388 +			return true;
   1.389 +		}
   1.390 +	return false;
   1.391 +}
   1.392 +
   1.393 +public int length(){
   1.394 +	return count();
   1.395 +}
   1.396 +
   1.397 +public int compareTo(Object o){
   1.398 +	IPersistentVector v = (IPersistentVector) o;
   1.399 +	if(count() < v.count())
   1.400 +		return -1;
   1.401 +	else if(count() > v.count())
   1.402 +		return 1;
   1.403 +	for(int i = 0; i < count(); i++)
   1.404 +		{
   1.405 +		int c = Util.compare(nth(i),v.nth(i));
   1.406 +		if(c != 0)
   1.407 +			return c;
   1.408 +		}
   1.409 +	return 0;
   1.410 +}
   1.411 +
   1.412 +    static class Seq extends ASeq implements IndexedSeq, IReduce{
   1.413 +	//todo - something more efficient
   1.414 +	final IPersistentVector v;
   1.415 +	final int i;
   1.416 +
   1.417 +
   1.418 +	public Seq(IPersistentVector v, int i){
   1.419 +		this.v = v;
   1.420 +		this.i = i;
   1.421 +	}
   1.422 +
   1.423 +	Seq(IPersistentMap meta, IPersistentVector v, int i){
   1.424 +		super(meta);
   1.425 +		this.v = v;
   1.426 +		this.i = i;
   1.427 +	}
   1.428 +
   1.429 +	public Object first(){
   1.430 +		return v.nth(i);
   1.431 +	}
   1.432 +
   1.433 +	public ISeq next(){
   1.434 +		if(i + 1 < v.count())
   1.435 +			return new APersistentVector.Seq(v, i + 1);
   1.436 +		return null;
   1.437 +	}
   1.438 +
   1.439 +	public int index(){
   1.440 +		return i;
   1.441 +	}
   1.442 +
   1.443 +	public int count(){
   1.444 +		return v.count() - i;
   1.445 +	}
   1.446 +
   1.447 +	public APersistentVector.Seq withMeta(IPersistentMap meta){
   1.448 +		return new APersistentVector.Seq(meta, v, i);
   1.449 +	}
   1.450 +
   1.451 +	public Object reduce(IFn f) throws Exception{
   1.452 +		Object ret = v.nth(i);
   1.453 +		for(int x = i + 1; x < v.count(); x++)
   1.454 +			ret = f.invoke(ret, v.nth(x));
   1.455 +		return ret;
   1.456 +	}
   1.457 +
   1.458 +	public Object reduce(IFn f, Object start) throws Exception{
   1.459 +		Object ret = f.invoke(start, v.nth(i));
   1.460 +		for(int x = i + 1; x < v.count(); x++)
   1.461 +			ret = f.invoke(ret, v.nth(x));
   1.462 +		return ret;
   1.463 +	}
   1.464 +    }
   1.465 +
   1.466 +public static class RSeq extends ASeq implements IndexedSeq, Counted{
   1.467 +	final IPersistentVector v;
   1.468 +	final int i;
   1.469 +
   1.470 +	public RSeq(IPersistentVector vector, int i){
   1.471 +		this.v = vector;
   1.472 +		this.i = i;
   1.473 +	}
   1.474 +
   1.475 +	RSeq(IPersistentMap meta, IPersistentVector v, int i){
   1.476 +		super(meta);
   1.477 +		this.v = v;
   1.478 +		this.i = i;
   1.479 +	}
   1.480 +
   1.481 +	public Object first(){
   1.482 +		return v.nth(i);
   1.483 +	}
   1.484 +
   1.485 +	public ISeq next(){
   1.486 +		if(i > 0)
   1.487 +			return new APersistentVector.RSeq(v, i - 1);
   1.488 +		return null;
   1.489 +	}
   1.490 +
   1.491 +	public int index(){
   1.492 +		return i;
   1.493 +	}
   1.494 +
   1.495 +	public int count(){
   1.496 +		return i + 1;
   1.497 +	}
   1.498 +
   1.499 +	public APersistentVector.RSeq withMeta(IPersistentMap meta){
   1.500 +		return new APersistentVector.RSeq(meta, v, i);
   1.501 +	}
   1.502 +}
   1.503 +
   1.504 +static class SubVector extends APersistentVector implements IObj{
   1.505 +	final IPersistentVector v;
   1.506 +	final int start;
   1.507 +	final int end;
   1.508 +	final IPersistentMap _meta;
   1.509 +
   1.510 +
   1.511 +
   1.512 +	public SubVector(IPersistentMap meta, IPersistentVector v, int start, int end){
   1.513 +		this._meta = meta;
   1.514 +
   1.515 +		if(v instanceof APersistentVector.SubVector)
   1.516 +			{
   1.517 +			APersistentVector.SubVector sv = (APersistentVector.SubVector) v;
   1.518 +			start += sv.start;
   1.519 +			end += sv.start;
   1.520 +			v = sv.v;
   1.521 +			}
   1.522 +		this.v = v;
   1.523 +		this.start = start;
   1.524 +		this.end = end;
   1.525 +	}
   1.526 +
   1.527 +	public Object nth(int i){
   1.528 +		if(start + i >= end)
   1.529 +			throw new IndexOutOfBoundsException();
   1.530 +		return v.nth(start + i);
   1.531 +	}
   1.532 +
   1.533 +	public IPersistentVector assocN(int i, Object val){
   1.534 +		if(start + i > end)
   1.535 +			throw new IndexOutOfBoundsException();
   1.536 +		else if(start + i == end)
   1.537 +			return cons(val);
   1.538 +		return new SubVector(_meta, v.assocN(start + i, val), start, end);
   1.539 +	}
   1.540 +
   1.541 +	public int count(){
   1.542 +		return end - start;
   1.543 +	}
   1.544 +
   1.545 +	public IPersistentVector cons(Object o){
   1.546 +		return new SubVector(_meta, v.assocN(end, o), start, end + 1);
   1.547 +	}
   1.548 +
   1.549 +	public IPersistentCollection empty(){
   1.550 +		return PersistentVector.EMPTY.withMeta(meta());
   1.551 +	}
   1.552 +
   1.553 +	public IPersistentStack pop(){
   1.554 +		if(end - 1 == start)
   1.555 +			{
   1.556 +			return PersistentVector.EMPTY;
   1.557 +			}
   1.558 +		return new SubVector(_meta, v, start, end - 1);
   1.559 +	}
   1.560 +
   1.561 +	public SubVector withMeta(IPersistentMap meta){
   1.562 +		if(meta == _meta)
   1.563 +			return this;
   1.564 +		return new SubVector(meta, v, start, end);
   1.565 +	}
   1.566 +
   1.567 +	public IPersistentMap meta(){
   1.568 +		return _meta;
   1.569 +	}
   1.570 +}
   1.571 +}