DO NOT REPLY TO THIS EMAIL, BUT PLEASE POST YOUR BUG RELATED COMMENTS THROUGH THE WEB INTERFACE AVAILABLE AT <http://nagoya.apache.org/bugzilla/show_bug.cgi?id=25818>. ANY REPLY MADE TO THIS MESSAGE WILL NOT BE COLLECTED AND INSERTED IN THE BUG DATABASE.
http://nagoya.apache.org/bugzilla/show_bug.cgi?id=25818 BinaryHeap.remove(Object) seems to break heap order Summary: BinaryHeap.remove(Object) seems to break heap order Product: Commons Version: Nightly Builds Platform: PC OS/Version: Linux Status: NEW Severity: Major Priority: Other Component: Collections AssignedTo: [EMAIL PROTECTED] ReportedBy: [EMAIL PROTECTED] I am currently attempting to migrate from my own implementation of a BinaryHeap to the implementation in org.apache.commons.collections.BinaryHeap. I have some existing unit tests for my implementation which fail when I run them on the commons BinaryHeap. Below is source-code for the JUnit test which fails. The test 'testRandom' is the test that fails. This test creates heaps initialised with 100 randomly generated Integers and proceeds to add and remove random elements from these heaps and then checks the heap order. Some of the elements that are removed may not exist in the heap. Heap order is checked by disassembling the heap using BinaryHeap.pop() and ensuring that subsequent elements are >= earlier elements. The problem appears to be related to the BinaryHeap.remove(Object) method-- if this is commented out the test succeeds. It may be the case that the problem occurs when non-existant elements are removed, but I have not attempted to verify this. --------- BinaryHeapTest.java --------- /* * JASA Java Auction Simulator API * Copyright (C) 2001-2003 Steve Phelps * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of * the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * See the GNU General Public License for more details. */ package test.uk.ac.liv.util; import test.uk.ac.liv.PRNGTestSeeds; import junit.framework.*; //import uk.ac.liv.util.*; import org.apache.commons.collections.BinaryHeap; import java.util.Random; import java.util.Iterator; import java.util.LinkedList; public class BinaryHeapTest extends TestCase { BinaryHeap h1; public BinaryHeapTest( String name ) { super(name); } public void setUp() { h1 = new BinaryHeap(); h1.insert(new Integer(1)); h1.insert(new Integer(3)); h1.insert(new Integer(9)); h1.insert(new Integer(3)); h1.insert(new Integer(5)); h1.insert(new Integer(7)); } public void test() { System.out.println("h1 = " + h1); assertTrue( h1.contains(new Integer(3)) ); assertTrue( h1.contains(new Integer(9)) ); assertTrue( h1.contains(new Integer(1)) ); assertTrue( h1.contains(new Integer(5)) ); assertTrue( !h1.contains(new Integer(10)) ); assertTrue( !h1.contains(new Integer(-1)) ); Object x = h1.pop(); System.out.println("h1 after removing first = " + h1); checkOrder(h1); assertTrue( ((Integer) x).equals(new Integer(1))); assertTrue( !h1.contains(new Integer(1)) ); assertTrue( h1.contains(new Integer(3)) ); assertTrue( h1.contains(new Integer(9)) ); assertTrue( h1.contains(new Integer(5)) ); h1.remove(new Integer(9)); System.out.println("h1 after removing 9 = " + h1); assertTrue( h1.contains(new Integer(3)) ); assertTrue( !h1.contains(new Integer(9)) ); assertTrue( h1.remove( new Integer(3) ) ); System.out.println("h1 after removing 3 = " + h1); // assertTrue( ! h1.contains(new Integer(3)) ); x = h1.pop(); System.out.println("h1 after removing first = " + h1); h1.pop(); System.out.println("h1 after removing first = " + h1); assertTrue( h1.remove( new Integer(7) ) ); System.out.println("h1 after removing 7 = " + h1); assertTrue( h1.isEmpty() ); assertTrue( ! h1.remove( new Integer(7) ) ); h1.add( new Integer(666) ); h1.add( new Integer(667) ); assertTrue( h1.remove(new Integer(667)) ); assertTrue( h1.size() == 1 ); assertTrue( ! h1.contains(new Integer(667)) ); assertTrue( h1.remove(new Integer(666)) ); } public void checkOrder( BinaryHeap h ) { System.out.println("Checking order of " + h); Integer lastNum = null; LinkedList l = new LinkedList(); while ( !h.isEmpty() ) { Integer num = (Integer) h.pop(); System.out.println(num); if ( lastNum != null && num.intValue() < lastNum.intValue() ) { System.out.println("!!??*** " + num + " smaller than " + lastNum); } assertTrue( lastNum == null || num.intValue() >= lastNum.intValue() ); lastNum = num; l.add(num); } Iterator it = l.iterator(); while ( it.hasNext() ) { h.add( it.next() ); } } public void testRandom() { Random randGenerator = new Random(PRNGTestSeeds.UNIT_TEST_SEED); for( int i=0; i<1000; i++ ) { BinaryHeap h = new BinaryHeap(); for( int r=0; r<100; r++ ) { h.add( new Integer( randGenerator.nextInt(100)) ); } System.out.println("Starting with heap " + h); for( int r=0; r<20; r++ ) { System.out.println("Attempting to remove " + r); System.out.println("result = " + h.remove( new Integer(r) ) ); Integer n = new Integer( randGenerator.nextInt(100) ); System.out.println("Adding " + n); h.add(n); } checkOrder(h); } } public static void main( String[] args ) { junit.textui.TestRunner.run (suite()); } public static Test suite() { return new TestSuite(BinaryHeapTest.class); } } /* * JASA Java Auction Simulator API * Copyright (C) 2001-2003 Steve Phelps * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of * the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * See the GNU General Public License for more details. */ ------- PRNGTestSeeds.java ------- package test.uk.ac.liv; /** * The PRNG seed to use for deterministing unit-testing of seedable classes. * This was introduced for ecj10, which uses a seed based on the * current system time when using the null argument constructor. * * @author Steve Phelps * @version $Revision: 1.2 $ */ public class PRNGTestSeeds { /** * The seed to use for all unit tests. */ public static final long UNIT_TEST_SEED = 1465187; } --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
