VectorDeque.hpp

#include <cstddef>
#include <sstream>
#include <stdexcept>
#include <cstring>
#include <string>

template <class DataType>
class VectorDeque {
    private:
    // Allow testing class to access private methods and fields.
    friend class VectorDequeTest;

    // Base class for the mutable and immutable iterator implementations.
    template <class VectorDequeType, class MemberType, bool IS_REVERSE>
    class IteratorBase {
        typedef IteratorBase<VectorDeque, DataType, IS_REVERSE> Iterator;
        typedef IteratorBase<const VectorDeque, const DataType, IS_REVERSE> ConstIterator;
        friend VectorDeque;

        private:
        // Position in the VectorDeque this iterator is pointing to.
        size_t _position;

        // Pointer to VectorDeque this iterator is iterating on.
        VectorDequeType* const _vectorDequePtr;

        static MemberType& dereferenceAt(VectorDequeType* const vectorDequePtr, const ptrdiff_t position) throw() {
            if (IS_REVERSE) {
                return (*vectorDequePtr)[vectorDequePtr->size() - position - 1];
            }
            return (*vectorDequePtr)[position];
        }

        public:
        // Constructs an Iterator from a VectorDeque pointer and a position.
        IteratorBase(VectorDequeType* const vectorDequePtr, const size_t position) throw():
                _vectorDequePtr(vectorDequePtr), _position(position) {}

        // Constructs an Iterator from a VectorDeque pointer.
        IteratorBase(VectorDequeType* const vectorDequePtr) throw(): _vectorDequePtr(vectorDequePtr), _position(0) {}

        IteratorBase() throw(): _position(0), _vectorDequePtr(NULL) {}

        IteratorBase(const Iterator& that) throw(): _position(that._position), 
        _vectorDequePtr(that._vectorDequePtr) {}

        IteratorBase(const ConstIterator& that) throw(): _position(that._position), 
                _vectorDequePtr(that._vectorDequePtr) {}

        IteratorBase& operator =(const Iterator& that) throw() {
            _position = that._position;
            _vectorDequePtr = that._vectorDequePointer;
            return *this;
        }

        IteratorBase& operator =(const ConstIterator& that) throw() {
            _position = that._position;
            _vectorDequePtr = that._vectorDequePointer;
            return *this;
        }

        bool operator ==(const ConstIterator& that) const throw() {
            return _position == that._position && _vectorDequePtr == that._vectorDequePtr;
        }

        bool operator !=(const ConstIterator& that) const throw() {
            return !(*this == that);
        }

        bool operator <(const ConstIterator& that) const throw() {
            return _position < that._position;
        }

        bool operator >(const ConstIterator& that) const throw() {
            return _position > that._position;
        }

        bool operator <=(const ConstIterator& that) const throw() {
            return *this == that || *this < that;
        }

        bool operator >=(const ConstIterator& that) const throw() {
            return *this == that || *this > that;
        }

        IteratorBase& operator ++() throw() {
            ++_position;
            return *this;
        }

        IteratorBase operator ++(int) throw() {
            const IteratorBase copy(*this);
            ++_position;
            return copy;
        }

        IteratorBase& operator --() throw() {
            --_position;
            return *this;
        }

        IteratorBase operator --(int) throw() {
            const IteratorBase copy(*this);
            --_position;
            return copy;
        }

        IteratorBase& operator +=(const ptrdiff_t amount) throw() {
            _position += amount;
            return *this;
        }

        IteratorBase& operator -=(const ptrdiff_t amount) throw() {
            _position -= amount;
            return *this;
        }

        IteratorBase operator +(const ptrdiff_t amount) const throw() {
            return IteratorBase(*this) += amount;
        }
        
        friend IteratorBase operator +(const ptrdiff_t amount, const IteratorBase& it) throw() {
            return it + amount;            
        }

        IteratorBase operator -(const ptrdiff_t amount) const throw() {
            return IteratorBase(*this) -= amount;
        }

        ptrdiff_t operator -(const ConstIterator& that) const throw() {
            return static_cast<ptrdiff_t>(_position) - that._position;
        }
        
        MemberType& operator *() const {
            return dereferenceAt(_vectorDequePtr, static_cast<ptrdiff_t>(_position));
        }

        MemberType* operator ->() const throw() {
            return &(**this);
        }

        MemberType& operator [](const ptrdiff_t offset) const {
            return dereferenceAt(_vectorDequePtr, static_cast<ptrdiff_t>(_position) + offset);
        }
    };
    
    // Length of current backing array.
    size_t _capacity;

    // The stored data.
    DataType* _data;

    // Index in the backing array of the first element.
    size_t _position;

    // Total number of elements currently contained.
    size_t _size;

    // Add `length` elements from `elements` to the back.
    // Assumes length of internal array has already been verified.
    void _addAll(const DataType* const elements, const size_t start, const size_t length) throw() {
        // Number of elements before wrapping around to beginning.
        const size_t numBeforeWrap = std::min(_capacity - start, length);
        const size_t numAfterWrap = length - numBeforeWrap;
        std::memcpy(_data + start, elements, sizeof(DataType) * numBeforeWrap);
        std::memcpy(_data, elements + numBeforeWrap, sizeof(DataType) * numAfterWrap);
    }
    
    // Check to see if `index` is valid.
    // If not, throw `length_error`.
    void _checkIndex(const size_t index) const {
        if (index >= _size) {
            throw std::length_error(std::to_string(index));
        }
    }

    // Check to see if `it` iterates over `*this`.
    // If not, throw `invalid_argument`.
    template <class IteratorType>
    void _checkIterator(const IteratorType& it) const {
        if (this != it._vectorDequePtr) {
            throw std::invalid_argument("Iterator is not iterating over this VectorDeque");
        }
    }

    // Check to see if `[from, until)` is a valid range.
    // If not, throw `length_error`.
    void _checkRange(const size_t from, const size_t until) const {
        _checkSize(until);
        if (from > until) {
            throw std::invalid_argument("Bad range: start = " + std::to_string(from) + ", end = " + 
                    std::to_string(until));
        }
    }

    // Check to see if this has at least `required` elements.
    // If not, throw `length_error`.
    void _checkSize(const size_t required = 1) const {
        if (required > 0) {
            _checkIndex(required - 1);
        }
    }

    // Check to see if the current backing array has length at least `required`.
    // If not, resize.
    void _ensureCapacity(const size_t required) throw() {
        if (_capacity < required) {
            const size_t newCapacity = required * 2 + 1;
            DataType* const newData = new DataType[newCapacity];
            copyToArray(newData);
            _position = 0;
            delete[] _data;
            _data = newData;
            _capacity = newCapacity;
        }
    }

    // Check to see if `amount` more elements can fit in `*this`.
    // If not, resize.
    void _ensureCanFit(const size_t amount = 1) throw() {
        _ensureCapacity(_size + amount);
    }

    // Initialize the backing array and all fields.
    void _init(const size_t capacity) throw() {
        _capacity = capacity;
        _data = new DataType[capacity];
        _position = 0;
        _size = 0;
    }

    // Optimization: Insert `element` and resize at the same time when _size == _capacity pre-insertion.
    void _insertAndResize(const DataType& element, const size_t before) {
        const size_t newCapacity = 2 * _capacity + 1;
        DataType* const newData = new DataType[newCapacity];
        sliceToArray(newData, 0, before);
        newData[before] = element;
        if (before < _size) {
            // `before == _size` would result in an exception.
            sliceToArray(newData + before + 1, before, _size);
        }
        delete[] _data;
        _data = newData;
        _capacity = newCapacity;
        ++_size;
        _position = 0;
    }

    // Compute the internal index for the offset `offset`.
    size_t _internalIndex(const size_t offset) const throw() {
        if (_position + offset < _capacity) {
            return _position + offset;
        }
        // Target index is past the length of _data: wrap around to the beginning.
        // Note that if `_position + offset == _capacity`, the resulting index is 0.
        return _position + offset - _capacity;
    }

    // Determine the internal index offsetted by `offset` from `from` going backwards.
    size_t _internalNegativeIndexFrom(const size_t from, const size_t offset) const throw() {
        const size_t internal = _internalIndex(from);
        if (internal >= offset) {
            return internal - offset;
        }
        // Target index is before 0: wrap around to the end.
        // Note that if `from == offset - 1`, the resulting index is `_capacity - 1`.
        return _capacity - (offset - internal);
    }

    // Compute the number of elements remaining before we need to wrap to the beginning starting from `start`
    // when `length` elements need to be added.
    size_t _numBeforeWrap(const size_t start, const size_t length) const throw() {
        return std::min(_capacity - start, length);
    }

    // Shift the elements down from `from` until `until`.
    void _shiftDown(const size_t from, const size_t until) throw() {
        // Since elements are overwritten before they are copied, it is safe to use `memcpy`.
        const size_t length = until - from;
        // Start the `memcpy` 1 before the `from`.
        const size_t start = _internalNegativeIndexFrom(from, 1);
        const size_t numBeforeWrap = _numBeforeWrap(start, length);
        const size_t numAfterWrap = length - numBeforeWrap;
        std::memcpy(_data + start, _data + start + 1, sizeof(DataType) * numBeforeWrap);
        if (numAfterWrap != 0) {
            // First internal elements should be "shifted down" to the last position.
            _data[_capacity - 1] = _data[0];
            // Note numAfterWrap >= 1, so this is safe.
            std::memcpy(_data, _data + 1, sizeof(DataType) * (numAfterWrap - 1));
        }
        if (from == 0) {
            // Update the position if we are shifting down the first element.
            if (_position == 0) {
                _position = _capacity - 1;
            } else {
                --_position;
            }
        }
    }

    // Shift the elements up from `from` until `until`.
    void _shiftUp(const size_t from, const size_t until) {
        // Need to start from the end and go backwards, since otherwise elements will be overwritten before they are 
        // copied. Thus, we may not use `memcpy`.
        for (size_t i = 0; i < until - from; ++i) {
            _data[_internalNegativeIndexFrom(until, i)] = _data[_internalNegativeIndexFrom(until, i + 1)];
        }
        if (from == 0) {
            // If we're shifting up the first element, we need to update `_position`.
            if (_position == _capacity - 1) {
                _position = 0;
            } else {
                ++_position;
            }
        }
    }

    // Compute the internal index for where the next element should be written.
    size_t _writePosition() const throw() {
        // We write _size elements after the current position.
        return _internalIndex(_size);
    }      

    public:
    typedef IteratorBase<VectorDeque, DataType, false> Iterator;

    typedef IteratorBase<const VectorDeque, const DataType, false> ConstIterator;

    typedef IteratorBase<VectorDeque, DataType, true> ReverseIterator;

    typedef IteratorBase<const VectorDeque, const DataType, true> ConstReverseIterator;

    const static size_t DEFAULT_INITIAL_CAPACITY;

    VectorDeque() throw() {
        _init(DEFAULT_INITIAL_CAPACITY);
    }

    explicit VectorDeque(const size_t capacity) throw() {
        _init(capacity);
    }

    VectorDeque(const VectorDeque& that) throw() {
        // Initialize backing array to be large enough to contain the contents of that.
        _init(that._size);
        that.copyToArray(_data);
        // Note that._position is still 0, and we are at capacity.
        _size = that._size;
    }

    VectorDeque(VectorDeque&& that) throw() {
        // Move contents of that with memcpy.
        std::memcpy(this, &that, sizeof(VectorDeque));
        // Allow safe destruction of that.
        that._data = NULL;
    }

    VectorDeque& operator =(const VectorDeque& that) throw() {
        if (this == &that) {
            return *this;
        }
        if (_capacity < that._size) {
            delete[] _data;
            _data = new DataType[that._size];
            _capacity = that._size;
        }
        that.copyToArray(_data);
        _position = 0;
        _size = that._size;
        return *this;
    }

    VectorDeque& operator =(VectorDeque&& that) throw() {
        delete[] _data;
        // Move with memcpy.
        std::memcpy(this, &that, sizeof(VectorDeque));
        // Allow safe destruction of that.
        that._data = NULL;
    }

    bool operator ==(const VectorDeque& that) const throw() {
        if (this == &that) {
            return true;
        }
        if (_size != that.size()) {
            return false;
        }
        for (size_t i = 0; i < _size; ++i) {
            if ((*this)[i] != that[i]) {
                return false;
            }
        }
        return true;
    }

    bool operator !=(const VectorDeque& that) const throw() {
        return !(*this == that);
    }

    DataType& operator [](const size_t index) const {
        _checkIndex(index);
        return _data[_internalIndex(index)];
    }

    operator std::string() const throw() {
        if (isEmpty()) {
            return "{}";
        }
        std::stringstream stream;
        stream << '{';
        stream << (*this)[0];
        for (size_t i = 1; i < _size; ++i) {
            stream << ", " << (*this)[i];
        }
        stream << '}';
        return stream.str();
    }

    void add(const DataType& element) throw() {
        _ensureCanFit();
        _data[_writePosition()] = element;
        ++_size;
    }

    void addAll(const DataType* const elements, const size_t length) throw() {
        _ensureCanFit(length);
        _addAll(elements, _writePosition(), length);
        _size += length;
    }

    template <class IteratorType>
    void addAll(IteratorType begin, IteratorType end) throw() {
        for (IteratorType it = begin; it != end; ++it) {
            add(*it);
        }
    }

    void addAllFirst(const DataType* const elements, const size_t length) throw() {
        // Can't take advantage of memcpy: use iterator version.
        addAllFirst(elements, elements + length);
    }

    template <class IteratorType>
    void addAllFirst(IteratorType begin, IteratorType end) throw() {
        for (IteratorType it = begin; it != end; ++it) {
            addFirst(*it);
        }
    }

    void addFirst(const DataType& element) throw() {
        _ensureCanFit();
        if (_position == 0) {
            _position = _capacity - 1;
        } else {
            --_position;
        }
        // The position is now at the element which was added to the front.
        _data[_position] = element;
        ++_size;
    }

    Iterator begin() throw() {
        return Iterator(this);
    }

    ConstIterator cbegin() const throw() {
        return ConstIterator(this);
    }

    ConstIterator cend() const throw() {
        return ConstIterator(this, _size);
    }

    void clear() throw() {
        _size = 0;
    }

    bool contains(const DataType& element) const throw() {
        return find(element) != -1;
    }

    void copyToArray(DataType* const target) const throw() {
        sliceToArray(target, 0, _size);
    }

    ConstReverseIterator crbegin() const throw() {
        return ConstReverseIterator(this);
    }

    ConstReverseIterator crend() const throw() {
        return ConstReverseIterator(this, _size);
    } 

    Iterator end() throw() {
        return Iterator(this, _size);
    }
    
    ssize_t find(const DataType& element) const throw() {
        for (size_t i = 0; i < _size; ++i) {
            if (element == (*this)[i]) {
                return i;
            }
        }
        return -1;
    }

     DataType& fromBack(const size_t index) const {
        return (*this)[_size - index - 1];
    } 

    void insert(const DataType& element, const size_t before) {
        if (before == 0) {
            // Handle the logic for 0 specially since it changes the position.
            addFirst(element);
            return;
        }
        if (before != _size) {
            // `before == _size` is okay because it translates to inserting `element` at the end.
            _checkIndex(before);
        } else {
            add(element);
            return;
        }
        if (_size == _capacity) {
            // Handle insertion and resizing simultaneously for efficiency.
            _insertAndResize(element, before);
            return;
        }
    
        if (before <= _size / 2) {
            // More efficient to shift front elements backwards.
            _shiftDown(0, before);

        } else {
            // More efficient to shift back elements forwards.
            _shiftUp(before, _size);
        }
        ++_size;
        const size_t insertionIndex = _internalIndex(before);
        _data[insertionIndex] = element;
    }

    void insert(const DataType& element, const ConstIterator& it) {
        _checkIterator(it);
        insert(element, it._position);
    }

    void insert(const DataType& element, const ConstReverseIterator& it) {
        _checkIterator(it);
        insert(element, _size - it._position);
    }

    bool isEmpty() const throw() {
        return _size == 0;
    }

    DataType peek() const {
        _checkSize();
        return (*this)[0];
    }

    DataType peekLast() const {
        _checkSize();
        return (*this)[_size - 1];
    }

    DataType pop() {
        _checkSize();
        const DataType popped = peek();
        skip();
        return popped;
    }

    void popAll(DataType* const target) throw() {
        copyToArray(target);
        clear();
    }

    void popAllLast(DataType* const target) throw() {
        reverseCopyToArray(target);
        clear();
    }

    DataType popLast() {
        _checkSize();
        const DataType popped = peekLast();
        skipLast();
        return popped;
    }

    void popSome(DataType* const target, const size_t amount) {
        sliceToArray(target, 0, amount);
        skip(amount);
    }

    void popSomeLast(DataType* const target, const size_t amount) {
        reverseSliceToArray(target, 0, amount);
        skipLast(amount);
    }

    ReverseIterator rbegin() throw() {
        return ReverseIterator(this);
    }

    DataType removeAt(const size_t index) {
        _checkIndex(index);
        const DataType result = (*this)[index];
        if (index == _size - 1) {
            --_size;
        }
        else if (index / 2 <= _size) {
            // More efficient to shift front elements forward.
            _shiftUp(0, index);
            --_size;

        } else {
            // More efficient to shift back elements backward.
            _shiftDown(index + 1, _size);
            --_size;
        }
        return result;
    }
    
    DataType removeAt(const ConstIterator& it) {
        _checkIterator(it);
        return removeAt(it._position);
    }

    DataType removeAt(const ConstReverseIterator& it) {
        _checkIterator(it);
        removeAt(_size - it._position);
    }

    Iterator rend() throw() {
        return ReverseIterator(this, _size);
    } 

    void reverseCopyToArray(DataType* const target) const throw() {
        reverseSliceToArray(target, 0, _size);
    }

    void reverseSliceToArray(DataType* const target, const size_t from, const size_t until) const {
        _checkRange(from, until);
        const size_t length = until - from;
        for (size_t i = 0; i < length; ++i) {
            target[i] = fromBack(i + from);
        }
    }

    size_t size() const throw() {
        return _size;
    }

    void skip(const size_t amount = 1) {
        _checkSize(amount);
        _position = _internalIndex(amount);
        _size -= amount;
    }

    void skipLast(const size_t amount = 1) {
        _checkSize(amount);
        // _position is already fine, since we are not removing from the front.
        _size -= amount;
    }

    void sliceToArray(DataType* const target, const size_t from, const size_t until) const {
        _checkRange(from, until);
        const size_t length = until - from;
        const size_t start = _internalIndex(from);
        const size_t numBeforeWrap = _numBeforeWrap(start, length);
        const size_t numAfterWrap = length - numBeforeWrap;
        memcpy(target, _data + start, sizeof(DataType) * numBeforeWrap);
        memcpy(target + numBeforeWrap, _data, sizeof(DataType) *  numAfterWrap);
    }
};

template <class DataType>
const size_t VectorDeque<DataType>::DEFAULT_INITIAL_CAPACITY = 11;

// Leftover friend function.

template <class DataType, class VectorDequeType, class MemberType, bool IS_REVERSE>
typename VectorDeque<DataType>::template IteratorBase<VectorDequeType, MemberType, IS_REVERSE> operator +
    (const ptrdiff_t amount, const typename VectorDeque<DataType>::template 
    IteratorBase<VectorDequeType, MemberType, IS_REVERSE>& it) throw();