Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 10 | reyssat | 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 | } |