Describe a 2D Bitmap Using Filled Rectangle Mapping

codegolf_173977.rs

// https://codegolf.stackexchange.com/questions/173977/describe-a-2d-bitmap-using-filled-rectangle-mapping#173977
// Badel2

extern crate rand;
use rand::{Rng, thread_rng};

#[derive(Copy, Clone, Debug)]
struct Rect {
    x0: usize,
    y0: usize,
    x1: usize,
    y1: usize
}

impl Rect {
    fn contains_xslice(&self, xa: usize, xb: usize) -> bool {
        self.x0 <= xa && xb <= self.x1
    }
    fn contains(&self, r: &Rect) -> bool {
        // r is completely inside of self
        self.x0 <= r.x0 && r.x1 <= self.x1 && self.y0 <= r.y0 && r.y1 <= self.y1
    }
}

fn display_rects(r: &[Rect]) -> String {
    let s = r.iter()
        .map(|z| format!("{},{},{},{}", z.x0, z.y0, z.x1, z.y1))
        .collect::<Vec<_>>()
        .join(",");

    // transform 1,1 into {1,1}
    format!("{{{}}}", s)
}

fn draw_rects(r: &[Rect], w: usize, h: usize) -> String {
    let mut s = format!("");
    for y in 0..h {
        for x in 0..w {
            let p = Rect { x0: x, x1: x, y0: y, y1: y };
            if r.iter().any(|a| a.contains(&p)) {
                s.push_str("1");
            } else {
                s.push_str("0");
            }
        }
        s.push_str("\n");
    }
    s
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct Matrix {
    v: Vec<u8>,
    size: (usize, usize),
}

impl Matrix {
    fn new(w: usize, h: usize) -> Self {
        Self {
            v: vec![0; w*h],
            size: (w, h),
        }
    }
    fn from_str(s: &str) -> Self {
        let mut v = vec![];
        let mut w = None;
        let mut h = 0;
        for l in s.lines() {
            h += 1;
            let mut tw = 0;
            for c in l.chars() {
                tw += 1;
                let x = match c {
                    '0' => 0,
                    '1' => 1,
                    a => panic!("Invalid input! {:?} at {},{}", a, tw, h),
                };
                v.push(x);
            }
            if let Some(ww) = w {
                if tw != ww {
                    panic!("All lines must have the same width! {} != {}", tw, ww);
                }
            } else {
                w = Some(tw);
            }
        }

        let w = w.unwrap_or(0);

        Matrix {
            v,
            size: (w, h),
        }
    }
    fn random(w: usize, h: usize) -> Self {
        let mut rng = thread_rng();
        let mut v = vec![];

        for _ in 0..w*h {
            let n = rng.gen_range(0, 6+1);
            let x = if n == 0 { 0 } else { 1 };
            v.push(x);
        }

        Matrix {
            v,
            size: (w, h),
        }
    }
    fn get(&self, x: usize, y: usize) -> u8 {
        self.v[y * self.size.0 + x]
    }
    fn hline(&self, y: usize) -> &[u8] {
        &self.v[y * self.size.0 .. (y + 1) * self.size.0]
    }
    fn hline_1_pieces(&self, y: usize) -> Vec<Rect> {
        let mut r = vec![];
        let line = self.hline(y);
        let xmax = self.size.0 - 1;
        let y0 = y;
        let y1 = y;
        let mut lineit = line.iter();
        let mut xoff = 0;
        while lineit.len() > 0 {
            // Find first non-zero pixel
            if let Some(x0) = lineit.position(|&x| x != 0) {
                let x0 = xoff + x0;
                // x0..x1 is a line of 11111
                let x1 = x0 + lineit.position(|&x| x == 0).unwrap_or(xmax - x0);
                r.push(Rect { x0, x1, y0, y1 });
                // Remember offset because the iterator is being consumed
                xoff = x1 + 2;
            }
        }
        
        r
    }
    fn rectangles(&self) -> Vec<Rect> {
        let mut r: Vec<Rect> = vec![];
        let ymax = self.size.1 - 1;
        // For each hline, add rectangles covering the maximum width possible
        let hpieces: Vec<Vec<Rect>> = (0..self.size.1).map(|i| self.hline_1_pieces(i)).collect();
        // Extend each rectangle down while possible
        for (y0, layer) in hpieces.iter().enumerate() {
            for rect in layer {
                let mut y = y0 + 1;
                while y <= ymax {
                    if hpieces[y].iter().any(|&r| r.contains_xslice(rect.x0, rect.x1)) {
                        y += 1;
                    } else {
                        break;
                    }
                }
                let y1 = y - 1;
                let rn = Rect { y1, ..*rect };
                if r.iter().any(|&r1| r1.contains(&rn)) {
                    // An equivalent rectangle is already in the vec
                } else {
                    // This rectangle covers some new area, push it
                    r.push(rn);
                }
            }
        }

        r
    }
}

fn benchmark(iterations: usize) -> f64 {
    let mut sum = 0;
    for _ in 0..iterations {
        let m = Matrix::random(20, 20);
        let r = m.rectangles();
        let output = draw_rects(&m.rectangles(), 20, 20);
        assert_eq!(m, Matrix::from_str(&output));
        sum += r.len();
    }
    sum as f64 / iterations as f64
}

fn main() {
    let input = "\
0000000000111100000000
0000000011111110000000
0000111111111111000000
0000011111111111000000
0000000000000000000000
1111111000000000011111
1111111111100000000011
1111111111111111000000
";
    let m = Matrix::from_str(input);
    assert_eq!(input, draw_rects(&m.rectangles(), 22, 8));
    println!("{}", display_rects(&m.rectangles()));
    println!("{}", benchmark(10000));
}