! Sort V0.0
! sorts a directory containing files n:m
! where n and m are the shortest and longest wordlengths respectively
! Uses a simple bubblesort because we always have 95% sorted files

%external %predicate Exists(%string (255) File, %integer %name len)
  %constant %integer os length index = 2
  %record %format osfile array fm (%integer %array element (0:3))
  %record (osfile array fm) osfile array
  %record %format Time stamp fm (%integer low, high)
  %record (time stamp fm) time stamp
  %external %integer %fn %spec Get file information(%c
    %record (osfile array fm) %name osfile array, 
    %record (time stamp fm) %name time stamp,
    %string (255) file name)

  %integer success = Get file information(osfile array,
                                          time stamp,
                                          File)
  %false %if success # 1
  len = osfile array_element(os length index)
  %true
%end

%external %routine loadup(%string (255) file name,
                          %integer address, actual length, max length)
  %external %routine %spec  X Load File (%string (255) file name,
                                         %integer      buffer size,
                                         %integer      address)
  %if max length < actual length %then %start
    print string("File ".file name." of ".itos(actual length,0). %c
                 " bytes is too big for buffer of ". %c
                 itos(max length,0)." bytes".nl)
    %stop
  %finish
  X Load file(file name, max length, address)
%end

%external %routine writeout(%string (255) file name, %integer address, len)
%external %integer %fn %spec Save File (%integer straddr,strlen,
                                     %integer     buffer size,
                                                  address)
%integer cc
  cc = Save file(ADDR(file name)+1, LENGTH(file name), len, address)
  %if cc < 0 %then printstring ("Failed to write out file ".file name.nl) %c
    %and %stop
%end

%begin
%constant %integer max dict = 120 000
%byte %array dict(0:max dict)
%integer step factor, word length

%string (63) %fn str(%integer idx)
%string(63) s
  s = ""
  s = s.dict(idx) %for idx = idx, 1, idx+word length-1
  %result = s
%end

%routine sortdict(%integer low index, high index)
%constant %integer true=0, false=1
%byte slot found
%integer back moves, forward moves
%string (63) pivot
%integer cp, wp, i, j, testp, leftp, rightp, swaps, pass
%byte char
pass = 1
%cycle
  printstring("Pass ".itos(pass,0))
  swaps = 0
  %for wp = low index+step factor, step factor, high index-step factor %cycle
    ! wp is index of word
    %for cp = wp, 1, wp+word length-1 %cycle
      ! cp is index of char
      %if dict(cp)<dict(cp+step factor) %then %exit {in place}
      %if dict(cp)>dict(cp+step factor) %then %start
        swaps = swaps+1
        ! Find correct place for WORD(wp)
        back moves = -100
        forward moves = -100
        slot found=false
        pivot = str(wp+step factor)
        %for testp = wp, -step factor, low index %cycle
          %if pivot>str(testp) %start
            leftp=testp
            back moves=wp-testp
            slot found=true
            %exit
          %finish
        %repeat
        ! try forwards this time
        pivot = str(wp)
        %for testp = wp+step factor, step factor, high index %cycle
          %if pivot<str(testp) %start
            rightp=testp
            forward moves = testp-wp
            slot found = true
            %exit
          %finish
        %repeat
!????
        %if slot found=false %start
          printstring("*** !!! Don't know where to put word ".str(wp)."!".nl)
          %exit
        %finish
        %if back moves > forward moves %start
!**** 1st
          testp=leftp
          pivot = str(wp+step factor)
          printstring("moving ".pivot." back to between ". %c
            str(testp)." and ".str(testp+step factor).nl)
          ! shunt testp+step to wp forward (+step)
          %for i = wp, -step factor, testp+step factor %cycle
            ! move <step factor> bytes at i to i+<step>
            %for j = 0, 1, word length-1 %cycle
              dict(i+j+step factor)=dict(i+j)
            %repeat
          %repeat
          ! slot wp in at testp+step (from saved copy)            
          %for i = testp+step factor, 1, %c
                     testp + step factor + word length-1 %cycle
            dict(i) = CHARNO(pivot, i-(testp+step factor)+1)
          %repeat
          %exit
        %else
!****
!#### 2nd
          testp=rightp
          pivot = str(wp)
          printstring("moving ".pivot." forward to between ". %c
            str(testp-step factor)." and ".str(testp).nl)
          ! shunt wp+<step> to testp-<step> backwards (-step)
          %for i = wp+step factor, step factor, testp-step factor %cycle
            ! move <step factor> bytes at i to i+<step>
            %for j = 0, 1, word length-1 %cycle
              dict(i+j-step factor)=dict(i+j)
            %repeat
          %repeat
          ! slot wp in at testp-<step> (from saved copy)
          %for i = testp-step factor, 1, %c
                     testp - step factor + word length-1 %cycle
            dict(i) = CHARNO(pivot, i-(testp-step factor)+1)
          %repeat
          %exit
        %finish
!####
      %finish
      ! if we go around all the way, words are same.
    %repeat
  %repeat %until wp = high index
  printstring(" - ".itos(swaps,0)." swaps".nl)
  pass = pass+1
%repeat %until swaps=0
%end

%routine printdict(%integer low index, high index)
%integer cp, wp
  %for wp = low index, step factor, high index %cycle
    ! wp is index of word
    Write(wp,6);space
    %for cp = wp, 1, wp+word length %cycle
      ! cp is index of char {inc. NL}
      print symbol(dict(cp))
    %repeat
  %repeat %until wp = high index
%end


%const %string (*) dict dir = "adfs::0.$.words.university."
%string (255) file name
%integer i, dict length
%for word length = 1, 1, 32 %cycle
  file name = dict dir.itos(word length,0)
  %if exists(file name, dict length) %start
    printstring("********* ".file name." **********".nl)
    step factor = word length+1 { 1 is for NL }
    loadup(file name, ADDR(dict(step factor)), dict length, max dict)
    dict(i) = '#' %for i = 0, 1, word length-1
    dict(word length)=NL                         {Start sentinel}
    dict(i) = '~' %c
      %for i = dict length+step factor,1,dict length+step factor+word length-1
    dict(dict length+step factor+word length)=NL {End sentinel}
    sortdict(0, dict length+step factor)
    ! printdict(0, dict length+step factor)
    ! writeout(file name, ADDR(dict(step factor)), dict length)
  %finish
%repeat
%endofprogram