package LinkedList
import NoWurst
import Wurstunit

public class LinkedList<T>
	private LLEntry<T> dummy
	protected int size = 0

	/** create a new, empty list */
	construct()
		dummy =  new LLEntry<T>(null, null, null)
		dummy.next = dummy
		dummy.prev = dummy

	/** add an element to the end of the list */
	function add(T elem)
		let entry = new LLEntry<T>(elem, dummy.prev, dummy)
		dummy.prev.next = entry
		dummy.prev = entry
		size ++

	/** add all elements from elems to the end of this list */
	function addAll(LinkedList<T> elems)
		for T elem in elems
			add(elem)

	/** remove element at index */
	function removeAt(int index)
		let e = getEntry(index)
		e.prev.next = e.next
		e.next.prev = e.prev
		destroy e
		size--

	/** removes the first occurence of t from this list */
	function remove(T t)
		LLEntry<T> r = dummy.next
		while r != dummy
			if r.elem == t
				r.prev.next = r.next
				r.next.prev = r.prev
				destroy r
				size--
				return
			r = r.next

	/** gets the size of the list */
	function getSize() returns int
		return size

	function contains(T elem) returns boolean
		LLEntry<T> r = dummy.next
		while r != dummy
			if r.elem == elem
				return true
			r = r.next
		return false

	private function getEntry(int index) returns LLEntry<T>
		LLEntry<T> r = dummy
		for int i = 0 to index
			r = r.next
		return r

	/** get the element at the specified index */
	function get(int index) returns T
		return getEntry(index).elem

	/** get an iterator for this list */
	function iterator() returns LLIterator<T>
		return new LLIterator(this, dummy)

	/** get an iterator for this list */
	function backiterator() returns LLBIterator<T>
		return new LLBIterator(dummy)

	/** adds an element to the beginning of the list */
	function addtoStart(T elem)
		let entry = new LLEntry<T>(elem, dummy, dummy.next)
		dummy.next.prev = entry
		dummy.next = entry
		size ++

	/** replaces the first occurence of 'whichElement' with 'newElement'
		returns true when an element has been replaced,
		false if 'whichelement' is not contained in the list
	*/
	function replace(T whichElement, T newElement) returns boolean
		LLEntry<T> current = dummy.next
		while current != dummy
			if current.elem == whichElement
				current.elem = newElement
				return true
			current = current.next
		return false

	ondestroy
		LLEntry<T> current = dummy.next
		while current != dummy
			current = current.next
			destroy current.prev
		destroy dummy

	function removeWhen(LinkedListPredicate<T> predicate)
		LLEntry<T> r = dummy.next
		while r != dummy
			if predicate.isTrueFor(r.elem)
				r.prev.next = r.next
				r.next.prev = r.prev
				destroy r
				size--
			r = r.next
		destroy predicate

	function updateAll(LinkedListUpdater<T> f)
		LLEntry<T> r = dummy.next
		while r != dummy
			r.elem = f.update(r.elem)
			r = r.next
		destroy f

	function toString() returns string
		string s="["
		var first = true
		for e in this
			if not first
				s += ", "
			s += I2S(e castTo int)
			first = false
		return s + "]"

class LLEntry<S>
	S elem
	LLEntry<S> prev
	LLEntry<S> next

	construct(S elem, LLEntry<S> prev, LLEntry<S> next)
		this.elem = elem
		this.prev = prev
		this.next = next

public class LLIterator<Q>
	LLEntry<Q>    dummy
	LLEntry<Q>    current
	LinkedList<Q> parent

	construct(LinkedList<Q> parent, LLEntry<Q> dummy)
		this.parent  = parent
		this.dummy   = dummy
		this.current = dummy

	/** remove the current element from the list */
	function remove()
		if current != dummy
			parent.size--
			current.next.prev = current.prev
			current.prev.next = current.next
			let removedNode   = current
			current           = current.prev
			destroy removedNode


	function hasNext() returns boolean
		return current.next != dummy

	function next() returns Q
		current = current.next
		return current.elem

	function close()
		destroy this

public class LLBIterator<Q>
	LLEntry<Q> dummy
	LLEntry<Q> current

	construct(LLEntry<Q> dummy)
		this.dummy = dummy
		this.current = dummy

	function hasNext() returns boolean
		return current.prev != dummy

	function next() returns Q
		current = current.prev
		return current.elem

	function close()
		destroy this



public interface LinkedListPredicate<T>
	function isTrueFor(T t) returns boolean

public interface LinkedListUpdater<T>
	function update(T t) returns T


@test function checkSizeWorks()
	let ll = new LinkedList<int>()..add(1)..add(2)..add(3)

	ll.getSize().assertEquals(3)

	let iter = ll.iterator()
	for x from iter
		if x % 2 == 1
			iter.remove()
	iter.close()

	var ctr = 100
	let iter2 = ll.iterator()
	for _ from iter2
		ctr++

	ctr.assertEquals(101)

	ll.getSize().assertEquals(1)