/*
 * This class creates a simple singly-linked list 
 * It illustrates recursion, iterators and list manipulation
 */

import java.util.*;
public class MyList implements Iterable<Integer> {
	private Node head;
	
	/*
	 * numberOfElements - number of elements to generate
	 * seed - for random number generation
	 * range - Controls the range (from 0 up to range-1 (inclusive))
	 */
	public MyList(int numberOfElements, long seed, int range) {
		head = new Node(1); // Autoboxing allow us to pass 1 to constructor
		Node curr = head;
		Random random = new Random(seed);
		for (int i=2; i<=numberOfElements; i++) { 
			curr.next = new Node(random.nextInt(range));
			curr = curr.next;
		}
	}
	
	public String toString() {
		String result = "";
	
		Node curr = head;
		while (curr != null) {
			result += curr.data;
			if (curr.next != null) 
				result += ", ";
			curr = curr.next;
		}
		return result;
	}
	
	public String reversePrinting() {
		return reversePrinting(head);
	}
	
	/* real recursion occurs via this method */
	private String reversePrinting(Node curr) {
		if (curr.next == null)
			return String.valueOf(curr.data);
		else {
			return reversePrinting(curr.next) + ", " + curr.data;
		}
	}
		
	public int findNumberOfInstances(Integer data) {
		return findNumberOfInstances(head, data);
	}
	
	/* real recursion occurs via this method */
	private int findNumberOfInstances(Node curr, Integer data) {
		if (curr == null)
			return 0;
		else if (curr.data.equals(data))
			return 1 + findNumberOfInstances(curr.next, data);
		else
			return findNumberOfInstances(curr.next, data);
	}
	
	/* Inner class representing the iterator */
	public class MyListIteratorOne implements Iterator<Integer> {
		private Node curr;
		
		public MyListIteratorOne() {
			curr = head;
		}
		
		public Integer next() {
			Integer temp = curr.data;
			curr = curr.next;
			return temp;
		}
		
		public boolean hasNext() {
			return (curr!=null ? true : false);
		}
		
		public void remove() {
			/* Left as exercise */
		}
	}
	
	public Iterator<Integer> iterator() {
		return new MyListIteratorOne();
	}
	
	/* Support Node class */
	private class Node {
		Node next;
		Integer data;
		public Node(Integer data) {
			next = null;
			this.data = data;
		}
	}
	
	public static void main(String[] args) {
		long seed = 123;
		int range = 100, numberOfElements = 10;
		
		MyList myList = new MyList(numberOfElements, seed, range);
		System.out.println("Original List:\n" + myList);
		System.out.println("Reversed List:\n" + myList.reversePrinting());
		
		int value = 95;
		System.out.println("Instances of " + value + ": " + myList.findNumberOfInstances(value));
		
		System.out.println("Using iterators:");
		Iterator<Integer> iterator = myList.iterator();
		while (iterator.hasNext()) {
			System.out.println(iterator.next());
		}
		
		/* The next statement is possible because MyList implements */
		/* the Iterable<Integer> interface */
		System.out.println("Using the new for loop construct:");
		for (Integer element : myList) {
			System.out.println(element);
		}
	}
}