Category talk:Wren-llist: Difference between revisions
m
→Source code: Now uses Wren S/H lexer.
(Added description and source code for new 'Wren-llist' module.) |
m (→Source code: Now uses Wren S/H lexer.) |
||
| (8 intermediate revisions by the same user not shown) | |||
Line 13:
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===
<
/* Node is a building block for a singly linked list. As such it consists of two fields:
Line 74:
return ll
}
// Copies the current instance to a new LinkedList.
copy() { LinkedList.new(this) }
// Basic properties.
Line 84 ⟶ 87:
isEmpty { _count == 0 }
// Adds an element at the tail of the current instance and returns it.
add(d) {
var node = Node.new(d)
Line 98 ⟶ 101:
}
_tail = node
return d
}
// Adds a sequence of elements at the tail of the current instance and returns them.
addAll(a) {
if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in a) add(e)
return a
}
// Inserts an element at the head of the current instance and returns it.
prepend(d) { insert_(0, d) }
// Inserts a sequence of elements at the head of the current instance and returns them.
prependAll(a) {
if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
Line 117 ⟶ 122:
i = i + 1
}
return a
}
Line 269 ⟶ 275:
// Exchanges the elements at indices 'i' and 'j' of the current instance.
if (i == j) return
var t = this[i]
this[i] = this[j]
Line 288 ⟶ 295:
var i = start
for (e in seq) {
}
return -1
Line 389 ⟶ 396:
// 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.
Line 409 ⟶ 416:
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()
}
Line 486 ⟶ 517:
return ll
}
// Copies the current instance to a new DLinkedList.
copy() { DLinkedList.new(this) }
// Basic properties.
Line 496 ⟶ 530:
isEmpty { _count == 0 }
// Adds an element at the tail of the current instance and returns it.
add(d) {
var node = DNode.new(d)
Line 512 ⟶ 546:
}
_tail = node
return d
}
// Adds a sequence of elements at the tail of the current instance and returns them.
addAll(a) {
if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in a) add(e)
return a
}
// Inserts an element at the head of the current instance and returns it.
prepend(d) { insert_(0, d) }
// Inserts a sequence of elements at the head of the current instance and returns them.
prependAll(a) {
if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
Line 531 ⟶ 567:
i = i + 1
}
return a
}
Line 607 ⟶ 644:
removed = _head.data
_head = _head.next
if (_head) _head.prev_ = null
} else if (index == _count - 1) {
removed = _tail.data
Line 703 ⟶ 740:
// Exchanges the elements at indices 'i' and 'j' of the current instance.
if (i == j) return
var t = this[i]
this[i] = this[j]
Line 900 ⟶ 938:
}
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(" <-> ") +"]" }
}</syntaxhighlight>
| |||