/* If a dual-processor UNIX machine, you can use a fork and run two 
experiments in parallel. Comment out the following #define to disable */
#define DUAL_PROCESSOR  /* UNIX system, dual-processor computer */
#ifdef DUAL_PROCESSOR
#include <unistd.h>     /* fork (at least for Linux)  */
#endif

#ifndef DUAL_PROCESSOR
   srand(time(NULL));   // Get a chance start to rand() sequence
#else
// If it IS dual-processor, fork the second process, then start two different
// random sequences and arrange to alternate tree sizes during the simulation.
   pid_t Child = fork();
   if ( Child != 0 )    // I.e., if this is the parent process
      N += Nstep;       // Do the odd-offset ones
   Nstep += Nstep;      // Each process steps by twice as much
// Chance start to rand() sequence, different for parent and child
   srand(time(NULL) + Child);
#endif

for ( ; N <= Nlim ; N += Nstep )  // Use value of N from above
{  clock_t Start = clock();       // Capture the starting tick
   double  CPUsecs,               // Processor time required
           SigmaHt = 0,           // Start summations at zero
           SigmaDp = 0; 
   for (Pass = 0; Pass < Npasses; Pass++)
   {  for ( k = 0; k < N; k++ )   // Fill the tree
         Tree.Insert ( rand() );
      Height   = Tree.Height();   // Capture this tree's data
      AvgDepth = Tree.AvgDepth();
      SigmaHt += Height;          // Collect the statistics
      SigmaDp += AvgDepth;
      Tree.Empty();               // Empty out the tree
   } // end for ( Pass...
   CPUsecs = double(clock()-Start) / CLOCKS_PER_SEC;
// Capture statistics in "comma-separated value" mode for later use.
   Fout << N << ',' << SigmaHt / Npasses << ','
        << SigmaDp / Npasses << ',' << CPUsecs << endl;
} // end for ( N...

   int fd = open("/tmp/Joint.data", O_RDWR|O_TRUNC|O_CREAT, 0666);
   .  .  .    < code segment omitted > 
// Spawn all the child processes as a chain
   for ( Proc = 1; Proc < Nproc; Proc ++ )
   {  Child = fork();
      if ( Child != 0 )      // Child spawns the NEXT child.
         break;
   }
   .  .  .    < code segment omitted > 
   if ( Proc == 1 )   // That is, the first parent in the chain
      wait(NULL);     // wait till everything is finished.
   else
   {  if ( Child != 0 )
         wait(NULL);  // Let the immediate descendent finish
      N_out = write (fd, &Nhits, sizeof(Nhits)); // write out Nhits
      exit(1);        // Bow out so that the next can process
   }
   N_out = lseek(fd, 0, SEEK_SET);  // Rewind the file
   for ( Proc = 1; Proc < Nproc; Proc++ )
   {  N_out = read (fd, &Part, sizeof(Part));    // read into Part
      Nhits += Part;
   }

   BSTrun[] worker;     // Compute-engine threads
     .  .  .    < code segment omitted >
   worker = new BSTrun[nThreads];
   for ( k = 0; k < nThreads; k++ )
   {//Note the threads have differing starting values for n,
    //while they all use a correspondingly coarser nStep.
      worker[k] = new BSTrun(n+k*nStep, nLim, nThreads*nStep,nPasses, fOut);
      worker[k].start();     // Start processing
   }
// Now wait for the workers to finish
   for ( k = 0; k < nThreads; k++ )
      try
      {  worker[k].join(); } // Returns when worker[k] terminates
      catch (InterruptedException e)   // We should never see this
      {  System.err.println (e);  System.exit(-1);  }

class BSTrun extends Thread
{ 
   // Seeded in the constructor, used in run()
   java.util.Random generator;
   // Subproblem description parameters / instance fields
   int n,          // Starting tree size
       nLim,       // Upper limit on tree size
       nStep,      // Increment for tree size
       nPasses;    // Number of trees to build for averaging
   // Output stream for the results
   PrintWriter fOut;
   // Copy all the construction parameters into their fields.
   BSTrun(int n, int nLim, int nStep, int nPasses, PrintWriter fOut)
   {  this.n = n; this.nLim = nLim; this.nStep = nStep;
      this.nPasses = nPasses; this.fOut = fOut;
      // Since n values differ, we have somewhat different seeds.
      generator = new java.util.Random(System.currentTimeMillis()
                  + n * nLim);
   } // end BSTrun constructor

// Compute engine portion --- copied from sequential code
public void run()
{  BST tree = new BST();
   for ( ; n <= nLim; n += nStep )
   {  long   start = System.currentTimeMillis();
      double elapsed;
      double sigmaHt = 0,  // Total of tree heights
             sigmaDp = 0;  // Total of tree average depths
      int    height;       // Individual tree height
      double avgDepth;     // Individual tree average depth
      String stats;        // Build the formatted output here
      DecimalFormat fmt = new DecimalFormat ("0.000");
      for ( int pass = 0; pass < nPasses; pass++ )
      {  for ( int k = 0; k < n; k++ ) // Fill the tree
            tree.insert ( generator.nextInt() );
         height   = tree.height();     // Capture this tree's data
         avgDepth = tree.avgDepth();
         sigmaHt += height;            // Collect the statistics
         sigmaDp += avgDepth;
         tree.empty();                 // Empty out the tree
      }// end for (pass...
      elapsed = (System.currentTimeMillis()-start) * 1.0e-03;
      stats = "," + fmt.format(sigmaHt / nPasses) + ","
                  + fmt.format(sigmaDp / nPasses) + "," 
                  + fmt.format(elapsed);
      fOut.println (n + stats);  fOut.flush();
   } // end for (n...
} // end run()

class IntWrapper
{  public int value;      // All values allowed, so direct access
   IntWrapper (int value) // Constructor:  copy over value
   {  this.value = value;  }
} // end class IntWrapper
. . . <code segment omitted>
// The following code segment is taken from the main() method--showing the 
// creation of an array of threads th[], and an array of IntWrapper objects 
// p[] to handle parameter passing. The p[] objects also pass information 
// into the thread--the instance number of the thread.
   LnCalc[]     th = null;
   IntWrapper[] p  = null;
   .  .  .    < code segment omitted >
   th = new LnCalc[nThreads];
   p  = new IntWrapper[nThreads];
   for ( k = 0; k < nThreads; k++ ) // Thread initiation
   {  p[k]  = new IntWrapper(k+1);
      th[k] = new LnCalc(x, nShots, p[k]);
      th[k].start();
   } // end thread initiation and start
   for ( k = 0; k < nThreads; k++ ) // Thread completion
   {  try
      {  th[k].join();  } // Wait for completion of this thread.
      catch (InterruptedException e)
      {  System.out.println (e);  System.exit(-1);  }
      nHits += p[k].value;
   } // end wait for thread termination