Rectangles2.R

rectangles <- function(m, rowfirst = TRUE) {

    if (rowfirst)
        m <- t(m)
    n <- length(m)
    nrow <- nrow(m)
    ncol <- ncol(m)
    rowindex <- seq_len(nrow)
    colindex <- seq_len(ncol)
    h <- hashtab()

    # initial column
    start <- shp <- 1L
    for (i in rowindex[-nrow]) {
        if (m[i] != m[i + 1L]) {
            sethash(h, start:(i), shp)
            start <- i + 1L
            shp <- shp + 1L
        }
    }
    sethash(h, start:nrow, shp)
    shp <- shp + 1L

    # subsequent columns
    for (j in colindex[-1L]) {
        idx <- startidx <- nrow * (j - 1L) + 1L
        for (i in rowindex[-nrow]) {
            if (m[idx] != m[idx + 1L]) {
                current <- startidx:idx
                previous <- current - nrow
                hsh <- gethash(h, previous)
                if (!is.null(hsh) && m[previous[1L]] == m[current[1L]]) {
                    sethash(h, current, hsh)
                } else {
                    sethash(h, current, shp)
                    shp <- shp + 1L
                }
                startidx <- idx + 1L
            }
            idx <- idx + 1L
        }
        
        # handle last row
        current <- startidx:idx
        previous <- current - nrow
        hsh <- gethash(h, previous)
        if (!is.null(hsh) && m[previous[1L]] == m[current[1L]]) {
            sethash(h, current, hsh)
        } else {
            sethash(h, current, shp)
            shp <- shp + 1L
        }
    }

    rectangle <- integer(n)
    maphash(h, function(key, value) rectangle[key] <<- value)
    out <- matrix(rectangle, nrow, ncol)
    if (rowfirst)
        out <- t(out)
    out
}


(m <- matrix(c(1,1,2,1,1,1,2,1,1), 3, 3))
(out <- rectangles(m))
cbind(
    expand.grid(row = 1:nrow(m), col = 1:ncol(m)),
    rectangle = as.integer(out)
)