deque.cpp

/**
 * @file deque.cpp
 * @author Sam Emison and Cole Belew
 * @date 2024-12-05
 * @brief Code for the functions in the Deque class
 * 
 * Has the code for the functions of the Deque class. Gives it functionality
 */


#include "deque.h"
#include <iostream>

//Constructor
Deque::Deque() {
    block_size = 10;
    block_count = 1;
    total_size = 0;
    front_index = 0;
    back_index = -1;
    block_start = 0;
    block_end = 0;
    blockmap = new int*[block_count];
    blockmap[0] = new int[block_size];
}

//Destructor
Deque::~Deque() {
    for (int i = block_start; i <= block_end; ++i) {
        delete[] blockmap[i];
    }
    delete[] blockmap;
}

//There if the blockmap needs to be resized
void Deque::resize_map() {
    int new_block_count = block_count * 2;
    int** new_blockmap = new int*[new_block_count];
    for (int i = 0; i < block_count; ++i) {
        new_blockmap[i] = blockmap[i];
    }

    for (int i = block_count; i < new_block_count; ++i) {
        new_blockmap[i] = nullptr;
    }

    delete[] blockmap;
    blockmap = new_blockmap;
    block_count = new_block_count;
}

//There if the block itself needs to be resized
void Deque::resize_block(int block_index) {
    int* new_block = new int[block_size * 2];
    for (int i = 0; i < block_size; ++i) {
        new_block[i] = blockmap[block_index][i];
    }
    delete[] blockmap[block_index];
    blockmap[block_index] = new_block;
    block_size *= 2;
}

//Pushes to the front
void Deque::push_front(int value) {
    if (front_index == 0) {
        if (block_start == 0) {
            resize_map();
        }
        --block_start;
        front_index = block_size - 1;
    }
    else {
        --front_index;
    }
    blockmap[block_start][front_index] = value;
    ++total_size;
}

//Pushes to the back
void Deque::push_back(int value) {
    if (back_index == block_size - 1) {
        if (block_end == block_count - 1) {
            resize_map();
        }
        ++block_end;
        back_index = 0;
        blockmap[block_end] = new int[block_size];
    }
    else {
        ++back_index;
    }
    blockmap[block_end][back_index] = value;
    ++total_size;
}

//Pops the front
void Deque::pop_front() {
    if (empty()) {
        std::cout << "Deque is empty, nothing to pop." << std::endl;
        return;
    }
    ++front_index;
    if (front_index == block_size) {
        front_index = 0;
        ++block_start;
    }
    --total_size;
}

//Pops the back
void Deque::pop_back() {
    if (empty()) {
        std::cout << "Deque is empty, nothing to pop." << std::endl;
        return;
    }
    if (back_index == 0) {
        back_index = block_size - 1;
        --block_end;
    }
    else {
        --back_index;
    }
    --total_size;
}

//Knows where the front is
int Deque::front() const {
    if (empty()) {
        std::cerr << "Deque is empty!" << std::endl;
        return -1; // Error value
    }
    return blockmap[block_start][front_index];
}

//Knows where the back is
int Deque::back() const {
    if (empty()) {
        std::cerr << "Deque is empty!" << std::endl;
        return -1; // Error value
    }
    return blockmap[block_end][back_index];
}

//Knows if its empty
bool Deque::empty() const {
    return total_size == 0;
}

//Knows the size
int Deque::size() const {
    return total_size;
}

//Checks the bounds
int Deque::operator[](int index) const {
    if (index < 0 || index >= total_size) {
        std::cerr << "Index out of bounds!" << std::endl;
        return -1; // Error value
    }
    int block_index = block_start;
    int offset = front_index + index;
    while (offset >= block_size) {
        ++block_index;
        offset -= block_size;
    }
    return blockmap[block_index][offset];
}