I was doing my homework for my data structures class, which involves a priority queue using an array based min heap. I wrote the following code.
The problem is that when I use the vSwap(), instead of just writting code to do the swap inside the vReheapify() functions, the pointers in my data get messed up. I'm using the queue in the following manner:
struct PathNode
{
int iCurVert, iTotalWeight;
CGenericQueue<int> Path;
};
CHeapPriorityQueue<PathNode> MainQueue;
After calling vSwap, the pointers inside CGenericQueue<int> Path; are pointing to garbage.
Is there something wrong with my code, or is this a bug in Visual C++? I showed the code to my teacher, and he thought it must be a bug.
template <class DataType> class Node
{
public:
int iPriority;
DataType Data;
Node *next;
};
template <class DataType> class CGenericQueue
{
protected:
Node<DataType> *head, *tail;
public:
CGenericQueue();
~CGenericQueue();
void vEnque(const DataType &item);
int iDeque(DataType &returndata);
CGenericQueue<DataType> & operator = (const CGenericQueue<DataType> &);
};
template <class DataType> CGenericQueue<DataType> & CGenericQueue<DataType>::operator = (const CGenericQueue<DataType> &From)
{
//remove everything from the queue
DataType x;
while(iDeque(x));
//enque the new data
Node<DataType> *cur = From.head;
for(; cur != NULL; cur = cur->next)
{
vEnque(cur->Data);
}
return *this;
}
template <class DataType> CGenericQueue<DataType>::~CGenericQueue()
{
while(head != NULL)
{
Node<DataType> *temp = head;
head = head->next;
delete temp;
}
}
template <class DataType> int CGenericQueue<DataType>::iDeque(DataType &returndata)
{
Node<DataType> *temp;
//Queue is empty
if(head == NULL)
return 0;
returndata = head->Data;
temp = head;
head = head->next;
delete temp;
return 1;
}
template <class DataType> void CGenericQueue<DataType>::vEnque(const DataType &item)
{
Node<DataType> *tempnode = new Node<DataType>;
tempnode->next = NULL;
tempnode->Data = item;
tempnode->iPriority = 0;
if(head == NULL)
head = tail = tempnode;
else
{
tail->next = tempnode;
tail = tail->next;
}
}
template <class DataType> CGenericQueue<DataType>::CGenericQueue()
{
head = tail = NULL;
}
template <class Typex> void vSwap(Typex &x, Typex &y)
{
Typex temp = x;
x = y;
y = temp;
}
template <class DataType> class ArrayNode
{
public:
int iPriority;
DataType Data;
};
template <class DataType> class CHeapPriorityQueue
{
public:
void vEnque(const DataType &item, int iPriority);
int iDeque(DataType &ReturnData);
CHeapPriorityQueue(int x = 100);
//~CHeapPriorityQueue();
protected:
void vReheapifyUp(); //Restores the last item
void vReheapifyDown(); //Restore the first item
int iGetParent(int x) {return (x - 1) / 2;}
int iGetRightChild(int x) {return (x + 1) * 2;}
int iGetLeftChild(int x) {return ((x + 1) * 2) - 1;}
ArrayNode<DataType> m_Data[25];
int m_iLength;
};
template <class DataType> void CHeapPriorityQueue<DataType>::vEnque(const DataType &item, int iPriority)
{
m_Data[m_iLength].Data = item;
m_Data[m_iLength].iPriority = iPriority;
m_iLength++;
vReheapifyUp();
}
template <class DataType> int CHeapPriorityQueue<DataType>::iDeque(DataType &ReturnData)
{
if(!m_iLength)
return 0;
ReturnData = m_Data[0].Data;
m_Data[0] = m_Data[m_iLength - 1];
m_iLength--;
vReheapifyDown();
return 1;
}
template <class DataType> void CHeapPriorityQueue<DataType>::vReheapifyDown()
{
for(int cur = 0; iGetLeftChild(cur) < m_iLength;)
{
if(m_Data[iGetLeftChild(cur)].iPriority < m_Data[iGetRightChild(cur)].iPriority)
{
//vSwap(m_Data[iGetLeftChild(cur)], m_Data[cur]);
ArrayNode<DataType> temp;
temp = m_Data[iGetLeftChild(cur)];
m_Data[iGetLeftChild(cur)] = m_Data[cur];
m_Data[cur] = temp;
cur = iGetLeftChild(cur);
}
else
{
//vSwap(m_Data[iGetRightChild(cur)], m_Data[cur]);
ArrayNode<DataType> temp;
temp = m_Data[iGetRightChild(cur)];
m_Data[iGetRightChild(cur)] = m_Data[cur];
m_Data[cur] = temp;
cur = iGetRightChild(cur);
}
}
}
template <class DataType> void CHeapPriorityQueue<DataType>::vReheapifyUp()
{
for(int cur = m_iLength - 1; cur > 0;)
{
if(m_Data[cur].iPriority < m_Data[iGetParent(cur)].iPriority)
{
//vSwap(m_Data[iGetParent(cur)], m_Data[cur]);
ArrayNode<DataType> temp;
temp = m_Data[iGetParent(cur)];
m_Data[iGetParent(cur)] = m_Data[cur];
m_Data[cur] = temp;
cur = iGetParent(cur);
}
else
return;
}
}
template <class DataType> CHeapPriorityQueue<DataType>::CHeapPriorityQueue(int x)
{
//m_Data = new ArrayNode<DataType>[x];
m_iLength = 0;
}
