basedOpinionated utility library |
| git clone git://git.dimitrijedobrota.com/based.git |
| Log | Files | Refs | README | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING | |
list.hpp (4045B)
1 #pragma once 2 3 #include <functional> 4 #include <utility> 5 #include <vector> 6 7 namespace based 8 { 9 10 template<typename T, typename N> 11 // T semiregular 12 // N integral 13 class list_pool 14 { 15 public: 16 using value_type = T; 17 using list_type = N; 18 19 private: 20 struct node_t 21 { 22 value_type value; 23 list_type next = list_type(0); 24 }; 25 26 std::vector<node_t> m_pool; 27 list_type m_free_list; 28 29 const node_t& node(list_type x) const { return m_pool[x - 1]; } 30 node_t& node(list_type x) { return m_pool[x - 1]; } 31 32 list_type new_node() 33 { 34 m_pool.push_back(node_t()); 35 return list_type(m_pool.size()); 36 } 37 38 public: 39 list_pool() 40 : m_free_list(node_empty()) 41 { 42 } 43 44 struct iterator 45 { 46 using iterator_category = std::forward_iterator_tag; 47 using difference_type = list_pool::list_type; 48 using value_type = list_pool::value_type; 49 using reference = value_type&; 50 using pointer = value_type*; 51 52 iterator() = default; 53 54 explicit iterator(list_pool& pool) 55 : iterator(pool, pool.node_empty()) 56 { 57 } 58 59 iterator(list_pool& pool, list_pool::list_type node) 60 : m_pool(pool) 61 , m_node(node) 62 { 63 } 64 65 reference operator*() const { return m_pool.get().value(m_node); } 66 pointer operator->() const { return &**this; } 67 68 iterator& operator++() 69 { 70 m_node = m_pool.get().next(m_node); 71 return *this; 72 } 73 74 iterator operator++(int) 75 { 76 iterator tmp(*this); 77 ++*this; 78 return tmp; 79 } 80 81 friend bool operator==(const iterator& x, const iterator& y) 82 { 83 // assert(x.m_pool == y.m_pool); 84 return x.m_node == y.m_node; 85 } 86 87 friend bool operator!=(const iterator& x, const iterator& y) 88 { 89 return !(x == y); 90 } 91 92 private: 93 std::reference_wrapper<list_pool> m_pool; 94 list_pool::list_type m_node; 95 }; 96 97 bool is_empty(list_type x) const { return x == node_empty(); } 98 list_type node_empty() const { return list_type(0); } 99 100 const value_type& value(list_type x) const { return node(x).value; } 101 value_type& value(list_type x) { return node(x).value; } 102 103 const list_type& next(list_type x) const { return node(x).next; } 104 list_type& next(list_type x) { return node(x).next; } 105 106 list_type free(list_type x) 107 { 108 const list_type ret = next(x); 109 next(x) = m_free_list; 110 m_free_list = x; 111 return ret; 112 } 113 114 list_type free( 115 list_type front, // NOLINT bugprone-easily-swappable-parameters 116 list_type back) 117 { 118 if (is_empty(front)) { 119 return node_empty(); 120 } 121 122 const list_type ret = next(back); 123 next(back) = m_free_list; 124 m_free_list = front; 125 return ret; 126 } 127 128 list_type allocate(const value_type& val, list_type tail) 129 { 130 list_type new_list = m_free_list; 131 132 if (is_empty(new_list)) { 133 new_list = new_node(); 134 } else { 135 m_free_list = next(m_free_list); 136 } 137 138 value(new_list) = val; 139 next(new_list) = tail; 140 return new_list; 141 } 142 143 using queue_t = std::pair<list_type, list_type>; 144 145 bool is_empty(const queue_t& que) const { return is_empty(que.first); } 146 queue_t queue_empty() { return {node_empty(), node_empty()}; } 147 148 queue_t push_front(const queue_t& que, const value_type& val) 149 { 150 auto new_node = allocate(val, que.first); 151 if (is_empty(que)) { 152 return {new_node, new_node}; 153 } 154 return {new_node, que.second}; 155 } 156 157 queue_t push_back(const queue_t& que, const value_type& val) 158 { 159 auto new_node = allocate(val, node_empty()); 160 if (is_empty(que)) { 161 return {new_node, new_node}; 162 } 163 next(que.second) = new_node; 164 return {que.first, new_node}; 165 } 166 167 queue_t pop_front(const queue_t& que) 168 { 169 if (is_empty(que)) { 170 return que; 171 } 172 queue_t ret = {next(que.first), que.second}; 173 free(que.first); 174 return ret; 175 } 176 177 void free(const queue_t& que) { free(que.first, que.second); } 178 }; 179 180 template<typename T, typename N> 181 void free_list(list_pool<T, N>& pool, typename list_pool<T, N>::list_type x) 182 { 183 while (!pool.is_empty(x)) { 184 x = pool.free(x); 185 } 186 } 187 188 } // namespace based