-
Notifications
You must be signed in to change notification settings - Fork 1
/
linked_list.ex
108 lines (87 loc) · 2.69 KB
/
linked_list.ex
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
defmodule Dasie.LinkedList do
@moduledoc """
Linked list.
https://en.wikipedia.org/wiki/Linked_list
This is a bit contrived, but was still fun to do.
"""
defstruct data: nil,
next: nil,
empty: false
@type t :: %__MODULE__{
data: any,
next: t | nil,
empty: boolean
}
@doc "Create a new empty linked list"
@spec new() :: __MODULE__.t()
def new(), do: %__MODULE__{empty: true}
@doc "Create a new linked list with some elements"
@spec new(elements :: any) :: __MODULE__.t()
def new([element]) do
new(element)
end
def new([h | tail]) do
add(new(h), tail)
end
def new(data) do
%__MODULE__{data: data}
end
@doc "Adds an element to the end of the list"
@spec add(list :: __MODULE__.t(), elements :: any) :: __MODULE__.t()
def add(%__MODULE__{} = list, elements) when is_list(elements) do
Enum.reduce(elements, list, fn element, acc ->
add(acc, element)
end)
end
def add(%__MODULE__{empty: true} = list, data) do
%__MODULE__{list | data: data, empty: false}
end
def add(%__MODULE__{next: nil} = list, data) do
%__MODULE__{list | next: new(data)}
end
def add(%__MODULE__{} = list, data) do
%__MODULE__{list | next: add(list.next, data)}
end
@doc "Returns the first element in the list"
@spec first(list :: __MODULE__.t()) :: any
def first(%__MODULE__{data: data}), do: data
def last(%__MODULE__{next: nil, data: data}), do: data
def last(%__MODULE__{next: next}) do
last(next)
end
@doc "Reverses the linked list"
@spec reverse(list :: __MODULE__.t()) :: __MODULE__.t()
def reverse(list) do
list
|> values()
|> Enum.reverse()
|> new()
end
@doc "Returns the items in the list"
@spec values(list :: __MODULE__.t()) :: list(any)
def values(%__MODULE__{next: nil, data: data}), do: [data]
def values(%__MODULE__{next: next, data: data}) do
[data | values(next)]
end
@doc "Deletes an element from the list"
@spec delete(list :: __MODULE__.t(), element :: any) :: __MODULE__.t()
def delete(%__MODULE__{next: nil, data: data}, element) when data == element do
new()
end
def delete(%__MODULE__{next: next, data: data}, element) when data == element do
next
end
def delete(%__MODULE__{next: next, data: data} = list, element) when data != element do
%__MODULE__{list | next: delete(next, element)}
end
defimpl Collectable, for: Dasie.LinkedList do
def into(original) do
collector_fun = fn
linked_list, {:cont, elem} -> Dasie.LinkedList.add(linked_list, elem)
linked_list, :done -> linked_list
_linked_list, :halt -> :ok
end
{original, collector_fun}
end
end
end