-
Notifications
You must be signed in to change notification settings - Fork 1
/
QuickList.h
229 lines (173 loc) · 7.27 KB
/
QuickList.h
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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Product: AWL (A Working Library)
// Author: Dmitriano
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#pragma once
#include "Awl/SingleList.h"
#include "Awl/DoubleIterator.h"
#include "Awl/QuickLink.h"
#include <cassert>
#include <initializer_list>
namespace awl
{
template <class T, class Link, class Derived>
class forward_list : public basic_single_list<T, Link, Derived>
{
};
template <class T, class Link, class Derived>
class backward_list : public basic_single_list<T, Link, Derived>
{
};
//! Doubly linked list consisting of two singly linked lists.
template < class T, class DLink = quick_link>
class quick_list :
private forward_list<T, typename DLink::ForwardLink, quick_list<T, DLink>>,
private backward_list<T, typename DLink::BackwardLink, quick_list<T, DLink>>
{
private:
using ForwardLink = typename DLink::ForwardLink;
using BackwardLink = typename DLink::BackwardLink;
using ForwardList = forward_list<T, typename DLink::ForwardLink, quick_list<T, DLink>>;
using BackwardList = backward_list<T, typename DLink::BackwardLink, quick_list<T, DLink>>;
ForwardList & forward() { return *this; }
const ForwardList & forward() const { return *this; }
BackwardList & backward() { return *this; }
const BackwardList & backward() const { return *this; }
public:
using value_type = T *;
using iterator = double_iterator<T, DLink, ForwardLink, BackwardLink>;
using const_iterator = double_iterator<const T, const DLink, const ForwardLink, const BackwardLink>;
using reverse_iterator = double_iterator<T, DLink, BackwardLink, ForwardLink>;
using const_reverse_iterator = double_iterator<const T, const DLink, const BackwardLink, const ForwardLink>;
//This also works, but I am not sure it is correct : Null(forward().null(), backward().null())
quick_list() : Null(&Null, &Null)
{
}
quick_list(std::initializer_list<value_type> init) : quick_list()
{
for (const value_type& val : init)
{
push_back(val);
}
}
quick_list(const quick_list& other) = delete;
quick_list(quick_list&& other) noexcept
{
attach(other);
}
quick_list& operator = (const quick_list& other) = delete;
quick_list& operator = (quick_list&& other) noexcept
{
if (this != &other)
{
//quick_list cannot free its resources, so it is supposed to be empty
assert(empty());
attach(other);
}
return *this;
}
//There can be using ForwardList::front, but not BackwardList::front.
T * front() { return forward().front(); }
const T * front() const { return forward().front(); }
T * back() { return backward().front(); }
const T * back() const { return backward().front(); }
iterator begin() { return forward().begin(); }
const_iterator begin() const { return forward().begin(); }
iterator end() { return forward().end(); }
const_iterator end() const { return forward().end(); }
reverse_iterator rbegin() { return backward().begin(); }
const_reverse_iterator rbegin() const { return backward().begin(); }
reverse_iterator rend() { return backward().end(); }
const_reverse_iterator rend() const { return backward().end(); }
bool empty() const { return forward().empty(); }
bool empty_or_contains_one() const { return forward().empty_or_contains_one(); }
bool contains_one() const { return forward().contains_one(); }
static void insert(iterator i, T * a) { insert_after(*i, a); }
static void erase(iterator i) { remove(*i); }
static_assert(!std::is_same<iterator, reverse_iterator>::value, "iterator and reverse_iterator are the same types.");
static void insert(reverse_iterator i, T * a) { insert_before(*i, a); }
static void erase(reverse_iterator i) { remove(*i); }
static void erase(T* a) { remove(a); }
void push_front(T * a) { insert_after(static_cast<DLink *>(forward().null()), a); }
void push_back(T * a) { insert_before(static_cast<DLink *>(forward().null()), a); }
T * pop_front() { return remove(forward().front()); }
T * pop_back() { return remove(backward().front()); }
void push_front(quick_list & src)
{
if (!src.empty())
{
DLink * first = src.first();
DLink * last = src.last();
DLink * old_last = this->first(); //the last element in the backward list
forward().push_front(first, last);
backward().push_back(last, first, old_last);
src.clear();
}
}
void push_back(quick_list & src)
{
if (!src.empty())
{
DLink * first = src.first();
DLink * last = src.last();
DLink * old_last = this->last(); //the last element in the forward list
forward().push_back(first, last, old_last);
backward().push_front(last, first);
src.clear();
}
}
void clear()
{
forward().clear();
backward().clear();
}
size_t size() const
{
return forward().size();
}
private:
DLink * first() { return static_cast<DLink *>(forward().first()); }
const DLink * first() const { return static_cast<const DLink *>(forward().first()); }
DLink * last() { return static_cast<DLink *>(backward().first()); }
const DLink * last() const { return static_cast<const DLink *>(backward().first()); }
//If T is included into multiple lists there can be multiple insert_after in T,
//so we cast T to DLink first.
static void insert_after(DLink * p, DLink * a) { p->insert_after(a); }
static void insert_before(DLink * p, DLink * a) { p->insert_before(a); }
void attach(quick_list & src)
{
if (src.empty())
{
clear();
}
else
{
T * first = src.front();
T * last = src.back();
attach(first, last);
src.clear();
}
}
void attach(T * first, T * last)
{
forward().attach(first, last);
backward().attach(last, first);
}
//! Excludes specified element from the list.
static T * remove(T * a)
{
a->DLink::exclude();
return a;
}
DLink Null;
template <class T1, class Link1, class Derived1> friend class basic_single_list;
};
}
#define AWL_DECLARE_QUICK_LINK(name) \
class name : public awl::basic_quick_link<name> \
{ \
private: \
using Base = basic_quick_link<name>; \
public:\
using Base::Base; \
};