Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
520 lines (436 sloc) 12.8 KB
package LinkedList
import NoWurst
import TypeCasting
import Integer
import String
import ClosureForGroups
import Real
/**
* 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
/** Create 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)
/** Create a new empty list */
construct()
dummy.next = dummy
dummy.prev = dummy
/** Add 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++
/** add all elements from elems to the end of this list */
function addAll(LinkedList<T> elems)
for elem in elems
add(elem)
/** Returns the element at the specified index */
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 */
function set(int index, T elem)
getEntry(index).elem = elem
/** Add 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 */
function getFirst() returns T
return dummy.next.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 dummy.prev.elem
/** Returns whether the lists contains the specified element */
@deprecated("Use .has instead") function contains(T elem) returns boolean
return has(elem)
/** 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 */
function remove(T elem)
var entry = dummy.next
while entry != dummy
if entry.elem == elem
removeEntry(entry)
return
entry = entry.next
/** gets the size of the list */
@deprecated("Use .size() instead.") function getSize() returns int
return size
/** 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 map */
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>(dummy, false)
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(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
var current = dummy.next
while current != dummy
if current.elem == whichElement
current.elem = newElement
return true
current = current.next
return false
@deprecated("Use #removeIf")
function removeWhen(LinkedListPredicate<T> predicate)
removeIf(predicate)
/** 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 */
function shuffle()
T array _a
let n = size()
var i0 = 0
let itr = iterator()
while itr.hasNext()
itr.next()
_a[i0] = itr.remove()
i0++
for i = n-1 downto 1
let j = GetRandomInt(0, i)
let tmp = _a[i]
_a[i] = _a[j]
_a[j] = tmp
for i = 0 to n-1
add(_a[i])
/** Adds the given element directly behind the element at the given index */
function addAt(T elem, int index)
let entryAtIndex = getEntry(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 */
function filter(LinkedListPredicate<T> predicate) returns LinkedList<T>
let result = copy()
result.removeIf(t -> not predicate.isTrueFor(t))
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
/** 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 */
function toString() returns string
let fold = foldl<string>("[", (i, q) -> q + (i castTo int).toString() + ",")
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 */
private function getEntry(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)
this.parent = parent
reset()
construct(LinkedList<T> parent, bool destroyOnClose)
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
parent.removeEntry(current)
let removed = current.elem
current = current.prev
return removed
return null
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 close()
if destroyOnClose
destroy this
public class LLBackIterator<T>
LLEntry<T> dummy
LLEntry<T> current
protected bool destroyOnClose = true
construct(LLEntry<T> dummy, bool destroyOnClose)
this.dummy = dummy
reset()
this.destroyOnClose = destroyOnClose
construct(LLEntry<T> dummy)
this.dummy = dummy
reset()
function reset()
this.current = dummy
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
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
constant Comparator<real> realComparator = (r1, r2) -> (r1 - r2).toInt()
public function LinkedList<real>.sort()
this.sortWith(realComparator)
constant Comparator<int> intComparator = (i1, i2) -> i1 - i2
public function LinkedList<int>.sort()
this.sortWith(intComparator)
public function group.asList() returns LinkedList<unit>
let result = new LinkedList<unit>()
this.forEachFrom() u ->
result.add(u)
return result
init
realToIndex(0.)