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 <sgraph.h>
17/* typedef snode** PQ; */
18
19#define N_VAL(n) (n)->n_val
20#define N_IDX(n) (n)->n_idx
21#define N_DAD(n) (n)->n_dad
22#define N_EDGE(n) (n)->n_edge
23#define E_WT(e) (e->weight)
24#define E_INCR(e) (e->incr)
25
26#ifdef INLINEPQ
27
28#include "assert.h"
29static snode** pq;
30static int PQcnt;
31static snode guard;
32static int PQsize;
33
34static void
35PQgen(int sz)
36{
37 if (!pq) {
38 pq = N_NEW(sz+1,snode*);
39 pq[0] = &guard;
40 PQsize = sz;
41 }
42 PQcnt = 0;
43}
44
45static void
46PQfree()
47{
48 free (pq);
49 pq = NULL;
50 PQcnt = 0;
51}
52
53static void
54PQinit()
55{
56 PQcnt = 0;
57}
58
59static void
60PQcheck ()
61{
62 int i;
63
64 for (i = 1; i <= PQcnt; i++) {
65 if (N_IDX(pq[i]) != i) {
66 assert (0);
67 }
68 }
69}
70
71static void
72PQupheap(int k)
73{
74 snode* x;
75 x = pq[k];
76 int v = x->n_val;
77 int next = k/2;
78 snode* n;
79
80 while (N_VAL(n = pq[next]) < v) {
81 pq[k] = n;
82 N_IDX(n) = k;
83 k = next;
84 next /= 2;
85 }
86 pq[k] = x;
87 N_IDX(x) = k;
88}
89
90static int
91PQ_insert(snode* np)
92{
93 if (PQcnt == PQsize) {
94 agerr (AGERR, "Heap overflow\n");
95 return 1;
96 }
97 PQcnt++;
98 pq[PQcnt] = np;
99 PQupheap (PQcnt);
100 PQcheck();
101 return 0;
102}
103
104static void
105PQdownheap (int k)
106{
107 snode* x = pq[k];
108 int v = N_VAL(x);
109 int lim = PQcnt/2;
110 snode* n;
111 int j;
112
113 while (k <= lim) {
114 j = k+k;
115 n = pq[j];
116 if (j < PQcnt) {
117 if (N_VAL(n) < N_VAL(pq[j+1])) {
118 j++;
119 n = pq[j];
120 }
121 }
122 if (v >= N_VAL(n)) break;
123 pq[k] = n;
124 N_IDX(n) = k;
125 k = j;
126 }
127 pq[k] = x;
128 N_IDX(x) = k;
129}
130
131static snode*
132PQremove ()
133{
134 snode* n;
135
136 if (PQcnt) {
137 n = pq[1];
138 pq[1] = pq[PQcnt];
139 PQcnt--;
140 if (PQcnt) PQdownheap (1);
141 PQcheck();
142 return n;
143 }
144 else return 0;
145}
146
147static void
148PQupdate (snode* n, int d)
149{
150 N_VAL(n) = d;
151 PQupheap (n->n_idx);
152 PQcheck();
153}
154
155static void
156PQprint ()
157{
158 int i;
159 snode* n;
160
161 fprintf (stderr, "Q: ");
162 for (i = 1; i <= PQcnt; i++) {
163 n = pq[i];
164 fprintf (stderr, "%s(%d:%d) ",
165 n->index, N_IDX(n), N_VAL(n));
166 }
167 fprintf (stderr, "\n");
168}
169#else
170
171#ifndef FPQ_H
172#define FPQ_H
173
174void PQgen(int sz);
175void PQfree(void);
176void PQinit(void);
177void PQcheck (void);
178void PQupheap(int);
179int PQ_insert(snode* np);
180void PQdownheap (int k);
181snode* PQremove (void);
182void PQupdate (snode* n, int d);
183void PQprint (void);
184#endif
185#endif
186