SeekableList.java

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

// The following are required for implementing the Iterable and Iterator interfaces. 
import java.lang.Iterable;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class SeekableList<T> {
	private List<T> list;

	public SeekableList(List<T> list){
		this.list = list;
	}

	public T getValue(int pos){
		return list.get(pos);
	}

	/*
		Here we have an inner class, Element. An inner class is a bit like the idea of a closure, if you've ever heard of that.
		Basically, it is a class that can use information (instance variables, methods, and type variables) in the enclosing class.
		In Element, calls are made to methods on the enclosing class (SeekableList), like getElement() and getValue().
		Additionally, you'll see that an inner class has access to the type variables (T) present in the enclosing class. So the method
		value() can return whatever type T is contained in the outer class' list.
		Yet, we do not declare the inner class with "Element<T>" - the <T> belongs to the enclosing class, but the inner can access it.
		So, declarations of this class (seen in main() method) look like "SeekableList<String>.Element".

		The purpose of the Element class is to provide an abstraction over a specific location in a SeekableList. It knows it's own position
		and the value at this position, and it also knows what is next to it and before it in the list. This makes it easier for us to navigate
		lists in nontrivial ways, like going backward or looking 2 spaces ahead.
	*/
	public class Element {
		// This Element's position in the containing list. It is declared final to indicate that its position doesn't change-
		// to get a different postition you get a different Element on the same list.
		private final int pos;

		public Element(int pos){
			this.pos = pos;
		}

		public int pos(){
			return pos;
		}

		public Element next(){
			return getElement(pos + 1);
		}

		public Element prev(){
			return getElement(pos - 1);
		}

		public T value(){
			return getValue(pos);
		}
	}

	/*
		Returns an instance of the Element inner class at a particular position in the list.
		Returns null if the position is out of bounds.
	*/
	public Element getElement(int pos){
		if (pos >= list.size() || pos < 0){
			return null;
		}

		return new Element(pos);
	}

	/*
		Method allowing us to iterate through a SeekableList. This uses the java Iterable and Iterator interfaces,
		which together allow us to use java's "for each" syntax (seen in the main() method).

		There is a lot going on here, and completely understanding how this works is a task that requires seeing a lot more code than this.
		There are 2 pieces of new syntax used here: lambda expressions and anonymous classes. These 2 features are working together to make
		the declaration of this iterator more concise. And if you understand the two above concepts, there is no loss in clarity.

		Before explaining the syntax, it's necessary to explain Iterable and Iterator. These 2 interfaces are required by java to do iteration.
		While it is relatively clunky to have to implement 2 interfaces just to get iteration, the idea is that if you write these two clunky things once,
		you avoid writing many more clunky things down the line.

		The basic way Iterable and Iterator work is:
			- An Iterable (ie. an instance of a class implementing the Iterable interface) has a method iterator()
				which returns an Iterator (ie. an instance of a class implementing the Iterator interface).
			- An Iterator has methods hasNext() and next() which maintain and update information about the sequence of values to iterate over.
			- Java uses "for each" syntax to hide everything done by the Iterable and Iterator and just expose the values iterated over.

		Now onto lambda expressions and anonymous classes.
		Let's say you decide to implement Iterable and Iterator over SeekableList. The default approach would be to create 2 new classes:
			(NOTE: The below are examples of what NOT to do)
			- class SeekableListIterable<T> implements Iterable<T>
			- class SeekableListIterator<T> implements Iterator<T>
		And you'd have to create 2 new files, one for each of these classes, and link them up with imports, etc. It would be bad for the code's readability.

		A slightly more concise approach is to use inner classes (like Element described above). You'd have 2 inner classes, one
		implementing Iterable and one implementing Iterator. This way you wouldn't have to create any extra files, which is good.
		And you would be able to access SeekableList's methods and type variables so you wouldn't have to repeat those things or type them out more verbosely.
		However, you'd still have 2 whole extra inner class definitions just to write the iterator(), hasNext() and next() methods.

		So the next improvement you can use is anonymous classes. This allows you to declare a class implementing a particular interface,
		without having to name that class. The idea is that all you care about are the methods required by the interface, and you do not expect
		to refer to the class itself anywhere- you will only ever use it in the context it appears, as an actual instance you can call the methods on.
		You can see the use of an anonymous class below, at "new Iterator<Element> () { ... }"
		What this does is creates an anonymous (unnamed) class which implements the Iterator interface, with all of the methods defined inside the "{ ... }",
		and it automatically creates an instance of this anonymous class and returns it.
		So, the type of the return value of "new Iterator<Element> () { ... }" is Iterator<Element>.

		The final improvement is lambda expressions. This can be thought of as a further shortening of the anonymous class syntax.
		Whereas anonymous classes can be used to implement any interface, lambda expressions can only be used to implement interfaces with a single method.
		So, because the Iterator interface has 2 methods (hasNext() and next()), a lambda expression cannot be used for it.
		However, the Iterable interface has a single method, iterator(). This means we can use a lambda expression to create an anonymous Iterable
		very concisely. Since there is only 1 required method (iterator()), we don't need to write its name, and we save having to type.

		The lambda expression used here is the "() -> ...". The "()" is an empty argument list (the iterator() method takes no arguments),
		and the "..." is an expression (NOT a statement or method body - no ; or "return" allowed) which returns the type expected by the interface that
		the lambda expression implements (in this case, the interface is Iterable<Element>, and so the return type of iterator() is Iterator<Element>).
		The "->" is just the symbol that separates the argument list "()" and the expression to return "...".

		So, putting it all together. We have a method elements() that returns an Iterable<Element>. It does this by using a lambda expression to
		create an anonymous class implementing Iterable<Element>, whose only required method is iterator(). The anonymous Iterable<Element> class
		must have this method return an Iterator<Element>. It does this by using anonymous class syntax to make an anonymous class implementing
		Iterator<Element>, and defining its hasNext() and next() methods.
	*/
	public Iterable<Element> elements() {
		return () -> new Iterator<Element> () {
			private Element elt = getElement(0); //start at position 0

			public boolean hasNext() {
				return elt != null;
			}

			public Element next() {
				if (!hasNext()){
					throw new NoSuchElementException(); //required by Iterator interface to throw this
				}
				Element oldElt = elt;
				elt = oldElt.next();
				return oldElt;
			}
		};
	}


	/*
		Here we demonstrate iterating through a SeekableList, and doing interesting things like
		looking at next and previous elements in the list while iterating through it.
	*/
	public static void main(String[] args){
		String[] values = {"a", "b", "c", "d", "e"};
		List<String> list = Arrays.asList(values);
		// we create a SeekableList from an existing underlying list, so we don't have to bother writing the methods for adding/removing/setting
		SeekableList<String> seekable = new SeekableList<String>(list);

		/*
			Here we use java's "for each" syntax. It works very similar to a for loop, but it is more concise.
			It is required that the expression after the ":" return an Iterable. Then behind the scenes java uses
			the hasNext() and next() methods on the Iterator returned by the Iterable to progress through the for loop.

			Here is how the for each syntax would be translated into normal for loop syntax:

			Iterable<SeekableList<String>.Element> iterable = seekable.elements();
			Iterator<SeekableList<String>.Element> iterator = iterable.iterator();
			if (iterator.hasNext()) {
				for (SeekableList<String>.Element elt = iterator.next(); iterator.hasNext(); elt = iterator.next()) { ... }
			}

			As you can see, it's way uglier.
		*/
		for (SeekableList<String>.Element elt : seekable.elements()) {
			int pos = elt.pos();
			String cur = elt.value();
			String prev = " ";
			String next = " ";
			String next2 = " ";
			if (elt.prev() != null) {
				prev = elt.prev().value();
			}
			if (elt.next() != null) {
				SeekableList<String>.Element nextElt = elt.next();
				next = nextElt.value();
				if (nextElt.next() != null){
					next2 = nextElt.next().value();
				}
			}
			System.out.println("At position " + pos + ", prev = " + prev + ", cur = " + cur + ", next = " + next +", next2 = " + next2);
		}
	}
}