/* ---------------------------------------------------------------------------
  fgets
  Purpose: Read one line from the Atari file descriptor into a bounded buffer.
  Parameters: data - destination character buffer; max - buffer capacity including
    the terminating null; fp - open file descriptor to read from.
  Returns: data, with "*" as the first character when end-of-input is reached.
  Variables used: r, c, i - character status, current byte, and buffer position.
  --------------------------------------------------------------------------- */
fgets(data,max,fp)
char *data;
int max,fp;
$(
  int r,c,i;
  i=0;
  while(i<max-1) $(
    c=cgetc(fp);
    if(c==-1) break;
    if(c==0) break;
    if(c==155) break;
    data[i]=c;
    i++;
  $)
  if(i==0 && (c==-1 || c==0)) $(
    data[0]='*';
    data[1]='\0';
    return data;
  $)
  data[i]='\0';
  if(c!=155) $(
    while(1) $(
      c=cgetc(fp);
      if(c==-1 || c==155 || c==0) break;
    $)
  $)
  return data;
$)

/* ---------------------------------------------------------------------------
  itostr
  Purpose: Convert a signed integer to a null-terminated decimal string.
  Parameters: value - integer to format; str - destination buffer.
  Returns: Pointer to the byte after the terminating null character.
  Variables used: neg - sign flag; idx - digit count/index; tmp - reversed digits.
  --------------------------------------------------------------------------- */
itostr(value,str)
int value;
char *str;
$(
  int neg,idx;
  char tmp[16];

  neg = 0;
  if(value < 0) $(
    neg = 1;
    value = -value;
  $)

  idx = 0;
  do $(
    tmp[idx] = (value % 10) + '0';
    value = value / 10;
    idx++;
  $) while(value != 0);

  if(neg) $(
    tmp[idx] = '-';
    idx++;
  $)

  while(idx > 0) $(
    idx--;
    *str = tmp[idx];
    str++;
  $)

  *str = '\0';
  return str;
$)

/* ---------------------------------------------------------------------------
  fputs
  Purpose: Write a null-terminated string and Atari end-of-line marker.
  Parameters: data - string to write; fp - open destination file descriptor.
  Returns: The final character-write result, or the first write error.
  Variables used: r - status from writing the string and line-ending byte.
  --------------------------------------------------------------------------- */
fputs(data,fp)
char *data;
int fp;
$(
  int r;
  r=cputs(data,fp);
  if(r<0) return r;
  return cputc(155,fp);
$)
/* ---------------------------------------------------------------------------
  log
  Purpose: Compute the integer base-two depth estimate used by introsort.
  Parameters: v - positive value whose repeated divisions are counted.
  Returns: Number of divisions needed to reduce v to zero; zero when v <= 0.
  Variables used: n - accumulated division count.
  --------------------------------------------------------------------------- */
log(v)
int v;
$(
  int num;
  num=0;
  while(v>0) $(
    v/=2;
    num++;
  $)
  return num;
$)

/* ---------------------------------------------------------------------------
  swap
  Purpose: Exchange the integer values stored at two addresses.
  Parameters: a, b - pointers to the values to exchange.
  Returns: No value; updates the two pointed-to integers.
  Variables used: t - temporary storage for one value during the exchange.
  --------------------------------------------------------------------------- */
swap(a,b)
int *a;
int *b;
$(
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
$)

/* ---------------------------------------------------------------------------
  readfile
  Purpose: Open the configured input and load up to 1000 integers into values.
  Parameters: None; the input path is fixed in this routine.
  Returns: No value; updates global values and numvals.
  Variables used: fp - file descriptor; c - iteration state; tmp - line buffer.
  --------------------------------------------------------------------------- */
readfile()
$(
  int fp,c;
  char tmp[16];
  cprints("READING INPUT FILE...");
  fp=open(2,4,0,"D:INPUT.TXT");
  if(fp!=1) $(
    printf("ERROR [%d]: Cannot open file.\n", fp);
    return;
  $)
  numvals = 0;
  while(numvals<1000) $(
    fgets(tmp,16,2);
    if(tmp[0]=='*')break;
    values[numvals]=val(tmp);
    numvals++;
  $)
  cprints("DONE.\n");
  cclose(2);
  return;
$)

/* ---------------------------------------------------------------------------
  savefile
  Purpose: Write each sorted value to the configured output file on its own line.
  Parameters: None; the output path and data are held by the program.
  Returns: No value; reports an open failure to the console.
  Variables used: fp - output file descriptor; c - current values index; tmp - number text.
  --------------------------------------------------------------------------- */
savefile()
$(
  cprints("SAVING OUTPUT FILE...");
  int fp,c;
  char tmp[16];
  fp=open(2,8,0,"D:OUTPUT.TXT");
  if(fp!=1) $(
    printf("ERROR [%d]: Cannot save file.",fp);
    return;
  $)
  for(c=0;c<numvals;c++) $(
    itostr(values[c],tmp);
    fputs(tmp,2);
  $)
  cprints("DONE.\n");
  cclose(2);
  return;
$)

/* ---------------------------------------------------------------------------
  partiton
  Purpose: Partition an array range around its middle element for introsort.
  Parameters: values - array to rearrange; start - inclusive range start;
    end - exclusive range end.
  Returns: Index of the first element in the right partition.
  Variables used: left, right - scanning indices; pivot - comparison value.
  --------------------------------------------------------------------------- */
partiton(values,start,end)
int *values;
int start,end;
$(
  int pivot,left,right;
  pivot=values[(start+(end-start)/2)];
  left = start;
  right = end - 1;
  while(left <= right) $(
    while(values[left]<pivot)left++;
    while(values[right]>pivot)right--;
    if(left<=right) $(
      swap(&values[left],&values[right]);
      left++;
      right--;
    $)
  $)
  return left;
$)

/* ---------------------------------------------------------------------------
  siftdown
  Purpose: Restore the max-heap property below root within a heap range.
  Parameters: values - array to mutate; root - subtree root; start - inclusive
    heap start; end - exclusive heap end.
  Returns: No value; moves the root value down as required.
  Variables used: child - selected larger child index.
  --------------------------------------------------------------------------- */
siftdown(values,root,start,end)
int *values;
int root,start,end;
$(
  int child;
  while(start+2*(root-start)+1<end) $(
    child=start+2*(root-start)+1;
    if(child+1<end && values[child]<values[child+1]) child++;
    if(values[root]>=values[child]) return;
    swap(&values[root],&values[child]);
    root=child;
  $)
$)

/* ---------------------------------------------------------------------------
  heapsort
  Purpose: Sort a range in ascending order as introsort's depth-limit fallback.
  Parameters: values - array to sort; start - inclusive range start; end -
    exclusive range end.
  Returns: No value; sorts the range in place and increments heaps.
  Variables used: root - heap-build position; last - extraction boundary.
  --------------------------------------------------------------------------- */
heapsort(values,start,end)
int *values;
int start,end;
$(
  heaps++;
  int root,last;
  for(root=start+((end-start)/2)-1;root>=start;root--) $(
    siftdown(values,root,start,end);
  $)
  for(last=end-1;last>start;last--) $(
    swap(&values[start],&values[last]);
    siftdown(values, start, start, last);
  $)
$)

/* ---------------------------------------------------------------------------
  insertst
  Purpose: Sort a short range in ascending order using insertion sort.
  Parameters: values - array to sort; start - inclusive range start; end -
    exclusive range end.
  Returns: No value; sorts the range in place and increments inserts.
  Variables used: index - next item; value - saved item; pos - insertion scan.
  --------------------------------------------------------------------------- */
insertst(values,start,end)
int *values;
int start,end;
$(
  inserts++;
  int value,pos,index;
  for(index=start;index<end;index++) $(
    value = values[index];
    pos = index - 1;
    while(pos >=start && values[pos] > value) $(
      values[pos+1]=values[pos];
      pos--;
    $)
    values[pos+1]=value;
  $)
$)

/* ---------------------------------------------------------------------------
  introsrt
  Purpose: Sort a range using insertion sort, partitioning, and heapsort fallback.
  Parameters: values - array to sort; start - inclusive start; end - exclusive
    end; maxDepth - remaining partition budget before heapsort is selected.
  Returns: No value; sorts in place and updates the sort-call counters.
  Variables used: length - range size; part - partition boundary; globals count
    calls to introsort, insertion sort, and heapsort.
  --------------------------------------------------------------------------- */
introsrt(values,start,end,maxDepth)
int *values;
int start,end,maxDepth;
$(
  intros++;
  int length,part;
  length=end-start;
  if(length<=1)return;
  if(length<16)insertst(values,start,end);
  else if(maxDepth<=0)heapsort(values,start,end);
  else $(
    part = partiton(values,start,end);
    introsrt(values,start,part,maxDepth-1);
    introsrt(values,part,end,maxDepth-1);
  $)
$)

/* ---------------------------------------------------------------------------
  dosort
  Purpose: Time introsort over all loaded values using a depth limit of 2*log2(n).
  Parameters: None; operates on global values and numvals.
  Returns: Elapsed time in seconds.
  Variables used: start, end - range bounds; maxDepth - partition budget.
  --------------------------------------------------------------------------- */
dosort()
$(
  int start, end, maxDepth;
  int sTime, eTime;
  cprints("SORTING ELEMENTS...");
  sTime=(peek(18)*65536+peek(19)*256+peek(20))/60;
  maxDepth=0;
  if(numvals>1) $(
    maxDepth=2*log(numvals);
  $)
  introsrt(values,0,numvals,maxDepth);
  eTime=(peek(18)*65536+peek(19)*256+peek(20))/60;
  cprints("DONE.\n");
  return eTime-sTime;
$)

int values[1000];
int numvals;
int intros;
int inserts;
int heaps;

/* ---------------------------------------------------------------------------
  main
  Purpose: Initialize the Atari environment, process the data, and report timings.
  Parameters: None.
  Returns: Program exit status from the platform's termination routine.
  Variables used: elapsed - duration returned by dosort; global counters report
    how often each sorting routine was called.
  --------------------------------------------------------------------------- */
main()
$(
  int elapsed;
  intros=inserts=heaps=0;
  graphics(0);
  cprints("�������������Ԡ���Р���Šý�����");
  readfile();
  elapsed=dosort();
  savefile();
  cprints("������������Π�������Ž���������");
  printf("INTROSORT TOOK %d SECONDS.\n", elapsed);
  cprints("================================");
  cprints("SORT CALLED | TIMES");
  printf ("Intro       | %d",intros);
  printf ("Insertion   | %d",inserts);
  printf ("Heap        | %d",heaps);
  cprints("================================");
  gets();
  return 0;
$)