Thread: Priority Q Exercise Due Today at night

  1. #1
    Registered User
    Join Date
    Dec 2017
    Posts
    37

    Priority Q Exercise Due Today at night

    I have to do this


    • Imagine you're writing a little program to categorize bugs in a game and you want to push the bugs into a queue. The bugs will have a char priority(level) of 'A', 'B', or 'C'.
    • I want you to create a small class (or struct) for the bugs and they only have to have two properties:
      • A char for the priority with a suggested name of m_cPriority
      • A string or char* for the description with a suggested name of m_sDesc

    • You'll be creating a queue of these objects as the nodes and this will be somewhat of a custom priority queue exercise.
    • For the most part, you're going to change the enQueue method of the BasicQueue to account for the priority of the Bug. For maximum templatability(?), you should have the char priority as the second parameter in the new enQueue in case you want to test the queue with other types. Then you would somehow need to set the priority of the node in the main when enQueue is called.
      • For example, when enQueueing a Bug node, invoke a GetPriority method for the Bug that returns the char priority and have that function invocation as the second parameter of the enQueue call.
      • Or, if you want to enQueue a simple type like int, give the simple nodes an arbitrary char priority. They would, of course, not be Bugs but you're still able to use this priority queue for other purposes.

    • So, in the enQueue, you have to check the priority of the Node and then insert the Node in the queue based on these priorities. 'A' have the highest priority, 'B' second and 'C' third. Nodes of the same priority are pushed to the end of their respective priorities. For example a new 'A' bug, will get pushed to the end of the 'A's already in the queue.
    • All I want you to alter is the enQueue and add the Bug struct and account for this new priority.


    this is my basicqueue.h
    Code:
     #pragma once
    #include <iostream>
    using namespace std;
    
    class Unit
    {
    private:
        string m_sName;
    public:
        Unit(const string s) : m_sName(s) {}
        friend ostream& operator<<(ostream& s, const Unit& u);
    };
    
    template <class T>
    class Node
    {
    public:
        T m_tData;
        Node<T>* m_pNext;
        Node(T val) : m_tData(val), m_pNext(nullptr) {}
    };
    
    class Bugs
    {
    private:
      char m_cPriority;
      string m_sDesc;
    
    };
    
    template <class T>
    class BasicQueue
    {
    private:
        Node<T>* m_pHead;
        Node<T>* m_pTail;
    public:
        BasicQueue() : m_pHead(nullptr), m_pTail(nullptr) {}
        ~BasicQueue()
        {
            //Node<T>* current = m_pHead; // Consider this an iterator.
            Node<T>* next;
            while (m_pHead != nullptr)
            {
                next = m_pHead->m_pNext;
                delete m_pHead;
                m_pHead = next;
            }
        }
        void enQueue(T val) // 'Push' method.
        {
            Node<T>* newNode = new Node<T>(val);
            if (m_pHead == nullptr) // List is empty.
            {
                m_pHead = m_pTail = newNode;
            }
            else // New node becomes the new tail.
            {
                m_pTail->m_pNext = newNode;
                m_pTail = m_pTail->m_pNext;
            }
        }
        T deQueue() // 'Pop' method. 
        {
            if (m_pHead != nullptr)
            {
                T val = m_pHead->m_tData; // Storing the data to be returned.
                Node<T>* next;
                next = m_pHead->m_pNext;
                delete m_pHead; // Deallocating head.
                m_pHead = next;
                return val; // Throwing copy of old head's data.
            }
        }
        bool isEmpty()
        {
            return m_pHead == nullptr;
        }
        void print()
        {
            if (isEmpty())
                return;
            cout << "Queue contents: ";
            Node<T>* current = m_pHead;
            while (current != nullptr)
            {
                cout << current->m_tData << ' ';
                current = current->m_pNext;
            }
            cout << endl;
        }
    };
    
    ostream& operator<<(ostream& s, const Unit& u)
    {
        s << u.m_sName;
        return s;
    }
    main.cpp
    Code:
    #include <iostream>
    #include <string>
    #include "BasicQueue.h"
    using namespace std;
    
    int main()
    {
        BasicQueue<int> iQ;
        iQ.enQueue(42);
        iQ.enQueue(117);
        iQ.print();
        Unit uOne("Infantry");
        Unit uTwo("Commando");
        BasicQueue<Unit> uQ;
        uQ.enQueue(uOne);
        uQ.enQueue(uTwo);
        uQ.print();
        uQ.deQueue();
        uQ.print();
        system("pause");
        return 0;
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,561
    So, what help do you need?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,767
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Dec 2017
    Posts
    37
    trying to put bugs in enqueue got error c2187 for the arrow thing it says it was unexpected here

    Code:
     #pragma once
    #include <iostream>
    
    using namespace std;
    
    template <class T>
    struct Bug {
        char m_cpriority;
        string m_sDesc;
        T data;
        Bug(const T &);
        Bug(const T &, char);
    };
    
    template <class T>
    class Node
    {
    public:
        T m_tData;
        Node<T>* m_pNext;
        Node(T val) : m_tData(val), m_pNext(nullptr) {}
    };
    
    template <class T>
    class PriorityQueue {
    private:
        Node<T> *head; 
    public:
        PriorityQueue();
        ~PriorityQueue();
        void enQueue(const Bug<T> &);
        Bug<T> deQueue();
        bool isEmpty() const;
        void print() const;
    };
    
    template <class T>
    class BasicQueue
    {
    private:
        Node<T>* m_pHead;
        Node<T>* m_pTail;
    public:
        BasicQueue() : m_pHead(nullptr), Bug(nullptr) {}
        ~BasicQueue()
        {
            //Node<T>* current = m_pHead; // Consider this an iterator.
            Node<T>* next;
            while (m_pHead != nullptr)
            {
                next = m_pHead->m_pNext;
                delete m_pHead;
                m_pHead = next;
            }
        }
        void enQueue(T val) // 'Push' method.
        {
            Node<T>* newNode = new Node<T>(val);
            if (m_pHead == nullptr) // List is empty.
            {
                m_pHead = newNode;
            }
            else // New node becomes the new tail.
            {
                Bug->m_pNext = newNode;
                Bug = Bug->m_pNext;
            }
        }
        T deQueue() // 'Pop' method. 
        {
            if (m_pHead != nullptr)
            {
                T val = m_pHead->m_tData; // Storing the data to be returned.
                Node<T>* next;
                next = m_pHead->m_pNext;
                delete m_pHead; // Deallocating head.
                m_pHead = next;
                return val; // Throwing copy of old head's data.
            }
        }
        bool isEmpty()
        {
            return m_pHead == nullptr;
        }
        void print()
        {
            if (isEmpty())
                return;
            cout << "Queue contents: ";
            Node<T>* current = m_pHead;
            while (current != nullptr)
            {
                cout << current->m_tData << ' ';
                current = current->m_pNext;
            }
            cout << endl;
        }
    };
    Code:
     #include <iostream>
    #include <string>
    #include "pch.h"
    #include "basicthing.h"
    using namespace std;
    
    int main()
    {
        BasicQueue<int> iQ;
        iQ.enQueue(42);
        iQ.enQueue(17);
        iQ.enQueue(7);
        iQ.enQueue(117);
        iQ.print();
        //Unit uOne("Infantry");
        //Unit uTwo("Commando");
        //<Unit> uQ;
        //uQ.enQueue(uOne);
        //uQ.enQueue(uTwo);
        //uQ.print();
        //uQ.deQueue();
        //uQ.print();
        system("pause");
        return 0;

  5. #5
    Informer -Adrian's Avatar
    Join Date
    Jan 2013
    Posts
    830
    Consider:
    Code:
    template <class T>
    class BasicQueue
    {
    private:
        Node<T>* m_pHead;
        Node<T>* m_pTail;
    public:
        BasicQueue() : m_pHead(nullptr), Bug(nullptr) {}
        ~BasicQueue()
        {
            Node<T>* next;
            while (m_pHead != nullptr)
            {
                next = m_pHead->m_pNext;
                delete m_pHead;
                m_pHead = next;
            }
        }
        void enQueue(T val)
        {
            Node<T>* newNode = new Node<T>(val);
            if (m_pHead == nullptr)
            {
                m_pHead = newNode;
            }
            else
            {
                Bug->m_pNext = newNode; // Where does this 'Bug' come from?
                Bug = Bug->m_pNext;     // ^
            }
        }
        // (...)

  6. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    37
    Did I do the assignment ok for A B and C?

    Code:
    #pragma once
    #include <iostream>
    
    using namespace std;
    
    template <class T>
    struct Bug {
        char m_cpriority;
        string m_sDesc;
        T data;
        Bug(const T &);
        Bug(const T &, char);
    };
    
    template <class T>
    class Node
    {
    public:
        T m_tData;
        Node<T>* m_pNext;
        Node(T val) : m_tData(val), m_pNext(nullptr) {}
    };
    
    template <class T>
    class PriorityQueue {
    private:
        Node<T> *head; 
    public:
        PriorityQueue();
        ~PriorityQueue();
        void enQueue(const Bug<T> &);
        Bug<T> deQueue();
        bool isEmpty() const;
        void print() const;
    };
    
    template <class T>
    class BasicQueue
    {
    private:
        Node<T>* m_pHead;
        Node<T>* m_cpriority;
    public:
        BasicQueue() : m_pHead(nullptr), m_cpriority(nullptr) {}
        ~BasicQueue()
        {
            //Node<T>* current = m_pHead; // Consider this an iterator.
            Node<T>* next;
            while (m_pHead != nullptr)
            {
                next = m_pHead->m_pNext;
                delete m_pHead;
                m_pHead = next;
            }
        }
        void enQueue(T val) // 'Push' method.
        {
            Node<T>* newNode = new Node<T>(val);
            if (m_pHead == nullptr) // List is empty.
            {
                m_pHead = m_cpriority = newNode;
            }
            else // New node becomes the new tail.
            {
                m_cpriority->m_pNext = newNode;
                m_cpriority = m_cpriority->m_pNext;
            }
        }
        T deQueue() // 'Pop' method. 
        {
            if (m_pHead != nullptr)
            {
                T val = m_pHead->m_tData; // Storing the data to be returned.
                Node<T>* next;
                next = m_pHead->m_pNext;
                delete m_pHead; // Deallocating head.
                m_pHead = next;
                return val; // Throwing copy of old head's data.
            }
        }
        bool isEmpty()
        {
            return m_pHead == nullptr;
        }
        void print()
        {
            if (isEmpty())
                return;
            cout << "Queue contents: ";
            Node<T>* current = m_pHead;
            while (current != nullptr)
            {
                cout << current->m_tData << ' ';
                current = current->m_pNext;
            }
            cout << endl;
        }
    };
    Code:
    #include <iostream>
    #include <string>
    #include "pch.h"
    #include "basicthing.h"
    using namespace std;
    
    int main()
    {
        BasicQueue<int> iQ;
        iQ.enQueue(42);
        iQ.enQueue(17);
        iQ.enQueue(7);
        iQ.enQueue(117);
        iQ.print();
        //Unit uOne("Infantry");
        //Unit uTwo("Commando");
        //<Unit> uQ;
        //uQ.enQueue(uOne);
        //uQ.enQueue(uTwo);
        //uQ.print();
        //uQ.deQueue();
        //uQ.print();
        system("pause");
        return 0;
    }

  7. #7
    Registered User
    Join Date
    Dec 2017
    Posts
    37
    am I getting closer
    Code:
    #pragma once
    #include <iostream>
    
    using namespace std;
    
    template <class T>
    struct Bug {
        char m_cpriority;
        string m_sDesc;
        T data;
        Bug(const T &);
        Bug(const T &, char);
        char enQueue(bug, Bug.GetPriority());
    };
    
    template <class T>
    class Node
    {
    public:
        T m_tData;
        Node<T>* m_pNext;
        Node(T val) : m_tData(val), m_pNext(nullptr) {}
    };
    
    template <class T>
    class PriorityQueue {
    private:
        Node<T> *head; 
    public:
        PriorityQueue();
        ~PriorityQueue();
        void enQueue(const Bug<T> &);
        Bug<T> deQueue();
        bool isEmpty() const;
        void print() const;
    };
    
    template <class T>
    class BasicQueue
    {
    private:
        Node<T>* m_pHead;
        Node<T>* m_cpriority;
    public:
        BasicQueue() : m_pHead(nullptr), m_cpriority(nullptr) {}
        ~BasicQueue()
        {
            //Node<T>* current = m_pHead; // Consider this an iterator.
            Node<T>* next;
            while (m_pHead != nullptr)
            {
                next = m_pHead->m_pNext;
                delete m_pHead;
                m_pHead = next;
            }
        }
        void enQueue(T val) // 'Push' method.
        {
            Node<T>* newNode = new Node<T>(val);
            if (m_pHead == nullptr) // List is empty.
            {
                m_pHead = m_cpriority = newNode;
            }
            else // New node becomes the new tail.
            {
                m_cpriority->m_pNext = newNode;
                m_cpriority = m_cpriority->m_pNext;
                Bug.GetPriority();
            }
        }
        T deQueue() // 'Pop' method. 
        {
            if (m_pHead != nullptr)
            {
                T val = m_pHead->m_tData; // Storing the data to be returned.
                Node<T>* next;
                next = m_pHead->m_pNext;
                delete m_pHead; // Deallocating head.
                m_pHead = next;
                return val; // Throwing copy of old head's data.
            }
        }
        bool isEmpty()
        {
            return m_pHead == nullptr;
        }
        void print()
        {
            if (isEmpty())
                return;
            cout << "Queue contents: ";
            Node<T>* current = m_pHead;
            while (current != nullptr)
            {
                cout << current->m_tData << ' ';
                current = current->m_pNext;
            }
            cout << endl;
        }
    };
    i got errors i got error C2061 line 13 syntax error identifer bug
    line 68 C2760 unexpected token '.' expected declaration

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,561
    Bug should be a class, not a class template. I might have written:
    Code:
    class Bug
    {
    public:
        Bug(const std::string& description, char priority) : m_cPriority(priority), m_sDesc(description) {}
    
        std::string GetDescription() const
        {
            return m_sDesc;
        }
    
        char GetPriority() const
        {
            return m_cPriority;
        }
    private:
        char m_cPriority;
        std::string m_sDesc;
    };
    By the way, my guess is that the 'c' in m_cPriority and the 's' in m_sDesc are because your teacher mandated Hungarian notation. These days, Hungarian notation (maybe even "Apps Hungarian", which tries to encode purpose rather than mere data type) is generally regarded as unnecessary in C++, so if it is not actually mandated, I'd suggest dropping it.

    Anyway, here's why Bug should not be a class template:
    Code:
    template<typename T>
    class PriorityQueue
    {
    public:
        PriorityQueue();
        ~PriorityQueue();
        void enQueue(const T& item);
        T deQueue();
        bool isEmpty() const;
        void print() const;
    private:
        Node<T>* head;
    };
    Notice that you would enQueue a T, not a Bug<T>. This T would be instantiated to be Bug. Likewise, you dequeue a T, not a Bug<T>.

    You should also either define the copy constructor and copy assignment operator, or disable them. If you're programming with respect to C++11 or later (and hopefully you are), you should consider if implementing the move constructor and move assignment operator would be useful.

    Besides these, it looks like you should move the code from BasicQueue to PriorityQueue, then get rid of BasicQueue. Furthermore, you actually need to make use of the priority. I don't think you need the queue itself to record a priority. Your teacher recommended this:
    • For the most part, you're going to change the enQueue method of the BasicQueue to account for the priority of the Bug. For maximum templatability(?), you should have the char priority as the second parameter in the new enQueue in case you want to test the queue with other types. Then you would somehow need to set the priority of the node in the main when enQueue is called.
      • For example, when enQueueing a Bug node, invoke a GetPriority method for the Bug that returns the char priority and have that function invocation as the second parameter of the enQueue call.
      • Or, if you want to enQueue a simple type like int, give the simple nodes an arbitrary char priority. They would, of course, not be Bugs but you're still able to use this priority queue for other purposes.

    I'd say this works though another way is to rely on a GetPriority free function that returns the priority of the item:
    Code:
    char GetPriority(const Bug& bug)
    {
        return bug.GetPriority();
    }
    
    char GetPriority(int x)
    {
        return 0;
    }
    So this way your template code will call GetPriority(item) for some item of type T, and it will work as long as GetPriority has been overloaded for T.
    Last edited by laserlight; 12-16-2018 at 03:00 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,767
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    Registered User
    Join Date
    Dec 2018
    Posts
    38
    Sometimes you simply deserve to fail.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Starry night
    By swgh in forum C Programming
    Replies: 5
    Last Post: 12-11-2007, 03:26 PM
  2. Great night for T.V.
    By DISGUISED in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 11-20-2003, 11:53 AM
  3. This is my last night on this computer.
    By joshdick in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 07-12-2003, 01:33 AM
  4. how many pm's do you get a night?
    By Waldo2k2 in forum A Brief History of Cprogramming.com
    Replies: 32
    Last Post: 11-25-2002, 12:44 AM
  5. Quite a night
    By Imperito in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 05-09-2002, 09:39 PM

Tags for this Thread