IT блог

package ru.outofrange.util;
 
public class AreaUtil {
// Finds the maximum area under the histogram represented
    // by histogram. See below article for details.
    // http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
    static HistResult maxHist(int numberOfColumns, int row[]) {
        // Create an empty stack. The stack holds indexes of
        // hist[] array. The bars stored in stack are always
        // in increasing order of their heights.
        Stack<Integer> stack = new Stack<Integer>();
 
        int top_value;     // Top of the stack
 
        int max_area = 0; // Initialize max area in the current
        // row (or histogram). Row is a special case of histogram.
 
        int area = 0;    // Initialize area with the current top
 
        // Run through all bars of the given histogram (or row)
        int i = 0;
 
        int current_width = 0;
        int current_height = 0;
 
        int width = 0;
        int height = 0;
        int x1 = 0;
 
        int position = -1; // will cause an error if we misuse this variable
        Map<Integer, Integer> rightmostPositionOfThisValue = new HashMap<>();
        // Pair <3, 2> means that row[2] is the rightmost element with height = 3.
 
        while (i < numberOfColumns) {
            // If this bar is higher than the bar on top stack,
            // push it to stack
            if (stack.empty() || row[stack.peek()] <= row[i]) {
                stack.push(i++);
            } else {
                // If this bar is lower than top of stack, then
                // calculate area of rectangle with stack top as
                // the smallest (or minimum height) bar. 'i' is
                // 'right index' for the top and element before
                // top in stack is 'left index'
                position = stack.pop();
                top_value = row[position];
 
                area = top_value * i;
 
                current_width = i;
                current_height = top_value;
                Integer posOfTopValue = rightmostPositionOfThisValue.get(current_height);
                if (posOfTopValue == null || posOfTopValue < position) {
                    rightmostPositionOfThisValue.put(current_height, new Integer(position));
                }
 
                if (!stack.empty()) {
                    area = top_value * (i - stack.peek() - 1);
                    current_width = (i - stack.peek() - 1);
                    current_height = top_value;
                    if (area > 0) {
                        // We found a rectangle with non-null area in the histogram.
                        // We store the rightmost position of top_value in this area.
                        posOfTopValue = rightmostPositionOfThisValue.get(current_height);
                        if (posOfTopValue == null || posOfTopValue < position) {
                            rightmostPositionOfThisValue.put(current_height, new Integer(position));
                        }
                    }
                }
 
                //max_area = Math.max(area, max_area); // line from original algorithm, for orienting
                if (area > max_area) {
                    max_area = area;
                    width = current_width;
                    height = current_height;
                    x1 = rightmostPositionOfThisValue.get(new Integer(current_height));
                }
            }
        }
 
        // Now pop the remaining bars from stack and calculate
        // area with every popped bar as the smallest bar
        while (!stack.empty()) {
            position = stack.pop();
            top_value = row[position];
 
            area = top_value * i;
            current_width = i;
            current_height = top_value;
            Integer posOfTopValue = rightmostPositionOfThisValue.get(current_height);
            if (posOfTopValue == null || posOfTopValue < position) {
                rightmostPositionOfThisValue.put(current_height, new Integer(position));
            }
 
            if (!stack.empty()) {
                area = top_value * (i - stack.peek() - 1);
                current_width = (i - stack.peek() - 1);
                current_height = top_value;
                if (area > 0) {
                    // We found a rectangle with non-null area in the histogram.
                    // We store the rightmost position of top_value in this area.
                    posOfTopValue = rightmostPositionOfThisValue.get(current_height);
                    if (posOfTopValue == null || posOfTopValue < position) {
                        rightmostPositionOfThisValue.put(current_height, new Integer(position));
                    }
                }
            }
 
            //max_area = Math.max(area, max_area); // line from original algorithm, for orienting
            if (area > max_area) {
                max_area = area;
                width = current_width;
                height = current_height;
                x1 = rightmostPositionOfThisValue.get(new Integer(current_height));
            }
        }
 
        // in array like {1, 2, 1, 2} we have max_height = 1 and it will give x1=2 so far which
        // isn't correct. We need to go to the right of this position and find rightmost
        // position of array where height>= found height. This position is 3 for this particular case.
 
        if (x1 < numberOfColumns) {
            position = x1 + 1;
            while (position < numberOfColumns) {
                if (row[position] >= row[x1]) {
                    x1 = position++;
                } else {
                    break;
                }
            }
        }
 
        return new HistResult(max_area, width, height, x1);
    }
 
    // Returns area and coordinates of the largest rectangle with all 1s in
    // A[][]
    // http://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/
    static Result maxRectangle(int numberOfRows, int numberOfColumns, int A[][]) {
        // Calculate area for first row and initialize it as
        // result
        HistResult histResult = maxHist(numberOfColumns, A[0]);
        //System.out.println("first call " + pairResult.getSquare());
        Integer result = histResult.getSquare();
        int x1 = histResult.getX1();
 
        // iterate over row to find maximum rectangular area
        // considering each row as histogram
 
        int width = 0;
        int height = 0;
        int y1 = -1; // if value -1 remains here, then we need to check the value of found square.
        // If it's > 0 then y1 = 0 - rectangle lies in the 0th row (has height = 1).
 
        for (int i = 1; i < numberOfRows; i++) {
            for (int j = 0; j < numberOfColumns; j++) {
                // if A[i][j] is 1 then add A[i -1][j]
                if (A[i][j] == 1) A[i][j] += A[i - 1][j];
            }
            // Update result if area with current row (as last
            // row of rectangle) is more
 
            HistResult currentResult = maxHist(numberOfColumns, A[i]);
 
            int currentMax = currentResult.getSquare();
 
            //result = Math.max(result, maxHist(R, C, A[i])); // line from original algorithm
            if (result < currentMax) {
                result = currentMax;
                y1 = i;
                width = currentResult.getWidth();
                height = currentResult.getHeight();
                x1 = currentResult.getX1();
            }
        }
 
        // special handling of the case when found area belongs to the 0th row. In this case y1=-1
        if (y1 == -1 && result != 0) {
            y1 = 0;
            height = 1;
            width = result / height;
        }
 
        return new Result(x1 - width + 1, y1 - height + 1, x1, y1);
    }
 
static class HistResult {
        private int square;
        private int width;
        private int height;
        private int x1;
 
        public HistResult(int square, int width, int height, int x1) {
            this.square = square;
            this.width = width;
            this.height = height;
            this.x1 = x1;
        }
 
        public int getHeight() {
            return height;
        }
 
        public int getSquare() {
            return square;
        }
 
        public int getWidth() {
            return width;
        }
 
        public int getX1() {
            return x1;
        }
    }
 
    static class Result {
        private int x0, y0;
        private int x1, y1;
 
        public Result(int x0, int y0, int x1, int y1) {
            this.x0 = x0;
            this.y0 = y0;
            this.x1 = x1;
            this.y1 = y1;
        }
 
        public int getX0() {
            return x0;
        }
 
        public int getY0() {
            return y0;
        }
 
        public int getX1() {
            return x1;
        }
 
        public int getY1() {
            return y1;
        }
    }
}

package ru.outofrange.util;
 
import org.junit.Assert;
import org.junit.Test;
 
public class AreaUtilTest {
@Test
    public void testHist1() {
        int A[] = {0, 1, 1, 0};
        int C = 4;
        HistResult hr = maxHist(C, A);
        int x1 = hr.x1;
        Assert.assertEquals(2, x1);
    }
 
    @Test
    public void testHist2() {
        int A[] = {1, 1, 1, 0};
        int C = 4;
        HistResult hr = maxHist(C, A);
        int x1 = hr.x1;
        Assert.assertEquals(2, x1);
    }
 
    @Test
    public void testHist3() {
        int A[] = {1, 2, 1, 2};
        int C = 4;
        HistResult hr = maxHist(C, A);
        int x1 = hr.x1;
        Assert.assertEquals(3, x1);
    }
 
    @Test
    public void testHist4() {
        int A[] = {1, 2, 2, 2};
        int C = 4;
        HistResult hr = maxHist(C, A);
        int x1 = hr.x1;
        Assert.assertEquals(3, x1);
    }
 
    @Test
    public void testHist5() {
        int A[] = {2, 1, 1, 1};
        int C = 4;
        HistResult hr = maxHist(C, A);
        int x1 = hr.x1;
        Assert.assertEquals(3, x1);
    }
 
    @Test
    public void testHist6() {
        int A[] = {0, 0, 1, 0};
        int C = 4;
        HistResult hr = maxHist(C, A);
        int x1 = hr.x1;
        Assert.assertEquals(2, x1);
    }
 
    @Test
    public void testHist7() {
        int A[] = {5, 1, 1, 1};
        int C = 4;
        HistResult hr = maxHist(C, A);
        int x1 = hr.x1;
        Assert.assertEquals(0, x1);
    }
 
    @Test
    public void testHist8() {
        int A[] = {2, 3, 2, 4};
        int C = 4;
        HistResult hr = maxHist(C, A);
        int x1 = hr.x1;
        Assert.assertEquals(3, x1);
    }
 
    @Test
    public void testHist9() {
        int A[] = {2, 3, 3, 2};
        int C = 4;
        HistResult hr = maxHist(C, A);
        int x1 = hr.x1;
        Assert.assertEquals(3, x1);
    }
 
    @Test
    public void testHist10() {
        int A[] = {0, 1, 1, 0, 1, 1, 1, 0};
        int C = 8;
        HistResult hr = maxHist(C, A);
        int x1 = hr.x1;
        Assert.assertEquals(6, x1);
    }
 
    @Test
    public void test1() {
        // dimensions
        int R = 4;
        int C = 4;
 
        int A[][] = {{0, 1, 1, 0},
                {1, 1, 1, 1},
                {1, 1, 1, 1},
                {1, 0, 1, 0},
        };
 
 
        Result result = maxRectangle(R, C, A);
 
        int x0 = result.getX0();
        int y0 = result.getY0();
        int x1 = result.getX1();
        int y1 = result.getY1();
 
        int width = x1 - x0 + 1;
        int height = y1 - y0 + 1;
        int square = width * height;
        System.out.println("Area of the largest rectangle is " + square);
        System.out.println("x0 = " + result.getX0());
        System.out.println("y0 = " + result.getY0());
        System.out.println("x1 = " + result.getX1());
        System.out.println("y1 = " + result.getY1());
        System.out.println("width = " + width);
        System.out.println("height = " + height);
        Assert.assertEquals(8, square);
        Assert.assertEquals(4, width);
        Assert.assertEquals(2, height);
        Assert.assertEquals("X1", 3, result.getX1());
        Assert.assertEquals(2, y1);
    }
 
    @Test
    public void test2() {
 
        int R = 4;
        int C = 4;
 
        int A[][] = {{1, 1, 1, 0},
                {1, 1, 1, 1},
                {1, 1, 1, 1},
                {1, 0, 1, 0},
        };
 
        Result result = maxRectangle(R, C, A);
 
        int x0 = result.getX0();
        int y0 = result.getY0();
        int x1 = result.getX1();
        int y1 = result.getY1();
 
        int width = x1 - x0 + 1;
        int height = y1 - y0 + 1;
        int square = width * height;
        System.out.println("Area of the largest rectangle is " + square);
        System.out.println("x0 = " + result.getX0());
        System.out.println("y0 = " + result.getY0());
        System.out.println("x1 = " + result.getX1());
        System.out.println("y1 = " + result.getY1());
        System.out.println("width = " + width);
        System.out.println("height = " + height);
        Assert.assertEquals(9, square);
        Assert.assertEquals(3, width);
        Assert.assertEquals(3, height);
        Assert.assertEquals("X1", 2, result.getX1());
        Assert.assertEquals(2, y1);
    }
 
    @Test
    public void test3() {
 
        int R = 4;
        int C = 4;
 
        int A[][] = {{0, 0, 1, 0},
                {1, 0, 1, 0},
                {0, 1, 1, 1},
                {1, 0, 1, 0},
        };
 
        Result result = maxRectangle(R, C, A);
 
        int x0 = result.getX0();
        int y0 = result.getY0();
        int x1 = result.getX1();
        int y1 = result.getY1();
 
        int width = x1 - x0 + 1;
        int height = y1 - y0 + 1;
        int square = width * height;
        System.out.println("Area of the largest rectangle is " + square);
        System.out.println("x0 = " + result.getX0());
        System.out.println("y0 = " + result.getY0());
        System.out.println("x1 = " + result.getX1());
        System.out.println("y1 = " + result.getY1());
        System.out.println("width = " + width);
        System.out.println("height = " + height);
        Assert.assertEquals(4, square);
        Assert.assertEquals(1, width);
        Assert.assertEquals(4, height);
        Assert.assertEquals("X1", 2, result.getX1());
        Assert.assertEquals(3, y1);
    }
 
    @Test
    public void test4() {
 
        int R = 4;
        int C = 4;
 
        int A[][] = {{1, 1, 1, 0},
                {1, 0, 1, 0},
                {0, 1, 0, 1},
                {1, 0, 1, 0},
        };
 
        Result result = maxRectangle(R, C, A);
 
        int x0 = result.getX0();
        int y0 = result.getY0();
        int x1 = result.getX1();
        int y1 = result.getY1();
 
        int width = x1 - x0 + 1;
        int height = y1 - y0 + 1;
        int square = width * height;
        System.out.println("Area of the largest rectangle is " + square);
        System.out.println("x0 = " + result.getX0());
        System.out.println("y0 = " + result.getY0());
        System.out.println("x1 = " + result.getX1());
        System.out.println("y1 = " + result.getY1());
        System.out.println("width = " + width);
        System.out.println("height = " + height);
        Assert.assertEquals(3, square);
        Assert.assertEquals(3, width);
        Assert.assertEquals(1, height);
        Assert.assertEquals("X1", 2, result.getX1());
        Assert.assertEquals(0, y1);
    }
 
    @Test
    public void test5() {
 
        int R = 4;
        int C = 4;
 
        int A[][] = {{1, 0, 1, 0},
                {1, 0, 0, 0},
                {1, 0, 0, 1},
                {1, 0, 1, 0},
        };
 
        Result result = maxRectangle(R, C, A);
 
        int x0 = result.getX0();
        int y0 = result.getY0();
        int x1 = result.getX1();
        int y1 = result.getY1();
 
        int width = x1 - x0 + 1;
        int height = y1 - y0 + 1;
        int square = width * height;
        System.out.println("Area of the largest rectangle is " + square);
        System.out.println("x0 = " + result.getX0());
        System.out.println("y0 = " + result.getY0());
        System.out.println("x1 = " + result.getX1());
        System.out.println("y1 = " + result.getY1());
        System.out.println("width = " + width);
        System.out.println("height = " + height);
        Assert.assertEquals(4, square);
        Assert.assertEquals(1, width);
        Assert.assertEquals(4, height);
        Assert.assertEquals("X1", 0, result.getX1());
        Assert.assertEquals(3, y1);
    }
 
    @Test
    public void test6() {
 
        int R = 4;
        int C = 4;
 
        int A[][] = {{1, 0, 1, 0},
                {1, 0, 0, 0},
                {1, 0, 1, 1},
                {0, 0, 1, 1},
        };
 
        Result result = maxRectangle(R, C, A);
 
        int x0 = result.getX0();
        int y0 = result.getY0();
        int x1 = result.getX1();
        int y1 = result.getY1();
 
        int width = x1 - x0 + 1;
        int height = y1 - y0 + 1;
        int square = width * height;
        System.out.println("Area of the largest rectangle is " + square);
        System.out.println("x0 = " + result.getX0());
        System.out.println("y0 = " + result.getY0());
        System.out.println("x1 = " + result.getX1());
        System.out.println("y1 = " + result.getY1());
        System.out.println("width = " + width);
        System.out.println("height = " + height);
        Assert.assertEquals(4, square);
        Assert.assertEquals(2, width);
        Assert.assertEquals(2, height);
        Assert.assertEquals("X1", 3, result.getX1());
        Assert.assertEquals(3, y1);
    }
 
    @Test
    public void test7() {
 
        int R = 4;
        int C = 4;
 
        int A[][] = {{0, 0, 1, 0},
                {1, 1, 0, 0},
                {1, 1, 1, 0},
                {1, 1, 0, 1},
        };
 
        Result result = maxRectangle(R, C, A);
 
        int x0 = result.getX0();
        int y0 = result.getY0();
        int x1 = result.getX1();
        int y1 = result.getY1();
 
        int width = x1 - x0 + 1;
        int height = y1 - y0 + 1;
        int square = width * height;
        System.out.println("Area of the largest rectangle is " + square);
        System.out.println("x0 = " + result.getX0());
        System.out.println("y0 = " + result.getY0());
        System.out.println("x1 = " + result.getX1());
        System.out.println("y1 = " + result.getY1());
        System.out.println("width = " + width);
        System.out.println("height = " + height);
        Assert.assertEquals(6, square);
        Assert.assertEquals(2, width);
        Assert.assertEquals(3, height);
        Assert.assertEquals("X1", 1, result.getX1());
        Assert.assertEquals(3, y1);
    }
}