Category talk:Wren-llist
Linked Lists
Many tasks on RC require the use of linked lists which are generally implemented as a chain of nodes with each node containing a pointer to the next (and in the case of a doubly-linked list a pointer to the previous) node in the chain. As is well known, linked lists can be more efficient than dynamic arrays (in which the elements are stored contiguously) in cases where a large number of insertions and/or removals are required though are less efficient when it comes to operations involving indexing.
This module therefore adds linked list support to Wren in the form of two classes, LinkedList and DLinkedList, which represent singly and doubly-linked lists respectively. Each of these has a corresponding Node or DNode class to represent the nodes themselves. The design of these classes has been guided by the following principles:
1. The user should not have to deal with the Node objects directly, just their data members. The creation of Nodes is therefore done internally and independently, which avoids problems with cycles and Node identity when the same Node objects (which are reference types in Wren) are added directly or indirectly to the linked list.
2. Even though the underlying implementations are completely different, the interface of the linked list classes should follow closely that of the built-in List class which reduces the learning curve. However, given the nature of linked lists, additional methods have been provided where needed.
3. The linked list classes should inherit from the built-in Sequence class to automatically enjoy the functionality it provides.
For various reasons (efficient indexing, smaller memory footprint, more cache friendly) dynamic arrays tend to be preferred to linked lists nowadays and it is not expected that this module will see much use outside of RC particularly as it is written entirely in Wren whereas the built-in List class is written mostly in C. Consequently, only limited effort has been made to optimize the implementation.
Source code
<lang ecmascript>/* Module "llist.wren" */
/* Node is a building block for a singly linked list. As such it consists of two fields:
a data member, which can be of any type, and a link to the next Node_ object.
- /
class Node {
// Constructs a new Node object.
construct new(data) {
_data = data
_next = null
}
// Public properties.
data { _data }
data=(d) { _data = d }
next { _next }
next=(n) {
_next = (n.type == Node || n == null) ? n : Fiber.abort("Invalid argument.")
}
// Private setters, no checks.
next_=(n) { _next = n }
prev_=(n) { _prev = n }
// Returns the string representation of this instance.
toString { _data.toString }
}
/* LinkedList represents a singly linked list of Node_ objects.
The 'elements' of the list generally refer to their data members, not the Nodes themselves. Indexing operations support negative indices which count backwards from the end of the list.
- /
class LinkedList is Sequence {
// Constructs a new, empty LinkedList object.
construct new() {
_count = 0
_head = null
_tail = null
}
// Constructs a new LinkedList object and adds the elements of a sequence to it.
construct new(a) {
_count = 0
_head = null
_tail = null
addAll(a)
}
// Creates a new LinkedList with 'size' elements, all set to 'd'.
static filled(size, d) {
if (size.type != Num || !size.isInteger || size < 0) {
Fiber.abort("Size cannot be negative.")
}
var ll = LinkedList.new()
if (size == 0) return ll
for (i in 1..size) ll.add(d)
return ll
}
// Basic properties.
head { _head ? _head.data : null } // returns the first element
tail { _tail ? _tail.data : null } // returns the last element
count { _count } // returns the number of elements
// Returns whether or not the current instance is empty.
isEmpty { _count == 0 }
// Adds an element at the tail of the current instance.
add(d) {
var node = Node.new(d)
if (!_head) {
_head = node
_head.next_ = null
_count = 1
} else {
var n = _tail
n.next_ = node
node.next_ = null
_count = _count + 1
}
_tail = node
}
// Adds a sequence of elements at the tail of the current instance.
addAll(a) {
if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in a) add(e)
}
// Inserts an element at the head of the current instance.
prepend(d) { insert_(0, d) }
// Inserts a sequence of elements at the head of the current instance.
prependAll(a) {
if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
var i = 0
for (e in a) {
insert_(i, e)
i = i + 1
}
}
// Private helper method to check whether an index is valid.
checkIndex_(index, inc, s) {
if (index.type != Num || !index.isInteger) Fiber.abort("%(s) must be an integer.")
var c = _count + inc
if (index >= c || index < -c) Fiber.abort("%(s) is out of bounds.")
}
// Inserts an element at a specified index of the current instance
// and returns the inserted element.
insert(index, d) {
checkIndex_(index, 1, "Index")
return insert_(index, d)
}
// Private helper method for 'insert' which avoids type and bounds checks.
insert_(index, d) {
if (index < 0) index = _count + index + 1
if (index == _count) {
add(d)
return d
}
var node = Node.new(d)
if (index == 0) {
node.next_ = _head
_head = node
} else {
var n = _head
for (i in 1...index) n = n.next
node.next_ = n.next
n.next_ = node
}
_count = _count + 1
return d
}
// Inserts an element 'e' immediately after the first occurrence of an element 'd'
// in the current instance and returns the inserted element. Returns null if 'd'
// not found.
insertAfter(d, e) {
var ix = indexOf_(d, 0)
return (ix >= 0) ? insert_(ix+1, e) : null
}
// Inserts an element 'e' immediately before the first occurrence of an element 'd'
// in the current instance and returns the inserted element. Returns null if 'd'
// not found.
insertBefore(d, e) {
var ix = indexOf_(d, 0)
return (ix >= 0) ? insert_(ix, e) : null
}
// Removes the element at the specified index of the current instance and returns it.
removeAt(index) {
checkIndex_(index, 0, "Index")
return removeAt_(index)
}
// Private helper method for 'removeAt' which avoids type and bounds checks.
removeAt_(index) {
if (index < 0) index = _count + index
var removed
if (index == 0) {
removed = _head.data
_head = _head.next
} else {
var n = _head
var pred = null
for (i in 0...index) {
pred = n
n = n.next
}
removed = n.data
pred.next_ = n.next
}
_count = _count - 1
return removed
}
// Removes the first 'k' elements of the current instance and returns a list of them.
removeFirst(k) {
if (k.type != Num || !k.isInteger || k < 0) {
Fiber.abort("Argument must be a non-negative integer.")
}
if (k == 0) return []
if (k >= _count) {
var removed = this.toList
clear()
return removed
}
var removed = this.take(k).toList
var n = _head
for (i in 1..k) n = n.next
_head = n
_count = _count - k
return removed
}
// Removes the last 'k' elements of the current instance and returns a list of them.
removeLast(k) {
if (k.type != Num || !k.isInteger || k < 0) {
Fiber.abort("Argument must be a non-negative integer.")
}
if (k == 0) return []
if (k >= _count) {
var removed = this.toList
clear()
return removed
}
var removed = this.skip(_count - k).toList
var n = _head
for (i in 1..._count-k) n = n.next
_tail = n
_tail.next_ = null
_count = _count - k
return removed
}
// Removes all occurrences of the element 'd' from the current instance
// and returns the number of occurrences.
remove(d) {
var ixs = indicesOf_(d, 0)[-1..0]
if (ixs.count > 0) {
for (ix in ixs) {
removeAt_(ix)
}
}
return ixs.count
}
// Clears the current instance of all its elements.
clear() {
_count = 0
_head = null
_tail = null
}
// Replaces all occurrences of the element 'd' in the current instance
// by 'e' and returns the number of occurrences.
replace(d, e) {
if (d == e) return 0
var ixs = indicesOf_(d, 0)
if (ixs.count > 0) {
for (ix in ixs) {
this[ix] = e
}
}
return ixs.count
}
// Exchanges the elements at indices 'i' and 'j' of the current instance.
exchange(i, j) {
var t = this[i]
this[i] = this[j]
this[j] = t
}
// Returns the index of the first occurrence of 'd' in the current instance starting
// from index 'start'.
indexOf(d, start) {
checkIndex_(start, 0, "Start")
return indexOf_(d, start)
}
// Private helper method for 'indexOf' which avoids type and bounds checks.
indexOf_(d, start) {
if (start < 0) start = _count + start
var seq = (start == 0) ? this : this.skip(start)
var i = start
for (e in seq) {
if (e == d) return i
i = i + 1
}
return -1
}
// Convenience version of 'indexOf' which starts from 0.
indexOf(d) { indexOf(d, 0) }
// Returns the index of the first occurrence of any element of the sequence 'ds'
// in the current instance starting from index 'start'.
indexOfAny(ds, start) {
checkIndex_(start, 0, "Start")
if (start < 0) start = _count + start
if (!(ds is Sequence)) Fiber.abort("First argument must be a Sequence.")
var i
for (d in ds) {
if ((i = indexOf_(d, start)) >= 0) return i
}
return -1
}
// Convenience version of 'indexOfAny' which starts from 0.
indexOfAny(ds) { indexOf(ds, 0) }
// Returns a list of the indices of all occurrences of 'd' in the current instance
// starting from index 'start'.
indicesOf(d, start) {
checkIndex_(start, 0, "Start")
return indicesOf_(d, start)
}
// Private helper method for 'indicesOf' which avoids type and bounds checks.
indicesOf_(d, start) {
if (start < 0) start = _count + start
var ixs = []
var seq = (start == 0) ? this : this.skip(start)
var i = start
for (e in seq) {
if (e == d) ixs.add(i)
i = i + 1
}
return ixs
}
// Convenience version of 'indicesOf' which starts from 0.
indicesOf(d) { indicesOf(d, 0) }
// Returns the element at a specified index or the elements within a specified
// index range of the current instance. In the latter case, the elements
// are copied to a new LinkedList instance.
[index] {
if (index is Range) {
if (index.from > index.to) Fiber.abort("Index range cannot be decreasing.")
var inc = index.isInclusive ? 0 : 1
if (index.from < 0 || (index.isInclusive && index.to >= _count + inc)) {
Fiber.abort("Index range is out of bounds.")
}
inc = index.isInclusive ? 1 : 0
var ll = LinkedList.new()
for (e in this.skip(index.from).take(index.to-index.from + inc)) ll.add(e)
return ll
}
checkIndex_(index, 0, "Index")
if (index < 0) index = _count + index
var i = 0
for (e in this) {
if (index == i) return e
i = i + 1
}
}
// Changes the element at the specified index of the current instance to 'd'.
[index]=(d) {
checkIndex_(index, 0, "Index")
var i = 0
var n = _head
for (e in this) {
if (index == i) {
n.data = d
return
}
i = i + 1
n = n.next
}
}
// Returns true if this instance contains ALL the values of a sequence, false otherwise.
containsAll(ds) {
if (!(ds is Sequence)) Fiber.abort("First argument must be a Sequence.")
for (d in ds) {
if (!contains(d)) return false
}
return true
}
// Returns true if this instance contains ANY of the values, false otherwise.
containsAny(ds) { indexOfAny(ds, 0) >= 0 }
// Returns true if this instance contains NONE of the values, false otherwise.
containsNone(ds) { !containsAny(ds) }
// Combines the elements of this instance plus those of another LinkedList object
// into a new LinkedList and returns it.
+(other) {
if (other.type != LinkedList) Fiber.abort("Addend must be another LinkedList.")
var ll = LinkedList.new()
ll.addAll(this)
ll.addAll(other)
return ll
}
// Iterator protocol methods.
iterate(iterator) {
if (!iterator) {
return !_head ? false : _head
}
return iterator.next
}
iteratorValue(iterator) { iterator.data }
// Iterates through the nodes of this instance and returns for each one
// a list containing the current and next data members.
nodes {
class N is Sequence {
construct new(head) {
_head = head
}
iterate(iterator) {
if (!iterator) {
return !_head ? false : _head
}
return iterator.next
}
iteratorValue(iterator) {
var n = iterator.next
var next = (n) ? n.data : null
return [iterator.data, next]
}
}
return N.new(_head)
}
// Prints the consecutive elements of the current instance to stdout
// separated by a single space and followed by a new line.
print() {
for (e in this) System.write("%(e) ")
System.print()
}
// Returns the string representation of the current instance.
toString { "[" + toList.join(" -> ") +"]" }
}
/* DNode is a building block for a doubly linked list. As such it consists of three fields:
a data member, which can be of any type, and links to the next and previous Node objects.
- /
class DNode {
// Constructs a new DNode object.
construct new(data) {
_data = data
_next = null
_prev = null
}
// Public properties.
data { _data }
data=(d) { _data = d }
next { _next }
next=(n) {
_next = (n.type == DNode || n == null) ? n : Fiber.abort("Invalid argument.")
}
prev { _prev }
prev=(n) {
_prev = (n.type == DNode || n == null) ? n : Fiber.abort("Invalid argument.")
}
// Private setters, no checks.
next_=(n) { _next = n }
prev_=(n) { _prev = n }
// Returns the string representation of this instance.
toString { _data.toString }
}
/* DLinkedList represents a doubly linked list of DNode objects.
The 'elements' of the list generally refer to their data members, not the DNodes themselves. Indexing operations support negative indices which count backwards from the end of the list.
- /
class DLinkedList is Sequence {
// Constructs a new, empty DLinkedList object.
construct new() {
_count = 0
_head = null
_tail = null
}
// Constructs a new DLinkedList object and adds the elements of a sequence to it.
construct new(a) {
_count = 0
_head = null
_tail = null
addAll(a)
}
// Creates a new DLinkedList with 'size' elements, all set to 'd'.
static filled(size, d) {
if (size.type != Num || !size.isInteger || size < 0) {
Fiber.abort("Size cannot be negative.")
}
var ll = DLinkedList.new()
if (size == 0) return ll
for (i in 1..size) ll.add(d)
return ll
}
// Basic properties.
head { _head ? _head.data : null } // returns the first element
tail { _tail ? _tail.data : null } // returns the last element
count { _count } // returns the number of elements
// Returns whether or not the current instance is empty.
isEmpty { _count == 0 }
// Adds an element at the tail of the current instance.
add(d) {
var node = DNode.new(d)
if (!_head) {
_head = node
_head.next_ = null
_head.prev_ = null
_count = 1
} else {
var n = _tail
n.next_ = node
node.next_ = null
node.prev_ = n
_count = _count + 1
}
_tail = node
}
// Adds a sequence of elements at the tail of the current instance.
addAll(a) {
if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in a) add(e)
}
// Inserts an element at the head of the current instance.
prepend(d) { insert_(0, d) }
// Inserts a sequence of elements at the head of the current instance.
prependAll(a) {
if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
var i = 0
for (e in a) {
insert_(i, e)
i = i + 1
}
}
// Private helper method to check whether an index is valid.
checkIndex_(index, inc, s) {
if (index.type != Num || !index.isInteger) Fiber.abort("%(s) must be an integer.")
var c = _count + inc
if (index >= c || index < -c) Fiber.abort("%(s) is out of bounds.")
}
// Inserts an element at a specified index of the current instance
// and returns the inserted element.
insert(index, d) {
checkIndex_(index, 1, "Index")
return insert_(index, d)
}
// Private helper method for 'insert' which avoids type and bounds checks.
insert_(index, d) {
if (index < 0) index = _count + index + 1
if (index == _count) {
add(d)
return d
}
var node = DNode.new(d)
if (index == 0) {
node.next_ = _head
node.prev_ = null
_head = node
} else {
var mid = (_count/2).floor
var n
if (index < mid) {
n = _head
for (i in 1...index) n = n.next
} else {
n = _tail
for (i in _count...index) n = n.prev
}
node.next_ = n.next
n.next.prev_ = node
node.prev_ = n
n.next_ = node
}
_count = _count + 1
return d
}
// Inserts an element 'e' immediately after the first occurrence of an element 'd'
// in the current instance and returns the inserted element. Returns null if 'd'
// not found.
insertAfter(d, e) {
var ix = indexOf_(d, 0)
return (ix >= 0) ? insert_(ix+1, e) : null
}
// Inserts an element 'e' immediately before the first occurrence of an element 'd'
// in the current instance and returns the inserted element. Returns null if 'd'
// not found.
insertBefore(d, e) {
var ix = indexOf_(d, 0)
return (ix >= 0) ? insert_(ix, e) : null
}
// Removes the element at the specified index of the current instance and returns it.
removeAt(index) {
checkIndex_(index, 0, "Index")
return removeAt_(index)
}
// Private helper method for 'removeAt' which avoids type and bounds checks.
removeAt_(index) {
if (index < 0) index = _count + index
var removed
if (index == 0) {
removed = _head.data
_head = _head.next
if (_head) _head.prev_ = null
} else if (index == _count - 1) {
removed = _tail.data
_tail = _tail.prev
_tail.next_ = null
} else {
var mid = (_count/2).floor
var n
if (index < mid) {
n = _head
for (i in 0...index) n = n.next
} else {
n = _tail
for (i in _count-1...index) n = n.prev
}
removed = n.data
n.prev.next_ = n.next
n.next.prev_ = n.prev
}
_count = _count - 1
return removed
}
// Removes the first 'k' elements of the current instance and returns a list of them.
removeFirst(k) {
if (k.type != Num || !k.isInteger || k < 0) {
Fiber.abort("Argument must be a non-negative integer.")
}
if (k == 0) return []
if (k >= _count) {
var removed = this.toList
clear()
return removed
}
var removed = this.take(k).toList
var n = _head
for (i in 1..k) n = n.next
n.prev_ = null
_head = n
_count = _count - k
return removed
}
// Removes the last 'k' elements of the current instance and returns a list of them.
removeLast(k) {
if (k.type != Num || !k.isInteger || k < 0) {
Fiber.abort("Argument must be a non-negative integer.")
}
if (k == 0) return []
if (k >= _count) {
var removed = this.toList
clear()
return removed
}
var removed = this.skip(_count - k).toList
var n = _tail
for (i in 1..k) n = n.prev
_tail = n
_tail.next_ = null
_count = _count - k
return removed
}
// Removes all occurrences of the element 'd' from the current instance
// and returns the number of occurrences.
remove(d) {
var ixs = indicesOf_(d, 0)[-1..0]
if (ixs.count > 0) {
for (ix in ixs) {
removeAt_(ix)
}
}
return ixs.count
}
// Clears the current instance of all its elements.
clear() {
_count = 0
_head = null
_tail = null
}
// Replaces all occurrences of the element 'd' in the current instance
// by 'e' and returns the number of occurrences.
replace(d, e) {
if (d == e) return 0
var ixs = indicesOf_(d, 0)
if (ixs.count > 0) {
for (ix in ixs) {
this[ix] = e
}
}
return ixs.count
}
// Exchanges the elements at indices 'i' and 'j' of the current instance.
exchange(i, j) {
var t = this[i]
this[i] = this[j]
this[j] = t
}
// Returns the index of the first occurrence of 'd' in the current instance starting
// from index 'start'.
indexOf(d, start) {
checkIndex_(start, 0, "Start")
return indexOf_(d, start)
}
// Private helper method for 'indexOf' which avoids type and bounds checks.
indexOf_(d, start) {
if (start < 0) start = _count + start
var seq = (start == 0) ? this : this.skip(start)
var i = start
for (e in seq) {
if (e == d) return i
i = i + 1
}
return -1
}
// Convenience version of 'indexOf' which starts from 0.
indexOf(d) { indexOf(d, 0) }
// Returns the index of the last occurrence of 'd' in the current instance.
lastIndexOf(d) {
var i = _count - 1
for (e in this.reversed) {
if (e == d) return i
i = i - 1
}
return -1
}
// Returns the index of the first occurrence of any element of the sequence 'ds'
// in the current instance starting from index 'start'.
indexOfAny(ds, start) {
checkIndex_(start, 0, "Start")
if (start < 0) start = _count + start
if (!(ds is Sequence)) Fiber.abort("First argument must be a Sequence.")
var i
for (d in ds) {
if ((i = indexOf_(d, start)) >= 0) return i
}
return -1
}
// Convenience version of 'indexOfAny' which starts from 0.
indexOfAny(ds) { indexOf(ds, 0) }
// Searches for the indices of all occurrences of 'd' in the current instance
// starting from index 'start' and returns a list of three items:
// The first item is a Bool indicating whether the value was found.
// The second item is the number of times the value was found.
// The third item is a list of indices at which the value was found.
indicesOf(d, start) {
checkIndex_(start, 0, "Start")
var res = indicesOf_(d, start)
var c = res.count
return [c > 0, c, res]
}
// Private helper method for 'indicesOf' which avoids type and bounds checks and
// just returns a list of indices at which the value was found.
indicesOf_(d, start) {
if (start < 0) start = _count + start
var ixs = []
var seq = (start == 0) ? this : this.skip(start)
var i = start
for (e in seq) {
if (e == d) ixs.add(i)
i = i + 1
}
return ixs
}
// Convenience version of 'indicesOf' which starts from 0.
indicesOf(d) { indicesOf(d, 0) }
// Returns the element at a specified index or the elements within a specified
// index range of the current instance. In the latter case, the elements
// are copied to a new DLinkedList instance.
[index] {
if (index is Range) {
if (index.from > index.to) Fiber.abort("Index range cannot be decreasing.")
var inc = index.isInclusive ? 0 : 1
if (index.from < 0 || (index.isInclusive && index.to >= _count + inc)) {
Fiber.abort("Index range is out of bounds.")
}
inc = index.isInclusive ? 1 : 0
var ll = DLinkedList.new()
for (e in this.skip(index.from).take(index.to-index.from + inc)) ll.add(e)
return ll
}
checkIndex_(index, 0, "Index")
if (index < 0) index = _count + index
var mid = (_count/2).floor
if (index < mid) {
var i = 0
for (e in this) {
if (index == i) return e
i = i + 1
}
} else {
var i = _count - 1
for (e in this.reversed) {
if (index == i) return e
i = i - 1
}
}
}
// Changes the element at the specified index of the current instance to 'd'.
[index]=(d) {
checkIndex_(index, 0, "Index")
var mid = (_count/2).floor
if (index < mid) {
var i = 0
var n = _head
for (e in this) {
if (index == i) {
n.data = d
return
}
i = i + 1
n = n.next
}
} else {
var i = _count - 1
var n = _tail
for (e in this.reversed) {
if (index == i) {
n.data = d
return
}
i = i - 1
n = n.prev
}
}
}
// Returns true if this instance contains ALL the values of a sequence, false otherwise.
containsAll(ds) {
if (!(ds is Sequence)) Fiber.abort("First argument must be a Sequence.")
for (d in ds) {
if (!contains(d)) return false
}
return true
}
// Returns true if this instance contains ANY of the values, false otherwise.
containsAny(ds) { indexOfAny(ds, 0) >= 0 }
// Returns true if this instance contains NONE of the values, false otherwise.
containsNone(ds) { !containsAny(ds) }
// Combines the elements of this instance plus those of another DLinkedList object
// into a new DLinkedList and returns it.
+(other) {
if (other.type != DLinkedList) Fiber.abort("Addend must be another DLinkedList.")
var ll = DLinkedList.new()
ll.addAll(this)
ll.addAll(other)
return ll
}
// Iterator protocol methods.
iterate(iterator) {
if (!iterator) {
return !_head ? false : _head
}
return iterator.next
}
iteratorValue(iterator) { iterator.data }
// Reverses the iteration order.
reversed {
class R is Sequence {
construct new(tail) {
_tail = tail
}
iterate(iterator) {
if (!iterator) {
return !_tail ? false : _tail
}
return iterator.prev
}
iteratorValue(iterator) { iterator.data }
}
return R.new(_tail)
}
// Iterates through the nodes of this instance and returns for each one
// a list containing the previous, current and next data members.
nodes {
class N is Sequence {
construct new(head) {
_head = head
}
iterate(iterator) {
if (!iterator) {
return !_head ? false : _head
}
return iterator.next
}
iteratorValue(iterator) {
var p = iterator.prev
var prev = (p) ? p.data : null
var n = iterator.next
var next = (n) ? n.data : null
return [prev, iterator.data, next]
}
}
return N.new(_head)
}
// Prints the consecutive elements of the current instance to stdout
// separated by a single space and followed by a new line.
print() {
for (e in this) System.write("%(e) ")
System.print()
}
// As 'print' method but prints the elements in reverse.
rprint() {
for (e in this.reversed) System.write("%(e) ")
System.print()
}
// Returns the string representation of the current instance.
toString { "[" + toList.join(" <-> ") +"]" }
}
// Type aliases for classes in case of any name clashes with other modules. var LList_Node = Node var LList_LinkedList = LinkedList var LList_DNode = DNode var LList_DLinkedList = DLinkedList</lang>