DO NOT REPLY [Bug 25818] New: - BinaryHeap.remove(Object) seems to break heap order

[bu...@apache.org]

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: commons-dev@jakarta.apache.org
        ReportedBy: sphelps@csc.liv.ac.uk


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: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org