package com.lightspeedtyrannosaurus.util;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Random;

/**
 * An implementation of William Pugh's skip list.
 * <code>null</code> elements are not allowed; attempting to add one will
 * cause an IllegalArgumentException to be thrown.
 * <p>
 * See <a href="ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf">
 * ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf</a> for more onformation on
 * skip lists.
 * 
 * @author  Eugene Kenny
 * @param <E> the type of elements held in this collection.
 */
public final class SkipList<E extends Comparable<E>>
	implements Collection<E>, Cloneable {

	/**
	 * The proportion of links present in one level that will also be present
	 * a level higher. In other words; if level <code>i</code> has
	 * <code>x</code> links, level <code>i+1</code> will have
	 * <code>x*DISTRIBUTION</code> links.
	 */
	private static final double DISTRIBUTION = 0.5;

	/**
	 * The maximum level an element may exist at.
	 * The actual the maximum level is <code>MAX_LEVEL - 1</code>,
	 * to account for array indexing from 0.
	 */
	private static final int MAX_LEVEL = 16;

	/**
	 * A dummy node at the start of the list.
	 */
	private SkipListNode<E> head;

	/**
	 * How many elements are currently stored in the list.
	 */
	private int size;

	/**
	 * The highest level any node in this SkipList currently has.
	 */
	private int level;

	/**
	 * Constructs an empty list.
	 */
	public SkipList() {
		clear();
	}

	/**
	 * Constructs a list containing the elements of the specified collection,
	 * in the order they are returned by the collection's iterator.
	 * 
	 * @param c the collection whose elements are to be placed into this list. 
	 */
	public SkipList(final Collection<? extends E> c) {
		this();
		if (c == null) {
			throw new IllegalArgumentException(); 
		}
		addAll(c);
	}

	/**
	 * Gets a random number between 0 and <code>MAX_LEVEL</code>, with
	 * successive logarithmic probability of <code>DISTRIBUTION</code>.
	 * 
	 * @return a number in the range <code>[0 - MAX_LEVEL}</code>.
	 */
	private int randomLevel() {
		int lvl = 1;
		while (Math.random() < DISTRIBUTION && lvl < MAX_LEVEL) {
			lvl++;
		}
		return lvl;
	}

	/**
	 * Adds the provided element to the list, according to its natural ordering.
	 * 
	 * @param e the element to add.
	 * @return true.
	 */
	@Override
	public boolean add(final E e) {
		if (e == null) {
			String err = "SkipLists cannot contain null elements.";
			throw new IllegalArgumentException(err);
		}
		List<SkipListNode<E>> update = new LinkedList<SkipListNode<E>>();
		SkipListNode<E> curr = head;
		for (int i = level; i >= 0; i--) {
			while (curr.getSkip(i) != null
				&& curr.getSkip(i).element.compareTo(e) < 0) {
				curr = curr.getSkip(i);
			}
			update.add(0, curr);
		}
		curr = curr.getSkip(0);
		if (curr == null || !curr.element.equals(e)) {
			int lvl = randomLevel();
			if (lvl > level) {
				for (int i = level; i < lvl; i++) {
					update.add(head);
				}
				level = lvl;
			}
			SkipListNode<E> ins = new SkipListNode<E>(e);
			for (int i = 0; i < lvl; i++) {
				ins.nexts.add(update.get(i).getSkip(i));
				update.get(i).setSkip(i, ins);
			}
		}
		size++;
		return true;
	}

	/**
	 * Adds the contents of the collection <code>c</code> to this list.
	 * 
	 * @param c collection containing elements to be added to this collection.
	 * @return true.
	 */
	@Override
	public boolean addAll(final Collection<? extends E> c) {
		Iterator<? extends E> it = c.iterator();
		for (int i = 0; i < c.size(); i++) {
			add(it.next());
		}
		return true;
	}

	/**
	 * Removes everything from this list.
	 */
	@Override
	public void clear() {
		head = new SkipListNode<E>(null);
		size = 0;
		level = 0;
	}

	/**
	 * Checks whether this SkipList contains the object <code>o</code>.
	 * 
	 * @param o element whose presence in this list is to be tested.
	 * @return true if this collection contains the element <code>o</code>
	 */
	@Override
	public boolean contains(final Object o) {
		if (o == null) {
			return false;
		}
		E eo;
		try {
			eo = (E) o;
		} catch (ClassCastException cce) {
			return false;
		}
		LinkedList<SkipListNode<E>> update = new LinkedList<SkipListNode<E>>();
		SkipListNode<E> curr = head;
		for (int i = level; i >= 0; i--) {
			while (curr.getSkip(i) != null
				&& curr.getSkip(i).element.compareTo(eo) < 0) {
				curr = curr.getSkip(i);
			}
			update.add(0, curr);
		}
		curr = curr.getSkip(0);
		return (curr != null && curr.element.equals(o));
	}

	/**
	 * Checks whether this SkipList contains every element in the collection c.
	 * 
	 * @param c collection to be checked for containment in this collection.
	 * @return true if this collection contains all of the elements in c.
	 */
	@Override
	public boolean containsAll(final Collection<?> c) {
		if (c == null) {
			throw new IllegalArgumentException();
		}
		Iterator<?> it = c.iterator();
		for (int i = 0; i < c.size(); i++) {
			if (!contains(it.next())) {
				return false;
			}
		}
		return true;
	}

	/**
	 * Checks whether this collection is empty, i.e. if it contains anything.
	 * @return true if this collection contains no elements.
	 */
	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * Gets an Iterator to walk through the elements in the list.
	 * 
	 * @return an iterator over this collection.
	 */
	@Override
	public Iterator<E> iterator() {
		return new SkipListIterator();
	}

	/**
	 * Removes the first occurrence of the specified element from this list,
     * if it is present.
	 * 
	 * @param o element to be removed from this collection, if present.
	 * @return true if an element was removed as a result of this call.
	 */
	@Override
	public boolean remove(final Object o) {
		if (o == null) {
			String err = "SkipLists cannot contain null elements.";
			throw new IllegalArgumentException(err);
		}
		E eo;
		try {
			eo = (E) o;
		} catch (ClassCastException cce) {
			return false;
		}
		LinkedList<SkipListNode<E>> update = new LinkedList<SkipListNode<E>>();
		SkipListNode<E> curr = head;
		for (int i = level; i >= 0; i--) {
			while (curr.getSkip(i) != null
				&& curr.getSkip(i).element.compareTo(eo) < 0) {
				curr = curr.getSkip(i);
			}
			update.add(0, curr);
		}
		curr = curr.getSkip(0);
		if (curr != null && curr.element.equals(eo)) {
			for (int i = 0; i < level; i++) {
				if (update.get(i).getSkip(i) != curr) {
					break;
				}
				update.get(i).setSkip(i, curr.getSkip(i));
			}
		}
		while (level > 1 && head.getSkip(level) == null) {
			level--;
		}
		size--;
		return true;
	}

	/**
	 * Removes all of this collection's elements that are
	 * also contained in the specified collection.
	 * 
	 * @param c collection of elements to be removed from this collection.
	 * @return true if this collection changed as a result of the call.
	 */
	@Override
	public boolean removeAll(final Collection<?> c) {
		Iterator<?> it = c.iterator();
		for (int i = 0; i < c.size(); i++) {
			remove(it.next());
		}
		return true;
	}

	/**
	 * Retains only the elements in this collection that are contained
	 * in the specified collection.
	 * 
	 * @param c the elements to be retained in this collection.
	 * @return true if this collection changed as a result of the call.
	 */
	@Override
	public boolean retainAll(final Collection<?> c) {
		boolean modified = false;
		Iterator<E> e = iterator();
		while (e.hasNext()) {
		    if (!c.contains(e.next())) {
			e.remove();
			modified = true;
		    }
		}
		return modified;
	}

	/**
	 * Returns the number of elements in this list.
	 * 
	 * @return The number of elements in this list.
	 */
	@Override
	public int size() {
		return size;
	}

	/**
	 * Returns an array containing all of the elements in this list
     * in proper sequence (from first to last element).
     * 
     * @return an array containing the elements of the list.
	 */
	@Override
	public Object[] toArray() {
		Object[] ret = new Object[size()];
		SkipListNode<E> curr = head;
		for (int i = 0; i < size(); i++) {
			curr = curr.getSkip(0);
			ret[i] = curr.element;
		}
		return ret;
	}

	/**
	 * Returns an array containing all of the elements in this list in
     * proper sequence (from first to last element); the runtime type of
     * the returned array is that of the specified array.  If the list fits
     * in the specified array, it is returned therein.  Otherwise, a new
     * array is allocated with the runtime type of the specified array and
     * the size of this list.
     * 
     * @param a the array to store the elements in, if they fit.
     * @param <T> the type of array to return.
     * @return an array containing the elements of the list.
	 */
	@Override
	public <T> T[] toArray(final T[] a) {
		Object[] ret;
		if (a.length < size()) {
			ret = toArray();
		} else {
			ret = a;
			SkipListNode<E> curr = head;
			for (int i = 0; i < size(); i++) {
				curr = curr.getSkip(0);
				ret[i] = curr.element;
			}
			if (a.length > size()) {
				a[size()] = null;
			}
		}
		return (T[]) ret;
	}

	/**
	 * Returns a shallow copy of this <code>LinkedList</code>.
	 * (The elements themselves are not cloned.)
     *
     * @return a shallow copy of this <tt>LinkedList</tt> instance
	 */
	@Override
	public Object clone() {
		SkipList<E> clone = null;
		try {
			clone = (SkipList<E>) super.clone();
		} catch (CloneNotSupportedException e) {
			throw new InternalError();
		}

		clone.clear();
		clone.addAll(this);

		return clone;
	}

	/**
	 * A node in the SkipList.
	 * @author Eugene Kenny
	 * @param <T> The type this is a wrapper for, can be any class.
	 */
	private final class SkipListNode<T extends Comparable<T>>
			implements Comparable<SkipListNode<T>> {

		/**
		 * The set of pointers to next elements on each level.
		 * May not be the right size, so getSkip() and setSkip() should be used.
		 */
		private List<SkipListNode<T>> nexts;

		/**
		 * The object this node is wrapping.
		 */
		private T element;

		/**
		 * 
		 * 
		 * @param elem the element to be stored at this node.
		 */
		private SkipListNode(final T elem) {
			element = elem;
			nexts = new ArrayList<SkipListNode<T>>();
		}

		/**
		 * Gets the next node in this list on the specified level.
		 * 
		 * @param lvl which level to get the next node from.
		 * @return the SkipListNode after this one on level <code>lvl</code>.
		 */
		public SkipListNode<T> getSkip(final int lvl) {
			if (lvl < nexts.size()) {
				return nexts.get(lvl);
			} else {
				return null;
			}
		}

		/**
		 * Sets the node after this on the specified level.
		 * 
		 * @param lvl which level to set the next node on.
		 * @param ins the SkipListNode to be set next on level <code>lvl</code>.
		 */
		public void setSkip(final int lvl, final SkipListNode<T> ins) {
			if (lvl < nexts.size()) {
				nexts.set(lvl, ins);
			} else {
				while (lvl >= nexts.size()) {
					nexts.add(null);
				}
				nexts.set(lvl, ins);
			}
		}

		/**
		 * Compares the elements <code>this</code> and <code>o</code> contain,
		 * and returns their natural order.
		 * 
		 * @param o the object to be compared.
		 * @return a negative integer, zero, or a positive integer as this
		 * object is less than, equal to, or greater than the specified object.
		 */
		@Override
		public int compareTo(final SkipListNode<T> o) {
			return o.element.compareTo(element);
		}
		
		/**
		 * Checks if this equals o, by comparing their <code>element</code>s.
		 * 
		 * @param o the other object to check for equality.
		 * @return whether the two nodes' elements are equal.
		 */
		@Override
		public boolean equals(final Object o) {
			if (o == null) {
				return false;
			}
			SkipListNode<T> to;
			try {
				to = (SkipListNode<T>) o;
			} catch (ClassCastException cce) {
				return false;
			}
			return to.element.equals(element);
		}
		
		/**
		 * Provides a hashCode by simply taking that of the node's element.
		 * 
		 * @return the hashCode of this node's element.
		 */
		@Override
		public int hashCode() {
			return element.hashCode();
		}
	}

	/**
	 * An Iterator to walk over the elements in a SkipList.
	 * @author Eugene Kenny
	 */
	private final class SkipListIterator implements Iterator<E> {

		/**
		 * The last node returned.
		 */
		private SkipListNode<E> last;

		/**
		 * Initialise a SkipListIterator pointing to the head of the list.
		 */
		public SkipListIterator() {
			last = head;
		}

		/**
		 * Returns true if the iterator has more elements. (In other words,
		 * returns true if next would return an element rather than throwing
		 * an exception.)
		 * 
		 * @return true if the iterator has more elements.
		 */
		@Override
		public boolean hasNext() {
			return (last.getSkip(0) == null);
		}

		/**
		 * Returns the next element in the iteration.
		 * 
		 * @return the next element in the iteration.
		 */
		@Override
		public E next() {
			SkipListNode<E> nodey = last.getSkip(0);
			if (nodey == null) {
				throw new NoSuchElementException();
			}
			last = nodey;
			return last.element;
		}

		/**
		 * Removes the last element fetched from the collection this Iterator
		 * is iterating over.
		 */
		@Override
		public void remove() {
			if (last == head) {
				throw new IllegalStateException();
			}
			SkipList.this.remove(last);
		}
	}

	/**
	 * Tests SkipList by creating one full of random integers.
	 * @param args Command line arguments (ignored).
	 */
	public static void main(final String[] args) {
		final int seed = 42;
		final int testSize = 1420;
		
		Random rand = new Random(seed);
		SkipList<Integer> ints = new SkipList<Integer>();
		List<Integer> intlist = new LinkedList<Integer>();
		
		for (int i = 0; i < testSize; i++) {
			intlist.add(Integer.valueOf(rand.nextInt()));
		}
		ints.addAll(intlist);
		
		for (int i = ints.level; i >= 0; i--) {
			SkipList<Integer>.SkipListNode<Integer> curr = ints.head;
			while (curr.getSkip(i) != null) {
				System.out.print(curr.getSkip(i).element + "\t");
				curr = curr.getSkip(i);
			}
			System.out.println("");
		}
	}
}