commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From pste...@apache.org
Subject cvs commit: jakarta-commons/collections/src/test/org/apache/commons/collections/buffer TestBinaryBuffer.java
Date Thu, 01 Jan 2004 23:56:51 GMT
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


Mime
View raw message