blob: 0e4df49bc8ace697641fd212e7620c12d3904699 (
plain)
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
/*
pqueue.c - implementation of a priority queue by using a binary heap.
Originally written by Justin-Heyes Jones
Modified by Shlomi Fish, 2000
This file is in the public domain (it's uncopyrighted).
Check out Justin-Heyes Jones' A* page from which this code has
originated:
http://www.geocities.com/jheyesjones/astar.html
*/
/* manage a priority queue as a heap
the heap is implemented as a fixed size array of pointers to your data */
#include <stdio.h>
#include <stdlib.h>
#include "jhjtypes.h"
#include "pqueue.h"
#ifdef DMALLOC
#include "dmalloc.h"
#endif
#define TRUE 1
#define FALSE 0
/* initialise the priority queue with a maximum size of maxelements. maxrating is the highest or lowest value of an
entry in the pqueue depending on whether it is ascending or descending respectively. Finally the bool32 tells you whether
the list is sorted ascending or descending... */
void freecell_solver_PQueueInitialise(
PQUEUE *pq,
int32 MaxElements
)
{
pq->MaxSize = MaxElements;
pq->CurrentSize = 0;
pq->Elements = (pq_element_t*) malloc( sizeof( pq_element_t ) * (MaxElements + 1) );
if( pq->Elements == NULL )
{
printf( "Memory alloc failed!\n" );
}
}
/* join a priority queue
returns TRUE if successful, FALSE if fails. (You fail by filling the pqueue.)
PGetRating is a function which returns the rating of the item you're adding for sorting purposes */
int freecell_solver_PQueuePush( PQUEUE *pq, void *item, pq_rating_t r)
{
uint32 i;
pq_element_t * Elements = pq->Elements;
int32 CurrentSize = pq->CurrentSize;
if (CurrentSize == pq->MaxSize )
{
int new_size;
new_size = pq->MaxSize + 256;
pq->Elements = Elements = (pq_element_t *)realloc( Elements, sizeof(pq_element_t) * (new_size+1));
pq->MaxSize = new_size;
}
{
/* set i to the first unused element and increment CurrentSize */
i = (++CurrentSize);
/* while the parent of the space we're putting the new node into is worse than
our new node, swap the space with the worse node. We keep doing that until we
get to a worse node or until we get to the top
note that we also can sort so that the minimum elements bubble up so we need to loops
with the comparison operator flipped... */
{
while( ( i==PTQ_FIRST_ENTRY ?
(PQUEUE_MaxRating) /* return biggest possible rating if first element */
:
(PGetRating(Elements[ PTQ_PARENT_INDEX(i) ]) )
)
< r
)
{
Elements[ i ] = Elements[ PTQ_PARENT_INDEX(i) ];
i = PTQ_PARENT_INDEX(i);
}
}
/* then add the element at the space we created. */
Elements[i].item = item;
Elements[i].rating = r;
}
pq->CurrentSize = CurrentSize;
return TRUE;
}
#define PQueueIsEmpty(pq) ((pq)->CurrentSize == 0)
/* free up memory for pqueue */
void freecell_solver_PQueueFree( PQUEUE *pq )
{
free( pq->Elements );
}
/* remove the first node from the pqueue and provide a pointer to it */
void *freecell_solver_PQueuePop( PQUEUE *pq)
{
int32 i;
int32 child;
pq_element_t * Elements = pq->Elements;
int32 CurrentSize = pq->CurrentSize;
pq_element_t pMaxElement;
pq_element_t pLastElement;
if( PQueueIsEmpty( pq ) )
{
return NULL;
}
pMaxElement = Elements[PTQ_FIRST_ENTRY];
/* get pointer to last element in tree */
pLastElement = Elements[ CurrentSize-- ];
{
/* code to pop an element from an ascending (top to bottom) pqueue */
/* UNTESTED */
for( i=PTQ_FIRST_ENTRY; (child = PTQ_LEFT_CHILD_INDEX(i)) <= CurrentSize; i=child )
{
/* set child to the smaller of the two children... */
if( (child != CurrentSize) &&
(PGetRating(Elements[child + 1]) > PGetRating(Elements[child])) )
{
child ++;
}
if( PGetRating( pLastElement ) < PGetRating( Elements[ child ] ) )
{
Elements[ i ] = Elements[ child ];
}
else
{
break;
}
}
}
Elements[i] = pLastElement;
pq->CurrentSize = CurrentSize;
return pMaxElement.item;
}
|
