8 Puzzle Code - LinkQueue.h

#include "TreeNode.h"

#ifndef _LINKQUEUE_H
#define _LINKQUEUE_H

#define TILESTEPS 1
#define DISTANCE 2
#define MANHATTAN 3
#define ASTAR 4

class QueueNode{
public:
TreeNode* treenode;
QueueNode* next;
QueueNode(TreeNode* thenode){
treenode=thenode;
next=NULL;
}
};

class LinkQueue{
public:
QueueNode* head;
QueueNode* tail;

LinkQueue(){
head=NULL;
tail=NULL;
}

BOOL isEmpty(){ return (head==NULL && tail==NULL); }

void add(TreeNode* thenode){
QueueNode* newnode = new QueueNode(thenode);
if(isEmpty()){
head=newnode;
tail=head;
}
else{
tail->next=newnode;
tail=newnode;
}
}

//Add in version 3.
//Adding Q with sort manner according to node heuristic value.
void addHeuristic(TreeNode* thenode, int type){
UINT currh, newh;
QueueNode* newnode=new QueueNode(thenode);

if(isEmpty()){
head=newnode;
tail=head;
}
else{
QueueNode* prevnode;
QueueNode* currnode;
BOOL addedflag;

addedflag=false;
currnode=head;
prevnode=NULL;

while(currnode!=NULL){
switch(type){
case TILESTEPS:
case DISTANCE:
case MANHATTAN:
currh=currnode->treenode->h;
newh=newnode->treenode->h;
break;

case ASTAR:
currh=currnode->treenode->fn;
newh=newnode->treenode->fn;
break;
}

if( currh>newh ){
if(prevnode==NULL){
head=newnode;
head->next=currnode;
}
else{
newnode->next=currnode;
prevnode->next=newnode;
}

addedflag=true;
break;
}

prevnode=currnode;
currnode=currnode->next;
}

if(!addedflag){
tail->next=newnode;
tail=newnode;
}
}
}

QueueNode* get(){
QueueNode* temp;
temp=head;
head=head->next;
if(head==NULL) tail=NULL;
return temp;
}

void deleteNode(){
QueueNode* curr;
curr=head;
while(curr!=NULL){
head=head->next;
delete curr;
curr=head;
}
}

void reset(){
deleteNode();
head=NULL;
tail=NULL;
}

~LinkQueue(){
deleteNode();
}
};
#endif