deque.hpp

#ifndef DEQUE_HPP
#define DEQUE_HPP
#include "vector.hpp"
#include <iostream>

template <typename data_t>
class deque{

private:
    vector<vector<data_t>> table;
    int control_start;
    int control_end;
    int table_start;
    int table_end;
    int cap;

    void resize_deque(){
        vector<vector<data_t>> new_table;
        int offset = table.size()/2;
        for(int i=0;i<table.size()*2;i++){
            vector<data_t> t(128);
            new_table.push_back(t);
        }

        for(int i=0;i<table.size();i++){
            new_table[i+offset] = std::move(table[i]);
        }

        table_start += offset;
        table_end += offset;
        table = std::move(new_table);
    }
    

public:
    deque() {
        table_start = 3;
        table_end = 3;
        cap = 128;
        control_start = -1;
        control_end = -1;

        for(int i=0;i<6;i++){
            vector<data_t> u(cap);
            table.push_back(u);
        }
    }

    deque(const deque& other_deque){
        table_start = other_deque.table_start;
        table_end = other_deque.table_end;
        table = other_deque.table;
        control_start = other_deque.control_start;
        control_end = other_deque.control_end;
    }

    deque(deque&& other_deque) noexcept {
        table_start = other_deque.table_start;
        table_end = other_deque.table_end;
        table = std::move(other_deque.table);
        control_start = std::move(other_deque.control_start);
        control_end = std::move(other_deque.control_end);
    }

    deque& operator=(const deque& other_deque){
        if(this != &other_deque){
            table_start = other_deque.table_start;
            table_end = other_deque.table_end;
            table = other_deque.table;
            control_start = other_deque.control_start;
            control_end = other_deque.control_end;
        }

        return this;
    }

    deque& operator=(deque&& other_deque) noexcept {
        if(this != &other_deque){
            table_start = other_deque.table_start;
            table_end = other_deque.table_end;
            table = std::move(other_deque.table);
            control_start = std::move(other_deque.control_start);
            control_end = std::move(other_deque.control_end);
        }
    }

    ~deque() {}

    void push_front(data_t& data){
        // empty table, first insertion
        if(control_start==-1){
            control_start = 0;
            control_end = 0;

            table[table_start][control_start] = data;
        }
        // table starting slot starts at 0
        else if(control_start==0){
            table_start--;
            control_start = cap-1;
            
            table[table_start][control_start] = data;
        }
        // table starting slot is >=0
        else {
            control_start--;
            
            table[table_start][control_start] = data;
        }

        if(table_start==0){
            resize_deque();
        }
    }

    void push_back(data_t& data){
        // empty table slot. first insertion in table_end slot
        if(control_end==-1){
            control_end = 0;
            control_start = 0;

            table[table_end][control_end] = data;
        }
        // end table slot is full.
        else if(control_end==cap-1){
            table_end++;
            control_end = 0;

            table[table_end][control_end] = data;
        }
        // table end slot is < cap
        else{
            control_end++;

            table[table_end][control_end] = data;
        }

        if(table_end==table.size()-1){
            resize_deque();
        }
    }

    data_t& front(){
        if(control_start==-1){
            throw std::runtime_error("Tried to access member 'front' of an empty deque : deque.hpp\n");
        }

        return table[table_start][control_start];
    }

    data_t& back(){
        if(control_end==-1){
            throw std::runtime_error("Tried to access member 'back' of and empty deque : deque.hpp\n");
        }

        return table[table_end][control_end];
    }

    void pop_front(){
        if(control_start==-1){
            throw std::runtime_error("Tried to access member 'pop_front' of an empty deque : deque.hpp\n");
        }
        
        table[table_start][control_start].~data_t();
        
        control_start++;
        if(control_start==cap){
            control_start = 0;
            table_start++;

            vector<data_t> replace(128);
            table[table_start-1] = std::move(replace);
        }

        if(table_start>table_end || (table_start==table_end && control_start>control_end)){
            control_end = -1;
            control_start = -1;
            table_start = table.size()/2;
            table_end = table.size()/2;
        }
    }
    
    void pop_back(){
        if(control_end==-1){
            throw std::runtime_error("Tried to access member 'pop_back' of an empty deque : deque.hpp\n");
        }

        table[table_end][control_end].~data_t();

        control_end--;
        if(control_end==-1){
            table_end--;
            control_end = cap-1;

            vector<data_t> replace(128);
            table[table_end+1] = std::move(replace);
        }

        if(table_start>table_end || (table_start==table_end && control_end<control_start)){
            control_start = -1;
            control_end = -1;
            table_start = table.size()/2;
            table_end = table.size()/2;
        }
    }

    bool empty(){
        return control_start == -1;
    }

    int size(){
        int slots_span = table_end - table_start + 1;
        int size_ = slots_span * cap;
        size_ -= control_start;
        size_ -= cap - 1 - control_end;

        return size_;
    }

    void clear(){
        vector<vector<data_t>> new_table;
        for(int i=0;i<6;i++){
            vector<data_t> t;
            new_table.push_back(t);
        }
        table = std::move(new_table);

        table_start = 3;
        table_end = 3;
        control_start = -1;
        control_end = -1;
    }
};


#endif