1 /* StaticArrayList 2 * ArrayList without dynamic memory allocation 3 * 4 * Copyright (C) 2018 - 2020 by Sven Jähnichen 5 * 6 * This program is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation; either version 3, or (at your option) 9 * any later version. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software Foundation, 18 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 19 */ 20 21 #ifndef STATICARRAYLIST_HPP_ 22 #define STATICARRAYLIST_HPP_ 23 24 #include <cstddef> 25 #include <cstdio> 26 // #include <iostream> 27 28 template<typename T, std::size_t sz> struct StaticArrayList 29 { 30 T data[sz]; 31 T* iterator[sz + 1]; // +1 for end () 32 T** reverse_iterator[sz]; 33 std::size_t size; 34 StaticArrayListStaticArrayList35 StaticArrayList () : data {}, iterator {nullptr}, reverse_iterator {nullptr}, size (0) {} 36 37 /*StaticArrayList (T dataarray[sz]) : data (dataarray), iterator ({}), reverse_iterator ({}), size (sz) 38 { 39 for (size_t i = 0; i < size; ++i) 40 { 41 iterator[i] = &data[i]; 42 reverse_iterator[i] = &iterator[i]; 43 } 44 }*/ 45 StaticArrayListStaticArrayList46 StaticArrayList (const StaticArrayList& that) : data {}, iterator {nullptr}, reverse_iterator {nullptr}, size (that.size) 47 { 48 for (size_t i = 0; i < size; ++i) 49 { 50 iterator[i] = &data[i]; 51 reverse_iterator[i] = &iterator[i]; 52 data[i] = *that.iterator[i]; 53 } 54 } 55 operator =StaticArrayList56 StaticArrayList& operator= (const StaticArrayList& that) 57 { 58 clear(); 59 size = that.size; 60 for (size_t i = 0; i < that.size; ++i) 61 { 62 iterator[i] = &data[i]; 63 reverse_iterator[i] = &iterator[i]; 64 data[i] = *that.iterator[i]; 65 } 66 67 return *this; 68 } 69 clearStaticArrayList70 void clear () 71 { 72 size = 0; 73 memset (iterator, 0, (sz + 1) * sizeof (T*)); 74 memset (reverse_iterator, 0, sz * sizeof (T*)); 75 } 76 beginStaticArrayList77 T** begin () {return &iterator [0];} 78 endStaticArrayList79 T** end () {return &iterator[size];} 80 emptyStaticArrayList81 bool empty () const {return (size == 0);} 82 operator []StaticArrayList83 T& operator[] (const size_t n) {return *iterator[n];} 84 operator []StaticArrayList85 const T& operator[] (const size_t n) const {return *iterator[n];} 86 atStaticArrayList87 T& at (const size_t n) {return ((n >= 0) && (n < size) ? *iterator[n] : data[0]);} 88 atStaticArrayList89 const T& at (const size_t n) const {return ((n >= 0) && (n < size) ? *iterator[n] : data[0]);} 90 frontStaticArrayList91 T& front () {return *iterator[0];} 92 frontStaticArrayList93 const T& front () const {return *iterator[0];} 94 backStaticArrayList95 T& back () {return *iterator[size - 1];} 96 backStaticArrayList97 const T& back () const {return *iterator[size - 1];} 98 new_data_segmentStaticArrayList99 void new_data_segment (T** iterator_ptr) 100 { 101 T* new_ptr = &data[0]; 102 if (!empty ()) 103 { 104 new_ptr = iterator[sz - 1]; // Default: last segment 105 for (size_t i = 0; i < sz; ++i) // But look for the first free segment 106 { 107 if (!reverse_iterator[i]) 108 { 109 new_ptr = &data[i]; 110 //fprintf (stderr, "<%li> ", i); 111 break; 112 } 113 } 114 115 } 116 117 //fprintf (stderr, "%li %li %li\n", size, long (new_ptr), long (iterator[sz - 1])); 118 *iterator_ptr = new_ptr; 119 reverse_iterator[new_ptr - &data[0]] = iterator_ptr; 120 } 121 push_backStaticArrayList122 void push_back (const T& content) 123 { 124 T** end_ptr = (size < sz ? end () : end () - 1); 125 new_data_segment (end_ptr); 126 **end_ptr = content; 127 if (size < sz) ++size; 128 } 129 pop_backStaticArrayList130 void pop_back () 131 { 132 if (!empty ()) 133 { 134 T** last = end () - 1; 135 reverse_iterator[*last - &data[0]] = nullptr; 136 *last = nullptr; 137 --size; 138 } 139 } 140 eraseStaticArrayList141 T** erase (T** iterator_ptr) 142 { 143 T** end_iit = end (); 144 145 if (!empty ()) 146 { 147 if (iterator_ptr == end_iit - 1) 148 { 149 pop_back (); 150 return end (); // Return new(!) end 151 } 152 153 if ((iterator_ptr >= begin ()) && (iterator_ptr < end_iit)) 154 { 155 reverse_iterator[*iterator_ptr - &data[0]] = nullptr; 156 for (T** iit = iterator_ptr; iit < end_iit - 1; ++iit) 157 { 158 reverse_iterator[*(iit + 1) - &data[0]] = iit; 159 *iit = *(iit + 1); 160 } 161 *(end_iit - 1) = nullptr; // New end: nullptr 162 --size; 163 return iterator_ptr; 164 } 165 } 166 167 return end_iit; 168 } 169 insertStaticArrayList170 T** insert (T** iterator_ptr, const T& content) 171 { 172 T** end_iit = (size < sz ? end () : end () - 1); 173 174 if (iterator_ptr >= end_iit) 175 { 176 push_back (content); 177 return end () - 1; 178 } 179 180 if ((iterator_ptr >= begin ()) && (iterator_ptr < end_iit)) 181 { 182 if (size == sz) reverse_iterator[*end_iit - &data[0]] = nullptr; 183 184 for (T** iit = end_iit - 1; iit >= iterator_ptr; --iit) 185 { 186 reverse_iterator[*iit - &data[0]] = iit + 1; 187 *(iit + 1) = *iit; 188 } 189 190 new_data_segment (iterator_ptr); 191 **iterator_ptr = content; 192 if (size < sz) ++size; 193 return iterator_ptr; 194 } 195 196 else return end (); 197 } 198 push_frontStaticArrayList199 void push_front (const T& content) {insert (begin (), content);} 200 pop_frontStaticArrayList201 void pop_front () {erase (begin ());} 202 203 }; 204 205 /* 206 template<typename T, std::size_t sz> std::ostream &operator<<(std::ostream &output, StaticArrayList<T, sz>& list) 207 { 208 output << "{"; 209 for (T** it = list.begin (); it != list.end (); ++it) 210 { 211 if (it != list.begin ()) output << ", "; 212 output << **it; 213 } 214 output << "}"; 215 return output; 216 } 217 */ 218 219 #endif /* STATICARRAYLIST_HPP_ */ 220