package coll;
/* Immutable Collection
 * by Martin Robinson
 * \__________________/
 *       /
 * \ ('<
 * (<=)
 * */

/*
 * collection abstract
 * contain basic redundancy
 * found in every implementation
 * of the list
 * \___________________________/
 *      /
 * \ ('<
 * (<=)
 * */
import java.util.Iterator;

/**
 * @author martin
 * Immutable Collection
 * @param <E>
 */
public abstract class Coll<E>  implements Lst<E>{
	/*implement Lst*/
	/* (non-Javadoc)
	 * @see array.Lst#set(int, java.lang.Object)
	 */
	public Lst<E> set(int i, E data){
		return Set.fromData(this,i,data);
	}
	/* (non-Javadoc)
	 * @see array.Lst#append(java.lang.Object)
	 */
	public Lst<E> append(final E data){
		return Append.fromData(this,data);
	}
	/* (non-Javadoc)
	 * @see array.Lst#remove(int)
	 */
	public Lst<E> remove(int index){
		return Remove.fromIndex(this, index);
	}
	/* (non-Javadoc)
	 * @see array.Lst#add(int, java.lang.Object)
	 */
	public Lst<E> add(int index, final E data){
		return Add.fromIndex(this, index, data);
	}
	/* (non-Javadoc)
	 * @see array.Lst#sub(int, int)
	 */
	public Lst<E> sub(int from, int to){
		return Sub.fromIndex(this, from, to);
	}
	/* (non-Javadoc)
	 * @see array.Lst#strip(int, int)
	 */
	public Lst<E> strip(int from, int to){
		return Strip.fromIndex(this, from, to);
	}
	/* (non-Javadoc)
	 * @see coll.Lst#insert(int, int, coll.Lst)
	 */
	public Lst<E> insert(int from, int to, final Lst<E> insertion){
		return Insert.fromIndex(this, from, to, insertion);
	}
	/* (non-Javadoc)
	 * @see coll.Lst#push(java.lang.Object)
	 */
	public Lst<E> push(final E value){
		return Push.fromVal(this, value);
	}
	/* (non-Javadoc)
	 * @see coll.Lst#pop()
	 */
	public Lst<E> pop(){
		return Pop.fromNothing(this);
	}
	/* (non-Javadoc)
	 * @see coll.Lst#limit(int)
	 */
	public Lst<E> limit(int size){
		return Limit.fromSize(this, size);
	}
	/*implement iterable*/
	/* (non-Javadoc)
	 * @see array.Lst#iterator()
	 */
	public Iterator<E> iterator(){
		//return Iteratator.fromList(this);
		final Lst<E> me = this;
		return new Iterator<E>(){
			private final Lst<E> _lst = me;
			private int _index = 0;
			public boolean hasNext() {
				return _lst.size() > _index;
			}
			public E next() {
				return _lst.get(_index++);
			}
			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
	}

	/*default object*/
	/* (non-Javadoc)
	 * @see java.lang.Object#equals(java.lang.Object)
	 */
	public boolean equals(final Object otherObj){
		if (!(otherObj instanceof Lst))
			return false;
		Lst other = (Lst)otherObj;
		if (other.size() != size())
			return false;
		for (int i=0;i<size();i++)
			if (other.get(i).equals(get(i)))
				return false;
		return true;
	}
	/* (non-Javadoc)
	 * @see java.lang.Object#hashCode()
	 */
	public int hashCode(){
		int hash = 37;
		for (int i=0;i<size();i++)
			hash = (17*hash)+ get(i).hashCode();
		return hash;
	}
	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	public String toString(){
		String tmp = new String();
		for (int i=0;i<size();i++)
			tmp += get(i).toString() + ' ';
		return tmp;
	}

/*
 * those private object act as filter
 * instead of modify directly the list
 * of copy on write, the filter take
 * it's place and alter result of getter
 * so it act as if the list was modified
 * without side effect. give modification
 * as fast as linked list but with some
 * overhead concerning getter
 * (lazy evaluation)
 * \________________________________/
 *       /
 * \ ('<
 * (=>)
 * */
	/**
	 * @author martin
	 * Set value in given list
	 * @param <E> type
	 */
	private static class Set<E> extends Coll<E>{
		private final Lst<E> _original;
		private final int _index;
		private final E _newValue;
		/**
		 * private constructor
		 * @param original as given list
		 * @param index as index of the value to set
		 * @param newValue as value to set
		 */
		private Set(final Lst<E> original, int index, final E newValue){
			_original = original;
			_index = index;
			_newValue = newValue;
		}
		/**
		 * static factory
		 * @param original given list
		 * @param index index of the value to set
		 * @param newValue as value to set at index
		 * @return new list
		 * @throws Exception if index is out of bound or original==nul
		 */
		public static <E> Lst<E> fromData(final Lst<E> original, int index, final E newValue){
			if (original == null)
				throw new NullPointerException();
			if (index >= original.size())
				throw new ArrayIndexOutOfBoundsException();
			return new Set<E>(original, index, newValue);
		}
		/* (non-Javadoc)
		 * @see array.Lst#get(int)
		 */
		public E get(int i){
			if (i==_index)
				return _newValue;
			return _original.get(i);
		}
		/* (non-Javadoc)
		 * @see array.Lst#size()
		 */
		public int size() {
			return _original.size();
		}
		/* (non-Javadoc)
		 * @see array.Lst#undo()
		 */
		public Lst<E> undo(){
			return _original;
		}
	}
	/**
	 * @author martin
	 * append value to given list
	 * @param <E>
	 */
	private static class Append<E> extends Coll<E>{
		private final Lst<E> _original;
		private final E _appendedValue;
		/**
		 * private constructor
		 * @param original as given list
		 * @param toAppend as new value to add at the end of the list
		 */
		private Append(final Lst<E> original, final E toAppend){
			_original = original;
			_appendedValue = toAppend;
		}
		/**
		 * static factory
		 * @param original as given list
		 * @param toAppend value to add at end of the list
		 * @return new list with given modification
		 * @throws Exception if original is null
		 */
		public static <E> Lst<E> fromData(final Lst<E> original, final E toAppend){
			if (original == null)
				throw new NullPointerException();
			return new Append<E>(original,toAppend);
		}

		/* (non-Javadoc)
		 * @see array.Lst#get(int)
		 */
		public E get(int i){
			if (i>=size())
				//return null;
				throw new ArrayIndexOutOfBoundsException();
			if (i==_original.size())
				return _appendedValue;
			return _original.get(i);
		}
		/* (non-Javadoc)
		 * @see array.Lst#size()
		 */
		public int size() {
			return _original.size()+1;
		}
		/* (non-Javadoc)
		 * @see array.Lst#undo()
		 */
		public Lst<E> undo(){
			return _original;
		}
	}
	/**
	 * @author martin
	 * remove value in list (shrink)
	 * @param <E>
	 */
	private static class Remove<E> extends Coll<E>{
		private final Lst<E> _original;
		private final int _index;
		/**
		 * private constructor
		 * @param original as given list
		 * @param index as index to remove
		 */
		private Remove(final Lst<E> original, int index){
			_original = original;
			_index = index;
		}

		/**
		 * static factory
		 * @param original  given list
		 * @param index index to remove
		 * @return modified list
		 * @throws Exception if index out of bound or original is null
		 */
		public static <E> Lst<E> fromIndex(final Lst<E> original, int index){
			if (original==null)
				throw new NullPointerException();
			if (index>= original.size())
				throw new ArrayIndexOutOfBoundsException();
			return new Remove<E>(original, index);
		}

		/* (non-Javadoc)
		 * @see array.Lst#get(int)
		 */
		public E get(int i) {
			if (i<_index)
				return _original.get(i);
			if (i<size())
				return _original.get(i+1);
			//return null;
			throw new ArrayIndexOutOfBoundsException();
		}

		/* (non-Javadoc)
		 * @see array.Lst#size()
		 */
		public int size() {
			return _original.size()-1;
		}
		/* (non-Javadoc)
		 * @see array.Lst#undo()
		 */
		public Lst<E> undo(){
			return _original;
		}
	}
	/**
	 * @author martin
	 * add value in list (expand)
	 * @param <E>
	 */
	private static class Add<E> extends Coll<E>{
		private final Lst<E> _original;
		private final int _index;
		private final E _data;
		/**
		 * private constructor
		 * @param original as given list
		 * @param index as index where to add value
		 * @param data as value to add
		 */
		private Add(final Lst<E> original, int index, final E data){
			_original = original;
			_index = index;
			_data = data;
		}
		/**
		 * static factory
		 * @param original as given list
		 * @param index index where value will be added
		 * @param data value to add
		 * @return new modified list
		 * @throws Exception if array is out of bound or orginal is null
		 */
		public static <E> Lst<E> fromIndex(final Lst<E> original, int index, final E data){
			if (original==null)
				throw new NullPointerException();
			if (index>= original.size())
				throw new ArrayIndexOutOfBoundsException();
			return new Add<E>(original, index, data);
		}
		/* (non-Javadoc)
		 * @see array.Lst#get(int)
		 */
		public E get(int i) {
			if (i<_index)
				return _original.get(i);
			if (i==_index)
				return _data;
			if (i<size())
				return _original.get(i-1);
			//return null;
			throw new ArrayIndexOutOfBoundsException();
		}
		/* (non-Javadoc)
		 * @see array.Lst#size()
		 */
		public int size() {
			return _original.size()+1;
		}
		/* (non-Javadoc)
		 * @see array.Lst#undo()
		 */
		public Lst<E> undo(){
			return _original;
		}
	}
	/**
	 * @author martin
	 * substring from given list
	 * @param <E>
	 */
	private static class Sub<E> extends Coll<E>{
		public final Lst<E> _original;
		public final int _from,
		                 _to;
		/**
		 * private constructor
		 * @param original as given list
		 * @param from as start of the sub
		 * @param to as end of the sub
		 */
		private Sub(final Lst<E> original, int from, int to) {
			_original = original;
			_from = from;
			_to = to;
		}
		/**
		 * static factory with two index
		 * @param original as given list
		 * @param from as start of the sub list
		 * @param to as end of the sub list
		 * @return new sub list
		 * @throws Exception if from ou to is out of bound or original is null or to < from
		 */
		public static <E> Lst<E> fromIndex(final Lst<E> original, int from, int to){
			if (to < from)
				throw new IllegalArgumentException();
			if (original==null)
				throw new NullPointerException();
			if (to >= original.size())
				throw new ArrayIndexOutOfBoundsException();
			return new Sub<E>(original, from, to);
		}
		/**
		 * static factory from index and size
		 * @param original as given list
		 * @param from as start of the list
		 * @param size as size of the sub
		 * @return new sub list
		 * @throws Exception if index and size out of bound or original is null
		 */
		public static <E> Lst<E> fromRange(final Lst<E> original, int from, int size){
			if (original==null)
				throw new NullPointerException();
			if (from+size >= original.size())
				throw new ArrayIndexOutOfBoundsException();
			return new Sub<E>(original, from, from+size);
		}
		/* (non-Javadoc)
		 * @see array.Lst#get(int)
		 */
		public E get(int i) {
			if (i<size())
				return _original.get(i+_from);
			//return null;
			throw new ArrayIndexOutOfBoundsException();
		}
		/* (non-Javadoc)
		 * @see array.Lst#size()
		 */
		public int size() {
			return _to-_from;
		}
		/* (non-Javadoc)
		 * @see array.Lst#undo()
		 */
		public Lst<E> undo(){
			return _original;
		}

	}
	/**
	 * @author martin
	 * strip part of the list
	 * @param <E>
	 */
	private static class Strip<E> extends Coll<E>{
		private final Lst<E> _original;
		private final int _from,
		                  _to;
		/**
		 * private constructor
		 * @param original
		 * @param from
		 * @param to
		 */
		private Strip(final Lst<E> original, int from, int to){
			_original = original;
			_from = from;
			_to = to;
		}
		/**
		 * static factory
		 * @param original as given list
		 * @param from as start of the strip
		 * @param to as end of the strip
		 * @return as modified list
		 * @throws Exception if from to as out of bound or original is null or to < from
		 */
		public static <E> Lst<E> fromIndex(final Lst<E> original, int from, int to){
			if (to < from)
				throw new IllegalArgumentException();
			if (to >= original.size())
				throw new ArrayIndexOutOfBoundsException();
			if (original == null)
				throw new NullPointerException();
			return new Strip<E>(original, from, to);
		}
		/* (non-Javadoc)
		 * @see array.Lst#get(int)
		 */
		public E get(int i) {
			if (i < _from)
				return _original.get(i);
			if (i < size())
				return _original.get(i+(_to-_from));
			//return null;
			throw new ArrayIndexOutOfBoundsException();
		}
		/* (non-Javadoc)
		 * @see array.Lst#size()
		 */
		public int size() {
			return _original.size()-(_to-_from);
		}
		/* (non-Javadoc)
		 * @see array.Lst#undo()
		 */
		public Lst<E> undo(){
			return _original;
		}
	}
	/**
	 * @author martin
	 * insert Lst into another
	 * @param <E>
	 */
	private static class Insert<E> extends Coll<E>{
		private final Lst<E> _superLst,
		                     _insertion;
		private final int _from,
		                  _to;
		/**
		 * private constructor
		 * @param superLst as list to insert in
		 * @param insertion as insertion
		 * @param from start index to mask
		 * @param to end index to mask
		 */
		private Insert(final Lst<E> superLst, final Lst<E> insertion, int from, int to) {
			_superLst = superLst;
			_insertion = insertion;
			_from = from;
			_to = to;
		}
		/**
		 * static factory with from to index
		 * @param superLst as list
		 * @param from as start index
		 * @param to as destination index
		 * @param insertion as list to insert
		 * @return new modified list
		 */
		public static <E> Lst<E> fromIndex(final Lst<E> superLst, int from, int to, final Lst<E> insertion){
			if (to<from)
				throw new IllegalArgumentException();
			if (superLst == null || insertion == null)
				throw new NullPointerException();
			if (to > superLst.size())
				throw new ArrayIndexOutOfBoundsException();
			return new Insert<E>(superLst, insertion, from, to);
		}
		/**
		 * static factory with from and size
		 * @param superLst as list
		 * @param from as start index to mask
		 * @param size as size of the mask
		 * @param insertion as insertion list
		 * @return new modified list
		 */
		public static <E> Lst<E> fromSize(final Lst<E> superLst, int from, int size, final Lst<E> insertion){
			if (superLst == null || insertion == null)
				throw new NullPointerException();
			if (from+size > superLst.size())
				throw new ArrayIndexOutOfBoundsException();
			return new Insert<E>(superLst, insertion, from, from+size);
		}
		/* (non-Javadoc)
		 * @see coll.Lst#get(int)
		 */
		public E get(int i) {
			if (i<_from)
				return _superLst.get(i);
			if (i<_from+_insertion.size())
				return _insertion.get(i-_from);
			if (i < size())
				return _superLst.get(i-_insertion.size()+(_to-_from));
			return null;
		}
		/* (non-Javadoc)
		 * @see coll.Lst#size()
		 */
		public int size() {
			return _superLst.size() - (_to-_from) + _insertion.size();
		}
		/* (non-Javadoc)
		 * @see coll.Lst#undo()
		 */
		public Lst<E> undo() {
			return _superLst;
		}
	}
	/**
	 * @author martin
	 *push value in front of the the list
	 * @param <E>
	 */
	private static class Push<E> extends Coll<E>{
		private final Lst<E> _lst;
		private final E _val;
		/**
		 * private constructor
		 * @param lst as list to increase
		 * @param val as value to insert
		 */
		private Push(final Lst<E> lst, final E val){
			_lst = lst;
			_val = val;
		}
		/**
		 * static constructor
		 * @param lst as list
		 * @param val as value to push
		 * @return new list with pushed value
		 */
		public static <E> Lst<E> fromVal(final Lst<E> lst, final E val){
			if (lst == null || val == null)
				throw new NullPointerException();
			return new Push<E>(lst,val);
		}
		/* (non-Javadoc)
		 * @see coll.Lst#get(int)
		 */
		public E get(int i) {
			if (i==0)
				return _val;
			if (_lst.size()+1 > i)
				return _lst.get(i-1);
			throw new ArrayIndexOutOfBoundsException();
		}
		/* (non-Javadoc)
		 * @see coll.Lst#size()
		 */
		public int size() {
			return _lst.size()+1;
		}
		/* (non-Javadoc)
		 * @see coll.Lst#undo()
		 */
		public Lst<E> undo() {
			return _lst;
		}
	}
	/**
	 * @author martin
	 * pop first index of the array
	 * @param <E>
	 */
	private static class Pop<E> extends Coll<E>{
		private final Lst<E> _lst;
		/**
		 * private constructor
		 * @param lst as list to increase
		 */
		private Pop(final Lst<E> lst){
			_lst = lst;
		}
		/**
		 * static constructor
		 * @param lst as list
		 * @return new list decreased size
		 */
		public static <E> Lst<E> fromNothing(final Lst<E> lst){
			if (lst == null)
				throw new NullPointerException();
			return new Pop<E>(lst);
		}
		/* (non-Javadoc)
		 * @see coll.Lst#get(int)
		 */
		public E get(int i) {
			if (i < _lst.size()-1)
				return _lst.get(i+1);
			throw new ArrayIndexOutOfBoundsException();

		}
		/* (non-Javadoc)
		 * @see coll.Lst#size()
		 */
		public int size() {
			return _lst.size()-1;
		}
		/* (non-Javadoc)
		 * @see coll.Lst#undo()
		 */
		public Lst<E> undo() {
			return _lst;
		}
	}

	/**
	 * @author martin
	 *list size limiter
	 * @param <E>
	 */
	private static class Limit<E> extends Coll<E>{
		private final Lst<E> _lst;
		private final int _limit;
		/**
		 * private factory
		 * @param lst as list to limit size
		 * @param limit as new size
		 */
		private Limit(final Lst<E> lst, int limit){
			_lst = lst;
			_limit = limit;
		}
		/**
		 * static factory
		 * @param lst as list to limit size
		 * @param size as new size
		 * @return new list with new size
		 */
		public static <E> Lst<E> fromSize(final Lst<E> lst, int size){
			if (lst == null)
				throw new NullPointerException();
			if (size<0)
				throw new IllegalArgumentException();
			return new Limit<E>(lst,size);
		}
		/* (non-Javadoc)
		 * @see coll.Lst#get(int)
		 */
		public E get(int i) {
			if (i >= _limit)
				throw new ArrayIndexOutOfBoundsException();
			if (i >= _lst.size())
				return null;
			if (i < 0)
				throw new IllegalArgumentException();
			return _lst.get(i);
		}
		/* (non-Javadoc)
		 * @see coll.Lst#size()
		 */
		public int size() {
			return _limit;
		}
		/* (non-Javadoc)
		 * @see coll.Lst#undo()
		 */
		public Lst<E> undo() {
			return _lst;
		}
	}
}