/* Super fast sort program.
   whereas slow methods like quicksort/mergesort use O(n * log n) methods,
   radixsort is a true O(n) method. Especially for large textfiles, it is a
   LOT faster than other sorters (a log order of magnitude ;-).
   Radixsort uses a 256 buckets at each level to put the strings in. arrays
   of buckets are only allocated when the number of strings left to sort is
   large.
   Radix.e reads from a file, and outputs to stdout.
*/

MODULE 'tools/file', 'tools/exceptions'

DEF rad1:PTR TO LONG,radsize:PTR TO LONG

OBJECT str
  next,data
ENDOBJECT

PROC main() HANDLE
  DEF m,l,n,list
  m,l:=readfile(arg)
  n:=countstrings(m,l)
  list:=stringsinfilenolist(m,l,n)
  doradix(NEW rad1[256],NEW radsize[256],list,n)
  restradix(rad1,radsize)
EXCEPT
  report_exception()
ENDPROC

PROC doradix(table:PTR TO LONG,size:PTR TO LONG,str:PTR TO LONG,num)
  DEF a,s,c
  FOR a:=1 TO num
    s:=str[]++
    c:=s[]
    table[c]:=NEW [table[c],s]:str
    size[c]:=size[c]+1
  ENDFOR
ENDPROC

PROC restradix(table:PTR TO LONG,size:PTR TO LONG,level=1)
  DEF a
  FOR a:=0 TO 255 DO recradix(table[]++,size[]++,level)
ENDPROC

PROC recradix(l:PTR TO str,num,level)
  DEF tab:PTR TO LONG,size:PTR TO LONG,s,c,temp:PTR TO str
  IF num
    IF num<20
      straight(l,num)
    ELSE
      NEW tab[256],size[256]
      WHILE l
        s:=l.data
        temp:=l
        l:=l.next
        c:=s[level]
        temp.next:=tab[c]
        tab[c]:=temp
        size[c]:=size[c]+1
      ENDWHILE
      restradix(tab,size,level+1)
      END tab[256],size[256]
    ENDIF
  ENDIF
ENDPROC

PROC straight(l:PTR TO str,num)			-> sort these with a silly method
  DEF a,tl:PTR TO str,best:PTR TO str,fbest
  fbest:=[NIL,[$7F7F7F7F,$7F7F7F7F,$7F7F7F7F,0]:LONG]:str
  FOR a:=1 TO num
    tl:=l
    best:=fbest
    WHILE tl
      IF tl.data THEN IF OstrCmp(best.data,tl.data)=-1 THEN best:=tl
      tl:=tl.next
    ENDWHILE
    IF best<>fbest
      PutStr(best.data)
      FputC(stdout,"\n")
      best.data:=NIL
    ENDIF
  ENDFOR
ENDPROC

PROC stringsinfilenolist(mem,len,max)	-> to eliminate 32k strings boundary
  DEF list:PTR TO LONG,l
  NEW list[max]
  MOVE.L list,A1
  MOVE.L max,D3
  MOVE.L mem,A0
  MOVE.L A0,D1
  ADD.L  len,D1
  MOVEQ  #0,D0
  MOVEQ  #10,D2
stringsl:
  CMP.L  D3,D0
  BPL.S  done
  ADDQ.L #1,D0
  MOVE.L A0,(A1)+
findstringl:
  CMP.B  (A0)+,D2
  BNE.S  findstringl
  CLR.B  -1(A0)
  CMPA.L D1,A0
  BMI.S  stringsl
done:
  MOVE.L D0,l
ENDPROC list,l