/* 
   ======================================================================
   Header for N-way out-of-core merge sort for records with 3D keys.
   
   Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
   (c) Lucerne University of Applied Sciences and Arts,
       supported by the Swiss National Science Foundation (SNSF, #147053)
   ======================================================================   
   
   $Id: oocsort.h,v 2.3 2016/05/17 17:39:47 rschregle Exp $
*/

#ifndef OOC_SORT_H
   #define OOC_SORT_H
   
   #include "fvect.h"
   #include "morton.h"
   #include <stdio.h>



   /* Priority queue node */
   typedef struct {
      MortonIdx         pri;        /* Record's priority (sort key) */
      unsigned          blk;        /* Block containing record */
   } OOC_SortQueueNode;

   /* Priority queue */
   typedef struct {
      OOC_SortQueueNode *head;
      unsigned          len, tail;
   } OOC_SortQueue;

   /* Additional data for key comparison function.*/
   typedef struct {
      RREAL *(*key)(const void*);   /* Callback to access 3D key in record */
      FVECT bbOrg;                  /* Origin of bbox containing keys */
      RREAL mortonScale;            /* Scale for generating Morton code */
   } OOC_KeyData;



   /* Read next record from file; return 0 and record in rec on success, 
    * else -1 */
   int OOC_SortRead (FILE *file, unsigned recSize, char *rec);

   /* Return next record from file WITHOUT advancing file position;
    * return 0 and record in rec on success, else -1 */
   int OOC_SortPeek (FILE *file, unsigned recSize, char *rec);

   /* Output record to file; return 0 on success, else -1 */
   int OOC_SortWrite (FILE *file, unsigned recSize, const char *rec);

   /* Insert specified block index into priority queue; return block index 
    * or -1 if queue is full */
   int OOC_SortPush (OOC_SortQueue *pq, MortonIdx pri, unsigned blk);

   /* Remove head of priority queue and return its block index or -1 
      if queue empty */
   int OOC_SortPop (OOC_SortQueue *pq);

   /* Sort records in inFile and append to outFile by subdividing inFile
    * into small blocks, sorting these in-core, and merging them out-of-core
    * via a priority queue.
    *
    * This is implemented as a recursive (numBlk)-way sort; the input is
    * successively split into numBlk smaller blocks until these are of size
    * <= blkSize, i.e.  small enough for in-core sorting, then merging the
    * sorted blocks as the stack unwinds.  The in-core sort is parallelised
    * over numProc processes.
    *
    * Parameters are as follows:
    * inFile      Opened input file containing unsorted records
    * outFile     Opened output file containing sorted records
    * numBlk      Number of blocks to divide into / merge from 
    * blkSize     Max block size and size of in-core sort buffer, in bytes 
    * numProc     Number of parallel processes for in-core sort 
    * recSize     Size of input records in bytes
    * bbOrg       Origin of bounding box containing record keys for Morton code
    * bbSize      Extent of bounding box containing record keys for Morton code
    * key         Callback to access 3D coords from records for Morton code
    */
   int OOC_Sort (FILE *inFile, FILE *outFile, 
      unsigned numBlk, unsigned long blkSize, unsigned numProc, 
      unsigned recSize, FVECT bbOrg, RREAL bbSize, 
      RREAL *(*key)(const void*));
#endif