Mercurial > repos > AlgTools / file diff

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/LinkedLists.jl	Mon Nov 18 11:00:54 2019 -0500
@@ -0,0 +1,52 @@
+####################################################################
+# Immutable linked list (different from the mutable lists of
+# https://github.com/ChrisRackauckas/LinkedLists.jl)
+####################################################################
+
+module LinkedLists
+
+##############
+# Our exports
+##############
+
+export LinkedListEntry,
+       LinkedList,
+       unfold_linked_list
+
+#############
+# Data types
+#############
+
+struct LinkedListEntry{T}
+    value :: T
+    next :: Union{LinkedListEntry{T},Nothing}
+end
+
+LinkedList{T} = Union{LinkedListEntry{T},Nothing}
+
+############
+# Functions
+############
+
+function Base.iterate(list::LinkedList{T}) where T
+    return Base.iterate(list, list)
+end
+
+function Base.iterate(list::LinkedList{T}, tail::Nothing) where T
+    return nothing
+end
+
+function Base.iterate(list::LinkedList{T}, tail::LinkedListEntry{T}) where T
+    return tail.value, tail.next
+end
+
+# Return the items in the list with the tail first
+function unfold_linked_list(list::LinkedList{T}) where T
+    res = []
+    for value ∈ list
+        push!(res, value)
+    end
+    return reverse(res)
+end
+
+end