# Path: tryalgo/rectangles_from_histogram.py
# def rectangles_from_histogram(H):
#     """Largest Rectangular Area in a Histogram
# 
#     :param H: histogram table
#     :returns: area, left, height, right, rect. is [0, height] * [left, right)
#     :complexity: linear
#     """
#     best = (float('-inf'), 0, 0, 0)
#     S = []
#     H2 = H + [float('-inf')]  # extra element to empty the queue
#     for right, _ in enumerate(H2):
#         x = H2[right]
#         left = right
#         while len(S) > 0 and S[-1][1] >= x:
#             left, height = S.pop()
#             # first element is area of candidate
#             rect = (height * (right - left), left, height, right)
#             if rect > best:
#                 best = rect
#         S.append((left, x))
#     return best


from tryalgo.rectangles_from_histogram import rectangles_from_histogram
# -*- coding: utf-8 -*-
"""\
Largest area rectangle in a binary matrix
plus grand rectangle monochromatique
jill-jenn vie et christoph durr - 2014-2018
"""



# snip{
def rectangles_from_grid(P, black=1):
    """Largest area rectangle in a binary matrix

    :param P: matrix
    :param black: search for rectangles filled with value black
    :returns: area, left, top, right, bottom of optimal rectangle
             consisting of all (i,j) with
             left <= j < right and top <= i <= bottom
    :complexity: linear
    """
    rows = len(P)
    cols = len(P[0])
    t = [0] * cols
    best = None
    for i in range(rows):
        for j in range(cols):
            if P[i][j] == black:
                t[j] += 1
            else:
                t[j] = 0

# Path: tryalgo/rectangles_from_histogram.py
# def rectangles_from_histogram(H):
#     """Largest Rectangular Area in a Histogram
# 
#     :param H: histogram table
#     :returns: area, left, height, right, rect. is [0, height] * [left, right)
#     :complexity: linear
#     """
#     best = (float('-inf'), 0, 0, 0)
#     S = []
#     H2 = H + [float('-inf')]  # extra element to empty the queue
#     for right, _ in enumerate(H2):
#         x = H2[right]
#         left = right
#         while len(S) > 0 and S[-1][1] >= x:
#             left, height = S.pop()
#             # first element is area of candidate
#             rect = (height * (right - left), left, height, right)
#             if rect > best:
#                 best = rect
#         S.append((left, x))
#     return best


# Path: tryalgo/rectangles_from_grid.py
from tryalgo.rectangles_from_histogram import rectangles_from_histogram

# -*- coding: utf-8 -*-
"""\
Largest area rectangle in a binary matrix
plus grand rectangle monochromatique
jill-jenn vie et christoph durr - 2014-2018
"""



# snip{
def rectangles_from_grid(P, black=1):
    """Largest area rectangle in a binary matrix

    :param P: matrix
    :param black: search for rectangles filled with value black
    :returns: area, left, top, right, bottom of optimal rectangle
             consisting of all (i,j) with
             left <= j < right and top <= i <= bottom
    :complexity: linear
    """
    rows = len(P)
    cols = len(P[0])
    t = [0] * cols
    best = None
    for i in range(rows):
        for j in range(cols):
            if P[i][j] == black:
                t[j] += 1
            else:
                t[j] = 0

        (area, left, height, right) = rectangles_from_histogram(t)