psteitz 2004/01/01 15:56:51 Modified: collections/src/java/org/apache/commons/collections BinaryHeap.java collections/src/java/org/apache/commons/collections/buffer BinaryBuffer.java collections/src/test/org/apache/commons/collections TestBinaryHeap.java collections/src/test/org/apache/commons/collections/buffer TestBinaryBuffer.java Log: Fixed BinaryHeap / BinaryBuffer remove(object) bug. PR #25818 Reported by: Steve Phelps Revision Changes Path 1.17 +70 -28 jakarta-commons/collections/src/java/org/apache/commons/collections/BinaryHeap.java Index: BinaryHeap.java =================================================================== RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/BinaryHeap.java,v retrieving revision 1.16 retrieving revision 1.17 diff -u -r1.16 -r1.17 --- BinaryHeap.java 1 Jan 2004 19:00:20 -0000 1.16 +++ BinaryHeap.java 1 Jan 2004 23:56:51 -0000 1.17 @@ -4,7 +4,7 @@ * * The Apache Software License, Version 1.1 * - * Copyright (c) 2001-2003 The Apache Software Foundation. All rights + * Copyright (c) 2001-2004 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without @@ -319,8 +319,9 @@ } /** - * Percolates element down heap from top. - * Assume it is a maximum heap. + * Percolates element down heap from the position given by the index. + * <p> + * Assumes it is a mimimum heap. * * @param index the index for the element */ @@ -350,8 +351,9 @@ } /** - * Percolates element down heap from top. - * Assume it is a maximum heap. + * Percolates element down heap from the position given by the index. + * <p> + * Assumes it is a maximum heap. * * @param index the index of the element */ @@ -381,16 +383,15 @@ } /** - * Percolates element up heap from bottom. - * Assume it is a maximum heap. + * Percolates element up heap from the position given by the index. + * <p> + * Assumes it is a minimum heap. * - * @param element the element + * @param index the index of the element to be percolated up */ - protected void percolateUpMinHeap(final Object element) { - int hole = ++m_size; - - m_elements[hole] = element; - + protected void percolateUpMinHeap(final int index) { + int hole = index; + Object element = m_elements[hole]; while (hole > 1 && compare(element, m_elements[hole / 2]) < 0) { // save element that is being pushed down // as the element "bubble" is percolated up @@ -398,19 +399,32 @@ m_elements[hole] = m_elements[next]; hole = next; } - m_elements[hole] = element; } /** - * Percolates element up heap from bottom. - * Assume it is a maximum heap. + * Percolates a new element up heap from the bottom. + * <p> + * Assumes it is a minimum heap. * * @param element the element */ - protected void percolateUpMaxHeap(final Object element) { - int hole = ++m_size; + protected void percolateUpMinHeap(final Object element) { + m_elements[++m_size] = element; + percolateUpMinHeap(m_size); + } + /** + * Percolates element up heap from from the position given by the index. + * <p> + * Assume it is a maximum heap. + * + * @param element the element + */ + protected void percolateUpMaxHeap(final int index) { + int hole = index; + Object element = m_elements[hole]; + while (hole > 1 && compare(element, m_elements[hole / 2]) > 0) { // save element that is being pushed down // as the element "bubble" is percolated up @@ -423,6 +437,18 @@ } /** + * Percolates a new element up heap from the bottom. + * <p> + * Assume it is a maximum heap. + * + * @param element the element + */ + protected void percolateUpMaxHeap(final Object element) { + m_elements[++m_size] = element; + percolateUpMaxHeap(m_size); + } + + /** * Compares two objects using the comparator if specified, or the * natural order otherwise. * @@ -494,18 +520,34 @@ } public void remove() { - if (lastReturnedIndex == -1) throw new IllegalStateException(); + if (lastReturnedIndex == -1) { + throw new IllegalStateException(); + } m_elements[ lastReturnedIndex ] = m_elements[ m_size ]; m_elements[ m_size ] = null; - m_size--; - if( m_size != 0 ) - { - //percolate top element to it's place in tree - if( m_isMinHeap ) percolateDownMinHeap( lastReturnedIndex ); - else percolateDownMaxHeap( lastReturnedIndex ); + m_size--; + if( m_size != 0 && lastReturnedIndex <= m_size) { + int compareToParent = 0; + if (lastReturnedIndex > 1) { + compareToParent = compare(m_elements[lastReturnedIndex], + m_elements[lastReturnedIndex / 2]); + } + if (m_isMinHeap) { + if (lastReturnedIndex > 1 && compareToParent < 0) { + percolateUpMinHeap(lastReturnedIndex); + } else { + percolateDownMinHeap(lastReturnedIndex); + } + } else { // max heap + if (lastReturnedIndex > 1 && compareToParent > 0) { + percolateUpMaxHeap(lastReturnedIndex); + } else { + percolateDownMaxHeap(lastReturnedIndex); + } + } } index--; - lastReturnedIndex = -1; + lastReturnedIndex = -1; } }; 1.2 +68 -29 jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/BinaryBuffer.java Index: BinaryBuffer.java =================================================================== RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/BinaryBuffer.java,v retrieving revision 1.1 retrieving revision 1.2 diff -u -r1.1 -r1.2 --- BinaryBuffer.java 1 Jan 2004 19:01:34 -0000 1.1 +++ BinaryBuffer.java 1 Jan 2004 23:56:51 -0000 1.2 @@ -4,7 +4,7 @@ * * The Apache Software License, Version 1.1 * - * Copyright (c) 2001-2003 The Apache Software Foundation. All rights + * Copyright (c) 2001-2004 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without @@ -337,9 +337,11 @@ return elements.length == size + 1; } + /** - * Percolates element down heap from top. - * Assume it is a minimum heap. + * Percolates element down heap from the position given by the index. + * <p> + * Assumes it is a mimimum heap. * * @param index the index for the element */ @@ -369,8 +371,9 @@ } /** - * Percolates element down heap from top. - * Assume it is a maximum heap. + * Percolates element down heap from the position given by the index. + * <p> + * Assumes it is a maximum heap. * * @param index the index of the element */ @@ -400,16 +403,15 @@ } /** - * Percolates element up heap from bottom. - * Assume it is a minimum heap. + * Percolates element up heap from the position given by the index. + * <p> + * Assumes it is a minimum heap. * - * @param element the element + * @param index the index of the element to be percolated up */ - protected void percolateUpMinHeap(final Object element) { - int hole = ++size; - - elements[hole] = element; - + protected void percolateUpMinHeap(final int index) { + int hole = index; + Object element = elements[hole]; while (hole > 1 && compare(element, elements[hole / 2]) < 0) { // save element that is being pushed down // as the element "bubble" is percolated up @@ -417,18 +419,31 @@ elements[hole] = elements[next]; hole = next; } - elements[hole] = element; } /** - * Percolates element up heap from bottom. + * Percolates a new element up heap from the bottom. + * <p> + * Assumes it is a minimum heap. + * + * @param element the element + */ + protected void percolateUpMinHeap(final Object element) { + elements[++size] = element; + percolateUpMinHeap(size); + } + + /** + * Percolates element up heap from from the position given by the index. + * <p> * Assume it is a maximum heap. * * @param element the element */ - protected void percolateUpMaxHeap(final Object element) { - int hole = ++size; + protected void percolateUpMaxHeap(final int index) { + int hole = index; + Object element = elements[hole]; while (hole > 1 && compare(element, elements[hole / 2]) > 0) { // save element that is being pushed down @@ -442,6 +457,18 @@ } /** + * Percolates a new element up heap from the bottom. + * <p> + * Assume it is a maximum heap. + * + * @param element the element + */ + protected void percolateUpMaxHeap(final Object element) { + elements[++size] = element; + percolateUpMaxHeap(size); + } + + /** * Compares two objects using the comparator if specified, or the * natural order otherwise. * @@ -495,19 +522,31 @@ if (lastReturnedIndex == -1) { throw new IllegalStateException(); } - elements[lastReturnedIndex] = elements[size]; - elements[size] = null; - size--; - if (size != 0) { - //percolate top element to it's place in tree - if (ascendingOrder) { - percolateDownMinHeap(lastReturnedIndex); - } else { - percolateDownMaxHeap(lastReturnedIndex); + elements[ lastReturnedIndex ] = elements[ size ]; + elements[ size ] = null; + size--; + if( size != 0 && lastReturnedIndex <= size) { + int compareToParent = 0; + if (lastReturnedIndex > 1) { + compareToParent = compare(elements[lastReturnedIndex], + elements[lastReturnedIndex / 2]); } + if (ascendingOrder) { + if (lastReturnedIndex > 1 && compareToParent < 0) { + percolateUpMinHeap(lastReturnedIndex); + } else { + percolateDownMinHeap(lastReturnedIndex); + } + } else { // max heap + if (lastReturnedIndex > 1 && compareToParent > 0) { + percolateUpMaxHeap(lastReturnedIndex); + } else { + percolateDownMaxHeap(lastReturnedIndex); + } + } } index--; - lastReturnedIndex = -1; + lastReturnedIndex = -1; } }; 1.14 +96 -3 jakarta-commons/collections/src/test/org/apache/commons/collections/TestBinaryHeap.java Index: TestBinaryHeap.java =================================================================== RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestBinaryHeap.java,v retrieving revision 1.13 retrieving revision 1.14 diff -u -r1.13 -r1.14 --- TestBinaryHeap.java 18 Nov 2003 22:37:16 -0000 1.13 +++ TestBinaryHeap.java 1 Jan 2004 23:56:51 -0000 1.14 @@ -4,7 +4,7 @@ * * The Apache Software License, Version 1.1 * - * Copyright (c) 2001-2003 The Apache Software Foundation. All rights + * Copyright (c) 2001-2004 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without @@ -62,6 +62,7 @@ import java.util.Collection; import java.util.Comparator; import java.util.NoSuchElementException; +import java.util.Random; import junit.framework.Test; import junit.framework.TestSuite; @@ -287,6 +288,98 @@ } catch (NoSuchElementException e) { // expected } + } + + /** + * Illustrates bad internal heap state reported in Bugzilla PR #235818. + */ + public void testAddRemove() { + resetEmpty(); + BinaryHeap heap = (BinaryHeap) collection; + heap.add(new Integer(0)); + heap.add(new Integer(2)); + heap.add(new Integer(4)); + heap.add(new Integer(3)); + heap.add(new Integer(8)); + heap.add(new Integer(10)); + heap.add(new Integer(12)); + heap.add(new Integer(3)); + confirmed.addAll(heap); + // System.out.println(heap); + Object obj = new Integer(10); + heap.remove(obj); + confirmed.remove(obj); + // System.out.println(heap); + verify(); + } + + /** + * Generate heaps staring with Integers from 0 - heapSize - 1. + * Then perform random add / remove operations, checking + * heap order after modifications. Alternates minHeaps, maxHeaps. + * + * Based on code provided by Steve Phelps in PR #25818 + * + */ + public void testRandom() { + int iterations = 500; + int heapSize = 100; + int operations = 20; + Random randGenerator = new Random(); + BinaryHeap h = null; + for(int i=0; i < iterations; i++) { + if (i < iterations / 2) { + h = new BinaryHeap(true); + } else { + h = new BinaryHeap(false); + } + for(int r = 0; r < heapSize; r++) { + h.add( new Integer( randGenerator.nextInt(heapSize)) ); + } + for( int r = 0; r < operations; r++ ) { + h.remove(new Integer(r)); + h.add(new Integer(randGenerator.nextInt(heapSize))); + } + checkOrder(h); + } + } + + /** + * Pops all elements from the heap and verifies that the elements come off + * in the correct order. NOTE: this method empties the heap. + */ + protected void checkOrder(BinaryHeap h) { + Integer lastNum = null; + Integer num = null; + boolean fail = false; + while (!h.isEmpty()) { + num = (Integer) h.pop(); + if (h.m_isMinHeap) { + assertTrue(lastNum == null || num.intValue() >= lastNum.intValue()); + } else { // max heap + assertTrue(lastNum == null || num.intValue() <= lastNum.intValue()); + } + lastNum = num; + num = null; + } + } + + /** + * Returns a string showing the contents of the heap formatted as a tree. + * Makes no attempt at padding levels or handling wrapping. + */ + protected String showTree(BinaryHeap h) { + int count = 1; + StringBuffer buffer = new StringBuffer(); + for (int offset = 1; count < h.size() + 1; offset *= 2) { + for (int i = offset; i < offset * 2; i++) { + if (i < h.m_elements.length && h.m_elements[i] != null) + buffer.append(h.m_elements[i] + " "); + count++; + } + buffer.append('\n'); + } + return buffer.toString(); } } 1.2 +95 -22 jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestBinaryBuffer.java Index: TestBinaryBuffer.java =================================================================== RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestBinaryBuffer.java,v retrieving revision 1.1 retrieving revision 1.2 diff -u -r1.1 -r1.2 --- TestBinaryBuffer.java 1 Jan 2004 19:01:34 -0000 1.1 +++ TestBinaryBuffer.java 1 Jan 2004 23:56:51 -0000 1.2 @@ -4,7 +4,7 @@ * * The Apache Software License, Version 1.1 * - * Copyright (c) 2001-2003 The Apache Software Foundation. All rights + * Copyright (c) 2001-2004 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without @@ -61,6 +61,7 @@ import java.util.Arrays; import java.util.Collection; import java.util.Comparator; +import java.util.Random; import junit.framework.Test; import junit.framework.TestSuite; @@ -286,24 +287,96 @@ } catch (BufferUnderflowException ex) {} } -// public void testAddRemove() { -// resetEmpty(); -// BinaryBuffer heap = (BinaryBuffer) collection; -// heap.add(new Integer(0)); -// heap.add(new Integer(2)); -// heap.add(new Integer(4)); -// heap.add(new Integer(3)); -// heap.add(new Integer(8)); -// heap.add(new Integer(10)); -// heap.add(new Integer(12)); -// heap.add(new Integer(3)); -// confirmed.addAll(heap); -// System.out.println(heap); -// Object obj = new Integer(10); -// heap.remove(obj); -// confirmed.remove(obj); -// System.out.println(heap); -// verify(); -// } + /** + * Illustrates bad internal heap state reported in Bugzilla PR #235818. + */ + public void testAddRemove() { + resetEmpty(); + BinaryBuffer heap = (BinaryBuffer) collection; + heap.add(new Integer(0)); + heap.add(new Integer(2)); + heap.add(new Integer(4)); + heap.add(new Integer(3)); + heap.add(new Integer(8)); + heap.add(new Integer(10)); + heap.add(new Integer(12)); + heap.add(new Integer(3)); + confirmed.addAll(heap); + // System.out.println(heap); + Object obj = new Integer(10); + heap.remove(obj); + confirmed.remove(obj); + // System.out.println(heap); + verify(); + } + + /** + * Generate heaps staring with Integers from 0 - heapSize - 1. + * Then perform random add / remove operations, checking + * heap order after modifications. Alternates minHeaps, maxHeaps. + * + * Based on code provided by Steve Phelps in PR #25818 + * + */ + public void testRandom() { + int iterations = 500; + int heapSize = 100; + int operations = 20; + Random randGenerator = new Random(); + BinaryBuffer h = null; + for(int i=0; i < iterations; i++) { + if (i < iterations / 2) { + h = new BinaryBuffer(true); + } else { + h = new BinaryBuffer(false); + } + for(int r = 0; r < heapSize; r++) { + h.add( new Integer( randGenerator.nextInt(heapSize)) ); + } + for( int r = 0; r < operations; r++ ) { + h.remove(new Integer(r)); + h.add(new Integer(randGenerator.nextInt(heapSize))); + } + checkOrder(h); + } + } + + /** + * Pops all elements from the heap and verifies that the elements come off + * in the correct order. NOTE: this method empties the heap. + */ + protected void checkOrder(BinaryBuffer h) { + Integer lastNum = null; + Integer num = null; + boolean fail = false; + while (!h.isEmpty()) { + num = (Integer) h.remove(); + if (h.ascendingOrder) { + assertTrue(lastNum == null || num.intValue() >= lastNum.intValue()); + } else { // max heap + assertTrue(lastNum == null || num.intValue() <= lastNum.intValue()); + } + lastNum = num; + num = null; + } + } + + /** + * Returns a string showing the contents of the heap formatted as a tree. + * Makes no attempt at padding levels or handling wrapping. + */ + protected String showTree(BinaryBuffer h) { + int count = 1; + StringBuffer buffer = new StringBuffer(); + for (int offset = 1; count < h.size() + 1; offset *= 2) { + for (int i = offset; i < offset * 2; i++) { + if (i < h.elements.length && h.elements[i] != null) + buffer.append(h.elements[i] + " "); + count++; + } + buffer.append('\n'); + } + return buffer.toString(); + } }
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]