Skip to content

Instantly share code, notes, and snippets.

@jaffreyjoy

jaffreyjoy/deque.cpp

Created December 28, 2023 14:41
Show Gist options
  • Save jaffreyjoy/ee2c2f6c770a32fe93735546c8a0e7a2 to your computer and use it in GitHub Desktop.
Save jaffreyjoy/ee2c2f6c770a32fe93735546c8a0e7a2 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. jaffreyjoy created this gist Dec 28, 2023.
    426 changes: 426 additions & 0 deletions deque.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,426 @@
    #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;
    }
    }
    }