Swapping nodes in a doubly linked list - bad logic??

[jojo212]

I've been working on this linked list priority queue for the better part of two days now, and for the life of me I can't find the root of this seg fault. It's driving me insane.

I know that the root of the problem is in my swapUp() function (swapping the positioning of two nodes based on their priority), because the list works great up until it is called. The seg fault is not actually being caused by swapUp(), it's being caused by peekAt(), which returns the element in the node at position n. But the error does not occur unless swapUp() is called first, so that is where the issue is (I think).

There is also a seg fault being caused in the destructor, which I believe may have the same root cause in swapUp().

I have gone over the code over and over and I've been debugging it all night but I just can't figure out exactly what is going wrong. I would really, really appreciate some help with this.

PRIORITY QUEUE:

#ifndef JMF_PriorityQueue
#define JMF_PriorityQueue

#include <iostream>
#include <string>

template <typename T>
class PriorityQueue{
    public:
        struct Node{
            T data;
            int priority;
            Node * next;
            Node * prev;
        };

    PriorityQueue();
    PriorityQueue & operator=(const PriorityQueue &rhs);
    bool isEmpty();         //Returns true if queue is empty
    int getLength();        //Returns length of queue
    void enqueue(T data, int p);    //Enqueues data T with priority p
    void enqueue(T data);           //Enqueues data T with priority 1
    T dequeue();                    //Dequeues and returns data at head of queue
    void clearQueue();              //Empties queue
    T peek();                       //Returns data at head of queue without dequeing it
    T peekAt(int n);                //Returns data element n without dequeuing it
    int getPriority(int n);         //Returns priority of item at position n
    void display();                 //Prints list of data elements to screen
    void revDisplay();
    void swapUp(Node * target);     //Swaps target node with it's neighbor next in line
    bool contains(T data);          //Returns true if data exists as an element anywhere on the queue
    ~PriorityQueue();

    private:
        int size;
        Node * head, *tail;
};

template <typename T>
PriorityQueue<T>::PriorityQueue(){
    size = 0;
    head = 0;
    tail = 0;
}

template <typename T>
PriorityQueue<T> & PriorityQueue<T>::operator=(const PriorityQueue &rhs){
    clearQueue();
    for(int n = 0; n < rhs.size(); n++)
        enqueue(rhs.peekAt(n));
    return *this;
}

template <typename T>
int PriorityQueue<T>::getLength(){
    return size;
}

template <typename T>
bool PriorityQueue<T>::isEmpty(){
    return(!size);
}

template <typename T>
void PriorityQueue<T>::enqueue(T data){
    enqueue(data, 1);
}

template <typename T>
void PriorityQueue<T>::enqueue(T data, int p){
    Node * newNode = new Node();
    newNode -> data = data;
    newNode -> priority = p;

    if(isEmpty()){
        head = newNode;
        tail = newNode;
    } else {
        newNode -> next = tail;
        tail -> prev = newNode;
        tail = newNode;


        //WHEN THIS WHILE LOOP IS COMMENTED OUT (IE NO SORTING), NO SEG FAULT ISSUES

        while(newNode != head && newNode->priority < newNode->next->priority)
            swapUp(newNode);

        std::cout << "\n";
    }
    tail->prev = 0;
    head->next = 0;
    size++;
}

template <typename T>
T PriorityQueue<T>::dequeue(){
    if(isEmpty()){
        std::cout << "\n\nWARNING: Trying to dequeue empty queue\n\n";
        throw 3;
    } else {
        Node * frontNode = head;
        T result = frontNode -> data;
        if(size == 1){
            head = 0;
            tail = 0;
        } else {
            head = frontNode -> prev;
            head -> next = 0;
        }
        delete frontNode;
        size--;
        return result;
    }
}

template <typename T>
void PriorityQueue<T>::clearQueue(){
    while(!isEmpty())
        dequeue();
}

template <typename T>
T PriorityQueue<T>::peek(){
    return peekAt(0);
}

template <typename T>
T PriorityQueue<T>::peekAt(int n){
    T result;
    Node * thisNode;
    if(isEmpty()){
        std::cout << "\n\nWARNING: Trying to peek empty queue\n\n";
        throw 3;
    } else if( n < 0 || n > size){
        std::cout << "\n\nWARNING: Trying to peek queue at non-existent index " << n << "\n\n";
        throw 3;
    } else {
        thisNode = head;
        if(thisNode->prev == 0)
        for(int k = 0; k < n; k++)
            thisNode = thisNode -> prev;
        result = thisNode -> data;              //Crashes program if swapUp() is ever called
    }
    return result;
}

template <typename T>
int PriorityQueue<T>::getPriority(int n){
    int result;
    if(isEmpty()){
        std::cout << "\n\nWARNING: Trying to get priority from empty queue\n\n";
        result = -1;
    } else if( n < 0 || n > size){
        std::cout << "\n\nWARNING: Trying to get priority from non-existent index " << n << "\n\n";
        result = -1;
    } else{
        Node * thisNode = head;
        for(int k = 0; k < n; k++)
            thisNode = thisNode -> prev;
        result = thisNode -> priority;
    }
    return result;
}

template <typename T>
void PriorityQueue<T>::display(){
    if(isEmpty()){
        std::cout << "\nQueue is empty\n";
    } else {
        std::cout << "\nINDEX\tDATA\tPRIORITY\n";
        std::cout << "-----------------------\n";
        Node * thisNode = head;
        for(int n = 0; n < size; n++){
            std::cout << n << "\t" << thisNode->data << "\t" << thisNode->priority << "\n";
            thisNode = thisNode -> prev;
        }
        std::cout << "\n";
    }
}


template <typename T>
void PriorityQueue<T>::revDisplay(){
    if(isEmpty()){
        std::cout << "\nQueue is empty\n";
    } else {
        std::cout << "\nINDEX\tDATA\tPRIORITY\n";
        std::cout << "-----------------------\n";
        Node * thisNode = tail;
        for(int n = 0; n < size; n++){
            std::cout << n << "\t" << thisNode->data << "\t" << thisNode->priority << "\n";
            thisNode = thisNode -> next;
        }
        std::cout << "\n";
    }
}


template <typename T>
void PriorityQueue<T>::swapUp(Node * target){
    Node * partner = target->next;    //Partner = target next

    Node * temp = new Node;   // temp spot to hold partner neighbors

    temp->next = partner->next;
    temp->prev = partner->prev;

    partner->next = target->next;
    partner->prev = target->prev;

    target->next = temp->next;
    target->prev = temp->prev;

    if(target == tail)
        tail = partner;
    if(partner == head)
        head = target;

    delete temp;
}

template <typename T>
bool PriorityQueue<T>::contains(T data){
     bool result = false;
     if(!isEmpty()){
        Node * thisNode = head;
        for(int n = 0; n < size; n++){
            if(thisNode->data == data){
                result = true;
                break;
            }
            thisNode = thisNode -> prev;
        }
    }
    return result;
}

template <typename T>
PriorityQueue<T>::~PriorityQueue(){
    clearQueue();
}

#endif 

TEST PROGRAM:

#include <iostream>
#include <string>
#include <ctype.h>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include "PriorityQueue.hpp"

int main(){
        PriorityQueue<char> test;
        test.enqueue('c',1);
        test.enqueue('a',2);
        test.enqueue('t',3);
        test.display();
        std::cout <<"\nREVERSE:\n";
        test.revDisplay();
        std::cout<<"\nWITH SORTING:\n";
        test.enqueue('d',5);
        test.enqueue('s',9);
        test.enqueue('g',7);
        test.enqueue('o',6);
        test.enqueue('&',4);
        test.display();
        std::cout <<"\n\nALL DONE\n\n";
        return 0; 
}

Okay, so I've tried implementing SwapUp() in a different new way, but it's still giving me the same problem

template <typename T>
void PriorityQueue<T>::swapUp(Node * target){
    Node * partner = target->next;    //Partner = target next

    target->next = partner->next;   //Target next = partner next
    partner->prev = target->prev;   //Partner prev = target prev
    partner->next = target;          //Partner next = target
    target->prev = partner;           //Target prev = partner

    if(target == tail)
        tail = partner;
    if(partner == head)
        head = target;

}

This is driving me absolutely mad. This is such an elementary logic problem I don't know why I'm having so much trouble with it. Any help would be greatly, greatly appreciated!

[cire]

swapUp takes it's argument by value. Any changes made to target in the function will be lost.

[jojo212]

swapUp actually takes it's argument by pointer, so I don't think that is the case. Please correct me if I'm wrong.

[MiiNiPaa]

swapUp messes with node order:

Before:
|->[n-1]-->[target]-->[partner]-->[n+1]--|
|--[n-1]<--[target]<--[partner]<--[n+1]<-|

After:
         /----------------\
         |                V
|->[n-1]-/ [partner]-->[target]-->[n+1]--|
|--[n-1]<--[partner]<--[target] /-[n+1]<-|
                ^               |
                \---------------/

[cire]

swapUp actually takes it's argument by pointer, so I don't think that is the case. Please correct me if I'm wrong.

There is no such thing as passing by pointer. You either pass by reference or by value. In this case you are passing a pointer by value. Any changes made to that pointer do not affect the original.