using System;

namespace Sandbox.Helper;

public class Histogram {

	private static Vector2 GetMaxRectangle(int[] hist, int width, out int posX) {

        posX = 0;

        // 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<int> s = new Stack<int>();

        int max_area = 0; // Initialize max area 
        int tp; // To store top of stack 
        int area_with_top; // To store area with top  
                           // bar as the smallest bar 
        int max_area_height = 0;
        int max_area_width = 0;

        // Run through all bars of 
        // given histogram  
        int i = 0;
        while (i < width) {
            // If this bar is higher than the  
            // bar on top stack, push it to stack  
            if (s.Count == 0 || hist[s.Peek()] <= hist[i]) {
                s.Push(i++);
            }

            // 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'  
            else {
                tp = s.Peek(); // store the top index 
                s.Pop(); // pop the top 

                // Calculate the area with hist[tp] 
                // stack as smallest bar  

                int h = (s.Count == 0 ? i : i - s.Peek() - 1);
                area_with_top = hist[tp] * h;

                // update max area, if needed  
                if (max_area < area_with_top) {
                    max_area = area_with_top;
                    max_area_width = h;
                    max_area_height = hist[tp];
                    posX = i - max_area_width;
                }
            }
        }

        // Now pop the remaining bars from  
        // stack and calculate area with every  
        // popped bar as the smallest bar  
        while (s.Count > 0) {
            tp = s.Peek();
            s.Pop();
            int h = (s.Count == 0 ? i : i - s.Peek() - 1);
            area_with_top = hist[tp] * h;

            if (max_area < area_with_top) {
                max_area = area_with_top;
                max_area_width = h;
                max_area_height = hist[tp];
                posX = i - max_area_width;
            }
        }

        return new Vector2(max_area_width, max_area_height);
    }

	private static BBox GetMaximumRectangleBounds( List<int> values, int width, int height )
	{
		int[] hist = new int[width];
		int maxArea = 0;
		int rectW = 0, rectH = 0, rectX = 0, rectY = 0;

		for ( int y = 0; y < height; y++ )
		{
			for ( int x = 0; x < width; x++ )
			{
				hist[x] = values[(width * y) + x] == 0 ? 0 : hist[x] + 1;
			}

			Vector2 size = GetMaxRectangle( hist, width, out int posX );
			int area = (int)size.x * (int)size.y;

			if ( area > maxArea )
			{
				maxArea = area;
				rectW = (int)size.x;
				rectH = (int)size.y;
				rectX = posX;
				rectY = y - rectH + 1;  // top row
			}
		}

		// BBox in integer tile coords — no float offsets
		var mins = new Vector3( rectX, rectY, 0 );
		var maxs = new Vector3( rectX + rectW, rectY + rectH, 0 );
		return new BBox( mins, maxs );
	}

	public static IEnumerable<BBox> GetOptimalQuadding( List<int> values, int width, int height )
	{
		List<int> map = new List<int>( values );
		int maxRecursion = width * height;

		while ( map.FindAll( ( int x ) => x == 1 ).Count > 0 && maxRecursion >= 0 )
		{
			maxRecursion--;

			BBox b = Histogram.GetMaximumRectangleBounds( map, width, height );

			if ( b.Size.x <= 0 || b.Size.y <= 0 ) break;

			ClearMapValuesInBBox( ref map, width, b );

			yield return b;
		}
	}

	private static void ClearMapValuesInBBox( ref List<int> map, int mapWidth, BBox toClear )
	{
		int startX = (int)toClear.Mins.x;
		int startY = (int)toClear.Mins.y;
		int endX = (int)toClear.Maxs.x;
		int endY = (int)toClear.Maxs.y;
		int mapHeight = map.Count / mapWidth;

		startX = Math.Clamp( startX, 0, mapWidth );
		startY = Math.Clamp( startY, 0, mapHeight );
		endX = Math.Clamp( endX, 0, mapWidth );
		endY = Math.Clamp( endY, 0, mapHeight );

		for ( int x = startX; x < endX; x++ )
			for ( int y = startY; y < endY; y++ )
				map[(mapWidth * y) + x] = 0;
	}
}