1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
# This file is a part of Julia. License is MIT: https://julialang.org/license
mutable struct InvasiveLinkedList{T}
# Invasive list requires that T have a field `.next >: U{T, Nothing}` and `.queue >: U{ILL{T}, Nothing}`
head::Union{T, Nothing}
tail::Union{T, Nothing}
InvasiveLinkedList{T}() where {T} = new{T}(nothing, nothing)
end
#const list_append!! = append!
#const list_deletefirst! = delete!
eltype(::Type{<:InvasiveLinkedList{T}}) where {T} = @isdefined(T) ? T : Any
iterate(q::InvasiveLinkedList) = (h = q.head; h === nothing ? nothing : (h, h))
iterate(q::InvasiveLinkedList{T}, v::T) where {T} = (h = v.next; h === nothing ? nothing : (h, h))
isempty(q::InvasiveLinkedList) = (q.head === nothing)
function length(q::InvasiveLinkedList)
i = 0
head = q.head
while head !== nothing
i += 1
head = head.next
end
return i
end
function list_append!!(q::InvasiveLinkedList{T}, q2::InvasiveLinkedList{T}) where T
q === q2 && error("can't append list to itself")
head2 = q2.head
if head2 !== nothing
tail2 = q2.tail::T
q2.head = nothing
q2.tail = nothing
tail = q.tail
q.tail = tail2
if tail === nothing
q.head = head2
else
tail.next = head2
end
while head2 !== nothing
head2.queue = q
head2 = head2.next
end
end
return q
end
function push!(q::InvasiveLinkedList{T}, val::T) where T
val.queue === nothing || error("val already in a list")
val.queue = q
tail = q.tail
if tail === nothing
q.head = q.tail = val
else
tail.next = val
q.tail = val
end
return q
end
function pushfirst!(q::InvasiveLinkedList{T}, val::T) where T
val.queue === nothing || error("val already in a list")
val.queue = q
head = q.head
if head === nothing
q.head = q.tail = val
else
val.next = head
q.head = val
end
return q
end
function pop!(q::InvasiveLinkedList{T}) where {T}
val = q.tail::T
list_deletefirst!(q, val) # expensive!
return val
end
function popfirst!(q::InvasiveLinkedList{T}) where {T}
val = q.head::T
list_deletefirst!(q, val) # cheap
return val
end
function list_deletefirst!(q::InvasiveLinkedList{T}, val::T) where T
val.queue === q || return
head = q.head::T
if head === val
if q.tail::T === val
q.head = q.tail = nothing
else
q.head = val.next::T
end
else
head_next = head.next
while head_next !== val
head = head_next
head_next = head.next::Union{T, Nothing}
end
if q.tail::T === val
head.next = nothing
q.tail = head
else
head.next = val.next::T
end
end
val.next = nothing
val.queue = nothing
return q
end
#function list_deletefirst!(q::Array{T}, val::T) where T
# i = findfirst(isequal(val), q)
# i === nothing || deleteat!(q, i)
# return q
#end
mutable struct LinkedListItem{T}
# Adapter class to use any `T` in a LinkedList
next::Union{LinkedListItem{T}, Nothing}
queue::Union{InvasiveLinkedList{LinkedListItem{T}}, Nothing}
value::T
LinkedListItem{T}(value::T) where {T} = new{T}(nothing, nothing, value)
end
const LinkedList{T} = InvasiveLinkedList{LinkedListItem{T}}
# delegate methods, as needed
eltype(::Type{<:LinkedList{T}}) where {T} = @isdefined(T) ? T : Any
iterate(q::LinkedList) = (h = q.head; h === nothing ? nothing : (h.value, h))
iterate(q::InvasiveLinkedList{LLT}, v::LLT) where {LLT<:LinkedListItem} = (h = v.next; h === nothing ? nothing : (h.value, h))
push!(q::LinkedList{T}, val::T) where {T} = push!(q, LinkedListItem{T}(val))
pushfirst!(q::LinkedList{T}, val::T) where {T} = pushfirst!(q, LinkedListItem{T}(val))
pop!(q::LinkedList) = invoke(pop!, Tuple{InvasiveLinkedList,}, q).value
popfirst!(q::LinkedList) = invoke(popfirst!, Tuple{InvasiveLinkedList,}, q).value
function list_deletefirst!(q::LinkedList{T}, val::T) where T
h = q.head
while h !== nothing
if isequal(h.value, val)
list_deletefirst!(q, h)
break
end
h = h.next
end
return q
end
|
