final class TestRun {

   static final boolean traceOn = false; 
   static int layout = 0;

   public static void main(String[] args) {
      int count = 10000;
      if (args.length > 0)
         count = Integer.parseInt(args[0]);     
         
     // Timing         
     long startTicks, stopTicks, frequency;
     startTicks = System.currentTimeMillis();                

      Scheduler s = new Scheduler(traceOn);
      Packet wkq;

      s.addIdleTask(Scheduler.IDLE, 0, null, count);

      wkq = new Packet(null, Scheduler.WORKER, Packet.WORK_KIND);
      wkq = new Packet(wkq, Scheduler.WORKER,  Packet.WORK_KIND);
      s.addWorkerTask(Scheduler.WORKER, 1000, wkq);

      wkq = new Packet(null, Scheduler.DEVICEA, Packet.DEVICE_KIND);
      wkq = new Packet(wkq, Scheduler.DEVICEA, Packet.DEVICE_KIND);
      wkq = new Packet(wkq, Scheduler.DEVICEA, Packet.DEVICE_KIND);
      s.addHandlerTask(Scheduler.HANDLERA, 2000, wkq);

      wkq = new Packet(null, Scheduler.DEVICEB, Packet.DEVICE_KIND);
      wkq = new Packet(wkq, Scheduler.DEVICEB, Packet.DEVICE_KIND);
      wkq = new Packet(wkq, Scheduler.DEVICEB, Packet.DEVICE_KIND);
      s.addHandlerTask(Scheduler.HANDLERB, 3000, wkq);

      s.addDeviceTask(Scheduler.DEVICEA, 4000, null);

      s.addDeviceTask(Scheduler.DEVICEB, 5000, null);

      s.schedule();
      
     // Timing
      stopTicks = System.currentTimeMillis();    
      frequency = 1000;  
     // Timing
      System.out.println("<ExternalStat>");
      System.out.println("<size>" + count + "</size>");
      System.out.println("<ticks>" + (stopTicks - startTicks) + "</ticks>");
      System.out.println("<ticksPerSecond>" + frequency + "</ticksPerSecond>");  
      System.out.println("</ExternalStat>");       
   }
   
   
   static final void trace(char aChar){
      --layout;
      if (layout <= 0)
      {
         System.out.println("");
         layout = 50;
      }
      System.out.print(aChar);         
   }
   
}


final class Scheduler {
   private Tcb[] table = new Tcb[MAXTASKS];
   private Tcb list = null;
   private Tcb currentTcb;
   private int currentId;

   int queueCount = 0;
   int holdCount = 0;
   boolean traceOn = false;
   
   final static  int IDLE = 0;
   final static int WORKER = 1;
   final static  int HANDLERA = 2;
   final static int HANDLERB = 3;
   final static  int DEVICEA = 4;
   final static int DEVICEB = 5;     
      
   final static int MAXTASKS = 6;          
   
   
   Scheduler(boolean trace)
   {
      traceOn = trace;
   }
  

   void addIdleTask(int anId, int aPriority, 
      Packet aWorkQueue, int aCount)
   {
      addRunningTask(
         anId, 
         aPriority, 
         aWorkQueue, 
         (ISchedulerTask)(new IdleTask(this, 1, aCount))
         );
   }
   
   
   void addWorkerTask(int anId, int aPriority, Packet aWorkQueue)
   {
      addTask(
         anId, 
         aPriority, 
         aWorkQueue, 
         (ISchedulerTask)(new WorkerTask(this, HANDLERA, 0))
         );
   }               
   

   void addHandlerTask(int anId, int aPriority, Packet aWorkQueue)
   {
      addTask(
         anId, 
         aPriority, 
         aWorkQueue, 
         (ISchedulerTask)(new HandlerTask(this))
         );         
   }      
   
         
   void addDeviceTask(int anId, int aPriority, Packet aWorkQueue)
   {
      addTask(
         anId, 
         aPriority, 
         aWorkQueue, 
         (ISchedulerTask)(new DeviceTask(this))
         ); 
   }     
         
   
   private void addTask(int anId, int aPriority,
      Packet aWorkQueue, ISchedulerTask aTask)
      // See addRunningTask before making changes
   {
      currentTcb = new Tcb(list, anId, aPriority, aWorkQueue, aTask);
      list = currentTcb;
      table[anId] = currentTcb;
   }
   
   
   private void addRunningTask(int anId, int aPriority,
      Packet aWorkQueue, ISchedulerTask aTask)
   {
      addTask(anId, aPriority, aWorkQueue, aTask);
      currentTcb.setRunning(); 
   }
   
   
   void schedule()
   {
      currentTcb = list;
      while (currentTcb != null)
      {
         if (currentTcb.isHeldOrSuspended())
            currentTcb = currentTcb.getLink();
         else
         {
            currentId = currentTcb.getId();
            //if (traceOn) TestRun.trace((char)('0' + currentId + 1));
            currentTcb = currentTcb.run();
         }
      }
   }
   
   
   Tcb queue(Packet aPacket)
   {
      Tcb t = table[aPacket.getId()];
      if (t == null) return t;
      queueCount++;
      aPacket.setLink(null);
      aPacket.setId(currentId);
      return t.checkPriorityAdd(currentTcb, aPacket);
   }
   
   
   Tcb release(int anId)
   {
      Tcb t = table[anId];
      if (t == null) return t;
      t.notHeld();
      if (t.getPriority() > currentTcb.getPriority()) 
         return t;
      else 
         return currentTcb;
   }
   
   
   Tcb holdCurrent()
   {
      ++holdCount;
      currentTcb.held();
      return currentTcb.getLink();
   }
   
   
   Tcb suspendCurrent()
   {
      currentTcb.suspended();
      return currentTcb;
   }
         
}


interface ISchedulerTask {
   Tcb run(Packet aPacket);
}


final class IdleTask implements ISchedulerTask {
   int v1, v2;
   Scheduler s;
   
   public IdleTask(Scheduler aScheduler, int value1, int value2){
      v1 = value1;
      v2 = value2;
      s = aScheduler;
   }
            
   final public Tcb run(Packet aPacket){
         v2--;                   
      if (v2 == 0)  
         return s.holdCurrent();

      if ( ( v1 & 1) == 0 )
      {
         v1 = v1 >> 1;
         return s.release(Scheduler.DEVICEA);
      }
      else
      {
         v1 = (v1 >> 1 ) ^ 0xD008 ;
         return s.release(Scheduler.DEVICEB);
      }
   }             
}


final class WorkerTask implements ISchedulerTask {
   int v1, v2;
   Scheduler s;
   
   public WorkerTask(Scheduler aScheduler, int value1, int value2){
      v1 = value1;
      v2 = value2;
      s = aScheduler;
   }
   
   final public Tcb run(Packet aPacket){
      if (aPacket == null) 
      {   
         return s.suspendCurrent(); 
         }
      else 
      {               
         if (v1 == Scheduler.HANDLERA)
            v1 = Scheduler.HANDLERB;
         else
            v1 = Scheduler.HANDLERA;
            
         aPacket.setId( v1 );
         aPacket.setA1( (byte)0 );              
         
         for (int i=0; i < Packet.DATA_SIZE; i++)
         {
            v2++;
            if (v2 > 26) v2 = 1;
            aPacket.getA2()[i] = (byte)('A' + v2 - 1);             
         } 
         return s.queue(aPacket);
      }
   }             
}


final class HandlerTask implements ISchedulerTask {
   Packet v1, v2;
   Scheduler s;
      
   public HandlerTask(Scheduler aScheduler){
      s = aScheduler;
   }
   
   final public Tcb run(Packet aPacket){               
      if (aPacket != null) 
      {
         if (aPacket.getKind() == Packet.WORK_KIND)
            v1 = aPacket.addTo(v1);
         else 
            v2 = aPacket.addTo(v2);
      }
      if (v1 != null) 
      {
         byte count = v1.getA1();
         Packet v; 
         if (count < Packet.DATA_SIZE )
         {
            if (v2 != null ) 
            {
               v = v2;
               v2 = v2.getLink();
               v.setA1( v1.getA2()[count] );
               v1.setA1( (byte)(count + 1) );
               return s.queue(v);
            }
         }
         else
         {
            v = v1;
            v1 = v1.getLink();
            return s.queue(v);
         }
      }
      return s.suspendCurrent();             
   }             
}


final class DeviceTask implements ISchedulerTask {
   Packet v1;
   Scheduler s;
   
   public DeviceTask(Scheduler aScheduler){
      s = aScheduler;
   }         
                     
   final public Tcb run(Packet aPacket){
      if (aPacket == null) 
      {
         if (v1 == null) 
            return s.suspendCurrent();
         Packet v = v1;
         v1 = null;
         return s.queue(v);
      }
      else 
      {
         v1 = aPacket;
         //if (s.traceOn) TestRun.trace( (char)(aPacket.getA1()) );
         return s.holdCurrent();      
      }                  
   }             
}      


final class Tcb {
   // Variables from spec
   private Tcb link;      // pointer to another tcb or nil
   private int id;        // identifier (a small integer)
   private int pri;       // priority (a positive integer)
   private Packet wkq;  // list of Packets in the tasks work queue
   private int state;    // a 3 bit value giving the state    
   private ISchedulerTask task; 
   // the function called by the scheduler when it transfers control to this task


   Tcb(Tcb aTcb, int anId, int aPriority, 
      Packet aWorkQueue, ISchedulerTask aTask
      )
   {
      link = aTcb;
      id = anId;
      pri = aPriority;
      wkq = aWorkQueue;   
      task = aTask;
      if (wkq == null) 
         state = SUSPENDED;
      else 
         state = SUSPENDED_RUNNABLE;
   }


   Tcb getLink(){
         return link;
   }


   int getId(){
      return id; 
   }


   int getPriority(){
         return pri;
   }
         
      
   Tcb checkPriorityAdd(Tcb aTask, Packet aPacket)
   {
      if (wkq == null )
      {
         wkq = aPacket;
         state = state | RUNNABLE; 
         if (pri > aTask.getPriority()) { return this; }
      }
      else 
      {
         wkq = aPacket.addTo(wkq);
      }
      return aTask;
   }
   
   
   Tcb run()
   {
      Packet packet;
      if (state == SUSPENDED_RUNNABLE)
      {
         packet = wkq;
         wkq = packet.getLink();
         if (wkq == null) 
            state = RUNNING; 
         else 
            state = RUNNABLE;         
      }
      else
      {
         packet = null;
      }
      return task.run(packet);
   }


   // Named bit masks to access 3 bit state value.
   private static int RUNNING = 0;   
   private static int RUNNABLE = 1;
   private static int SUSPENDED = 2;
   private static int HELD = 4;
   private static int SUSPENDED_RUNNABLE = SUSPENDED | RUNNABLE;
   private static int NOT_HELD = ~HELD;


   void setRunning()
   {
      state = RUNNING;
   }    
   
   void suspended(){
      state = state | SUSPENDED; 
   }         
   
   void held(){
      state = state | HELD; 
   }  
   
   void notHeld(){
      state = state & NOT_HELD; 
   }                      
   
   boolean isHeldOrSuspended(){
      return (state & HELD) != 0 || (state == SUSPENDED); 
   }                        

}



final class Packet {
   final static int DATA_SIZE = 4;
   // Variables from spec
   private Packet link;    // pointer to the next Packet or nil
   private int id;         // task or device that sent the packet
   private int kind;      // part of the message
   private byte a1 = 0; // part of the message
   private byte[] a2 = new byte[DATA_SIZE];  

   final static  int DEVICE_KIND = 0;
   final static int WORK_KIND = 1;

   Packet(Packet aLink, int anId, int aKind)
   {
      link = aLink;
      id = anId;
      kind = aKind;
   }
   

   Packet addTo(Packet aQueue)
   {
      Packet next, peek;
      link = null;
      if (aQueue == null) return this;
      next = aQueue;
      while ((peek = next.link) != null)
         next = peek;
      next.link = this;
      return aQueue;
   }

   Packet getLink(){ 
      return link;
   }
   
   void setLink(Packet aPacket){
      link = aPacket;
   }

   int getId(){ 
      return id;
   }
   
   void setId(int anId){
      id = anId;
   }
   
   int getKind(){
      return kind;
   }
   
   byte getA1(){
      return a1;
   }
   
   void setA1(byte aByte){
      a1 = aByte;
   }
   
   byte[] getA2(){
      return a2;
   }
      
}