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;
017:
018: import java.util.ArrayList;
019: import java.util.Arrays;
020: import java.util.Collection;
021: import java.util.Comparator;
022: import java.util.NoSuchElementException;
023: import java.util.Random;
024:
025: import junit.framework.Test;
026: import junit.framework.TestSuite;
027:
028: import org.apache.commons.collections.collection.AbstractTestCollection;
029: import org.apache.commons.collections.comparators.ComparableComparator;
030: import org.apache.commons.collections.comparators.ReverseComparator;
031:
032: /**
033: * Tests the BinaryHeap.
034: *
035: * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
036: *
037: * @author Michael A. Smith
038: */
039: public class TestBinaryHeap extends AbstractTestCollection {
040:
041: public static Test suite() {
042: return new TestSuite(TestBinaryHeap.class);
043: }
044:
045: public TestBinaryHeap(String testName) {
046: super (testName);
047: }
048:
049: //-----------------------------------------------------------------------
050: public void verify() {
051: super .verify();
052: BinaryHeap heap = (BinaryHeap) collection;
053:
054: Comparator c = heap.m_comparator;
055: if (c == null)
056: c = ComparatorUtils.naturalComparator();
057: if (!heap.m_isMinHeap)
058: c = ComparatorUtils.reversedComparator(c);
059:
060: Object[] tree = heap.m_elements;
061: for (int i = 1; i <= heap.m_size; i++) {
062: Object parent = tree[i];
063: if (i * 2 <= heap.m_size) {
064: assertTrue(
065: "Parent is less than or equal to its left child",
066: c.compare(parent, tree[i * 2]) <= 0);
067: }
068: if (i * 2 + 1 < heap.m_size) {
069: assertTrue(
070: "Parent is less than or equal to its right child",
071: c.compare(parent, tree[i * 2 + 1]) <= 0);
072: }
073: }
074: }
075:
076: //-----------------------------------------------------------------------
077: /**
078: * Overridden because UnboundedFifoBuffer isn't fail fast.
079: * @return false
080: */
081: public boolean isFailFastSupported() {
082: return false;
083: }
084:
085: //-----------------------------------------------------------------------
086: public Collection makeConfirmedCollection() {
087: return new ArrayList();
088: }
089:
090: public Collection makeConfirmedFullCollection() {
091: ArrayList list = new ArrayList();
092: list.addAll(Arrays.asList(getFullElements()));
093: return list;
094: }
095:
096: /**
097: * Return a new, empty {@link Object} to used for testing.
098: */
099: public Collection makeCollection() {
100: return new BinaryHeap();
101: }
102:
103: //-----------------------------------------------------------------------
104: public Object[] getFullElements() {
105: return getFullNonNullStringElements();
106: }
107:
108: public Object[] getOtherElements() {
109: return getOtherNonNullStringElements();
110: }
111:
112: //-----------------------------------------------------------------------
113: public void testBasicOps() {
114: BinaryHeap heap = new BinaryHeap();
115:
116: assertTrue("heap should be empty after create", heap.isEmpty());
117:
118: try {
119: heap.peek();
120: fail("NoSuchElementException should be thrown if peek is called before any elements are inserted");
121: } catch (NoSuchElementException e) {
122: // expected
123: }
124:
125: try {
126: heap.pop();
127: fail("NoSuchElementException should be thrown if pop is called before any elements are inserted");
128: } catch (NoSuchElementException e) {
129: // expected
130: }
131:
132: heap.insert("a");
133: heap.insert("c");
134: heap.insert("e");
135: heap.insert("b");
136: heap.insert("d");
137: heap.insert("n");
138: heap.insert("m");
139: heap.insert("l");
140: heap.insert("k");
141: heap.insert("j");
142: heap.insert("i");
143: heap.insert("h");
144: heap.insert("g");
145: heap.insert("f");
146:
147: assertTrue("heap should not be empty after inserts", !heap
148: .isEmpty());
149:
150: for (int i = 0; i < 14; i++) {
151: assertEquals(
152: "peek using default constructor should return minimum value in the binary heap",
153: String.valueOf((char) ('a' + i)), heap.peek());
154:
155: assertEquals(
156: "pop using default constructor should return minimum value in the binary heap",
157: String.valueOf((char) ('a' + i)), heap.pop());
158:
159: if (i + 1 < 14) {
160: assertTrue(
161: "heap should not be empty before all elements are popped",
162: !heap.isEmpty());
163: } else {
164: assertTrue(
165: "heap should be empty after all elements are popped",
166: heap.isEmpty());
167: }
168: }
169:
170: try {
171: heap.peek();
172: fail("NoSuchElementException should be thrown if peek is called after all elements are popped");
173: } catch (NoSuchElementException e) {
174: // expected
175: }
176:
177: try {
178: heap.pop();
179: fail("NoSuchElementException should be thrown if pop is called after all elements are popped");
180: } catch (NoSuchElementException e) {
181: // expected
182: }
183: }
184:
185: public void testBasicComparatorOps() {
186: BinaryHeap heap = new BinaryHeap(new ReverseComparator(
187: new ComparableComparator()));
188:
189: assertTrue("heap should be empty after create", heap.isEmpty());
190:
191: try {
192: heap.peek();
193: fail("NoSuchElementException should be thrown if peek is called before any elements are inserted");
194: } catch (NoSuchElementException e) {
195: // expected
196: }
197:
198: try {
199: heap.pop();
200: fail("NoSuchElementException should be thrown if pop is called before any elements are inserted");
201: } catch (NoSuchElementException e) {
202: // expected
203: }
204:
205: heap.insert("a");
206: heap.insert("c");
207: heap.insert("e");
208: heap.insert("b");
209: heap.insert("d");
210: heap.insert("n");
211: heap.insert("m");
212: heap.insert("l");
213: heap.insert("k");
214: heap.insert("j");
215: heap.insert("i");
216: heap.insert("h");
217: heap.insert("g");
218: heap.insert("f");
219:
220: assertTrue("heap should not be empty after inserts", !heap
221: .isEmpty());
222:
223: for (int i = 0; i < 14; i++) {
224:
225: // note: since we're using a comparator that reverses items, the
226: // "minimum" item is "n", and the "maximum" item is "a".
227:
228: assertEquals(
229: "peek using default constructor should return minimum value in the binary heap",
230: String.valueOf((char) ('n' - i)), heap.peek());
231:
232: assertEquals(
233: "pop using default constructor should return minimum value in the binary heap",
234: String.valueOf((char) ('n' - i)), heap.pop());
235:
236: if (i + 1 < 14) {
237: assertTrue(
238: "heap should not be empty before all elements are popped",
239: !heap.isEmpty());
240: } else {
241: assertTrue(
242: "heap should be empty after all elements are popped",
243: heap.isEmpty());
244: }
245: }
246:
247: try {
248: heap.peek();
249: fail("NoSuchElementException should be thrown if peek is called after all elements are popped");
250: } catch (NoSuchElementException e) {
251: // expected
252: }
253:
254: try {
255: heap.pop();
256: fail("NoSuchElementException should be thrown if pop is called after all elements are popped");
257: } catch (NoSuchElementException e) {
258: // expected
259: }
260: }
261:
262: /**
263: * Illustrates bad internal heap state reported in Bugzilla PR #235818.
264: */
265: public void testAddRemove() {
266: resetEmpty();
267: BinaryHeap heap = (BinaryHeap) collection;
268: heap.add(new Integer(0));
269: heap.add(new Integer(2));
270: heap.add(new Integer(4));
271: heap.add(new Integer(3));
272: heap.add(new Integer(8));
273: heap.add(new Integer(10));
274: heap.add(new Integer(12));
275: heap.add(new Integer(3));
276: confirmed.addAll(heap);
277: // System.out.println(heap);
278: Object obj = new Integer(10);
279: heap.remove(obj);
280: confirmed.remove(obj);
281: // System.out.println(heap);
282: verify();
283: }
284:
285: /**
286: * Generate heaps staring with Integers from 0 - heapSize - 1.
287: * Then perform random add / remove operations, checking
288: * heap order after modifications. Alternates minHeaps, maxHeaps.
289: *
290: * Based on code provided by Steve Phelps in PR #25818
291: *
292: */
293: public void testRandom() {
294: int iterations = 500;
295: int heapSize = 100;
296: int operations = 20;
297: Random randGenerator = new Random();
298: BinaryHeap h = null;
299: for (int i = 0; i < iterations; i++) {
300: if (i < iterations / 2) {
301: h = new BinaryHeap(true);
302: } else {
303: h = new BinaryHeap(false);
304: }
305: for (int r = 0; r < heapSize; r++) {
306: h.add(new Integer(randGenerator.nextInt(heapSize)));
307: }
308: for (int r = 0; r < operations; r++) {
309: h.remove(new Integer(r));
310: h.add(new Integer(randGenerator.nextInt(heapSize)));
311: }
312: checkOrder(h);
313: }
314: }
315:
316: /**
317: * Pops all elements from the heap and verifies that the elements come off
318: * in the correct order. NOTE: this method empties the heap.
319: */
320: protected void checkOrder(BinaryHeap h) {
321: Integer lastNum = null;
322: Integer num = null;
323: boolean fail = false;
324: while (!h.isEmpty()) {
325: num = (Integer) h.pop();
326: if (h.m_isMinHeap) {
327: assertTrue(lastNum == null
328: || num.intValue() >= lastNum.intValue());
329: } else { // max heap
330: assertTrue(lastNum == null
331: || num.intValue() <= lastNum.intValue());
332: }
333: lastNum = num;
334: num = null;
335: }
336: }
337:
338: /**
339: * Returns a string showing the contents of the heap formatted as a tree.
340: * Makes no attempt at padding levels or handling wrapping.
341: */
342: protected String showTree(BinaryHeap h) {
343: int count = 1;
344: StringBuffer buffer = new StringBuffer();
345: for (int offset = 1; count < h.size() + 1; offset *= 2) {
346: for (int i = offset; i < offset * 2; i++) {
347: if (i < h.m_elements.length && h.m_elements[i] != null)
348: buffer.append(h.m_elements[i] + " ");
349: count++;
350: }
351: buffer.append('\n');
352: }
353: return buffer.toString();
354: }
355:
356: }
|