Untitled
unknown
plain_text
a year ago
19 kB
2
Indexable
#pragma once
#include "cstring"
#include "sstream"
#include "string"
#include <iostream>
namespace cs251
{
template<typename T>
class cyclic_double_queue
{
public:
/**
* \brief The constructor with settings.
* \param initialCapacity Preset initial capacity of the array.
* \param increaseFactor Preset increase factor for expanding the array.
* \param decreaseFactor Preset decrease factor for shrinking the array.
*/
cyclic_double_queue(size_t initialCapacity = 7, size_t increaseFactor = 2, size_t decreaseFactor = 2);
/**
* \brief The default destructor. You should make sure no memory leaks happens after the queue is destroyed.
*/
~cyclic_double_queue();
/**
* \brief Push the item at the front of the queue.
* \param item The item to be added.
*/
void enqueue_front(const T& item);
/**
* \brief Push the item at the back of the queue.
* \param item The item to be added.
*/
void enqueue_back(const T& item);
/**
* \brief Returns the occupancy of the queue.
* \return Whether the queue is empty.
*/
bool empty() const;
/**
* \brief Dequeue the element at the front of the queue.
* \return The item dequeued.
*/
T dequeue_front();
/**
* \brief Dequeue the element at the back of the queue.
* \return The item dequeued.
*/
T dequeue_back();
/**
* \brief Remove the item at the front of the queue, returns nothing.
*/
void pop_front();
/**
* \brief Remove the item at the back of the queue, returns nothing.
*/
void pop_back();
/**
* \brief Provide the access to the item at the front of the queue.
* \return The modifiable reference to the item.
*/
T& front();
/**
* \brief Provide the access to the item at the back of the queue.
* \return The modifiable reference to the item.
*/
T& back();
/**
* \brief Empty the queue, and resize the queue to initial capacity.
* \n !Note! You should set the size and the front index of the queue to 0 when this function is called!
*/
void clear();
/**
* \brief Print the queue's current status according to the handout.
* \return The string represents the array. For format please refer to the handout.
*/
std::string print_status() const;
/**
* \brief Returns the number of items currently in queue.
* \return The size of the queue.
*/
size_t get_size() const;
/**
* \brief Returns the total capacity of the array.
* \return The capacity of the array.
*/
size_t get_capacity() const;
private:
//TODO: You may add private members/methods here.
/**
* Item array, the underlying data structure for the queue
*/
T* m_data = nullptr;
/**
* The front index of the queue within the array
*/
size_t m_frontIndex = 0;
/**
* The length of the array, including the empty slots.
*/
size_t m_capacity = 0;
/**
* Keeps track of the size of the queue
*/
size_t m_size = 0;
/**
* Factor by which the queue length must be increased
*/
size_t m_increaseFactor = 0;
/**
* Factor by which the queue length must be decreased
*/
size_t m_decreaseFactor = 0;
/**
* The initial capacity of the queue, predefined as 7
*/
size_t m_initialCapacity = 0;
size_t m_backIndex = 0;
/* front index of the queue in the array */
T* resize(size_t new_size);
};
template <typename T>
cyclic_double_queue<T>::cyclic_double_queue(const size_t initialCapacity, const size_t increaseFactor, size_t decreaseFactor)
{
//TODO: Remove following line and add your implementation here.
m_initialCapacity = initialCapacity;
m_increaseFactor = increaseFactor;
m_decreaseFactor = decreaseFactor;
m_capacity = initialCapacity;
m_data = new T[m_capacity]();
}
template <typename T>
cyclic_double_queue<T>::~cyclic_double_queue()
{
//TODO: Add your implementation here.
delete[] m_data;
}
template <typename T>
T* cyclic_double_queue<T>::resize(size_t new_size)
{
/*copying old array into new array */
T* newArray = new T[new_size]();
m_backIndex = 0;
for (int i=0; i < m_size; i++) {
newArray[i] = m_data[m_frontIndex];
m_frontIndex++;
m_backIndex++;
if (m_frontIndex >= m_capacity) {
m_frontIndex = 0;
}
}
m_frontIndex = 0;
return newArray;
}
template <typename T>
void cyclic_double_queue<T>::enqueue_front(const T& item)
{
//TODO: Remove following line and add your implementation here.
if (m_size == m_capacity) {
m_data = resize(m_capacity * m_increaseFactor);
m_capacity = m_capacity * m_increaseFactor;
}
if (m_frontIndex == 0) {
m_frontIndex = m_capacity - 1;
} else {
m_frontIndex--;
}
m_data[m_frontIndex] = item;
m_size++;
}
template <typename T>
void cyclic_double_queue<T>::enqueue_back(const T& item)
{
//TODO: Remove following line and add your implementation here.
if (m_size == m_capacity) {
m_data = resize(m_capacity * m_increaseFactor);
m_capacity = m_capacity * m_increaseFactor;
}
m_data[m_backIndex] = item;
m_backIndex++;
if(m_backIndex == m_capacity) {
m_backIndex = 0;
}
m_size++;
}
template <typename T>
T cyclic_double_queue<T>::dequeue_front()
{
//TODO: Remove following line and add your implementation here.
if (empty()) {
throw std::out_of_range("cyclic_double_queue is empty!");
}
T item = m_data[m_frontIndex];
m_frontIndex = (m_frontIndex + 1) % m_capacity;
m_size--;
if (m_capacity > 4 * m_size) {
if (m_capacity == m_initialCapacity) {
}
else if((m_capacity/m_decreaseFactor) > m_initialCapacity) {
m_data = resize(m_capacity/m_decreaseFactor);
m_capacity = m_capacity/m_decreaseFactor;
}
else {
m_data = resize(m_initialCapacity);
m_capacity = m_initialCapacity;
}
}
return item;
}
template <typename T>
T cyclic_double_queue<T>::dequeue_back()
{
//TODO: Remove following line and add your implementation here.
if (empty()) {
throw std::out_of_range("cyclic_double_queue is empty!");
}
if (m_backIndex == 0) {
m_backIndex = m_capacity - 1;
} else {
m_backIndex--;
}
T item = m_data[m_backIndex];
m_size--;
if (m_capacity > 4 * m_size) {
if (m_capacity == m_initialCapacity) {
}
else if((m_capacity/m_decreaseFactor) > m_initialCapacity) {
m_data = resize(m_capacity/m_decreaseFactor);
m_capacity = m_capacity/m_decreaseFactor;
}
else {
m_data = resize(m_initialCapacity);
m_capacity = m_initialCapacity;
}
}
return item;
}
template <typename T>
void cyclic_double_queue<T>::pop_front()
{
//TODO: Remove following line and add your implementation here.
dequeue_front();
}
template <typename T>
void cyclic_double_queue<T>::pop_back()
{
//TODO: Remove following line and add your implementation here.
dequeue_back();
}
template <typename T>
bool cyclic_double_queue<T>::empty() const
{
//TODO: Remove following line and add your implementation here.
if (m_size == 0) {
return true;
}
else {
return false;
}
}
template <typename T>
T& cyclic_double_queue<T>::front()
{
//TODO: Remove following line and add your implementation here.
if (empty()) {
throw std::out_of_range("cyclic_double_queue is empty!");
}
return m_data[m_frontIndex];
}
template <typename T>
T& cyclic_double_queue<T>::back()
{
//TODO: Remove following line and add your implementation here.
if (empty()) {
throw std::out_of_range("cyclic_double_queue is empty!");
}
if (m_backIndex == 0) {
return m_data[m_capacity - 1];
}
return m_data[m_backIndex - 1];
}
template <typename T>
void cyclic_double_queue<T>::clear()
{
//TODO: Remove following line and add your implementation here.
delete[] m_data;
m_capacity = m_initialCapacity;
m_data = new T[m_capacity];
m_frontIndex = 0;
m_backIndex = 0;
m_size = 0;
}
template <typename T>
std::string cyclic_double_queue<T>::print_status() const
/* {
//TODO: Remove following line and add your implementation here.
std::string result;
for (size_t i = 0; i < m_capacity; ++i) {
if ( i < m_backIndex && m_backIndex < m_frontIndex) {
// queue is B - F
result += "[+]";
}
else if (i >= m_frontIndex && i < m_backIndex && m_backIndex < m_capacity) {
// queue is F - B
result += "[+]";
}
else {
result += "[-]";
}
}
return result;
} */
{
//TODO: Remove following line and add your implementation here.
std::string result;
if(m_size == 0){
for(size_t i = 0; i<m_capacity; ++i){
result += "[-]";
}
}
else if(m_size == m_capacity){
for(size_t i =0; i<m_capacity; i++){
result += "[+]";
}
}
else {
if(m_backIndex < m_frontIndex){
for (size_t i = 0; i < m_capacity; ++i) { // 2
// if ( i < m_backIndex && m_backIndex < m_frontIndex) {
// // queue is B - F
// result += "[+]";
// }
// else if (i >= m_frontIndex && i < m_backIndex && m_backIndex < m_capacity) {
// // queue is F - B
// result += "[+]";
// }
// else {
// result += "[-]";
// }
if(i < m_backIndex && i < m_frontIndex){
result += "[+]";
}
else if(i < m_frontIndex){
result += "[-]";
}
else{
result += "[+]";
}
}
}
else{
for(size_t i =0; i<m_capacity; i++){
if(i >= m_frontIndex && i < m_backIndex){
result += "[+]";
}
else{
result += "[-]";
}
}
}
}
return result;
}
template <typename T>
size_t cyclic_double_queue<T>::get_size() const
{
//TODO: Remove following line and add your implementation here.
return m_size;
}
template <typename T>
size_t cyclic_double_queue<T>::get_capacity() const
{
//TODO: Remove following line and add your implementation here.
return m_capacity;
}
}
//debugger code
/*
template <typename T>
T* cyclic_double_queue<T>::resize(size_t new_size)
{
/*copying old array into new array */
/* T* newArray = new T[new_size]();
m_backIndex = 0;
for (int i=0; i < m_size; i++) {
newArray[i] = m_data[m_frontIndex];
m_frontIndex++;
m_backIndex++;
if (m_frontIndex >= m_capacity) {
m_frontIndex = 0;
}
}
m_frontIndex = 0;
std :: cout << "I resized the array\n";
for(int i =0; i<new_size; i++){
std::cout << newArray[i] << " ";
}
std :: cout << "\n";
std :: cout << "Front = " << m_frontIndex << " and Back = " << m_backIndex << "\n";
return newArray;
}
template <typename T>
void cyclic_double_queue<T>::enqueue_front(const T& item)
{
//TODO: Remove following line and add your implementation here.
if (m_size == m_capacity) {
m_data = resize(m_capacity * m_increaseFactor);
m_capacity = m_capacity * m_increaseFactor;
}
if (m_frontIndex == 0) {
m_frontIndex = m_capacity - 1;
} else {
m_frontIndex--;
}
m_data[m_frontIndex] = item;
m_size++;
std :: cout << "I Enqueued front\n";
for(int i =0; i<m_capacity; i++){
std::cout << m_data[i] << " ";
}
std :: cout << "\n";
}
template <typename T>
void cyclic_double_queue<T>::enqueue_back(const T& item)
{
//TODO: Remove following line and add your implementation here.
if (m_size == m_capacity) {
m_data = resize(m_capacity * m_increaseFactor);
m_capacity = m_capacity * m_increaseFactor;
}
m_data[m_backIndex] = item;
m_backIndex++;
if(m_backIndex == m_capacity) {
m_backIndex = 0;
}
m_size++;
std :: cout << "I Enqueued back\n";
for(int i =0; i<m_capacity; i++){
std::cout << m_data[i] << " ";
}
std :: cout << "\n";
}
template <typename T>
T cyclic_double_queue<T>::dequeue_front()
{
//TODO: Remove following line and add your implementation here.
if (empty()) {
throw std::out_of_range("cyclic_double_queue is empty!");
}
T item = m_data[m_frontIndex];
m_frontIndex = (m_frontIndex + 1) % m_capacity;
m_size--;
std :: cout << "I Dequeued front\nNow, my front = "<<m_frontIndex << "and back = "<<m_backIndex << "\n";
for(int i =0; i<m_capacity; i++){
std::cout << m_data[i] << " ";
}
std :: cout << "\n";
if (m_capacity > 4 * m_size) {
if((m_capacity/m_decreaseFactor) > m_initialCapacity) {
m_data = resize((m_capacity/m_decreaseFactor));
m_capacity = m_capacity/m_decreaseFactor;
}
else {
m_data = resize(m_initialCapacity);
m_capacity = m_initialCapacity;
}
}
return item;
}
template <typename T>
T cyclic_double_queue<T>::dequeue_back()
{
//TODO: Remove following line and add your implementation here.
if (empty()) {
throw std::out_of_range("cyclic_double_queue is empty!");
}
if (m_backIndex == 0) {
m_backIndex = m_capacity - 1;
} else {
m_backIndex--;
}
T item = m_data[m_backIndex];
m_size--;
std :: cout << "I Dequeued back\n";
for(int i =0; i<m_capacity; i++){
std::cout << m_data[i] << " ";
}
std :: cout << "\n";
if (m_capacity > 4 * m_size) {
if((m_capacity/m_decreaseFactor) > m_initialCapacity) {
m_data = resize((m_capacity/m_decreaseFactor));
m_capacity = m_capacity/m_decreaseFactor;
}
else{
m_data = resize(m_initialCapacity);
m_capacity = m_initialCapacity;
}
}
return item;
}
template <typename T>
void cyclic_double_queue<T>::pop_front()
{
//TODO: Remove following line and add your implementation here.
dequeue_front();
}
template <typename T>
void cyclic_double_queue<T>::pop_back()
{
//TODO: Remove following line and add your implementation here.
dequeue_back();
}
template <typename T>
bool cyclic_double_queue<T>::empty() const
{
//TODO: Remove following line and add your implementation here.
if (m_size == 0) {
return true;
}
else {
return false;
}
}
template <typename T>
T& cyclic_double_queue<T>::front()
{
//TODO: Remove following line and add your implementation here.
if (empty()) {
throw std::out_of_range("cyclic_double_queue is empty!");
}
return m_data[m_frontIndex];
}
template <typename T>
T& cyclic_double_queue<T>::back()
{
//TODO: Remove following line and add your implementation here.
if (empty()) {
throw std::out_of_range("cyclic_double_queue is empty!");
}
if (m_backIndex == 0) {
return m_data[m_capacity - 1];
}
return m_data[m_backIndex - 1];
}
template <typename T>
void cyclic_double_queue<T>::clear()
{
//TODO: Remove following line and add your implementation here.
delete[] m_data;
m_capacity = m_initialCapacity;
m_data = new T[m_capacity];
m_frontIndex = 0;
m_backIndex = 0;
m_size = 0;
}
template <typename T>
std::string cyclic_double_queue<T>::print_status() const
{
//TODO: Remove following line and add your implementation here.
std::string result;
if(m_size == 0){
for(size_t i = 0; i<m_capacity; ++i){
result += "[-]";
}
}
else if(m_size == m_capacity){
for(size_t i =0; i<m_capacity; i++){
result += "[+]";
}
}
else {
if(m_backIndex < m_frontIndex){
for (size_t i = 0; i < m_capacity; ++i) {
if(i < m_backIndex && i < m_frontIndex){
result += "[+]";
}
else if(i < m_frontIndex){
result += "[-]";
}
else{
result += "[+]";
}
}
}
else{
for(size_t i =0; i<m_capacity; i++){
if(i >= m_frontIndex && i < m_backIndex){
result += "[+]";
}
else{
result += "[-]";
}
}
}
}
return result;
}
template <typename T>
size_t cyclic_double_queue<T>::get_size() const
{
//TODO: Remove following line and add your implementation here.
return m_size;
}
template <typename T>
size_t cyclic_double_queue<T>::get_capacity() const
{
//TODO: Remove following line and add your implementation here.
return m_capacity;
}
}
*/Leave a Comment