/* ---------------------------------------------------------------- */
/* PROGRAM  psort :                                                 */
/*    This program generates a Generator who keeps sending random   */
/* numbers to the first Sorter task, a Terminator who waits until   */
/* it received the END message and then exits, and many Sorter tasks*/
/* each of which has a mailbox connected with the previous Sorter   */
/* task, inBox, and a mailbox connected with its successor, outBox. */
/* The Generator has a mailbox connected with the first Sorter's    */
/* inBox, while the Terminator has a mailbox connected with the last*/
/* Sorter's outBox.                                                 */
/*    For each Sorter, it first gets a message from its inBox and   */
/* memorizes it.  Then, each Sorter keeps receiving messages from   */
/* its inBox.  If the incoming message if not an END, it is an      */
/* integer.  If this integer is larger than or equal to the number  */
/* that the Sorter memorized, the incoming number is sent to this   */
/* Sorter's neighbor via its outBox.  If this integer is smaller    */
/* than the number the Sorter's memorized, the new number is kept   */
/* and the memorized one is sent to the neighbor.                   */
/*    It is not difficult to see that when everyone receives the END*/
/* message, the numbers that are memorized by the Sorters are in    */
/* increasing order.  That is, they are sorted.                     */
/* ---------------------------------------------------------------- */

#include  <stdio.h>
#include  <stdlib.h>
#include  <time.h>
#include  "mtuThread.h"

#define   END       -1                  /* the END message          */
#define   MAX_NUM   10                  /* max # sent by Generator  */
#define   BOUND     100                 /* max value of random #s   */

/* ---------------------------------------------------------------- */
/*                        Function Prototypes                       */
/* ---------------------------------------------------------------- */

void  Generator(int);                   /* the Generator            */
void  Terminator(int);                  /* the Terminator           */
void  Sorter(int);                      /* the Sorters              */

/* ---------------------------------------------------------------- */
/*                             Mailboxes                            */
/* ---------------------------------------------------------------- */

MBOX_t   Box[MAX_NUM+1];              

/* ---------------------------------------------------------------- */
/* FUNCTION  Generator:                                             */
/*    Function Generator sends random numbers to mailbox Box[0].    */
/* After that it sends an END so that everybody would know to stop. */
/* ---------------------------------------------------------------- */

void  Generator(int ID)
{
     int  i;
     int  mail;

     srand((unsigned int) time(NULL));  /* init. random # generator */
     for (i = 0; i < MAX_NUM; i++) {    /* send numbers             */
          mail = rand() % BOUND;
          MSG_SEND(Box[0], mail);
     }
     MSG_SEND(Box[0], END);             /* send END                 */

     THREAD_EXIT();
}

/* ---------------------------------------------------------------- */
/* FUNCTION  Terminator:                                            */
/*    Function Terminator waits for the END message and then exits. */
/* Thus, stop all tasks.                                            */
/* ---------------------------------------------------------------- */

void  Terminator(int ID)
{
     int  data;

     if (MSG_RECEIVE(Box[MAX_NUM], &data) != END) /* waits msg      */
          printf("Oops, how could the Terminator get a non-END?\n");
     printf("\n");
     exit(0);                           /* it must be END.  Exit    */
}

/* ---------------------------------------------------------------- */
/* FUNCTION  Sorter:                                                */
/*   Each Sorter has an inBox and an outBox.  It receives the first */
/* number and memorizes the number.  Then, each Sorter iterates and */
/* receives new numbers.  If the new one is not smaller than the    */
/* one this Sorter memorizes, the new one is sent via the outBox to */
/* this Sorter's successor; otherwise, this Sorter memorizes the new*/
/* number and sends the memorized one.  At the end, this Sorter     */
/* displays the number it memorized and returns.                    */
/* ---------------------------------------------------------------- */

void  Sorter(int n)
{
     int  inBox  = n - 1;               /* my inBox                 */
     int  outBox = n;                   /* my outBox                */
     int  MyNumber;                     /* the number I memorized   */
     int  NewNumber;                    /* the incoming number      */

     MSG_RECEIVE(Box[inBox], &MyNumber);    /* receive my first no. */
     MSG_RECEIVE(Box[inBox], &NewNumber);   /* get the next one     */
     while (NewNumber != END) {         /* while it is not the END  */
          if (NewNumber >= MyNumber)    /* if it is larger, then    */
               MSG_SEND(Box[outBox], NewNumber);   /* send it       */
          else {                                   /* otherwise,    */
               MSG_SEND(Box[outBox], MyNumber);    /* send old      */
               MyNumber = NewNumber;    /* and keep the new one     */
          }
          MSG_RECEIVE(Box[inBox], &NewNumber);     /* receive next  */
     }
     printf("%4d", MyNumber);           /* END received! display    */
     MSG_SEND(Box[outBox], END);        /* pass the END to my neigh.*/

     THREAD_EXIT();
}


/* ---------------------------------------------------------------- */
/*                    The main program starts here                  */
/* ---------------------------------------------------------------- */

int main(int argc, char *argv[])
{
     THREAD_t  id[MAX_NUM+2];           /* thread ID                */
     int       i, No[MAX_NUM+2];

     for (i = 0; i < MAX_NUM+2; i++)    /* initialize task ID       */
          No[i] = i;

     for (i = 0; i <= MAX_NUM; i++)     /* get mailboxes            */
          Box[i] = MSG_INIT();
                                        /* create the generator     */
     id[0] = THREAD_CREATE(Generator, THREAD_SIZE, THREAD_NORMAL, 
			   No[0], (char **)0);
     for (i = 1; i < MAX_NUM+1; i++)    /* create sorters           */
          id[i] = THREAD_CREATE(Sorter, THREAD_SIZE, THREAD_NORMAL, 
				No[i], (char **)0);
                                        /* create the terminator    */
     id[MAX_NUM+1] = THREAD_CREATE(Terminator, THREAD_SIZE, THREAD_NORMAL, 
                                   No[MAX_NUM+1], (char **)0);
     THREAD_JOIN(id[MAX_NUM+1]);        /* never successful.  why?  */

     return 0;
}