basedOpinionated utility library |
| git clone git://git.dimitrijedobrota.com/based.git |
| Log | Files | Refs | README | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING |
list.hpp (4127B)
1 #pragma once 2 3 #include <cassert> 4 #include <functional> 5 #include <utility> 6 #include <vector> 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 = list_type(0); 25 }; 26 27 std::vector<node_t> m_pool; 28 list_type m_free_list; 29 30 const node_t& node(list_type x) const 31 { 32 assert(x != 0); 33 return m_pool[x - 1]; 34 } 35 36 node_t& node(list_type x) 37 { 38 assert(x != 0); 39 return m_pool[x - 1]; 40 } 41 42 list_type new_node() 43 { 44 m_pool.push_back(node_t()); 45 return list_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 bool is_empty(list_type x) const { return x == node_empty(); } 108 list_type node_empty() const { return list_type(0); } 109 110 const value_type& value(list_type x) const { return node(x).value; } 111 value_type& value(list_type x) { return node(x).value; } 112 113 const list_type& next(list_type x) const { return node(x).next; } 114 list_type& next(list_type x) { return node(x).next; } 115 116 list_type free(list_type x) 117 { 118 const list_type ret = next(x); 119 next(x) = m_free_list; 120 m_free_list = x; 121 return ret; 122 } 123 124 list_type free( 125 list_type front, // NOLINT bugprone-easily-swappable-parameters 126 list_type back) 127 { 128 if (is_empty(front)) { 129 return node_empty(); 130 } 131 132 const list_type ret = next(back); 133 next(back) = m_free_list; 134 m_free_list = front; 135 return ret; 136 } 137 138 list_type allocate(const value_type& val, list_type tail) 139 { 140 list_type new_list = m_free_list; 141 142 if (is_empty(new_list)) { 143 new_list = new_node(); 144 } else { 145 m_free_list = next(m_free_list); 146 } 147 148 value(new_list) = val; 149 next(new_list) = tail; 150 return new_list; 151 } 152 153 using queue_t = std::pair<list_type, list_type>; 154 155 bool is_empty(const queue_t& queue) const { return is_empty(queue.first); } 156 queue_t queue_empty() { return {node_empty(), node_empty()}; } 157 158 queue_t push_front(const queue_t& queue, const value_type& val) 159 { 160 auto new_node = allocate(val, queue.first); 161 if (is_empty(queue)) { 162 return {new_node, new_node}; 163 } 164 return {new_node, queue.second}; 165 } 166 167 queue_t push_back(const queue_t& queue, const value_type& val) 168 { 169 auto new_node = allocate(val, node_empty()); 170 if (is_empty(queue)) { 171 return {new_node, new_node}; 172 } 173 next(queue.second) = new_node; 174 return {queue.first, new_node}; 175 } 176 177 queue_t pop_front(const queue_t& queue) 178 { 179 if (is_empty(queue)) { 180 return queue; 181 } 182 queue_t ret = {next(queue.first), queue.second}; 183 free(queue.first); 184 return ret; 185 } 186 187 void free(const queue_t& queue) { free(queue.first, queue.second); } 188 }; 189 190 template<typename T, typename N> 191 void free_list(list_pool<T, N>& pool, typename list_pool<T, N>::list_type x) 192 { 193 while (!pool.is_empty(x)) { 194 x = pool.free(x); 195 } 196 } 197 198 } // namespace based