blob: ab552c46647a1bf7f0f84c7d00f1b64e55fe228f (
plain)
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
|
#pragma once
#include <utility>
namespace AK {
template<typename T>
class SinglyLinkedList {
private:
struct Node {
explicit Node(T&& v) : value(v) { }
T value;
Node* next { nullptr };
};
public:
SinglyLinkedList() { }
~SinglyLinkedList() { clear(); }
bool is_empty() const { return !head(); }
void clear()
{
for (auto* node = m_head; node; ) {
auto* next = node->next;
delete node;
node = next;
}
m_head = nullptr;
m_tail = nullptr;
}
T& first() { ASSERT(head()); return head()->value; }
const T& first() const { ASSERT(head()); return head()->value; }
T& last() { ASSERT(head()); return tail()->value; }
const T& last() const { ASSERT(head()); return tail()->value; }
void append(T&& value)
{
auto* node = new Node(std::move(value));
if (!m_head) {
m_head = node;
m_tail = node;
return;
}
m_tail->next = node;
m_tail = node;
}
bool containsSlow(const T& value) const
{
for (auto* node = m_head; node; node = node->next) {
if (node->value == value)
return true;
}
return false;
}
class Iterator {
public:
bool operator!=(const Iterator& other) { return m_node != other.m_node; }
Iterator& operator++() { m_node = m_node->next; return *this; }
T& operator*() { return m_node->value; }
bool isEnd() const { return !m_node; }
static Iterator universalEnd() { return Iterator(nullptr); }
private:
friend class SinglyLinkedList;
explicit Iterator(SinglyLinkedList::Node* node) : m_node(node) { }
SinglyLinkedList::Node* m_node;
};
Iterator begin() { return Iterator(m_head); }
Iterator end() { return Iterator::universalEnd(); }
class ConstIterator {
public:
bool operator!=(const ConstIterator& other) { return m_node != other.m_node; }
ConstIterator& operator++() { m_node = m_node->next; return *this; }
const T& operator*() const { return m_node->value; }
bool isEnd() const { return !m_node; }
static ConstIterator universalEnd() { return ConstIterator(nullptr); }
private:
friend class SinglyLinkedList;
explicit ConstIterator(const SinglyLinkedList::Node* node) : m_node(node) { }
const SinglyLinkedList::Node* m_node;
};
ConstIterator begin() const { return ConstIterator(m_head); }
ConstIterator end() const { return ConstIterator::universalEnd(); }
ConstIterator find(const T& value) const
{
for (auto* node = m_head; node; node = node->next) {
if (node->value == value)
return ConstIterator(node);
}
return end();
}
Iterator find(const T& value)
{
for (auto* node = m_head; node; node = node->next) {
if (node->value == value)
return Iterator(node);
}
return end();
}
private:
friend class Iterator;
Node* head() { return m_head; }
const Node* head() const { return m_head; }
Node* tail() { return m_tail; }
const Node* tail() const { return m_tail; }
Node* m_head { nullptr };
Node* m_tail { nullptr };
};
}
using AK::SinglyLinkedList;
|
