Efficient recursive iteration over self referencing struct

General Usage Performance
9

Not my best work, but supports sparsity, circularity (given one or more starting elements), and iteration. May implement removal and insertion after.

module FastLinkedLists

struct SingleLL{T, N}
	data :: Vector{T}
	next :: Vector{N}
end

"""
    function SingleLL(data, ::Type{N} = Int; kwargs...) where {T, N}

Create a linked list with unidirectional links (forward). NOTE: starting
with an empty circular buffer is no supported.
"""
function SingleLL(
	data :: Vector{T}, ::Type{N} = Int;
	copy_data = true, sparsity_factor :: Int = 1,
	circular = false
) where {T, N}
	if sparsity_factor < 1
		throw(ArgumentError("sparsity_factor should be one or more"))
	end
	if !copy_data && sparsity_factor > 1
		throw(ArgumentError(
			"You cannot disable copy_data and have sparsity_factor greater than one" *
			", use the default constructor for this kind of fiddling."
		))
	end
	if circular && isempty(data)
		throw(ArgumentError(
			"You cannot start with an empty circular buffer, the circularity is " *
			"engraved into the elements, not the list itself."
		))
	end
	sparsity_factor = convert(N, sparsity_factor)

	isempty(data) && return SingleLL{T, N}(copy_data ? copy(data) : data, N[])

	if isone(sparsity_factor)
		data = copy_data ? copy(data) : data
		next = collect(convert(N, 2):convert(N, length(data)))
		next[end] = circular ? one(N) : zero(N)
		return SingleLL{T, N}(data, next)
	end

	n = length(data)
	m = n * sparsity_factor
	data_ = Vector{T}(undef, m)
	next = zeros(N, m)
	j :: Int, i :: Int = 1, 1
	while i <= n
		data_[j] = data[i]
		next[j] = j + sparsity_factor
		j = next[j]
		i += 1
	end
	next[j - sparsity_factor] = circular ? one(n) : zero(n)

	return SingleLL{T, N}(data_, next)
end

import Base.iterate
function Base.iterate(l :: SingleLL{T, N}) where {T, N}
	isempty(l.next) && return nothing
	i = 1
	while iszero(l.next[i]); i += 1; end
	return (l.data[i], l.next[i])
end

function Base.iterate(l :: SingleLL{T, N}, i) where {T, N}
	iszero(i) && return nothing
	return (l.data[i], l.next[i])
end

end # module
1 Like