Assigning priority to strings

[jkm1]

Hi all,

I have created a string array of 5 and I will use that to enter some "tasks", then I also have an integer array of 5 where i can assign priorities to the information in the string

string info[5];
int p[5];

cout<<"Enter info 1"<<endl;
cin>>info[0];

cout<<"Enter priority"<<endl;
cin>>p[0];

etc,

I want to be able to link the priorities that i assign to that string and be able to call the information that has the highest priority.
I can only using iostream and string header files so far,
any ideas that could point me in the right direction, would be much appreciated.

thank you

[vince1027]

Using what you have, you can just iterate through the p array, get the index with the highest value (assuming value represents priority). Using this array index to obtain the matching value in info array. Very primitive solution, but it does what it needs to do.

[D80DSL3A]

The approach suggested by vince1027 should work well.
It's all about the array index values.

Assuming that priorities are always positive numbers one could use a "sentinel" value of -1 (or any "illegal" value) to indicate that a "slot" is open (no task assigned).
ie: if p[i] = -1 then the queue is not yet full and a new task may be placed in "slot i". If no such i can be found then the queue is full.

When popping a task from the queue, find the index (i) to the highest value stored in p[]. This is next task out. Have your pop() function return info[i] (or an "empty" string if the queue is empty).

Of course, there are always details to consider.
If the queue is full but push() is called anyways, should the new task bump the lowest task off the list (if the new task priority is higher)?

Many solution routes are possible.
I usually try for ease and flexibility of use:

int main()
{
    priorityQ_Arr<5> Q;// A 5 element todo list

    // push tasks in
    Q.push( "task A", 4 );
    Q.push( "task B", 1 );
    Q.push( "task C", 9 );
    Q.push( "task D", 3 );
    Q.push( "task E", 7 );// queue now full

    Q.push( "task F", 5 );// "task F" should be ignored because dropLowTaskPolicy is false
    Q.push( "task G", 6, true );// overriding policy - "task G" will bump "task B" off the list.
    Q.push( "task H", 2, true );// "task H" priority is too low so it will not be added

    // pop tasks out
    while( Q.Size() > 0 ) cout << "Task done: " << Q.pop() << endl;

    return 0;
}

Output:

Task done: task C
Task done: task E
Task done: task G
Task done: task A
Task done: task D

Here, I have chosen to make the "drop low priority task" issue a matter of assignable policy in a class based solution, where I am templating on the array size so queues of this type can be declared (statically) in different sizes. Everything below would actually go above main().
Note: Only the iostream and string headers need be included!

#include <iostream>
#include <string>

using namespace std;
typedef unsigned int uint;

// a template class for an array based priority queue
template<uint capacity>
class priorityQ_Arr
{
    private:
    string info[capacity];
    int p[capacity];
    uint size;
    // copy ctor - tasks are "non copyable", so the queue shouldn't be either (except maybe privately)
    priorityQ_Arr( const priorityQ_Arr& rQ ):size(rQ.size)
    { for(uint i=0; i<capacity; ++i) { p[i] = rQ.p[i]; info[i] = rQ.info[i]; } }

    public:
    static bool dropLowTaskPolicy;// permit public assignment of this policy
    // functions
    bool push( string Info, uint Priority, bool dropLowTask = dropLowTaskPolicy );// returns false if task not added.
    string pop(void);// returns empty string on empty queue
    uint Size(void)const { return size; }
    uint Capacity(void)const { return capacity; }
    // ctor
    priorityQ_Arr(void):size(0) { for(uint i=0; i<capacity; ++i) p[i] = -1; }
};

template<uint capacity>// Add a task to the queue
bool priorityQ_Arr<capacity>::push( string Info, uint Priority, bool dropLowTask )
{
    int i=0, iNew = -1;

    while( (i < (int)capacity) && (p[i] != -1) ) ++i;
    if( i < (int)capacity )
    {
        iNew = i;// take open slot on todo list
        ++size;
    }
    // replace low task ?
    if( (iNew == -1) && dropLowTask )
    {
        int iMin = 0, minPriority = p[0];
        for(i=0; i<(int)capacity; ++i)// find lowest priority task
            if( (p[i] < minPriority) )
            {
                minPriority = p[i];
                iMin = i;
            }
        // replace task iMin with the new higher priority task
        if( p[iMin] < (int)Priority ) iNew = iMin;
    }

    if(iNew >= 0)
    {
        p[iNew] = (int)Priority;// new task
        info[iNew] = Info;
        return true;
    }

    return false;
}

template<uint capacity>// Remove a task from the queue
string priorityQ_Arr<capacity>::pop(void)
{
    int iMax = 0, maxPriority = p[0];
    for(int i=1; i<(int)capacity; ++i)// find highest priority task
        if( p[i] > maxPriority )
        {
            maxPriority = p[i];
            iMax = i;
        }

    if( maxPriority >= 0)
    {
        p[iMax] = -1;// top task performed
        --size;
        return info[iMax];// description of task just completed
    }
    return string();
}

template<uint capacity>// drop lowest priority task if queue already full on push(), unless told otherwise ?
bool priorityQ_Arr<capacity>::dropLowTaskPolicy = false;

[jkm1]

thanks for the information on the stack algorithm, I will definitely have a crack at this way of doing the problem, your help has pointed me in the right direction, will let you know how I have got on :)