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
|
#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;
}
/* TODO: we need to handle if a pos is already in ppq, but this time we have it with better priority.
* I think we need to implement ppq_remove(*ppq, pos), which'll see if pos is in ppq and will remove it.
* Then we call it where we return PPQ_INSERT_SUCCESS, but before we actually insert the pos. */
int ppq_insert(PositionPQ **ppq, Position pos, size_t priority) {
//printf("Inserting %zu %zu\n", pos.x, pos.y);
PositionPQ *start = *ppq;
if ((*ppq) == NULL) {
(*ppq) = ppq_new(pos, priority);
return PPQ_INSERT_NEW;
}
PositionPQ *n = ppq_new(pos, priority);
if (start->priority > priority) {
n->next = start;
start = n;
*ppq = start;
ppq_remove(&(n->next), pos);
return PPQ_INSERT_SUCCESS;
}
PositionPQ *temp = *ppq;
/* The '=' is commented out because we want to insert before, for speed. To insert after, uncomment it*/
while(temp->next != NULL && temp->next->priority </*=*/ priority) {
if (temp->pos.x == pos.x && temp->pos.y == pos.y && temp->priority <= priority) {
free(n);
return PPQ_INSERT_ALREADY;
}
temp = temp->next;
}
if (temp->pos.x == pos.x && temp->pos.y == pos.y && temp->priority <= priority) {
free(n);
return PPQ_INSERT_ALREADY;
}
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);
}
|
