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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
#include <stdio.h>
#include <curses.h>
#include "priority_queue.h"
#include "error.h"
PositionPQ *ppq_new(Position pos, size_t priority) {
PositionPQ *ppq = malloc(sizeof(PositionPQ));
ppq->pos = pos;
ppq->priority = priority;
ppq->next = NULL;
return ppq;
}
int ppq_insert(PositionPQ **ppq, Position pos, size_t priority) {
//printf("Inserting %zu %zu\n", pos.x, pos.y);
PositionPQ *start = *ppq;
/* If ppq is empty, create one */
if ((*ppq) == NULL) {
(*ppq) = ppq_new(pos, priority);
return PPQ_INSERT_NEW;
}
/* The new node */
PositionPQ *n = ppq_new(pos, priority);
/* If new priority is better than that of the start, insert in the beginning */
if (start->priority >= priority) {
n->next = start;
start = n;
*ppq = start;
ppq_remove(&(n->next), pos);
return PPQ_INSERT_SUCCESS;
}
/* To avoid changing ppq as it's passed as pointed */
PositionPQ *temp = *ppq;
/* Skip nodes with smaller priority */
while(temp->next != NULL && temp->next->priority < priority) {
/* Node is already in ppq */
if (temp->pos.x == pos.x && temp->pos.y == pos.y && temp->priority <= priority) {
free(n);
return PPQ_INSERT_ALREADY;
}
temp = temp->next;
}
/* Node is already in ppq */
if (temp->pos.x == pos.x && temp->pos.y == pos.y && temp->priority <= priority) {
free(n);
return PPQ_INSERT_ALREADY;
}
/* Insert */
n->next = temp->next;
temp->next = n;
ppq_remove(&(n->next), pos);
return PPQ_INSERT_SUCCESS;
}
Position ppq_pop(PositionPQ **ppq) {
if (*ppq == NULL) {
error("Tried to pop a NULL PositionPQ\n");
}
Position pos = (*ppq)->pos;
if ((*ppq)->next != NULL) { /* If there's a next node */
PositionPQ *next = (*ppq)->next;
free((*ppq));
(*ppq) = next;
} else { /* No next node */
free((*ppq));
(*ppq) = NULL;
}
return pos;
}
void ppq_remove(PositionPQ **ppq, Position pos) {
PositionPQ *temp = *ppq;
if (temp == NULL) {
return;
}
PositionPQ *prev = NULL;
while (temp->next != NULL && (pos.x != temp->pos.x || pos.y != temp->pos.y)) {
prev = temp;
temp = temp->next;
}
if (pos.x == temp->pos.x && pos.y == temp->pos.y) {
if (prev != NULL) {
prev->next = temp->next;
free(temp);
} else {
prev = *ppq;
*ppq = (*ppq)->next;
free(prev);
}
}
}
void ppq_reprioritize(PositionPQ *ppq, Position pos, size_t priority) {
(void)ppq, (void)pos, (void)priority;
todo();
}
void ppq_print(PositionPQ *ppq) {
if (ppq == NULL) {
printf("ppq is NULL\n");
return;
}
int i = 0;
while (ppq->next != NULL) {
printf("%i - %li: %li, %li\n", i++, ppq->priority, ppq->pos.x, ppq->pos.y);
ppq = ppq->next;
}
printf("%i - %li: %li, %li\n", i++, ppq->priority, ppq->pos.x, ppq->pos.y);
}
void ppq_free(PositionPQ *ppq) {
if (ppq == NULL) return;
while(ppq->next != NULL) {
PositionPQ *t = ppq;
ppq = ppq->next;
free(t);
}
if (ppq != NULL) free(ppq);
}
|
