Untitled
unknown
plain_text
a year ago
9.3 kB
6
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 >= new_size) { 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_capacity = m_capacity * m_increaseFactor; m_data = resize(m_capacity); } 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_capacity = m_capacity * m_increaseFactor; m_data = resize(m_capacity); } 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) { m_capacity = m_capacity/m_decreaseFactor; if(m_capacity > m_initialCapacity) { m_data = resize(m_capacity); } else { 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) { m_capacity = m_capacity/m_decreaseFactor; if(m_capacity > m_initialCapacity) { m_data = resize(m_capacity); } else { 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) { 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; } } 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; } }
Editor is loading...
Leave a Comment