Untitled
#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