using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RectangleMapper
{


    /// <summary>
    /// Stores non-located 2D rectangle
    /// </summary>
    public class Box
    {
        public int Width { get; set; }
        public int Height { get; set; }
        public object Tag { get; set; }
        public Box(int w, int h)
        {
            Width = w;
            Height = h;
        }
        public Box() : this(0, 0) { }
    }
    /// <summary>
    /// Stores a location
    /// </summary>
    public class Point
    {
        public int Left { get; set; }
        public int Top { get; set; }
        public Point(int x, int y)
        {
            Left = x;
            Top = y;
        }
        public Point() : this(0, 0) { }
    }
    /// <summary>
    /// Horizontal strip of similar boxes
    /// </summary>
    public class BoxStrip
    {
        public List<Box> Elements { get; private set; }
        public int Width
        {
            get
            {
                if (Elements.Count == 0)
                    return 0;
                return Elements[0].Width * Elements.Count;
            }
        }
        public int Height
        {
            get
            {
                if (Elements.Count == 0)
                    return 0;
                return Elements[0].Height * Elements.Count;
            }
        }
        public BoxStrip()
        {
            Elements = new List<Box>();
        }
    }

    public class StripRectangle
    {
        public BoxStrip Size { get; private set; }
        public Point Location { get; private set; }

        public bool Contains(Point p)
        {
            return ((p.Left >= Location.Left) && (p.Left < (Location.Left + Size.Width)) &&
                (p.Top >= Location.Top) && (p.Top < (Location.Top + Size.Height)));
        }
        public bool Contains(int x, int y)
        {
            return ((x >= Location.Left) && (x < (Location.Left + Size.Width))
                && (y >= Location.Top) && (y < (Location.Top + Size.Height)));
        }

        public StripRectangle(BoxStrip size, Point location)
        {
            Size = size;
            Location = location;
        }
    }

    public static class Extensions
    {
        public static List<BoxStrip> GetStrips(this List<Box> boxes)
        {
            List<BoxStrip> strips = new List<BoxStrip>();
            foreach (var box in boxes)
            {
                var strip = strips.Find(s => s.Elements[0].Height == box.Height);
                if (strip == null)
                {
                    strip = new BoxStrip();
                    strips.Add(strip);
                }
                strip.Elements.Add(box);
            }
            return strips;
        }

        public static List<StripRectangle> GetRectangleMap(
            this List<Box> boxes)
        {
            List<StripRectangle> output = new List<StripRectangle>();
            List<BoxStrip> strips = boxes.GetStrips();

            if (strips.Count == 0)
                return output;

            strips.Sort((s1, s2) => s2.Height - s1.Height);

            int HMAX = strips[0].Height;
            int cx = strips[0].Width;
            output.Add(new StripRectangle(strips[0], new Point(0, 0)));
            while (strips.Count > 0)
            {
                int cy = 0;
                for (var coveringStrip = output.First(of => of.Contains(cx, cy));
                    coveringStrip != null;
                    coveringStrip = output.First(of=>of.Contains(cx,cy))
                    )
                    cy = coveringStrip.Location.Top + coveringStrip.Size.Height;
                int cy2 = HMAX - 1;
                for (var coveringStrip = output.First(of => of.Contains(cx, cy2));
                    coveringStrip != null;
                    coveringStrip = output.First(of => of.Contains(cx, cy2)))
                    cy2 = coveringStrip.Location.Top - 1;
                if (cy2 < 0)
                {
                    cx = (from os in output
                          where os.Contains(cx, cy)
                          select os.Location.Left + os.Size.Width).Min();
                    continue;
                }
                int dh = 1 + cy2 - cy;
                BoxStrip selected = null;
                foreach(var s in strips)
                    if (s.Height <= dh)
                    {
                        selected = s;
                        break;
                    }
                if (selected == null)
                {
                    cx = (from os in output
                          where os.Location.Left + os.Size.Width >= cx
                          select os.Location.Left + os.Size.Width).Min();
                    continue;
                }
                strips.Remove(selected);
                output.Add(new StripRectangle(selected, new Point(cx, cy)));
            }
            return output;
        }
    }



}