001: /*
002: * Copyright 2001-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.buffer;
017:
018: import java.io.IOException;
019: import java.util.ArrayList;
020: import java.util.Arrays;
021: import java.util.Collection;
022: import java.util.Comparator;
023: import java.util.Iterator;
024: import java.util.Random;
025:
026: import junit.framework.Test;
027: import junit.framework.TestSuite;
028:
029: import org.apache.commons.collections.Buffer;
030: import org.apache.commons.collections.BufferUnderflowException;
031: import org.apache.commons.collections.ComparatorUtils;
032: import org.apache.commons.collections.collection.AbstractTestCollection;
033: import org.apache.commons.collections.comparators.ComparableComparator;
034: import org.apache.commons.collections.comparators.ReverseComparator;
035:
036: /**
037: * Tests the PriorityBuffer.
038: *
039: * @version $Revision: 307292 $ $Date: 2005-10-08 13:49:53 +0100 (Sat, 08 Oct 2005) $
040: *
041: * @author Michael A. Smith
042: * @author Steve Phelps
043: */
044: public class TestPriorityBuffer extends AbstractTestCollection {
045:
046: public static void main(String[] args) {
047: junit.textui.TestRunner.run(suite());
048: }
049:
050: public static Test suite() {
051: return new TestSuite(TestPriorityBuffer.class);
052: }
053:
054: public TestPriorityBuffer(String testName) {
055: super (testName);
056: }
057:
058: //-----------------------------------------------------------------------
059: public void verify() {
060: super .verify();
061: PriorityBuffer heap = (PriorityBuffer) collection;
062:
063: Comparator c = heap.comparator;
064: if (c == null) {
065: c = ComparatorUtils.naturalComparator();
066: }
067: if (!heap.ascendingOrder) {
068: c = ComparatorUtils.reversedComparator(c);
069: }
070:
071: Object[] tree = heap.elements;
072: for (int i = 1; i <= heap.size; i++) {
073: Object parent = tree[i];
074: if (i * 2 <= heap.size) {
075: assertTrue(
076: "Parent is less than or equal to its left child",
077: c.compare(parent, tree[i * 2]) <= 0);
078: }
079: if (i * 2 + 1 < heap.size) {
080: assertTrue(
081: "Parent is less than or equal to its right child",
082: c.compare(parent, tree[i * 2 + 1]) <= 0);
083: }
084: }
085: }
086:
087: //-----------------------------------------------------------------------
088: /**
089: * Overridden because BinaryBuffer isn't fail fast.
090: * @return false
091: */
092: public boolean isFailFastSupported() {
093: return false;
094: }
095:
096: //-----------------------------------------------------------------------
097: public Collection makeConfirmedCollection() {
098: return new ArrayList();
099: }
100:
101: public Collection makeConfirmedFullCollection() {
102: ArrayList list = new ArrayList();
103: list.addAll(Arrays.asList(getFullElements()));
104: return list;
105: }
106:
107: /**
108: * Return a new, empty {@link Object} to used for testing.
109: */
110: public Collection makeCollection() {
111: return new PriorityBuffer();
112: }
113:
114: //-----------------------------------------------------------------------
115: public Object[] getFullElements() {
116: return getFullNonNullStringElements();
117: }
118:
119: public Object[] getOtherElements() {
120: return getOtherNonNullStringElements();
121: }
122:
123: //-----------------------------------------------------------------------
124: public void testBufferEmpty() {
125: resetEmpty();
126: Buffer buffer = (Buffer) collection;
127:
128: assertEquals(0, buffer.size());
129: assertEquals(true, buffer.isEmpty());
130: try {
131: buffer.get();
132: fail();
133: } catch (BufferUnderflowException ex) {
134: }
135:
136: try {
137: buffer.remove();
138: fail();
139: } catch (BufferUnderflowException ex) {
140: }
141: }
142:
143: public void testBasicOps() {
144: PriorityBuffer heap = new PriorityBuffer();
145:
146: heap.add("a");
147: heap.add("c");
148: heap.add("e");
149: heap.add("b");
150: heap.add("d");
151: heap.add("n");
152: heap.add("m");
153: heap.add("l");
154: heap.add("k");
155: heap.add("j");
156: heap.add("i");
157: heap.add("h");
158: heap.add("g");
159: heap.add("f");
160:
161: assertTrue("heap should not be empty after adds", !heap
162: .isEmpty());
163:
164: for (int i = 0; i < 14; i++) {
165: assertEquals(
166: "get using default constructor should return minimum value in the binary heap",
167: String.valueOf((char) ('a' + i)), heap.get());
168:
169: assertEquals(
170: "remove using default constructor should return minimum value in the binary heap",
171: String.valueOf((char) ('a' + i)), heap.remove());
172:
173: if (i + 1 < 14) {
174: assertTrue(
175: "heap should not be empty before all elements are removed",
176: !heap.isEmpty());
177: } else {
178: assertTrue(
179: "heap should be empty after all elements are removed",
180: heap.isEmpty());
181: }
182: }
183:
184: try {
185: heap.get();
186: fail("NoSuchElementException should be thrown if get is called after all elements are removed");
187: } catch (BufferUnderflowException ex) {
188: }
189:
190: try {
191: heap.remove();
192: fail("NoSuchElementException should be thrown if remove is called after all elements are removed");
193: } catch (BufferUnderflowException ex) {
194: }
195: }
196:
197: public void testBasicComparatorOps() {
198: PriorityBuffer heap = new PriorityBuffer(new ReverseComparator(
199: new ComparableComparator()));
200:
201: assertTrue("heap should be empty after create", heap.isEmpty());
202:
203: try {
204: heap.get();
205: fail("NoSuchElementException should be thrown if get is called before any elements are added");
206: } catch (BufferUnderflowException ex) {
207: }
208:
209: try {
210: heap.remove();
211: fail("NoSuchElementException should be thrown if remove is called before any elements are added");
212: } catch (BufferUnderflowException ex) {
213: }
214:
215: heap.add("a");
216: heap.add("c");
217: heap.add("e");
218: heap.add("b");
219: heap.add("d");
220: heap.add("n");
221: heap.add("m");
222: heap.add("l");
223: heap.add("k");
224: heap.add("j");
225: heap.add("i");
226: heap.add("h");
227: heap.add("g");
228: heap.add("f");
229:
230: assertTrue("heap should not be empty after adds", !heap
231: .isEmpty());
232:
233: for (int i = 0; i < 14; i++) {
234:
235: // note: since we're using a comparator that reverses items, the
236: // "minimum" item is "n", and the "maximum" item is "a".
237:
238: assertEquals(
239: "get using default constructor should return minimum value in the binary heap",
240: String.valueOf((char) ('n' - i)), heap.get());
241:
242: assertEquals(
243: "remove using default constructor should return minimum value in the binary heap",
244: String.valueOf((char) ('n' - i)), heap.remove());
245:
246: if (i + 1 < 14) {
247: assertTrue(
248: "heap should not be empty before all elements are removed",
249: !heap.isEmpty());
250: } else {
251: assertTrue(
252: "heap should be empty after all elements are removed",
253: heap.isEmpty());
254: }
255: }
256:
257: try {
258: heap.get();
259: fail("NoSuchElementException should be thrown if get is called after all elements are removed");
260: } catch (BufferUnderflowException ex) {
261: }
262:
263: try {
264: heap.remove();
265: fail("NoSuchElementException should be thrown if remove is called after all elements are removed");
266: } catch (BufferUnderflowException ex) {
267: }
268: }
269:
270: /**
271: * Illustrates bad internal heap state reported in Bugzilla PR #235818.
272: */
273: public void testAddRemove() {
274: resetEmpty();
275: PriorityBuffer heap = (PriorityBuffer) collection;
276: heap.add(new Integer(0));
277: heap.add(new Integer(2));
278: heap.add(new Integer(4));
279: heap.add(new Integer(3));
280: heap.add(new Integer(8));
281: heap.add(new Integer(10));
282: heap.add(new Integer(12));
283: heap.add(new Integer(3));
284: confirmed.addAll(heap);
285: // System.out.println(heap);
286: Object obj = new Integer(10);
287: heap.remove(obj);
288: confirmed.remove(obj);
289: // System.out.println(heap);
290: verify();
291: }
292:
293: /**
294: * Generate heaps staring with Integers from 0 - heapSize - 1.
295: * Then perform random add / remove operations, checking
296: * heap order after modifications. Alternates minHeaps, maxHeaps.
297: *
298: * Based on code provided by Steve Phelps in PR #25818
299: *
300: */
301: public void testRandom() {
302: int iterations = 500;
303: int heapSize = 100;
304: int operations = 20;
305: Random randGenerator = new Random();
306: PriorityBuffer h = null;
307: for (int i = 0; i < iterations; i++) {
308: if (i < iterations / 2) {
309: h = new PriorityBuffer(true);
310: } else {
311: h = new PriorityBuffer(false);
312: }
313: for (int r = 0; r < heapSize; r++) {
314: h.add(new Integer(randGenerator.nextInt(heapSize)));
315: }
316: for (int r = 0; r < operations; r++) {
317: h.remove(new Integer(r));
318: h.add(new Integer(randGenerator.nextInt(heapSize)));
319: }
320: checkOrder(h);
321: }
322: }
323:
324: /**
325: * Pops all elements from the heap and verifies that the elements come off
326: * in the correct order. NOTE: this method empties the heap.
327: */
328: protected void checkOrder(PriorityBuffer h) {
329: Integer lastNum = null;
330: Integer num = null;
331: while (!h.isEmpty()) {
332: num = (Integer) h.remove();
333: if (h.ascendingOrder) {
334: assertTrue(lastNum == null
335: || num.intValue() >= lastNum.intValue());
336: } else { // max heap
337: assertTrue(lastNum == null
338: || num.intValue() <= lastNum.intValue());
339: }
340: lastNum = num;
341: num = null;
342: }
343: }
344:
345: /**
346: * Returns a string showing the contents of the heap formatted as a tree.
347: * Makes no attempt at padding levels or handling wrapping.
348: */
349: protected String showTree(PriorityBuffer h) {
350: int count = 1;
351: StringBuffer buffer = new StringBuffer();
352: for (int offset = 1; count < h.size() + 1; offset *= 2) {
353: for (int i = offset; i < offset * 2; i++) {
354: if (i < h.elements.length && h.elements[i] != null)
355: buffer.append(h.elements[i] + " ");
356: count++;
357: }
358: buffer.append('\n');
359: }
360: return buffer.toString();
361: }
362:
363: /**
364: * Generates 500 randomly initialized heaps of size 100
365: * and tests that after serializing and restoring them to a byte array
366: * that the following conditions hold:
367: *
368: * - the size of the restored heap is the same
369: * as the size of the orignal heap
370: *
371: * - all elements in the original heap are present in the restored heap
372: *
373: * - the heap order of the restored heap is intact as
374: * verified by checkOrder()
375: */
376: public void testSerialization() {
377: int iterations = 500;
378: int heapSize = 100;
379: PriorityBuffer h;
380: Random randGenerator = new Random();
381: for (int i = 0; i < iterations; i++) {
382: if (i < iterations / 2) {
383: h = new PriorityBuffer(true);
384: } else {
385: h = new PriorityBuffer(false);
386: }
387: for (int r = 0; r < heapSize; r++) {
388: h.add(new Integer(randGenerator.nextInt(heapSize)));
389: }
390: assertTrue(h.size() == heapSize);
391: PriorityBuffer h1 = serializeAndRestore(h);
392: assertTrue(h1.size() == heapSize);
393: Iterator hit = h.iterator();
394: while (hit.hasNext()) {
395: Integer n = (Integer) hit.next();
396: assertTrue(h1.contains(n));
397: }
398: checkOrder(h1);
399: }
400: }
401:
402: public PriorityBuffer serializeAndRestore(PriorityBuffer h) {
403: PriorityBuffer h1 = null;
404: try {
405: byte[] objekt = writeExternalFormToBytes(h);
406: h1 = (PriorityBuffer) readExternalFormFromBytes(objekt);
407: } catch (IOException e) {
408: e.printStackTrace();
409: fail(e.toString());
410: } catch (ClassNotFoundException e) {
411: e.printStackTrace();
412: fail(e.toString());
413: }
414: return h1;
415: }
416:
417: public String getCompatibilityVersion() {
418: return "3.2";
419: }
420:
421: // public void testCreate() throws Exception {
422: // resetEmpty();
423: // writeExternalFormToDisk((java.io.Serializable) collection, "C:/commons/collections/data/test/PriorityBuffer.emptyCollection.version3.2.obj");
424: // resetFull();
425: // writeExternalFormToDisk((java.io.Serializable) collection, "C:/commons/collections/data/test/PriorityBuffer.fullCollection.version3.2.obj");
426: // }
427:
428: }
|