1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14/* Priority Queue Code for shortest path in graph */
15
16#include "config.h"
17#include <memory.h>
18#include <assert.h>
19
20#include "fPQ.h"
21
22static snode** pq;
23static int PQcnt;
24static snode guard;
25static int PQsize;
26
27void
28PQgen(int sz)
29{
30 if (!pq) {
31 pq = N_NEW(sz+1,snode*);
32 pq[0] = &guard;
33 PQsize = sz;
34 }
35 PQcnt = 0;
36}
37
38void
39PQfree(void)
40{
41 free (pq);
42 pq = NULL;
43 PQcnt = 0;
44}
45
46void
47PQinit(void)
48{
49 PQcnt = 0;
50}
51
52void
53PQcheck (void)
54{
55 int i;
56
57 for (i = 1; i <= PQcnt; i++) {
58 if (N_IDX(pq[i]) != i) {
59 assert (0);
60 }
61 }
62}
63
64void
65PQupheap(int k)
66{
67 snode* x = pq[k];
68 int v = x->n_val;
69 int next = k/2;
70 snode* n;
71
72 while (N_VAL(n = pq[next]) < v) {
73 pq[k] = n;
74 N_IDX(n) = k;
75 k = next;
76 next /= 2;
77 }
78 pq[k] = x;
79 N_IDX(x) = k;
80}
81
82int
83PQ_insert(snode* np)
84{
85 if (PQcnt == PQsize) {
86 agerr (AGERR, "Heap overflow\n");
87 return (1);
88 }
89 PQcnt++;
90 pq[PQcnt] = np;
91 PQupheap (PQcnt);
92 PQcheck();
93 return 0;
94}
95
96void
97PQdownheap (int k)
98{
99 snode* x = pq[k];
100 int v = N_VAL(x);
101 int lim = PQcnt/2;
102 snode* n;
103 int j;
104
105 while (k <= lim) {
106 j = k+k;
107 n = pq[j];
108 if (j < PQcnt) {
109 if (N_VAL(n) < N_VAL(pq[j+1])) {
110 j++;
111 n = pq[j];
112 }
113 }
114 if (v >= N_VAL(n)) break;
115 pq[k] = n;
116 N_IDX(n) = k;
117 k = j;
118 }
119 pq[k] = x;
120 N_IDX(x) = k;
121}
122
123snode*
124PQremove (void)
125{
126 snode* n;
127
128 if (PQcnt) {
129 n = pq[1];
130 pq[1] = pq[PQcnt];
131 PQcnt--;
132 if (PQcnt) PQdownheap (1);
133 PQcheck();
134 return n;
135 }
136 else return 0;
137}
138
139void
140PQupdate (snode* n, int d)
141{
142 N_VAL(n) = d;
143 PQupheap (n->n_idx);
144 PQcheck();
145}
146
147void
148PQprint (void)
149{
150 int i;
151 snode* n;
152
153 fprintf (stderr, "Q: ");
154 for (i = 1; i <= PQcnt; i++) {
155 n = pq[i];
156 fprintf (stderr, "%d(%d:%d) ",
157 n->index, N_IDX(n), N_VAL(n));
158 }
159 fprintf (stderr, "\n");
160}
161