ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

array.h

Go to the documentation of this file.
00001 /* ScummVM - Graphic Adventure Engine
00002  *
00003  * ScummVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the COPYRIGHT
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 #ifndef COMMON_ARRAY_H
00024 #define COMMON_ARRAY_H
00025 
00026 #include "common/scummsys.h"
00027 #include "common/algorithm.h"
00028 #include "common/textconsole.h" // For error()
00029 #include "common/memory.h"
00030 
00031 namespace Common {
00032 
00044 template<class T>
00045 class Array {
00046 public:
00047     typedef T *iterator;
00048     typedef const T *const_iterator;
00049 
00050     typedef T value_type;
00051 
00052     typedef uint size_type;
00053 
00054 protected:
00055     size_type _capacity;
00056     size_type _size;
00057     T *_storage;
00058 
00059 public:
00060     Array() : _capacity(0), _size(0), _storage(nullptr) {}
00061 
00066     explicit Array(size_type count) : _size(count) {
00067         allocCapacity(count);
00068         for (size_type i = 0; i < count; ++i)
00069             new ((void *)&_storage[i]) T();
00070     }
00071 
00075     Array(size_type count, const T &value) : _size(count) {
00076         allocCapacity(count);
00077         uninitialized_fill_n(_storage, count, value);
00078     }
00079 
00080     Array(const Array<T> &array) : _capacity(array._size), _size(array._size), _storage(nullptr) {
00081         if (array._storage) {
00082             allocCapacity(_size);
00083             uninitialized_copy(array._storage, array._storage + _size, _storage);
00084         }
00085     }
00086 
00090     template<class T2>
00091     Array(const T2 *array, size_type n) {
00092         _size = n;
00093         allocCapacity(n);
00094         uninitialized_copy(array, array + _size, _storage);
00095     }
00096 
00097     ~Array() {
00098         freeStorage(_storage, _size);
00099         _storage = nullptr;
00100         _capacity = _size = 0;
00101     }
00102 
00104     void push_back(const T &element) {
00105         if (_size + 1 <= _capacity)
00106             new ((void *)&_storage[_size++]) T(element);
00107         else
00108             insert_aux(end(), &element, &element + 1);
00109     }
00110 
00111     void push_back(const Array<T> &array) {
00112         if (_size + array.size() <= _capacity) {
00113             uninitialized_copy(array.begin(), array.end(), end());
00114             _size += array.size();
00115         } else
00116             insert_aux(end(), array.begin(), array.end());
00117     }
00118 
00120     void pop_back() {
00121         assert(_size > 0);
00122         _size--;
00123         // We also need to destroy the last object properly here.
00124         _storage[_size].~T();
00125     }
00126 
00128     const T *data() const {
00129         return _storage;
00130     }
00131 
00133     T *data() {
00134         return _storage;
00135     }
00136 
00138     T &front() {
00139         assert(_size > 0);
00140         return _storage[0];
00141     }
00142 
00144     const T &front() const {
00145         assert(_size > 0);
00146         return _storage[0];
00147     }
00148 
00150     T &back() {
00151         assert(_size > 0);
00152         return _storage[_size-1];
00153     }
00154 
00156     const T &back() const {
00157         assert(_size > 0);
00158         return _storage[_size-1];
00159     }
00160 
00161 
00162     void insert_at(size_type idx, const T &element) {
00163         assert(idx <= _size);
00164         insert_aux(_storage + idx, &element, &element + 1);
00165     }
00166 
00167     void insert_at(size_type idx, const Array<T> &array) {
00168         assert(idx <= _size);
00169         insert_aux(_storage + idx, array.begin(), array.end());
00170     }
00171 
00175     void insert(iterator pos, const T &element) {
00176         insert_aux(pos, &element, &element + 1);
00177     }
00178 
00179     T remove_at(size_type idx) {
00180         assert(idx < _size);
00181         T tmp = _storage[idx];
00182         copy(_storage + idx + 1, _storage + _size, _storage + idx);
00183         _size--;
00184         // We also need to destroy the last object properly here.
00185         _storage[_size].~T();
00186         return tmp;
00187     }
00188 
00189     // TODO: insert, remove, ...
00190 
00191     T &operator[](size_type idx) {
00192         assert(idx < _size);
00193         return _storage[idx];
00194     }
00195 
00196     const T &operator[](size_type idx) const {
00197         assert(idx < _size);
00198         return _storage[idx];
00199     }
00200 
00201     Array<T> &operator=(const Array<T> &array) {
00202         if (this == &array)
00203             return *this;
00204 
00205         freeStorage(_storage, _size);
00206         _size = array._size;
00207         allocCapacity(_size);
00208         uninitialized_copy(array._storage, array._storage + _size, _storage);
00209 
00210         return *this;
00211     }
00212 
00213     size_type size() const {
00214         return _size;
00215     }
00216 
00217     void clear() {
00218         freeStorage(_storage, _size);
00219         _storage = nullptr;
00220         _size = 0;
00221         _capacity = 0;
00222     }
00223 
00224     iterator erase(iterator pos) {
00225         copy(pos + 1, _storage + _size, pos);
00226         _size--;
00227         // We also need to destroy the last object properly here.
00228         _storage[_size].~T();
00229         return pos;
00230     }
00231 
00232     bool empty() const {
00233         return (_size == 0);
00234     }
00235 
00236     bool operator==(const Array<T> &other) const {
00237         if (this == &other)
00238             return true;
00239         if (_size != other._size)
00240             return false;
00241         for (size_type i = 0; i < _size; ++i) {
00242             if (_storage[i] != other._storage[i])
00243                 return false;
00244         }
00245         return true;
00246     }
00247 
00248     bool operator!=(const Array<T> &other) const {
00249         return !(*this == other);
00250     }
00251 
00252     iterator       begin() {
00253         return _storage;
00254     }
00255 
00256     iterator       end() {
00257         return _storage + _size;
00258     }
00259 
00260     const_iterator begin() const {
00261         return _storage;
00262     }
00263 
00264     const_iterator end() const {
00265         return _storage + _size;
00266     }
00267 
00268     void reserve(size_type newCapacity) {
00269         if (newCapacity <= _capacity)
00270             return;
00271 
00272         T *oldStorage = _storage;
00273         allocCapacity(newCapacity);
00274 
00275         if (oldStorage) {
00276             // Copy old data
00277             uninitialized_copy(oldStorage, oldStorage + _size, _storage);
00278             freeStorage(oldStorage, _size);
00279         }
00280     }
00281 
00282     void resize(size_type newSize) {
00283         reserve(newSize);
00284         for (size_type i = _size; i < newSize; ++i)
00285             new ((void *)&_storage[i]) T();
00286         _size = newSize;
00287     }
00288 
00289     void assign(const_iterator first, const_iterator last) {
00290         resize(distance(first, last)); // FIXME: ineffective?
00291         T *dst = _storage;
00292         while (first != last)
00293             *dst++ = *first++;
00294     }
00295 
00296 protected:
00297     static size_type roundUpCapacity(size_type capacity) {
00298         // Round up capacity to the next power of 2;
00299         // we use a minimal capacity of 8.
00300         size_type capa = 8;
00301         while (capa < capacity)
00302             capa <<= 1;
00303         return capa;
00304     }
00305 
00306     void allocCapacity(size_type capacity) {
00307         _capacity = capacity;
00308         if (capacity) {
00309             _storage = (T *)malloc(sizeof(T) * capacity);
00310             if (!_storage)
00311 				::error("Common::Array: failure to allocate %u bytes", capacity * (size_type)sizeof(T));
00312         } else {
00313             _storage = nullptr;
00314         }
00315     }
00316 
00317     void freeStorage(T *storage, const size_type elements) {
00318         for (size_type i = 0; i < elements; ++i)
00319             storage[i].~T();
00320         free(storage);
00321     }
00322 
00336     iterator insert_aux(iterator pos, const_iterator first, const_iterator last) {
00337         assert(_storage <= pos && pos <= _storage + _size);
00338         assert(first <= last);
00339         const size_type n = last - first;
00340         if (n) {
00341             const size_type idx = pos - _storage;
00342             if (_size + n > _capacity || (_storage <= first && first <= _storage + _size)) {
00343                 T *const oldStorage = _storage;
00344 
00345                 // If there is not enough space, allocate more.
00346                 // Likewise, if this is a self-insert, we allocate new
00347                 // storage to avoid conflicts.
00348                 allocCapacity(roundUpCapacity(_size + n));
00349 
00350                 // Copy the data from the old storage till the position where
00351                 // we insert new data
00352                 uninitialized_copy(oldStorage, oldStorage + idx, _storage);
00353                 // Copy the data we insert
00354                 uninitialized_copy(first, last, _storage + idx);
00355                 // Afterwards copy the old data from the position where we
00356                 // insert.
00357                 uninitialized_copy(oldStorage + idx, oldStorage + _size, _storage + idx + n);
00358 
00359                 freeStorage(oldStorage, _size);
00360             } else if (idx + n <= _size) {
00361                 // Make room for the new elements by shifting back
00362                 // existing ones.
00363                 // 1. Move a part of the data to the uninitialized area
00364                 uninitialized_copy(_storage + _size - n, _storage + _size, _storage + _size);
00365                 // 2. Move a part of the data to the initialized area
00366                 copy_backward(pos, _storage + _size - n, _storage + _size);
00367 
00368                 // Insert the new elements.
00369                 copy(first, last, pos);
00370             } else {
00371                 // Copy the old data from the position till the end to the new
00372                 // place.
00373                 uninitialized_copy(pos, _storage + _size, _storage + idx + n);
00374 
00375                 // Copy a part of the new data to the position inside the
00376                 // initialized space.
00377                 copy(first, first + (_size - idx), pos);
00378 
00379                 // Copy a part of the new data to the position inside the
00380                 // uninitialized space.
00381                 uninitialized_copy(first + (_size - idx), last, _storage + _size);
00382             }
00383 
00384             // Finally, update the internal state
00385             _size += n;
00386         }
00387         return pos;
00388     }
00389 
00390 };
00391 
00395 template<class T>
00396 class SortedArray : public Array<T> {
00397 public:
00398     typedef T *iterator;
00399     typedef uint size_type;
00400 
00401     SortedArray(int (*comparator)(const void *, const void *)) {
00402         _comparator = comparator;
00403     }
00404 
00408     void insert(const T &element) {
00409         if (!this->_size) {
00410             this->insert_aux(this->_storage, &element, &element + 1);
00411             return;
00412         }
00413 
00414         T *where = bsearchMin(element);
00415 
00416         if (where > this->_storage + this->_size)
00417             Array<T>::push_back(element);
00418         else
00419             Array<T>::insert(where, element);
00420     }
00421 
00422 private:
00423     T &operator[](size_type idx);
00424 
00425     void insert_at(size_type idx, const T &element);
00426 
00427     void insert_at(size_type idx, const Array<T> &array);
00428 
00429     void insert(iterator pos, const T &element);
00430 
00431     void push_back(const T &element);
00432 
00433     void push_back(const Array<T> &array);
00434 
00435     // Based on code Copyright (C) 2008-2009 Ksplice, Inc.
00436     // Author: Tim Abbott <tabbott@ksplice.com>
00437     // Licensed under GPLv2+
00438     T *bsearchMin(void *key) {
00439         uint start_ = 0, end_ = this->_size;
00440         int result;
00441 
00442         while (start_ < end_) {
00443             uint mid = start_ + (end_ - start_) / 2;
00444 
00445             result = this->_comparator(key, this->_storage[mid]);
00446             if (result < 0)
00447                 end_ = mid;
00448             else if (result > 0)
00449                 start_ = mid + 1;
00450             else
00451                 return &this->_storage[mid];
00452         }
00453 
00454         return &this->_storage[start_];
00455     }
00456 
00457     int (*_comparator)(const void *, const void *);
00458 };
00459 
00460 } // End of namespace Common
00461 
00462 #endif


Generated on Sat Jul 13 2019 05:00:58 for ResidualVM by doxygen 1.7.1
curved edge   curved edge