based

0 #pragma once

1

2 #include <cassert>

3 #include <vector>

4

5 #include "based/concepts/is/same.hpp"

6 #include "based/types/types.hpp"

7

8 namespace based

9 {

10

11 template<typename T, typename N>

12 // T semiregular

13 // N integral

14 class list_pool

15 {

16 public:

17 using value_type = T;

18 using list_type = N;

19

20 private:

21 struct node_t

22 {

23 value_type value {};

24 list_type next;

25 };

26

27 std::vector<node_t> m_pool;

28 list_type m_free_list;

29

30 [[nodiscard]] const node_t& node(list_type x) const

31 {

32 assert(x != list_type(0));

33 return m_pool[(x - list_type(1)).value];

34 }

35

36 [[nodiscard]] node_t& node(list_type x)

37 {

38 assert(x != list_type(0));

39 return m_pool[(x - list_type(1)).value];

40 }

41

42 [[nodiscard]] list_type new_node()

43 {

44 m_pool.push_back(node_t());

45 return list_type {static_cast<list_type::basic_type>(m_pool.size())};

46 }

47

48 public:

49 list_pool()

50 : m_free_list(node_empty())

51 {

52 }

53

54 struct iterator

55 {

56 using iterator_category = std::forward_iterator_tag;

57 using difference_type = list_pool::list_type;

58 using value_type = list_pool::value_type;

59 using reference = value_type&;

60 using pointer = value_type*;

61

62 iterator() = default;

63

64 explicit iterator(list_pool& pool)

65 : iterator(pool, pool.node_empty())

66 {

67 }

68

69 iterator(list_pool& pool, list_pool::list_type node)

70 : m_pool(&pool)

71 , m_node(node)

72 {

73 }

74

75 reference operator*() const { return m_pool->value(m_node); }

76 pointer operator->() const { return &**this; }

77

78 iterator& operator++()

79 {

80 m_node = m_pool->next(m_node);

81 return *this;

82 }

83

84 iterator operator++(int)

85 {

86 iterator tmp(*this);

87 ++*this;

88 return tmp;

89 }

90

91 friend bool operator==(const iterator& x, const iterator& y)

92 {

93 assert(x.m_pool == y.m_pool);

94 return x.m_node == y.m_node;

95 }

96

97 friend bool operator!=(const iterator& x, const iterator& y)

98 {

99 return !(x == y);

100 }

101

102 private:

103 list_pool* m_pool;

104 list_pool::list_type m_node;

105 };

106

107 struct const_iterator

108 {

109 using iterator_category = std::forward_iterator_tag;

110 using difference_type = list_pool::list_type;

111 using value_type = list_pool::value_type;

112 using reference = const value_type&;

113 using pointer = const value_type*;

114

115 const_iterator() = default;

116

117 explicit const_iterator(const list_pool& pool)

118 : const_iterator(pool, pool.node_empty())

119 {

120 }

121

122 const_iterator(const list_pool& pool, list_pool::list_type node)

123 : m_pool(&pool)

124 , m_node(node)

125 {

126 }

127

128 reference operator*() const { return m_pool->value(m_node); }

129 pointer operator->() const { return &**this; }

130

131 const_iterator& operator++()

132 {

133 m_node = m_pool->next(m_node);

134 return *this;

135 }

136

137 const_iterator operator++(int)

138 {

139 const_iterator tmp(*this);

140 ++*this;

141 return tmp;

142 }

143

144 friend bool operator==(const const_iterator& x, const const_iterator& y)

145 {

146 assert(x.m_pool == y.m_pool);

147 return x.m_node == y.m_node;

148 }

149

150 friend bool operator!=(const const_iterator& x, const const_iterator& y)

151 {

152 return !(x == y);

153 }

154

155 private:

156 const list_pool* m_pool;

157 list_pool::list_type m_node;

158 };

159

160 [[nodiscard]] bool is_empty(list_type x) const { return x == node_empty(); }

161 [[nodiscard]] list_type node_empty() const { return list_type(0); }

162

163 [[nodiscard]] const value_type& value(list_type x) const

164 {

165 return node(x).value;

166 }

167 [[nodiscard]] value_type& value(list_type x) { return node(x).value; }

168

169 [[nodiscard]] const list_type& next(list_type x) const

170 {

171 return node(x).next;

172 }

173 [[nodiscard]] list_type& next(list_type x) { return node(x).next; }

174

175 list_type free(list_type x)

176 {

177 const list_type ret = next(x);

178 next(x) = m_free_list;

179 m_free_list = x;

180 return ret;

181 }

182

183 list_type free(

184 list_type front, // NOLINT(*swappable*)

185 list_type back

186 )

187 {

188 if (is_empty(front)) {

189 return node_empty();

190 }

191

192 const list_type ret = next(back);

193 next(back) = m_free_list;

194 m_free_list = front;

195 return ret;

196 }

197

198 [[nodiscard]] list_type allocate(const value_type& val, list_type tail)

199 {

200 list_type new_list = m_free_list;

201

202 if (is_empty(new_list)) {

203 new_list = new_node();

204 } else {

205 m_free_list = next(m_free_list);

206 }

207

208 value(new_list) = val;

209 next(new_list) = tail;

210 return new_list;

211 }

212

213 using queue_t = std::pair<list_type, list_type>;

214

215 [[nodiscard]] bool is_empty(const queue_t& queue) const

216 {

217 return is_empty(queue.first);

218 }

219 [[nodiscard]] queue_t queue_empty() { return {node_empty(), node_empty()}; }

220

221 [[nodiscard]] queue_t push_front(const queue_t& queue, const value_type& val)

222 {

223 auto new_node = allocate(val, queue.first);

224 if (is_empty(queue)) {

225 return {new_node, new_node};

226 }

227 return {new_node, queue.second};

228 }

229

230 [[nodiscard]] queue_t push_back(const queue_t& queue, const value_type& val)

231 {

232 auto new_node = allocate(val, node_empty());

233 if (is_empty(queue)) {

234 return {new_node, new_node};

235 }

236 next(queue.second) = new_node;

237 return {queue.first, new_node};

238 }

239

240 [[nodiscard]] queue_t pop_front(const queue_t& queue)

241 {

242 if (is_empty(queue)) {

243 return queue;

244 }

245 queue_t ret = {next(queue.first), queue.second};

246 free(queue.first);

247 return ret;

248 }

249

250 void free(const queue_t& queue) { free(queue.first, queue.second); }

251 };

252

253 template<typename T, typename N>

254 void free_list(list_pool<T, N>& pool, typename list_pool<T, N>::list_type x)

255 {

256 while (!pool.is_empty(x)) {

257 x = pool.free(x);

258 }

259 }

260

261 } // namespace based