-- RandomizeWords.mesa 
--   Edited by Sweet, 22-Jan-81 15:48:41

DIRECTORY
  Ascii,
  IODefs,
  OutputDefs,
  Random,
  Segments,
  Storage,
  StreamDefs,
  Streams,
  String;

RandomizeWords: PROGRAM
  IMPORTS IODefs, OutputDefs, Random, Segments, Storage, StreamDefs, Streams, String =
  BEGIN

  Sort: PUBLIC PROCEDURE [
      a: DESCRIPTOR FOR ARRAY OF UNSPECIFIED, 
      Greater: PROC[UNSPECIFIED, UNSPECIFIED] RETURNS [BOOLEAN]] =
    BEGIN
    n: CARDINAL = LENGTH[a];
    i: CARDINAL;
    temp: CARDINAL;
    SiftUp: PROC [l, u: CARDINAL] =
      BEGIN
      s: CARDINAL;
      key: CARDINAL _ a[l-1];
      DO
        s _ l*2;
        IF s > u THEN EXIT;
        IF s < u AND Greater[a[s+1-1], a[s-1]] THEN s _ s+1;
        IF Greater[key, a[s-1]] THEN EXIT;
        a[l-1] _ a[s-1];
        l _ s;
        ENDLOOP;
      a[l-1] _ key;
      END;
    FOR i DECREASING IN [2..n/2] DO SiftUp[i, n]; ENDLOOP;
    FOR i DECREASING IN [2..n] DO
      SiftUp[1, i];
      temp _ a[1-1];
      a[1-1] _ a[i-1];
      a[i-1] _ temp;
      ENDLOOP;
    END;

  Randomize: PROC [rand: DESCRIPTOR FOR ARRAY OF UNSPECIFIED] =
    BEGIN
    r: DESCRIPTOR FOR ARRAY OF CARDINAL;
    rGreater: PROC [x, y: CARDINAL] RETURNS [BOOLEAN] =
      {RETURN [r[x] > r[y]]};
    i: CARDINAL;
    r _ DESCRIPTOR[Storage.Node[LENGTH[rand]], LENGTH[rand]];
    FOR i IN [0..LENGTH[rand]) DO
      r[i] _ Random.InRange[0, 1000];
      ENDLOOP;
    Sort[rand, rGreater];
    Storage.Free[BASE[r]];
    END;
      
  ReadDataFile: PROC [file: STRING, Add: PROC [STRING]] =
    BEGIN
    in: Streams.Handle _ NIL;
    streamEnd: BOOLEAN _ FALSE;
    name: STRING = [40];
    number: STRING = [20];
    ch: CHARACTER;

    GetToken: PROC [token: STRING] =
      BEGIN ENABLE Streams.End[] => {streamEnd _ TRUE; GO TO done};
      token.length _ 0;
      IF streamEnd THEN RETURN;
      WHILE ch = Ascii.SP OR ch = Ascii.CR DO
        ch _ Streams.GetChar[in];
	ENDLOOP;
      WHILE (ch IN ['A..'Z]) OR (ch IN ['a..'z]) OR (ch IN ['0..'9]) DO
	String.AppendChar[token, ch];
        ch _ Streams.GetChar[in];
	ENDLOOP;
      IF token.length = 0 AND ~streamEnd THEN ERROR;
      EXITS
        done => RETURN;
      END;
    BEGIN
    ENABLE {
      String.StringBoundsFault => GO TO tooLong;
      String.InvalidNumber => GO TO badNumber};

    in _ Streams.NewStream [file, Streams.Read !
      Segments.FileNameProblem[] => GO TO notFound];
    ch _ Streams.GetChar[in ! Streams.End[] => GO TO badFormat];
    WHILE ~streamEnd DO 
      GetToken[name]; 
      Add[name];
      ENDLOOP;
    EXITS
      notFound => {
	IODefs.WriteString[file];
	IODefs.WriteLine[" not found."L]};
      tooLong => {
	IODefs.WriteString["token too long at "L];
	WriteLongNumber[Streams.GetIndex[in]]};
      badNumber => {
	IODefs.WriteString["invalid number at "L];
	WriteLongNumber[Streams.GetIndex[in]]};
      badFormat => {
	IODefs.WriteString["invalid format at "L];
	WriteLongNumber[Streams.GetIndex[in]]};
    END;
    IF in # NIL THEN Streams.Destroy[in];
    END;

  input: DESCRIPTOR FOR ARRAY OF STRING;

  WriteLongNumber: PROC [ln: LONG CARDINAL] =
    BEGIN
    ls: STRING = [20];
    String.AppendLongNumber[ls, ln, 10];
    IODefs.WriteString[ls];
    END;

  
  Driver: PROC =
    BEGIN OPEN IODefs, StreamDefs, OutputDefs;
    nS: CARDINAL _ 0;
    Count: PROC [s: STRING] = {nS _ nS + 1};
    Insert: PROC [s: STRING] = 
      {input[nS] _ Storage.CopyString[s]; nS _ nS + 1};
    inputFile: STRING _ [40];
    WriteString["Input data: "L];
    ReadID[inputFile]; WriteChar[CR];
    ReadDataFile[inputFile, Count];
    input _ DESCRIPTOR[Storage.Node[nS], nS]; nS _ 0;
    ReadDataFile[inputFile, Insert];
    Randomize[input];
    OpenOutput[inputFile, ".rand"];
    FOR i: CARDINAL IN [0..nS) DO
      PutString[input[i]];
      PutCR[];
      ENDLOOP;
    CloseOutput[];
    Storage.FreeWords[BASE[input]];
    END;
    
  Driver[];
  END.