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 | } |
---|