Mercurial > repos > AlgTools / file revision

####################################################################
# 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