int values[1000];
int numvals;

/* ---------------------------------------------------------------------------
  siftdown
  Purpose: restore the max-heap property below root in values[0..end-1].
  Parameters: values - array; root - subtree root; end - exclusive heap end.
  Returns: no value; mutates values.
  Variables used: child - index of the larger child.
  --------------------------------------------------------------------------- */
siftdown(values,root,end)
int *values;
int root;
int end;
$(
  int child;
  while(2*root+1<end)
  $(
    child=2*root+1;
    if(child+1<end && values[child]<values[child+1]) $(
      child++;
    $)
    if(values[root]>=values[child]) $(
      return;
    $)
    swap(&values[root],&values[child]);
    root=child;
  $)
$)

/* ---------------------------------------------------------------------------
  savefile
  Purpose: write values[0..numvals-1] to the output file, one per line.
  Parameters: none; uses global values and numvals.
  Returns: no value.
  Variables used: fp - file handle; c - array index; tmp - formatted value.
  --------------------------------------------------------------------------- */
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 open output file.\n",fp);
  $)
  for(c=0;c<numvals;c++) $(
    itostr(values[c],tmp);
    fputs(tmp,2);
  $)
  cprints("DONE.\n");
  cclose(2);
  return;
$)

/* ---------------------------------------------------------------------------
  loadfile
  Purpose: read input lines into values and update numvals.
  Parameters: none; uses global input path and values array.
  Returns: no value.
  Variables used: fp - file handle; tmp - input line buffer.
  --------------------------------------------------------------------------- */
loadfile()
$(
  int fp,c;
  char tmp[16];

  cprints("LOADING INPUT FILE...");
  fp=open(2,4,0,"D:INPUT.TXT");
  if(fp!=1) $(
    printf("ERROR [%d]: Cannot find input 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;
$)

/* ---------------------------------------------------------------------------
  dosort
  Purpose: heap-sort values[0..numvals-1] in place and measure elapsed jiffies.
  Parameters: none; uses global values and numvals.
  Returns: elapsed clock count.
  Variables used: start/end - heap indices; sTime/eTime - timer snapshots.
  --------------------------------------------------------------------------- */
dosort()
$(
  int start, end;
  int sTime, eTime;
  cprints("SORTING ELEMENTS...");
  sTime = (peek(18)*65536 + peek(19)*256 + peek(20))/60;
  for(start=(numvals/2)-1;start>=0;start--) $(
    siftdown(values,start,numvals);
  $)
  for(end=numvals-1;end>0;end--) $(
    swap(&values[0],&values[end]);
    siftdown(values,0,end);
  $)
  eTime = (peek(18)*65536 + peek(19)*256 + peek(20))/60;
  cprints("DONE.\n");
  return eTime - sTime;
$)

/* ---------------------------------------------------------------------------
  main
  Purpose: initialize display, load, sort, save values, and report timing.
  Parameters: none.
  Returns: process status 0.
  Variables used: elapsed - duration returned by dosort.
  --------------------------------------------------------------------------- */
main()
$(
    int elapsed; 
    graphics(0);
    cprints("}");
    cprints("***HEAPSORT 6502 ASM***\n");
    loadfile();
    elapsed = dosort();
    savefile();
    cprints("***RUN COMPLETE***\n");
    printf("HEAPSORT TOOK %d SECONDS\n", elapsed);
    gets();

    return 0;
$)

/* ---------------------------------------------------------------------------
  swap
  Purpose: exchange the integers addressed by a and b.
  Parameters: a, b - pointers to integers.
  Returns: no value; updates both pointed-to integers.
  Variables used: temp - swap storage.
  --------------------------------------------------------------------------- */
swap(a,b) 
int *a;
int *b;
$(
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
$)

/* ---------------------------------------------------------------------------
  fgets
  Purpose: read one file record into data, bounded by max bytes.
  Parameters: data - destination; max - capacity; fp - file handle.
  Returns: data, containing the record or an end-of-file marker.
  Variables used: r, c, i - input status, character, and buffer index.
  --------------------------------------------------------------------------- */
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 NUL-terminated decimal string.
  Parameters: value - integer to convert; str - destination buffer.
  Returns: pointer past the terminating NUL.
  Variables used: neg, idx - sign and output 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 NUL-terminated string and Atari record terminator.
  Parameters: data - string to write; fp - file handle.
  Returns: status from the final character write, or an earlier write error.
  Variables used: r - string-write status.
  --------------------------------------------------------------------------- */
fputs(data,fp)
char *data;
int fp;
$(
  int r;
  r=cputs(data,fp);
  if(r<0) return r;
  return cputc(155,fp);
$)