package LinkedList
import NoWurst
import TypeCasting
import ClosureForGroups
// re-exports Integer, String, Real and Printing
import ErrorHandling
import Wurstunit

/**
 * Doubly-linked list implementation that implements all common list, stack and queue operations.
 * Permits all elements (including null).
 * Use the Typecasting package if you require lists of warcraft handles.
 * LinkedLists should be generally used anywhere you need a list, because they are the most versatile
 * and fast in common operations. If you need faster contains or access operations on big lists,
 * use HashList. If you want to limit each element's occurance to one, consider HashSet.
 */
public class LinkedList<T>
	private var dummy = new LLEntry<T>(null, null, null)
	protected var size = 0

	private LLIterator<T> staticItr = null
	private LLBackIterator<T> staticBackItr = null

	/** Creates a new list by copying all elements from another list into it */
	construct(thistype base)
		dummy.next = dummy
		dummy.prev = dummy
		for elem in base
			add(elem)

	/** Creates a new empty list */
	construct()
		dummy.next = dummy
		dummy.prev = dummy

	/** Adds one or more elements to the end of the list (top of stack, beginning of queue) */
	function add(vararg T elems)
		for elem in elems
			let entry = new LLEntry<T>(elem, dummy.prev, dummy)
			dummy.prev.next = entry
			dummy.prev = entry
			size++

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

	/** Adds all elements from the other list to the end of this list and removes them from the provided list.

		It does not add/remove elements internally, only the internal pointers of the list nodes are re-pointed.
		The other list will be empty, but not destroyed. */
	function splice(LinkedList<T> other)
		dummy.prev.next = other.dummy.next
		dummy.prev.next.prev = dummy.prev
		dummy.prev = other.dummy.prev
		dummy.prev.next = dummy
		size += other.size
		other.dummy.next = other.dummy
		other.dummy.prev = other.dummy
		other.size = 0

	/** Returns the element at the specified index.
		Errors if the index is outside [0, size). */
	function get(int index) returns T
		return getEntry(index).elem

	/** Returns the index of the specified element or -1 is it doesn't exist */
	function indexOf(T t) returns int
		var entry = dummy.next
		var idx = 0
		while entry != dummy
			if entry.elem == t
				return idx
			entry = entry.next
			idx++
		return -1

	/** Sets the element at the specified index.
		Errors if the index is outside [0, size). */
	function set(int index, T elem)
		getEntry(index).elem = elem

	/** Adds an element to the end of the list (top of stack, beginning of queue) */
	function push(T elem)
		add(elem)

	/** Returns the first element in the list, or null if it is empty */
	function getFirst() returns T
		return dummy.next.elem

	/** Returns the last element in the list, or null if it is empty */
	function getLast() returns T
		return dummy.prev.elem

	/** Returns and removes the first added Element (FIFO) */
	function dequeue() returns T
		let top = dummy.next
		T result = null
		if top != dummy
			result = top.elem
			removeEntry(top)
		return result

	/** Returns and removes the last added Element (LIFO) */
	function pop() returns T
		let top = dummy.prev
		T result = null
		if top != dummy
			result = top.elem
			removeEntry(top)
		return result

	/** Returns the lastly added Element */
	function peek() returns T
		return getLast()

	/** Returns whether the lists contains the specified element */
	function has(T elem) returns boolean
		var entry = dummy.next
		while entry != dummy
			if entry.elem == elem
				return true
			entry = entry.next
		return false

	/** Removes the element and it's entry at the given index */
	function removeAt(int index) returns T
		let entry = getEntry(index)
		entry.prev.next = entry.next
		entry.next.prev = entry.prev
		let res = entry.elem
		destroy entry
		size--
		return res

	/** Removes the first occurence of t from this list.
		Returns true if an element was removed from the list. */
	function remove(T elem) returns bool
		var result = false
		var entry = dummy.next
		while entry != dummy
			if entry.elem == elem
				removeEntry(entry)
				result = true
				break
			entry = entry.next
		return result

	/** gets the size of the list (java-compat wrapper) */
	function size() returns int
		return size

	/** checks whether this list is empty */
	function isEmpty() returns boolean
		return size == 0

	/** Returns a shallow copy of this list */
	function copy() returns LinkedList<T>
		let list = new LinkedList<T>
		for elem in this
			list.add(elem)
		return list

	/** get the static iterator for this list */
	function staticItr() returns LLIterator<T>
		if staticItr == null
			staticItr = new LLIterator<T>(this, false)
		staticItr.reset()
		return staticItr

	/** get the static back iterator for this list */
	function staticBackItr() returns LLBackIterator<T>
		if staticBackItr == null
			staticBackItr = new LLBackIterator<T>(this)
		staticBackItr.reset()
		return staticBackItr

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

	/** get a backiterator for this list */
	function backiterator() returns LLBackIterator<T>
		return new LLBackIterator(this)

	/** adds an element to the beginning of the list */
	function enqueue(T elem)
		add(elem)

	/** 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
		var current = dummy.next
		while current != dummy
			if current.elem == whichElement
				current.elem = newElement
				return true
			current = current.next
		return false

	/** Removes the element if the predicates returns true */
	function removeIf(LinkedListPredicate<T> predicate)
		let itr = iterator()
		for elem from itr
			if predicate.isTrueFor(elem)
				itr.remove()
		itr.close()

		destroy predicate

	/** Executes the closure for each element */
	function forEach(LLItrClosure<T> itr) returns LinkedList<T>
		var r = dummy.next
		while r != dummy
			itr.run(r.elem)
			r = r.next
		destroy itr
		return this

	/** Updates all elements */
	function updateAll(LinkedListUpdater<T> f)
		var r = dummy.next
		while r != dummy
			r.elem = f.update(r.elem)
			r = r.next
		destroy f

	/** Performs a Fisher-Yates shuffle on this list.
		Permutes the elements in place - no nodes are destroyed or reallocated. */
	function shuffle()
		if size < 2
			return

		LLEntry<T> array entries
		var count = 0
		var entry = dummy.next
		while entry != dummy
			entries[count] = entry
			count++
			entry = entry.next

		for i = count - 1 downto 1
			let j = GetRandomInt(0, i)
			let tmp = entries[i].elem
			entries[i].elem = entries[j].elem
			entries[j].elem = tmp

	/** Returns a random element from this list, or null if it is empty */
	function getRandomElement() returns T
		if size == 0
			return null
		return getEntry(GetRandomInt(0, size - 1)).elem

	/** Inserts the given element at the given index, shifting the element that
		was there (and everything after it) one position to the right.
		An index equal to the list's size appends to the end. */
	function addAt(T elem, int index)
		if index < 0 or index > size
			error("LinkedList: Index out of bounds: " + index)
		let entryAtIndex = getEntryUnchecked(index)
		let entry = new LLEntry<T>(elem, entryAtIndex.prev, entryAtIndex)
		entryAtIndex.prev.next = entry
		entryAtIndex.prev = entry
		size++

	/** Sorts the list according the the comparator using merge sort */
	function sortWith(Comparator<T> comparator)
		if comparator != null and size() > 1
			dummy.next = sort(comparator, dummy.next)
			dummy.next.prev = dummy
			var last = dummy.next
			while last.next != dummy
				last = last.next
			dummy.prev = last

	/** Returns the list obtained by applying the given closure to each element of the original list */
	function map<Q>(MapClosure<T, Q> itr) returns LinkedList<Q>
		let output = new LinkedList<Q>()
		forEach(t -> output.add(itr.run(t)))
		destroy itr
		return output

	/** Returns a new list of the elements that satisfy the predicate.
		Builds the result directly instead of copying and pruning, so only the
		matching elements are ever allocated. */
	function filter(LinkedListPredicate<T> predicate) returns LinkedList<T>
		let result = new LinkedList<T>()
		var entry = dummy.next
		while entry != dummy
			if predicate.isTrueFor(entry.elem)
				result.add(entry.elem)
			entry = entry.next
		destroy predicate
		return result

	/** 'Folds' this list into a single value of type Q
		Example int-list sum: `list.foldl<int>(0, (i, q) -> q + i)` */
	function foldl<Q>(Q startValue, FoldClosure<T, Q> predicate) returns Q
		var result = startValue
		var r = dummy.next
		while r != dummy
			result = predicate.run(r.elem, result)
			r = r.next
		destroy predicate
		return result

	/** Returns the first element that satisfies the predicate, or null if none present */
	function find(LinkedListPredicate<T> predicate) returns T
		T result = null
		let iter = this.iterator()
		for elem from iter
			if predicate.isTrueFor(elem)
				result = elem
				break
		iter.close()
		destroy predicate
		return result

	/** internal merge sort */
	private function sort(Comparator<T> comparator, LLEntry<T> e) returns LLEntry<T>
		if e == dummy or e.next == dummy
			return e

		var second = split(e)
		let first = sort(comparator, e)
		second = sort(comparator, second)
		return sortMerge(comparator, first, second)

	/** internal merge */
	private function sortMerge(Comparator<T> comparator, LLEntry<T> pa, LLEntry<T> pb) returns LLEntry<T>
		var a = pa
		var b = pb
		if a == dummy
			return b
		if b == dummy
			return a
		LLEntry<T> head
		LLEntry<T> tail
		if comparator.compare(a.elem, b.elem) < 0
			head = a
			tail = a
			a = a.next
		else
			head = b
			tail = b
			b = b.next

		while true
			if a == dummy
				tail.next = b
				b.prev = tail
				break
			if b == dummy
				tail.next = a
				a.prev = tail
				break
			if comparator.compare(a.elem, b.elem) < 0
				tail.next = a
				a.prev = tail
				tail = a
				a = a.next
			else
				tail.next = b
				b.prev = tail
				tail = b
				b = b.next
		return head

	/** returns the middle of a fragment list */
	private function split(LLEntry<T> e) returns LLEntry<T>
		var normalRef = e
		var halfRef = e
		while(normalRef.next != dummy and normalRef.next.next != dummy)
			normalRef = normalRef.next.next
			halfRef = halfRef.next
		let tmp = halfRef.next
		halfRef.next = dummy
		return tmp

	/** Prints the content of the list. Only meaningful for int-like element types. */
	function toString() returns string
		if size == 0
			return "[]"
		let fold = foldl<string>("[", (i, q) -> q + (i castTo int) + ",")
		return fold.substring(0, fold.length()-1) + "]"

	/** Removes all elements from the list */
	function clear()
		var current = dummy.next
		while current != dummy
			current = current.next
			destroy current.prev
		dummy.next = dummy
		dummy.prev = dummy
		size = 0

	protected function getDummy() returns LLEntry<T>
		return dummy

	/** Returns the entry at the given index, erroring if it is out of bounds.
		Without the check the walk simply wraps past the dummy entry and back
		into the list, silently returning the wrong element. */
	private function getEntry(int index) returns LLEntry<T>
		if index < 0 or index >= size
			error("LinkedList: Index out of bounds: " + index)
		return getEntryUnchecked(index)

	/** Walks to the entry at the given index without validating it.
		An index equal to size yields the dummy entry, which is what addAt uses
		to append to the end. */
	private function getEntryUnchecked(int index) returns LLEntry<T>
		var entry = dummy
		for i = 0 to index
			entry = entry.next
		return entry

	/** Removes an entry */
	protected function removeEntry(LLEntry<T> entry)
		entry.prev.next = entry.next
		entry.next.prev = entry.prev
		destroy entry
		size--

	ondestroy
		if staticItr != null
			destroy staticItr
		if staticBackItr != null
			destroy staticBackItr
		var current = dummy.next
		while current != dummy
			current = current.next
			destroy current.prev
		destroy dummy

public function asList<T>(vararg T ts) returns LinkedList<T>
	let ll = new LinkedList<T>
	for t in ts
		ll.add(t)
	return ll

class LLEntry<T>
	T elem
	LLEntry<T> prev
	LLEntry<T> next

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

public class LLIterator<T>
	LLEntry<T>	dummy
	LLEntry<T>	current
	LinkedList<T> parent
	protected var destroyOnClose = true

	construct(LinkedList<T> parent)
		assertTrue(parent != null)
		this.parent  = parent
		reset()

	construct(LinkedList<T> parent, bool destroyOnClose)
		assertTrue(parent != null)
		this.parent  = parent
		reset()
		this.destroyOnClose = destroyOnClose

	function reset()
		this.dummy   = parent.getDummy()
		this.current = dummy

	/** Removes from the list the last element that was returned by next() (optional operation).
	 	This call can only be made once per call to next */
	function remove() returns T
		if current != dummy
			// Read both fields before removeEntry destroys the node.
			let removed = current.elem
			let previous = current.prev
			parent.removeEntry(current)
			current = previous
			return removed
		return null

	/** Modifies the last element that was returned by next() (optional operation). */
	function modify(T newval)
		if current != dummy
			current.elem = newval

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

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

	function lookahead() returns T
		T retVal = null
		if hasNext()
			retVal = current.next.elem
		return retVal

	function previous() returns T
		return current.prev.elem

	/** Adds an element before the currently iterated element */
	function addBefore(T elem)
		let entry = new LLEntry<T>(elem, current.prev, current)
		current.prev.next = entry
		current.prev = entry
		parent.size++

	function close()
		if destroyOnClose
			destroy this

public class LLBackIterator<T>
	LLEntry<T> dummy
	LLEntry<T> current
	LinkedList<T> parent
	protected bool destroyOnClose = true

	construct(LinkedList<T> parent, bool destroyOnClose)
		assertTrue(parent != null)
		this.parent = parent
		reset()
		this.destroyOnClose = destroyOnClose

	construct(LinkedList<T> parent)
		assertTrue(parent != null)
		this.parent = parent
		reset()

	function reset()
		this.dummy = parent.getDummy()
		this.current = dummy

	/** Modifies the last element that was returned by next() (optional operation). */
	function modify(T newval)
		if current != dummy
			current.elem = newval

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

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

	function lookahead() returns T
		T retVal = null
		if hasNext()
			retVal = current.prev.elem
		return retVal

	/** Adds an element before the currently iterated element */
	function addBefore(T elem)
		let entry = new LLEntry<T>(elem, current.prev, current)
		current.prev.next = entry
		current.prev = entry
		parent.size++

	function close()
		if destroyOnClose
			destroy this

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

public interface LLItrClosure<T>
	function run(T t)

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

public interface MapClosure<T, Q>
	function run(T t) returns Q

public interface FoldClosure<T, Q>
	function run(T t, Q q) returns Q

public interface Comparator<T>
	function compare(T o1, T o2) returns int

// Three-way comparisons: subtracting truncates sub-1.0 real differences to
// "equal" and overflows for far-apart ints.
constant Comparator<real> realComparator = (r1, r2) -> r1 < r2 ? -1 : (r1 > r2 ? 1 : 0)
public function LinkedList<real>.sort()
	this.sortWith(realComparator)

constant Comparator<int> intComparator = (i1, i2) -> i1 < i2 ? -1 : (i1 > i2 ? 1 : 0)
public function LinkedList<int>.sort()
	this.sortWith(intComparator)

constant Comparator<string> stringComparator = (s1, s2) -> stringCompare(s1, s2)
public function LinkedList<string>.sort()
	this.sortWith(stringComparator)

public function group.asList() returns LinkedList<unit>
	let result = new LinkedList<unit>()
	this.forEachFrom() u ->
		result.add(u)
	return result

/** Joins elements from a string list into one string using a separator */
public function LinkedList<string>.joinBy(string separator) returns string
	var joined = ""
	let iter = this.iterator()

	for str from iter
		if iter.hasNext()
			joined += str + separator
		else
			joined += str

	iter.close()
	return joined

interface ToStringClosure<T>
	function toString(T elem) returns string

public function LinkedList<T>.joinBy<T>(ToStringClosure<T> cls, string separator) returns string
	let iter = this.iterator()
	let strings = new LinkedList<string>

	for elem from iter
		strings.add(cls.toString(elem))

	iter.close()
	let result = strings.joinBy(separator)
	destroy strings
	return result

/** Joins elements from a string list into one string */
public function LinkedList<string>.join() returns string
	return this.joinBy("")

init
	realToIndex(0.)