CleanSgfFromKgs: Sgf.pmod

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
 * This is gnugoclient, a program to connect go engines to go        *
 * servers. See http://www.lysator.liu.se/~gunnar/gnugoclient        *
 * for information.                                                  *
 *                                                                   *
 * Copyright 1997-2004 by Gunnar Farnebäck.                          *
 * E-mail: gunnar@lysator.liu.se                                     *
 *                                                                   *
 * This program is free software; you can redistribute it and/or     *
 * modify it under the terms of the GNU General Public License as    *
 * published by the Free Software Foundation - version 2             *
 *                                                                   *
 * This program is distributed in the hope that it will be useful,   *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of    *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the     *
 * GNU General Public License in file COPYING for more details.      *
 *                                                                   *
 * You should have received a copy of the GNU General Public         *
 * License along with this program; if not, write to the Free        *
 * Software Foundation, Inc., 59 Temple Place - Suite 330,           *
 * Boston, MA 02111, USA.                                            *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

constant sgf_letters =
([
     1:"a",   2:"b",   3:"c",   4:"d",   5:"e",   6:"f",   7:"g",
     8:"h",   9:"i",  10:"j",  11:"k",  12:"l",  13:"m",  14:"n",
    15:"o",  16:"p",  17:"q",  18:"r",  19:"s",  20:"t",  21:"u",
    22:"v",  23:"w",  24:"x",  25:"y",  26:"z",
    27:"A",  28:"B",  29:"C",  30:"D",  31:"E",  32:"F",  33:"G",
    34:"H",  35:"I",  36:"J",  37:"K",  38:"L",  39:"M",  40:"N",
    41:"O",  42:"P",  43:"Q",  44:"R",  45:"S",  46:"T",  47:"U",
    48:"V",  49:"W",  50:"X",  51:"Y",  52:"Z"
]);

string decode_move(string sgfmove, int size)
{
    if (sgfmove == "" || (sgfmove == "tt" && size <= 19))
        return "PASS";
    
    int row = 1 + size - search(sgf_letters, sgfmove[1..1]);
    int col = search(sgf_letters, sgfmove[0..0]);
    
    return sprintf("%c%d", 'A' + (col - 1) + (col > 8), row);
}

int sgf_linewidth = 70;

void set_linewidth(int n)
{
    sgf_linewidth = n;
}

// Building block for the sgf tree structure
class SgfNode
{
    constant SGF_INDENTSTEP = 2;

    mapping(string:string|array(string)) properties = ([]);
    object parent;                 // Pointer to parent node.
    array(SgfNode) children = ({}); // Pointers to child nodes.
    
    constant root_properties_order =
    ({
        "GM", "FF",
        "SZ", "HA", "KM",
        "PW", "WR",
        "PB", "BR",
        "PC", "CP",
        "DT", "AP",
        "EV", "GN",
        "RE",
        "TM", "OT", "OP", "OM", "RU"
    });

    constant node_properties_order = ({"B", "W", "BL", "OB", "WL", "OW",
                                       "AB", "AW", "TB", "TW", "C"});

    constant needs_quoting = (<"EV", "GN", "C">);
    
    constant property_requires_newline = (<"FF", "CP", "KM", "WR", "BR",
                                           "GN", "OT", "OM", "AP", "RE",
                                           "RU", "AB", "AW">);

    // Methods to add properties.

    static string encode_move(int size, int col, int row)
    {
        return sgf_letters[(int)col] + sgf_letters[1 + size - (int)row];
    }

    // Notice that in the case of composed text, ":" must also be
    // quoted. That is assumed to have been done previously.
    string quote_text(string s)
    {
        return replace(s, ({"]", "\\"}), ({"\\]", "\\\\"}));
    }

    void add_property(string identity, string|array(string) value)
    {
        if (needs_quoting[identity])
            value = quote_text(value);
        switch (identity)
        {
        case "C":
        case "AB":
        case "AW":
        case "TB":
        case "TW":
            if (properties[identity])
                if (stringp(value))
                    properties[identity] += ({value});
                else
                    properties[identity] += value;
            else
                if (stringp(value))
                    properties[identity] = ({value});
                else
                    properties[identity] = value;
            break;
        default:
            properties[identity] = value;
        }
    }

    void remove_property(string identity)
    {
        m_delete(properties, identity);
    }

    static void add_stone_or_move(string prefix, string color, string move,
                               int size)
    {
        color = lower_case(color);
        if (color == "b" || color == "B")
            color = "B";
        else
            color = "W";

        move = lower_case(move);
        if (move == "pass")
            add_property(prefix + color, "");
        else
        {
            int col = 1 + move[0] - 'a' - (move[0] > 'i');
            int row = (int) move[1..];
            add_property(prefix + color, encode_move(size, col, row));
        }
    }

    void add_move(string color, string move, int size)
    {
        add_stone_or_move("", color, move, size);
    }

    void add_stone(string color, string move, int size)
    {
        add_stone_or_move("A", color, move, size);
    }

    // Methods to retrieve information.

    SgfNode get_parent()
    {
        return parent;
    }

    SgfNode get_child(int n)
    {
        if (n >= sizeof(children))
            return 0;
        else
            return children[n];
    }

    array(SgfNode) get_children()
    {
        return children;
    }

    string|array(string) get_property(string s)
    {
        return properties[s];
    }

    int get_size()
    {
        if (parent)
            return parent->get_size();
        
        return ((int) properties->SZ) || 19;
    }

    array(string) get_move(int|void size)
    {
        string color = "";
        string move = "";

        if (!size)
            size = get_size();

        if (properties->B)
        {
            color = "B";
            move = decode_move(properties->B, size);
        }
        else if (properties->W)
        {
            color = "W";
            move = decode_move(properties->W, size);
        }

        return ({color, move});
    }
    
    array(string) get_handicap_stones()
    {
        int size = get_size();
        array(string) stones = ({});

        if (properties->AB)
            foreach (properties->AB, string stone)
                stones += ({decode_move(stone, size)});
        
        return stones;
    }


    // Methods to write to string.
  
    static string indentation(int indentation_level)
    {
        return " " * (indentation_level * SGF_INDENTSTEP);
    }
    
    static array(string) add_text(array(string) sgf, string s,
                                  int indentation_level)
    {
        if (sizeof(sgf[-1]) + sizeof((s / "\n")[0]) >= sgf_linewidth)
            sgf = force_newline(sgf, indentation_level);
        sgf[-1] += s;
        return sgf;
    }

    array(string) force_newline(array(string) sgf, int indentation_level)
    {
        if (sizeof(sgf[-1]) != 0 && sgf[-1][-1] != ' ')
            sgf += ({indentation(indentation_level)});
        return sgf;
    }

    array(string) write_property(array(string) sgf, string name,
                                 int indentation_level, string|void prefix)
    {
        string s = "";
        if (prefix)
            s = prefix;
        if (stringp(properties[name]))
            s += name + "[" + properties[name] + "]";
        else if (name == "C")
            s += name + "[" + properties[name] * "\n" + "]";
        else // AB, AW, TB, TW
        {
            if (sizeof(properties[name]) > 0)
            {
                s += name;
                foreach (properties[name], string propvalue)
                {
                    s += "[" + propvalue + "]";
                    sgf = add_text(sgf, s, indentation_level);
                    s = "";
                }
            }
        }
        if (sizeof(s) > 0)
            sgf = add_text(sgf, s, indentation_level);
        if (property_requires_newline[name])
            sgf = force_newline(sgf, indentation_level);
        return sgf;
    }
    
    array(string)|string write(array(string)|void sgf,
                               int|void indentation_level)
    {
        int root = 0;
        if (!sgf) // Root node
        {
            indentation_level = 0;
            root = 1;
            sgf = ({"(;"});
            foreach (root_properties_order + node_properties_order,
                     string name)
                if (properties[name])
                    sgf = write_property(sgf, name, indentation_level);

            // Is there some property we missed above?
            foreach (indices(properties), string name)
                if (!has_value(root_properties_order + node_properties_order,
                               name))
                    sgf = write_property(sgf, name, indentation_level);

            // Always newline at the end of the root node.
            sgf = force_newline(sgf, indentation_level);
        }
        else
        {
            string prefix = ";";
            foreach (node_properties_order, string name)
                if (properties[name])
                {
                    sgf = write_property(sgf, name, indentation_level, prefix);
                    prefix = "";
                }

            // Is there some property we missed above?
            foreach (indices(properties), string name)
                if (!has_value(node_properties_order, name))
                    sgf = write_property(sgf, name, indentation_level);
        }
        
        if (sizeof(children) == 1)
        {
            SgfNode child = children[0];
            sgf = child->write(sgf, indentation_level);
        }
        else if (sizeof(children) > 1)
        {
            foreach (children, SgfNode child)
            {
                sgf = force_newline(sgf, indentation_level);
                sgf = add_text(sgf, "(", indentation_level);
                sgf = child->write(sgf, indentation_level + 1);
                sgf = add_text(sgf, ")", indentation_level);
            }
        }
        if (root)
        {
            sgf = add_text(sgf, ")", indentation_level);
            return sgf * "\n";
        }
        else
            return sgf;
    }

    string read_property(string name, string sgfdata)
    {
        string value = "";
        int quoted = 0;
        while (sgfdata != "")
        {
            string c = sgfdata[0..0];
            sgfdata = sgfdata[1..];
            if (quoted)
            {
                if (value != "\n")
                    value += c;
                quoted = 0;
            }
            else if (c == "\\")
                quoted = 1;
            else if (c == "]")
            {
                add_property(name, value);
                return sgfdata;
            }
            else
                value += c;
        }
        werror("Unexpected end of sgf data.\n");
        return sgfdata;
    }

    string read(string sgfdata)
    {
        string property_name = "";
        int variation = 0;
        while (sgfdata != "")
        {
            string c = sgfdata[0..0];
            if (c >= "A" && c <= "Z")
                sscanf(sgfdata, "%[A-Z]%s", property_name, sgfdata);
            else if (c == "[")
                sgfdata = read_property(property_name, sgfdata[1..]);
            else if (c == "(")
            {
                variation = 1;
                sgfdata = sgfdata[1..];
            }
            else if (c == ")")
                return sgfdata[1..];
            else if (c == ";")
            {
                SgfNode child = SgfNode(this_object());
                if (!variation)
                    return child->read(sgfdata[1..]);
                else
                    sgfdata = child->read(sgfdata[1..]);
            }
            else if (c == " " || c == "\t" || c == "\v" || c == "\n")
                sgfdata = sgfdata[1..];
            else
            {
                werror("Warning: Skipping unexpected character %s.\n", c);
                sgfdata = sgfdata[1..];
            }
        }
        werror("Unexpected end of sgf data.\n");
        return sgfdata;
    }
    
    void add_child(SgfNode node)
    {
        children += ({node});
    }

    SgfNode new_node()
    {
        return SgfNode(this_object());
    }

    void create(SgfNode|void _parent)
    {
        parent = _parent;
        if (parent)
            parent->add_child(this_object());
    }
}


SgfNode parse_sgf(string sgfdata)
{
    SgfNode sgf = SgfNode();
    sgfdata = normalize_linebreaks(sgfdata);
    while (1) 
    {
        if (sscanf(sgfdata, "%*s(%s", sgfdata) == 0)
            return 0;
        if (sscanf(sgfdata, "%*[ \t\v\n];%s", sgfdata) == 2)
            break;
    }
    sgf->read(sgfdata);
    return sgf;
}


string normalize_linebreaks(string s)
{
    if (search(s, "\r\n") >= 0 || search(s, "\n\r") >= 0)
        return s - "\r";

    return replace(s, "\r", "\n");
}

void simplify_dates(array(string) dates)
{
    array(string) last_date = "--"/"-";
    for (int i=0; i<sizeof(dates); i++)
    {
        array(string) date = dates[i] / "-";
        if (date[0] != last_date[0])
            ;
        else if (date[1] != last_date[1])
            dates[i] = date[1..] * "-";
        else if (date[2] != last_date[2])
            dates[i] = date[2];
        last_date = date;
    }
}

class Territory
{
    class Run
    {
        int start_col;
        int start_row;
        string direction;
        int length;

        array(int) start()
        {
            return ({start_col, start_row});
        }

        array(int) end()
        {
            if (direction == "vertical")
                return ({start_col, start_row + length - 1});
            else
                return ({start_col + length - 1, start_row});
        }
        
        void enlarge()
        {
            length++;
        }
        
        void create(int col, int row, string dir)
        {
            start_col = col;
            start_row = row;
            direction = dir;
            length = 0;
        }
    }
    
    int size;
    // Use a zero padded board to get rid of boundary checking.
    array(int) board;
    array(int) vertical_runs;
    array(int) horizontal_runs;
    mapping(int:object) runs = ([]);
    int max_run_length = 0;
    int next_run = 1;

    int index(int col, int row)
    {
        return col + row * (size + 2);
    }
    
    void find_runs(string direction)
    {
        int col, row;
        for (int x=1; x<=size; x++)
        {
            int run = 0;
            for (int y=1; y<=size+1; y++)
            {
                if (direction == "vertical")
                {
                    col = x;
                    row = y;
                }
                else
                {
                    col = y;
                    row = x;
                }
                if (board[index(col, row)])
                {
                    if (!run)
                    {
                        run = next_run++;
                        runs[run] = Run(col, row, direction);
                    }
                    runs[run]->enlarge();
                    if (direction == "vertical")
                        vertical_runs[index(col, row)] = run;
                    else
                        horizontal_runs[index(col, row)] = run;
                }
                else
                    run = 0;
            }
        }
    }

    string other_direction(string direction)
    {
        if (direction == "vertical")
            return "horizontal";
        else
            return "vertical";
    }
        
    object get_run(int col, int row, string direction)
    {
        if (direction == "vertical")
            return runs[vertical_runs[index(col, row)]];
        else
            return runs[horizontal_runs[index(col, row)]];
    }

    object get_run_length(int col, int row, string direction)
    {
        return get_run(col, row, direction)->length;
    }

    string encode_rectangle(array(int) rectangle, function encode_move)
    {
        int col1, row1, col2, row2;
        [col1, row1, col2, row2] = rectangle;
        if (col1 == col2 && row1 == row2)
            return encode_move(size, col1, row1);
        else
            return (encode_move(size, col2, row1) + ":" 
                    + encode_move(size, col1, row2));
    }

    void rebuild_run(object old_run)
    {
        int col1, row1, col2, row2;
        [col1, row1] = old_run->start();
        [col2, row2] = old_run->end();
        if (old_run->direction == "vertical")
        {
            int run = 0;
            for (int row=row1; row<=row2+1; row++)
            {
                if (board[index(col1, row)])
                {
                    if (!run)
                    {
                        run = next_run++;
                        runs[run] = Run(col1, row, old_run->direction);
                    }
                    runs[run]->enlarge();
                    vertical_runs[index(col1, row)] = run;
                }
                else
                    run = 0;
            }
        }
        else
        {
            int run = 0;
            for (int col=col1; col<=col2+1; col++)
            {
                if (board[index(col, row1)])
                {
                    if (!run)
                    {
                        run = next_run++;
                        runs[run] = Run(col, row1, old_run->direction);
                    }
                    runs[run]->enlarge();
                    horizontal_runs[index(col, row1)] = run;
                }
                else
                    run = 0;
            }
        }
    }

    // This is a ridiculously inefficient implementation.
    array(string) noncompressed_encode(function encode_move)
    {
        array(string) s = ({});
        for (int col=1; col<=size; col++)
            for (int row=1; row<=size; row++)
                if (board[index(col, row)])
                    s += ({encode_move(size, col, row)});
        return s;
    }
    
    array(string) compressed_encode(function encode_move)
    {
        vertical_runs = allocate((size+2) * (size+2));
        horizontal_runs = allocate((size+2) * (size+2));
        find_runs("vertical");
        find_runs("horizontal");
//      debug();
        int max_run_length = 0;
        mapping(object:int) run_lengths = ([]);
        foreach (values(runs), object run)
        {
            run_lengths[run] = run->length;
            if (run->length > max_run_length)
                max_run_length = run->length;
        }
        array(string) territory_strings = ({});
        int col1, row1, col2, row2;
        while (max_run_length>0)
        {
            object run = search(run_lengths, max_run_length);
            if (!run)
            {
                max_run_length--;
                continue;
            }
            [col1, row1] = run->start();
            [col2, row2] = run->end();

            array(int) rectangle;
            if (run->direction == "vertical")
            {
                if (run->length > 2)
                {
                    if (get_run_length(col1, row1, "horizontal") == 1)
                        row1++;
                    if (get_run_length(col2, row2, "horizontal") == 1)
                        row2--;
                }
                while (get_run(col2+1, row1, "vertical")
                       && (get_run(col2+1, row1, "vertical")
                           == get_run(col2+1, row2, "vertical")))
                    col2++;
                while (get_run(col1-1, row1, "vertical")
                       && (get_run(col1-1, row1, "vertical")
                           == get_run(col1-1, row2, "vertical")))
                    col1--;
                if (col1 == col2)
                    rectangle = run->start() + run->end();
                else
                {
                    array(object) splinters = ({});
                    for (int col=col1; col<=col2; col++)
                        splinters != ({get_run(col, row1-1, "horizontal"),
                                       get_run(col, row2+1, "horizontal")});
                    int cost = 7;
                    foreach (splinters, object splinter)
                    {
                        if (!splinter)
                            continue;
                        if (splinter->length == 1)
                            cost += 4;
                        else
                            cost += 7;
                    }
                    // This is indeed completely heuristic.
                    if (cost > (col2 - col1 + 1) * 7)
                        rectangle = run->start() + run->end();
                    else
                        rectangle = ({col1, row1, col2, row2});
                }
            }
            else
            {
                if (run->length > 2)
                {
                    if (get_run_length(col1, row1, "vertical") == 1)
                        col1++;
                    if (get_run_length(col2, row2, "vertical") == 1)
                        col2--;
                }
                while (get_run(col1, row2+1, "horizontal")
                       && (get_run(col1, row2+1, "horizontal")
                           == get_run(col2, row2+1, "horizontal")))
                    row2++;
                while (get_run(col1, row1-1, "horizontal")
                       && (get_run(col1, row1-1, "horizontal")
                           == get_run(col2, row1-1, "horizontal")))
                    row1--;
                if (row1 == row2)
                    rectangle = run->start()+run->end();
                else
                {
                    array(object) splinters = ({});
                    for (int row=row1; row<=row2; row++)
                        splinters |= ({get_run(col1-1, row, "vertical"),
                                       get_run(col2+1, row, "vertical")});
                    int cost = 7;
                    foreach (splinters, object splinter)
                    {
                        if (!splinter)
                            continue;
                        if (splinter->length == 1)
                            cost += 4;
                        else
                            cost += 7;
                    }
                    // This is indeed completely heuristic.
                    if (cost > (col2 - col1 + 1) * 7)
                        rectangle = run->start() + run->end();
                    else
                        rectangle = ({col1, row1, col2, row2});
                }
            }
            territory_strings += ({encode_rectangle(rectangle, encode_move)});
            // Update the set of runs.
            [col1, row1, col2, row2] = rectangle;
            array(int) destroyed_runs = ({});
            for (int col=col1; col<=col2; col++)
                for (int row=row1; row<=row2; row++)
                {
                    int i = index(col, row);
                    destroyed_runs |= ({vertical_runs[i],
                                        horizontal_runs[i]});
                    board[i] = 0;
                    vertical_runs[i] = 0;
                    horizontal_runs[i] = 0;
                }
            foreach (destroyed_runs, int run)
            {
                rebuild_run(runs[run]);
                m_delete(runs, run);
            }
            run_lengths = ([]);
            foreach (values(runs), object run)
                run_lengths[run] = run->length;
//          debug();
        }
        // Remove outer pair of brackets.
        return territory_strings;
    }

#if 0    
    void debug()
    {
        string s1 = "";
        string s2 = "";
        string s3 = "";
        for (int row=1; row<=size; row++)
        {
            for (int col=1; col<=size; col++)
            {
                int i = index(col, row);
                s1 += sprintf(" %d", board[i]);
                s2 += sprintf(" %2d", vertical_runs[i]);
                s3 += sprintf(" %2d", horizontal_runs[i]);
            }
            s1 += "\n";
            s2 += "\n";
            s3 += "\n";
        }
        werror(s1 + "\n" + s2 + "\n" + s3 + "\n");
    }
#endif

    void create(int board_size, array(array(int)) territory)
    {
        size = board_size;
        board = allocate((size+2) * (size+2));
        foreach (territory, array(int) point)
        {
            int col = 1 + point[0];
            int row = 1 + point[1];
            board[index(col, row)] = 1;
        }
    }
}