/* sort.c (comment7.c) - Sort screen characters - Don Yang (uguu.org)

   DOS only: cl sort.c

   This is the kind of program where confusion comes not solely from
   layout and misleading variable names, but mainly from flow of control.
   I would probably forget how it goes two days later too, so here it is:

      1. Startup: System calls main(+,?,?)
         First argument will be positive value, because that is argument
         count (argc) and is at least 1.  main() then maps the screen
         indexes, skipping all characters in "DON".  Indexes for each row
         are also stored at this time.

      2. Sort rows: main(+,?,?) calls main(-,?,?)
         First argument is negative, denoting the row index (25-a).  First
         call to this part of main() will have argument -1, meaning the
         last screen row.  main() will then recursively sort all rows above
         that row before sorting the current row (i.e. sorting from top to
         bottom).

      3. Quicksort: main(-,?,?) calls main(0,low,high)
         First argument is zero, second and third arguments are logical
         screen indexes (this is the only time when those arguments are
         meaningful).  This is the standard quicksort algorithm, with the
         first element as pivot.

      4. Shellsort: main(+,?,?) calls shell()
         After returning from step 2, main() does shell sort on entire
         screen.  shell() will call itself recursively to sort larger
         spans first.

      5. End: main(+,?,?) returns.
         So it wasn't that complicated after all ^_^

   There are some differences between this version and the preprocessed /
   arranged version, but the flow of control stays the same.

   System notes:
      b800:0000 is VGA text memory buffer for mode 3.
      0040:006c is system clock, updated regularly 18.2 times per second.

   System clock is a less accurate way to synchronize / slow down the
   program, but it works under DOS box and lets me get rid of included files
   completely :)

   Now that I got it recursive, maybe the next program will be
   multithreaded?

   05/04/99: main
             wait
             shell
                                                                           */

/* System */
int far *screen = (int far *)0xb8000000;
volatile long far *clock = (long far *)0x0040006c;

/* Sync */
long tick;

/* Screen map */
int order[2000], limit;
int row[26];

/* etc */
int i, j, k;
int swaptmp, swapcount = 0;

/********************************************************************** swap
   Swap screen characters / wait for clock sync.                           */
void swap(int a, int b, int wait)
{
   screen[order[a]] ^= 0x1100;
   screen[order[b]] ^= 0x2200;
   swaptmp = screen[order[a]];
   screen[order[a]] = screen[order[b]];
   screen[order[b]] = swaptmp;

   swapcount++;
   if( (swapcount % wait) == 0 && (swaptmp & 0xff) != ' ' )
   {
      while( tick == *clock );
      tick = *clock;
   }
   screen[order[a]] ^= 0x2200;
   screen[order[b]] ^= 0x1100;

} /* swap() */

/********************************************************************* shell
   Shell sort entire screen                                                */
void shell(int span)
{
   /* Sort next span */
   if( span < (limit / 2) )
      shell(span * 2);

   do
   {
      for(i = j = 0; i < limit - span; i++)
      {
         if( (screen[order[i]] & 0xff) < (screen[order[i + span]] & 0xff) )
            swap(i, i + (j = span), 10);
      }
   } while( j );

} /* shell() */

/********************************************************************** main
   Quick sort each row / initialize                                        */
void main(int state, int lowerbound, int upperbound)
{
   if( state > 0 )
   {
      /* Initial state */

      /* Initialize offsets */
      for(i = limit = 0; i < 2000; i++)
      {
         if( !(i % 80) )
            row[i / 80] = limit;

         order[limit] = i;
         if( (screen[i] & 0xff) != 'D' &&
             (screen[i] & 0xff) != 'O' &&
             (screen[i] & 0xff) != 'N' )
            limit++;
      }
      row[25] = limit;

      main(-1, 0, 0);
      shell(1);
   }
   else if( !state )
   {
      /* Quick sort */
      if( upperbound > lowerbound )
      {
         k = screen[order[lowerbound]] & 0xff;

         i = lowerbound;
         j = upperbound;

         while( i <= j )
         {
            while( i < upperbound && (screen[order[i]] & 0xff) < k )
               i++;
            while( j > lowerbound && (screen[order[j]] & 0xff) > k )
               j--;

            if( i <= j )
            {
               swap(i, j, 8);
               i++;
               j--;
            }
         }
         main(0, lowerbound, j);
         main(0, i, upperbound);
      }
   }
   else  /* state < 0 */
   {
      /* Sort row */
      if( state > -25 )
         main(state - 1, 0, 0);

      main(0, row[25 + state], row[26 + state] - 1);
   }

} /* main() */