Source code: com/port80/graph/dot/impl/GridHeap.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.util.Arrays;
8
9 import com.port80.util.Debug;
10 import com.port80.util.msg;
11 import com.port80.util.sprint;
12
13 /**
14 * A heap of Grid customized for AStar algorithm.
15 * The heap used Grid.heapIndex.
16 *
17 * @author chrisl
18 */
19 public class GridHeap {
20
21 ////////////////////////////////////////////////////////////////////////
22
23 private static final String NAME = "GridHeap";
24 private static boolean CHECK = Debug.isCheck();
25
26 private static int fMAXSIZE=0;
27
28 ////////////////////////////////////////////////////////////////////////
29
30 private int size;
31 private Grid[] heap;
32
33 ////////////////////////////////////////////////////////////////////////
34
35 public GridHeap() {
36 this(100);
37 }
38
39 public GridHeap(int n) {
40 heap = new Grid[n];
41 }
42
43 ////////////////////////////////////////////////////////////////////////
44
45 public int size() {
46 return size;
47 }
48
49 public Grid get(int i) {
50 if (i >= size)
51 msg.err("i>=size: size=" + size + ", i=" + i);
52 return heap[i + 1];
53 }
54
55 public Grid peek() {
56 return heap[1];
57 }
58
59 public void enqueue(Grid a) {
60 if (a.heapIndex > 0) {
61 requeue(a);
62 return;
63 }
64 if (false)
65 msg.println(NAME + ".enqueue(): " + a);
66 if (++size >= heap.length)
67 growTo(heap.length * 2 + 1);
68 int i = 1;
69 if (size > 1) {
70 for (i = size; i > 1 && heap[i / 2].lowerCostThan(a) < 0; i /= 2) {
71 heap[i] = heap[i / 2];
72 heap[i].heapIndex = i;
73 }
74 }
75 a.heapIndex = i;
76 heap[i]=a;
77 }
78
79 /**
80 * In current implementation, dequeue() is not used.
81 *
82 * @return the highest priority (lowest cost) item.
83 * @enter (existing item count >= 1) && (item != NULL)
84 * @exit item has been deleted.
85 */
86 public Grid dequeue() {
87 if (size == 0) {
88 msg.err("size==0");
89 return null;
90 }
91 Grid ret = heap[1]; // Save the root.
92 ret.heapIndex = 0;
93 heap[1] = heap[size]; // Put the last item in the root.
94 heap[1].heapIndex = 1;
95 --size;
96 moveDown(1); // Move the new root down if necessary.
97 return ret;
98 }
99
100 /**
101 * Reorder the given cell with value changed.
102 *
103 * @return The next heap index for the given cell.
104 * @enter (existing item count >= 1) && (item != NULL)
105 * @exit item moved to legal position.
106 */
107 public void requeue(Grid a) {
108 if (size == 0) {
109 msg.err("GridHeap.requeue(): size==0");
110 return;
111 }
112 int index = a.heapIndex;
113 if (index <= 0) {
114 msg.err("index<=0: index=" + index+"\n\t"+a);
115 return;
116 }
117 if (CHECK) {
118 if (index > size) {
119 msg.err("index>=size: size=" + size + ", index=" + index+"\n\t"+a);
120 return;
121 }
122 if (!heap[index].equals(a)) {
123 msg.err(
124 "Incorrect item at index: index="
125 + index
126 + ", a="
127 + a
128 + ", heap[index]="
129 + heap[index]);
130 return;
131 }
132 }
133 int i = index;
134 for (i = index; i > 1 && heap[i / 2].lowerCostThan(a) < 0; i /= 2) {
135 heap[i] = heap[i / 2];
136 heap[i].heapIndex = i;
137 }
138 heap[i] = a;
139 a.heapIndex = i;
140 moveDown(index); // Move the item down if necessary.
141 return;
142 }
143
144 public int getMaxSize() {
145 if(size>fMAXSIZE) fMAXSIZE=size;
146 return fMAXSIZE;
147 }
148
149 public void clear() {
150 if(size>fMAXSIZE) fMAXSIZE=size;
151 size = 0;
152 }
153
154 /**
155 * @return 0 if test passed, else the 1-based index at which test failed.
156 */
157 public int sanityCheck() {
158 if (size == 0)
159 return 0;
160 return sanityCheck(1);
161 }
162
163 private int sanityCheck(int index) {
164 int i = index * 2;
165 int ret;
166 if (i <= size) {
167 if (heap[i].lowerCostThan(heap[index]) > 0)
168 return index;
169 ret = sanityCheck(i);
170 if (ret != 0)
171 return ret;
172 }
173 if (i + 1 < size) {
174 if (heap[i + 1].lowerCostThan(heap[index]) > 0)
175 return index;
176 ret = sanityCheck(i + 1);
177 if (ret != 0)
178 return ret;
179 }
180 return 0;
181 }
182
183 public int printHeap(StringBuffer buf, int index, String indent) {
184 ++index;
185 if (index > size)
186 return 0;
187 int ret = 1;
188 buf.append(indent + heap[index].estTotal + "\n");
189 ret += printHeap(buf, index * 2 - 1, indent + " |");
190 ret += printHeap(buf, index * 2, indent + " |");
191 return ret;
192 }
193
194 ////////////////////////////////////////////////////////////////////////
195
196 private void moveDown(int k) {
197 int left = 2 * k;
198 if (left <= size) {
199 int right = 2 * k + 1;
200 if (right <= size && heap[right].lowerCostThan(heap[left]) > 0)
201 left = right;
202 if (heap[k].lowerCostThan(heap[left]) < 0) {
203 Grid a = heap[k];
204 heap[k] = heap[left];
205 heap[k].heapIndex = k;
206 heap[left] = a;
207 heap[left].heapIndex = left;
208 moveDown(left);
209 }
210 }
211 }
212 private void growTo(int n) {
213 Grid[] a = new Grid[n];
214 //NOTE: size has been incremented to ==heap.length.
215 System.arraycopy(heap, 0, a, 0, size);
216 heap = a;
217 }
218
219 ////////////////////////////////////////////////////////////////////////
220
221 }