You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by ps...@apache.org on 2004/01/02 00:56:51 UTC
cvs commit: jakarta-commons/collections/src/test/org/apache/commons/collections/buffer TestBinaryBuffer.java
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: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org