commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From scolebou...@apache.org
Subject cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections/buffer PriorityBuffer.java package.html BinaryBuffer.java
Date Fri, 02 Jan 2004 02:14:29 GMT
scolebourne    2004/01/01 18:14:29

  Modified:    collections/src/test/org/apache/commons/collections/buffer
                        TestAll.java
               collections/src/java/org/apache/commons/collections
                        BinaryHeap.java
               collections/src/java/org/apache/commons/collections/buffer
                        package.html
  Added:       collections/src/test/org/apache/commons/collections/buffer
                        TestPriorityBuffer.java
               collections/src/java/org/apache/commons/collections/buffer
                        PriorityBuffer.java
  Removed:     collections/src/test/org/apache/commons/collections/buffer
                        TestBinaryBuffer.java
               collections/src/java/org/apache/commons/collections/buffer
                        BinaryBuffer.java
  Log:
  Rename BinaryBuffer to PriorityBuffer
  
  Revision  Changes    Path
  1.4       +6 -5      jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestAll.java
  
  Index: TestAll.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestAll.java,v
  retrieving revision 1.3
  retrieving revision 1.4
  diff -u -r1.3 -r1.4
  --- TestAll.java	1 Jan 2004 19:01:34 -0000	1.3
  +++ TestAll.java	2 Jan 2004 02:14:28 -0000	1.4
  @@ -83,14 +83,15 @@
       public static Test suite() {
           TestSuite suite = new TestSuite();
           
  -        suite.addTest(TestBinaryBuffer.suite());
  -        suite.addTest(TestBlockingBuffer.suite());
           suite.addTest(TestBoundedFifoBuffer.suite());
           suite.addTest(TestBoundedFifoBuffer2.suite());
           suite.addTest(TestCircularFifoBuffer.suite());
  +        suite.addTest(TestPriorityBuffer.suite());
  +        suite.addTest(TestUnboundedFifoBuffer.suite());
  +        
  +        suite.addTest(TestBlockingBuffer.suite());
           suite.addTest(TestPredicatedBuffer.suite());
           suite.addTest(TestTransformedBuffer.suite());
  -        suite.addTest(TestUnboundedFifoBuffer.suite());
           
           return suite;
       }
  
  
  
  1.1                  jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestPriorityBuffer.java
  
  Index: TestPriorityBuffer.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestPriorityBuffer.java,v
1.1 2004/01/02 02:14:28 scolebourne Exp $
   * ====================================================================
   *
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2001-2004 The Apache Software Foundation.  All rights
   * reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   *
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in
   *    the documentation and/or other materials provided with the
   *    distribution.
   *
   * 3. The end-user documentation included with the redistribution, if
   *    any, must include the following acknowledgement:
   *       "This product includes software developed by the
   *        Apache Software Foundation (http://www.apache.org/)."
   *    Alternately, this acknowledgement may appear in the software itself,
   *    if and wherever such third-party acknowledgements normally appear.
   *
   * 4. The names "The Jakarta Project", "Commons", and "Apache Software
   *    Foundation" must not be used to endorse or promote products derived
   *    from this software without prior written permission. For written
   *    permission, please contact apache@apache.org.
   *
   * 5. Products derived from this software may not be called "Apache"
   *    nor may "Apache" appear in their names without prior written
   *    permission of the Apache Software Foundation.
   *
   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   * SUCH DAMAGE.
   * ====================================================================
   *
   * This software consists of voluntary contributions made by many
   * individuals on behalf of the Apache Software Foundation.  For more
   * information on the Apache Software Foundation, please see
   * <http://www.apache.org/>.
   *
   */
  package org.apache.commons.collections.buffer;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collection;
  import java.util.Comparator;
  import java.util.Random;
  
  import junit.framework.Test;
  import junit.framework.TestSuite;
  
  import org.apache.commons.collections.Buffer;
  import org.apache.commons.collections.BufferUnderflowException;
  import org.apache.commons.collections.ComparatorUtils;
  import org.apache.commons.collections.collection.AbstractTestCollection;
  import org.apache.commons.collections.comparators.ComparableComparator;
  import org.apache.commons.collections.comparators.ReverseComparator;
  
  /**
   * Tests the PriorityBuffer.
   * 
   * @version $Revision: 1.1 $ $Date: 2004/01/02 02:14:28 $
   * 
   * @author Michael A. Smith
   */
  public class TestPriorityBuffer extends AbstractTestCollection {
  
      public static void main(String[] args) {
          junit.textui.TestRunner.run(suite());
      }
  
      public static Test suite() {
          return new TestSuite(TestPriorityBuffer.class);
      }
  
      public TestPriorityBuffer(String testName) {
          super(testName);
      }
  
      //-----------------------------------------------------------------------  
      public void verify() {
          super.verify();
          PriorityBuffer heap = (PriorityBuffer) collection;
  
          Comparator c = heap.comparator;
          if (c == null) {
              c = ComparatorUtils.naturalComparator();
          }
          if (!heap.ascendingOrder) {
              c = ComparatorUtils.reversedComparator(c);
          }
  
          Object[] tree = heap.elements;
          for (int i = 1; i <= heap.size; i++) {
              Object parent = tree[i];
              if (i * 2 <= heap.size) {
                  assertTrue("Parent is less than or equal to its left child", c.compare(parent,
tree[i * 2]) <= 0);
              }
              if (i * 2 + 1 < heap.size) {
                  assertTrue("Parent is less than or equal to its right child", c.compare(parent,
tree[i * 2 + 1]) <= 0);
              }
          }
      }
  
      //-----------------------------------------------------------------------  
      /**
       * Overridden because BinaryBuffer isn't fail fast.
       * @return false
       */
      public boolean isFailFastSupported() {
          return false;
      }
  
      //-----------------------------------------------------------------------  
      public Collection makeConfirmedCollection() {
          return new ArrayList();
      }
  
      public Collection makeConfirmedFullCollection() {
          ArrayList list = new ArrayList();
          list.addAll(Arrays.asList(getFullElements()));
          return list;
      }
  
      /**
       * Return a new, empty {@link Object} to used for testing.
       */
      public Collection makeCollection() {
          return new PriorityBuffer();
      }
  
      //-----------------------------------------------------------------------  
      public Object[] getFullElements() {
          return getFullNonNullStringElements();
      }
  
      public Object[] getOtherElements() {
          return getOtherNonNullStringElements();
      }
  
      //-----------------------------------------------------------------------  
      public void testBufferEmpty() {
          resetEmpty();
          Buffer buffer = (Buffer) collection;
  
          assertEquals(0, buffer.size());
          assertEquals(true, buffer.isEmpty());
          try {
              buffer.get();
              fail();
          } catch (BufferUnderflowException ex) {}
  
          try {
              buffer.remove();
              fail();
          } catch (BufferUnderflowException ex) {}
      }
      
      public void testBasicOps() {
          PriorityBuffer heap = new PriorityBuffer();
  
          heap.add("a");
          heap.add("c");
          heap.add("e");
          heap.add("b");
          heap.add("d");
          heap.add("n");
          heap.add("m");
          heap.add("l");
          heap.add("k");
          heap.add("j");
          heap.add("i");
          heap.add("h");
          heap.add("g");
          heap.add("f");
  
          assertTrue("heap should not be empty after adds", !heap.isEmpty());
  
          for (int i = 0; i < 14; i++) {
              assertEquals(
                  "get using default constructor should return minimum value in the binary
heap",
                  String.valueOf((char) ('a' + i)),
                  heap.get());
  
              assertEquals(
                  "remove using default constructor should return minimum value in the binary
heap",
                  String.valueOf((char) ('a' + i)),
                  heap.remove());
  
              if (i + 1 < 14) {
                  assertTrue("heap should not be empty before all elements are removed", !heap.isEmpty());
              } else {
                  assertTrue("heap should be empty after all elements are removed", heap.isEmpty());
              }
          }
  
          try {
              heap.get();
              fail("NoSuchElementException should be thrown if get is called after all elements
are removed");
          } catch (BufferUnderflowException ex) {}
  
          try {
              heap.remove();
              fail("NoSuchElementException should be thrown if remove is called after all
elements are removed");
          } catch (BufferUnderflowException ex) {}
      }
  
      public void testBasicComparatorOps() {
          PriorityBuffer heap = new PriorityBuffer(new ReverseComparator(new ComparableComparator()));
  
          assertTrue("heap should be empty after create", heap.isEmpty());
  
          try {
              heap.get();
              fail("NoSuchElementException should be thrown if get is called before any elements
are added");
          } catch (BufferUnderflowException ex) {}
  
          try {
              heap.remove();
              fail("NoSuchElementException should be thrown if remove is called before any
elements are added");
          } catch (BufferUnderflowException ex) {}
  
          heap.add("a");
          heap.add("c");
          heap.add("e");
          heap.add("b");
          heap.add("d");
          heap.add("n");
          heap.add("m");
          heap.add("l");
          heap.add("k");
          heap.add("j");
          heap.add("i");
          heap.add("h");
          heap.add("g");
          heap.add("f");
  
          assertTrue("heap should not be empty after adds", !heap.isEmpty());
  
          for (int i = 0; i < 14; i++) {
  
              // note: since we're using a comparator that reverses items, the
              // "minimum" item is "n", and the "maximum" item is "a".
  
              assertEquals(
                  "get using default constructor should return minimum value in the binary
heap",
                  String.valueOf((char) ('n' - i)),
                  heap.get());
  
              assertEquals(
                  "remove using default constructor should return minimum value in the binary
heap",
                  String.valueOf((char) ('n' - i)),
                  heap.remove());
  
              if (i + 1 < 14) {
                  assertTrue("heap should not be empty before all elements are removed", !heap.isEmpty());
              } else {
                  assertTrue("heap should be empty after all elements are removed", heap.isEmpty());
              }
          }
  
          try {
              heap.get();
              fail("NoSuchElementException should be thrown if get is called after all elements
are removed");
          } catch (BufferUnderflowException ex) {}
  
          try {
              heap.remove();
              fail("NoSuchElementException should be thrown if remove is called after all
elements are removed");
          } catch (BufferUnderflowException ex) {}
      }
  
      /**
       * Illustrates bad internal heap state reported in Bugzilla PR #235818. 
       */  
      public void testAddRemove() {
          resetEmpty();
          PriorityBuffer heap = (PriorityBuffer) 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();
          PriorityBuffer h = null;
          for(int i=0; i < iterations; i++) {
              if (i < iterations / 2) {          
                  h = new PriorityBuffer(true);
              } else {
                  h = new PriorityBuffer(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(PriorityBuffer 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(PriorityBuffer 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();
      }
      
  }
  
  
  
  1.19      +3 -3      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.18
  retrieving revision 1.19
  diff -u -r1.18 -r1.19
  --- BinaryHeap.java	2 Jan 2004 01:36:51 -0000	1.18
  +++ BinaryHeap.java	2 Jan 2004 02:14:28 -0000	1.19
  @@ -68,7 +68,7 @@
    * The <code>PriorityQueue</code> interface has now been replaced for most
uses
    * by the <code>Buffer</code> interface. This class and the interface are
    * retained for backwards compatability. The intended replacement is
  - * {@link org.apache.commons.collections.buffer.BinaryBuffer BinaryBuffer}.
  + * {@link org.apache.commons.collections.buffer.PriorityBuffer PriorityBuffer}.
    * <p>
    * The removal order of a binary heap is based on either the natural sort
    * order of its elements or a specified {@link Comparator}.  The 
  
  
  
  1.7       +1 -1      jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/package.html
  
  Index: package.html
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/package.html,v
  retrieving revision 1.6
  retrieving revision 1.7
  diff -u -r1.6 -r1.7
  --- package.html	1 Jan 2004 19:01:34 -0000	1.6
  +++ package.html	2 Jan 2004 02:14:29 -0000	1.7
  @@ -5,7 +5,7 @@
   <p>
   The following implementations are provided in the package:
   <ul>
  -<li>BinaryBuffer - provides for removal based on a comparator ordering (priority
queue)
  +<li>PriorityBuffer - provides for removal based on a comparator ordering
   <li>BoundedFifoBuffer - implements a buffer with a fixed size that throws exceptions
when full
   <li>CircularFifoBuffer - implements a buffer with a fixed size that discards oldest
when full
   <li>UnboundedFifoBuffer - implements a buffer that grows in size if necessary
  
  
  
  1.1                  jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/PriorityBuffer.java
  
  Index: PriorityBuffer.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/PriorityBuffer.java,v
1.1 2004/01/02 02:14:29 scolebourne Exp $
   * ====================================================================
   *
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2001-2004 The Apache Software Foundation.  All rights
   * reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   *
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in
   *    the documentation and/or other materials provided with the
   *    distribution.
   *
   * 3. The end-user documentation included with the redistribution, if
   *    any, must include the following acknowledgement:
   *       "This product includes software developed by the
   *        Apache Software Foundation (http://www.apache.org/)."
   *    Alternately, this acknowledgement may appear in the software itself,
   *    if and wherever such third-party acknowledgements normally appear.
   *
   * 4. The names "The Jakarta Project", "Commons", and "Apache Software
   *    Foundation" must not be used to endorse or promote products derived
   *    from this software without prior written permission. For written
   *    permission, please contact apache@apache.org.
   *
   * 5. Products derived from this software may not be called "Apache"
   *    nor may "Apache" appear in their names without prior written
   *    permission of the Apache Software Foundation.
   *
   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   * SUCH DAMAGE.
   * ====================================================================
   *
   * This software consists of voluntary contributions made by many
   * individuals on behalf of the Apache Software Foundation.  For more
   * information on the Apache Software Foundation, please see
   * <http://www.apache.org/>.
   *
   */
  package org.apache.commons.collections.buffer;
  
  import java.util.AbstractCollection;
  import java.util.Comparator;
  import java.util.Iterator;
  import java.util.NoSuchElementException;
  
  import org.apache.commons.collections.Buffer;
  import org.apache.commons.collections.BufferUnderflowException;
  
  /**
   * Binary heap implementation of <code>Buffer</code> that provides for
   * removal based on <code>Comparator</code> ordering.
   * <p>
   * The removal order of a binary heap is based on either the natural sort
   * order of its elements or a specified {@link Comparator}.  The 
   * {@link #remove()} method always returns the first element as determined
   * by the sort order.  (The <code>ascendingOrder</code> flag in the constructors
   * can be used to reverse the sort order, in which case {@link #remove()}
   * will always remove the last element.)  The removal order is 
   * <i>not</i> the same as the order of iteration; elements are
   * returned by the iterator in no particular order.
   * <p>
   * The {@link #add(Object)} and {@link #remove()} operations perform
   * in logarithmic time.  The {@link #get()} operation performs in constant
   * time.  All other operations perform in linear time or worse.
   * <p>
   * Note that this implementation is not synchronized.  Use 
   * {@link org.apache.commons.collections.BufferUtils#synchronizedBuffer(Buffer)} or
   * {@link org.apache.commons.collections.buffer.SynchronizedBuffer#decorate(Buffer)}
   * to provide synchronized access to a <code>PriorityBuffer</code>:
   *
   * <pre>
   * Buffer heap = SynchronizedBuffer.decorate(new PriorityBuffer());
   * </pre>
   *
   * @since Commons Collections 3.0 (previously BinaryHeap v1.0)
   * @version $Revision: 1.1 $ $Date: 2004/01/02 02:14:29 $
   * 
   * @author Peter Donald
   * @author Ram Chidambaram
   * @author Michael A. Smith
   * @author Paul Jack
   * @author Stephen Colebourne
   */
  public class PriorityBuffer extends AbstractCollection implements Buffer {
  
      /**
       * The default capacity for the buffer.
       */
      private static final int DEFAULT_CAPACITY = 13;
      
      /**
       * The elements in this buffer.
       */
      protected Object[] elements;
      /**
       * The number of elements currently in this buffer.
       */
      protected int size;
      /**
       * If true, the first element as determined by the sort order will 
       * be returned.  If false, the last element as determined by the
       * sort order will be returned.
       */
      protected boolean ascendingOrder;
      /**
       * The comparator used to order the elements
       */
      protected Comparator comparator;
  
      //-----------------------------------------------------------------------
      /**
       * Constructs a new empty buffer that sorts in ascending order by the
       * natural order of the objects added.
       */
      public PriorityBuffer() {
          this(DEFAULT_CAPACITY, true, null);
      }
  
      /**
       * Constructs a new empty buffer that sorts in ascending order using the
       * specified comparator.
       * 
       * @param comparator  the comparator used to order the elements,
       *  null means use natural order
       */
      public PriorityBuffer(Comparator comparator) {
          this(DEFAULT_CAPACITY, true, comparator);
      }
  
      /**
       * Constructs a new empty buffer specifying the sort order and using the
       * natural order of the objects added.
       *
       * @param ascendingOrder  if <code>true</code> the heap is created as a

       * minimum heap; otherwise, the heap is created as a maximum heap
       */
      public PriorityBuffer(boolean ascendingOrder) {
          this(DEFAULT_CAPACITY, ascendingOrder, null);
      }
  
      /**
       * Constructs a new empty buffer specifying the sort order and comparator.
       *
       * @param ascendingOrder  true to use the order imposed by the given 
       *   comparator; false to reverse that order
       * @param comparator  the comparator used to order the elements,
       *  null means use natural order
       */
      public PriorityBuffer(boolean ascendingOrder, Comparator comparator) {
          this(DEFAULT_CAPACITY, ascendingOrder, comparator);
      }
  
      /**
       * Constructs a new empty buffer that sorts in ascending order by the
       * natural order of the objects added, specifying an initial capacity.
       *  
       * @param capacity  the initial capacity for the buffer, greater than zero
       * @throws IllegalArgumentException if <code>capacity</code> is &lt;=
<code>0</code>
       */
      public PriorityBuffer(int capacity) {
          this(capacity, true, null);
      }
  
      /**
       * Constructs a new empty buffer that sorts in ascending order using the
       * specified comparator and initial capacity.
       *
       * @param capacity  the initial capacity for the buffer, greater than zero
       * @param comparator  the comparator used to order the elements,
       *  null means use natural order
       * @throws IllegalArgumentException if <code>capacity</code> is &lt;=
<code>0</code>
       */
      public PriorityBuffer(int capacity, Comparator comparator) {
          this(capacity, true, comparator);
      }
  
      /**
       * Constructs a new empty buffer that specifying initial capacity and
       * sort order, using the natural order of the objects added.
       *
       * @param capacity  the initial capacity for the buffer, greater than zero
       * @param ascendingOrder if <code>true</code> the heap is created as a 
       *  minimum heap; otherwise, the heap is created as a maximum heap.
       * @throws IllegalArgumentException if <code>capacity</code> is <code>&lt;=
0</code>
       */
      public PriorityBuffer(int capacity, boolean ascendingOrder) {
          this(capacity, ascendingOrder, null);
      }
  
      /**
       * Constructs a new empty buffer that specifying initial capacity,
       * sort order and comparator.
       *
       * @param capacity  the initial capacity for the buffer, greater than zero
       * @param ascendingOrder  true to use the order imposed by the given 
       *   comparator; false to reverse that order
       * @param comparator  the comparator used to order the elements,
       *  null means use natural order
       * @throws IllegalArgumentException if <code>capacity</code> is <code>&lt;=
0</code>
       */
      public PriorityBuffer(int capacity, boolean ascendingOrder, Comparator comparator) {
          super();
          if (capacity <= 0) {
              throw new IllegalArgumentException("invalid capacity");
          }
          this.ascendingOrder = ascendingOrder;
  
          //+1 as 0 is noop
          this.elements = new Object[capacity + 1];
          this.comparator = comparator;
      }
  
      //-----------------------------------------------------------------------
      /**
       * Checks whether the heap is ascending or descending order.
       * 
       * @return true if ascending order (a min heap)
       */
      public boolean isAscendingOrder() {
          return ascendingOrder;
      }
      
      /**
       * Gets the comparator being used for this buffer, null is natural order.
       * 
       * @return the comparator in use, null is natural order
       */
      public Comparator comparator() {
          return comparator;
      }
      
      //-----------------------------------------------------------------------
      /**
       * Returns the number of elements in this buffer.
       *
       * @return the number of elements in this buffer
       */
      public int size() {
          return size;
      }
  
      /**
       * Clears all elements from the buffer.
       */
      public void clear() {
          elements = new Object[elements.length]; // for gc
          size = 0;
      }
  
      /**
       * Adds an element to the buffer.
       * <p>
       * The element added will be sorted according to the comparator in use.
       *
       * @param element  the element to be added
       */
      public boolean add(Object element) {
          if (isAtCapacity()) {
              grow();
          }
          // percolate element to it's place in tree
          if (ascendingOrder) {
              percolateUpMinHeap(element);
          } else {
              percolateUpMaxHeap(element);
          }
          return true;
      }
  
      /**
       * Gets the next element to be removed without actually removing it (peek).
       *
       * @return the next element
       * @throws BufferUnderflowException if the buffer is empty
       */
      public Object get() {
          if (isEmpty()) {
              throw new BufferUnderflowException();
          } else {
              return elements[1];
          }
      }
  
      /**
       * Gets and removes the next element (pop).
       *
       * @return the next element
       * @throws BufferUnderflowException if the buffer is empty
       */
      public Object remove() {
          final Object result = get();
          elements[1] = elements[size--];
  
          // set the unused element to 'null' so that the garbage collector
          // can free the object if not used anywhere else.(remove reference)
          elements[size + 1] = null;
  
          if (size != 0) {
              // percolate top element to it's place in tree
              if (ascendingOrder) {
                  percolateDownMinHeap(1);
              } else {
                  percolateDownMaxHeap(1);
              }
          }
  
          return result;
      }
  
      //-----------------------------------------------------------------------
      /**
       * Tests if the buffer is at capacity.
       *
       * @return <code>true</code> if buffer is full; <code>false</code>
otherwise.
       */
      protected boolean isAtCapacity() {
          //+1 as element 0 is noop
          return elements.length == size + 1;
      }
  
      
      /**
       * 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
       */
      protected void percolateDownMinHeap(final int index) {
          final Object element = elements[index];
          int hole = index;
  
          while ((hole * 2) <= size) {
              int child = hole * 2;
  
              // if we have a right child and that child can not be percolated
              // up then move onto other child
              if (child != size && compare(elements[child + 1], elements[child]) <
0) {
                  child++;
              }
  
              // if we found resting place of bubble then terminate search
              if (compare(elements[child], element) >= 0) {
                  break;
              }
  
              elements[hole] = elements[child];
              hole = child;
          }
  
          elements[hole] = element;
      }
  
      /**
       * 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
       */
      protected void percolateDownMaxHeap(final int index) {
          final Object element = elements[index];
          int hole = index;
  
          while ((hole * 2) <= size) {
              int child = hole * 2;
  
              // if we have a right child and that child can not be percolated
              // up then move onto other child
              if (child != size && compare(elements[child + 1], elements[child]) >
0) {
                  child++;
              }
  
              // if we found resting place of bubble then terminate search
              if (compare(elements[child], element) <= 0) {
                  break;
              }
  
              elements[hole] = elements[child];
              hole = child;
          }
  
          elements[hole] = element;
      }
  
      /**
       * Percolates element up heap from the position given by the index.
       * <p>
       * Assumes it is a minimum heap.
       *
       * @param index the index of the element to be percolated up
       */
      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
              final int next = hole / 2;
              elements[hole] = elements[next];
              hole = next;
          }
          elements[hole] = element;
      }
  
      /**
       * 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 index the index of the element to be percolated up
       */
      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
              // as the element "bubble" is percolated up
              final int next = hole / 2;
              elements[hole] = elements[next];
              hole = next;
          }
  
          elements[hole] = element;
      }
  
      /**
       * 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.
       * 
       * @param a  the first object
       * @param b  the second object
       * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
       */
      protected int compare(Object a, Object b) {
          if (comparator != null) {
              return comparator.compare(a, b);
          } else {
              return ((Comparable) a).compareTo(b);
          }
      }
  
      /**
       * Increases the size of the heap to support additional elements
       */
      protected void grow() {
          final Object[] array = new Object[elements.length * 2];
          System.arraycopy(elements, 0, array, 0, elements.length);
          elements = array;
      }
  
      //-----------------------------------------------------------------------
      /**
       * Returns an iterator over this heap's elements.
       *
       * @return an iterator over this heap's elements
       */
      public Iterator iterator() {
          return new Iterator() {
  
              private int index = 1;
              private int lastReturnedIndex = -1;
  
              public boolean hasNext() {
                  return index <= size;
              }
  
              public Object next() {
                  if (!hasNext()) {
                      throw new NoSuchElementException();
                  }
                  lastReturnedIndex = index;
                  index++;
                  return elements[lastReturnedIndex];
              }
  
              public void remove() {
                  if (lastReturnedIndex == -1) {
                      throw new IllegalStateException();
                  }
                  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; 
              }
  
          };
      }
  
      /**
       * Returns a string representation of this heap.  The returned string
       * is similar to those produced by standard JDK collections.
       *
       * @return a string representation of this heap
       */
      public String toString() {
          final StringBuffer sb = new StringBuffer();
  
          sb.append("[ ");
  
          for (int i = 1; i < size + 1; i++) {
              if (i != 1) {
                  sb.append(", ");
              }
              sb.append(elements[i]);
          }
  
          sb.append(" ]");
  
          return sb.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