TraceTracer.java

package buffalo.dataStructures;

import buffalo.dataStructures.*;
import buffalo.util.Fifo;
import java.util.Vector;
import buffalo.twoTasksAnalysis.TwoTasksCircuit;//déplacer la méthode sur les circuits...

/**
   Ensemble de méthodes permettant de tracer des graphes 
   partiels (ou non) des contraintes de précédence 
   et d'y rechercher des circuits.
 */

public class TraceTracer
{

    /*-------------------------------------------------------*/

    /**
       Trace les contraintes de Buffer vide de <CODE>myBuffer</CODE>, 
       retourne vrai si c'est possible, faux sinon. 
     */

    public static boolean traceEmptyBufferConstraints(Buffer myBuffer)
    {
	Task readingTask = myBuffer.getReadingTask();
	Task writingTask = myBuffer.getWritingTask();
	int nbReadingOperations = myBuffer.getNbInversedN(readingTask);
	int nbWritingOperations = myBuffer.getNbInversedN(writingTask);	
	Operation readingOperation;
	Operation writingOperation;
	if (nbReadingOperations != nbWritingOperations)
	    {
		return false;
	    }
	for (int i = 0 ; i < nbReadingOperations ; i++)
	    {
		writingOperation = myBuffer.getInversedN(i, writingTask);
		readingOperation = myBuffer.getInversedN(i, readingTask);
		writingOperation.setNextBufferedOperation(readingOperation);
	    }
	return true;
    }
    
    /*-------------------------------------------------------*/

    /**
       Trace les contraintes de Buffer vide de tous les buffers, 
       retourne vrai si c'est possible, faux sinon. 
     */

    public static boolean traceAllEmptyBufferConstraints()
    {
	Buffer myBuffer;
	int nbBuffers = Buffer.getNbBuffers();
	boolean feasible;
	for (int i = 0; i < nbBuffers ; i++)
	    {
		myBuffer = Buffer.get(i);
		feasible = traceEmptyBufferConstraints(myBuffer);
		if (!feasible)
		    {
			return false;
		    }
	    }	
	return true;
    }
    
    /*-------------------------------------------------------*/

    /**
       Trace les contraintes de Buffer plein de tous les buffers, 
       retourne vrai si c'est possible, faux sinon. 
     */

    public static boolean traceAllFullBufferConstraints()
    {
	Buffer myBuffer;
	int nbBuffers = Buffer.getNbBuffers();
	boolean feasible;
	for (int i = 0; i < nbBuffers ; i++)
	    {
		myBuffer = Buffer.get(i);
		feasible = traceFullBufferConstraints(myBuffer);
		if (!feasible)
		    {
			return false;
		    }
	    }	
	return true;
    }
    
    /*-------------------------------------------------------*/

    /**
       Trace les contraintes de Buffer plein de <CODE>myBuffer</CODE>. 
       Cette m&eacute;thode se charge 
       d'&eacute;craser le cha&icirc;nage pr&eacute;c&eacute;dent. 
       Si par exemple on redimmensionne <CODE>myBuffer</CODE>, 
       cette m&eacute;thode r&eacute;ajuste les arcs de la trace.
    */

    public static boolean traceFullBufferConstraints(Buffer myBuffer)    
    {
	Task readingTask = myBuffer.getReadingTask();
	Task writingTask = myBuffer.getWritingTask();
	int nbOperations = myBuffer.getNbInversedN(readingTask);
	int sizeOfBuffer = myBuffer.getSize();
	if (sizeOfBuffer <= 0) return false;	    
	Operation readingOperation;
	Operation writingOperation;
	for (int i = 0 ; (i < sizeOfBuffer)&&(i < nbOperations) ; i ++)
	    {
		writingOperation = myBuffer.getInversedN(i, writingTask);
		writingOperation.setPreviousBufferedOperation(null);
	    }
	for (int i = sizeOfBuffer ; (i < nbOperations - sizeOfBuffer + 1)&&(i < nbOperations); i++)
	    {
		writingOperation = myBuffer.getInversedN(i, writingTask);
		readingOperation = myBuffer.getInversedN(i - sizeOfBuffer, 
							 readingTask);
		writingOperation.setPreviousBufferedOperation(readingOperation);
	    }
	int i;
	if (nbOperations - sizeOfBuffer < -1)
	    {
		i = 0;
	    }
	else
	    {
		i = nbOperations - sizeOfBuffer + 1;
	    }
	for (; i < nbOperations ; i++)
	    {
		readingOperation = myBuffer.getInversedN(i, 
							 readingTask);
		readingOperation.setNextBufferedOperation(null);
	    }
	return true;
    }
    
    /*-------------------------------------------------------*/

    /**
       Elimine <U>tous</U> les arcs du graphe.
    */

    public static void removeAllConstraints()
    {
	int nbBuffers = Buffer.getNbBuffers();
	for (int i = 0; i < nbBuffers; i++)
	    {
		removeAllConstraints(Buffer.get(i));
	    }
    }

    /*-------------------------------------------------------*/

    /**
       Elimine tous les arcs li&eacute;s &agrave; des contraintes de 
       buffer vide ou de buffer plein du 
       buffer <CODE>myBuffer</CODE>.
    */

    public static void removeAllConstraints(Buffer myBuffer)
    {
	int nbOperations = myBuffer.getNbInversedN(myBuffer.getReadingTask());
	for (int i = 0; i < nbOperations; i++)
	    {
		myBuffer.getInversedN(i, myBuffer.getReadingTask()).setNextBufferedOperation(null);
		myBuffer.getInversedN(i, myBuffer.getReadingTask()).setPreviousBufferedOperation(null);
	    }
    }

    /*-------------------------------------------------------*/

    /**
       Recherche un circuit dans la trace d'ex&eacute;cution 
       <U>&agrave; deux T&acirc;ches</U> et le retourne.
       Cette m&eacute;thode retourne <CODE>null</CODE> si il n'y a pas de circuits.
    */

    public static TwoTasksCircuit findTwoTasksCircuit(Task northTask, 
					      Task southTask)
    {
	int upperBound = 2 * (northTask.getNbOperations() + 
			      southTask.getNbOperations());
	Fifo toVisit = new Fifo(upperBound);
	toVisit.add(northTask.getOperation(0));
	toVisit.add(southTask.getOperation(0));
	Operation northSuspect = null;
	Operation southSuspect = null;
	Operation myOperation;
	Operation nextOperation;
	boolean[] northMarks = new boolean[northTask.getNbOperations()];
	boolean[] southMarks = new boolean[southTask.getNbOperations()];
	initialiseMarks(northMarks, southMarks);
	while (toVisit.get() != null)
	    {
		myOperation = (Operation)toVisit.get();		
		if (!isMarked(myOperation, northMarks, southMarks, 
		    myOperation.getActiveTask() == northTask))
		    {
			if (isMarquable(myOperation, northMarks, southMarks, 
					myOperation.getActiveTask() == northTask))
			    {
				mark(myOperation, northMarks, southMarks, 
				     myOperation.getActiveTask() == northTask);		    
				nextOperation = myOperation.getNextFixedOperation();
				if (nextOperation != null) 
				    {
					toVisit.add(nextOperation);
				    }
				nextOperation = myOperation.getNextBufferedOperation();
				if (nextOperation != null) 
				    {
					toVisit.add(nextOperation);
				    }
				if (northSuspect == myOperation) 
				    {
					northSuspect = null;
				    }
				if (southSuspect == myOperation) 
				    {
					southSuspect = null;
				    }
			    }
			else
			    {
				if (myOperation.getActiveTask()==northTask) 
				    { 
					northSuspect = myOperation; 
				    }
				else 
				    { 
					southSuspect = myOperation;
				    }
			    }		
		    }
		toVisit.extract();		
	    }
	if ((northSuspect != null)||(southSuspect != null))
	    {
		return new TwoTasksCircuit
		    (northTask, northSuspect, southSuspect, 
		     northSuspect.getPreviousBufferedOperation(),
		     southSuspect.getPreviousBufferedOperation());
	    }
	else
	    {
		return null;
	    }		
    }

    /*-------------------------------------------------------*/

    /*
      Utilitaires sans int&eacute;r&ecirc;t     
    */
 
    private static void initialiseMarks(boolean[] northMarks, 
					boolean[] southMarks)
    {
	for (int i = 0 ; i < northMarks.length ; i++)
	    {
		northMarks[i] = false;
	    }
	for (int i = 0 ; i < southMarks.length ; i++)
	    {
		southMarks[i] = false;
	    }
    }

    private static boolean isMarquable
	(Operation myOperation, 
	 boolean[] northMarks, 
	 boolean[] southMarks, 
	 boolean isNorthOperation)
    {
	return (
		((isNorthOperation)&&
		 (
		  (myOperation.getIndex() == 0)||
		  (northMarks[myOperation.getIndex() - 1])
		  )&&
		 (
		  (myOperation.getPreviousBufferedOperation() == null)||
		  (southMarks
		   [myOperation.getPreviousBufferedOperation().getIndex()]
		   )
		  )
		 )
		||
		((!isNorthOperation)&&
		 (
		  (myOperation.getIndex() == 0)||
		  (southMarks[myOperation.getIndex() - 1])
		  )&&
		(
		 (myOperation.getPreviousBufferedOperation() == null)||
		 (northMarks
		  [myOperation.getPreviousBufferedOperation().getIndex()]
		  )
		 )
		 )
		);
    }
 
    private static void mark
	(Operation myOperation, 
	 boolean[] northMarks, 
	 boolean[] southMarks, 
	 boolean isNorthTask)
    {
	if (isNorthTask)
	    {
		northMarks[myOperation.getIndex()] = true;
	    }
	else
	    {
		southMarks[myOperation.getIndex()] = true;
	    }
    }

   private static boolean isMarked
	(Operation myOperation, 
	 boolean[] northMarks, 
	 boolean[] southMarks, 
	 boolean isNorthTask)
    {
	return (
		(isNorthTask) && (northMarks[myOperation.getIndex()])
		||
		(!isNorthTask) && (southMarks[myOperation.getIndex()])
		);
    }
    
    /*-------------------------------------------------------*/

    public static void main(String[] args)
    {
        try
            {
                Loader.run(args[0]);
            }
        catch(Loader.ScriptErrorException e)
            {
                System.out.println(e);
            }
        catch(Exception e)
            {
                System.out.println(e);
            }
	Buffer.get(0).setSize(1);
	System.out.println(traceAllEmptyBufferConstraints() + 
			   "\n--------------------------------");
	System.out.println(findTwoTasksCircuit( Task.get(1), 
						Task.get(0)));
    }

}