donaldp 01/04/22 00:35:42
Added: src/scratchpad/org/apache/avalon/util Circuit.java
CircularDependencyException.java
DependencyGraph.java Primes.java
src/scratchpad/org/apache/avalon/util/test
DependencyGraphTestlet.java
Log:
Moved unused code to whiteboard directory.
Revision Changes Path
1.1
jakarta-avalon/src/scratchpad/org/apache/avalon/util/Circuit.java
Index: Circuit.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;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;
/**
*
* @version 0.0.20, 04/07/1998
* @author Federico Barbieri <[EMAIL PROTECTED]>
* @author Stefano Mazzocchi <[EMAIL PROTECTED]>
*/
public class Circuit
{
protected Hashtable m_map;
public Circuit()
{
m_map = new Hashtable();
}
public void addNode( final String name )
{
if( null == m_map.get( name ) )
{
m_map.put( name, new Node( name ) );
}
}
public void removeNode( final String name )
{
String tmp = null;
Enumeration e = m_map.keys();
while( e.hasMoreElements() )
{
tmp = (String)e.nextElement();
if( !tmp.equals( name ) )
{
try { unlink( tmp, name ); }
catch( final CircuitException ce) {}
try { unlink( name, tmp ); }
catch( final CircuitException ce ) {}
}
}
m_map.remove( name );
}
public void link( final String parent, final String child )
throws CircuitException
{
Node tempNode = null;
Node pnode = (Node)m_map.get( parent );
Node cnode = (Node)m_map.get( child );
if( null == pnode )
{
throw new CircuitException( "Unknown node " + parent );
}
else if( null == cnode )
{
throw new CircuitException( "Unknown node " + child );
}
else if( pnode.isChildOf( cnode ) )
{
throw new CircuitException( "Loop! Node " + parent +
" is already child of node " + child );
}
else
{
final Enumeration e = m_map.elements();
while( e.hasMoreElements() )
{
tempNode = (Node)e.nextElement();
if( tempNode.isChildOf( cnode ) )
{
tempNode.m_parents.addAll( pnode.m_parents );
}
}
}
}
public void unlink( final String parent, final String child )
throws CircuitException
{
Node cnode = (Node)m_map.get( child );
Node pnode = (Node)m_map.get( parent );
if( cnode.m_parents.contains( pnode ) )
{
Node tempNode = null;
Enumeration e = m_map.elements();
while( e.hasMoreElements() )
{
tempNode = (Node)e.nextElement();
if( tempNode.m_parents.contains( cnode ) )
{
tempNode.m_parents.removeAll( pnode.m_parents );
}
}
}
else
{
throw new CircuitException( "Node " + parent + " is not parent of node "
+ child );
}
}
public Vector getAncestors()
{
Vector ancestors = new Vector();
String name = null;
Node tempNode = null;
Enumeration e = m_map.keys();
while( e.hasMoreElements() )
{
name = (String)e.nextElement();
tempNode = (Node)m_map.get( name );
if( 1 == tempNode.m_parents.size() )
{
ancestors.addElement( name );
}
}
return ancestors;
}
public String getAncestor()
{
String name = null;
Node tempNode = null;
Enumeration e = m_map.keys();
while( e.hasMoreElements() )
{
name = (String)e.nextElement();
tempNode = (Node)m_map.get( name );
if( 1 == tempNode.m_parents.size() )
{
return name;
}
}
return null;
}
public boolean isEmpty()
{
return m_map.isEmpty();
}
protected final class Node
{
protected Vector m_parents;
protected String m_name;
protected Node( final String name )
{
m_parents = new Vector( 5 );
m_parents.addElement( this );
m_name = name;
}
protected boolean isChildOf( final Node parent )
{
return m_parents.contains( parent );
}
public String toString()
{
StringBuffer buffer = new StringBuffer();
Enumeration e = m_parents.elements();
buffer.append( m_name + "[" );
while( e.hasMoreElements() )
{
buffer.append(((Node) e.nextElement()).m_name + " ");
}
buffer.append("]");
return buffer.toString();
}
}
public final class CircuitException
extends RuntimeException
{
public CircuitException()
{
}
public CircuitException( final String message )
{
super( message );
}
}
public String toString()
{
StringBuffer buffer = new StringBuffer();
String name = null;
Node tempNode = null;
Enumeration e = m_map.keys();
while( e.hasMoreElements() )
{
name = (String)e.nextElement();
tempNode = (Node)m_map.get( name );
buffer.append( name + "(" + ( tempNode.m_parents.size() - 1 ) + ") " );
}
return buffer.toString();
}
}
1.1
jakarta-avalon/src/scratchpad/org/apache/avalon/util/CircularDependencyException.java
Index: CircularDependencyException.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;
import java.util.List;
import org.apache.avalon.CascadingException;
/**
*
* @author <a href="mailto:[EMAIL PROTECTED]">Peter Donald</a>
*/
public class CircularDependencyException
extends CascadingException
{
protected List m_stack;
public CircularDependencyException( final String dependee,
final String dependent,
final List stack )
{
super( dependee + " depends upon " + dependent + " which depends upong " +
dependee );
m_stack = stack;
}
public List getStack()
{
return m_stack;
}
}
1.1
jakarta-avalon/src/scratchpad/org/apache/avalon/util/DependencyGraph.java
Index: DependencyGraph.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;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
/**
* DirectedGraph is a acyclic Directed graph implementation.
*
* @author <a href="mailto:[EMAIL PROTECTED]">Peter Donald</a>
*/
public class DependencyGraph
{
protected final HashMap m_map = new HashMap();
protected boolean m_allowCircularity = true;
public void setAllowCircularity( final boolean allowCircularity )
{
m_allowCircularity = allowCircularity;
}
public void add( final String name, final String[] dependencies )
{
m_map.put( name, new GraphNode( name, dependencies ) );
}
public void remove( final String name )
{
m_map.remove( name );
}
public Dependency[] getDependencyList( final String name )
throws CircularDependencyException
{
final ArrayList list = new ArrayList();
final Dependency dependency = new Dependency( name , null );
list.add( dependency );
if( null != m_map.get( name ) )
{
final ArrayList stack = new ArrayList();
stack.add( name );
buildDependencyList( name, list, new ArrayList(), stack );
}
return (Dependency[])list.toArray( new Dependency[ 0 ] );
}
protected void buildDependencyList( final String name,
final ArrayList list,
final ArrayList done,
final ArrayList stack )
throws CircularDependencyException
{
if( done.contains( name ) ) return;
done.add( name );
final GraphNode node = (GraphNode)m_map.get( name );
if( null == node ) return;
final String[] dependencies = node.getDependencies();
for( int i = 0; i < dependencies.length; i++ )
{
if( stack.contains( dependencies[ i ] ) )
{
if( m_allowCircularity ) continue;
else
{
throw new CircularDependencyException( dependencies[ i ], name,
stack );
}
}
if( done.contains( dependencies[ i ] ) ) continue;
final Dependency dependency = new Dependency( dependencies[ i ], name );
list.add( dependency );
stack.add( dependencies[ i ] );
buildDependencyList( dependencies[ i ], list, done, stack );
stack.remove( stack.size() - 1 );
}
}
public final static class Dependency
{
protected final String m_name;
protected final String m_requiredBy;
protected Dependency( final String name, final String requiredBy )
{
m_name = name;
m_requiredBy = requiredBy;
}
public String getName()
{
return m_name;
}
public String getRequiredBy()
{
return m_requiredBy;
}
public String toString()
{
return getName();
}
}
protected final static class GraphNode
{
protected final String m_name;
protected final String[] m_dependencies;
protected GraphNode( final String name, final String[] dependencies )
{
m_name = name;
m_dependencies = dependencies;
}
public String getName()
{
return m_name;
}
public String[] getDependencies()
{
return m_dependencies;
}
}
}
1.1 jakarta-avalon/src/scratchpad/org/apache/avalon/util/Primes.java
Index: Primes.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;
/**
*
* @author Federico Barbieri <[EMAIL PROTECTED]>
* @author Stefano Mazzocchi <[EMAIL PROTECTED]>
*/
public class Primes
{
/**
* Last prime found.
*
*/
protected static long c_lastPrime = 1;
/**
* Return next prime.
*
*/
public static long nextPrime()
{
long l = c_lastPrime + 1;
long v = 2;
while( true )
{
l++;
while( v < l )
{
v++;
if( (l % v) == 0 )
{
v = 0;
break;
}
} // while v < l
if( v == l )
{
c_lastPrime = l;
return l;
} // if v is l
} // while true (break is used to escape)
}
}
1.1
jakarta-avalon/src/scratchpad/org/apache/avalon/util/test/DependencyGraphTestlet.java
Index: DependencyGraphTestlet.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.test;
import java.util.List;
import org.apache.avalon.util.CircularDependencyException;
import org.apache.avalon.util.DependencyGraph;
import org.apache.testlet.AbstractTestlet;
/**
*
* @author <a href="mailto:[EMAIL PROTECTED]">Peter Donald</a>
*/
public final class DependencyGraphTestlet
extends AbstractTestlet
{
protected final String[][] DEPENDENCY_TREE =
{
{ "A" }, { "B", "C", "D" },
{ "B" }, { "E" },
{ "C" }, {},
{ "D" }, { "F" },
{ "E" }, { "F" },
{ "F" }, { },
{ "G" }, { "H" },
{ "H" }, { "G" },
{ "I" }, { "I" }
};
protected DependencyGraph m_graph;
public void initialize()
{
m_graph = new DependencyGraph();
for( int i = 0; i < DEPENDENCY_TREE.length; i += 2 )
{
m_graph.add( DEPENDENCY_TREE[ i ][0], DEPENDENCY_TREE[ i + 1 ] );
}
}
protected boolean contains( final DependencyGraph.Dependency[] list, final
String name )
{
for( int i = 0; i < list.length; i++ )
{
if( list[ i ].getName().equals( name ) )
{
return true;
}
}
return false;
}
public void testNoDependency()
throws Exception
{
final DependencyGraph.Dependency[] list = m_graph.getDependencyList( "F" );
assertEquality( "Graph for F", list.length, 1 );
assertEquality( "Graph for F[1]", list[ 0 ].getName(), "F" );
assertEquality( "Graph for F[1]", list[ 0 ].getRequiredBy(), null );
}
public void test1LevelDependency()
throws Exception
{
final DependencyGraph.Dependency[] list = m_graph.getDependencyList( "E" );
assertEquality( "Graph for E", list.length, 2 );
assert( "Graph for E[1]", contains( list, "E" ) );
assert( "Graph for E[2]", contains( list, "F" ) );
}
public void test2LevelDependency()
throws Exception
{
final DependencyGraph.Dependency[] list = m_graph.getDependencyList( "B" );
assertEquality( "Graph for E", list.length, 3 );
assert( "Graph for E[1]", contains( list, "E" ) );
assert( "Graph for E[2]", contains( list, "F" ) );
assert( "Graph for E[3]", contains( list, "B" ) );
}
public void testNLevelDependency()
throws Exception
{
final DependencyGraph.Dependency[] list = m_graph.getDependencyList( "A" );
assertEquality( "Graph for A", list.length, 6 );
assert( "Graph for A[1]", contains( list, "A" ) );
assert( "Graph for A[2]", contains( list, "B" ) );
assert( "Graph for A[3]", contains( list, "C" ) );
assert( "Graph for A[4]", contains( list, "D" ) );
assert( "Graph for A[5]", contains( list, "E" ) );
assert( "Graph for A[6]", contains( list, "F" ) );
}
public void testAllowableCircularDependency()
throws Exception
{
m_graph.setAllowCircularity( true );
final DependencyGraph.Dependency[] list = m_graph.getDependencyList( "G" );
assertEquality( "Graph for G", list.length, 2 );
assert( "Graph for G[1]", contains( list, "G" ) );
assert( "Graph for H[2]", contains( list, "H" ) );
}
public void testUnallowableCircularDependency()
throws Exception
{
try
{
m_graph.setAllowCircularity( false );
m_graph.getDependencyList( "G" );
}
catch( final CircularDependencyException cde )
{
return;
}
fail( "Expected CircularDependencyException" );
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
