/*  AWM_TO_REGIONS.P  */


section awm_to_regions => awm_to_regions;


/*
SPECIFICATION
-------------

This module exports a routine for marking regions within an AWM. The
idea is best shown by an example:

    awm =>
    ** AWM:
         xk: -5 to 5;  yk: -5 to 5
         xbounds: -10 to 10;   ybounds: -10 to 10
         position: (0,0)
         forward: [0 1];   right: [1 0]
    ???     ???
    ???*****???
    ???     ???
      *   k  *
      *      *
      *  B   #
      *    * *
      *      *
    ???*****???
    ???     ???
    ???@    ???

    awm_to_regions( awm, `a`, procedure(c);1+c;endprocedure, true )
        -> regions;

    awm=>
    ** AWM:
         xk: -5 to 5;  yk: -5 to 5
         xbounds: -10 to 10;   ybounds: -10 to 10
         position: (0,0)
         forward: [0 1];   right: [1 0]
    ???eeeee???
    ???*****???
    ???ccccc???
    bb*ccckcc*d
    bb*cccccc*d
    bb*ccBccc#d
    bb*cccc*c*d
    bb*cccccc*d
    ???*****???
    ???aaaaa???
    ???@aaaa???

    regions==>
    ** [[101 [-2 5] [-1 5] [0 5] [1 5] [2 5]]
        [100 [5 -2] [5 -1] [5 0] [5 1] [5 2]]
        [99 [-2 -2]
            [-2 -1]
            <etc>
            [3 2]
            [2 3]]
        [98 [-5 -2]
            [-5 -1]
            <etc>
            [-4 -2]
            [-4 2]]
        [97 [-1 -5] [-2 -4] [-1 -4] [0 -5] [0 -4]
            [1 -5] [1 -4] [2 -5] [2 -4]]]

Essentially, within an AWM, awm_to_regions finds all the regions
(connected regions of blank squares, bounded by non-spaces or
undefineds), and replaces all the blanks in each with a unique
character. It also returns a list of these characters and the points
making up each region. The marked AWM can be used in various types of
analogical processing. For example, to find out what region an object is
in, you only need to look at the region markers neighbouring it.


PUBLIC awm_to_regions( awm, first_reg, next_reg, keep ):

This routine marks awm in the way described above. first_reg must be a
character, to be used as the marker for the first region found.
next_reg must be a function which when applied to a region marker,
yields the next one. In the example above, this is done just by
adding one to it.

If keep is true, awm_to_regions returns a list of sublists. Each sublist
is of the form
    [ <region> <point1> <point2> ... ]
where <region> is that region's character, and <point1> etc are the
points within the region, as vecs (or lists: see HELP VEC).        

If keep is true, awm_to_regions just returns an integer, giving the
number of regions found.


Resetting an AWM
----------------

You can use the routine awm_replace from AWM.P to get rid of the region
markers. In the example above, the call

    awm_replace( awm, procedure(c);lvars c; c>=`a`;endprocedure, ` ` );

will replace any character whose ASCII code is that for `a` or greater,
with a space.
*/


/*
IMPLEMENTATION
--------------

I use a brute-force method. awm_to_regions runs through its awm argument,
examining every character in turn. If this character is blank, it calls
flood to replace it and all the blanks connected to it by a region
marker. It then restarts the scan.

It should be possible to make this more efficient by not examining
characters which have been flooded out. I haven't thought about how to
do this.

This module has a HELP file, HELP AWM_TO_REGIONS. Keep it in step with
the code.
*/


needs awm;


vars flood;/*forward*/


define awm_to_regions( awm, first_reg, next_reg, keep );
    lvars awm, first_reg, next_reg, keep;
    lvars i=awm.awm_x_known_min, j=awm.awm_y_known_min;
    lvars reg=first_reg, regno=0, regions = [];

    /*  Scans from one beyond the location of the last-scanned
        character, i.e. (i+1,j) for a c. If found, set (i,j) to
        its location and return true, else return false.
    */
    define scan_until(c);
        lvars c;
        lvars x=i+1, y=j;
        repeat
            if x > awm.awm_x_known_max and y > awm.awm_y_known_max then return(false) endif;
            if x > awm.awm_x_known_max then awm.awm_x_known_min->x; 1+y->y; nextloop; endif;
            if awm(x,y) = c then x->i; y->j; return(true) else 1+x->x; endif;
        endrepeat;
    enddefine;

    while scan_until(` `) do
        1 + regno -> regno;
        if keep then
            [ [ ^reg ^^([%flood(awm,reg,i,j,keep)%]) ] ^^regions ] -> regions;
        else
            flood(awm,reg,i,j,keep)
        endif;
        next_reg(reg) -> reg;
    endwhile;

    if keep then regions else regno endif;          
enddefine;


/*  flood( awm, c, i, j, keep ):
        Starting at awm(i,j), which should be blank, fill it and all
        squares connected thereto with a c. We use depth-first search to
        do this, implemented by recursive calls to flood within
        awm_app_neighbours. If the recursion depth grows too big, we
        could use depth-first search from SEARCH.P instead.
*/
define flood( awm, c, i, j, keep );
    lvars awm, c, i, j, keep;

    if awm(i,j) = ` ` then
        c -> awm(i,j);
        if keep then [% i, j %] endif;
        awm_app_neighbours( awm, i, j,
                            procedure(awm,x,y);
                                lvars awm, x, y;
                                if awm(x,y) = ` ` then flood(awm,c,x,y,keep) endif
                            endprocedure
                          )
    endif;
enddefine;


endsection;