Makin' ma deq

deque.cpp

#pragma once

#include <initializer_list>
#include <algorithm>
#include <deque>
#include <memory>

struct Block {
    int& operator[](size_t index) {
        return data_[index + start_];
    }

    int operator[](size_t index) const {
        return data_[index + start_];
    }

    void PushBack(int new_element) {
        if (end_ < 128) {
            data_[(++end_) - 1] = new_element;
        }
    }

    void PopBack() {
        if (end_ > start_) {
            data_[--end_] = 0;
        }
    }

    void PushFront(int new_element) {
        if (start_ == 0 && end_ == 0) {
            start_ = 127;
            end_ = 128;
            data_[127] = new_element;
        }
        if (start_ > 0) {
            data_[--start_] = new_element;
        }
    }

    void PopFront() {
        if (start_ < end_) {
            data_[start_++] = 0;
        }
    }

    int data_[128]{};
    size_t start_{};
    size_t end_{};
};

class Deque {
public:
    Deque() : block_size_(0), size_(0), start_(0), end_(0), data_(nullptr) {
    }

    void Reset(size_t block_size) {
        data_ = std::make_unique<std::unique_ptr<Block>[]>(block_size);
        for (size_t i = 0; i < block_size; ++i) {
            data_[i] = std::make_unique<Block>();
        }
    }

    explicit Deque(size_t size)
        : block_size_((size + 127) / 128), size_(size), start_(0), end_(block_size_ - 1) {
        Reset(block_size_);
    }

    Deque(const Deque& rhs)
        : block_size_(rhs.block_size_), size_(rhs.size_), start_(rhs.start_), end_(rhs.end_) {
        data_ = std::make_unique<std::unique_ptr<Block>[]>(block_size_);
        for (size_t i = 0; i < rhs.block_size_; ++i) {
            data_[i] = std::make_unique<Block>(*rhs.data_[i]);
        }
    }

    void Swap(Deque& rhs) {
        std::swap(*this, rhs);
    }

    Deque(Deque&& rhs) = default;

    Deque(std::initializer_list<int> list) : Deque(list.size()) {
        size_t i = 0;
        for (size_t j = list.size(); j > 128; j -= 128) {
            std::copy(list.begin() + i * 128, list.begin() + (i + 1) * 128,
                      std::begin(data_[i]->data_));
            data_[i]->start_ = 0;
            data_[i]->end_ = 128;
            ++i;
        }
        std::copy(list.begin() + i * 128, list.end(), std::begin(data_[i]->data_));
        data_[i]->start_ = 0;
        data_[i]->end_ = list.end() - (list.begin() + i * 128);
    }

    Deque& operator=(Deque&& rhs) = default;

    Deque& operator=(const Deque& rhs) {
        if (data_ == rhs.data_) {
            return *this;
        }
        data_ = std::make_unique<std::unique_ptr<Block>[]>(rhs.block_size_);
        for (size_t i = 0; i < rhs.block_size_; ++i) {
            data_[i] = std::make_unique<Block>(*rhs.data_[i]);
        }
        block_size_ = rhs.block_size_;
        size_ = rhs.size_;
        start_ = rhs.start_;
        end_ = rhs.end_;
        return *this;
    }

    void PushBack(int value) {
        if (data_ == nullptr) {
            Reset(1);
            block_size_ = 1;
            size_ = 0;
            start_ = 0;
            end_ = 0;
        }
        if (data_[end_]->end_ == 128) {
            PushBlockBack();
        }
        data_[end_]->PushBack(value);
        ++size_;
    }

    void PopBack() {
        if (data_ != nullptr) {
            data_[end_]->PopBack();
            if (data_[end_]->end_ == 0) {
                if (end_ == start_) {
                    data_ = nullptr;
                } else {
                    --end_;
                }
            }
            if (size_ != 0) {
                --size_;
            }
        }
    }

    void PushFront(int value) {
        if (data_ == nullptr) {
            Reset(1);
            block_size_ = 1;
            size_ = 0;
            start_ = 0;
            end_ = 0;
        }
        if (data_[start_]->start_ == 0) {
            PushBlockFront();
        }
        data_[start_]->PushFront(value);
        ++size_;
    }

    void PopFront() {
        if (data_ != nullptr) {
            data_[start_]->PopFront();
            if (data_[start_]->start_ == 127) {
                if (start_ == end_) {
                    data_ = nullptr;
                } else {
                    ++start_;
                }
            }
            if (size_ != 0) {
                --size_;
            }
        }
    }

    int& operator[](size_t ind) {
        if (ind <= 127 - data_[start_]->start_) {
            return (*data_[start_])[ind];
        }
        ind -= 127 - data_[start_]->start_;
        int quot = ind / 128;
        int rem = ind % 128;
        return (*data_[start_ + quot + 1])[rem - 1];
    }

    int operator[](size_t ind) const {
        if (ind <= 127 - data_[start_]->start_) {
            return (*data_[start_])[ind];
        }
        ind -= 127 - data_[start_]->start_;
        int quot = ind / 128;
        int rem = ind % 128;
        return (*data_[start_ + quot + 1])[rem - 1];
    }

    size_t Size() const {
        return size_;
    }

    size_t max_size() const {
        return 128 * block_size_;
    }

    void Clear() {
        block_size_ = 0;
        size_ = 0;
        start_ = 0;
        end_ = 0;
        data_ = nullptr;
    }

private:
    void Reserve(size_t new_block_size) {
        if (new_block_size > block_size_) {
            auto new_data = std::make_unique<std::unique_ptr<Block>[]>(new_block_size);
            if (start_ <= end_) {
                std::move(data_.get() + start_, data_.get() + end_ + 1, new_data.get());
                end_ = end_ - start_;
            } else {
                std::move(data_.get() + start_, data_.get() + block_size_, new_data.get());
                std::move(data_.get(), data_.get() + end_ + 1,
                          new_data.get() + block_size_ - start_);
                end_ = (block_size_ - start_) + end_;
            }
            start_ = 0;
            data_ = std::move(new_data);
            block_size_ = new_block_size;
            for (size_t i = end_ + 1; i < block_size_; ++i) {
                data_[i] = std::make_unique<Block>();
            }
        }
    }

    void Realloc() {
        if (block_size_ != 0) {
            Reserve(block_size_ * 2);
        } else {
            Reserve(1);
        }
    }

    void PushBlockBack() {
        if ((end_ + 1) % block_size_ == start_) {
            Realloc();
        } else {
            end_ = (end_ + 1) % block_size_;
        }
    }

    void PushBlockFront() {
        if (start_ == 0) {
            if (end_ == block_size_ - 1) {
                Realloc();
            }
            start_ = block_size_ - 1;
        } else if (start_ - 1 == end_) {
            Realloc();
            start_ = block_size_ - 1;
        } else {
            --start_;
        }
    }

    size_t block_size_;
    size_t size_;
    size_t start_;
    size_t end_;
    std::unique_ptr<std::unique_ptr<Block>[]> data_;
};