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#include "LinkedList.h"
15#include "PriorityQueue.h"
16#include "memory.h"
17#include "logic.h"
18#include "assert.h"
19#include "arith.h"
20
21#define MALLOC gmalloc
22#define REALLOC grealloc
23#define FREE free
24#define MEMCPY memcpy
25
26
27PriorityQueue PriorityQueue_new(int n, int ngain){
28 PriorityQueue q;
29 int i;
30 q = N_GNEW(1,struct PriorityQueue_struct);
31 q->count = 0;
32 q->n = n;
33 q->ngain = ngain;
34 q->gain_max = -1;/* no entries yet */
35 q->buckets = N_GNEW((ngain+1),DoubleLinkedList);
36 for (i = 0; i < ngain+1; i++) (q->buckets)[i] = NULL;
37
38 q->where = N_GNEW((n+1),DoubleLinkedList);
39 for (i = 0; i < n+1; i++) (q->where)[i] = NULL;
40
41 q->gain = N_GNEW((n+1),int);
42 for (i = 0; i < n+1; i++) (q->gain)[i] = -999;
43 return q;
44
45}
46
47void PriorityQueue_delete(PriorityQueue q){
48 int i;
49
50 if (q){
51 if (q->buckets){
52 for (i = 0; i < q->ngain+1; i++) DoubleLinkedList_delete((q->buckets)[i], free);
53 FREE(q->buckets);
54 }
55
56 if (q->where){
57 FREE(q->where);
58 }
59
60 FREE(q->gain);
61 FREE(q);
62 }
63}
64
65PriorityQueue PriorityQueue_push(PriorityQueue q, int i, int gain){
66 DoubleLinkedList l;
67 int *data, gainold;
68
69 assert(q);
70 assert(gain <= q->ngain);
71
72
73 if (!(q->where)[i]){
74 /* this entry is no in the queue yet, so this is a new addition */
75
76 (q->count)++;
77 if (gain > q->gain_max) q->gain_max = gain;
78 q->gain[i] = gain;
79
80 data = N_GNEW(1,int);
81 data[0] = i;
82 if ((l = (q->buckets)[gain])){
83 (q->buckets)[gain] = (q->where)[i] = DoubleLinkedList_prepend(l, data);
84 } else {
85 (q->buckets)[gain] = (q->where)[i] = DoubleLinkedList_new(data);
86 }
87
88 } else {
89 /* update gain for an exisiting entry */
90 l = q->where[i];
91 gainold = q->gain[i];
92 q->where[i] = NULL;
93 (q->count)--;
94 DoubleLinkedList_delete_element(l, free, &((q->buckets)[gainold]));
95 return PriorityQueue_push(q, i, gain);
96 }
97 return q;
98}
99
100int PriorityQueue_pop(PriorityQueue q, int *i, int *gain){
101 int gain_max;
102 DoubleLinkedList l;
103 int *data;
104
105 if (!q || q->count <= 0) return 0;
106 *gain = gain_max = q->gain_max;
107 (q->count)--;
108 l = (q->buckets)[gain_max];
109 data = (int*) DoubleLinkedList_get_data(l);
110 *i = data[0];
111
112 DoubleLinkedList_delete_element(l, free, &((q->buckets)[gain_max]));
113 if (!(q->buckets)[gain_max]){/* the bin that contain the best gain is empty now after poping */
114 while (gain_max >= 0 && !(q->buckets)[gain_max]) gain_max--;
115 q->gain_max = gain_max;
116 }
117 q->where[*i] = NULL;
118 q->gain[*i] = -999;
119 return 1;
120}
121
122
123
124
125int PriorityQueue_get_gain(PriorityQueue q, int i){
126 return q->gain[i];
127}
128
129int PriorityQueue_remove(PriorityQueue q, int i){
130 /* remove an entry from the queue. If error, return 0. */
131 int gain, gain_max;
132 DoubleLinkedList l;
133
134 if (!q || q->count <= 0) return 0;
135 gain = q->gain[i];
136 (q->count)--;
137 l = (q->where)[i];
138
139 DoubleLinkedList_delete_element(l, free, &((q->buckets)[gain]));
140
141 if (gain == (gain_max = q->gain_max) && !(q->buckets)[gain_max]){/* the bin that contain the best gain is empty now after poping */
142 while (gain_max >= 0 && !(q->buckets)[gain_max]) gain_max--;
143 q->gain_max = gain_max;
144 }
145 q->where[i] = NULL;
146 q->gain[i] = -999;
147 return 1;
148}
149
150/*
151
152main(){
153 int i, gain;
154
155
156 PriorityQueue q;
157 q = PriorityQueue_new(10,100);
158 PriorityQueue_push(q, 3, 1);
159 PriorityQueue_push(q, 2, 2);
160 PriorityQueue_push(q, 4, 2);
161 PriorityQueue_push(q, 5, 2);
162 PriorityQueue_push(q, 1, 100);
163 PriorityQueue_push(q, 2, 1);
164 while (PriorityQueue_pop(q, &i, &gain)){
165 printf("i = %d gain = %d\n", i, gain);
166 }
167
168 printf("=========\n");
169 PriorityQueue_push(q, 3, 1);
170 PriorityQueue_push(q, 2, 2);
171 PriorityQueue_push(q, 4, 2);
172 PriorityQueue_push(q, 5, 2);
173 PriorityQueue_push(q, 1, 100);
174 PriorityQueue_push(q, 2, 1);
175 PriorityQueue_push(q, 2, 100);
176 while (PriorityQueue_pop(q, &i, &gain)){
177 printf("i = %d gain = %d\n", i, gain);
178 }
179
180
181 printf("====after removing 3 and 2 =====\n");
182 PriorityQueue_push(q, 3, 1);
183 PriorityQueue_push(q, 2, 2);
184 PriorityQueue_push(q, 4, 2);
185 PriorityQueue_push(q, 5, 2);
186 PriorityQueue_push(q, 1, 100);
187 PriorityQueue_push(q, 2, 1);
188 PriorityQueue_push(q, 2, 100);
189 PriorityQueue_remove(q, 3);
190 PriorityQueue_remove(q, 2);
191 while (PriorityQueue_pop(q, &i, &gain)){
192 printf("i = %d gain = %d\n", i, gain);
193 }
194 PriorityQueue_delete(q);
195
196}
197
198*/
199