import java.util.Iterator;

public class CircularLinkedList<Type> {
	private CircularListNode<Type> accessPoint;
	
	public CircularLinkedList(Type element) {
		accessPoint = new CircularListNode<Type>(element);
		accessPoint.setNext(accessPoint);
	}
	
	public CircularListNode<Type> getFirst() {
		return accessPoint;
	}
	
	public static void main(String[] args) {
		// Using the most basic implementation.
		CircularLinkedList<String> list = new CircularLinkedList<String>("A");
		
		CircularListNode<String> node = list.getFirst();
		node.setNext(new CircularListNode<String>("B"));
		node.getNext().setNext(new CircularListNode<String>("C"));
		node.getNext().getNext().setNext(new CircularListNode<String>("D"));
		
		while (node != null) {
			System.out.println(node);
			node = node.getNext();
		}
		
		// Using add methods and iterator.
		list = new CircularLinkedList<String>("1");
		list.add("2", 1);
		list.add("3", 2);
		list.add("4", 3);
		
		list.remove(2);
		
		CircularIterator<String> iter = list.iterator();
		while (iter.getIterationIndex() < 2) {
			System.out.println(iter.next());
		}
		
		// Add 3 again, reverse list, and print out.
		list.add("3", 2);
		list.reverse();
		iter = list.iterator();
		System.out.println("Reversed list:");
		while (iter.getIterationIndex() < 2) {
			System.out.println(iter.next());
		}
	}
	
	// Extra methods
	
	public void add(Type element, int index) {
		if (index == 0) {
			CircularListNode<Type> newHead = new CircularListNode<Type>(element);
			newHead.setNext(accessPoint);
			CircularListNode<Type> current = accessPoint;
			while (current.getNext() != accessPoint) {
				current = current.getNext();
			}
			current.setNext(newHead);
			accessPoint = newHead;
		} else {
			int count = 1;
			CircularListNode<Type> next = accessPoint;
			while (count < index && next.getNext() != null) {
				next = next.getNext();
				count++;
			}
			CircularListNode<Type> newNode = new CircularListNode<Type>(element);
			newNode.setNext(next.getNext());
			next.setNext(newNode);
		}
	}
	
	public Type remove(int index) {
		int count = 0;
		CircularListNode<Type> current = accessPoint, previous = null;
		
		while (count < index) {
			previous = current;
			current = current.getNext();
			count++;
		}
		
		if (previous == null) {
			while (current.getNext() != accessPoint) {
				current = current.getNext();
			}
			current.setNext(accessPoint.getNext());
			Type element = accessPoint.getElement();
			accessPoint = accessPoint.getNext();
			return element;
		} else {
			Type element = current.getElement();
			previous.setNext(current.getNext());
			return element;
		}
	}
	
	public void reverse() {
		CircularListNode<Type> current = accessPoint, next = accessPoint.getNext();

		while (next != accessPoint) {
			CircularListNode<Type> temp = next;
			next = next.getNext();
			temp.setNext(current);
			current = temp;
		}
		accessPoint = current;
		next.setNext(current);
	}
	
	public CircularIterator<Type> iterator() {
		return new CircularListIterator<Type>(accessPoint);
	}
	
	class CircularListIterator<IteratorType> implements CircularIterator<IteratorType> {
		private CircularListNode<IteratorType> current, accessPoint;
		private int iteration = 0;

		public CircularListIterator(CircularListNode<IteratorType> accessPoint) {
			current = this.accessPoint = accessPoint;
		}
		
		public boolean hasNext() {
			return true;
		}
		
		public IteratorType next() {
			IteratorType next = current.getElement();
			current = current.getNext();
			if (current == accessPoint) {
				iteration++;
			}
			return next;
		}
		
		public int getIterationIndex() {
			return iteration;
		}
		
		public void remove() {
		}
	}
}

class CircularListNode<NodeType> {
	private NodeType element;
	private CircularListNode<NodeType> next;
	
	public CircularListNode(NodeType element) {
		this.element = element;
	}
	
	public void setNext(CircularListNode<NodeType> next) {
		this.next = next;
	}
	
	public CircularListNode<NodeType> getNext() {
		return next;
	}
	
	public NodeType getElement() {
		return element;
	}
	
	public String toString() {
		return element.toString();
	}
}

interface CircularIterator<CircularIteratorType> extends Iterator<CircularIteratorType> {
	public int getIterationIndex();
}