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 BinaryBuffer.java package.html BinaryHeap.java
Date Thu, 01 Jan 2004 19:01:34 GMT
scolebourne    2004/01/01 11:01:34

  Modified:    collections/src/test/org/apache/commons/collections/buffer
                        TestAll.java
               collections/src/java/org/apache/commons/collections/buffer
                        package.html
  Added:       collections/src/test/org/apache/commons/collections/buffer
                        TestBinaryBuffer.java
               collections/src/java/org/apache/commons/collections/buffer
                        BinaryBuffer.java
  Removed:     collections/src/test/org/apache/commons/collections/buffer
                        TestBinaryHeap.java
               collections/src/java/org/apache/commons/collections/buffer
                        BinaryHeap.java
  Log:
  Rename BinaryHeap to BinaryBuffer
  Remove PriorityQueue interface
  
  Revision  Changes    Path
  1.3       +3 -3      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.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- TestAll.java	29 Nov 2003 18:04:56 -0000	1.2
  +++ TestAll.java	1 Jan 2004 19:01:34 -0000	1.3
  @@ -83,7 +83,7 @@
       public static Test suite() {
           TestSuite suite = new TestSuite();
           
  -        suite.addTest(TestBinaryHeap.suite());
  +        suite.addTest(TestBinaryBuffer.suite());
           suite.addTest(TestBlockingBuffer.suite());
           suite.addTest(TestBoundedFifoBuffer.suite());
           suite.addTest(TestBoundedFifoBuffer2.suite());
  
  
  
  1.1                  jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestBinaryBuffer.java
  
  Index: TestBinaryBuffer.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestBinaryBuffer.java,v
1.1 2004/01/01 19:01:34 scolebourne Exp $
   * ====================================================================
   *
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2001-2003 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 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 BinaryHeap.
   * 
   * @version $Revision: 1.1 $ $Date: 2004/01/01 19:01:34 $
   * 
   * @author Michael A. Smith
   */
  public class TestBinaryBuffer extends AbstractTestCollection {
  
      public static void main(String[] args) {
          junit.textui.TestRunner.run(suite());
      }
  
      public static Test suite() {
          return new TestSuite(TestBinaryBuffer.class);
      }
  
      public TestBinaryBuffer(String testName) {
          super(testName);
      }
  
      //-----------------------------------------------------------------------  
      public void verify() {
          super.verify();
          BinaryBuffer heap = (BinaryBuffer) 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 BinaryBuffer();
      }
  
      //-----------------------------------------------------------------------  
      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() {
          BinaryBuffer heap = new BinaryBuffer();
  
          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() {
          BinaryBuffer heap = new BinaryBuffer(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) {}
      }
  
  //    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();
  //    }
      
  }
  
  
  
  1.6       +5 -6      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.5
  retrieving revision 1.6
  diff -u -r1.5 -r1.6
  --- package.html	11 Dec 2003 23:15:12 -0000	1.5
  +++ package.html	1 Jan 2004 19:01:34 -0000	1.6
  @@ -1,15 +1,14 @@
   <BODY>
   <p>
   This package contains implementations of the
  -{@link org.apache.commons.collections.Buffer Buffer} and
  -{@link org.apache.commons.collections.PriorityQueue PriorityQueue} interfaces.
  +{@link org.apache.commons.collections.Buffer Buffer} interface.
   <p>
   The following implementations are provided in the package:
   <ul>
  -<li>BinaryHeap - implements both Buffer and PriorityQueue
  -<li>BoundedBuffer - implements a buffer with a fixed size that throws exceptions
when full
  -<li>CircularBuffer - implements a buffer with a fixed size that discards oldest when
full
  -<li>UnboundedBuffer - implements a buffer that grows in size if necessary
  +<li>BinaryBuffer - provides for removal based on a comparator ordering (priority
queue)
  +<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
   </ul>
   <p>
   The following decorators are provided in the package:
  
  
  
  1.1                  jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/BinaryBuffer.java
  
  Index: BinaryBuffer.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/BinaryBuffer.java,v
1.1 2004/01/01 19:01:34 scolebourne Exp $
   * ====================================================================
   *
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2001-2003 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>BinaryBuffer</code>:
   *
   * <pre>
   * Buffer heap = SynchronizedBuffer.decorate(new BinaryBuffer());
   * </pre>
   *
   * @since Commons Collections 3.0 (previously BinaryHeap v1.0)
   * @version $Revision: 1.1 $ $Date: 2004/01/01 19:01:34 $
   * 
   * @author Peter Donald
   * @author Ram Chidambaram
   * @author Michael A. Smith
   * @author Paul Jack
   * @author Stephen Colebourne
   */
  public class BinaryBuffer extends AbstractCollection implements Buffer {
  
      /**
       * The default capacity for a binary heap.
       */
      private static final int DEFAULT_CAPACITY = 13;
      
      /**
       * The elements in this heap.
       */
      protected Object[] elements;
      /**
       * The number of elements currently in this heap.
       */
      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 BinaryBuffer() {
          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 BinaryBuffer(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 BinaryBuffer(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 BinaryBuffer(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 BinaryBuffer(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 BinaryBuffer(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 BinaryBuffer(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 BinaryBuffer(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 top.
       * Assume it is a minimum 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 top.
       * Assume 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 bottom.
       * Assume it is a minimum heap.
       *
       * @param element the element
       */
      protected void percolateUpMinHeap(final Object element) {
          int hole = ++size;
  
          elements[hole] = element;
  
          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 element up heap from bottom.
       * Assume it is a maximum heap.
       *
       * @param element the element
       */
      protected void percolateUpMaxHeap(final Object element) {
          int hole = ++size;
  
          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;
      }
  
      /**
       * 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) {
                      //percolate top element to it's place in tree
                      if (ascendingOrder) {
                          percolateDownMinHeap(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