package fr.moresmau.jp.collections;

import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

import fr.moresmau.jp.func.Function1;
import fr.moresmau.jp.func.Mapper;


/**
 * @author JP Moresmau
 *
 * @param <T> the class of elements to hold
 */
public class VList<T> extends AbstractCollection<T> {
	private int offset;
	private Block base;
	private int size=0;	
	
	/**
	 * construct an empty vlist
	 * @param cls the class of elements to hold
	 */
	public VList() {
		super();
		base=new Block();
		base.data=new Object[1];
	}
	
	/**
	 * construct a singleton vlist
	 * @param cls the class of elements to hold
	 */
	public VList(T obj) {
		super();
		base=new Block();
		base.data=new Object[1];
		add(obj);
	}
	
	/**
	 * construct a new vlist on top of another one
	 * @param vl
	 */
	protected VList(VList<T> vl){
		if (vl.offset>1){
			offset=vl.offset-1;
			base=vl.base;
		}  else {
			base=vl.base.previousBase;
			offset=base.lastUsed;
		}
		size=vl.size-1;
	}
	
	/**
	 * get the nth element
	 * @param a
	 * @return
	 */
	public T get(int a){
		if (a<0 || a>=size){
			throw new ArrayIndexOutOfBoundsException(a);
		}
		if (a==0){
			return first();
		}
		int currentOffset=offset;
		Block currentBase=base;
		while (a>currentOffset-1){
			a-=currentOffset;
			currentOffset=currentBase.previousOffset;
			currentBase=currentBase.previousBase;
		}
		currentOffset-=a;
		
		return (T)currentBase.data[currentOffset-1];
	}

	/**
	 * get the initial element
	 * @return
	 */
	public T first(){
		if (offset-1<base.data.length){
			return (T)base.data[offset-1];
		}
		return null;
	}
	
	public T last(){
		if (isEmpty()){
			return null;
		}
		Block b=base;
		while (b.previousBase!=null){
			b=b.previousBase;
		}
		return (T)b.data[0];
	}
	
	/**
	 * get the tail list
	 * @return
	 */
	public VList<T> rest(){
		if (base.data.length==0 && offset==0){
			throw new ArrayIndexOutOfBoundsException(0);
		}
		return new VList<T>(this);
	}
	
	/**
	 * add an element at the start
	 * @param val
	 */
	public void addFirst(T val){
		int newOffset=base.add(val,offset);
		if (newOffset==-1){
			Block newBase=new Block();
			
			newBase.data=new Object[base.data.length*2];
			newBase.previousBase=base;
			newBase.previousOffset=offset;
			offset=newBase.add(val,0);
			base=newBase;
		} else {
			offset=newOffset;
		}
		size++;
	}
	
	@Override
	public boolean addAll(Collection<? extends T> c) {
		Object[] o=c.toArray();
		for (int a=o.length-1;a>=0;a--){
			this.addFirst((T)o[a]);
		}
		return true;
	}
	
	public T removeFirst(){
		T t=first();
		size--;
		offset--;
		if (offset<1){
			offset=base.previousOffset;
			if (base.previousBase!=null){
				base=base.previousBase;
			}
		}
		return t;
	}
	
	/**
	 * dump to System.out
	 *
	 */
	public void dump(){
		System.out.println("offset:"+offset);
		System.out.println("");
		base.dump();
	}
	
	/**
	 * size of list
	 * @return
	 */
	public int size(){
		return size;
	}
	
	public boolean isEmpty(){
		return size==0;
	}
	
	/* (non-Javadoc)
	 * @see java.lang.Iterable#iterator()
	 */
	public Iterator<T> iterator(){
		return new VListIterator();
	}
	
	public Iterator<T> reverseIterator(){
		return new VListReverseIterator();
	}
	
	public Iterable<T> reverse(){
		return new Iterable<T>(){
			public Iterator<T> iterator() {
				return new VListReverseIterator();
			}
		};
	}
	
	public <T1> VList<T1> map(Mapper<T,T1> mapper){
		VList<T1> ret=new VList<T1>();
		for (Iterator<T> it=reverseIterator();it.hasNext();){
			ret.addFirst(mapper.map(it.next()));
		}
		return ret;
	}
	
	
	public VList<T> filter(Function1<T,Boolean> f){
		VList<T> ret=new VList<T>();
		for (T t:this.reverse()){
			if (f.run(t)){
				ret.add(t);
			}
		}
		return ret;
	}
	
	/* (non-Javadoc)
	 * @see java.util.Collection#add(java.lang.Object)
	 */
	public boolean add(T o) {
		addFirst(o);
		return true;
	}

	/* (non-Javadoc)
	 * @see java.util.Collection#clear()
	 */
	public void clear() {
		size=0;
		base=new Block();
		base.data=new Object[1];
		offset=0;
	}

	private class VListIterator implements Iterator<T>{
		int count=0;
		
		public boolean hasNext() {
			return VList.this.size()>count;
		}
		
		public T next() {
			return VList.this.get(count++);
		}
		
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}
	
	private class VListReverseIterator implements Iterator<T>{
		int count=VList.this.size()-1;
		
		public boolean hasNext() {
			return count>-1;
		}
		
		public T next() {
			return VList.this.get(count--);
		}
		
		public void remove() {
			throw new UnsupportedOperationException();
		}
		
		
	}
	
	
	private class Block {
		Block previousBase;
		int previousOffset;
		int lastUsed;
		Object[] data;
		
		int add(T val, int offset){
			if (offset==lastUsed && offset<data.length){
				data[offset]=val;
				offset++;
				lastUsed=offset;
				return offset;
			}
			return -1;
		}
		
		
		void dump(){
			System.out.println("previousOffset:"+previousOffset);
			System.out.println("size:"+data.length);
			System.out.println("lastUsed:"+lastUsed);
			for (Object o:data){
				System.out.println(String.valueOf(o));
			}
			System.out.println("");
			if (previousBase!=null){
				previousBase.dump();
			}
		}
	}
	
	
}