You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@avalon.apache.org by do...@apache.org on 2001/04/16 10:45:12 UTC
cvs commit: jakarta-avalon/src/java/org/apache/avalon/util/collections ArrayEnumeration.java ArrayStack.java BinaryHeap.java CircularBuffer.java IteratorEnumeration.java ListUtils.java PriorityQueue.java SynchronizedPriorityQueue.java
donaldp 01/04/16 01:45:12
Added: src/java/org/apache/avalon/util/collections
ArrayEnumeration.java ArrayStack.java
BinaryHeap.java CircularBuffer.java
IteratorEnumeration.java ListUtils.java
PriorityQueue.java SynchronizedPriorityQueue.java
Removed: src/java/org/apache/avalon/util ArrayEnumeration.java
ArrayStack.java BinaryHeap.java CircularBuffer.java
IteratorEnumeration.java ListUtils.java
PriorityQueue.java SynchronizedPriorityQueue.java
Log:
Move collections related classes into a sub-package
Revision Changes Path
1.1 jakarta-avalon/src/java/org/apache/avalon/util/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.avalon.util.collections;
import java.util.Enumeration;
import java.util.List;
import java.util.NoSuchElementException;
/**
* Enumeration wrapper for array.
*
* @author <a href="mailto:donaldp@apache.org">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-avalon/src/java/org/apache/avalon/util/collections/ArrayStack.java
Index: ArrayStack.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.avalon.util.collections;
import java.util.ArrayList;
import java.util.EmptyStackException;
/**
* Unsynchronized stakc.
*
* @author <a href="mailto:donaldp@apache.org">Peter Donald</a>
*/
public class ArrayStack
extends ArrayList
{
public void setSize( final int size )
{
if( 0 == size ) clear();
else
{
removeRange( size, size() - 1 );
}
}
/**
* Adds the object to the top of the stack.
*
* @param element object to add to stack
* @return the object
*/
public Object push( final Object element )
{
add( element );
return element;
}
/**
* Remove element from top of stack and return it
*
* @return the element from stack
* @exception EmptyStackException if no elements left on stack
*/
public Object pop()
throws EmptyStackException
{
final int size = size();
if( 0 == size ) throw new EmptyStackException();
return remove( size - 1 );
}
}
1.1 jakarta-avalon/src/java/org/apache/avalon/util/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.avalon.util.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:donaldp@apache.org">Peter Donald</a>
* @author <a href="mailto:ram.chidambaram@telus.com">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-avalon/src/java/org/apache/avalon/util/collections/CircularBuffer.java
Index: CircularBuffer.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.avalon.util.collections;
/**
*
* @author Federico Barbieri <fe...@apache.org>
*/
public class CircularBuffer
{
protected Object[] m_buffer;
protected int m_bufferSize;
protected int m_contentSize;
protected int m_head;
protected int m_tail;
public CircularBuffer( int size )
{
m_buffer = new Object[size];
m_bufferSize = size;
m_contentSize = 0;
m_head = 0;
m_tail = 0;
}
public CircularBuffer()
{
this( 32 );
}
public boolean isEmpty()
{
return (m_contentSize == 0);
}
public int getContentSize()
{
return m_contentSize;
}
public int getBufferSize()
{
return m_bufferSize;
}
public void append( final Object o )
{
if( m_contentSize >= m_bufferSize )
{
int j = 0;
int i = m_tail;
Object[] tmp = new Object[ m_bufferSize * 2 ];
while( m_contentSize > 0 )
{
i++;
i %= m_bufferSize;
j++;
m_contentSize--;
tmp[ j ] = m_buffer[ i ];
}
m_buffer = tmp;
m_tail = 0;
m_head = j;
m_contentSize = j;
m_bufferSize *= 2;
}
m_buffer[ m_head ] = o;
m_head++;
m_head %= m_bufferSize;
m_contentSize++;
}
public Object get()
{
if( m_contentSize <= 0 )
{
return null;
}
Object o = m_buffer[ m_tail ];
m_tail++;
m_tail %= m_bufferSize;
m_contentSize--;
return o;
}
}
1.1 jakarta-avalon/src/java/org/apache/avalon/util/collections/IteratorEnumeration.java
Index: IteratorEnumeration.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.avalon.util.collections;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* Enumeration wrapper for iterator.
*
* @author <a href="mailto:donaldp@apache.org">Peter Donald</a>
*/
public final class IteratorEnumeration
implements Enumeration
{
protected Iterator m_iterator;
public IteratorEnumeration( final Iterator iterator )
{
m_iterator = iterator;
}
public boolean hasMoreElements()
{
return m_iterator.hasNext();
}
public Object nextElement()
{
return m_iterator.next();
}
}
1.1 jakarta-avalon/src/java/org/apache/avalon/util/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.avalon.util.collections;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* Miscelaneous utilities to manipulate Lists.
*
* @author <a href="mailto:fede@apache.org">Federico Barbieri</a>
* @author <a href="mailto:donaldp@apache.org">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-avalon/src/java/org/apache/avalon/util/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.avalon.util.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:donaldp@apache.org">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-avalon/src/java/org/apache/avalon/util/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.avalon.util.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:ram.chidambaram@telus.com">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();
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: avalon-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: avalon-dev-help@jakarta.apache.org