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