Perform a Selection Sort based on Priority Key

[DoABarrelRoll94]

I seem to have a problem with my code in that when I test data, I get the same value priority key for each entry. This is a priority queue and the passenger with the least amount in the priority key is supposed to be first in the priority queue but something is wrong. I think it's something to do with the selection sort function but I'm not sure.

#include <iostream>
#include <string>
using namespace std;

class Node
{
    int key = 0;
    string FFS;
    int ticketPrice = 0;
    int arrivalTime = 0;
    string lastName;
    Node* next;
    Node* prev;
    
    friend class Pqueue;
};


class Pqueue
{
private:
    Node* header;                                                 //sentinel node
    Node* trailer;                                                //sentinel node
    Node* curr;
public:
    Pqueue()                                                      //constructor
    {
        header = new Node;
        trailer = new Node;
        header->next = trailer;
        trailer->prev = header;
    }
    void insert(Node*, int, string, int, int, string);            //inserts entry and key
    void removeMin();                                             //removes entry with smallest key
    void size();                                                  //size of priority queue
    bool empty()                                                  //is priority queue empty?
    {
        return header->next == trailer && trailer->prev == header;
    }
    void menu();                                                  //menu for user
    void selectionSort();                                         //selection sort on unsorted sequence
};

void Pqueue::size()
{
    int count = 0;
    curr = header;
    while(curr->next != trailer)
    {
        curr = curr->next;
        count++;
    }
    cout << "The size of the priority queue is " << count << "." << endl;
}

void Pqueue::insert(Node* nextloc, int k, string freqFlyStat, int tickPrice, int arrTime, string lName)
{
    Node* t = new Node;
    t->key = k;
    t->FFS = freqFlyStat;
    t->ticketPrice = tickPrice;
    t->arrivalTime = arrTime;
    t->lastName = lName;
    t->next = nextloc;
    t->prev = nextloc->prev;
    nextloc->prev->next = t;
    nextloc->prev = t;
    cout << endl;
}

void Pqueue::removeMin()
{
    cout << "\nPriority Queue:\n";
    cout << "-----------------\n";
    
    while(!empty())
    {
        Node* old = header->next;
        header->next = old->next;
        old->next->prev = header;
    
        cout << endl << "Last Name: " << old->lastName << endl;
        cout << "Frequent Flyer Status: " << old->FFS << endl;
        cout << "Ticket Price: " << old->ticketPrice << endl;
        cout << "Arrival Time: " << old->arrivalTime << endl;
        cout << "Priority Key: " << old->key << endl;
        
        delete old;
    }
    cout << endl;
}

void Pqueue::menu()
{
    int k = 0;
    int choice;
    int arrTime = 0;
    string freqFlyStat;
    string lName;
    int tickPrice = 0;
    do{
        cout << "Enter 1: Enter passenger information to determine priority of passengers in the queue.\n";
        cout << "Enter 2: Display priority queue.\n";
        cout << "Enter 3: Quit.\n";
        cin >> choice;
    
        switch(choice)
        {
            case 1:
                cout << "Please enter your last name.\n";
                cin >> lName;
            
                cout << "Please enter your frequent flyer status.(NONE, GOLD, SLVR, PLAT)\n";
                cin >> freqFlyStat;
                if(freqFlyStat == "NONE")
                {
                    k += 40;
                }
                else if(freqFlyStat == "SLVR")
                {
                    k += 30;
                }
                else if(freqFlyStat == "GOLD")
                {
                    k += 20;
                }
                else if(freqFlyStat == "PLAT")
                {
                    k += 0;
                }
                
                cout << "Please enter the price paid for the ticket.($1-$500)\n";
                cin >> tickPrice;
                if(tickPrice < 500 && tickPrice > 450)
                {
                    k += 5;
                }
                else if(tickPrice < 450 && tickPrice > 400)
                {
                    k += 10;
                }
                else if(tickPrice < 400 && tickPrice > 350)
                {
                    k += 15;
                }
                else if(tickPrice < 350 && tickPrice > 300)
                {
                    k += 20;
                }
                else if(tickPrice < 300 && tickPrice > 250)
                {
                    k += 25;
                }
                else if(tickPrice < 250 && tickPrice > 200)
                {
                    k += 30;
                }
                else if(tickPrice < 200 && tickPrice > 150)
                {
                    k += 35;
                }
                else if(tickPrice < 150 && tickPrice > 100)
                {
                    k += 40;
                }
                else if(tickPrice < 100 && tickPrice > 50)
                {
                    k += 45;
                }
                else if(tickPrice < 50 && tickPrice > 0)
                {
                    k += 50;
                }
                else if(tickPrice >= 500)
                {
                    k += 0;
                }
                
                cout << "Enter arrival time (in minutes) at the gate prior to departure. Gate opens 1 hour before departure.\n";
                cin >> arrTime;
                if(arrTime == 60)
                {
                    k += 0;
                }
                else
                {
                    k += (60 - arrTime);
                }
                
                insert(trailer, k, freqFlyStat, tickPrice, arrTime, lName);
                break;
            case 2:
                removeMin();
                break;
            case 3:
                return;
            default:
                cout << "You have entered an invalid choice.\n\n";
        }
    }while(choice != 3);
}

void Pqueue::selectionSort()
{
    Node* min;
    Node* i;
    Node* j;
    
    for(i = header; i->next != trailer; i = i->next)
    {
        min = i;
        for(j = i->next; j != trailer; j = j->next)
        {
            if(j->key < min->key)
            {
                min = j;
            }
        }
        if(min != i)
        {
            int temp;
            temp = min->key;
            min->key = i->key;
            i->key = temp;
        }
    }
}

int main()
{
    Pqueue passenger;
    
    cout << "This program determines the priority of passengers who are wait-listed for a flight.\n";
    cout << "------------------------------------------------------------------------------------\n";
    passenger.menu();
    passenger.selectionSort();
    
    cout << "Goodbye.\n";
    
    return 0;
}

[TheIdeasMan]

Have you considered using a debugger?

Hopefully there is a GUI one in your IDE. You can set up a watch list of variable values, step through code 1 line at a time, look at the values, deduce where things go wrong. One can also have break points, evaluate expressions and other handy things.

It will save you days of staring at code, one usually identify problems in a few minutes.

Good Luck !! :+)

[DoABarrelRoll94]

I have considered using a debugger but I have no idea how to use one lol. Do you know of any good tutorials online, specifically for Xcode?

Just a quick question though, does the logic in my selection sort function look correct? I have a good feeling that that is the problem.

[TheIdeasMan]

I have considered using a debugger but I have no idea how to use one lol.

TheIdeasMan wrote:

You can set up a watch list of variable values, step through code 1 line at a time, look at the values, deduce where things go wrong. One can also have break points, evaluate expressions and other handy things.

I am fairly sure Xcode has a GUI debugger somewhere, just have a go - it should be reasonably obvious given my outline here.

Do you know of any good tutorials online, specifically for Xcode?

Surely there would be some results from Google?

Just a quick question though, does the logic in my selection sort function look correct? I have a good feeling that that is the problem.

I don't know enough about the subject to answer that :+(. Where did you get the logic from: why do you think it's wrong? Or do you think you have implemented it incorrectly?

A debugging session can help identify all kinds of things - logical errors is a broad category.

Hope this help a little :+)