rwaldhoff 01/04/22 12:56:38
Added: collections/src/java/org/apache/commons/collections
ArrayEnumeration.java BinaryHeap.java
ListUtils.java PriorityQueue.java
SynchronizedPriorityQueue.java
Log:
committing several files from Peter Donald and Avalon
Revision Changes Path
1.1
jakarta-commons/collections/src/java/org/apache/commons/collections/ArrayEnumeration.java
Index: ArrayEnumeration.java
===================================================================
/*
* Copyright (C) The Apache Software Foundation. All rights reserved.
*
* This software is published under the terms of the Apache Software License
* version 1.1, a copy of which has been included with this distribution in
* the LICENSE file.
*/
package org.apache.commons.collections;
import java.util.Enumeration;
import java.util.List;
import java.util.NoSuchElementException;
/**
* Enumeration wrapper for array.
*
* @author <a href="mailto:[EMAIL PROTECTED]">Peter Donald</a>
*/
public final class ArrayEnumeration
implements Enumeration
{
protected Object[] m_elements;
protected int m_index;
public ArrayEnumeration( final List elements )
{
m_elements = elements.toArray();
}
public ArrayEnumeration( final Object[] elements )
{
m_elements = elements;
}
public boolean hasMoreElements()
{
return ( m_index < m_elements.length );
}
public Object nextElement()
{
if( !hasMoreElements() )
{
throw new NoSuchElementException("No more elements exist");
}
return m_elements[ m_index++ ];
}
}
1.1
jakarta-commons/collections/src/java/org/apache/commons/collections/BinaryHeap.java
Index: BinaryHeap.java
===================================================================
/*
* Copyright (C) The Apache Software Foundation. All rights reserved.
*
* This software is published under the terms of the Apache Software License
* version 1.1, a copy of which has been included with this distribution in
* the LICENSE file.
*/
package org.apache.commons.collections;
import java.util.NoSuchElementException;
/**
* Iterface for priority queues.
* This interface does not dictate whether it is min or max heap.
*
* @author <a href="mailto:[EMAIL PROTECTED]">Peter Donald</a>
* @author <a href="mailto:[EMAIL PROTECTED]">Ram Chidambaram</a>
*/
public final class BinaryHeap
implements PriorityQueue
{
protected final static int DEFAULT_CAPACITY = 13;
protected int m_size;
protected Comparable[] m_elements;
protected boolean m_isMinHeap;
public BinaryHeap()
{
this( DEFAULT_CAPACITY, true );
}
public BinaryHeap( final int capacity )
{
this( capacity, true );
}
public BinaryHeap( final boolean isMinHeap )
{
this( DEFAULT_CAPACITY, isMinHeap );
}
public BinaryHeap( final int capacity, final boolean isMinHeap )
{
m_isMinHeap = isMinHeap;
//+1 as 0 is noop
m_elements = new Comparable[ capacity + 1 ];
}
/**
* Clear all elements from queue.
*/
public void clear()
{
m_size = 0;
}
/**
* Test if queue is empty.
*
* @return true if queue is empty else false.
*/
public boolean isEmpty()
{
return ( 0 == m_size );
}
/**
* Test if queue is full.
*
* @return true if queue is full else false.
*/
public boolean isFull()
{
//+1 as element 0 is noop
return ( m_elements.length == m_size+1 );
}
/**
* Insert an element into queue.
*
* @param element the element to be inserted
*/
public void insert( final Comparable element )
{
if( isFull() ) grow();
//percolate element to it's place in tree
if( m_isMinHeap ) percolateUpMinHeap( element );
else percolateUpMaxHeap( element );
}
/**
* Return element on top of heap but don't remove it.
*
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
public Comparable peek() throws NoSuchElementException
{
if( isEmpty() ) throw new NoSuchElementException();
else return m_elements[ 1 ];
}
/**
* Return element on top of heap and remove it.
*
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
public Comparable pop() throws NoSuchElementException
{
final Comparable 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;
}
/**
* Percolate element down heap from top.
* Assume it is a maximum heap.
*
* @param element the element
*/
protected void percolateDownMinHeap( final int index )
{
final Comparable 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 &&
m_elements[ child + 1 ].compareTo( m_elements[ child ] ) < 0 )
{
child++;
}
//if we found resting place of bubble then terminate search
if( m_elements[ child ].compareTo( element ) >= 0 )
{
break;
}
m_elements[ hole ] = m_elements[ child ];
hole = child;
}
m_elements[ hole ] = element;
}
/**
* Percolate element down heap from top.
* Assume it is a maximum heap.
*
* @param element the element
*/
protected void percolateDownMaxHeap( final int index )
{
final Comparable 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 &&
m_elements[ child + 1 ].compareTo( m_elements[ child ] ) > 0 )
{
child++;
}
//if we found resting place of bubble then terminate search
if( m_elements[ child ].compareTo( element ) <= 0 )
{
break;
}
m_elements[ hole ] = m_elements[ child ];
hole = child;
}
m_elements[ hole ] = element;
}
/**
* Percolate element up heap from bottom.
* Assume it is a maximum heap.
*
* @param element the element
*/
protected void percolateUpMinHeap( final Comparable element )
{
int hole = ++m_size;
m_elements[ hole ] = element;
while( hole > 1 &&
element.compareTo( 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;
}
/**
* Percolate element up heap from bottom.
* Assume it is a maximum heap.
*
* @param element the element
*/
protected void percolateUpMaxHeap( final Comparable element )
{
int hole = ++m_size;
while( hole > 1 &&
element.compareTo( 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;
}
protected void grow()
{
final Comparable[] elements =
new Comparable[ m_elements.length * 2 ];
System.arraycopy( m_elements, 0, elements, 0, m_elements.length );
m_elements = elements;
}
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();
}
}
1.1
jakarta-commons/collections/src/java/org/apache/commons/collections/ListUtils.java
Index: ListUtils.java
===================================================================
/*
* Copyright (C) The Apache Software Foundation. All rights reserved.
*
* This software is published under the terms of the Apache Software License
* version 1.1, a copy of which has been included with this distribution in
* the LICENSE file.
*/
package org.apache.commons.collections;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* Miscelaneous utilities to manipulate Lists.
*
* @author <a href="mailto:[EMAIL PROTECTED]">Federico Barbieri</a>
* @author <a href="mailto:[EMAIL PROTECTED]">Peter Donald</a>
*/
public class ListUtils
{
public static List intersection( final List list1, final List list2 )
{
final ArrayList result = new ArrayList();
final Iterator iterator = list2.iterator();
while( iterator.hasNext() )
{
final Object o = iterator.next();
if ( list1.contains( o ) )
{
result.add( o );
}
}
return result;
}
public static List subtract( final List list1, final List list2 )
{
final ArrayList result = new ArrayList( list1 );
final Iterator iterator = list2.iterator();
while( iterator.hasNext() )
{
result.remove( iterator.next() );
}
return result;
}
public static List sum( final List list1, final List list2 )
{
return subtract( union( list1, list2 ),
intersection( list1, list2 ) );
}
public static List union( final List list1, final List list2 )
{
final ArrayList result = new ArrayList( list1 );
result.addAll( list2 );
return result;
}
}
1.1
jakarta-commons/collections/src/java/org/apache/commons/collections/PriorityQueue.java
Index: PriorityQueue.java
===================================================================
/*
* Copyright (C) The Apache Software Foundation. All rights reserved.
*
* This software is published under the terms of the Apache Software License
* version 1.1, a copy of which has been included with this distribution in
* the LICENSE file.
*/
package org.apache.commons.collections;
import java.util.NoSuchElementException;
/**
* Iterface for priority queues.
* This interface does not dictate whether it is min or max heap.
*
* @author <a href="mailto:[EMAIL PROTECTED]">Peter Donald</a>
*/
public interface PriorityQueue
{
/**
* Clear all elements from queue.
*/
void clear();
/**
* Test if queue is empty.
*
* @return true if queue is empty else false.
*/
boolean isEmpty();
/**
* Insert an element into queue.
*
* @param element the element to be inserted
*/
void insert( Comparable element );
/**
* Return element on top of heap but don't remove it.
*
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
Comparable peek() throws NoSuchElementException;
/**
* Return element on top of heap and remove it.
*
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
Comparable pop() throws NoSuchElementException;
}
1.1
jakarta-commons/collections/src/java/org/apache/commons/collections/SynchronizedPriorityQueue.java
Index: SynchronizedPriorityQueue.java
===================================================================
/*
* Copyright (C) The Apache Software Foundation. All rights reserved.
*
* This software is published under the terms of the Apache Software License
* version 1.1, a copy of which has been included with this distribution in
* the LICENSE file.
*/
package org.apache.commons.collections;
import java.util.NoSuchElementException;
/**
* A thread safe version of the PriorityQueue.
* Provides synchronized wrapper methods for all the methods
* defined in the PriorityQueue interface.
*
* @author <a href="mailto:[EMAIL PROTECTED]">Ram Chidambaram</a>
*/
public final class SynchronizedPriorityQueue
implements PriorityQueue
{
protected final PriorityQueue m_priorityQueue;
public SynchronizedPriorityQueue( final PriorityQueue priorityQueue )
{
m_priorityQueue = priorityQueue;
}
/**
* Clear all elements from queue.
*/
public synchronized void clear()
{
m_priorityQueue.clear();
}
/**
* Test if queue is empty.
*
* @return true if queue is empty else false.
*/
public synchronized boolean isEmpty()
{
return m_priorityQueue.isEmpty();
}
/**
* Insert an element into queue.
*
* @param element the element to be inserted
*/
public synchronized void insert( final Comparable element )
{
m_priorityQueue.insert( element );
}
/**
* Return element on top of heap but don't remove it.
*
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
public synchronized Comparable peek() throws NoSuchElementException
{
return m_priorityQueue.peek();
}
/**
* Return element on top of heap and remove it.
*
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
public synchronized Comparable pop() throws NoSuchElementException
{
return m_priorityQueue.pop();
}
public synchronized String toString()
{
return m_priorityQueue.toString();
}
}
