<commit_before>extern crate "boxdraw-rs" as boxdraw;

use boxdraw::{Undraw, Script};
use boxdraw::grid::Grid;

pub struct SimpleSearch;

impl Undraw for SimpleSearch {
    fn undraw(&self, picture: &str) -> Script {
        let mut grid = Grid::from_str(picture).unwrap();
        let w = grid.width();
        let h = grid.height();

        let mut s = Script::new(w, h);

        for x in range(0, w) {
            for y in range(0, h) {
                // Found a left-corner; find the extent of the box.
                println!("inspecting ({},{})", x, y);
                println!("char at: ({},{}): '{}'", x, y, grid.get(x, y));
                if grid.get(x, y) == '+' {
                    let mut box_w = 1;
                    for i in range(x+1, w) {
                        let c = grid.get(i, y);
                        println!("scanning across, c: '{}'", c);
                        if c == '-' {
                            continue;
                        }
                        if c == '+' {
                            box_w = i - x + 1;
                            break;
                        }
                    }

                    let mut box_h = 1;
                    for j in range(y+1, h) {
                        assert!(j < h);
                        let left = grid.get(x, j);
                        assert!(j < h);
                        let right = grid.get(x + box_w - 1, j);
                        println!("scanning down, left: '{}' right: '{}'",
                                 left, right);
                        if left == '|' && right == '|' {
                            continue
                        }
                        if left == '+' && right == '+' {
                            box_h = j - y + 1;
                            break;
                        }
                    }

                    assert!(y+1 < h);
                    let fill = grid.get(x+1, y+1);
                    let cmd = boxdraw::rect(x, y, box_w, box_h, fill);
                    s.add_end_command(cmd);

                    // Now, clear the matched area.
                    println!("clearing matched area ({},{}) of w:{} h:{}",
                             x, y, box_w, box_h);
                    for i in range(x, x+box_w) {
                        for j in range(y, y+box_h) {
                            grid.set(i, j, '?');
                        }
                    }
                }
            }
        }

        s
    }
}

#[test]
fn check_simple() {
    boxdraw::check_undraw("...\n", &SimpleSearch).unwrap();

    boxdraw::check_undraw(".....\n\
                           .+-+.\n\
                           .|b|.\n\
                           .+-+.\n\
                          ",
                          &SimpleSearch).unwrap();

    boxdraw::check_undraw(".............\n\
                           .......+--+..\n\
                           .+-+...|cc|..\n\
                           .|b|...|cc|..\n\
                           .+-+...+--+..\n\
                           .............\n\
                          ",
                          &SimpleSearch).unwrap();

    boxdraw::check_undraw(".........\n\
                           .........\n\
                           .+-+.....\n\
                           .|b|.....\n\
                           .+-+.....\n\
                           .+--+....\n\
                           .|cc|....\n\
                           .|cc|....\n\
                           .+--+....\n\
                           .........\n\
                          ",
                          &SimpleSearch).unwrap();
}

#[test]
#[should_fail]
fn too_naive_to_pass_this_yet() {
    boxdraw::check_undraw(".............\n\
                           ....+---+....\n\
                           ....|bbb|....\n\
                           ....|bb+--+..\n\
                           ....|bb|cc|..\n\
                           ....+--|cc|..\n\
                           .......+--+..\n\
                           .............\n\
                          ",
                          &SimpleSearch).unwrap();

}<commit_msg>an improved naive undraw impl.<commit_after>#![feature(phase)]

extern crate "boxdraw-rs" as boxdraw;

#[phase(plugin)]
extern crate log;
extern crate log;

use boxdraw::{Undraw, Script};
use boxdraw::grid::Grid;

use std::char::from_u32;

pub struct SimpleSearch;

impl Undraw for SimpleSearch {
    fn undraw(&self, picture: &str) -> Script {
        debug!("undraw:\n{}", picture);

        let unused_char = self.find_unused_char(picture);

        let mut grid = Grid::from_str(picture).unwrap();
        let w = grid.width();
        let h = grid.height();

        let mut s = Script::new(w, h);

        // We find the commands in reverse order.
        let mut rev_commands = vec![];
        let mut cleared_some;
        loop {
            cleared_some = false;
            for y in range(0, h) {
                for x in range(0, w) {

                    match self.try_upper_left(&grid, unused_char, x, y) {
                        Some(cmd) => {
                            rev_commands.push(cmd);

                            // Now, clear the matched area.
                            debug!("clearing matched area ({},{}) of w:{} h:{}",
                                   x, y, cmd.w, cmd.h);
                            for i in range(x, x+cmd.w) {
                                for j in range(y, y+cmd.h) {
                                    grid.set(i, j, unused_char);
                                    cleared_some = true;
                                }
                            }
                        }

                        None => {
                            continue;
                        }
                    }

                }
            }
            if !cleared_some {
                break;
            }
        }
        let commands = {
            rev_commands.as_mut_slice().reverse();
            rev_commands
        };

        for cmd in commands.into_iter() {
            s.add_end_command(cmd);
        }

        s
    }
}

#[deriving(Show)]
enum MatchBox {
    ExactMatch(boxdraw::Command),
    PartialMatch,

    NonMatch(WhyNonMatch),
}

#[deriving(PartialEq, Show)]
struct WhyNonMatch {
    reason: String,
}

fn non_match(why: String) -> MatchBox {
    NonMatch(WhyNonMatch { reason: why })
}

impl PartialEq for MatchBox {
    fn eq(&self, that: &MatchBox) -> bool {
        match (self, that) {
            (&ExactMatch(c1), &ExactMatch(c2)) => {
                c1.x == c2.x &&
                    c1.y == c2.y &&
                    c1.w == c2.w &&
                    c1.h == c2.h &&
                    c1.fill == c2.fill
            }
            (&PartialMatch, &PartialMatch) => true,
            (&NonMatch(_), &NonMatch(_)) => true,
            _ => false
        }
    }
}

impl SimpleSearch {
    fn find_unused_char(&self, picture: &str) -> char {
        static AVOID : [char, ..5] = ['.', '+', '-', '|', '\n'];
        let mut guess = '?' as u32;
        loop {
            match from_u32(guess) {
                Some(char_guess) if !AVOID.contains(&char_guess) && !picture.contains_char(char_guess) => {
                    return char_guess;
                }
                _ => {
                    guess += 1;
                }
            }
        }
    }

    /// Attempts to match a box at `(x,y)`, using `hidden` as a marker
    /// for spaces that were overwritten by a later command.
    fn try_upper_left(&self, grid: &Grid, hidden: char, x: u32, y: u32) -> Option<boxdraw::Command> {

        let w = grid.width();
        let h = grid.height();

        // Found a left-corner; find the extent of the box.
        // println!("inspecting ({},{})", x, y);
        // println!("char at: ({},{}): '{}'", x, y, grid.get(x, y));

        let mut saw_partial = false;
        assert!(x < w); assert!(y < h);
        let c = grid.get(x,y);
        if c == '+' {
            'next_width:
            for i in range(x+1, w) {
                for j in range(y+1, h) {
                    let match_at = TryMatchAt {
                        grid: grid,
                        hidden: hidden,
                        x: x,
                        y: y,
                    };
                    match match_at.try(i, j) {
                        ExactMatch(cmd) => return Some(cmd),
                        PartialMatch => {
                            saw_partial = true;
                            continue;
                        }
                        NonMatch(ref why) => {
                            if saw_partial {
                                debug!("nonmatch for {}-{} because {}", (x,y), (i,j), why.reason);
                            }
                            continue 'next_width;
                        }
                    }
                }
            }
            None
        } else {
            None
        }
    }
}

struct TryMatchAt<'a> {
    grid: &'a Grid,
    hidden: char,
    x: u32,
    y: u32,
}

impl<'a> TryMatchAt<'a> {

    /// Attempts to match a box at `(self.x, self.y)` extending to `(right, below)`
    /// using `self.hidden` as a marker for spaces
    /// that were overwritten by a later command.
    fn try(&self, right: u32, below: u32) -> MatchBox {
        let x = self.x;
        let y = self.y;
        let grid = self.grid;
        let w = grid.width();
        let h = grid.height();

        let box_w = right - x + 1;
        let box_h = below - y + 1;

        let trial = (x, y, box_w, box_h);

        debug!("try: x {} y {} box_w {} box_h {} right {} below {} w {} h {}",
               x, y, box_w, box_h, right, below, w, h);

        assert!(x < w); assert!(y < h);
        let upper_left = grid.get(x, y);
        assert!(x < w); assert!(below < h);
        let lower_left = grid.get(x, below);
        assert!(right < w); assert!(y < h);
        let upper_right = grid.get(right, y);
        assert!(right < w); assert!(below < h);
        let lower_right = grid.get(right, below);


        let mut extends_right = false;
        let mut extends_down = false;

        // Tracks the character to use for the box interior, which we
        // do not necessarily know until scanning deep into the box.
        let mut interior = None;

        if !self.matches_corner(upper_left) {
            return non_match(format!("failed to match upper_left corner: {}", upper_left));
        }
        if !self.matches_corner(lower_left) {
            if lower_left == '|' {
                extends_down = true;
            } else {
                return non_match(format!("failed to match lower_left corner: {}", lower_left));
            }
        }

        if !self.matches_corner(upper_right) {
            if upper_right == '-' {
                extends_right = true;
            } else {
                return non_match(format!("failed to match upper_right corner: {}", upper_right));
            }
        }

        if !self.matches_corner(lower_right) {
            if extends_down && lower_right == '|' {
                // okay
            } else if extends_right && lower_right == '-' {
                // okay
            } else if extends_down && extends_right {
                if lower_right != self.hidden {
                    interior = Some(lower_right);
                }
            } else {
                return non_match(format!("failed to match lower_right corner: {}", lower_right));
            }
        }

        // Check that walls of box are in place.
        for i in range(x + 1, right) { // across
            assert!(i < w); assert!(y < h);
            let c = grid.get(i, y);
            if !self.matches_horizontal_wall(c) {
                return non_match(format!("failed to match top horizontal wall at {}: {}", (i, y), c));
            }
            assert!(i < w); assert!(below < h);
            let c = grid.get(i, below);
            if !extends_down {
                if !self.matches_horizontal_wall(c) {
                    return non_match(format!("failed to match bot horizontal wall at {}: {}", (i, below), c));
                }
            } else if c == self.hidden {
                // keep going
            } else {
                if interior.is_none() {
                    interior = Some(c);
                }
                if interior.is_some() && Some(c) != interior {
                    return non_match(format!("failed to match bot interior {} at {}: {}", interior, (i, below), c));
                }
            }
        }
        for j in range(y + 1, below) { // down
            assert!(x < w); assert!(j < h);
            let c = grid.get(x, j);
            if !self.matches_vertical_wall(c) {
                return non_match(format!("failed to match left vertical wall at {}: {}", (x, j), c));
            }
            assert!(right < w); assert!(j < h);
            let c = grid.get(right, j);
            if !extends_right {
                if !self.matches_vertical_wall(c) {
                    return non_match(format!("failed to match right vertical wall at {}: {}", (right, j), c));
                }
            } else if c == self.hidden {
                // keep going
            } else {
                if interior.is_none() {
                    interior = Some(c);
                }
                if interior.is_some() && Some(c) != interior {
                    return non_match(format!("failed to match right interior {} at {}: {}", interior, (right, j), c));
                }
            }
        }

        // Check that the interior is sound
        for i in range(x + 1, right) {
            for j in range(y + 1, below) {
                assert!(i < w); assert!(j < h);
                match (interior, grid.get(i, j)) {
                    (None, c) => {
                        if c == self.hidden {
                            // Okay, clean match and we still do not know
                            // what the interior is.
                            continue;
                        } else {
                            // finally, a non-hidden marker.  Assume
                            // that this is the interior.
                            interior = Some(c);
                            continue;
                        }
                    }
                    (Some(c1), c2) => {
                        if c1 == c2 || c2 == self.hidden {
                            // the color c2 matches the interior c1; keep
                            // going.
                            continue;
                        } else {
                            return non_match(format!("failed to match interior {} at {}: {}", c1, (i, j), c2));
                        }
                    }
                }
            }
        }

        // got this far; return either full or partial box, as
        // appropriate.

        if extends_down || extends_right {
            debug!("partial match {} interior: {}", trial, interior);
            PartialMatch
        } else {
            assert!(x+1 < w); assert!(y+1 < h);
            let fill = grid.get(x+1, y+1);
            let cmd = boxdraw::rect(x, y, box_w, box_h, fill);

            debug!("exact match: {}", cmd);
            ExactMatch(cmd)
        }
    }

    fn matches_corner(&self, c: char) -> bool {
        c == '+' || c == self.hidden
    }

    fn matches_horizontal_wall(&self, c: char) -> bool {
        c == '-' || c == self.hidden
    }

    fn matches_vertical_wall(&self, c: char) -> bool {
        c == '|' || c == self.hidden
    }
}

#[test]
fn check_simple() {
    boxdraw::check_undraw("...\n", &SimpleSearch).unwrap();

    boxdraw::check_undraw(".....\n\
                           .+-+.\n\
                           .|b|.\n\
                           .+-+.\n\
                          ",
                          &SimpleSearch).unwrap();

    boxdraw::check_undraw(".............\n\
                           .......+--+..\n\
                           .+-+...|cc|..\n\
                           .|b|...|cc|..\n\
                           .+-+...+--+..\n\
                           .............\n\
                          ",
                          &SimpleSearch).unwrap();

    boxdraw::check_undraw(".........\n\
                           .........\n\
                           .+-+.....\n\
                           .|b|.....\n\
                           .+-+.....\n\
                           .+--+....\n\
                           .|cc|....\n\
                           .|cc|....\n\
                           .+--+....\n\
                           .........\n\
                          ",
                          &SimpleSearch).unwrap();
}

#[test]
fn check_that_hidden_char_works() {
    fn check_for_1x1_picture(picture: &str) {
        let grid = Grid::from_str(picture).unwrap();
        let match_at = TryMatchAt {
            grid: &grid,
            hidden: '?',
            x: 1,
            y: 1,
        };
        assert_eq!(match_at.try(3,3), ExactMatch(boxdraw::rect(1, 1, 3, 3, 'b')));
    }

    check_for_1x1_picture(".....\n\
                           .+-+.\n\
                           .|b|.\n\
                           .+-+.\n\
                          ");

    check_for_1x1_picture(".....\n\
                           .+-+.\n\
                           .|b|.\n\
                           .+-?.\n\
                          ");

    check_for_1x1_picture(".....\n\
                           .+-+.\n\
                           .|b?.\n\
                           .+-+.\n\
                          ");

    check_for_1x1_picture(".....\n\
                           .+-+.\n\
                           .|b|.\n\
                           .+?+.\n\
                          ");

    check_for_1x1_picture(".....\n\
                           .+-+.\n\
                           .|b?.\n\
                           .+?+.\n\
                          ");

    check_for_1x1_picture(".....\n\
                           .+-+.\n\
                           .|b?.\n\
                           .+??.\n\
                          ");

    check_for_1x1_picture(".....\n\
                           .+-?.\n\
                           .|b?.\n\
                           .+?+.\n\
                          ");

    check_for_1x1_picture(".....\n\
                           .+-?.\n\
                           .?b?.\n\
                           .??+.\n\
                          ");

}

#[test]
fn check_specific_expected_case_from_overlapping_test() {
    let picture = ".............\n\
                   ....+---+....\n\
                   ....|bbb|....\n\
                   ....|bb????..\n\
                   ....|bb????..\n\
                   ....+--????..\n\
                   .......????..\n\
                   .............\n\
                  ";
    let grid = Grid::from_str(picture).unwrap();
    let match_at = TryMatchAt {
        grid: &grid,
        hidden: '?',
        x: 4,
        y: 1,
    };
    assert_eq!(match_at.try(8,5), ExactMatch(boxdraw::rect(4, 1, 5, 5, 'b')));

}

#[test]
fn overlapping_boxes() {
    boxdraw::check_undraw(".............\n\
                           ....+---+....\n\
                           ....|bbb|....\n\
                           ....|bb+--+..\n\
                           ....|bb|cc|..\n\
                           ....+--|cc|..\n\
                           .......+--+..\n\
                           .............\n\
                          ",
                          &SimpleSearch).unwrap();

}

#[test]
fn nested() {
    boxdraw::check_undraw(".............\n\
                           ..+--------+.\n\
                           ..|aaaaaaaa|.\n\
                           ..|aaaaaaaa|.\n\
                           ..|aa+--+aa|.\n\
                           ..|aa|bb|aa|.\n\
                           ..|aa|bb|aa|.\n\
                           ..|aa+--+aa|.\n\
                           ..|aaaaaaaa|.\n\
                           ..|aaaaaaaa|.\n\
                           ..+--------+.\n\
                           .............\n\
                          ",
                          &SimpleSearch).unwrap();
}

#[test]
fn three_by_three() {
    boxdraw::check_undraw(".............\n\
                           ..+--+--+--+.\n\
                           ..|aa|bb|cc|.\n\
                           ..|aa|bb|cc|.\n\
                           ..+--+--+--+.\n\
                           ..|dd|ee|ff|.\n\
                           ..|dd|ee|ff|.\n\
                           ..+--+--+--+.\n\
                           ..|gg|hh|ii|.\n\
                           ..|gg|hh|ii|.\n\
                           ..+--+--+--+.\n\
                           .............\n\
                          ",
                          &SimpleSearch).unwrap();

}
{'fraction_non_alphanumeric': 0.16268285686968162, 'fraction_numerical': 0.004828377473945884, 'mean_word_length': 0.7945440507849361, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 4, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6830280', 'n_tokens_mistral': 5931, 'n_tokens_neox': 5713, 'n_words': 1246}