package org.pcollections;
import java.io.Serializable;
import java.util.AbstractQueue;
import java.util.Collection;
import java.util.Iterator;
public class AmortizedPQueue<E> extends AbstractQueue<E> implements PQueue<E>, Serializable {
private static final long serialVersionUID = 1L;
private static final AmortizedPQueue<Object> EMPTY = new AmortizedPQueue<Object>();
@SuppressWarnings("unchecked")
public static <E> AmortizedPQueue<E> empty() {
return (AmortizedPQueue<E>) EMPTY;
}
private final PStack<E> front;
private final PStack<E> back;
private AmortizedPQueue() {
front = Empty.<E>stack();
back = Empty.<E>stack();
}
private AmortizedPQueue(AmortizedPQueue<E> queue, E e) {
if (queue.front.size() == 0) {
this.front = queue.front.plus(e);
this.back = queue.back;
} else {
this.front = queue.front;
this.back = queue.back.plus(e);
}
}
private AmortizedPQueue(PStack<E> front, PStack<E> back) {
this.front = front;
this.back = back;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
private PQueue<E> queue = AmortizedPQueue.this;
public boolean hasNext() {
return queue.size() > 0;
}
public E next() {
E e = queue.peek();
queue = queue.minus();
return e;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
@Override
public int size() {
return front.size() + back.size();
}
public E peek() {
if (size() == 0) return null;
return front.get(0);
}
public AmortizedPQueue<E> minus() {
if (size() == 0) {
return this;
}
int fsize = front.size();
if (fsize == 0) {
return new AmortizedPQueue<E>(Empty.<E>stack().plusAll(back), Empty.<E>stack()).minus();
} else if (fsize == 1) {
return new AmortizedPQueue<E>(Empty.<E>stack().plusAll(back), Empty.<E>stack());
} else {
return new AmortizedPQueue<E>(front.minus(0), back);
}
}
public AmortizedPQueue<E> plus(E e) {
return new AmortizedPQueue<E>(this, e);
}
public AmortizedPQueue<E> plusAll(Collection<? extends E> list) {
AmortizedPQueue<E> result = this;
for (E e : list) {
result = result.plus(e);
}
return result;
}
public PCollection<E> minus(Object e) {
return Empty.<E>vector().plusAll(this).minus(e);
}
public PCollection<E> minusAll(Collection<?> list) {
return Empty.<E>vector().plusAll(this).minusAll(list);
}
public boolean offer(E o) {
throw new UnsupportedOperationException();
}
public E poll() {
throw new UnsupportedOperationException();
}
public static void main(String[] args) {
AmortizedPQueue<Integer> queue = new AmortizedPQueue<Integer>();
queue = queue.plus(1).minus().minus().plus(2).plus(3).plus(4).plus(5).minus().plus(6).plus(7);
PQueue<Integer> original = queue;
System.out.println(" \t" + queue.front + " " + queue.back);
while (queue.size() > 0) {
int i = queue.peek();
queue = queue.minus();
System.out.println(i + " <- \t" + queue.front + " " + queue.back);
}
System.out.println(original);
}
}