summaryrefslogtreecommitdiffstats
path: root/kpat/freecell-solver/pqueue.h
blob: cf5f5372bb938b0b15eadc4ea9229e05487a51f4 (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
/*
    pqueue.h - header file for the priority queue implementation.

    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
*/

#ifndef FC_SOLVE__PQUEUE_H
#define FC_SOLVE__PQUEUE_H

#ifdef __cplusplus
extern "C" {
#endif

#include <limits.h>

#include "jhjtypes.h"

#define PQUEUE_MaxRating INT_MAX

typedef int32 pq_rating_t;

typedef struct struct_pq_element_t
{
    void * item;
    pq_rating_t rating;
} pq_element_t;

typedef struct _PQUEUE
{
    int32 MaxSize;
    int32 CurrentSize;
    pq_element_t * Elements; /* pointer to void pointers */
    pq_rating_t MaxRating; /* biggest element possible */
} PQUEUE;

/* given an index to any element in a binary tree stored in a linear array with the root at 1 and
   a "sentinel" value at 0 these macros are useful in making the code clearer */

/* the parent is always given by index/2 */
#define PQ_PARENT_INDEX(i) ((i)>>1)
#define PQ_FIRST_ENTRY (1)

/* left and right children are index * 2 and (index * 2) +1 respectively */
#define PQ_LEFT_CHILD_INDEX(i) ((i)<<1)
#define PQ_RIGHT_CHILD_INDEX(i) (((i)<<1)+1)

void freecell_solver_PQueueInitialise(
    PQUEUE *pq,
    int32 MaxElements
    );

void freecell_solver_PQueueFree( PQUEUE *pq );

int freecell_solver_PQueuePush( PQUEUE *pq, void *item, pq_rating_t);

void *freecell_solver_PQueuePop( PQUEUE *pq);

#define PGetRating(elem) ((elem).rating)

#ifdef __cplusplus
}
#endif

#endif /* #ifdef FC_SOLVE__PQUEUE_H */