[666] | 1 | |
---|
| 2 | /*** HEAP.C ***/ |
---|
| 3 | |
---|
| 4 | |
---|
| 5 | #include "vdefs.h" |
---|
| 6 | |
---|
| 7 | int PQmin, PQcount, PQhashsize ; |
---|
| 8 | Halfedge * PQhash ; |
---|
| 9 | |
---|
| 10 | void |
---|
| 11 | PQinsert(Halfedge * he, Site * v, float offset) |
---|
| 12 | { |
---|
| 13 | Halfedge * last, * next ; |
---|
| 14 | |
---|
| 15 | he->vertex = v ; |
---|
| 16 | ref(v) ; |
---|
| 17 | he->ystar = v->coord.y + offset ; |
---|
| 18 | last = &PQhash[ PQbucket(he)] ; |
---|
| 19 | while ((next = last->PQnext) != (Halfedge *)NULL && |
---|
| 20 | (he->ystar > next->ystar || |
---|
| 21 | (he->ystar == next->ystar && |
---|
| 22 | v->coord.x > next->vertex->coord.x))) |
---|
| 23 | { |
---|
| 24 | last = next ; |
---|
| 25 | } |
---|
| 26 | he->PQnext = last->PQnext ; |
---|
| 27 | last->PQnext = he ; |
---|
| 28 | PQcount++ ; |
---|
| 29 | } |
---|
| 30 | |
---|
| 31 | void |
---|
| 32 | PQdelete(Halfedge * he) |
---|
| 33 | { |
---|
| 34 | Halfedge * last; |
---|
| 35 | |
---|
| 36 | if(he -> vertex != (Site *) NULL) |
---|
| 37 | { |
---|
| 38 | last = &PQhash[PQbucket(he)] ; |
---|
| 39 | while (last -> PQnext != he) |
---|
| 40 | { |
---|
| 41 | last = last->PQnext ; |
---|
| 42 | } |
---|
| 43 | last->PQnext = he->PQnext; |
---|
| 44 | PQcount-- ; |
---|
| 45 | deref(he->vertex) ; |
---|
| 46 | he->vertex = (Site *)NULL ; |
---|
| 47 | } |
---|
| 48 | } |
---|
| 49 | |
---|
| 50 | int |
---|
| 51 | PQbucket(Halfedge * he) |
---|
| 52 | { |
---|
| 53 | int bucket ; |
---|
| 54 | |
---|
| 55 | |
---|
| 56 | if (he->ystar < ymin) bucket = 0; |
---|
| 57 | else if (he->ystar >= ymax) bucket = PQhashsize-1; |
---|
| 58 | else bucket = (he->ystar - ymin)/deltay * PQhashsize; |
---|
| 59 | if (bucket < 0) |
---|
| 60 | { |
---|
| 61 | bucket = 0 ; |
---|
| 62 | } |
---|
| 63 | if (bucket >= PQhashsize) |
---|
| 64 | { |
---|
| 65 | bucket = PQhashsize-1 ; |
---|
| 66 | } |
---|
| 67 | if (bucket < PQmin) |
---|
| 68 | { |
---|
| 69 | PQmin = bucket ; |
---|
| 70 | } |
---|
| 71 | return (bucket); |
---|
| 72 | } |
---|
| 73 | |
---|
| 74 | int |
---|
| 75 | PQempty(void) |
---|
| 76 | { |
---|
| 77 | return (PQcount == 0) ; |
---|
| 78 | } |
---|
| 79 | |
---|
| 80 | |
---|
| 81 | Point |
---|
| 82 | PQ_min(void) |
---|
| 83 | { |
---|
| 84 | Point answer ; |
---|
| 85 | |
---|
| 86 | while (PQhash[PQmin].PQnext == (Halfedge *)NULL) |
---|
| 87 | { |
---|
| 88 | ++PQmin ; |
---|
| 89 | } |
---|
| 90 | answer.x = PQhash[PQmin].PQnext->vertex->coord.x ; |
---|
| 91 | answer.y = PQhash[PQmin].PQnext->ystar ; |
---|
| 92 | return (answer) ; |
---|
| 93 | } |
---|
| 94 | |
---|
| 95 | Halfedge * |
---|
| 96 | PQextractmin(void) |
---|
| 97 | { |
---|
| 98 | Halfedge * curr ; |
---|
| 99 | |
---|
| 100 | curr = PQhash[PQmin].PQnext ; |
---|
| 101 | PQhash[PQmin].PQnext = curr->PQnext ; |
---|
| 102 | PQcount-- ; |
---|
| 103 | return (curr) ; |
---|
| 104 | } |
---|
| 105 | |
---|
| 106 | void |
---|
| 107 | PQinitialize(void) |
---|
| 108 | { |
---|
| 109 | int i ; |
---|
| 110 | |
---|
| 111 | PQcount = PQmin = 0 ; |
---|
| 112 | PQhashsize = 4 * sqrt_nsites ; |
---|
| 113 | PQhash = (Halfedge *)myalloc(PQhashsize * sizeof *PQhash) ; |
---|
| 114 | for (i = 0 ; i < PQhashsize; i++) |
---|
| 115 | { |
---|
| 116 | PQhash[i].PQnext = (Halfedge *)NULL ; |
---|
| 117 | } |
---|
| 118 | } |
---|