/**

  *   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.util.Collection;

 import java.util.Iterator;

 //import java.util.concurrent.ConcurrentLinkedQueue;

 

 /**

  * conses onto rear, peeks/pops from front

  * See Okasaki's Batched Queues

  * This differs in that it uses a PersistentArrayList as the rear, which is in-order,

  * so no reversing or suspensions required for persistent use

  */

 

 public class PersistentQueue extends Obj implements IPersistentList, Collection{

 

 final public static PersistentQueue EMPTY = new PersistentQueue(null, null, null);

 

 //*

 final ISeq f;

 final PersistentVector r;

 //static final int INITIAL_REAR_SIZE = 4;

 int _hash = -1;

 

 PersistentQueue(IPersistentMap meta, ISeq f, PersistentVector r){

 	super(meta);

 	this.f = f;

 	this.r = r;

 }

 

 public boolean equiv(Object obj){

 

 	if(!(obj instanceof Sequential))

 		return false;

 	ISeq ms = RT.seq(obj);

 	for(ISeq s = seq(); s != null; s = s.next(), ms = ms.next())

 		{

 		if(ms == null || !Util.equiv(s.first(), ms.first()))

 			return false;

 		}

 	return ms == null;

 

 }

 

 public boolean equals(Object obj){

 

 	if(!(obj instanceof Sequential))

 		return false;

 	ISeq ms = RT.seq(obj);

 	for(ISeq s = seq(); s != null; s = s.next(), ms = ms.next())

 		{

 		if(ms == null || !Util.equals(s.first(), ms.first()))

 			return false;

 		}

 	return ms == null;

 

 }

 

 public int hashCode(){

 	if(_hash == -1)

 		{

 		int hash = 0;

 		for(ISeq s = seq(); s != null; s = s.next())

 			{

 			hash = Util.hashCombine(hash, Util.hash(s.first()));

 			}

 		this._hash = hash;

 		}

 	return _hash;

 }

 

 public Object peek(){

 	return RT.first(f);

 }

 

 public PersistentQueue pop(){

 	if(f == null)  //hmmm... pop of empty queue -> empty queue?

 		return this;

 	//throw new IllegalStateException("popping empty queue");

 	ISeq f1 = f.next();

 	PersistentVector r1 = r;

 	if(f1 == null)

 		{

 		f1 = RT.seq(r);

 		r1 = null;

 		}

 	return new PersistentQueue(meta(), f1, r1);

 }

 

 public int count(){

 	return RT.count(f) + RT.count(r);

 }

 

 public ISeq seq(){

 	if(f == null)

 		return null;

 	return new Seq(f, RT.seq(r));

 }

 

 public PersistentQueue cons(Object o){

 	if(f == null)     //empty

 		return new PersistentQueue(meta(), RT.list(o), null);

 	else

 		return new PersistentQueue(meta(), f, (r != null ? r : PersistentVector.EMPTY).cons(o));

 }

 

 public IPersistentCollection empty(){

 	return EMPTY.withMeta(meta());	

 }

 

 public PersistentQueue withMeta(IPersistentMap meta){

 	return new PersistentQueue(meta, f, r);

 }

 

 static class Seq extends ASeq{

 	final ISeq f;

 	final ISeq rseq;

 

 	Seq(ISeq f, ISeq rseq){

 		this.f = f;

 		this.rseq = rseq;

 	}

 

 	Seq(IPersistentMap meta, ISeq f, ISeq rseq){

 		super(meta);

 		this.f = f;

 		this.rseq = rseq;

 	}

 

 	public Object first(){

 		return f.first();

 	}

 

 	public ISeq next(){

 		ISeq f1 = f.next();

 		ISeq r1 = rseq;

 		if(f1 == null)

 			{

 			if(rseq == null)

 				return null;

 			f1 = rseq;

 			r1 = null;

 			}

 		return new Seq(f1, r1);

 	}

 

 	public int count(){

 		return RT.count(f) + RT.count(rseq);

 	}

 

 	public Seq withMeta(IPersistentMap meta){

 		return new Seq(meta, f, rseq);

 	}

 }

 

 // java.util.Collection implementation

 

 public Object[] toArray(){

 	return RT.seqToArray(seq());

 }

 

 public boolean add(Object o){

 	throw new UnsupportedOperationException();

 }

 

 public boolean remove(Object o){

 	throw new UnsupportedOperationException();

 }

 

 public boolean addAll(Collection c){

 	throw new UnsupportedOperationException();

 }

 

 public void clear(){

 	throw new UnsupportedOperationException();

 }

 

 public boolean retainAll(Collection c){

 	throw new UnsupportedOperationException();

 }

 

 public boolean removeAll(Collection c){

 	throw new UnsupportedOperationException();

 }

 

 public boolean containsAll(Collection c){

 	for(Object o : c)

 		{

 		if(contains(o))

 			return true;

 		}

 	return false;

 }

 

 public Object[] toArray(Object[] a){

 	if(a.length >= count())

 		{

 		ISeq s = seq();

 		for(int i = 0; s != null; ++i, s = s.next())

 			{

 			a[i] = s.first();

 			}

 		if(a.length >= count())

 			a[count()] = null;

 		return a;

 		}

 	else

 		return toArray();

 }

 

 public int size(){

 	return count();

 }

 

 public boolean isEmpty(){

 	return count() == 0;

 }

 

 public boolean contains(Object o){

 	for(ISeq s = seq(); s != null; s = s.next())

 		{

 		if(Util.equiv(s.first(), o))

 			return true;

 		}

 	return false;

 }

 

 public Iterator iterator(){

 	return new SeqIterator(seq());

 }

 

 /*

 public static void main(String[] args){

 	if(args.length != 1)

 		{

 		System.err.println("Usage: PersistentQueue n");

 		return;

 		}

 	int n = Integer.parseInt(args[0]);

 

 

 	long startTime, estimatedTime;

 

 	Queue list = new LinkedList();

 	//Queue list = new ConcurrentLinkedQueue();

 	System.out.println("Queue");

 	startTime = System.nanoTime();

 	for(int i = 0; i < n; i++)

 		{

 		list.add(i);

 		list.add(i);

 		list.remove();

 		}

 	for(int i = 0; i < n - 10; i++)

 		{

 		list.remove();

 		}

 	estimatedTime = System.nanoTime() - startTime;

 	System.out.println("time: " + estimatedTime / 1000000);

 	System.out.println("peek: " + list.peek());

 

 

 	PersistentQueue q = PersistentQueue.EMPTY;

 	System.out.println("PersistentQueue");

 	startTime = System.nanoTime();

 	for(int i = 0; i < n; i++)

 		{

 		q = q.cons(i);

 		q = q.cons(i);

 		q = q.pop();

 		}

 //    IPersistentList lastq = null;

 //    IPersistentList lastq2;

 	for(int i = 0; i < n - 10; i++)

 		{

 		//lastq2 = lastq;

 		//lastq = q;

 		q = q.pop();

 		}

 	estimatedTime = System.nanoTime() - startTime;

 	System.out.println("time: " + estimatedTime / 1000000);

 	System.out.println("peek: " + q.peek());

 

 	IPersistentList q2 = q;

 	for(int i = 0; i < 10; i++)

 		{

 		q2 = (IPersistentList) q2.cons(i);

 		}

 //    for(ISeq s = q.seq();s != null;s = s.rest())

 //        System.out.println("q: " + s.first().toString());

 //    for(ISeq s = q2.seq();s != null;s = s.rest())

 //        System.out.println("q2: " + s.first().toString());

 }

 */

 }