Thread: Problem implementing priority queue using array

First off, why don't you do this*:

Code:

unsigned int time[13], i;
for (i=0; i<13; i++) {
    time[i] = GetCurrTime();
}

As for your problem, well, if this is just a couple of (randomly placed) identical values

1. print out the values in time[] before you feed them to the array, because they were probably identical to start with
2. add sleep(1) into the for loop I suggested to guarantee all the values are different

Your processor can perform tens of billions of operations per second. Of course, the whole routine GetCurrentTime() includes way more than one op, and the processor is also responsible for other things. But the point is, it is easily possible to fit lots of operations into one microsecond.

As is, you can see the differences differ by a factor of ten (sometimes it is <50 usec, sometimes it is >500 usec), and you only have 13 samples. If you did this 10000 times, you might get some idea of the general window -- but that is still a guarantee of nothing, since chances are if processor priorities permit, GetCurrentTime() will execute more than once in a microsecond (conversely, it may have to wait a while). You must use a gap. If 1 second is too long for you to wait, you are already using the high res timer, so:

Code:

void gap (int secs, int hundredths) {
        struct timespec interval;
        interval.tv_sec=secs;
        interval.tv_nsec=hundredths*10000;
        nanosleep(&interval,NULL);
}

Usage is gap(0,1) to "sleep" 1/100th of a second.

* in fact, you can do this:

Code:

for (i=0; i<13; i++) {
    addToQueue(GetCurrTime());
    gap(0,1);
}

to use the return value of one function as a parameter for another.

It's quite possible to get the same timestamp in two successive calls. Processors are FAST.

If you want to preserve the SEQUENCE of events in the queue, so that they at least get processed in the order they were inserted even though they all have the same timestamp, then just make a minor change to your queue insert function so that events are always inserted AFTER any event with the same timestamp.

I didn't test your code but here is my guess.

Code:

for (move=rear; move>=pos; move--)
		{
			msgArray[move+1]=msgArray[move];
		}

Now, that means that even if a number is higher than all the other numbers, so pos == rear, this loop will occur once, copying the second highest number into it's position. More importantly, this will also happen the first time, which throws a wrench into this set of conditions:

num>=msgArray[pos]&& pos<=rear && msgArray[pos]!=0

msgArray[rear] is no longer 0, and pos could == rear. So right away you end up with an extra number (notice there's 16 of them at the end). This error will be "corrected" whenever a new low number is added, pushing the whole list down. But that does not happen after you insert the fourth highest value -- 1, 2, and 3 are already there. So now you have 1, 2, 3, and 4, and four is there twice, then you add 5*. This portion of the array is never modified again.

The reason this problem doesn't repeat has to do with the order the numbers are inserted in -- they continue to bump one another down in sets. Basically, this is a complex version of the classic "off by one error".

* oops! that's not true. You add five first -- anyway, it seems to me this is the nature of the problem. A little hard to get straight just by thinking about it why it occurs where it does, maybe I will come back in a minute if I can get it exactly I would start by fixing that for loop. Remember, presuming "rear" was initially 0, it will always refer to the number after the last number in the array.

Originally Posted by lazyme

Turns out there was no problem with the code.

Well, I assume that you will not come back to read this then, but if you do, take into account what I pointed out -- the end result is okay, but that method is still flawed IMO. Which is not an A-train way to program*

And if I didn't want to waste my time, I should've spotted that mix up first. Except, like I said, there is CLEARLY an issue with that for loop anyway. If you add the highest number last, it will show up, methinks.

* judging one set of results as proof "there is nothing wrong with the code".

Originally Posted by lazyme

Ok.

What do you suggest me to change? Is my for loop flawed?
This is the best way I could think of implementing it.

Well, at least read that post and see if you see what I see.

Then gimme a moment to test this, since I'm the one making a fuss, and I could be wrong...

Okay, I was right, and wrong. It does "unnecessarily" push the numbers down, eg, even when you insert the highest number, it bumps the zeros down.

But this does not lead to the complications I hypothesized, so it is not really a bug.

You could eliminate it anyway by enclosing in a condition:

Code:

if (pos != rear) {
      [the for loop]
}

Also -- I presume you are aware of this -- if one of the numbers added to the queue is zero, the algorithm falls apart (try it). That doesn't matter if it is intended for time stamps or values guaranteed to be greater than zero.

If you are curious, here's the code I used to test. Notice a "!" is printed inside the for loop, indicating when it occurs. It occurs the first time, even though there are no numbers to push down (etc).

Code:

#include <stdio.h>

#define MAX 10

unsigned int msgArray[10] = {0};
int rear = 0;

void addToQueue( unsigned int num )
{
	int pos = 0;
	int move = 0;

	printf("add: %d\n",num);

	if(rear<MAX)
	{
		/*find position to insert*/
		for (pos=0; num>=msgArray[pos]&& pos<=rear  && msgArray[pos]!=0 ; pos++)
		{
		
		}
		
		/*shift cells*/
		for (move=rear; move>=pos; move--)
		{
			printf("!"); fflush(stdout);
			msgArray[move+1]=msgArray[move];
		}
		
		/*copy new int*/
		msgArray[pos]=num;
		rear++;

	}
	else
	{
		printf("\nNo more room to add data", "");
	}
}

int main(int argc, char *argv[]) {
	unsigned int testdata[10] = { 1234, 3, 345, 999999, 89231, 890, 666, 1, 8765, 10 };
	int i,j;
	
	for (j=0; j<10; j++) {
		addToQueue(testdata[j]);
		for (i=0; i<10; i++) printf("%d\n", msgArray[i]);
		getchar();
	}

	return 0;
}

ps. you don't have to use empty brackets with the insertion loop, you can just write:

Code:

for (pos=0; num>=msgArray[pos]&& pos<=rear  && msgArray[pos]!=0 ; pos++);

Incidentally, have you considered using the array to implement a heap, then using the heap to implement a priority queue?