C++/CLI: priority stack problems

[Dyndrilliac]

I'm implementing my own priority stack as part of a project, and ran into a problem. For some reason, I can't seem to sort the stack properly. I believe the problem lies in my Swap routine. Here's the relevant code:

Code Select Expand

Node^ GetNode(long i) {
if (!ValidIndex(i)) {
throw gcnew Exception("Index out of range.");
} else {
Node^ temp = this->first;

while (i) {
temp = temp->next;
i--;
}

return (temp);
}
}

Byte GetNodePriority(long i) {
if (!ValidIndex(i)) {
throw gcnew Exception("Index out of range.");
} else {
Node^ temp = this->first;

while (i) {
temp = temp->next;
i--;
}

return (temp->priority);
}
}

bool ValidIndex(long i) {
return (this->size >= i);
}

void Swap(Node^ val1, Node^ val2) {
Node^ temp = val1;
val1 = val2;
val2 = temp;
}

void Sort() {
// BubbleSort Algorithm!
long i = this->size;

for (int x = 0; x < i; x++) {
for (int y = x + 1; y < i; y++) {
if (GetNodePriority(y) < GetNodePriority(x)) {
Swap(this->GetNode(y), this->GetNode(x));
}
}
}
}

int main() {

Stack^ s = gcnew Stack;

s->Push("Highest priority data.", 0x00);
s->Push("Higher priority data.", 0x32);
s->Push("High priority data.", 0x64);

s->Push(1);
s->Push(2);
s->Push(3);

s[0] = 1;
s[1] = 22;
s[2] = 333;

Console::WriteLine("{0}",s->Size);
Console::WriteLine();

long x = s->Size;

for (long i = 0; i < (x); i++) // Because the internal count of the stack changes
Console::WriteLine("{0}", s->Pop()); // as Pop's are peformed, it is necessary
// to keep a constant external upperbounds
Console::WriteLine();
Console::WriteLine("{0}",s->Size);

return (0);
}Here's the program output:

6

1
22
333
High priority data.
Higher priority data.
Highest priority data.

0
Press any key to continue . . .

Sort() is called upon completion of a successful Push() operation, and at the beginning of the Pop() routine. The output should be in reverse order, but nothing I do to the sorting algorithm itself makes any difference, therefore the problem must be that the nodes aren't being moved. Anyone have any suggestions?

[K]

I would wager that you're swapping the variables correctly inside the function, but that the pointers external to the function do not change.  Try adding a level of indirection, like

Code Select Expand


void Swap(Node^* val1, Node^* val2)
{
   Node^ temp = *val1;
*val1 = *val2;
*val2 = temp;
}


or whatever the syntax is for an unmanaged pointer to a managed pointer.  If that's possible.

I would help more, but I can't test any of this.  Sorry!

[MyndFyre]

You don't need to use a sort algorithm to do a priority queue.  There are a few general ways to do it.

You can use a list of singly-linked lists where the main list has one node for every priority level that you're going to use.  This works best when you have a pre-known set of priorities and they're not just arbitrarily defined.  Both the push() and pop() operations on this type of stack are O(n) where n is the number of priorities, as long as you keep references to the head and tail of the lists.

On the other hand, if you have to have an arbitrary set of priorities, it's better just to use a single doubly-linked list.  This costs O(1) for a pop operation and O(n) where n is the number of items for a push operation.

If you can work it out, I highly recommend the first option.  It's much more consistent in access speeds and very easy to lock down.  And, if you have constants that define priorities (for example, PRIORITY_HIGHEST) and nothing in between, it's even more efficient because you can store just an array of lists.

Here's pseudocode for both:

Code Select Expand


// stack with predefined priorities:
class Stack
{
 object Pop()
 {
   object result = null;
   for (int priority = HIGHEST_PRIORITY; priority >= LOWEST_PRIORITY; priority--)
   {
     if (lists[priority].peek() == null) continue;
     // List::removeAt(int) should return the object at the specified index and then remove it from the list.
     result = lists[priority].removeAt(0);
     break;
   }
   return result;
 }
 void Push(object o, int priority)
 {
     assert(priority <= HIGHEST_PRIORITY && priority >= LOWEST_PRIORITY);

     // append should simply change the tail of the list.  if (m_tail != null) { m_tail.Next = o; m_tail = o; } else {
     // m_head = m_tail = o; }
     lists[priority].append(o);
 }
}

// stack with arbitrary priorities
class Stack
{
 object Pop()
 {
   object result = m_list.removeAt(0);
   return result;
 }
 void Push(object o, int priority)
 {
   bool inserted = false;
   for (int i = 0; i < m_list.getLength(); i++)
   {
     if (m_list[i].getPriority() < priority)
     {
       m_list.insertAt(o, i);
       inserted = true;
       break;
     }
   }
   // alternatively you could check if (m_list[m_list.getLength() - 1].getPriority() > priority) at the start and insert then, skipping the
   // for loop when you're simply appending to the list.
   if (!inserted)
     m_list.append(o, i);
 }
}


There are more efficient algorithms than just O(n) for loops for i = 0 to n, such as a binary search, but I doubt you're looking to tighten up your code that much (otherwie you'd just use STL).

[Dyndrilliac]

I've been reading through the C++/CLI specification (partly out of curiosity, partly out of necessity), and it makes it sound as though indirection in the way K described is a real pain in the ass. I made the following alterations:

Code Select Expand

void Swap(Node^ val1, Node^ val2) {
Node^ temp = val1;
val1->value = val2->value;
val2->value = temp->value;
}This yields the following output:

6

1
22
333
333
333
333

0
Press any key to continue . . .

For some reason it changed all of the items with priorities into copies of the bottom-most item without a priority.

As far as a different route of implementation is concerned, I would rather make my current method work. I will need to know how to implement sorting in C++/CLI anyway, and this way I can change the sorting mechanism at my leisure.

Edit: The following change was made:

Code Select Expand

void Swap(Node^ val1, Node^ val2) {
Object^ temp = val1->value;
val1->value = val2->value;
val2->value = temp;
}The change yielded the following output:

6

Higher priority data.
333
3
22
1
1

0
Press any key to continue . . .

It's getting closer.

[UserLoser]

Code Select Expand


val1->value ^= val2->value ^= val1->value ^= val2->value;


^^ forget using third variables for swapping values