Raw Implementation of deque in cpp using 2 arrays

deque.cpp

#include<iostream>
#include<string>
#include<stdexcept>
#include<typeinfo>
using namespace std;

#define ull unsigned long long
#define ll long long
#define INITIAL_CAPACITY 2
#define CAPACITY_SCALING_FACTOR 2

ull _max(ull a, ull b){
    return (a>b)?a:b;
}


template <class Type>
class Deque {
    ull right_capacity = 0;
    ull left_capacity  = 0;
    ll right_start     = -1;
    ll right_end       = -1;
    ll left_start      = -1;
    ll left_end        = -1;

    Type default_val;
    Type* right = nullptr;
    Type* left = nullptr;

    Type get_default_value_of_type(){
        if(typeid(default_val).name()==typeid(1).name()
            || typeid(default_val).name()==typeid(1.0).name()
            || typeid(default_val).name()==typeid(1.0f).name()) return 0;
        else return {};
    }

    ull right_size() {
        if(right_end==-1)
            return 0;
        else
            return (right_end-right_start+1);
    }

    ull left_size() {
        if(left_end==-1)
            return 0;
        else
            return (left_end-left_start+1);
    }

    public:
    void display(){
        if(size()==0){
            cout << endl << "Deque Empty!" << endl;
            return;
        }


        if(left_end>=0){
            for(ll index=left_end;index>=left_start;index--){
                cout << left[index] << " ";
            }
        }


        if(right_end>=0){
            for(ll index=right_start;index<=right_end;index++){
                cout << right[index] << " ";
            }
        }


        cout << endl;
    }

    public:
        void deque(){
            if(right!=nullptr) delete[] right;
            right_capacity = INITIAL_CAPACITY;
            right = new Type[right_capacity];
            right_start = -1;
            right_end = -1;

            if(left!=nullptr) delete[] left;
            left_capacity = INITIAL_CAPACITY;
            left = new Type[left_capacity];
            left_start = -1;
            left_end = -1;
        }

        void deque(ull size, Type value){
            if(right!=nullptr) delete[] right;
            right_capacity = size;
            right = new Type[_max(INITIAL_CAPACITY, right_capacity)];
            right_end = -1;
            for(ll index=0; index<size; index++){
                right[index] = value;
                right_end++;
                right_start=0;
            }
            if(left!=nullptr) delete[] left;
            left_capacity = INITIAL_CAPACITY;
            left = new Type[left_capacity];
            left_start = -1;
            left_end = -1;
        }

        void push_back(Type value){
            //check if left has space in the beginning
            if(left_start>0){
                left[--left_start] = value;
            }
            else{
                //check if we have space available for another element
                if(right_capacity > right_size()){
                    if(right_start<=0){
                        right[++right_end] = value;
                        if(right_start==-1)
                            right_start = 0;
                    }
                    else{
                        for(ll index=0,right_index=right_start; right_index<=right_end; index++,right_index++)
                            right[index] = right[right_index];
                        right[++right_end] = value;
                        right_start = 0;
                    }
                }
                else{
                    ull new_right_capacity = _max((ull)INITIAL_CAPACITY,right_capacity*CAPACITY_SCALING_FACTOR);
                    Type* new_right = new Type[new_right_capacity];

                    //copy all elements in right to to new right
                    for(ll index=0; index<=right_end; index++)
                        new_right[index] = right[index];
                    new_right[++right_end] = value;
                    right_start=0;
                    if(right!=nullptr) delete[] right;
                    right = new_right;
                    right_capacity = new_right_capacity;
                }
            }
        }

        void pop_back(){
            if(right_size()>0){
                right_end--;
                if(right_end==-1)
                    right_start = -1;
            }
            else if(left_size()>0){
                left_start++;
                if(left_start>left_end){
                    left_end = -1;
                    left_start = -1;
                }
            }
            else{
                cout << "No element left to pop!" << endl;
            }
        }

        void push_front(Type value){
            //check if left has space in the beginning
            if(right_start>0){
                right[--right_start] = value;
            }
            else{
                //check if we have space available for another element
                if(left_capacity > left_size()){
                    if(left_start<=0){
                        left[++left_end] = value;
                        if(left_start==-1)
                            left_start = 0;
                    }
                    else{
                        for(ll index=0,left_index=left_start; left_index<=left_end; index++,left_index++)
                            left[index] = left[left_index];
                        left[++left_end] = value;
                        left_start = 0;
                    }
                }
                else{
                    ull new_left_capacity = _max((ull)INITIAL_CAPACITY,left_capacity*CAPACITY_SCALING_FACTOR);
                    Type* new_left = new Type[new_left_capacity];

                    //copy all elements in left to to new left
                    for(ll index=0; index<=left_end; index++)
                        new_left[index] = left[index];
                    new_left[++left_end] = value;
                    left_start=0;
                    if(left!=nullptr) delete[] left;
                    left = new_left;
                    left_capacity = new_left_capacity;
                }
            }
        }

        void pop_front(){
            if(left_size()>0){
                left_end--;
                if(left_end<left_start){
                    left_end = -1;
                    left_start = -1;
                }
            }
            else if(right_size()>0){
                right_start++;
                if(right_start>right_end){
                    right_start = -1;
                    right_end = -1;
                }
            }
            else{
                cout << "No element left to pop!" << endl;
                // throw runtime_error("No element left to pop");
                // exit(0);
            }
        }

        Type front(){
            if(left_end != -1)
                return left[left_end];
            else if (right_start != -1)
                return right[right_start];
            else{
                return get_default_value_of_type();
                // throw runtime_error("Deque Empty");
                // exit(0);
            }
        }

        Type back(){
            if(right_end != -1)
                return right[right_end];
            else if (left_start != -1)
                return left[left_start];
            else{
                return get_default_value_of_type();
                // throw runtime_error("Deque Empty");
                // exit(0);
            }
        }

        //overload [] operator
        Type operator [](ll index){
            if(index > size()-1){
                return get_default_value_of_type();
                // throw runtime_error("Index out of Bounds");
                // exit(0);
            }
            else if(left_size() >= index+1)
                return left[left_end-index];
            else if(right_size() >= index-left_size()+1)
                return right[right_start+(index-left_size())];
            else{
                cout << "aing idhar kese aagaya" << endl;
                return 0;
                // exit(0);
            }
        }

        ll size(){
            return right_size()+left_size();
        }

        bool empty(){
            if (size()==0)
                return true;
            else
                return false;
        }

        void resize(ull new_size, Type value){

            ull new_right_capacity = new_size;
            Type* new_right = new Type[_max(INITIAL_CAPACITY,new_right_capacity)];
            right_capacity = new_right_capacity;

            ll filled=0;

            //copy elements from left if they exist
            ll left_index=left_end;
            if(left_end>=0){
                for(ll index=0;
                    index<(new_size) && left_index>=left_start;
                    index++,left_index--)
                {
                        new_right[index]=left[left_index];
                        filled++;
                }
            }

            //copy elements from right if they exist
            ll right_index=right_start;
            if(right_end>=0){
                for(ull index=_max((ll)0,filled);
                    right_index<=right_end && filled<=new_size;
                    index++,right_index++)
                {
                        new_right[index]=right[right_index];
                        filled++;
                }
            }

            if(filled<new_size){
                for(ull index=_max((ll)0,filled); filled<=new_size;index++){
                    new_right[index]=value;
                    filled++;
                }
            }

            if(right!=nullptr) delete[] right;
            right = new_right;
            right_start = 0;
            right_end=new_size-1;
            left_start = -1;
            left_end = -1;

        }

        void clear(){
            right_start    = -1;
            right_end      = -1;
            left_start     = -1;
            left_end       = -1;
        }
};



int main(){
    ull n;

    // declaration
    Deque<string> d;
    string x;

    while(true){
        cout << endl << "--------- Options ---------" << endl;
        cout << "0. exit" << endl;
        cout << "1. deque()" << endl;
        cout << "2. deque(n, x)" << endl;
        cout << "3. push_back()" << endl;
        cout << "4. pop_back()" << endl;
        cout << "5. push_front()" << endl;
        cout << "6. pop_front()" << endl;
        cout << "7. front()" << endl;
        cout << "8. back()" << endl;
        cout << "9. d[n]" << endl;
        cout << "10. empty()" << endl;
        cout << "11. size()" << endl;
        cout << "12. resize(n,x)" << endl;
        cout << "13. clear()" << endl;
        cout << "14. display()" << endl;

        cout << endl << "Enter choice: ";
        unsigned choice;
        cin >> choice;


        switch (choice){
            case 0:
                return 0;
                break;
            case 1:
                d.deque();
                break;
            case 2:
                cout << "Enter n: ";
                cin >> n;
                cout << "Enter x: ";
                cin >> x;
                d.deque(n,x);
                break;
            case 3:
                cout << "Enter x: ";
                cin >> x;
                d.push_back(x);
                break;
            case 4:
                d.pop_back();
                break;
            case 5:
                cout << "Enter x: ";
                cin >> x;
                d.push_front(x);
                break;
            case 6:
                d.pop_front();
                break;
            case 7:
                cout << d.front() << endl;
                break;
            case 8:
                cout << d.back() << endl;
                break;
            case 9:
                cout << "Enter n: ";
                cin >> n;
                cout << d[n] << endl;
                break;
            case 10:
                cout << d.empty() << endl;
                break;
            case 11:
                cout << d.size() << endl;
                break;
            case 12:
                cout << "Enter n: ";
                cin >> n;
                cout << "Enter x: ";
                cin >> x;
                d.resize(n, x);
                break;
            case 13:
                d.clear();
                break;
            case 14:
                d.display();
                break;
            default:
                return 0;
                break;
        }
    }
}