← Back to branch summary

~ubuntu-branches/ubuntu/trusty/libmath-geometry-voronoi-perl/trusty

« back to all changes in this revision

Viewing changes to heap.c

  • Committer: Package Import Robot
  • Author(s): Florian Schlichting
  • Date: 2013-05-23 21:40:53 UTC
  • Revision ID: package-import@ubuntu.com-20130523214053-1reukv29881hn1o4
Tags: upstream-1.3
Import upstream version 1.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
heap.c
 
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, double 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
    }