commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From m..@apache.org
Subject cvs commit: jakarta-commons/collections/src/test/org/apache/commons/collections TestBinaryHeap.java
Date Wed, 03 Jul 2002 02:09:06 GMT
mas         2002/07/02 19:09:06

  Modified:    collections/src/java/org/apache/commons/collections
                        ArrayStack.java BinaryHeap.java
               collections/src/test/org/apache/commons/collections
                        TestBinaryHeap.java
  Log:
  ArrayStack and BinaryHeap now implement Buffer.
  
  Submitted by: Paul Jack
  
  Revision  Changes    Path
  1.6       +40 -5     jakarta-commons/collections/src/java/org/apache/commons/collections/ArrayStack.java
  
  Index: ArrayStack.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/ArrayStack.java,v
  retrieving revision 1.5
  retrieving revision 1.6
  diff -u -r1.5 -r1.6
  --- ArrayStack.java	12 Jun 2002 03:59:15 -0000	1.5
  +++ ArrayStack.java	3 Jul 2002 02:09:06 -0000	1.6
  @@ -74,15 +74,24 @@
    * is therefore operates faster in environments where you do not need to
    * worry about multiple thread contention.
    *
  + * The removal order of an <Code>ArrayStack</Code> is based on insertion 
  + * order: The most recently added element is removed first.  The iteration
  + * order is <I>not</I> the same as the removal order.  The iterator returns
  + * elements from the bottom up, whereas the {@link remove()} method removes
  + * them from the top down.
  + *
    * @since 1.0
    * @author Craig R. McClanahan
    * @version $Revision$ $Date$
    * @see java.util.Stack
    */
   
  -public class ArrayStack extends ArrayList {
  +public class ArrayStack extends ArrayList implements Buffer {
   
   
  +    final private static long serialVersionUID = 2130079159931574599L;
  +//, local class serialVersionUID = -3491241305852305742
  +
       // --------------------------------------------------------- Public Methods
   
   
  @@ -187,5 +196,31 @@
   
       }
   
  +
  +    /**
  +     *  Returns the element on the top of the stack.
  +     *
  +     *  @return the element on the top of the stack
  +     *  @throws BufferUnderflowException if the stack is empty
  +     */
  +    public Object get() {
  +        int size = size();
  +        if (size == 0) throw new BufferUnderflowException();
  +        return get(size - 1);
  +    }
  +
  +
  +
  +    /**
  +     *  Removes the element on the top of the stack.
  +     *
  +     *  @return the removed element 
  +     *  @throws BufferUnderflowException if the stack is empty
  +     */
  +    public Object remove() {
  +        int size = size();
  +        if (size == 0) throw new BufferUnderflowException();
  +        return remove(size - 1);
  +    }
   
   }
  
  
  
  1.8       +128 -6    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.7
  retrieving revision 1.8
  diff -u -r1.7 -r1.8
  --- BinaryHeap.java	12 Jun 2002 03:59:15 -0000	1.7
  +++ BinaryHeap.java	3 Jul 2002 02:09:06 -0000	1.8
  @@ -60,19 +60,43 @@
    */
   package org.apache.commons.collections;
   
  +import java.util.AbstractCollection;
  +import java.util.Iterator;
   import java.util.NoSuchElementException;
   import java.util.Comparator;
   
   /**
  - * Binary heap implementation of {@link PriorityQueue}.
  + * Binary heap implementation of {@link PriorityQueue} and {@link Buffer}.
  + *
  + * 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 1.0
    * @author  <a href="mailto:donaldp@apache.org">Peter Donald</a>
    * @author  <a href="mailto:ram.chidambaram@telus.com">Ram Chidambaram</a>
    * @author  <a href="mailto:mas@apache.org">Michael A. Smith</a>
  + * @author  Paul Jack
    */
  -public final class BinaryHeap
  -    implements PriorityQueue
  +public final class BinaryHeap extends AbstractCollection
  +    implements PriorityQueue, Buffer
   {
       protected final static int      DEFAULT_CAPACITY   = 13;
   
  @@ -400,6 +424,104 @@
           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 o  the object to add
  +     *  @return true, always
  +     */
  +    public boolean add(Object o) {
  +        insert(o);
  +        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;
  +    }
  +
  +
  +    Comparator comparator() {
  +        return m_comparator;
       }
   }
   
  
  
  
  1.4       +55 -6     jakarta-commons/collections/src/test/org/apache/commons/collections/TestBinaryHeap.java
  
  Index: TestBinaryHeap.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestBinaryHeap.java,v
  retrieving revision 1.3
  retrieving revision 1.4
  diff -u -r1.3 -r1.4
  --- TestBinaryHeap.java	11 Jun 2002 02:41:47 -0000	1.3
  +++ TestBinaryHeap.java	3 Jul 2002 02:09:06 -0000	1.4
  @@ -62,6 +62,10 @@
   package org.apache.commons.collections;
   
   import junit.framework.*;
  +import java.util.Arrays;
  +import java.util.ArrayList;
  +import java.util.Collection;
  +import java.util.Comparator;
   import java.util.Iterator;
   import java.util.NoSuchElementException;
   
  @@ -74,7 +78,7 @@
    * @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
    * @version $Id$
    */
  -public class TestBinaryHeap extends TestObject {
  +public class TestBinaryHeap extends TestCollection {
       
     public static Test suite() {
       return new TestSuite(TestBinaryHeap.class);
  @@ -87,10 +91,32 @@
     /**
      * Return a new, empty {@link Object} to used for testing.
      */
  -  public Object makeObject() {
  +  public Collection makeCollection() {
       return new BinaryHeap();
     }
     
  +
  +  public Collection makeConfirmedCollection() {
  +    return new ArrayList();
  +  }
  +
  +  public Collection makeConfirmedFullCollection() {
  +    ArrayList list = new ArrayList();
  +    list.addAll(Arrays.asList(getFullElements()));
  +    return list;
  +  }
  +
  +  public Object[] getFullElements() {
  +      return getFullNonNullStringElements();
  +  }
  +
  +  public Object[] getOtherElements() {
  +      return getOtherNonNullStringElements();
  +  }
  +
  +  public void testCollectionIteratorFailFast() {
  +  }
  +
     public void testBasicOps() {
       BinaryHeap heap = new BinaryHeap();
       
  @@ -240,6 +266,29 @@
       } catch (NoSuchElementException e) {
         // expected
       }     
  +  }
  +
  +
  +  public void verify() {
  +      super.verify();
  +      BinaryHeap heap = (BinaryHeap)collection;
  +
  +      Comparator c = heap.comparator();
  +      if (c == null) c = ComparatorUtils.NATURAL;
  +      if (!heap.m_isMinHeap) c = ComparatorUtils.reverse(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);
  +          }
  +      }
     }
   }
   
  
  
  

--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message