Okay, sorry. Still getting used to this. This is my Item.h file which can be consider the same as a "node" for a tree. The actual "node" that gets stored in the (Minimum) priority queue list (unsorted). Also contains a locator function.
class Locator
{
public:
int pos;
};
template<typename ElemType>
class Item
{
private:
int key;
ElemType elem;
Locator* loc;
public:
Item() { }
Item(const int k = 0, ElemType e = ElemType())
: key(k), elem(e)
{
loc = new Locator();
}
Locator* getLoc()
{
return loc;
}
const int getKey() const
{
return key;
}
const ElemType& getElem() const
{
return elem;
}
void setKey(const int k)
{
key = k;
}
void setElem(const ElemType& e)
{
elem = e;
}
};
This is the unsorted list that the priority queue is implemented from. The function I need help with is the decreaseKey function which I want to take in a int to determine which position should be changed, and the key to change it to. The rest of it works.
#include <list>
#include <iostream>
using namespace std;
template<typename ElemType, typename Comp>
class List
{
public:
int size() const;
bool empty() const;
void insert(const ElemType& e);
const ElemType& min() const;
void deleteMin();
void decreaseKey(const ElemType& e, int key);
private:
list<ElemType> ll;
Comp comp;
};
//Size
template<typename ElemType, typename Comp>
int List<ElemType, Comp>::size() const
{
return ll.size();
}
//Empty
template<typename ElemType, typename Comp>
bool List<ElemType, Comp>::empty() const
{
return ll.empty();
}
//Insert
template<typename ElemType, typename Comp>
void List<ElemType, Comp>::insert(const ElemType& e)
{
list<ElemType>::iterator i;
i = ll.begin();
while( i != ll.end() && !comp(e, *i))
++i;
ll.insert(i,e);
}
//Minimum
template<typename ElemType, typename Comp>
const ElemType& List<ElemType, Comp>::min() const
{
return ll.back();
}
//Remove Minimum
template<typename ElemType, typename Comp>
void List<ElemType, Comp>::deleteMin()
{
ll.pop_back();
}
template<typename ElemType, typename Comp>
void List<ElemType, Comp>::decreaseKey(const ElemType& e, int key)
{
list<ElemType>::iterator i;
for(i = ll.begin(); i != ll.end(); ++i) {
}
}
This is the actual Priority Queue file with the comparator function which can be changed from ">" (minimum) to "<" (maximum).
Function decKey should call decreaseKey from list.h and pass the items I mentioned above (key and position).
#include "List.h"
#include "Item.h"
template<typename ElemType>
class PQComp
{
public:
bool operator()(const Item<ElemType>& e1, const Item<ElemType>& e2)
{
return e1.getKey() > e2.getKey();
}
};
template<typename ElemType>
class PriorityQueue
{
protected:
typedef Item<ElemType> item;
typedef PQComp<ElemType> comp;
private:
List<item, comp> T;
static const int DEF_SIZE = 8;
public:
int size()
{
return T.size();
}
bool isEmpty() const
{
return T.empty();
}
void insertItem(const int k, const ElemType& e)
{
T.insert(item(k, e));
}
const ElemType& minElement()
{
return T.min().getElem();
}
const int minKey()
{
return T.min().getKey();
}
int removeMin()
{
if(!T.empty())
{
T.deleteMin();
return 1;
}
return 0;
}
void decKey(int key, const ElemType& e)
{
T.decreaseKey(item(key, e), key);
}
};
And the main.cpp file which is just a normal main file, nothing to special.
#include "PriorityQueue.h"
#include <string>
#include <iostream>
using namespace std;
int main()
{
PriorityQueue<string> pqList;
string elem;
elem = "bdd";
pqList.insertItem(9, elem);
elem = "acd";
pqList.insertItem(7, elem);
elem = "bcd";
pqList.insertItem(8, elem);
pqList.decKey(2, "zzz");
cout << "Size: " << pqList.size() << endl;
cout << "minElement: " << pqList.minElement() << endl;
cout << "minKey: " << pqList.minKey() << endl;
cout << "Comparisons: " << pqList.removeMin() << endl;
cout << "Minimum removed." << endl << endl;
cout << "Size: " << pqList.size() << endl;
cout << "minElement: " << pqList.minElement() << endl;
cout << "minKey: " << pqList.minKey() << endl << endl;
cout << "Comparisons: " << pqList.removeMin() << endl;
cout << "Minimum removed." << endl << endl;
cout << "Is it empty: " << pqList.isEmpty() << endl;
cout << "Comparisons: " << pqList.removeMin() << endl;
cout << "Minimum removed." << endl << endl;
cout << "Size: " << pqList.size() << endl;
cout << "Is it empty: " << pqList.isEmpty() << endl;
return 0;
}
It all compiles right now and the only thing I haven't implemented is the decrease Key Function which I need in order to implement Dijkstra's algorithm. Thanks for all the help, and sorry if I am going about this the wrong way. Thanks for any help you can give me!