Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
19 kB
1
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