comparison: src/containers.h
src/containers.h
- changeset 73
- 1ee9b312dc18
- parent 72
- 03e4d9db3fd9
- child 75
- bf8c57437231
equal
deleted
inserted
replaced
| 72:03e4d9db3fd9 | 73:1ee9b312dc18 |
|---|---|
| 1 #ifndef LIBCOBALT_CONTAINERS_H | 1 /* |
| 2 #define LIBCOBALT_CONTAINERS_H | 2 Copyright (c) 2013-2014, Santeri Piippo |
| 3 All rights reserved. | |
| 4 | |
| 5 Redistribution and use in source and binary forms, with or without | |
| 6 modification, are permitted provided that the following conditions are met: | |
| 7 | |
| 8 * Redistributions of source code must retain the above copyright | |
| 9 notice, this list of conditions and the following disclaimer. | |
| 10 | |
| 11 * Redistributions in binary form must reproduce the above copyright | |
| 12 notice, this list of conditions and the following disclaimer in the | |
| 13 documentation and/or other materials provided with the distribution. | |
| 14 | |
| 15 * Neither the name of the <organization> nor the | |
| 16 names of its contributors may be used to endorse or promote products | |
| 17 derived from this software without specific prior written permission. | |
| 18 | |
| 19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND | |
| 20 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED | |
| 21 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | |
| 22 DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY | |
| 23 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | |
| 24 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |
| 25 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND | |
| 26 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
| 27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS | |
| 28 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
| 29 */ | |
| 30 | |
| 31 #ifndef BOTC_CONTAINERS_H | |
| 32 #define BOTC_CONTAINERS_H | |
| 3 | 33 |
| 4 #include <cassert> | 34 #include <cassert> |
| 5 #include <algorithm> | 35 #include <algorithm> |
| 6 #include <deque> | 36 #include <deque> |
| 7 #include <initializer_list> | 37 #include <initializer_list> |
| 8 | 38 |
| 9 template<class T> class list | 39 template<class T> class list |
| 10 { | 40 { |
| 11 public: | 41 public: |
| 12 typedef typename ::std::deque<T> list_type; | 42 typedef typename ::std::deque<T> list_type; |
| 13 typedef typename list_type::iterator it; | 43 typedef typename list_type::iterator it; |
| 14 typedef typename list_type::const_iterator c_it; | 44 typedef typename list_type::const_iterator c_it; |
| 15 typedef typename list_type::reverse_iterator r_it; | 45 typedef typename list_type::reverse_iterator r_it; |
| 16 typedef typename list_type::const_reverse_iterator cr_it; | 46 typedef typename list_type::const_reverse_iterator cr_it; |
| 17 typedef T element_type; | 47 typedef T element_type; |
| 18 typedef list<T> self_type; | 48 typedef list<T> self_type; |
| 19 | 49 |
| 20 list() {} | 50 // ===================================================================== |
| 21 list (std::initializer_list<element_type> vals) | 51 // |
| 22 { | 52 list() {} |
| 23 m_data = vals; | 53 |
| 24 } | 54 // ===================================================================== |
| 25 | 55 // |
| 26 list (const list_type& a) : m_data (a) {} | 56 list (std::initializer_list<element_type> vals) |
| 27 | 57 { |
| 28 it begin() | 58 m_data = vals; |
| 29 { | 59 } |
| 30 return m_data.begin(); | 60 |
| 31 } | 61 // ===================================================================== |
| 32 | 62 // |
| 33 c_it begin() const | 63 list (const list_type& a) : |
| 34 { | 64 m_data (a) {} |
| 35 return m_data.cbegin(); | 65 |
| 36 } | 66 // ===================================================================== |
| 37 | 67 // |
| 38 it end() | 68 it begin() |
| 39 { | 69 { |
| 40 return m_data.end(); | 70 return m_data.begin(); |
| 41 } | 71 } |
| 42 | 72 |
| 43 c_it end() const | 73 // ===================================================================== |
| 44 { | 74 // |
| 45 return m_data.cend(); | 75 c_it begin() const |
| 46 } | 76 { |
| 47 | 77 return m_data.cbegin(); |
| 48 r_it rbegin() | 78 } |
| 49 { | 79 |
| 50 return m_data.rbegin(); | 80 // ===================================================================== |
| 51 } | 81 // |
| 52 | 82 it end() |
| 53 cr_it crbegin() const | 83 { |
| 54 { | 84 return m_data.end(); |
| 55 return m_data.crbegin(); | 85 } |
| 56 } | 86 |
| 57 | 87 // ===================================================================== |
| 58 r_it rend() | 88 // |
| 59 { | 89 c_it end() const |
| 60 return m_data.rend(); | 90 { |
| 61 } | 91 return m_data.cend(); |
| 62 | 92 } |
| 63 cr_it crend() const | 93 |
| 64 { | 94 // ===================================================================== |
| 65 return m_data.crend(); | 95 // |
| 66 } | 96 r_it rbegin() |
| 67 | 97 { |
| 68 void erase (int pos) | 98 return m_data.rbegin(); |
| 69 { | 99 } |
| 70 assert (pos < size()); | 100 |
| 71 m_data.erase (m_data.begin() + pos); | 101 // ===================================================================== |
| 72 } | 102 // |
| 73 | 103 cr_it crbegin() const |
| 74 element_type& push_front (const element_type& value) | 104 { |
| 75 { | 105 return m_data.crbegin(); |
| 76 m_data.push_front (value); | 106 } |
| 77 return m_data[0]; | 107 |
| 78 } | 108 // ===================================================================== |
| 79 | 109 // |
| 80 element_type& push_back (const element_type& value) | 110 r_it rend() |
| 81 { | 111 { |
| 82 m_data.push_back (value); | 112 return m_data.rend(); |
| 83 return m_data[m_data.size() - 1]; | 113 } |
| 84 } | 114 |
| 85 | 115 // ===================================================================== |
| 86 void push_back (const self_type& vals) | 116 // |
| 87 { | 117 cr_it crend() const |
| 88 for (const T & val : vals) | 118 { |
| 89 push_back (val); | 119 return m_data.crend(); |
| 90 } | 120 } |
| 91 | 121 |
| 92 bool pop (T& val) | 122 // ===================================================================== |
| 93 { | 123 // |
| 94 if (size() == 0) | 124 inline void erase (int pos) |
| 95 return false; | 125 { |
| 96 | 126 assert (pos < size()); |
| 97 val = m_data[size() - 1]; | 127 m_data.erase (m_data.begin() + pos); |
| 98 erase (size() - 1); | 128 } |
| 99 return true; | 129 |
| 100 } | 130 // ===================================================================== |
| 101 | 131 // |
| 102 T& operator<< (const T& value) | 132 element_type& push_front (const element_type& value) |
| 103 { | 133 { |
| 104 return push_back (value); | 134 m_data.push_front (value); |
| 105 } | 135 return m_data[0]; |
| 106 | 136 } |
| 107 void operator<< (const self_type& vals) | 137 |
| 108 { | 138 // ===================================================================== |
| 109 push_back (vals); | 139 // |
| 110 } | 140 element_type& push_back (const element_type& value) |
| 111 | 141 { |
| 112 bool operator>> (T& value) | 142 m_data.push_back (value); |
| 113 { | 143 return m_data[m_data.size() - 1]; |
| 114 return pop (value); | 144 } |
| 115 } | 145 |
| 116 | 146 // ===================================================================== |
| 117 self_type reverse() const | 147 // |
| 118 { | 148 void push_back (const self_type& vals) |
| 119 self_type rev; | 149 { |
| 120 | 150 for (const T & val : vals) |
| 121 for (const T & val : *this) | 151 push_back (val); |
| 122 val >> rev; | 152 } |
| 123 | 153 |
| 124 return rev; | 154 // ===================================================================== |
| 125 } | 155 // |
| 126 | 156 bool pop (T& val) |
| 127 void clear() | 157 { |
| 128 { | 158 if (is_empty()) |
| 129 m_data.clear(); | 159 return false; |
| 130 } | 160 |
| 131 | 161 val = m_data[size() - 1]; |
| 132 void insert (int pos, const element_type& value) | 162 m_data.erase (m_data.end() - 1); |
| 133 { | 163 return true; |
| 134 m_data.insert (m_data.begin() + pos, value); | 164 } |
| 135 } | 165 |
| 136 | 166 // ===================================================================== |
| 137 void makeUnique() | 167 // |
| 138 { | 168 T& operator<< (const T& value) |
| 139 // Remove duplicate entries. For this to be effective, the vector must be | 169 { |
| 140 // sorted first. | 170 return push_back (value); |
| 141 sort(); | 171 } |
| 142 it pos = std::unique (begin(), end()); | 172 |
| 143 resize (std::distance (begin(), pos)); | 173 // ===================================================================== |
| 144 } | 174 // |
| 145 | 175 void operator<< (const self_type& vals) |
| 146 int size() const | 176 { |
| 147 { | 177 push_back (vals); |
| 148 return m_data.size(); | 178 } |
| 149 } | 179 |
| 150 | 180 // ===================================================================== |
| 151 element_type& operator[] (int n) | 181 // |
| 152 { | 182 bool operator>> (T& value) |
| 153 assert (n < size()); | 183 { |
| 154 return m_data[n]; | 184 return pop (value); |
| 155 } | 185 } |
| 156 | 186 |
| 157 const element_type& operator[] (int n) const | 187 // ===================================================================== |
| 158 { | 188 // |
| 159 assert (n < size()); | 189 self_type reverse() const |
| 160 return m_data[n]; | 190 { |
| 161 } | 191 self_type rev; |
| 162 | 192 |
| 163 void resize (std::ptrdiff_t size) | 193 for (const T & val : *this) |
| 164 { | 194 val >> rev; |
| 165 m_data.resize (size); | 195 |
| 166 } | 196 return rev; |
| 167 | 197 } |
| 168 void sort() | 198 |
| 169 { | 199 // ===================================================================== |
| 170 std::sort (begin(), end()); | 200 // |
| 171 } | 201 void clear() |
| 172 | 202 { |
| 173 int find (const element_type& needle) | 203 m_data.clear(); |
| 174 { | 204 } |
| 175 int i = 0; | 205 |
| 176 | 206 // ===================================================================== |
| 177 for (const element_type & hay : *this) | 207 // |
| 178 { | 208 void insert (int pos, const element_type& value) |
| 179 if (hay == needle) | 209 { |
| 180 return i; | 210 m_data.insert (m_data.begin() + pos, value); |
| 181 | 211 } |
| 182 i++; | 212 |
| 183 } | 213 // ===================================================================== |
| 184 | 214 // |
| 185 return -1; | 215 void makeUnique() |
| 186 } | 216 { |
| 187 | 217 // Remove duplicate entries. For this to be effective, the vector must be |
| 188 void remove (const element_type& it) | 218 // sorted first. |
| 189 { | 219 sort(); |
| 190 int idx; | 220 it pos = std::unique (begin(), end()); |
| 191 | 221 resize (std::distance (begin(), pos)); |
| 192 if ( (idx = find (it)) != -1) | 222 } |
| 193 erase (idx); | 223 |
| 194 } | 224 // ===================================================================== |
| 195 | 225 // |
| 196 inline bool is_empty() const | 226 int size() const |
| 197 { | 227 { |
| 198 return size() == 0; | 228 return m_data.size(); |
| 199 } | 229 } |
| 200 | 230 |
| 201 self_type mid (int a, int b) const | 231 // ===================================================================== |
| 202 { | 232 // |
| 203 assert (a >= 0 && b >= 0 && a < size() && b < size() && a <= b); | 233 element_type& operator[] (int n) |
| 204 self_type result; | 234 { |
| 205 | 235 assert (n < size()); |
| 206 for (int i = a; i <= b; ++i) | 236 return m_data[n]; |
| 207 result << operator[] (i); | 237 } |
| 208 | 238 |
| 209 return result; | 239 // ===================================================================== |
| 210 } | 240 // |
| 211 | 241 const element_type& operator[] (int n) const |
| 212 inline const list_type& std_deque() const | 242 { |
| 213 { | 243 assert (n < size()); |
| 214 return m_data; | 244 return m_data[n]; |
| 215 } | 245 } |
| 216 | 246 |
| 217 private: | 247 // ===================================================================== |
| 218 list_type m_data; | 248 // |
| 249 void resize (int size) | |
| 250 { | |
| 251 m_data.resize (size); | |
| 252 } | |
| 253 | |
| 254 // ===================================================================== | |
| 255 // | |
| 256 void sort() | |
| 257 { | |
| 258 std::sort (begin(), end()); | |
| 259 } | |
| 260 | |
| 261 // ===================================================================== | |
| 262 // | |
| 263 int find (const element_type& needle) | |
| 264 { | |
| 265 int i = 0; | |
| 266 | |
| 267 for (const element_type & hay : *this) | |
| 268 { | |
| 269 if (hay == needle) | |
| 270 return i; | |
| 271 | |
| 272 i++; | |
| 273 } | |
| 274 | |
| 275 return -1; | |
| 276 } | |
| 277 | |
| 278 // ===================================================================== | |
| 279 // | |
| 280 void remove (const element_type& it) | |
| 281 { | |
| 282 int idx; | |
| 283 | |
| 284 if ((idx = find (it)) != -1) | |
| 285 erase (idx); | |
| 286 } | |
| 287 | |
| 288 // ===================================================================== | |
| 289 // | |
| 290 inline bool is_empty() const | |
| 291 { | |
| 292 return size() == 0; | |
| 293 } | |
| 294 | |
| 295 // ===================================================================== | |
| 296 // | |
| 297 self_type mid (int a, int b) const | |
| 298 { | |
| 299 assert (a >= 0 && b >= 0 && a < size() && b < size() && a <= b); | |
| 300 self_type result; | |
| 301 | |
| 302 for (int i = a; i <= b; ++i) | |
| 303 result << operator[] (i); | |
| 304 | |
| 305 return result; | |
| 306 } | |
| 307 | |
| 308 // ===================================================================== | |
| 309 // | |
| 310 inline const list_type& std_deque() const | |
| 311 { | |
| 312 return m_data; | |
| 313 } | |
| 314 | |
| 315 // ===================================================================== | |
| 316 // | |
| 317 const element_type& first() const | |
| 318 { | |
| 319 return *(m_data.begin()); | |
| 320 } | |
| 321 | |
| 322 // ===================================================================== | |
| 323 // | |
| 324 const element_type& last() const | |
| 325 { | |
| 326 return *(m_data.end()); | |
| 327 } | |
| 328 | |
| 329 // ===================================================================== | |
| 330 // | |
| 331 bool contains (const element_type& a) const | |
| 332 { | |
| 333 return find (a) != -1; | |
| 334 } | |
| 335 | |
| 336 private: | |
| 337 list_type m_data; | |
| 219 }; | 338 }; |
| 220 | 339 |
| 340 // ============================================================================= | |
| 341 // | |
| 221 template<class T> list<T>& operator>> (const T& value, list<T>& haystack) | 342 template<class T> list<T>& operator>> (const T& value, list<T>& haystack) |
| 222 { | 343 { |
| 223 haystack.push_front (value); | 344 haystack.push_front (value); |
| 224 return haystack; | 345 return haystack; |
| 225 } | 346 } |
| 226 | 347 |
| 227 #endif // LIBCOBALT_CONTAINERS_H | 348 #endif // BOTC_CONTAINERS_H |
