import net.jini.core.entry.*;
import net.jini.core.lookup.*;
import net.jini.core.discovery.*;
import net.jini.lookup.entry.*;
import com.sun.jini.lookup.*;
import com.sun.jini.lease.*;
import java.io.*;
import java.rmi.*;
import java.rmi.server.*;
import java.util.*;

/***************************************************************************

    <p><i>JSort (Jini Sort)</i>

    <p>This is a Jini service that performs a virtual sort of fixed length
    strings based on sort fields within the string.  This is a familiar
    service to those who have written batch programs.  

    <p>Use the r1.bat, r2.bat, and r3.bat files in JiniExample1 to start
    the Jini environment before running JSort or JClient.

    <p><i>Error Return Codes</i>

    * <pre>
    *    0 -- Sorted with no errors.
    *    1 -- Parameter error.
    *    3 -- Available memory work area is too small.
    *    4 -- Available memory too small for rec length.
    *    5 -- Memory allocation error.
    *    6 -- File creation error.
    *    8 -- Illegal item length.
    *    9 -- More than 32K records to sort.
    *   10 -- Write error during sorting (disk full?)
    *   11 -- Read error during sorting.
    *   12 -- Impossible to create new file (dir full?)
    * </pre>


    <p><i>ToDo</i>

    <ol type=1>
      <li>Fix the error reporting.</li>
      <li>Provide method to send records as an array of bytes
          rather than having to release them record by record. </li>
      <li>Provide method to fetch sorted file as an array of bytes 
          rather than having to return it record by record. </li>
    </ol>


    <p><i>Development Environment</i>

    <p>Compiled under JDK 1.2.0, Jini 1.0.0 <p>


    <p><i>History</i>

    <p>03/10/99  NDE  Created the program.


 ***************************************************************************/

    public class JSort extends UnicastRemoteObject 
      implements JSortInterface, ServiceIDListener
      {


/**   The maximum number of real pages. *//*
      ======================================  */

      final static int MAXRPAGES = 11;           


/**   Used in quickSort() for a local stack.  Able to sort 
      Log2(20) = 1 million records. *//*
      ====================================================  */

      final static int MAXSTACK = 20;           


/**   Sector size for block reads and writes. *//*
      ============================================  */

      final static int SECTSIZE = 128;          


/**   Heap reserved for user stack. *//*
      ==================================  */

      final static double USERSTACK = 2000.0;       


/**   Maximum value of a signed int. *//*
      ===================================  */

      final static double LONGLGTH = 2147483647.0; 


/**   Maximum value of 2 bytes unsigned. *//*
      =======================================  */

      final static double SEGLGTH = 65536.0;      


/**   Maximum value of 2 bytes signed. *//*
      =====================================  */

      final static double HALFSEG = 32768.0;      


/**   key = "sortjob3", v = JSortJob object. *//*
      ===========================================  */

      Hashtable htSortJobs;



/*    J   S O R T
 */
/**
 */
public JSort () throws RemoteException 
      {
      super ();
      htSortJobs = new Hashtable ();
      }



/*    M A I N
 */
/**
 */
public static void main (String[] args)
      {
      JSort jSort;

      try
        {
        jSort = new JSort ();
        jSort.register ("JSort", jSort);     //ttt
        System.out.println ("ready to receive requests...");
//ttt   jSort.test ();
        }
      catch (Exception e)
        {
        System.out.println ("JSort.main() exception: " + e);
        }
      }



/*=========================================================================
              The following methods are in alphabetical order
  =========================================================================*/



/*    A D J U S T   F O R   F I E L D   O R D E R
 */
/**   If the sort order is ascending, this method will return the same
 *    boolean that was passed to it, otherwise it returns the opposite.
 *    
 */
private boolean adjustForFieldOrder (int iSortOrderIn, boolean bIsLessIn)
      {
      if (iSortOrderIn == ASCENDING)
        {
        return (bIsLessIn);
        }
      else
        {
        return (!bIsLessIn);
        }
      }



/*    A L L O C A T E   B U F F E R S
 */
/**
 */
private void allocateBuffers (JSortJob jobIn, Hashtable htParmsIn)
      {
      int i;
      String s;
      Runtime rt;
      int iPageSize;
      double dFreeMemory;


/*    Calculate size of available work space.  Reserve work space for two
      sort records (used during quicksort) and for user stack work space.
      ===================================================================  */

      rt = Runtime.getRuntime ();
      dFreeMemory = rt.freeMemory () / 2;


/*    Calculate number of pages that will fit in real memory in such a 
      way that each page is smaller than a complete segment.  The sort 
      algorithm needs a minimum of 3 pages in memory.
      ================================================================  */

      jobIn.num_rpages = (int) ((dFreeMemory / SEGLGTH) + 1.0);
      if (jobIn.num_rpages < 3)
        {
        jobIn.num_rpages = 3;
        }


/*    Calculate the number of sectors that will completely fit into 
      a page.
      =============================================================  */

      jobIn.sect_pr_page = (int) (dFreeMemory / SECTSIZE) / jobIn.num_rpages;
//ttt jobIn.num_rpages = 3;
//ttt jobIn.sect_pr_page = 1;


/*    If sectors per page > 20 then make sure it is an even multiple 
      of 4.
      ==============================================================  */

      if (jobIn.sect_pr_page > 20)
        {
        jobIn.sect_pr_page = 4 * (jobIn.sect_pr_page / 4);
        }


/*    Calculate the page size making sure it isn't larger than a segment.
      ===================================================================  */

      iPageSize = jobIn.sect_pr_page * SECTSIZE;
      if (iPageSize > SEGLGTH)
        {
        iPageSize = (int) SEGLGTH;
        }

      jobIn.items_pr_page = iPageSize / jobIn.itemlgth;
      if (jobIn.items_pr_page <= 0)
        {
        s = "allocateBuffers(): items_pr_page=" + jobIn.items_pr_page 
          + ", not enough memory to make pages large enough for at least "
          + "1 item per page.";
        System.out.println (jobIn.sJobName + ": " + s);
        htParmsIn.put (NOTE_TAG, s);
        jobIn.error = 3;
        return;
        }


/*    Allocate memory.
      ================  */

      jobIn.swoppost = new byte[jobIn.itemlgth];
      jobIn.savez = new byte[jobIn.itemlgth];
      jobIn.rpage_ptr = new byte[jobIn.num_rpages][];
      jobIn.vpage_num = new int[jobIn.num_rpages];
      jobIn.rpage_modified = new boolean[jobIn.num_rpages];

      for (i = 0; i < jobIn.num_rpages; i++)
        {
        jobIn.rpage_ptr[i] = new byte[iPageSize];
        initPage (jobIn.rpage_ptr[i]);


/*      If there is an error during memory allocation, return with error 
        code.
        ================================================================ */

        if (jobIn.rpage_ptr[i] == null)
          {
          s = "allocateBuffers(): unable to allocate buffer "
            + i + " of " + jobIn.num_rpages + " real buffers";
          System.out.println (jobIn.sJobName + ": " + s);
          htParmsIn.put (NOTE_TAG, s);
          jobIn.error = 5;
          return;
          }
        }


/*    Screen for item length > page size.
      ===================================  */

      if (jobIn.itemlgth > iPageSize)
        {
        s = "allocateBuffers(): item length " + jobIn.itemlgth 
          + " is > than iPageSize " + iPageSize;
        System.out.println (jobIn.sJobName + ": " + s);
        htParmsIn.put (NOTE_TAG, s);
        jobIn.error = 4;
        return;
        }
      }



/*    C L O S E
 */
/**
 */
public Hashtable close (Hashtable htParmsIn)            // JSortInterface
      throws RemoteException
      {
      File f;
      String s;
      JSortJob job;
      Hashtable htReturn;

      htReturn = new Hashtable ();
      s = (String) htParmsIn.get (JOB_NAME_TAG);
      job = (JSortJob) htSortJobs.get (s);

      s = "close()";
      System.out.println (job.sJobName + ": " + s);
      if (job.iDebug > 0)
        {
        writeDebug (job, s);
        }

      try
        {
        if (job.filecreated)                             // sortwork file
          {
          job.sortwkfile.close ();
          f = new File (job.sJobName + "/" + job.sortwkfilename);
          if (f.exists ())
            {
            f.delete ();
            }
          }

        if (job.rafDebug != null)                        // debug file
          {
          job.rafDebug.close ();
          f = new File (job.sJobName + "/" + job.debugfilename);
          if (f.exists ())
            {
            f.delete ();
            }
          }

        f = new File (job.sJobName);                     // job directory
        if (f.isDirectory ())
          {
          f.delete ();
          }

        htSortJobs.remove (job.sJobName);                // job object
        }

      catch (Exception e)
        {
        }

      htReturn.put (RETURN_TAG, "0");
      return (htReturn);
      }



/*    E X C H A N G E 
 */
/**   This is called by quickSort() to exchange two sort item records.
 *
 *    @param i - first item number.
 *    @param j - second item number.
 *    @param swoppost - storage within which an item can be saved during swop.
 *
 */
private void exchange (JSortJob jobIn, long i, long j, byte[] swoppost)
      {
      int iVirtualPageNumber;          /* Virtual page number.             */
      JSortItem itemI;                 /* Pointer to item i.               */
      JSortItem itemJ;                 /* Pointer to item j.               */


/*    Locate the first record in memory by real page number & item number 
      within the page.
      ===================================================================  */

      itemI = new JSortItem ();
      itemJ = new JSortItem ();

      iVirtualPageNumber = (int) (i / jobIn.items_pr_page);
      for 
        (
        itemI.iRealPageNumber = 0; 
        jobIn.vpage_num[itemI.iRealPageNumber] != iVirtualPageNumber; 
        itemI.iRealPageNumber++
        );
      itemI.iItemOffset = (int) (i % jobIn.items_pr_page) * jobIn.itemlgth;


/*    Locate the second record in memory by real page number & item 
      number within the page.
      =============================================================  */

      iVirtualPageNumber = (int) (j / jobIn.items_pr_page);
      for 
        (
        itemJ.iRealPageNumber = 0; 
        jobIn.vpage_num[itemJ.iRealPageNumber] != iVirtualPageNumber; 
        itemJ.iRealPageNumber++
        );
      itemJ.iItemOffset = (int) (j % jobIn.items_pr_page) * jobIn.itemlgth;


/*    Swap the records using the allocated record 'swoppost' as temp 
      storage.
      ==============================================================  */

      System.arraycopy                 /* i to swop.                       */
        (
        jobIn.rpage_ptr[itemI.iRealPageNumber], 
        itemI.iItemOffset, 
        swoppost, 
        0, 
        jobIn.itemlgth
        );
      System.arraycopy                 /* j to i.                          */
        (
        jobIn.rpage_ptr[itemJ.iRealPageNumber], 
        itemJ.iItemOffset, 
        jobIn.rpage_ptr[itemI.iRealPageNumber], 
        itemI.iItemOffset, 
        jobIn.itemlgth
        );
      System.arraycopy                 /* swop to j.                       */
        (
        swoppost, 
        0, 
        jobIn.rpage_ptr[itemJ.iRealPageNumber], 
        itemJ.iItemOffset, 
        jobIn.itemlgth
        );


/*    Mark the real pages containing i and j as modified.
      ===================================================  */

      jobIn.rpage_modified[itemI.iRealPageNumber] = true;
      jobIn.rpage_modified[itemJ.iRealPageNumber] = true;

      }



/*    G E T   N E X T   J O B   N A M E
 */
/**
 */
private synchronized String getNextJobName ()
      {
      int i;
      String s;

      for (i = 1; i <= 100; i++)
        {
        s = SORT_JOB_TAG + String.valueOf (i);
        if (htSortJobs.get (s) == null)
          {
          htSortJobs.put (s, s);
          return (s);
          }
        }
      if (i >= 101)
        {
        s = "getNextJobName(): exceeded maximum (100) number of jobs";
        System.out.println (s);
        }
      return (null);
      }



/*    I N I T   P A G E   
 */
/**
 */
private void initPage (byte[] abIn)
      {
      int i;

      for (i = 0; i < abIn.length; i++)
        {
        abIn[i] = (byte) INIT_CHAR;
        }
      }



/*    L E S S   (JSortJob, JSortItem, byte[])
 */
/**   This compares two byte array items according to the sort fields
 *    for the job.  It the first item is < the second item, then this
 *    returns true.
 *
 *    @return true if the first byte array item is < the second one.
 *
 */
private boolean less (JSortJob jobIn, JSortItem itemIn, byte[] abIn)
      {
      int iField;
      int iOffset;

      if (jobIn.iDebug > 6)
        {
        writeDebug 
          (
          jobIn,
          new String (jobIn.rpage_ptr[itemIn.iRealPageNumber], 
            itemIn.iItemOffset, jobIn.itemlgth) 
            + " < " + new String (abIn)
          );
        }
      for (iField = 0; iField < jobIn.aiFieldStart.length; iField++)
        {
        for (iOffset = 0; iOffset < jobIn.aiFieldLength[iField]; iOffset++)
          {
          if (jobIn.iDebug > 8)
            {
            writeDebug (jobIn, "" + iField + ":" + iOffset + " " 
              + (char) jobIn.rpage_ptr[itemIn.iRealPageNumber][itemIn.iItemOffset 
              + jobIn.aiFieldStart[iField] + iOffset] + " < " 
              + (char) abIn[jobIn.aiFieldStart[iField] + iOffset] + " ");
            }
          if (jobIn.rpage_ptr[itemIn.iRealPageNumber][itemIn.iItemOffset + jobIn.aiFieldStart[iField] + iOffset] < abIn[jobIn.aiFieldStart[iField] + iOffset])
            {
            if (jobIn.iDebug > 6)
              {
              writeDebug (jobIn, "    true" + sCRLF);
              }
            return (adjustForFieldOrder (jobIn.aiFieldOrder[iField], true));
            }
          if (jobIn.rpage_ptr[itemIn.iRealPageNumber][itemIn.iItemOffset + jobIn.aiFieldStart[iField] + iOffset] > abIn[jobIn.aiFieldStart[iField] + iOffset])
            {
            if (jobIn.iDebug > 6)
              {
              writeDebug (jobIn, "    false" + sCRLF);
              }
            return (adjustForFieldOrder (jobIn.aiFieldOrder[iField], false));
            }
          if (jobIn.iDebug > 8)
            {
            writeDebug (jobIn, "    equal");
            }
          }
        }
      if (jobIn.iDebug > 6)
        {
        writeDebug (jobIn, "    false" + sCRLF);
        }
      return (false);
      }



/*    L E S S   (JSortJob, byte[], JSortItem)
 */
/**   This compares two byte array items according to the sort fields
 *    for the job.  It the first item is < the second item, then this
 *    returns true.
 *
 *    @return true if the first byte array item is < the second one.
 *
 */
private boolean less (JSortJob jobIn, byte[] abIn, JSortItem itemIn)
      {
      int iField;
      int iOffset;

      if (jobIn.iDebug > 6)
        {
        writeDebug 
          (
          jobIn,
          new String (abIn) + " < " 
            + new String (jobIn.rpage_ptr[itemIn.iRealPageNumber], 
            itemIn.iItemOffset, jobIn.itemlgth)
          );
        }
      for (iField = 0; iField < jobIn.aiFieldStart.length; iField++)
        {
        for (iOffset = 0; iOffset < jobIn.aiFieldLength[iField]; iOffset++)
          {
          if (jobIn.iDebug > 8)
            {
            writeDebug (jobIn, "" + iField + ":" + iOffset + " " 
              + (char) abIn[jobIn.aiFieldStart[iField] + iOffset] + " < " 
              + (char) jobIn.rpage_ptr[itemIn.iRealPageNumber][itemIn.iItemOffset 
              + jobIn.aiFieldStart[iField] + iOffset] + " ");
            }
          if (abIn[jobIn.aiFieldStart[iField] + iOffset] < jobIn.rpage_ptr[itemIn.iRealPageNumber][itemIn.iItemOffset + jobIn.aiFieldStart[iField] + iOffset])
            {
            if (jobIn.iDebug > 6)
              {
              writeDebug (jobIn, "    true" + sCRLF);
              }
            return (adjustForFieldOrder (jobIn.aiFieldOrder[iField], true));
            }
          if (abIn[jobIn.aiFieldStart[iField] + iOffset] > jobIn.rpage_ptr[itemIn.iRealPageNumber][itemIn.iItemOffset + jobIn.aiFieldStart[iField] + iOffset])
            {
            if (jobIn.iDebug > 6)
              {
              writeDebug (jobIn, "    false" + sCRLF);
              }
            return (adjustForFieldOrder (jobIn.aiFieldOrder[iField], false));
            }
          if (jobIn.iDebug > 8)
            {
            writeDebug (jobIn, "    equal");
            }
          }
        }
      if (jobIn.iDebug > 6)
        {
        writeDebug (jobIn, "    false" + sCRLF);
        }
      return (false);
      }



/*    O P E N
 */
/**
 */
public Hashtable open (Hashtable htParmsIn)             // JSortInterface
      throws RemoteException 
      {
      int i;
      String s;
      String sValue;
      String sJobName;
      StringTokenizer st;
      int iNumFields = 0;
      Hashtable htReturn;
      JSortJob job;
      File f;


/*    Get a new job name and add it to the current group of job names.
      ================================================================  */

      htReturn = new Hashtable ();
      sJobName = getNextJobName ();
      job = new JSortJob ();
      htSortJobs.put (sJobName, job);
      job.sJobName = sJobName;

      s = (String) htParmsIn.get (DEBUG_TAG);
      if (s != null)
        {
        job.iDebug = new Integer (s).intValue ();
        try
          {


/*        Create the job directory.
          =========================  */

          f = new File (job.sJobName);
          if (!f.mkdir ())                                 // Create dir
            {
            // ignored, it may already exist.
            System.out.println ("open(): Can not create the "
              + "work directory " + job.sJobName + " continuing...");
            }


/*        Remove any existing debug files and create the current
          debug file.
          ======================================================  */

          f = new File (job.sJobName + "/" + job.debugfilename);
          if (f.exists ())
            {
            f.delete ();
            }
          job.rafDebug = new RandomAccessFile 
            (
            job.sJobName + "/" + job.debugfilename, 
            "rw"
            );
          job.rafDebug.close ();
          }

        catch (Exception e)
          {
          s = "open(): exception creating debug file: " + job.sJobName 
            + "/" + job.debugfilename + ": " + e;
          System.out.println (job.sJobName + ": " + s);
          htReturn.put (NOTE_TAG, s);
          htReturn.put (RETURN_TAG, "6");
          return (htReturn);
          }
        }

      s = "open(): htParmsIn: " + htParmsIn;
      System.out.println ("*-----------------------------------------*");
      System.out.println (job.sJobName + ": " + s);
      if (job.iDebug > 0)
        {
        writeDebug (job, s);
        }

      job.itemlgth 
        = new Integer ((String) htParmsIn.get (REC_LENGTH_TAG)).intValue ();
      if (job.iDebug > 0)
        {
        s = "open(): record length=" + job.itemlgth;
        writeDebug (job, s);
        }
      if (job.itemlgth <= 1)
        {
        s = "open(): error - illegal record length=" + job.itemlgth;
        System.out.println (job.sJobName + ": " + s);
        if (job.iDebug > 0)
          {
          writeDebug (job, s);
          }
        htReturn.put (NOTE_TAG, s);
        htReturn.put (RETURN_TAG, "8");
        return (htReturn);
        }


/*    Figure out how many fields are defined in the parameters.
      =========================================================  */

      for (i = 1; i <= 100; i++)
        {
        if (htParmsIn.get (FIELD_TAG + String.valueOf (i)) == null)
          {
          iNumFields = i - 1;
          break;
          }
        }
      if (job.iDebug > 0)
        {
        s = "open(): number of fields = " + iNumFields;
        writeDebug (job, s);
        }

      job.aiFieldStart  = new int[i];
      job.aiFieldLength = new int[i];
      job.aiFieldOrder  = new int[i];

      for (i = 1; i <= iNumFields; i++)
        {
        sValue = (String) htParmsIn.get (FIELD_TAG + String.valueOf (i));
        if (job.iDebug > 0)
          {
          s = "open(): field " + i + ": value=" + sValue;
          writeDebug (job, s);
          }
        if (sValue.indexOf ('-') == -1)
          {
          s = "open(): invalid format for field tag -->" + sValue + "<--";
          System.out.println (job.sJobName + ": " + s);
          htReturn.put (NOTE_TAG, s);
          htReturn.put (RETURN_TAG, "1");
          return (htReturn);        
          }

        st = new StringTokenizer (sValue, "\n\r -", false);
        job.aiFieldStart[i] = 
          new Integer (st.nextToken ()).intValue ();
        job.aiFieldLength[i] = 
          new Integer (st.nextToken ()).intValue () + 1
          - job.aiFieldStart[i];

        if (job.aiFieldStart[i] + job.aiFieldLength[i] > job.itemlgth)
          {
          s = "open(): field definition " + sValue 
            + " exceeded sort record size of " + job.itemlgth;
          System.out.println (job.sJobName + ": " + s);
          htReturn.put (NOTE_TAG, s);
          htReturn.put (RETURN_TAG, "1");
          return (htReturn);        
          }

        sValue = (String) htParmsIn.get (ORDER_TAG + String.valueOf (i));
        if (ASCENDING_VALUE.equals (sValue))
          {
          job.aiFieldOrder[i] = ASCENDING;
          }
        else
          {
          job.aiFieldOrder[i] = DESCENDING;
          }

        if (job.iDebug > 0)
          {
          s = "open(): order=" + sValue + " ordercode=" 
            + job.aiFieldOrder[i];
          writeDebug (job, s);
          s = "open(): field " + i + ": start=" + job.aiFieldStart[i] 
            + " length=" + job.aiFieldLength[i];
          writeDebug (job, s);
          }
        }

      allocateBuffers (job, htParmsIn);

      if (job.error != 0)
        {
        htReturn.put (RETURN_TAG, String.valueOf (job.error));
        return (htReturn);
        }


/*    Finish initializing all the constants for the sort job.
      =======================================================  */

      job.filecreated = false;
      job.num_items = 0;
      job.num_leftovr_items = 0;
      job.num_vpages = 0;
      for (i = 0; i < job.num_rpages; i++)
        {
        job.vpage_num[i] = i;
        }
      job.curr_rpage = 0;
      if (job.iDebug > 0)
        {
        s = "open(): job=" + job;
        writeDebug (job, s);
        }

      htReturn.put (JOB_NAME_TAG, sJobName);
      return (htReturn);
      }



/*    P A G E   I N
 */
/**   After calling this function the page that contains the requested 
 *    item_num is in memory.  If item numbers keep_rec1 or keep_rec2 are 
 *    in real memory, they will be kept in memory and not swapped to disk.
 *
 *    @param jobIn - the sort job object.
 *    @param item_num - item number (rec number) whose page is sought.
 *    @param keep_rec1 - 1st item number to not swap out of memory.
 *    @param keep_rec2 - 2nd item number to not swap out of memory.
 * 
 */
private void pageIn (JSortJob jobIn, long item_num, long keep_rec1, 
      long keep_rec2)
      {
      int i;                           /* Counters.                        */
      int item_vpg_num;                /* Virtual page number of item_num. */
      int keep_pg1;                    /* Virtual page num of keep_rec1.   */
      int keep_pg2;                    /* Virtual page num of keep_rec2.   */
      int swap_rpage;                  /* Real page number to swap.        */


/*    If the requested page is already in memory, return.
      ===================================================  */

      item_vpg_num = (int) (item_num / jobIn.items_pr_page);

      for (i = 0; i < jobIn.num_rpages; i++)
        {
        if (item_vpg_num == jobIn.vpage_num[i])
          {
          return;
          }
        }


/*    Calculate virtual page numbers for items to keep in memory.
      ===========================================================  */

      keep_pg1 = (int) (keep_rec1 / jobIn.items_pr_page);
      keep_pg2 = (int) (keep_rec2 / jobIn.items_pr_page);


/*    Seek a real page to swap out.
      =============================  */

      for (swap_rpage = 0; 
        (jobIn.vpage_num[swap_rpage] == keep_pg1) ||
        (jobIn.vpage_num[swap_rpage] == keep_pg2);
        swap_rpage++);


/*    If the selected page has been modified, write it to the file.
      =============================================================  */

      if (jobIn.rpage_modified[swap_rpage])
        {
        pageOut (jobIn, jobIn.rpage_ptr[swap_rpage], 
          jobIn.vpage_num[swap_rpage]);
        if (jobIn.error != 0) return;
        }


/*    Position the file pointer to the virtual page to retrieve.
      ==========================================================  */

      try
        {
        jobIn.sortwkfile.seek (item_vpg_num * jobIn.sect_pr_page * SECTSIZE);
        }
      catch (Exception e)
        {
        System.out.println ("pageIn(): exception seeking spot in "
          + "sort work file: " + e);
        jobIn.error = 11;
        return;
        }


/*    Fetch the page from the sort work file to the selected real page.
      =================================================================  */

      try
        {
        jobIn.sortwkfile.read (jobIn.rpage_ptr[swap_rpage]);
        }
      catch (Exception e)
        {
        System.out.println ("pageIn(): exception reading page from "
          + "sort work file: " + e);
        jobIn.error = 11;
        return;
        }


/*    Record the virtual page number that now exists in the selected real
      page and reset its modified flag.
      ===================================================================  */

      jobIn.vpage_num[swap_rpage] = item_vpg_num;
      jobIn.rpage_modified[swap_rpage] = false;

      }



/*    P A G E   O U T
 */
/**   Write the virtual page in the passed real memory location to the file.
 *
 *    Notice that the records in the file are pages full of fixed length
 *    sort items.  The record numbers are the virtual page numbers and 
 *    begin with page 0.
 *
 *    @param jobIn - The sort job object.
 *    @param rpage_ptr - the real page to store.
 *    @param vpage_num - number of the virtual page.
 * 
 */
private void pageOut (JSortJob jobIn, byte[] rpage_ptr, int vpage_num)
      {


/*    Screen any i/o errors.
      ======================  */

      if (jobIn.error != 0)
        {
        System.out.println ("pageOut(): encountered an error");
        return;
        }


/*    Position the file pointer to the passed virtual page number.
      ============================================================  */

      try
        {
        jobIn.sortwkfile.seek (vpage_num * jobIn.sect_pr_page * SECTSIZE);
        }
      catch (Exception e)
        {
        System.out.println ("pageOut(): exception seeking spot in "
          + "sort work file: " + e);
        jobIn.error = 10;
        return;
        }


/*    Write the memory page to the file at the current position.
      ==========================================================  */

      try
        {
        jobIn.sortwkfile.write (rpage_ptr);
        }
      catch (Exception e)
        {
        System.out.println ("pageOut(): exception writing page to "
          + "sort work file: " + e);
        jobIn.error = 10;
        return;
        }

      return;
      }



/*    Q U I C K   S O R T
 */
/**   This is a non-recursive version of the quicksort algorithm as given 
 *    in Nicklaus Wirth ALGORITHMS + DATA STRUCTURES = PROGRAMS.
 *
 *    @param jobIn - job object that contains the real and virtual page 
 *      arrays.
 *    @param swoppost - save area during the sort exchange.
 *    @param savez - save area for the middle record during the sort.
 *
 */
private void quickSort (JSortJob jobIn, byte[] swoppost, byte[] savez)
      {
      long[] lstack;                   /* Stack of left index record nums. */
      long[] rstack;                   /* Stack of right index record nums.*/
      int sp;                          /* Stack pointer.                   */
      long l;                          /* Left border (where i started).   */
      long m;                          /* Middle of range.                 */
      long r;                          /* Right border (where j started).  */
      long i;                          /* Left border moving right.        */
      long j;                          /* Right border moving left.        */
      JSortItem itemX;                 /* Points to data record for i.     */
      JSortItem itemY;                 /* Points to data record for j.     */
      JSortItem itemZ;                 /* Points to data record for m.     */



/*    Screen for no records in the virtual system.
      ============================================  */

      lstack = new long[MAXSTACK];
      rstack = new long[MAXSTACK];
      itemX = new JSortItem ();
      itemY = new JSortItem ();
      itemZ = new JSortItem ();

      if (jobIn.num_items <= 0L)
        {
        return;
        }


/*    Initialize the sort range.  The left most item is item number 0.  
      The right most item is the last item in the system.
      ================================================================  */

      lstack[0] = 0L;
      rstack[0] = jobIn.num_items - 1L;
      sp = 0;


/*    After the first iteration, each cycle of this loop processes ranges 
      on the stack that are progressively bigger.
      ===================================================================  */

      while (sp >= 0)
        {


/*      Pop the range stacks.  This is retrieving the last left-right 
        range that was left to process latter.
        =============================================================  */

        l = lstack[sp];
        r = rstack[sp];
        sp--;


/*      Cycle 1.  After the first iteration, each cycle of this loop 
        processes a progressively smaller range. 
        ============================================================  */

        do
          {


/*        The variable 'l' holds the place of the left border of the 
          range and 'r' holds the place of the right border of the 
          range.  'i' becomes the left border that moves to the right 
          and 'j' becomes the right border that moves to the left.
          ===========================================================  */

          i = l;
          j = r;


/*        Fetch the record in the middle of the range (m).
          ================================================  */

          m = (i + j) >> 1;            /* Calculate the record number.     */
          pageIn (jobIn, m, i, j);     /* Get its vpage in memry (hold i&j)*/
          if (jobIn.error != 0) return; /* . . . check for i/o error . . . */
          itemZ.getItem (jobIn, m);    /* Fetch the item's memory address. */
          System.arraycopy             /* Move Z record to a save Z area.  */
            (
            jobIn.rpage_ptr[itemZ.iRealPageNumber], 
            itemZ.iItemOffset, 
            savez, 
            0, 
            jobIn.itemlgth
            );


/*        Cycle 2.  This loop actually processes the range.
          =================================================  */

          do
            {


/*          Fetch the first left record (i).
            ================================  */

            pageIn (jobIn, i, j, m);   /* Get its vpage in memry (hold j&m)*/
            if (jobIn.error != 0) return; /* . . . check for i/o error . . */
            itemX.getItem (jobIn, i);  /* Fetch the item's memory address. */


/*          Each cycle of this loop compares the left item with the 
            middle item using the user written ordering function 
            'less()'.  If the two items are in order, it moves the 
            left border one item to the right and compairs it with 
            the middle item.  This continues until a left item is 
            found that is >= the middle item.
            =======================================================  */

            while (less (jobIn, itemX, savez))
              {
              i++;                     /* Move left bordr 1 positn to right*/
              pageIn (jobIn, i, j, m); /* Get new left item's pg holdg j&m.*/
              if (jobIn.error != 0) return; /* . . . check for i/o error . */
              itemX.getItem (jobIn, i);/* Fetch the item's memory address. */
              }


/*          Fetch the first right record (j).
            =================================  */

            pageIn (jobIn, j, i, m);   /* Get its vpage in memry (hold i&m)*/
            if (jobIn.error != 0) return; /* . . . check for i/o error . . */
            itemY.getItem (jobIn, j);  /* Fetch the item's memory address. */


/*          Each cycle of this loop compares the right item with the 
            middle item using the user written ordering function 
            'less()'.  If the two items are in order, it moves the 
            right border one item to the left and compairs it with 
            the middle item.  This continues until a left item is 
            found that is >= the middle item.  
            ========================================================  */

            while (less (jobIn, savez, itemY))
              {
              j--;                     /* Move right bordr 1 positn to left*/
              pageIn (jobIn, j, i, m); /* Get new right item's pg holdg i&m*/
              if (jobIn.error != 0) return; /* . . . check for i/o error . */
              itemY.getItem (jobIn, j);/* Fetch the item's memory address. */
              }


/*          The previous processing has guaranteed that the specific 
            items that i, m, and j are pointing to are ordered exactly 
            backwards -- i > m > j.  Now that this is established, 
            items i and j can be swapped to cause them to be ordered 
            correctly -- i < m < j.  Only perform swapping if the 
            borders haven't crossed.
            ==========================================================  */

            if (i <= j)
              {


/*            There is no need to swap an item with itself.
              =============================================  */

              if (i != j)
                {
                exchange (jobIn, i, j, swoppost);
                }


/*            Narrow the range to two new items.
              ==================================  */

              i++;
              j--;
              }


/*          End of cycle 2: After the possible increment just above check
            to see if the approaching borders have crossed.  If not then
            loop back to the top of cycle 2.
            =============================================================  */

            } while (i <= j);


/*        The range is now logically divided into two sections.  The left
          section is from the original left border to the current left 
          border.  The right section of from the original right border to
          the the current right border.  Determine which section is the
          longest.
          ===============================================================  */

          if (j - l < r - i)
            {


/*          If the right section is longer and has at least some length,
            save it as a range on the stack for latter processing.
            ============================================================  */

            if (i < r)
              {
              sp++;
              lstack[sp] = i;
              rstack[sp] = r;
              }


/*          . . . and establish the left section as the new range to 
            process.
            ========================================================  */

            r = j;
            }


/*        If the left section is longer and has at least some length,
          save it as a range on the stack for latter processing.
          ===========================================================  */

          else
            {
            if (l < j)
              {
              sp++;
              lstack[sp] = l;
              rstack[sp] = j;
              }


/*          . . . and establish the right section as the new range to 
            process.
            ========================================================= */

            l = i;
            }


/*        End of cycle 1.  This loop continues until the approaching 
          left and right borders meet.
          ==========================================================  */

          } while (l < r);
        }
      }



/*    R E G I S T E R
 */
/**
 */
private void register (String sServiceNameIn, ServiceIDListener sidServiceIn)
      {
      int i;
      int iPort;
      String sHost;
      LookupLocator lookup;
      Entry[] aeAttributes;
      JoinManager joinmanager;
      ServiceID id;       
      ServiceMatches matches;
      ServiceRegistrar registrar;


      try 
        {
        System.setSecurityManager (new RMISecurityManager ());


/*      Register with the lookup service.
        =================================  */

        aeAttributes = new Entry[1];
        aeAttributes[0] = new Name(sServiceNameIn);
        joinmanager = new JoinManager 
          (
          sidServiceIn, 
          aeAttributes, 
          sidServiceIn, 
          new LeaseRenewalManager ()
          );
        System.out.println ();
        System.out.println ("register(): JoinManager = " + joinmanager);
        } 

      catch (Exception e) 
        {
        System.out.println("server: JSort.register(): Exception " + e);
        }
      }



/*    R E L E A S E   B L O C K
 */
/**   This processes a block of sort items, one item at a time.  This
 *    improves input performance by optimizing network transfer.
 *
 */
public void releaseBlock (String sJobNameIn, byte[] abIn) // JSortInterface
      throws RemoteException
      {
      String s;
      int iOffset;
      JSortJob job;
      Hashtable ht;

      job = (JSortJob) htSortJobs.get (sJobNameIn);
      ht = new Hashtable ();
      ht.put (JOB_NAME_TAG, sJobNameIn);

      for (iOffset = 0; iOffset + job.itemlgth <= abIn.length; 
        iOffset += job.itemlgth)
        {
        s = new String (abIn, iOffset, job.itemlgth);
        ht.put (DATA_TAG, s);
        releaseRecord (ht);
        }            
      }



/*    R E L E A S E   R E C O R D
 */
/**   This function copies a record from the passed parameter hashtable 
 *    into the virtual sort system.  If real memory becomes full, this 
 *    creates the sort work file.
 *
 */
public Hashtable releaseRecord (Hashtable htParmsIn)    // JSortInterface
      throws RemoteException
      {
      int i;
      byte[] ab;
      String recptr;
      String s;
      JSortJob job;
      int next_itemptr;
      File fJobDirectory;


      s = (String) htParmsIn.get (JOB_NAME_TAG);
      job = (JSortJob) htSortJobs.get (s);
      recptr = (String) htParmsIn.get (DATA_TAG);


/*    Return if an error has been encountered during sort input.
      ==========================================================  */
    
      if (job.error != 0)
        {
        System.out.println ("releaseRecord(): error has occurred");
        return (new Hashtable ());       // zzz
        }


/*    The number of sort records is limited to the range of an 
      unsigned long.
      ========================================================  */

      if (job.num_items == LONGLGTH)
        {
        System.out.println ("releaseRecord(): too many sort recs " 
          + job.num_items);
        job.error = 9;
        return (new Hashtable ());       // zzz
        }


/*    If the input process is at a page boundary and internal memory has
      been exhausted, do virtual paging out.
      ==================================================================  */

      if (job.iDebug > 6)
        {
        writeDebug (job, "releaseRecord(): num_leftovr_items=" 
          + job.num_leftovr_items + " num_vpages=" + job.num_vpages 
          + " numrpages=" + job.num_rpages);
        }
      if ((job.num_leftovr_items == 0) && (job.num_vpages >= job.num_rpages))
        {


/*      If real memory pages have JUST been filled then create the sort
        work virtual file.
        ===============================================================  */

        if (job.num_vpages == job.num_rpages)
          {
          try
            {
            fJobDirectory = new File (job.sJobName);
            if (!fJobDirectory.mkdir ())                   // Create dir
              {
              if (job.iDebug > 0)
                {
                writeDebug (job, "releaseRecord(): Can not create the "
                  + "work directory " + job.sJobName + " continuing...");
                }
              }
            job.sortwkfile = new RandomAccessFile (job.sJobName + "/" 
              + job.sortwkfilename, "rw");
            }
          catch (Exception e)
            {
            System.out.println ("releaseRecord(): exception creating "
              + "sort work file: " + job.sJobName + "/" + job.sortwkfilename
              + ": " + e);
            job.error = 12;
            return (new Hashtable ());    //zzz
            }
          job.filecreated = true;


/*        . . . and write all but the last real page to it.  Note that 
          the records in the file are pages full of a fixed number of 
          sort items.
          ============================================================  */

          for (i = 0; i < job.num_rpages - 1; i++)
            {
            pageOut (job, job.rpage_ptr[i], i);
            }
          }


/*      Whether real memory has JUST been filled or has LONG been filled,
        write the virtual page in the last real page to the file.
        =================================================================  */

        pageOut (job, job.rpage_ptr[job.num_rpages - 1], 
          job.vpage_num[job.num_rpages - 1]);


/*      Increment the virtual page number in the last real page slot.
        =============================================================  */

        job.vpage_num[job.num_rpages - 1]++;
        initPage (job.rpage_ptr[job.num_rpages - 1]);
        }


/*    After doing any necessary paging out, select the current real 
      page . . .
      ============================================================= */

      if (job.num_vpages >= job.num_rpages)
        {
        job.curr_rpage = job.num_rpages - 1;
        }

      else
        {
        job.curr_rpage = job.num_vpages;
        }


/*    . . . and the spot in which to place the next item . . .
      ========================================================  */

      next_itemptr = job.num_leftovr_items * job.itemlgth;


/*    . . . and move the new item to that slot.
      =========================================  */

      ab = recptr.getBytes ();
      System.arraycopy 
        (
        ab, 
        0, 
        job.rpage_ptr[job.curr_rpage], 
        next_itemptr, 
        job.itemlgth
        );


/*    Increment counters.
      ===================  */

      job.num_items++;
      job.num_leftovr_items++;
      if (job.num_leftovr_items == job.items_pr_page)
        {
        job.num_leftovr_items = 0;
        job.num_vpages++;
        }
      if (job.iDebug > 8)
        {
        writeDebug (job, "releaseRecord(): buffer-->" 
          + new String (job.rpage_ptr[job.curr_rpage]).substring (0, next_itemptr + job.itemlgth) 
          + "<--");
        }
      if (job.iDebug > 4)
        {
        writeDebug (job, "releaseRecord(): job: " + job);
        }

      return (new Hashtable ());  //zzz
      }



/*    R E T U R N   B L O C K
 */
/**   This accepts the number of requested sort items and returns a 
 *    byte array that consists of the requested number of sort items.
 *    if the number of items that is returned is less than the requested
 *    number, the end of the sortwork file has been reached.
 *
 */
public byte[] returnBlock (String sJobNameIn, int iNumReqItemsIn) // JSortInterface
      throws RemoteException
      {
      int i;
      String s;
      Hashtable ht;
      Hashtable htRet;
      JSortJob job;
      boolean bEof;
      ByteArrayOutputStream baos;

      baos = new ByteArrayOutputStream ();
      job = (JSortJob) htSortJobs.get (sJobNameIn);
      ht = new Hashtable ();
      ht.put (JOB_NAME_TAG, sJobNameIn);
      bEof = false;

      for (i = 0; (i < iNumReqItemsIn) && !bEof; i++)
        {
        htRet = returnRecord (ht);
        if (htRet.get (JSortInterface.EOF_TAG) != null)
          {
          bEof = true;
          continue;
          }

        s = (String) htRet.get (DATA_TAG);
        try
          {
          baos.write (s.getBytes ());
          }
        catch (Exception e)
          {
          System.out.println (job.sJobName + ": returnBlock(): exception: " 
            + e);  //zzz
          }
        }

      return (baos.toByteArray ());
      }



/*    R E T U R N   R E C O R D
 */
/**   This finds the current sort output item and returns it to the caller.
 *    When the last record is fetched, the job's current item is set to
 *    -1.  Rewind sets it to 0.
 *
 */
public Hashtable returnRecord (Hashtable htParmsIn)     // JSortInterface
      throws RemoteException
      {
      byte[] ab;
      String recptr;
      String s;
      JSortJob job;
      JSortItem item;


/*    Get the job name.
      =================  */

      s = (String) htParmsIn.get (JOB_NAME_TAG);
      job = (JSortJob) htSortJobs.get (s);


/*    Screen for i/o error.
      =====================  */

      if (job.error != 0)
        {
        System.out.println ("returnRecord(): encountered error " + job.error);
        return (new Hashtable ());       // zzz
        }


/*    If end of file has been reached, return no data record and set
      the end of file marker.
      ==============================================================  */

      if (job.curr_item < 0)
        {
        htParmsIn.remove (DATA_TAG);
        htParmsIn.put (EOF_TAG, "true");
        return (htParmsIn);
        }


/*    Fetch the page that corresponds to the current output record.  
      Notice that this is done while requesting that only the last 
      page be kept in memory.  The negative entry is resolved to a 
      virtual page number of -1.  There is no virtual page numbered -1.
      =================================================================  */

      pageIn (job, job.curr_item, job.num_items - 1, -job.items_pr_page);


/*    Fetch the address of the current output item in memory and move 
      it to caller storage.
      ===============================================================  */

      item = new JSortItem ();
      item.getItem (job, job.curr_item);
      ab = new byte[job.itemlgth];
      System.arraycopy 
        (
        job.rpage_ptr[item.iRealPageNumber],
        item.iItemOffset,
        ab,
        0,
        job.itemlgth
        );


/*    If the item that was processed was the last item, then set
      the job's current item to -1.  Else increment the current 
      output item number.
      ==========================================================  */

      if (job.curr_item >= job.num_items - 1)
        {
        job.curr_item = -1;
        }
      else
        {
        job.curr_item++;
        }
      htParmsIn.put (DATA_TAG, new String (ab));
      htParmsIn.remove (EOF_TAG);

      return (htParmsIn);
      }



/*    R E W I N D 
 */
/**   This resets the current item counter to 0 which allows returnRec
 *    to start over at the beginning of the sort work file.
 *
 */
public Hashtable rewind (Hashtable htParmsIn)           // JSortInterface
      throws RemoteException
      {
      String s;
      JSortJob job;


/*    Get the job name.
      =================  */

      s = (String) htParmsIn.get (JOB_NAME_TAG);
      job = (JSortJob) htSortJobs.get (s);


/*    Reset the current item.
      =======================  */

      job.curr_item = 0;

      htParmsIn.put (RETURN_TAG, String.valueOf (job.error));
      return (htParmsIn);
      }



/*    S E R V I C E   I D   N O T I F Y
 */
/**
 */
public void serviceIDNotify (ServiceID sidIn)           // ServiceIDListener
      {
      System.out.println ("serviceIDNotify(): received ServiceID = " 
        + sidIn);
      }



/*    S O R T
 */
/**
 */
public Hashtable sort (Hashtable htParmsIn)             // JSortInterface
      throws RemoteException
      {
      int i;
      String s;
      JSortJob job;


/*    Get the job name.
      =================  */

      s = (String) htParmsIn.get (JOB_NAME_TAG);
      job = (JSortJob) htSortJobs.get (s);


/*    Sort the job.
      =============  */

      job.curr_item = 0;
      quickSort (job, new byte[job.itemlgth], new byte[job.itemlgth]);


/*    If a sortwork file was created, save all dirty real pages back
      to the file.  Each cycle of the loop conditionally saves one
      real page to its spot in the sortwork file.
      ==============================================================  */

      if (job.filecreated)
        {
        for (i = 0; i < job.rpage_ptr.length; i++)
          {
          if (job.iDebug > 4)
            {
            writeDebug (job, "Checking real page " + i + " modified = " 
              + job.rpage_modified[i]);
            }
          if (job.rpage_modified[i])
            {
            pageOut (job, job.rpage_ptr[i], job.vpage_num[i]);
            if (job.error != 0) break;
            }
          }
        }

      htParmsIn.put (RETURN_TAG, String.valueOf (job.error));
      return (htParmsIn);
      }



/*    T E S T
 */
/**
 */
private void test ()
      {
      Hashtable ht, htRet;

      ht = new Hashtable ();

      try
        {
        ht.put (FIELD_TAG + "1", "0-1");
        ht.put (ORDER_TAG + "1", ASCENDING_VALUE);
        ht.put (FIELD_TAG + "2", "2-4");
        ht.put (ORDER_TAG + "2", DESCENDING_VALUE);
        ht.put (REC_LENGTH_TAG,  "5");
        ht.put (DEBUG_TAG, "10");
        htRet = open (ht);
        System.out.println ("Return from open: " + htRet);

        ht.put (JOB_NAME_TAG, htRet.get (JOB_NAME_TAG));

        ht.put (DATA_TAG,     "eeccc");
        htRet = releaseRecord (ht);

        ht.put (DATA_TAG,     "eebbb");
        htRet = releaseRecord (ht);

        ht.put (DATA_TAG,     "eeccc");
        htRet = releaseRecord (ht);

        ht.put (DATA_TAG,     "eeaaa");
        htRet = releaseRecord (ht);

        ht.put (DATA_TAG,     "ddaaa");
        htRet = releaseRecord (ht);

        ht.put (DATA_TAG,     "ddbbb");
        htRet = releaseRecord (ht);

        ht.put (DATA_TAG,     "ddccc");
        htRet = releaseRecord (ht);

        ht.put (DATA_TAG,     "ddddd");
        htRet = releaseRecord (ht);

        ht.put (DATA_TAG,     "aaccc");
        htRet = releaseRecord (ht);

        ht.put (DATA_TAG,     "aabbb");
        htRet = releaseRecord (ht);

        ht.put (DATA_TAG,     "aaaaa");
        htRet = releaseRecord (ht);

        htRet = sort (ht);
        System.out.println ("\nSort return: " + htRet + "\n");

        htRet = returnRecord (ht);
        while (htRet.get (EOF_TAG) == null)
          {
          System.out.println ("Returned -->" + htRet.get (DATA_TAG) + "<--"
            + " EOF=" + htRet.get (EOF_TAG));
          htRet = returnRecord (ht);
          }

        System.out.println ("\nrewind, htRet=" + rewind (htRet) + "\n");

        htRet = returnRecord (ht);
        while (htRet.get (EOF_TAG) == null)
          {
          System.out.println ("Returned -->" + htRet.get (DATA_TAG) + "<--"
            + " EOF=" + htRet.get (EOF_TAG));
          htRet = returnRecord (ht);
          }

        htRet = close (ht);
        System.out.println ("\nClose return: " + htRet + "\n");
        }
      catch (Exception e)
        {
        System.out.println ("test(): exception opening sort job: " + e);
        }
      }



/*    W R I T E   D E B U G
 */
/**
 */
private void writeDebug (JSortJob jobIn, String sIn)
      {
      try
        {
        jobIn.rafDebug = new RandomAccessFile 
          (
          jobIn.sJobName + "/" + jobIn.debugfilename, 
          "rw"
          );
        jobIn.rafDebug.seek (jobIn.rafDebug.length ());
        jobIn.rafDebug.write ((sIn + sCRLF).getBytes ());
        jobIn.rafDebug.close ();
        }
      catch (Exception e) 
        {
        }
      }

      }


/*==========================(  End of Source  )============================*/