list.pony

``````class List[A] is Seq[A]
"""
"""
var _head: (ListNode[A] | None) = None
var _tail: (ListNode[A] | None) = None
var _size: USize = 0

new create(len: USize = 0) =>
"""
Do nothing, but be compatible with Seq.
"""
None

new unit(a: A) =>
"""
Builds a new list from an element.
"""
push(consume a)

new from(seq: Array[A^]) =>
"""
Builds a new list from the sequence passed in.
"""
for value in seq.values() do
push(consume value)
end

fun ref reserve(len: USize) =>
"""
Do nothing, but be compatible with Seq.
"""
None

fun size(): USize =>
"""
Returns the number of items in the list.
"""
_size

fun apply(i: USize = 0): this->A ? =>
"""
Get the i-th element, raising an error if the index is out of bounds.
"""
index(i)?()?

fun ref update(i: USize, value: A): A^ ? =>
"""
Change the i-th element, raising an error if the index is out of bounds.
Returns the previous value, which may be None if the node has been popped
but left on the list.
"""
index(i)?()? = consume value

fun index(i: USize): this->ListNode[A] ? =>
"""
Gets the i-th node, raising an error if the index is out of bounds.
"""
if i >= _size then
error
end

var node = _head as this->ListNode[A]
var j = USize(0)

while j < i do
node = node.next() as this->ListNode[A]
j = j + 1
end

node

fun ref remove(i: USize): ListNode[A] ? =>
"""
Remove the i-th node, raising an error if the index is out of bounds.
The removed node is returned.
"""
index(i)? .> remove()

fun ref clear() =>
"""
Empties the list.
"""
_tail = None
_size = 0

"""
Get the head of the list.
"""

fun tail(): this->ListNode[A] ? =>
"""
Get the tail of the list.
"""
_tail as this->ListNode[A]

fun ref prepend_node(node: ListNode[A]) =>
"""
"""
else
_set_both(node)
end

fun ref append_node(node: ListNode[A]) =>
"""
Adds a node to the tail of the list.
"""
match _tail
| let tail': ListNode[A] =>
tail'.append(node)
else
_set_both(node)
end

fun ref append_list(that: List[A]) =>
"""
Remove all nodes from that and append them to this.
"""
if this isnt that then
while that._size > 0 do
end
end

fun ref prepend_list(that: List[A]) =>
"""
Remove all nodes from that and prepend them to this.
"""
if this isnt that then
while that._size > 0 do
try prepend_node(that.tail()?) end
end
end

fun ref push(a: A) =>
"""
Adds a value to the tail of the list.
"""
append_node(ListNode[A](consume a))

fun ref pop(): A^ ? =>
"""
Removes a value from the tail of the list.
"""
tail()? .> remove().pop()?

fun ref unshift(a: A) =>
"""
"""
prepend_node(ListNode[A](consume a))

fun ref shift(): A^ ? =>
"""
Removes a value from the head of the list.
"""

fun ref append(
offset: USize = 0,
len: USize = -1)
=>
"""
Append len elements from a sequence, starting from the given offset.
"""
if offset >= seq.size() then
return
end

let copy_len = len.min(seq.size() - offset)
reserve(_size + copy_len)

let cap = copy_len + offset
var i = offset

try
while i < cap do
push(seq(i)?)
i = i + 1
end
end

fun ref concat(iter: Iterator[A^], offset: USize = 0, len: USize = -1) =>
"""
Add len iterated elements to the end of the list, starting from the given
offset.
"""
try
for i in Range(0, offset) do
if iter.has_next() then
iter.next()?
else
return
end
end

for i in Range(0, len) do
if iter.has_next() then
push(iter.next()?)
else
return
end
end
end

fun ref truncate(len: USize) =>
"""
Truncate the list to the given length, discarding excess elements.
If the list is already smaller than len, do nothing.
"""
try
while _size > len do
pop()?
end
end

fun clone(): List[this->A!]^ =>
"""
Clone the list.
"""
let out = List[this->A!]

for v in values() do
out.push(v)
end
out

fun map[B](f: {(this->A!): B^} box): List[B]^ =>
"""
Builds a new list by applying a function to every member of the list.
"""
try
else
List[B]
end

fun _map[B](
ln: this->ListNode[A],
f: {(this->A!): B^} box,
acc: List[B])
: List[B]^
=>
"""
Private helper for map, recursively working with ListNodes.
"""
try acc.push(f(ln()?)) end

try
_map[B](ln.next() as this->ListNode[A], f, acc)
else
acc
end

fun flat_map[B](f: {(this->A!): List[B]} box): List[B]^ =>
"""
Builds a new list by applying a function to every member of the list and
using the elements of the resulting lists.
"""
try
else
List[B]
end

fun _flat_map[B](
ln: this->ListNode[A],
f: {(this->A!): List[B]} box,
acc: List[B]): List[B]^
=>
"""
Private helper for flat_map, recursively working with ListNodes.
"""
try acc.append_list(f(ln()?)) end

try
_flat_map[B](ln.next() as this->ListNode[A], f, acc)
else
acc
end

fun filter(f: {(this->A!): Bool} box): List[this->A!]^ =>
"""
Builds a new list with those elements that satisfy a provided predicate.
"""
try
else
List[this->A!]
end

fun _filter(
ln: this->ListNode[A],
f: {(this->A!): Bool} box,
acc: List[this->A!]): List[this->A!]
=>
"""
Private helper for filter, recursively working with ListNodes.
"""
try
let cur = ln()?
if f(cur) then acc.push(cur) end
end

try
_filter(ln.next() as this->ListNode[A], f, acc)
else
acc
end

fun fold[B](f: {(B!, this->A!): B^} box, acc: B): B =>
"""
Folds the elements of the list using the supplied function.
"""
let h = try
else
return acc
end

_fold[B](h, f, consume acc)

fun _fold[B](
ln: this->ListNode[A],
f: {(B!, this->A!): B^} box,
acc: B)
: B
=>
"""
Private helper for fold, recursively working with ListNodes.
"""
let nextAcc: B = try f(acc, ln()?) else consume acc end
let h = try
ln.next() as this->ListNode[A]
else
return nextAcc
end

_fold[B](h, f, consume nextAcc)

fun every(f: {(this->A!): Bool} box): Bool =>
"""
Returns true if every element satisfies the provided predicate, false
otherwise.
"""
try
else
true
end

fun _every(ln: this->ListNode[A], f: {(this->A!): Bool} box): Bool =>
"""
Private helper for every, recursively working with ListNodes.
"""
try
if not(f(ln()?)) then
false
else
_every(ln.next() as this->ListNode[A], f)
end
else
true
end

fun exists(f: {(this->A!): Bool} box): Bool =>
"""
Returns true if at least one element satisfies the provided predicate,
false otherwise.
"""
try
else
false
end

fun _exists(ln: this->ListNode[A], f: {(this->A!): Bool} box): Bool =>
"""
Private helper for exists, recursively working with ListNodes.
"""
try
if f(ln()?) then
true
else
_exists(ln.next() as this->ListNode[A], f)
end
else
false
end

fun partition(
f: {(this->A!): Bool} box)
: (List[this->A!]^, List[this->A!]^)
=>
"""
Builds a pair of lists, the first of which is made up of the elements
satisfying the supplied predicate and the second of which is made up of
those that do not.
"""
let l1 = List[this->A!]
let l2 = List[this->A!]
for item in values() do
if f(item) then l1.push(item) else l2.push(item) end
end
(l1, l2)

fun drop(n: USize): List[this->A!]^ =>
"""
Builds a list by dropping the first n elements.
"""
let l = List[this->A!]

if size() > n then
try
var node = index(n)?

for i in Range(n, size()) do
l.push(node()?)
node = node.next() as this->ListNode[A]
end
end
end
l

fun take(n: USize): List[this->A!] =>
"""
Builds a list of the first n elements.
"""
let l = List[this->A!]

if size() > 0 then
try

for i in Range(0, n.min(size())) do
l.push(node()?)
node = node.next() as this->ListNode[A]
end
end
end
l

fun take_while(f: {(this->A!): Bool} box): List[this->A!]^ =>
"""
Builds a list of elements satisfying the provided predicate until one does
not.
"""
let l = List[this->A!]

if size() > 0 then
try

for i in Range(0, size()) do
let item = node()?
if f(item) then l.push(item) else return l end
node = node.next() as this->ListNode[A]
end
end
end
l

fun reverse(): List[this->A!]^ =>
"""
Builds a new list by reversing the elements in the list.
"""
try
else
List[this->A!]
end

fun _reverse(ln: this->ListNode[A], acc: List[this->A!]): List[this->A!]^ =>
"""
Private helper for reverse, recursively working with ListNodes.
"""
try acc.unshift(ln()?) end

try
_reverse(ln.next() as this->ListNode[A], acc)
else
acc
end

fun contains[B: (A & HasEq[A!] #read) = A](a: box->B): Bool =>
"""
Returns true if the list contains the provided element, false otherwise.
"""
try
else
false
end

fun _contains[B: (A & HasEq[A!] #read) = A](
ln: this->ListNode[A],
a: box->B)
: Bool
=>
"""
Private helper for contains, recursively working with ListNodes.
"""
try
if a == ln()? then
true
else
_contains[B](ln.next() as this->ListNode[A], a)
end
else
false
end

fun nodes(): ListNodes[A, this->ListNode[A]]^ =>
"""
Return an iterator on the nodes in the list.
"""

fun rnodes(): ListNodes[A, this->ListNode[A]]^ =>
"""
Return an iterator on the nodes in the list.
"""

fun values(): ListValues[A, this->ListNode[A]]^ =>
"""
Return an iterator on the values in the list.
"""

fun rvalues(): ListValues[A, this->ListNode[A]]^ =>
"""
Return an iterator on the values in the list.
"""

fun ref _increment() =>
_size = _size + 1

fun ref _decrement() =>
_size = _size - 1

fun ref _set_tail(tail': (ListNode[A] | None)) =>
_tail = tail'

fun ref _set_both(node: ListNode[A]) =>
node._set_list(this)
_tail = node
_size = 1

class ListNodes[A, N: ListNode[A] #read] is Iterator[N]
"""
Iterate over the nodes in a list.
"""
var _next: (N | None)
let _reverse: Bool

new create(head: (N | None), reverse: Bool = false) =>
"""
Keep the next list node to be examined.
"""
_reverse = reverse

fun has_next(): Bool =>
"""
If we have a list node, we have more values.
"""
_next isnt None

fun ref next(): N ? =>
"""
Get the list node and replace it with the next one.
"""
match _next
| let next': N =>
if _reverse then
_next = next'.prev()
else
_next = next'.next()
end

next'
else
error
end

class ListValues[A, N: ListNode[A] #read] is Iterator[N->A]
"""
Iterate over the values in a list.
"""
var _next: (N | None)
let _reverse: Bool

new create(head: (N | None), reverse: Bool = false) =>
"""
Keep the next list node to be examined.
"""
_reverse = reverse

fun has_next(): Bool =>
"""
If we have a list node, we have more values.
"""
_next isnt None

fun ref next(): N->A ? =>
"""
Get the value of the list node and replace it with the next one.
"""
match _next
| let next': N =>
if _reverse then
_next = next'.prev()
else
_next = next'.next()
end

next'()?
else
error
end

``````