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 UnboundedFifoBuffer.java BinaryHeap.java CircularFifoBuffer.java BoundedFifoBuffer.java
Date Sat, 29 Nov 2003 18:04:57 GMT
scolebourne    2003/11/29 10:04:57

  Modified:    collections/src/test/org/apache/commons/collections/buffer
                        TestAll.java
               collections/src/java/org/apache/commons/collections
                        UnboundedFifoBuffer.java BinaryHeap.java
                        CircularFifoBuffer.java BoundedFifoBuffer.java
  Added:       collections/src/test/org/apache/commons/collections/buffer
                        TestBinaryHeap.java TestUnboundedFifoBuffer.java
                        TestBoundedFifoBuffer.java
                        TestCircularFifoBuffer.java
                        TestBoundedFifoBuffer2.java
               collections/src/java/org/apache/commons/collections/buffer
                        BoundedFifoBuffer.java UnboundedFifoBuffer.java
                        CircularFifoBuffer.java BinaryHeap.java
  Log:
  Refactor Buffer implementations to buffer subpackage
  
  Revision  Changes    Path
  1.2       +7 -2      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.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- TestAll.java	16 Nov 2003 00:05:46 -0000	1.1
  +++ TestAll.java	29 Nov 2003 18:04:56 -0000	1.2
  @@ -83,9 +83,14 @@
       public static Test suite() {
           TestSuite suite = new TestSuite();
           
  +        suite.addTest(TestBinaryHeap.suite());
           suite.addTest(TestBlockingBuffer.suite());
  +        suite.addTest(TestBoundedFifoBuffer.suite());
  +        suite.addTest(TestBoundedFifoBuffer2.suite());
  +        suite.addTest(TestCircularFifoBuffer.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/TestBinaryHeap.java
  
  Index: TestBinaryHeap.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestBinaryHeap.java,v 1.1 2003/11/29 18:04:56 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 java.util.NoSuchElementException;
  
  import junit.framework.Test;
  import junit.framework.TestSuite;
  
  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: 2003/11/29 18:04:56 $
   * 
   * @author Michael A. Smith
   */
  public class TestBinaryHeap extends AbstractTestCollection {
  
      public static Test suite() {
          return new TestSuite(TestBinaryHeap.class);
      }
  
      public TestBinaryHeap(String testName) {
          super(testName);
      }
  
      //-----------------------------------------------------------------------  
      public void verify() {
          super.verify();
          BinaryHeap heap = (BinaryHeap) collection;
  
          Comparator c = heap.m_comparator;
          if (c == null)
              c = ComparatorUtils.naturalComparator();
          if (!heap.m_isMinHeap)
              c = ComparatorUtils.reversedComparator(c);
  
          Object[] tree = heap.m_elements;
          for (int i = 1; i <= heap.m_size; i++) {
              Object parent = tree[i];
              if (i * 2 <= heap.m_size) {
                  assertTrue("Parent is less than or equal to its left child", c.compare(parent, tree[i * 2]) <= 0);
              }
              if (i * 2 + 1 < heap.m_size) {
                  assertTrue("Parent is less than or equal to its right child", c.compare(parent, tree[i * 2 + 1]) <= 0);
              }
          }
      }
  
      //-----------------------------------------------------------------------  
      /**
       * Overridden because UnboundedFifoBuffer 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 BinaryHeap();
      }
  
      //-----------------------------------------------------------------------  
      public Object[] getFullElements() {
          return getFullNonNullStringElements();
      }
  
      public Object[] getOtherElements() {
          return getOtherNonNullStringElements();
      }
  
      //-----------------------------------------------------------------------  
      public void testBasicOps() {
          BinaryHeap heap = new BinaryHeap();
  
          assertTrue("heap should be empty after create", heap.isEmpty());
  
          try {
              heap.peek();
              fail("NoSuchElementException should be thrown if peek is called before any elements are inserted");
          } catch (NoSuchElementException e) {
              // expected
          }
  
          try {
              heap.pop();
              fail("NoSuchElementException should be thrown if pop is called before any elements are inserted");
          } catch (NoSuchElementException e) {
              // expected
          }
  
          heap.insert("a");
          heap.insert("c");
          heap.insert("e");
          heap.insert("b");
          heap.insert("d");
          heap.insert("n");
          heap.insert("m");
          heap.insert("l");
          heap.insert("k");
          heap.insert("j");
          heap.insert("i");
          heap.insert("h");
          heap.insert("g");
          heap.insert("f");
  
          assertTrue("heap should not be empty after inserts", !heap.isEmpty());
  
          for (int i = 0; i < 14; i++) {
              assertEquals(
                  "peek using default constructor should return minimum value in the binary heap",
                  String.valueOf((char) ('a' + i)),
                  heap.peek());
  
              assertEquals(
                  "pop using default constructor should return minimum value in the binary heap",
                  String.valueOf((char) ('a' + i)),
                  heap.pop());
  
              if (i + 1 < 14) {
                  assertTrue("heap should not be empty before all elements are popped", !heap.isEmpty());
              } else {
                  assertTrue("heap should be empty after all elements are popped", heap.isEmpty());
              }
          }
  
          try {
              heap.peek();
              fail("NoSuchElementException should be thrown if peek is called after all elements are popped");
          } catch (NoSuchElementException e) {
              // expected
          }
  
          try {
              heap.pop();
              fail("NoSuchElementException should be thrown if pop is called after all elements are popped");
          } catch (NoSuchElementException e) {
              // expected
          }
      }
  
      public void testBasicComparatorOps() {
          BinaryHeap heap = new BinaryHeap(new ReverseComparator(new ComparableComparator()));
  
          assertTrue("heap should be empty after create", heap.isEmpty());
  
          try {
              heap.peek();
              fail("NoSuchElementException should be thrown if peek is called before any elements are inserted");
          } catch (NoSuchElementException e) {
              // expected
          }
  
          try {
              heap.pop();
              fail("NoSuchElementException should be thrown if pop is called before any elements are inserted");
          } catch (NoSuchElementException e) {
              // expected
          }
  
          heap.insert("a");
          heap.insert("c");
          heap.insert("e");
          heap.insert("b");
          heap.insert("d");
          heap.insert("n");
          heap.insert("m");
          heap.insert("l");
          heap.insert("k");
          heap.insert("j");
          heap.insert("i");
          heap.insert("h");
          heap.insert("g");
          heap.insert("f");
  
          assertTrue("heap should not be empty after inserts", !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(
                  "peek using default constructor should return minimum value in the binary heap",
                  String.valueOf((char) ('n' - i)),
                  heap.peek());
  
              assertEquals(
                  "pop using default constructor should return minimum value in the binary heap",
                  String.valueOf((char) ('n' - i)),
                  heap.pop());
  
              if (i + 1 < 14) {
                  assertTrue("heap should not be empty before all elements are popped", !heap.isEmpty());
              } else {
                  assertTrue("heap should be empty after all elements are popped", heap.isEmpty());
              }
          }
  
          try {
              heap.peek();
              fail("NoSuchElementException should be thrown if peek is called after all elements are popped");
          } catch (NoSuchElementException e) {
              // expected
          }
  
          try {
              heap.pop();
              fail("NoSuchElementException should be thrown if pop is called after all elements are popped");
          } catch (NoSuchElementException e) {
              // expected
          }
      }
  
  }
  
  
  
  1.1                  jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestUnboundedFifoBuffer.java
  
  Index: TestUnboundedFifoBuffer.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestUnboundedFifoBuffer.java,v 1.1 2003/11/29 18:04:56 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.Collection;
  import java.util.Iterator;
  
  import junit.framework.Test;
  
  import org.apache.commons.collections.BulkTest;
  import org.apache.commons.collections.collection.AbstractTestCollection;
  
  /**
   * Test cases for UnboundedFifoBuffer.
   * 
   * @version $Revision: 1.1 $ $Date: 2003/11/29 18:04:56 $
   * 
   * @author Unknown
   */
  public class TestUnboundedFifoBuffer extends AbstractTestCollection {
  
      public TestUnboundedFifoBuffer(String n) {
          super(n);
      }
  
      public static Test suite() {
          return BulkTest.makeSuite(TestUnboundedFifoBuffer.class);
      }
  
      //-----------------------------------------------------------------------
      /**
       *  Verifies that the ArrayList has the same elements in the same 
       *  sequence as the UnboundedFifoBuffer.
       */
      public void verify() {
          super.verify();
          Iterator iterator1 = collection.iterator();
          Iterator iterator2 = confirmed.iterator();
          while (iterator2.hasNext()) {
              assertTrue(iterator1.hasNext());
              Object o1 = iterator1.next();
              Object o2 = iterator2.next();
              assertEquals(o1, o2);
          }
      }
  
      //-----------------------------------------------------------------------
      /**
       * Overridden because UnboundedFifoBuffer doesn't allow null elements.
       * @return false
       */
      public boolean isNullSupported() {
          return false;
      }
  
      /**
       * Overridden because UnboundedFifoBuffer isn't fail fast.
       * @return false
       */
      public boolean isFailFastSupported() {
          return false;
      }
  
      //-----------------------------------------------------------------------
      /**
       *  Returns an empty ArrayList.
       *
       *  @return an empty ArrayList
       */
      public Collection makeConfirmedCollection() {
          return new ArrayList();
      }
  
      /**
       *  Returns a full ArrayList.
       *
       *  @return a full ArrayList
       */
      public Collection makeConfirmedFullCollection() {
          Collection c = makeConfirmedCollection();
          c.addAll(java.util.Arrays.asList(getFullElements()));
          return c;
      }
  
      /**
       *  Returns an empty UnboundedFifoBuffer with a small capacity.
       *
       *  @return an empty UnboundedFifoBuffer
       */
      public Collection makeCollection() {
          return new UnboundedFifoBuffer(5);
      }
  
      //-----------------------------------------------------------------------
      /**
       *  Tests that UnboundedFifoBuffer removes elements in the right order.
       */
      public void testUnboundedFifoBufferRemove() {
          resetFull();
          int size = confirmed.size();
          for (int i = 0; i < size; i++) {
              Object o1 = ((UnboundedFifoBuffer)collection).remove();
              Object o2 = ((ArrayList)confirmed).remove(0);
              assertEquals("Removed objects should be equal", o1, o2);
              verify();
          }
      }
  
      /**
       * Tests that the constructor correctly throws an exception.
       */
      public void testConstructorException1() {
          try {
              new UnboundedFifoBuffer(0);
          } catch (IllegalArgumentException ex) {
              return;
          }
          fail();
      }
      
      /**
       * Tests that the constructor correctly throws an exception.
       */
      public void testConstructorException2() {
          try {
              new UnboundedFifoBuffer(-20);
          } catch (IllegalArgumentException ex) {
              return;
          }
          fail();
      }
  }
  
  
  
  
  1.1                  jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestBoundedFifoBuffer.java
  
  Index: TestBoundedFifoBuffer.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestBoundedFifoBuffer.java,v 1.1 2003/11/29 18:04:56 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.Collection;
  import java.util.Iterator;
  
  import junit.framework.Test;
  
  import org.apache.commons.collections.BufferUnderflowException;
  import org.apache.commons.collections.BulkTest;
  import org.apache.commons.collections.collection.AbstractTestCollection;
  
  /**
   * Test cases for BoundedFifoBuffer.
   * 
   * @version $Revision: 1.1 $ $Date: 2003/11/29 18:04:56 $
   * 
   * @author Paul Jack
   */
  public class TestBoundedFifoBuffer extends AbstractTestCollection {
  
      public TestBoundedFifoBuffer(String n) {
          super(n);
      }
  
      public static Test suite() {
          return BulkTest.makeSuite(TestBoundedFifoBuffer.class);
      }
  
      //-----------------------------------------------------------------------
      /**
       *  Runs through the regular verifications, but also verifies that 
       *  the buffer contains the same elements in the same sequence as the
       *  list.
       */
      public void verify() {
          super.verify();
          Iterator iterator1 = collection.iterator();
          Iterator iterator2 = confirmed.iterator();
          while (iterator2.hasNext()) {
              assertTrue(iterator1.hasNext());
              Object o1 = iterator1.next();
              Object o2 = iterator2.next();
              assertEquals(o1, o2);
          }
      }
  
      //-----------------------------------------------------------------------
      /**
       * Overridden because UnboundedFifoBuffer doesn't allow null elements.
       * @return false
       */
      public boolean isNullSupported() {
          return false;
      }
  
      /**
       * Overridden because UnboundedFifoBuffer isn't fail fast.
       * @return false
       */
      public boolean isFailFastSupported() {
          return false;
      }
  
      //-----------------------------------------------------------------------  
      /**
       *  Returns an empty ArrayList.
       *
       *  @return an empty ArrayList
       */
      public Collection makeConfirmedCollection() {
          return new ArrayList();
      }
  
      /**
       *  Returns a full ArrayList.
       *
       *  @return a full ArrayList
       */
      public Collection makeConfirmedFullCollection() {
          Collection c = makeConfirmedCollection();
          c.addAll(java.util.Arrays.asList(getFullElements()));
          return c;
      }
  
      /**
       *  Returns an empty BoundedFifoBuffer that won't overflow.  
       *  
       *  @return an empty BoundedFifoBuffer
       */
      public Collection makeCollection() {
          return new BoundedFifoBuffer(100);
      }
  
      //-----------------------------------------------------------------------  
      /**
       * Tests that the removal operation actually removes the first element.
       */
      public void testBoundedFifoBufferRemove() {
          resetFull();
          int size = confirmed.size();
          for (int i = 0; i < size; i++) {
              Object o1 = ((BoundedFifoBuffer)collection).remove();
              Object o2 = ((ArrayList)confirmed).remove(0);
              assertEquals("Removed objects should be equal", o1, o2);
              verify();
          }
  
          try {
              ((BoundedFifoBuffer)collection).remove();
              fail("Empty buffer should raise Underflow.");
          } catch (BufferUnderflowException e) {
              // expected
          }
      }
  
      /**
       * Tests that the constructor correctly throws an exception.
       */
      public void testConstructorException1() {
          try {
              new BoundedFifoBuffer(0);
          } catch (IllegalArgumentException ex) {
              return;
          }
          fail();
      }
      
      /**
       * Tests that the constructor correctly throws an exception.
       */
      public void testConstructorException2() {
          try {
              new BoundedFifoBuffer(-20);
          } catch (IllegalArgumentException ex) {
              return;
          }
          fail();
      }
  
      /**
       * Tests that the constructor correctly throws an exception.
       */
      public void testConstructorException3() {
          try {
              new BoundedFifoBuffer(null);
          } catch (NullPointerException ex) {
              return;
          }
          fail();
      }
  }
  
  
  
  1.1                  jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestCircularFifoBuffer.java
  
  Index: TestCircularFifoBuffer.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestCircularFifoBuffer.java,v 1.1 2003/11/29 18:04:56 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.Collection;
  import java.util.Iterator;
  import java.util.List;
  
  import junit.framework.Test;
  
  import org.apache.commons.collections.Buffer;
  import org.apache.commons.collections.BufferUnderflowException;
  import org.apache.commons.collections.BulkTest;
  import org.apache.commons.collections.collection.AbstractTestCollection;
  
  /**
   * Test cases for CircularFifoBuffer.
   * 
   * @version $Revision: 1.1 $ $Date: 2003/11/29 18:04:56 $
   * 
   * @author Stephen Colebourne
   */
  public class TestCircularFifoBuffer extends AbstractTestCollection {
  
      public TestCircularFifoBuffer(String n) {
          super(n);
      }
  
      public static Test suite() {
          return BulkTest.makeSuite(TestCircularFifoBuffer.class);
      }
  
      //-----------------------------------------------------------------------
      /**
       *  Runs through the regular verifications, but also verifies that 
       *  the buffer contains the same elements in the same sequence as the
       *  list.
       */
      public void verify() {
          super.verify();
          Iterator iterator1 = collection.iterator();
          Iterator iterator2 = confirmed.iterator();
          while (iterator2.hasNext()) {
              assertTrue(iterator1.hasNext());
              Object o1 = iterator1.next();
              Object o2 = iterator2.next();
              assertEquals(o1, o2);
          }
      }
  
      //-----------------------------------------------------------------------
      /**
       * Overridden because UnboundedFifoBuffer doesn't allow null elements.
       * @return false
       */
      public boolean isNullSupported() {
          return false;
      }
  
      /**
       * Overridden because UnboundedFifoBuffer isn't fail fast.
       * @return false
       */
      public boolean isFailFastSupported() {
          return false;
      }
  
      //-----------------------------------------------------------------------
      /**
       * Returns an empty ArrayList.
       *
       * @return an empty ArrayList
       */
      public Collection makeConfirmedCollection() {
          return new ArrayList();
      }
  
      /**
       * Returns a full ArrayList.
       *
       * @return a full ArrayList
       */
      public Collection makeConfirmedFullCollection() {
          Collection c = makeConfirmedCollection();
          c.addAll(java.util.Arrays.asList(getFullElements()));
          return c;
      }
  
      /**
       * Returns an empty BoundedFifoBuffer that won't overflow.  
       *  
       * @return an empty BoundedFifoBuffer
       */
      public Collection makeCollection() {
          return new CircularFifoBuffer(100);
      }
  
      //-----------------------------------------------------------------------
      /**
       * Tests that the removal operation actually removes the first element.
       */
      public void testCircularFifoBufferCircular() {
          List list = new ArrayList();
          list.add("A");
          list.add("B");
          list.add("C");
          Buffer buf = new CircularFifoBuffer(list);
          
          assertEquals(true, buf.contains("A"));
          assertEquals(true, buf.contains("B"));
          assertEquals(true, buf.contains("C"));
          
          buf.add("D");
          
          assertEquals(false, buf.contains("A"));
          assertEquals(true, buf.contains("B"));
          assertEquals(true, buf.contains("C"));
          assertEquals(true, buf.contains("D"));
          
          assertEquals("B", buf.get());
          assertEquals("B", buf.remove());
          assertEquals("C", buf.remove());
          assertEquals("D", buf.remove());
      }
  
      /**
       * Tests that the removal operation actually removes the first element.
       */
      public void testCircularFifoBufferRemove() {
          resetFull();
          int size = confirmed.size();
          for (int i = 0; i < size; i++) {
              Object o1 = ((CircularFifoBuffer) collection).remove();
              Object o2 = ((ArrayList) confirmed).remove(0);
              assertEquals("Removed objects should be equal", o1, o2);
              verify();
          }
  
          try {
              ((CircularFifoBuffer) collection).remove();
              fail("Empty buffer should raise Underflow.");
          } catch (BufferUnderflowException e) {
              // expected
          }
      }
  
      /**
       * Tests that the constructor correctly throws an exception.
       */
      public void testConstructorException1() {
          try {
              new CircularFifoBuffer(0);
          } catch (IllegalArgumentException ex) {
              return;
          }
          fail();
      }
  
      /**
       * Tests that the constructor correctly throws an exception.
       */
      public void testConstructorException2() {
          try {
              new CircularFifoBuffer(-20);
          } catch (IllegalArgumentException ex) {
              return;
          }
          fail();
      }
      
      /**
       * Tests that the constructor correctly throws an exception.
       */
      public void testConstructorException3() {
          try {
              new CircularFifoBuffer(null);
          } catch (NullPointerException ex) {
              return;
          }
          fail();
      }
  }
  
  
  
  1.1                  jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestBoundedFifoBuffer2.java
  
  Index: TestBoundedFifoBuffer2.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestBoundedFifoBuffer2.java,v 1.1 2003/11/29 18:04:56 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.Arrays;
  import java.util.Collection;
  
  import junit.framework.Test;
  
  import org.apache.commons.collections.BufferOverflowException;
  import org.apache.commons.collections.BulkTest;
  import org.apache.commons.collections.collection.BoundedCollection;
  
  /**
   * Runs tests against a full BoundedFifoBuffer, since many of the algorithms
   * differ depending on whether the fifo is full or not.
   * 
   * @version $Revision: 1.1 $ $Date: 2003/11/29 18:04:56 $
   * 
   * @author Unknown
   */
  public class TestBoundedFifoBuffer2 extends TestBoundedFifoBuffer {
  
      public TestBoundedFifoBuffer2(String n) {
          super(n);
      }
  
      public static Test suite() {
          return BulkTest.makeSuite(TestBoundedFifoBuffer2.class);
      }
  
      /**
       *  Returns a BoundedFifoBuffer that's filled to capacity.
       *  Any attempt to add to the returned buffer will result in a 
       *  BufferOverflowException.
       *
       *  @return a full BoundedFifoBuffer
       */
      public Collection makeFullCollection() {
          return new BoundedFifoBuffer(Arrays.asList(getFullElements()));
      }
  
  
      /**
       *  Overridden to skip the add tests.  All of them would fail with a 
       *  BufferOverflowException.
       *
       *  @return false
       */
      public boolean isAddSupported() {
          return false;
      }
  
  
      /**
       *  Overridden because the add operations raise BufferOverflowException
       *  instead of UnsupportedOperationException.
       */
      public void testUnsupportedAdd() {
      }
  
  
      /**
       *  Tests to make sure the add operations raise BufferOverflowException.
       */
      public void testBufferOverflow() {
          resetFull();
          try {
              collection.add(getOtherElements()[0]);
              fail("add should raise BufferOverflow.");
          } catch (BufferOverflowException e) {
              // expected
          }
          verify();
  
          try {
              collection.addAll(Arrays.asList(getOtherElements()));
              fail("addAll should raise BufferOverflow.");
          } catch (BufferOverflowException e) {
              // expected
          }
          verify();
      }
  
      /**
       * Tests is full
       */
      public void testIsFull() {
          resetFull();
          assertEquals(true, ((BoundedCollection) collection).isFull());
          ((BoundedFifoBuffer) collection).remove();
          assertEquals(false, ((BoundedCollection) collection).isFull());
          ((BoundedFifoBuffer) collection).add("jj");
          assertEquals(true, ((BoundedCollection) collection).isFull());
      }
  
      /**
       * Tests max size
       */
      public void testMaxSize() {
          resetFull();
          assertEquals(getFullElements().length, ((BoundedCollection) collection).maxSize());
          ((BoundedFifoBuffer) collection).remove();
          assertEquals(getFullElements().length, ((BoundedCollection) collection).maxSize());
          ((BoundedFifoBuffer) collection).add("jj");
          assertEquals(getFullElements().length, ((BoundedCollection) collection).maxSize());
      }
  
  }
  
  
  
  
  1.1                  jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/BoundedFifoBuffer.java
  
  Index: BoundedFifoBuffer.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/BoundedFifoBuffer.java,v 1.1 2003/11/29 18:04:57 scolebourne Exp $
   * ====================================================================
   *
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2002-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.Arrays;
  import java.util.Collection;
  import java.util.Iterator;
  import java.util.NoSuchElementException;
  
  import org.apache.commons.collections.Buffer;
  import org.apache.commons.collections.BufferOverflowException;
  import org.apache.commons.collections.BufferUnderflowException;
  import org.apache.commons.collections.collection.BoundedCollection;
  
  /**
   * The BoundedFifoBuffer is a <strong>very</strong> efficient implementation of
   * Buffer that does not alter the size of the buffer at runtime.
   * <p>
   * The removal order of a <code>BoundedFifoBuffer</code> is based on the 
   * insertion order; elements are removed in the same order in which they
   * were added.  The iteration order is the same as the removal order.
   * <p>
   * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations
   * all perform in constant time.  All other operations perform in linear
   * time or worse.
   * <p>
   * Note that this implementation is not synchronized.  The following can be
   * used to provide synchronized access to your <code>BoundedFifoBuffer</code>:
   * <pre>
   *   Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer());
   * </pre>
   * <p>
   * This buffer prevents null objects from being added.
   *
   * @since Commons Collections 3.0
   * @version $Revision: 1.1 $ $Date: 2003/11/29 18:04:57 $
   * 
   * @author Avalon
   * @author Berin Loritsch
   * @author Paul Jack
   * @author Stephen Colebourne
   * @author Herve Quiroz
   */
  public class BoundedFifoBuffer extends AbstractCollection
          implements Buffer, BoundedCollection {
              
      private final Object[] m_elements;
      private int m_start = 0;
      private int m_end = 0;
      private boolean m_full = false;
      private final int maxElements;
  
      /**
       * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
       * 32 elements.
       */
      public BoundedFifoBuffer() {
          this(32);
      }
  
      /**
       * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
       * the specified number of elements.
       *
       * @param size  the maximum number of elements for this fifo
       * @throws IllegalArgumentException  if the size is less than 1
       */
      public BoundedFifoBuffer(int size) {
          if (size <= 0) {
              throw new IllegalArgumentException("The size must be greater than 0");
          }
          m_elements = new Object[size];
          maxElements = m_elements.length;
      }
  
      /**
       * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold all
       * of the elements in the specified collection. That collection's
       * elements will also be added to the buffer.
       *
       * @param coll  the collection whose elements to add, may not be null
       * @throws NullPointerException if the collection is null
       */
      public BoundedFifoBuffer(Collection coll) {
          this(coll.size());
          addAll(coll);
      }
  
      /**
       * Returns the number of elements stored in the buffer.
       *
       * @return this buffer's size
       */
      public int size() {
          int size = 0;
  
          if (m_end < m_start) {
              size = maxElements - m_start + m_end;
          } else if (m_end == m_start) {
              size = (m_full ? maxElements : 0);
          } else {
              size = m_end - m_start;
          }
  
          return size;
      }
  
      /**
       * Returns true if this buffer is empty; false otherwise.
       *
       * @return true if this buffer is empty
       */
      public boolean isEmpty() {
          return size() == 0;
      }
  
      /**
       * Returns true if this collection is full and no new elements can be added.
       *
       * @return <code>true</code> if the collection is full
       */
      public boolean isFull() {
          return size() == maxElements;
      }
      
      /**
       * Gets the maximum size of the collection (the bound).
       *
       * @return the maximum number of elements the collection can hold
       */
      public int maxSize() {
          return maxElements;
      }
      
      /**
       * Clears this buffer.
       */
      public void clear() {
          m_full = false;
          m_start = 0;
          m_end = 0;
          Arrays.fill(m_elements, null);
      }
  
      /**
       * Adds the given element to this buffer.
       *
       * @param element  the element to add
       * @return true, always
       * @throws NullPointerException  if the given element is null
       * @throws BufferOverflowException  if this buffer is full
       */
      public boolean add(Object element) {
          if (null == element) {
              throw new NullPointerException("Attempted to add null object to buffer");
          }
  
          if (m_full) {
              throw new BufferOverflowException("The buffer cannot hold more than " + maxElements + " objects.");
          }
  
          m_elements[m_end++] = element;
  
          if (m_end >= maxElements) {
              m_end = 0;
          }
  
          if (m_end == m_start) {
              m_full = true;
          }
  
          return true;
      }
  
      /**
       * Returns the least recently inserted element in this buffer.
       *
       * @return the least recently inserted element
       * @throws BufferUnderflowException  if the buffer is empty
       */
      public Object get() {
          if (isEmpty()) {
              throw new BufferUnderflowException("The buffer is already empty");
          }
  
          return m_elements[m_start];
      }
  
      /**
       * Removes the least recently inserted element from this buffer.
       *
       * @return the least recently inserted element
       * @throws BufferUnderflowException  if the buffer is empty
       */
      public Object remove() {
          if (isEmpty()) {
              throw new BufferUnderflowException("The buffer is already empty");
          }
  
          Object element = m_elements[m_start];
  
          if (null != element) {
              m_elements[m_start++] = null;
  
              if (m_start >= maxElements) {
                  m_start = 0;
              }
  
              m_full = false;
          }
  
          return element;
      }
  
      /**
       * Increments the internal index.
       * 
       * @param index  the index to increment
       * @return the updated index
       */
      private int increment(int index) {
          index++; 
          if (index >= maxElements) {
              index = 0;
          }
          return index;
      }
  
      /**
       * Decrements the internal index.
       * 
       * @param index  the index to decrement
       * @return the updated index
       */
      private int decrement(int index) {
          index--;
          if (index < 0) {
              index = maxElements - 1;
          }
          return index;
      }
  
      /**
       * Returns an iterator over this buffer's elements.
       *
       * @return an iterator over this buffer's elements
       */
      public Iterator iterator() {
          return new Iterator() {
  
              private int index = m_start;
              private int lastReturnedIndex = -1;
              private boolean isFirst = m_full;
  
              public boolean hasNext() {
                  return isFirst || (index != m_end);
                  
              }
  
              public Object next() {
                  if (!hasNext()) throw new NoSuchElementException();
                  isFirst = false;
                  lastReturnedIndex = index;
                  index = increment(index);
                  return m_elements[lastReturnedIndex];
              }
  
              public void remove() {
                  if (lastReturnedIndex == -1) throw new IllegalStateException();
  
                  // First element can be removed quickly
                  if (lastReturnedIndex == m_start) {
                      BoundedFifoBuffer.this.remove();
                      lastReturnedIndex = -1;
                      return;
                  }
  
                  // Other elements require us to shift the subsequent elements
                  int i = lastReturnedIndex + 1;
                  while (i != m_end) {
                      if (i >= maxElements) {
                          m_elements[i - 1] = m_elements[0];
                          i = 0;
                      } else {
                          m_elements[i - 1] = m_elements[i];
                          i++;
                      }
                  }
  
                  lastReturnedIndex = -1;
                  m_end = decrement(m_end);
                  m_elements[m_end] = null;
                  m_full = false;
                  index = decrement(index);
              }
  
          };
      }
  
  }
  
  
  
  1.1                  jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/UnboundedFifoBuffer.java
  
  Index: UnboundedFifoBuffer.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/UnboundedFifoBuffer.java,v 1.1 2003/11/29 18:04:57 scolebourne Exp $
   * ====================================================================
   *
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2002-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.Iterator;
  import java.util.NoSuchElementException;
  
  import org.apache.commons.collections.Buffer;
  import org.apache.commons.collections.BufferUnderflowException;
  
  /**
   * UnboundedFifoBuffer is a <strong>very</strong> efficient buffer implementation.
   * According to performance testing, it exhibits a constant access time, but it
   * also outperforms ArrayList when used for the same purpose.
   * <p>
   * The removal order of an <code>UnboundedFifoBuffer</code> is based on the insertion
   * order; elements are removed in the same order in which they were added.
   * The iteration order is the same as the removal order.
   * <p>
   * The {@link #remove()} and {@link #get()} operations perform in constant time.
   * The {@link #add(Object)} operation performs in amortized constant time.  All
   * other operations perform in linear time or worse.
   * <p>
   * Note that this implementation is not synchronized.  The following can be
   * used to provide synchronized access to your <code>UnboundedFifoBuffer</code>:
   * <pre>
   *   Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoBuffer());
   * </pre>
   * <p>
   * This buffer prevents null objects from being added.
   * 
   * @since Commons Collections 3.0
   * @version $Revision: 1.1 $ $Date: 2003/11/29 18:04:57 $
   *
   * @author Avalon
   * @author Federico Barbieri
   * @author Berin Loritsch
   * @author Paul Jack
   * @author Stephen Colebourne
   */
  public class UnboundedFifoBuffer extends AbstractCollection implements Buffer {
      
      protected Object[] m_buffer;
      protected int m_head;
      protected int m_tail;
  
      /**
       * Constructs an UnboundedFifoBuffer with the default number of elements.
       * It is exactly the same as performing the following:
       *
       * <pre>
       *   new UnboundedFifoBuffer(32);
       * </pre>
       */
      public UnboundedFifoBuffer() {
          this(32);
      }
  
      /**
       * Constructs an UnboundedFifoBuffer with the specified number of elements.
       * The integer must be a positive integer.
       * 
       * @param initialSize  the initial size of the buffer
       * @throws IllegalArgumentException  if the size is less than 1
       */
      public UnboundedFifoBuffer(int initialSize) {
          if (initialSize <= 0) {
              throw new IllegalArgumentException("The size must be greater than 0");
          }
          m_buffer = new Object[initialSize + 1];
          m_head = 0;
          m_tail = 0;
      }
  
      /**
       * Returns the number of elements stored in the buffer.
       *
       * @return this buffer's size
       */
      public int size() {
          int size = 0;
  
          if (m_tail < m_head) {
              size = m_buffer.length - m_head + m_tail;
          } else {
              size = m_tail - m_head;
          }
  
          return size;
      }
  
      /**
       * Returns true if this buffer is empty; false otherwise.
       *
       * @return true if this buffer is empty
       */
      public boolean isEmpty() {
          return (size() == 0);
      }
  
      /**
       * Adds the given element to this buffer.
       *
       * @param obj  the element to add
       * @return true, always
       * @throws NullPointerException  if the given element is null
       * @throws BufferOverflowException  if this buffer is full
       */
      public boolean add(final Object obj) {
          if (obj == null) {
              throw new NullPointerException("Attempted to add null object to buffer");
          }
  
          if (size() + 1 >= m_buffer.length) {
              Object[] tmp = new Object[((m_buffer.length - 1) * 2) + 1];
  
              int j = 0;
              for (int i = m_head; i != m_tail;) {
                  tmp[j] = m_buffer[i];
                  m_buffer[i] = null;
  
                  j++;
                  i++;
                  if (i == m_buffer.length) {
                      i = 0;
                  }
              }
  
              m_buffer = tmp;
              m_head = 0;
              m_tail = j;
          }
  
          m_buffer[m_tail] = obj;
          m_tail++;
          if (m_tail >= m_buffer.length) {
              m_tail = 0;
          }
          return true;
      }
  
      /**
       * Returns the next object in the buffer.
       *
       * @return the next object in the buffer
       * @throws BufferUnderflowException  if this buffer is empty
       */
      public Object get() {
          if (isEmpty()) {
              throw new BufferUnderflowException("The buffer is already empty");
          }
  
          return m_buffer[m_head];
      }
  
      /**
       * Removes the next object from the buffer
       *
       * @return the removed object
       * @throws BufferUnderflowException  if this buffer is empty
       */
      public Object remove() {
          if (isEmpty()) {
              throw new BufferUnderflowException("The buffer is already empty");
          }
  
          Object element = m_buffer[m_head];
  
          if (null != element) {
              m_buffer[m_head] = null;
  
              m_head++;
              if (m_head >= m_buffer.length) {
                  m_head = 0;
              }
          }
  
          return element;
      }
  
      /**
       * Increments the internal index.
       * 
       * @param index  the index to increment
       * @return the updated index
       */
      private int increment(int index) {
          index++;
          if (index >= m_buffer.length) {
              index = 0;
          }
          return index;
      }
  
      /**
       * Decrements the internal index.
       * 
       * @param index  the index to decrement
       * @return the updated index
       */
      private int decrement(int index) {
          index--;
          if (index < 0) {
              index = m_buffer.length - 1;
          }
          return index;
      }
  
      /**
       * Returns an iterator over this buffer's elements.
       *
       * @return an iterator over this buffer's elements
       */
      public Iterator iterator() {
          return new Iterator() {
  
              private int index = m_head;
              private int lastReturnedIndex = -1;
  
              public boolean hasNext() {
                  return index != m_tail;
  
              }
  
              public Object next() {
                  if (!hasNext())
                      throw new NoSuchElementException();
                  lastReturnedIndex = index;
                  index = increment(index);
                  return m_buffer[lastReturnedIndex];
              }
  
              public void remove() {
                  if (lastReturnedIndex == -1)
                      throw new IllegalStateException();
  
                  // First element can be removed quickly
                  if (lastReturnedIndex == m_head) {
                      UnboundedFifoBuffer.this.remove();
                      lastReturnedIndex = -1;
                      return;
                  }
  
                  // Other elements require us to shift the subsequent elements
                  int i = lastReturnedIndex + 1;
                  while (i != m_tail) {
                      if (i >= m_buffer.length) {
                          m_buffer[i - 1] = m_buffer[0];
                          i = 0;
                      } else {
                          m_buffer[i - 1] = m_buffer[i];
                          i++;
                      }
                  }
  
                  lastReturnedIndex = -1;
                  m_tail = decrement(m_tail);
                  m_buffer[m_tail] = null;
                  index = decrement(index);
              }
  
          };
      }
      
  }
  
  
  
  1.1                  jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/CircularFifoBuffer.java
  
  Index: CircularFifoBuffer.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/CircularFifoBuffer.java,v 1.1 2003/11/29 18:04:57 scolebourne Exp $
   * ====================================================================
   *
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 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.Collection;
  
  /** 
   * CircularFifoBuffer is a first in first out buffer with a fixed size that
   * replaces its oldest element if full.
   * <p>
   * The removal order of a <code>CircularFifoBuffer</code> is based on the 
   * insertion order; elements are removed in the same order in which they
   * were added.  The iteration order is the same as the removal order.
   * <p>
   * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations
   * all perform in constant time.  All other operations perform in linear
   * time or worse.
   * <p>
   * Note that this implementation is not synchronized.  The following can be
   * used to provide synchronized access to your <code>CircularFifoBuffer</code>:
   * <pre>
   *   Buffer fifo = BufferUtils.synchronizedBuffer(new CircularFifoBuffer());
   * </pre>
   * <p>
   * This buffer prevents null objects from being added.
   * 
   * @since Commons Collections 3.0
   * @version $Revision: 1.1 $ $Date: 2003/11/29 18:04:57 $
   * 
   * @author Stefano Fornari
   * @author Stephen Colebourne
   */
  public class CircularFifoBuffer extends BoundedFifoBuffer {
  
      /**
       * Constructor that creates a buffer with the default size of 32.
       */
      public CircularFifoBuffer() {
          super(32);
      }
  
      /**
       * Constructor that creates a buffer with the specified size.
       * 
       * @param size  the size of the buffer (cannot be changed)
       * @throws IllegalArgumentException  if the size is less than 1
       */
      public CircularFifoBuffer(int size) {
          super(size);
      }
  
      /**
       * Constructor that creates a buffer from the specified collection.
       * The collection size also sets the buffer size
       * 
       * @param coll  the collection to copy into the buffer, may not be null
       * @throws NullPointerException if the collection is null
       */
      public CircularFifoBuffer(Collection coll) {
          super(coll);
      }
  
      /**
       * If the buffer is full, the least recently added element is discarded so
       * that a new element can be inserted.
       *
       * @param element the element to add
       * @return true, always
       */
      public boolean add(Object element) {
          if (isFull()) {
              remove();
          }
          return super.add(element);
      }
      
  }
  
  
  
  1.1                  jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/BinaryHeap.java
  
  Index: BinaryHeap.java
  ===================================================================
  /*
   * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/BinaryHeap.java,v 1.1 2003/11/29 18:04:57 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;
  import org.apache.commons.collections.PriorityQueue;
  
  /**
   * Binary heap implementation of {@link PriorityQueue} and {@link Buffer}.
   * <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>isMinHeap</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 BufferUtils#synchronizedBuffer(Buffer)} to provide
   * synchronized access to a <code>BinaryHeap</code>:
   *
   * <pre>
   * Buffer heap = BufferUtils.synchronizedBuffer(new BinaryHeap());
   * </pre>
   *
   * @since Commons Collections 3.0
   * @version $Revision: 1.1 $ $Date: 2003/11/29 18:04:57 $
   * 
   * @author Peter Donald
   * @author Ram Chidambaram
   * @author Michael A. Smith
   * @author Paul Jack
   * @author Stephen Colebourne
   */
  public final class BinaryHeap extends AbstractCollection
          implements PriorityQueue, Buffer {
  
      /**
       * The default capacity for a binary heap.
       */
      private final static int DEFAULT_CAPACITY = 13;
      /**
       * The number of elements currently in this heap.
       */
      int m_size;  // package scoped for testing
      /**
       * The elements in this heap.
       */
      Object[] m_elements;  // package scoped for testing
      /**
       * 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.
       */
      boolean m_isMinHeap;  // package scoped for testing
      /**
       * The comparator used to order the elements
       */
      Comparator m_comparator;  // package scoped for testing
  
      /**
       * Constructs a new minimum binary heap.
       */
      public BinaryHeap() {
          this(DEFAULT_CAPACITY, true);
      }
  
      /**
       * Constructs a new <code>BinaryHeap</code> that will use the given
       * comparator to order its elements.
       * 
       * @param comparator  the comparator used to order the elements, null
       *  means use natural order
       */
      public BinaryHeap(Comparator comparator) {
          this();
          m_comparator = comparator;
      }
      
      /**
       * Constructs a new minimum binary heap with the specified initial capacity.
       *  
       * @param capacity  The initial capacity for the heap.  This value must
       *  be greater than zero.
       * @throws IllegalArgumentException  
       *  if <code>capacity</code> is &lt;= <code>0</code>
       */
      public BinaryHeap(int capacity) {
          this(capacity, true);
      }
  
      /**
       * Constructs a new <code>BinaryHeap</code>.
       *
       * @param capacity  the initial capacity for the heap
       * @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 BinaryHeap(int capacity, Comparator comparator) {
          this(capacity);
          m_comparator = comparator;
      }
  
      /**
       * Constructs a new minimum or maximum binary heap
       *
       * @param isMinHeap  if <code>true</code> the heap is created as a 
       * minimum heap; otherwise, the heap is created as a maximum heap
       */
      public BinaryHeap(boolean isMinHeap) {
          this(DEFAULT_CAPACITY, isMinHeap);
      }
  
      /**
       * Constructs a new <code>BinaryHeap</code>.
       *
       * @param isMinHeap  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 BinaryHeap(boolean isMinHeap, Comparator comparator) {
          this(isMinHeap);
          m_comparator = comparator;
      }
  
      /**
       * Constructs a new minimum or maximum binary heap with the specified 
       * initial capacity.
       *
       * @param capacity the initial capacity for the heap.  This value must 
       * be greater than zero.
       * @param isMinHeap 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 BinaryHeap(int capacity, boolean isMinHeap) {
          if (capacity <= 0) {
              throw new IllegalArgumentException("invalid capacity");
          }
          m_isMinHeap = isMinHeap;
  
          //+1 as 0 is noop
          m_elements = new Object[capacity + 1];
      }
  
      /**
       * Constructs a new <code>BinaryHeap</code>.
       *
       * @param capacity  the initial capacity for the heap
       * @param isMinHeap  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 BinaryHeap(int capacity, boolean isMinHeap, Comparator comparator) {
          this(capacity, isMinHeap);
          m_comparator = comparator;
      }
  
      
      /**
       * Clears all elements from queue.
       */
      public void clear() {
          m_elements = new Object[m_elements.length];  // for gc
          m_size = 0;
      }
  
      /**
       * Tests if queue is empty.
       *
       * @return <code>true</code> if queue is empty; <code>false</code> 
       *  otherwise.
       */
      public boolean isEmpty() {
          return m_size == 0;
      }
  
      /**
       * Tests if queue is full.
       *
       * @return <code>true</code> if queue is full; <code>false</code>
       *  otherwise.
       */
      public boolean isFull() {
          //+1 as element 0 is noop
          return m_elements.length == m_size + 1;
      }
  
      /**
       * Inserts an element into queue.
       *
       * @param element  the element to be inserted
       */
      public void insert(Object element) {
          if (isFull()) {
              grow();
          }
          //percolate element to it's place in tree
          if (m_isMinHeap) {
              percolateUpMinHeap(element);
          } else {
              percolateUpMaxHeap(element);
          }
      }
  
      /**
       * Returns the element on top of heap but don't remove it.
       *
       * @return the element at top of heap
       * @throws NoSuchElementException  if <code>isEmpty() == true</code>
       */
      public Object peek() throws NoSuchElementException {
          if (isEmpty()) {
              throw new NoSuchElementException();
          } else {
              return m_elements[1];
          }
      }
  
      /**
       * Returns the element on top of heap and remove it.
       *
       * @return the element at top of heap
       * @throws NoSuchElementException  if <code>isEmpty() == true</code>
       */
      public Object pop() throws NoSuchElementException {
          final Object result = peek();
          m_elements[1] = m_elements[m_size--];
  
          // set the unused element to 'null' so that the garbage collector
          // can free the object if not used anywhere else.(remove reference)
          m_elements[m_size + 1] = null;
  
          if (m_size != 0) {
              // percolate top element to it's place in tree
              if (m_isMinHeap) {
                  percolateDownMinHeap(1);
              } else {
                  percolateDownMaxHeap(1);
              }
          }
  
          return result;
      }
  
      /**
       * Percolates element down heap from top.
       * Assume it is a maximum heap.
       *
       * @param index the index for the element
       */
      protected void percolateDownMinHeap(final int index) {
          final Object element = m_elements[index];
          int hole = index;
  
          while ((hole * 2) <= m_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 != m_size && compare(m_elements[child + 1], m_elements[child]) < 0) {
                  child++;
              }
  
              // if we found resting place of bubble then terminate search
              if (compare(m_elements[child], element) >= 0) {
                  break;
              }
  
              m_elements[hole] = m_elements[child];
              hole = child;
          }
  
          m_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 = m_elements[index];
          int hole = index;
  
          while ((hole * 2) <= m_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 != m_size && compare(m_elements[child + 1], m_elements[child]) > 0) {
                  child++;
              }
  
              // if we found resting place of bubble then terminate search
              if (compare(m_elements[child], element) <= 0) {
                  break;
              }
  
              m_elements[hole] = m_elements[child];
              hole = child;
          }
  
          m_elements[hole] = element;
      }
  
      /**
       * Percolates element up heap from bottom.
       * Assume it is a maximum heap.
       *
       * @param element the element
       */
      protected void percolateUpMinHeap(final Object element) {
          int hole = ++m_size;
  
          m_elements[hole] = element;
  
          while (hole > 1 && compare(element, m_elements[hole / 2]) < 0) {
              // save element that is being pushed down
              // as the element "bubble" is percolated up
              final int next = hole / 2;
              m_elements[hole] = m_elements[next];
              hole = next;
          }
  
          m_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 = ++m_size;
  
          while (hole > 1 && compare(element, m_elements[hole / 2]) > 0) {
              // save element that is being pushed down
              // as the element "bubble" is percolated up
              final int next = hole / 2;
              m_elements[hole] = m_elements[next];
              hole = next;
          }
  
          m_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
       */
      private int compare(Object a, Object b) {
          if (m_comparator != null) {
              return m_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[] elements = new Object[m_elements.length * 2];
          System.arraycopy(m_elements, 0, elements, 0, m_elements.length);
          m_elements = elements;
      }
  
      /**
       * 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 < m_size + 1; i++) {
              if (i != 1) {
                  sb.append(", ");
              }
              sb.append(m_elements[i]);
          }
  
          sb.append(" ]");
  
          return sb.toString();
      }
  
  
      /**
       * 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 <= m_size;
              }
  
              public Object next() {
                  if (!hasNext()) throw new NoSuchElementException();
                  lastReturnedIndex = index;
                  index++;
                  return m_elements[lastReturnedIndex];
              }
  
              public void remove() {
                  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 );
                  }
                  index--;
                  lastReturnedIndex = -1;        
              }
  
          };
      }
  
  
      /**
       * Adds an object to this heap. Same as {@link #insert(Object)}.
       *
       * @param object  the object to add
       * @return true, always
       */
      public boolean add(Object object) {
          insert(object);
          return true;
      }
  
      /**
       * Returns the priority element. Same as {@link #peek()}.
       *
       * @return the priority element
       * @throws BufferUnderflowException if this heap is empty
       */
      public Object get() {
          try {
              return peek();
          } catch (NoSuchElementException e) {
              throw new BufferUnderflowException();
          }
      }
  
      /**
       * Removes the priority element. Same as {@link #pop()}.
       *
       * @return the removed priority element
       * @throws BufferUnderflowException if this heap is empty
       */
      public Object remove() {
          try {
              return pop();
          } catch (NoSuchElementException e) {
              throw new BufferUnderflowException();
          }
      }
  
      /**
       * Returns the number of elements in this heap.
       *
       * @return the number of elements in this heap
       */
      public int size() {
          return m_size;
      }
  
  }
  
  
  
  1.12      +3 -2      jakarta-commons/collections/src/java/org/apache/commons/collections/UnboundedFifoBuffer.java
  
  Index: UnboundedFifoBuffer.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/UnboundedFifoBuffer.java,v
  retrieving revision 1.11
  retrieving revision 1.12
  diff -u -r1.11 -r1.12
  --- UnboundedFifoBuffer.java	14 Oct 2003 18:06:41 -0000	1.11
  +++ UnboundedFifoBuffer.java	29 Nov 2003 18:04:57 -0000	1.12
  @@ -82,6 +82,7 @@
    * <p>
    * This buffer prevents null objects from being added.
    * 
  + * @deprecated Moved to buffer subpackage. Due to be removed in v4.0.
    * @since Commons Collections 2.1
    * @version $Revision$ $Date$
    *
  
  
  
  1.15      +3 -2      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.14
  retrieving revision 1.15
  diff -u -r1.14 -r1.15
  --- BinaryHeap.java	31 Aug 2003 17:26:44 -0000	1.14
  +++ BinaryHeap.java	29 Nov 2003 18:04:57 -0000	1.15
  @@ -86,6 +86,7 @@
    * Buffer heap = BufferUtils.synchronizedBuffer(new BinaryHeap());
    * </pre>
    *
  + * @deprecated Moved to buffer subpackage. Due to be removed in v4.0.
    * @since Commons Collections 1.0
    * @version $Revision$ $Date$
    * 
  
  
  
  1.5       +3 -4      jakarta-commons/collections/src/java/org/apache/commons/collections/CircularFifoBuffer.java
  
  Index: CircularFifoBuffer.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/CircularFifoBuffer.java,v
  retrieving revision 1.4
  retrieving revision 1.5
  diff -u -r1.4 -r1.5
  --- CircularFifoBuffer.java	31 Aug 2003 17:26:44 -0000	1.4
  +++ CircularFifoBuffer.java	29 Nov 2003 18:04:57 -0000	1.5
  @@ -59,8 +59,6 @@
   
   import java.util.Collection;
   
  -import org.apache.commons.collections.BoundedFifoBuffer;
  -
   /** 
    * CircularFifoBuffer is a first in first out buffer with a fixed size that
    * replaces its oldest element if full.
  @@ -81,6 +79,7 @@
    * <p>
    * This buffer prevents null objects from being added.
    * 
  + * @deprecated WILL BE REMOVED BEFORE v3.0
    * @since Commons Collections 3.0
    * @version $Revision$ $Date$
    * 
  
  
  
  1.12      +6 -3      jakarta-commons/collections/src/java/org/apache/commons/collections/BoundedFifoBuffer.java
  
  Index: BoundedFifoBuffer.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/BoundedFifoBuffer.java,v
  retrieving revision 1.11
  retrieving revision 1.12
  diff -u -r1.11 -r1.12
  --- BoundedFifoBuffer.java	18 Nov 2003 22:50:44 -0000	1.11
  +++ BoundedFifoBuffer.java	29 Nov 2003 18:04:57 -0000	1.12
  @@ -85,6 +85,7 @@
    * <p>
    * This buffer prevents null objects from being added.
    *
  + * @deprecated Moved to buffer subpackage. Due to be removed in v4.0.
    * @since 2.1
    * @version $Revision$ $Date$
    * 
  @@ -94,7 +95,9 @@
    * @author Stephen Colebourne
    * @author Herve Quiroz
    */
  -public class BoundedFifoBuffer extends AbstractCollection implements Buffer, BoundedCollection {
  +public class BoundedFifoBuffer extends AbstractCollection
  +        implements Buffer, BoundedCollection {
  +            
       private final Object[] m_elements;
       private int m_start = 0;
       private int m_end = 0;
  
  
  

---------------------------------------------------------------------
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