% "maze.t"
%
% University of Toronto
% CSC148s, 1996
% Solution to Assignment 2
%
% This file contains code for reading a file supposedly describing a
% well-formed rectangular maze and checks whether it satisfies some
% specifications. Refer to the handout and to the included file "supt.t"
% for details.


% Include routines for manipulating mazes.
include "supt.t"



% Constants specified by handout.

const wellFormedMsg : string := "The input is a well-formed rectangular maze."
const illFormedMsg : string := "The input is not a well-formed rectangular maze."

const solidElement := "1" % Input character that represents a solid
const spaceElement := "0" % Input character that represents a space



% This type defines the possible format errors.

type formatErrorType : enum (Line1, Line2, LineXchar, LineXshort,
    TooFewLines, TooManyLines)



% putError(e, lineNumber)
%     - This procedure outputs an appropriate error message (see
% assignment handout) based on the error 'e' and the line number
% it occurred on.

procedure putError (e : formatErrorType, lineNumber : int)

    case e of
        label formatErrorType.Line1 :

            assert lineNumber = 1
            put "Line 1 does not consist of two positive integers."

        label formatErrorType.Line2 :

            assert lineNumber = 2
            put "Line 2 does not consist of two positive integers."

        label formatErrorType.LineXchar :

            assert lineNumber > 2
            put "Line ", lineNumber, 
                " contains a character that is not a bit."

        label formatErrorType.LineXshort :

            assert lineNumber > 2
            put "Line ", lineNumber, 
                " does not consist of the correct number of characters."

        label formatErrorType.TooFewLines :

            put "Too few lines."

        label formatErrorType.TooManyLines :

            put "Too many lines."

        label : % Should never happen

            assert false

    end case

end putError



% isDigit(ch) : boolean
%     - This function returns true iff 'ch' is a base ten digit.

function isDigit (ch : string (1)) : boolean

    const digits : string := "0123456789"

    result index (digits, ch) not= 0

end isDigit



% isSpace(ch) : boolean
%     - This function returns true iff 'ch' is a space.

function isSpace (ch : string (1)) : boolean

    result ch = " "

end isSpace



% isStringOfBits(s) : boolean
%     - This function returns true iff 's' is only made up
% of the characters 'solidElement' and 'spaceElement' defined
% above.

function isStringOfBits (s : string) : boolean

    for i : 1 .. length (s)
        if not (s (i) = solidElement or s (i) = spaceElement) then
            result false
        end if
    end for

    result true

end isStringOfBits



% setRowOfMaze(M, row, bitString)
%     - This procedure sets row 'row' of the rectangle according to
% a bitString (see handout).

procedure setRowOfMaze (var M : array 1 .. *, 1 .. * of boolean,
        row : int, bitString : string)

    const stringLength := length (bitString)

    assert stringLength = upper (M, 1)
        and 1 <= row and row <= upper (M, 2)

    for i : 1 .. stringLength
        if bitString (i) = solidElement then
            M (i, row) := solid
        elsif bitString (i) = spaceElement then
            M (i, row) := space
        else
            assert false % Can't happen
        end if
    end for

end setRowOfMaze



% getTwoIntegers(line, N1, N2, error)
%     - This procedure parses a 'line' and extracts the two
% integers which should occurr on that line. If the line doesn't
% contain two integers or contains extra information, the parameter
% 'error' is set to true. Otherwise, the parameters N1 and N2 are
% set to be the two integers encountered (N1 being the leftmost).

procedure getTwoIntegers (line : string, var N1, N2 : int, var error : 
    boolean)

    % Assume that there isn't an error for now.

    error := false

    % Find 'start' and 'finish' of the first integer.

    var start, finish : int := 1
    const lineLength := length (line)

    % Check length of line.
    if lineLength < 1 then
	error := true
	return
    end if

    % Find start of first integer. Allow any number of spaces to precede.
    loop
        exit when isDigit (line (start)) or not isSpace (line (start))
            or start = lineLength

        start += 1
    end loop

    % Check for error.

    if not isDigit (line (start)) then
        error := true
        return
    end if

    % Find 'finish' of first integer.

    finish := start
    loop
        exit when finish = lineLength or not isDigit (line (finish + 1))
        finish += 1
    end loop

    % Check for error

    if not isDigit (line (finish)) or finish = lineLength then
        error := true
        return
    end if

    % Find value of first integer.

    N1 := strint (line (start .. finish))

    % Find start of second integer.

    start := finish + 1
    loop
        exit when isDigit (line (start)) or not isSpace (line (start))
            or start = lineLength

        start += 1
    end loop

    % Check for error.

    if not isDigit (line (start)) then
        error := true
        return
    end if

    % Find 'finish' of second integer.

    finish := start
    loop
        exit when finish = lineLength or not isDigit (line (finish + 1))
        finish += 1
    end loop

    if not isDigit (line (finish)) then
        error := true
        return
    end if

    % Check that there are only spaces after the finish.

    for i : finish + 1 .. lineLength
        if not isSpace (line (i)) then
            error := true
            return
        end if
    end for

    % Find value of second integer.

    N2 := strint (line (start .. finish))

end getTwoIntegers



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Main program
%     - See handout for details.

var isFormatError : boolean

var line : string
var lineNumber : int := 1

var height, width : int
var entranceX, entranceY : int
var error : boolean

% First line should be two integers denoting the height and width.

if not eof then
    get line : *
    getTwoIntegers (line, height, width, error)
    if error or height < 1 or width < 1 then
        putError (formatErrorType.Line1, lineNumber)
        return
    end if
else
    putError (formatErrorType.TooFewLines, lineNumber)
    return
end if

% Declare the array containing the maze and initialize it.

var M : array 1 .. width, 1 .. height of boolean

initializeMaze (M)

% Second line should be two integers denoting the horizontal and
% vertical and position of the entrance.

lineNumber += 1

if not eof then
    get line : *
    getTwoIntegers (line, entranceX, entranceY, error)
    if error or entranceX < 1 or entranceY < 1 then
        putError (formatErrorType.Line2, lineNumber)
        return
    end if
else
    putError (formatErrorType.TooFewLines, lineNumber)
    return
end if

% There should be 'height' remaining lines all of which are
% strings of length 'width' and which only contain 'bit' values.

% Each input line is first checked to see if it only contains 'bit'
% values and only then is it checked for correct length.

for decreasing y : height .. 1

    lineNumber += 1

    if eof then
        putError (formatErrorType.TooFewLines, lineNumber)
        return
    end if

    get line : *

    if not isStringOfBits (line) then
        putError (formatErrorType.LineXchar, lineNumber)
        return
    end if

    if length (line) not= width then
        putError (formatErrorType.LineXshort, lineNumber)
        return
    end if

    % Store the information in the maze.

    setRowOfMaze (M, y, line)

end for

% Check for extra input.

if not eof then
    putError (formatErrorType.TooManyLines, lineNumber)
    return
end if

% If we get here, there were no format errors.

if isValidMaze (M, entranceX, entranceY) then
    put wellFormedMsg
else
    put illFormedMsg
end if