pushrelabel/DijkstraQueue.cpp at master · marmor7/pushrelabel · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include "DijkstraQueue.h"

//Create the Dijkstra Queue
DijkstraQueue::DijkstraQueue(int node_num)
{
	listArray = new DList[node_num - 1];
	arrayPtr = node_num;
}

//Destroy the Dijkstra Queue
DijkstraQueue::~DijkstraQueue(void)
{
	free(listArray);
}

//Add a node with a given distance
void DijkstraQueue::addNode(Node* node, int distance)
{
	if (arrayPtr > distance)
		arrayPtr = distance;
	listArray[distance].insertFront(node);
	count++;
}

//Get the node with the lowest distance label;
Node* DijkstraQueue::getNode()
{
	count--;
	Node* n = listArray[arrayPtr].removeFront();
	//If there are no more nodes in the list find the new lowest pointer
	if (listArray[arrayPtr].front == NULL)
		findNewPtr();
	return n;
}

//Get a node from ptr index with a specific ID
Node* DijkstraQueue::getNode(int ptr, int id)
{
	Node* n;
	while (1)
	{
		n = listArray[ptr].removeFront();
		if (n->getID() == id)
		{
			if (listArray[ptr].front == NULL)
				findNewPtr();
			count--;
			break;
		}
		listArray[ptr].insertBack(n);
	}
	return n;
}

//Find the new array pointer, meaning the lowest index with a non empty list
void DijkstraQueue::findNewPtr()
{
	bool flag = false;
	int i = 0;

	while (!flag)
	{
		if (listArray[i].front != NULL)
		{
			arrayPtr = i;
			flag = true;
		}
		else
			i++;
	}
}