Untitled

 avatar
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