|
1
16 package org.apache.commons.collections;
17
18 import java.util.ArrayList  ;
19 import java.util.Arrays ;
20 import java.util.Collection ;
21 import java.util.Comparator ;
22 import java.util.NoSuchElementException ;
23 import java.util.Random ;
24
25 import junit.framework.Test;
26 import junit.framework.TestSuite;
27
28 import org.apache.commons.collections.collection.AbstractTestCollection;
29 import org.apache.commons.collections.comparators.ComparableComparator;
30 import org.apache.commons.collections.comparators.ReverseComparator;
31
32
39 public class TestBinaryHeap extends AbstractTestCollection {
40
41 public static Test suite() {
42 return new TestSuite(TestBinaryHeap.class);
43 }
44
45 public TestBinaryHeap(String testName) {
46 super(testName);
47 }
48
49 public void verify() {
51 super.verify();
52 BinaryHeap heap = (BinaryHeap) collection;
53
54 Comparator c = heap.m_comparator;
55 if (c == null)
56 c = ComparatorUtils.naturalComparator();
57 if (!heap.m_isMinHeap)
58 c = ComparatorUtils.reversedComparator(c);
59
60 Object [] tree = heap.m_elements;
61 for (int i = 1; i <= heap.m_size; i++) {
62 Object parent = tree[i];
63 if (i * 2 <= heap.m_size) {
64 assertTrue("Parent is less than or equal to its left child", c.compare(parent, tree[i * 2]) <= 0);
65 }
66 if (i * 2 + 1 < heap.m_size) {
67 assertTrue("Parent is less than or equal to its right child", c.compare(parent, tree[i * 2 + 1]) <= 0);
68 }
69 }
70 }
71
72
77 public boolean isFailFastSupported() {
78 return false;
79 }
80
81 public Collection makeConfirmedCollection() {
83 return new ArrayList ();
84 }
85
86 public Collection makeConfirmedFullCollection() {
87 ArrayList list = new ArrayList ();
88 list.addAll(Arrays.asList(getFullElements()));
89 return list;
90 }
91
92
95 public Collection makeCollection() {
96 return new BinaryHeap();
97 }
98
99 public Object [] getFullElements() {
101 return getFullNonNullStringElements();
102 }
103
104 public Object [] getOtherElements() {
105 return getOtherNonNullStringElements();
106 }
107
108 public void testBasicOps() {
110 BinaryHeap heap = new BinaryHeap();
111
112 assertTrue("heap should be empty after create", heap.isEmpty());
113
114 try {
115 heap.peek();
116 fail("NoSuchElementException should be thrown if peek is called before any elements are inserted");
117 } catch (NoSuchElementException e) {
118 }
120
121 try {
122 heap.pop();
123 fail("NoSuchElementException should be thrown if pop is called before any elements are inserted");
124 } catch (NoSuchElementException e) {
125 }
127
128 heap.insert("a");
129 heap.insert("c");
130 heap.insert("e");
131 heap.insert("b");
132 heap.insert("d");
133 heap.insert("n");
134 heap.insert("m");
135 heap.insert("l");
136 heap.insert("k");
137 heap.insert("j");
138 heap.insert("i");
139 heap.insert("h");
140 heap.insert("g");
141 heap.insert("f");
142
143 assertTrue("heap should not be empty after inserts", !heap.isEmpty());
144
145 for (int i = 0; i < 14; i++) {
146 assertEquals(
147 "peek using default constructor should return minimum value in the binary heap",
148 String.valueOf((char) ('a' + i)),
149 heap.peek());
150
151 assertEquals(
152 "pop using default constructor should return minimum value in the binary heap",
153 String.valueOf((char) ('a' + i)),
154 heap.pop());
155
156 if (i + 1 < 14) {
157 assertTrue("heap should not be empty before all elements are popped", !heap.isEmpty());
158 } else {
159 assertTrue("heap should be empty after all elements are popped", heap.isEmpty());
160 }
161 }
162
163 try {
164 heap.peek();
165 fail("NoSuchElementException should be thrown if peek is called after all elements are popped");
166 } catch (NoSuchElementException e) {
167 }
169
170 try {
171 heap.pop();
172 fail("NoSuchElementException should be thrown if pop is called after all elements are popped");
173 } catch (NoSuchElementException e) {
174 }
176 }
177
178 public void testBasicComparatorOps() {
179 BinaryHeap heap = new BinaryHeap(new ReverseComparator(new ComparableComparator()));
180
181 assertTrue("heap should be empty after create", heap.isEmpty());
182
183 try {
184 heap.peek();
185 fail("NoSuchElementException should be thrown if peek is called before any elements are inserted");
186 } catch (NoSuchElementException e) {
187 }
189
190 try {
191 heap.pop();
192 fail("NoSuchElementException should be thrown if pop is called before any elements are inserted");
193 } catch (NoSuchElementException e) {
194 }
196
197 heap.insert("a");
198 heap.insert("c");
199 heap.insert("e");
200 heap.insert("b");
201 heap.insert("d");
202 heap.insert("n");
203 heap.insert("m");
204 heap.insert("l");
205 heap.insert("k");
206 heap.insert("j");
207 heap.insert("i");
208 heap.insert("h");
209 heap.insert("g");
210 heap.insert("f");
211
212 assertTrue("heap should not be empty after inserts", !heap.isEmpty());
213
214 for (int i = 0; i < 14; i++) {
215
216
219 assertEquals(
220 "peek using default constructor should return minimum value in the binary heap",
221 String.valueOf((char) ('n' - i)),
222 heap.peek());
223
224 assertEquals(
225 "pop using default constructor should return minimum value in the binary heap",
226 String.valueOf((char) ('n' - i)),
227 heap.pop());
228
229 if (i + 1 < 14) {
230 assertTrue("heap should not be empty before all elements are popped", !heap.isEmpty());
231 } else {
232 assertTrue("heap should be empty after all elements are popped", heap.isEmpty());
233 }
234 }
235
236 try {
237 heap.peek();
238 fail("NoSuchElementException should be thrown if peek is called after all elements are popped");
239 } catch (NoSuchElementException e) {
240 }
242
243 try {
244 heap.pop();
245 fail("NoSuchElementException should be thrown if pop is called after all elements are popped");
246 } catch (NoSuchElementException e) {
247 }
249 }
250
251
254 public void testAddRemove() {
255 resetEmpty();
256 BinaryHeap heap = (BinaryHeap) collection;
257 heap.add(new Integer (0));
258 heap.add(new Integer (2));
259 heap.add(new Integer (4));
260 heap.add(new Integer (3));
261 heap.add(new Integer (8));
262 heap.add(new Integer (10));
263 heap.add(new Integer (12));
264 heap.add(new Integer (3));
265 confirmed.addAll(heap);
266 Object obj = new Integer (10);
268 heap.remove(obj);
269 confirmed.remove(obj);
270 verify();
272 }
273
274
282 public void testRandom() {
283 int iterations = 500;
284 int heapSize = 100;
285 int operations = 20;
286 Random randGenerator = new Random ();
287 BinaryHeap h = null;
288 for(int i=0; i < iterations; i++) {
289 if (i < iterations / 2) {
290 h = new BinaryHeap(true);
291 } else {
292 h = new BinaryHeap(false);
293 }
294 for(int r = 0; r < heapSize; r++) {
295 h.add( new Integer ( randGenerator.nextInt(heapSize)) );
296 }
297 for( int r = 0; r < operations; r++ ) {
298 h.remove(new Integer (r));
299 h.add(new Integer (randGenerator.nextInt(heapSize)));
300 }
301 checkOrder(h);
302 }
303 }
304
305
309 protected void checkOrder(BinaryHeap h) {
310 Integer lastNum = null;
311 Integer num = null;
312 boolean fail = false;
313 while (!h.isEmpty()) {
314 num = (Integer ) h.pop();
315 if (h.m_isMinHeap) {
316 assertTrue(lastNum == null || num.intValue() >= lastNum.intValue());
317 } else { assertTrue(lastNum == null || num.intValue() <= lastNum.intValue());
319 }
320 lastNum = num;
321 num = null;
322 }
323 }
324
325
329 protected String showTree(BinaryHeap h) {
330 int count = 1;
331 StringBuffer buffer = new StringBuffer ();
332 for (int offset = 1; count < h.size() + 1; offset *= 2) {
333 for (int i = offset; i < offset * 2; i++) {
334 if (i < h.m_elements.length && h.m_elements[i] != null)
335 buffer.append(h.m_elements[i] + " ");
336 count++;
337 }
338 buffer.append('\n');
339 }
340 return buffer.toString();
341 }
342
343 }
344 |
Popular Tags |
Java API By Example, From Geeks To Geeks.