I am trying to implement a priority queue using a doubly-linked list, but am having trouble with percolating the nodes up the list. Whenever a node travels more than two levels up, it leaves either a copy of itself or another node in that thread where it should be the node it replaced. The problem is that whenever I percolate, the address for the data is stored locally and not updated correctly. Here is some of my code in case that would help. The deletion of the keys is just something I did as a test, so they can more or less be ignored.
Code:
class PQueue2 {
friend class dList<Queue2>;
public:
PQueue2();
~PQueue2();
void insert(int key, Jval val);
int minkey();
Jval minval();
void deletemin();
int size();
bool empty();
void print_it();
void moveto(int place);
// void dList<Queue2 *>::swap(Queue2 *, Queue2 *);
protected:
Queue2 *data;
dList<Queue2 *> *Qlist;
int Qsize;
};
...
void PQueue2::insert(int key, Jval val) {
dList<Queue2 *> *temp;
Queue2 *newdata, *olddata;
int i, position, prev, current_key, newkey, newval;
i = 0;
newdata = new Queue2;
olddata = new Queue2;
olddata->key = key;
olddata->val = val;
temp = new dList<Queue2 *>();
printf(" inside insert\n");
if(Qsize++ == 0) { // Therefore, the list is empty
Qlist->append(olddata);
Qlist->first();
}
else { // Element(s) is/are present in the queue, so have to find insertion point
position = Qsize;
current_key = key;
Qlist->append(olddata); // Inserts at end of list
while(position > 1) {
prev = position;
position /= 2;
moveto(position); // Moves to the last node's parent
if(current_key < Qlist->get()->key){ // Swap with the parent node, which is the current one
delete olddata;
olddata = new Queue2;
delete newdata;
newdata = new Queue2;
olddata->key = key;
olddata->val = val;
newdata->key = Qlist->get()->key; // This is the data
newdata->val.i = Qlist->get()->val.i; // To be moved
moveto(prev); // Moves to the pointer which is to be moved up
Qlist->deleteNode();
Qlist->insertBeforeCursor(newdata);
moveto(position);
Qlist->deleteNode();
Qlist->insertBeforeCursor(olddata);
current_key = Qlist->get()->key;
} // END of IF key < ...
} // END WHILE
} // END ELSE
printf(" inside insert, the current tree is\n");
dl_traverse(Qlist) {
printf(" element %d: Val = %d, key = %d\n", ++i, Qlist->get()->val.i, Qlist->get()->key);
}
}
I know I haven't explained this well at all, but if anyone can see where I need to change something or can give me advice on how to do this, I would greatly appreciate it.
Thanks!
P.S. The append, dl_traverse, etc. are functions from a tool my professor gave us that we need to use. If need be, I can explain more about how it works.