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
15#include "render.h"
16#include <stdio.h>
17
18#include "mem.h"
19#include "hedges.h"
20#include "heap.h"
21
22
23static Halfedge *PQhash;
24static int PQhashsize;
25static int PQcount;
26static int PQmin;
27
28static int PQbucket(Halfedge * he)
29{
30 int bucket;
31 double b;
32
33 b = (he->ystar - ymin) / deltay * PQhashsize;
34 if (b < 0)
35 bucket = 0;
36 else if (b >= PQhashsize)
37 bucket = PQhashsize - 1;
38 else
39 bucket = b;
40 if (bucket < PQmin)
41 PQmin = bucket;
42 return (bucket);
43}
44
45void PQinsert(Halfedge * he, Site * v, double offset)
46{
47 Halfedge *last, *next;
48
49 he->vertex = v;
50 ref(v);
51 he->ystar = v->coord.y + offset;
52 last = &PQhash[PQbucket(he)];
53 while ((next = last->PQnext) != (struct Halfedge *) NULL &&
54 (he->ystar > next->ystar ||
55 (he->ystar == next->ystar
56 && v->coord.x > next->vertex->coord.x))) {
57 last = next;
58 }
59 he->PQnext = last->PQnext;
60 last->PQnext = he;
61 PQcount += 1;
62}
63
64void PQdelete(Halfedge * he)
65{
66 Halfedge *last;
67
68 if (he->vertex != (Site *) NULL) {
69 last = &PQhash[PQbucket(he)];
70 while (last->PQnext != he)
71 last = last->PQnext;
72 last->PQnext = he->PQnext;
73 PQcount -= 1;
74 deref(he->vertex);
75 he->vertex = (Site *) NULL;
76 }
77}
78
79
80int PQempty(void)
81{
82 return (PQcount == 0);
83}
84
85
86Point PQ_min(void)
87{
88 Point answer;
89
90 while (PQhash[PQmin].PQnext == (struct Halfedge *) NULL) {
91 PQmin += 1;
92 }
93 answer.x = PQhash[PQmin].PQnext->vertex->coord.x;
94 answer.y = PQhash[PQmin].PQnext->ystar;
95 return (answer);
96}
97
98Halfedge *PQextractmin(void)
99{
100 Halfedge *curr;
101
102 curr = PQhash[PQmin].PQnext;
103 PQhash[PQmin].PQnext = curr->PQnext;
104 PQcount -= 1;
105 return (curr);
106}
107
108void PQcleanup(void)
109{
110 free(PQhash);
111 PQhash = NULL;
112}
113
114void PQinitialize(void)
115{
116 int i;
117
118 PQcount = 0;
119 PQmin = 0;
120 PQhashsize = 4 * sqrt_nsites;
121 if (PQhash == NULL)
122 PQhash = N_GNEW(PQhashsize, Halfedge);
123 for (i = 0; i < PQhashsize; i += 1)
124 PQhash[i].PQnext = (Halfedge *) NULL;
125}
126
127static void PQdumphe(Halfedge * p)
128{
129 printf(" [%p] %p %p %d %d %d %d %f\n",
130 p, p->ELleft, p->ELright, p->ELedge->edgenbr,
131 p->ELrefcnt, p->ELpm, (p->vertex ? p->vertex->sitenbr : -1),
132 p->ystar);
133}
134
135void PQdump(void)
136{
137 int i;
138 Halfedge *p;
139
140 for (i = 0; i < PQhashsize; i += 1) {
141 printf("[%d]\n", i);
142 p = PQhash[i].PQnext;
143 while (p != NULL) {
144 PQdumphe(p);
145 p = p->PQnext;
146 }
147 }
148
149}
150