You are viewing a plain text version of this content. The canonical link for it is here.
Posted to cvs@avalon.apache.org by do...@apache.org on 2002/07/12 02:06:37 UTC
cvs commit: jakarta-avalon-cornerstone/src/java/org/apache/avalon/cornerstone/blocks/scheduler BinaryHeap.java PriorityQueue.java SynchronizedPriorityQueue.java DefaultTimeScheduler.java
donaldp 2002/07/11 17:06:37
Modified: src/java/org/apache/avalon/cornerstone/blocks/scheduler
DefaultTimeScheduler.java
Added: src/java/org/apache/avalon/cornerstone/blocks/scheduler
BinaryHeap.java PriorityQueue.java
SynchronizedPriorityQueue.java
Log:
Decouple scheduler from collections as that is moving repos anyways
Revision Changes Path
1.18 +13 -19 jakarta-avalon-cornerstone/src/java/org/apache/avalon/cornerstone/blocks/scheduler/DefaultTimeScheduler.java
Index: DefaultTimeScheduler.java
===================================================================
RCS file: /home/cvs/jakarta-avalon-cornerstone/src/java/org/apache/avalon/cornerstone/blocks/scheduler/DefaultTimeScheduler.java,v
retrieving revision 1.17
retrieving revision 1.18
diff -u -r1.17 -r1.18
--- DefaultTimeScheduler.java 18 May 2002 13:30:09 -0000 1.17
+++ DefaultTimeScheduler.java 12 Jul 2002 00:06:37 -0000 1.18
@@ -13,11 +13,7 @@
import org.apache.avalon.cornerstone.services.scheduler.TimeScheduler;
import org.apache.avalon.cornerstone.services.scheduler.TimeTrigger;
import org.apache.avalon.cornerstone.services.threads.ThreadManager;
-import org.apache.avalon.excalibur.collections.BinaryHeap;
-import org.apache.avalon.excalibur.collections.PriorityQueue;
-import org.apache.avalon.excalibur.collections.SynchronizedPriorityQueue;
import org.apache.avalon.framework.activity.Disposable;
-import org.apache.avalon.framework.activity.Initializable;
import org.apache.avalon.framework.activity.Startable;
import org.apache.avalon.framework.logger.AbstractLogEnabled;
import org.apache.avalon.framework.service.ServiceException;
@@ -35,12 +31,13 @@
*/
public class DefaultTimeScheduler
extends AbstractLogEnabled
- implements TimeScheduler, Serviceable, Initializable, Startable, Disposable, Runnable
+ implements TimeScheduler, Serviceable, Startable, Disposable, Runnable
{
- private boolean m_running;
- private Hashtable m_entries;
- private PriorityQueue m_priorityQueue;
+ private final Hashtable m_entries = new Hashtable();
+ private final PriorityQueue m_priorityQueue =
+ new SynchronizedPriorityQueue( new BinaryHeap() );
private ThreadManager m_threadManager;
+ private boolean m_running;
/**
* @phoenix:dependency name="org.apache.avalon.cornerstone.services.threads.ThreadManager"
@@ -51,16 +48,10 @@
m_threadManager = (ThreadManager)serviceManager.lookup( ThreadManager.ROLE );
}
- public void initialize()
- {
- m_entries = new Hashtable();
- m_priorityQueue = new SynchronizedPriorityQueue( new BinaryHeap() );
- }
-
public void dispose()
{
- m_entries = null;
- m_priorityQueue = null;
+ m_entries.clear();
+ m_priorityQueue.clear();
}
/**
@@ -98,8 +89,10 @@
}
catch( final NoSuchElementException nse )
{
- getLogger().warn( "Unexpected exception when peek() on priority queue for " +
- entry.getName(), nse );
+ final String message =
+ "Unexpected exception when peek() on priority queue for " +
+ entry.getName();
+ getLogger().warn( message, nse );
}
}
@@ -224,7 +217,8 @@
}
catch( final Exception e )
{
- getLogger().warn( "Error executing trigger " + entry.getName(), e );
+ final String message = "Error executing trigger " + entry.getName();
+ getLogger().warn( message, e );
}
}
1.1 jakarta-avalon-cornerstone/src/java/org/apache/avalon/cornerstone/blocks/scheduler/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.txt file.
*/
package org.apache.avalon.cornerstone.blocks.scheduler;
import java.util.Comparator;
import java.util.NoSuchElementException;
/**
* BinaryHeap implementation of priority queue.
* The heap is either a minimum or maximum heap as determined
* by parameters passed to constructor.
*
* @author <a href="mailto:peter@apache.org">Peter Donald</a>
* @author <a href="mailto:ram.chidambaram@telus.com">Ram Chidambaram</a>
* @author <a href="mailto:stansburyc@earthlink.net">Chad Stansbury</a>
* @version CVS $Revision: 1.1 $ $Date: 2002/07/12 00:06:37 $
* @since 4.0
*/
final class BinaryHeap
implements PriorityQueue
{
private static final class MinComparator
implements Comparator
{
public final int compare( final Object lhs, final Object rhs )
{
return ( (Comparable)lhs ).compareTo( rhs );
}
}
private static final class MaxComparator
implements Comparator
{
public final int compare( final Object lhs, final Object rhs )
{
return ( (Comparable)rhs ).compareTo( lhs );
}
}
/**
* Comparator used to instantiate a min heap - assumes contents implement
* the Comparable interface.
*/
public static final Comparator MIN_COMPARATOR = new MinComparator();
/**
* Comparator used to instantiate a max heap - assumes contents implement
* the Comparable interface.
*/
public static final Comparator MAX_COMPARATOR = new MaxComparator();
private static final int DEFAULT_CAPACITY = 13;
private static final Comparator DEFAULT_COMPARATOR = MIN_COMPARATOR;
private int m_size;
private Object[] m_elements;
private Comparator m_comparator;
/**
* Instantiates a new min binary heap with the default initial capacity.
*/
public BinaryHeap()
{
this( DEFAULT_CAPACITY, DEFAULT_COMPARATOR );
}
/**
* Instantiates a new min binary heap with the given initial capacity.
*
* @param capacity the size of the heap
*/
public BinaryHeap( final int capacity )
{
this( capacity, DEFAULT_COMPARATOR );
}
/**
* Instantiates a new binary heap with the default initial capacity and
* ordered using the given Comparator.
*
* @param comparator to order the contents of the heap
*/
public BinaryHeap( final Comparator comparator )
{
this( DEFAULT_CAPACITY, comparator );
}
/**
* Instantiates a new binary heap with the given initial capacity and
* ordered using the given Comparator.
*
* @param capacity the size of the heap
* @param comparator to order the contents of the heap
*/
public BinaryHeap( final int capacity, final Comparator comparator )
{
//+1 as 0 is noop
m_elements = new Object[ capacity + 1 ];
m_comparator = comparator;
}
/**
* Create a binary heap of Comparables. Takes a parameter
* to specify whether it is a minimum or maximum heap.
*
* @param isMinHeap true to make it a minimum heap, false to make it a max heap
*/
public BinaryHeap( final boolean isMinHeap )
{
this( DEFAULT_CAPACITY, isMinHeap );
}
/**
* Create a binary heap of Comparables. Takes a parameter
* to specify whether it is a minimum or maximum heap and another
* parameter to specify the size of the heap.
*
* @param capacity the size of the heap
* @param isMinHeap true to make it a minimum heap, false to make it a max heap
*/
public BinaryHeap( final int capacity, final boolean isMinHeap )
{
this( capacity, isMinHeap ? MIN_COMPARATOR : MAX_COMPARATOR );
}
/**
* 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 );
}
/**
* Returns the number of elements currently on the heap.
*
* @return the size of the heap.
*/
public int size()
{
return m_size;
}
/**
* Insert an element into queue.
*
* @param element the element to be inserted
*/
public void insert( final Object element )
{
if( isFull() )
{
grow();
}
percolateUpHeap( element );
}
/**
* Return element on top of heap but don't remove it.
*
* @return the element at top of heap
* @throws NoSuchElementException if isEmpty() == true
*/
public Object 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
* @throws NoSuchElementException if isEmpty() == true
*/
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 )
{
percolateDownHeap( 1 );
}
return result;
}
/**
* Percolate element down heap from top.
*
* @param index the index of element
*/
private void percolateDownHeap( final int index )
{
final Object element = m_elements[ index ];
int hole = index;
int child = hole << 1;
while( child <= m_size )
{
//if we have a right child and that child can not be percolated
//up then move onto other child
if( child != m_size &&
m_comparator.compare( m_elements[ child + 1 ], m_elements[ child ] ) < 0 )
{
child++;
}
//if we found resting place of bubble then terminate search
if( m_comparator.compare( m_elements[ child ], element ) >= 0 )
{
break;
}
m_elements[ hole ] = m_elements[ child ];
hole = child;
child = hole << 1;
}
m_elements[ hole ] = element;
}
/**
* Percolate element up heap from bottom.
*
* @param element the element
*/
private void percolateUpHeap( final Object element )
{
int hole = ++m_size;
int next = hole >> 1;
m_elements[ hole ] = element;
while( hole > 1 &&
m_comparator.compare( element, m_elements[ next ] ) < 0 )
{
m_elements[ hole ] = m_elements[ next ];
hole = next;
next = hole >> 1;
}
m_elements[ hole ] = element;
}
/**
* Grows the heap by a factor of 2.
*/
private void grow()
{
final Object[] elements =
new Object[ m_elements.length * 2 ];
System.arraycopy( m_elements, 0, elements, 0, m_elements.length );
m_elements = elements;
}
/**
* Create a string representing heap
* and all elements in heap.
*
* @return the string representing 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();
}
}
1.1 jakarta-avalon-cornerstone/src/java/org/apache/avalon/cornerstone/blocks/scheduler/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.txt file.
*/
package org.apache.avalon.cornerstone.blocks.scheduler;
import java.util.NoSuchElementException;
/**
* Iterface for priority queues.
* This interface does not dictate whether it is min or max heap.
*
* @author <a href="mailto:peter@apache.org">Peter Donald</a>
* @version CVS $Revision: 1.1 $ $Date: 2002/07/12 00:06:37 $
* @since 4.0
*/
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( Object element );
/**
* Return element on top of heap but don't remove it.
*
* @return the element at top of heap
* @throws NoSuchElementException if isEmpty() == true
*/
Object peek() throws NoSuchElementException;
/**
* Return element on top of heap and remove it.
*
* @return the element at top of heap
* @throws NoSuchElementException if isEmpty() == true
*/
Object pop() throws NoSuchElementException;
}
1.1 jakarta-avalon-cornerstone/src/java/org/apache/avalon/cornerstone/blocks/scheduler/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.txt file.
*/
package org.apache.avalon.cornerstone.blocks.scheduler;
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>
* @version CVS $Revision: 1.1 $ $Date: 2002/07/12 00:06:37 $
* @since 4.0
*/
final class SynchronizedPriorityQueue
implements PriorityQueue
{
private final PriorityQueue m_priorityQueue;
public SynchronizedPriorityQueue( final PriorityQueue priorityQueue )
{
if( null == priorityQueue )
{
throw new NullPointerException( "priorityQueue" );
}
m_priorityQueue = priorityQueue;
}
/**
* Clear all elements from queue.
*/
public void clear()
{
synchronized( m_priorityQueue )
{
m_priorityQueue.clear();
}
}
/**
* Test if queue is empty.
*
* @return true if queue is empty else false.
*/
public boolean isEmpty()
{
synchronized( m_priorityQueue )
{
return m_priorityQueue.isEmpty();
}
}
/**
* Insert an element into queue.
*
* @param element the element to be inserted
*/
public void insert( final Object element )
{
synchronized( m_priorityQueue )
{
m_priorityQueue.insert( element );
}
}
/**
* Return element on top of heap but don't remove it.
*
* @return the element at top of heap
* @throws NoSuchElementException if isEmpty() == true
*/
public Object peek() throws NoSuchElementException
{
synchronized( m_priorityQueue )
{
return m_priorityQueue.peek();
}
}
/**
* Return element on top of heap and remove it.
*
* @return the element at top of heap
* @throws NoSuchElementException if isEmpty() == true
*/
public Object pop() throws NoSuchElementException
{
synchronized( m_priorityQueue )
{
return m_priorityQueue.pop();
}
}
public String toString()
{
synchronized( m_priorityQueue )
{
return m_priorityQueue.toString();
}
}
}
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>