array.h

/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#ifndef COMMON_ARRAY_H
#define COMMON_ARRAY_H

#include "common/scummsys.h"
#include "common/algorithm.h"
#include "common/textconsole.h" // For error()
#include "common/memory.h"

namespace Common {

template<class T>
class Array {
public:
    typedef T *iterator; 
    typedef const T *const_iterator; 
    typedef T value_type; 
    typedef uint size_type; 
protected:
    size_type _capacity; 
    size_type _size; 
    T *_storage;  
public:
    constexpr Array() : _capacity(0), _size(0), _storage(nullptr) {}

    explicit Array(size_type count) : _size(count) {
        allocCapacity(count);

        T *storage = _storage;

        for (size_type i = 0; i < count; ++i)
            new ((void *)&storage[i]) T();
    }

    Array(size_type count, const T &value) : _size(count) {
        allocCapacity(count);
        uninitialized_fill_n(_storage, count, value);
    }

    Array(const Array<T> &array) : _capacity(array._size), _size(array._size), _storage(nullptr) {
        if (array._storage) {
            allocCapacity(_size);
            uninitialized_copy(array._storage, array._storage + _size, _storage);
        }
    }

    Array(Array<T> &&old) : _capacity(old._capacity), _size(old._size), _storage(old._storage) {
        old._storage = nullptr;
        old._capacity = 0;
        old._size = 0;
    }

    Array(std::initializer_list<T> list) : _size(list.size()) {
        allocCapacity(list.size());
        if (_storage)
            Common::uninitialized_copy(list.begin(), list.end(), _storage);
    }

    template<class T2>
    Array(const T2 *array, size_type n) {
        _size = n;
        allocCapacity(n);
        uninitialized_copy(array, array + _size, _storage);
    }

    ~Array() {
        freeStorage(_storage, _size);
        _storage = nullptr;
        _capacity = _size = 0;
    }

    template<class... TArgs>
    void emplace(const_iterator pos, TArgs&&... args) {
        assert(pos >= _storage && pos <= _storage + _size);

        const size_type index = static_cast<size_type>(pos - _storage);

        if (_size != _capacity && index == _size) {
            // Added at the end in the existing storage
            new (_storage + index) T(Common::forward<TArgs>(args)...);
        } else {
            // Either added in the middle, or ran out of space
            // In the added-in-the-middle case, the copy is required because the parameters
            // may contain a const ref to the original storage.
            T *oldStorage = _storage;

            allocCapacity(roundUpCapacity(_size + 1));

            // Construct the new element first, since it may copy-construct from
            // the original array
            new (_storage + index) T(Common::forward<TArgs>(args)...);

            // Move the original data
            uninitialized_move(oldStorage, oldStorage + index, _storage);
            uninitialized_move(oldStorage + index, oldStorage + _size, _storage + index + 1);

            freeStorage(oldStorage, _size);
        }

        _size++;
    }

    template<class... TArgs>
    void emplace_back(TArgs &&...args) {
        emplace(begin() + _size, Common::forward<TArgs>(args)...);
    }

    void push_back(const T &element) {
        emplace_back(element);
    }

    void push_back(T &&element) {
        emplace_back(Common::move(element));
    }

    void push_back(const Array<T> &array) {
        if (_size + array.size() <= _capacity) {
            uninitialized_copy(array.begin(), array.end(), end());
            _size += array.size();
        } else
            insert_aux(end(), array.begin(), array.end());
    }

    void pop_back() {
        assert(_size > 0);
        _size--;
        // We also need to destroy the last object properly here.
        _storage[_size].~T();
    }

    const T *data() const {
        return _storage;
    }

    T *data() {
        return _storage;
    }

    T &front() {
        assert(_size > 0);
        return _storage[0];
    }

    const T &front() const {
        assert(_size > 0);
        return _storage[0];
    }

    T &back() {
        assert(_size > 0);
        return _storage[_size-1];
    }

    const T &back() const {
        assert(_size > 0);
        return _storage[_size-1];
    }

    void insert_at(size_type idx, const T &element) {
        assert(idx <= _size);
        insert_aux(_storage + idx, &element, &element + 1);
    }

    void insert_at(size_type idx, const Array<T> &array) {
        assert(idx <= _size);
        insert_aux(_storage + idx, array.begin(), array.end());
    }

    void insert(iterator pos, const T &element) {
        insert_aux(pos, &element, &element + 1);
    }

    T remove_at(size_type idx) {
        assert(idx < _size);
        T tmp = Common::move(_storage[idx]);
        move(_storage + idx + 1, _storage + _size, _storage + idx);
        _size--;
        // We also need to destroy the last object properly here.
        _storage[_size].~T();
        return tmp;
    }

    // TODO: insert, remove, ...

    T &operator[](size_type idx) {
        assert(idx < _size);
        return _storage[idx];
    }

    const T &operator[](size_type idx) const {
        assert(idx < _size);
        return _storage[idx];
    }

    Array<T> &operator=(const Array<T> &array) {
        if (this == &array)
            return *this;

        freeStorage(_storage, _size);
        _size = array._size;
        allocCapacity(_size);
        uninitialized_copy(array._storage, array._storage + _size, _storage);

        return *this;
    }

    Array &operator=(Array<T> &&old) {
        if (this == &old)
            return *this;

        freeStorage(_storage, _size);
        _capacity = old._capacity;
        _size = old._size;
        _storage = old._storage;

        old._storage = nullptr;
        old._capacity = 0;
        old._size = 0;

        return *this;
    }

    size_type size() const {
        return _size;
    }

    void clear() {
        freeStorage(_storage, _size);
        _storage = nullptr;
        _size = 0;
        _capacity = 0;
    }

    iterator erase(iterator pos) {
        move(pos + 1, _storage + _size, pos);
        _size--;
        // We also need to destroy the last object properly here.
        _storage[_size].~T();
        return pos;
    }

    iterator erase(iterator first, iterator last) {
        move(last, _storage + _size, first);

        int count = (last - first);
        _size -= count;

        // We also need to destroy the objects beyond the new size
        for (uint idx = _size; idx < (_size + count); ++idx)
            _storage[idx].~T();

        return first;
    }

    bool empty() const {
        return (_size == 0);
    }

    bool operator==(const Array<T> &other) const {
        if (this == &other)
            return true;
        if (_size != other._size)
            return false;
        for (size_type i = 0; i < _size; ++i) {
            if (_storage[i] != other._storage[i])
                return false;
        }
        return true;
    }

    bool operator!=(const Array<T> &other) const {
        return !(*this == other);
    }

    iterator       begin() {
        return _storage;
    }

    iterator       end() {
        return _storage + _size;
    }

    const_iterator begin() const {
        return _storage;
    }

    const_iterator end() const {
        return _storage + _size;
    }

    void reserve(size_type newCapacity) {
        if (newCapacity <= _capacity)
            return;

        T *oldStorage = _storage;
        allocCapacity(newCapacity);

        if (oldStorage) {
            // Move old data
            uninitialized_move(oldStorage, oldStorage + _size, _storage);
            freeStorage(oldStorage, _size);
        }
    }

    void resize(size_type newSize) {
        reserve(newSize);

        T *storage = _storage;

        for (size_type i = newSize; i < _size; ++i)
            storage[i].~T();
        for (size_type i = _size; i < newSize; ++i)
            new ((void *)&storage[i]) T();

        _size = newSize;
    }

    void resize(size_type newSize, const T value) {
        reserve(newSize);

        T *storage = _storage;

        for (size_type i = newSize; i < _size; ++i)
            storage[i].~T();
        if (newSize > _size)
            uninitialized_fill_n(storage + _size, newSize - _size, value);

        _size = newSize;
    }

    void assign(const_iterator first, const_iterator last) {
        resize(distance(first, last)); // FIXME: ineffective?
        T *dst = _storage;
        while (first != last)
            *dst++ = *first++;
    }

    void swap(Array &arr) {
        SWAP(this->_capacity, arr._capacity);
        SWAP(this->_size, arr._size);
        SWAP(this->_storage, arr._storage);
    }

protected:
    static size_type roundUpCapacity(size_type capacity) {
        size_type capa = 8;
        while (capa < capacity)
            capa <<= 1;
        return capa;
    }

    void allocCapacity(size_type capacity) {
        _capacity = capacity;
        if (capacity) {
            _storage = (T *)malloc(sizeof(T) * capacity);
            if (!_storage)
                ::error("Common::Array: failure to allocate %u bytes", capacity * (size_type)sizeof(T));
        } else {
            _storage = nullptr;
        }
    }

    void freeStorage(T *storage, const size_type elements) {
        for (size_type i = 0; i < elements; ++i)
            storage[i].~T();
        free(storage);
    }

    iterator insert_aux(iterator pos, const_iterator first, const_iterator last) {
        assert(_storage <= pos && pos <= _storage + _size);
        assert(first <= last);
        const size_type n = last - first;
        if (n) {
            const size_type idx = pos - _storage;
            if (_size + n > _capacity || (_storage <= first && first <= _storage + _size)) {
                T *const oldStorage = _storage;

                // If there is not enough space, allocate more.
                // Likewise, if this is a self-insert, we allocate new
                // storage to avoid conflicts.
                allocCapacity(roundUpCapacity(_size + n));

                // Move the data from the old storage till the position where
                // we insert new data
                uninitialized_move(oldStorage, oldStorage + idx, _storage);
                // Copy the data we insert
                uninitialized_copy(first, last, _storage + idx);
                // Afterwards, move the old data from the position where we
                // insert.
                uninitialized_move(oldStorage + idx, oldStorage + _size, _storage + idx + n);

                freeStorage(oldStorage, _size);
            } else if (idx + n <= _size) {
                // Make room for the new elements by shifting back
                // existing ones.
                // 1. Move a part of the data to the uninitialized area
                uninitialized_move(_storage + _size - n, _storage + _size, _storage + _size);
                // 2. Move a part of the data to the initialized area
                move_backward(pos, _storage + _size - n, _storage + _size);

                // Insert the new elements.
                copy(first, last, pos);
            } else {
                // Move the old data from the position till the end to the new
                // place.
                uninitialized_move(pos, _storage + _size, _storage + idx + n);

                // Copy a part of the new data to the position inside the
                // initialized space.
                copy(first, first + (_size - idx), pos);

                // Copy a part of the new data to the position inside the
                // uninitialized space.
                uninitialized_copy(first + (_size - idx), last, _storage + _size);
            }

            // Finally, update the internal state
            _size += n;
        }
        return pos;
    }

};

template<class T, typename CompareArgType = const void *>
class SortedArray : public Array<T> {
public:
    typedef int (*Comparator)(CompareArgType, CompareArgType);
    typedef T *iterator;
    typedef uint size_type;

    SortedArray(Comparator comparator) {
        _comparator = comparator;
    }

    void insert(const T &element) {
        if (!this->_size) {
            this->insert_aux(this->_storage, &element, &element + 1);
            return;
        }

        T *where = bsearchMin(element);

        if (where > this->_storage + this->_size)
            Array<T>::push_back(element);
        else
            Array<T>::insert(where, element);
    }

private:
    T &operator[](size_type idx);

    void insert_at(size_type idx, const T &element);

    void insert_at(size_type idx, const Array<T> &array);

    void insert(iterator pos, const T &element);

    void push_back(const T &element);

    void push_back(const Array<T> &array);

    // Based on code Copyright (C) 2008-2009 Ksplice, Inc.
    // Author: Tim Abbott <tabbott@ksplice.com>
    // Licensed under GPLv2+
    T *bsearchMin(CompareArgType key) {
        uint start_ = 0, end_ = this->_size;
        int result;

        while (start_ < end_) {
            uint mid = start_ + (end_ - start_) / 2;

            result = this->_comparator(key, this->_storage[mid]);
            if (result < 0)
                end_ = mid;
            else
                start_ = mid + 1;
        }

        return &this->_storage[start_];
    }

    Comparator _comparator;
};

} // End of namespace Common

#endif