Calculating rowspan and colspan for html table (Algorithm)

I have been working about 18 hours and I became a zombie.. And I can't figure out this problem without your help..

Project

I am working on a pdf to epub converter application what converts pdf files to epub format.

Problem

Because of EPub limitations, absolute positioning is not allowed on EPub xhtml. So, i decided to use table layout for all elements (text and images) on a page (html).

But i can't imagine how i could calculate the rowspan and colspan values of cells..

What I Did

    class TableItem
    {
        public IRenderable Item;
        public Rectangle Bounds;
        public int RowSpan, ColSpan;
        public TableItem(Rectangle bounds, IRenderable item)
        {
            this.Bounds = bounds;
            this.Item = item;
        }
    }

    class Table
    {
        Rectangle bounds;
        List<TableItem> items;

        public Table(int width, int height)
        {
            bounds = new Rectangle(0, 0, width, height);
            items = new List<TableItem>();
        }

        public void Add(IRenderable item)
        {
            Rectangle rect = Rectangle.Intersect(bounds, item.GetBounds());
            if (rect.IsEmpty)
                return;
            items.Add(new TableItem(rect, item));
        }

        List<TableItem> Slice(List<TableItem> list, int startIndex, int endIndex)
        {
            TableItem[] tmp = new TableItem[endIndex - startIndex];
            list.CopyTo(startIndex, tmp, 0, tmp.Length);
            return new List<TableItem>(tmp);
        }

        List<TableItem>[] Analyze(out int maxCol)
        {
            maxCol = 0;
            if (items.Count < 1)
                return new List<TableItem>[0];

            /*
            items.Sort
                (
                    delegate(TableItem x, TableItem y)
                    {
                        if (x.Bounds.Y == y.Bounds.Y)
                            return x.Bounds.X - y.Bounds.X;
                        return x.Bounds.Y - y.Bounds.Y;
                    }
                );
             */ 

            List<Rectangle> freeAreas = new List<Rectangle>();
            freeAreas.Add(bounds);

            foreach (TableItem item in items)
            {
                for (int i = 0; i < freeAreas.Count; i++)
                {
                    Rectangle area;
                    if ((area = freeAreas[i]).Contains(item.Bounds))
                    {
                        freeAreas.RemoveAt(i);
                        freeAreas.InsertRange(i, SplitRect(area, item.Bounds));
                    }
                }
            }

            foreach (Rectangle rt in freeAreas)
                items.Add(new TableItem(rt, null));

            items.Sort
                (
                    delegate(TableItem x, TableItem y)
                    {
                        if (x.Bounds.Y == y.Bounds.Y)
                            return x.Bounds.X - y.Bounds.X;
                        return x.Bounds.Y - y.Bounds.Y;
                    }
                );

            List<List<TableItem>> xlist = new List<List<TableItem>>();
            int lasty = items[0].Bounds.Y;
            int startIndex = 0;
            for(int i=0;i<items.Count;i++)
                if (lasty < items[i].Bounds.Y)
                {
                    lasty = items[i].Bounds.Y;
                    List<TableItem> xl = Slice(items, startIndex, i);
                    xlist.Add(xl);
                    startIndex = i;
                    if (maxCol < xl.Count)
                        maxCol = xl.Count;
                }

            if (startIndex < items.Count - 1)
            {
                xlist.Add(Slice(items, startIndex, items.Count));
                int t = xlist[xlist.Count - 1].Count;
                if (maxCol < t)
                    t = maxCol;
            }

            return xlist.ToArray();
        }

        private Rectangle[] SplitRect(Rectangle a, Rectangle r)
        {
            if (a == r)
                return new Rectangle[0];

            if (!Rectangle.Inflate(a, -2, -2).Contains(r))
                return new Rectangle[0];

            #region MyRegion
            if (r.X == a.X)
            {
                if (r.Height == a.Height)
                {
                    #region MyRegion
                    return new Rectangle[]
                    {
                        new Rectangle(r.Right, a.Y, a.Width - r.Width, a.Height)
                    };
                    #endregion
                }
                else if (r.Y == a.Y)
                {
                    #region MyRegion
                    if (r.Width == a.Width)
                    {
                        return new Rectangle[]
                        {
                            new Rectangle(a.X, r.Bottom, a.Width, a.Height - r.Height)
                        };
                    }
                    return new Rectangle[]
                    {
                        new Rectangle(r.Right, a.Y, a.Width - r.Width, r.Height),
                        new Rectangle(a.X, r.Bottom, a.Width, a.Height - r.Height)
                    };
                    #endregion
                }
                else if (r.Bottom == a.Bottom)
                {
                    #region MyRegion
                    if (r.Width == a.Width)
                    {
                        return new Rectangle[]
                        {
                            new Rectangle(a.X, a.Y, a.Width, r.Y - a.Y)
                        };
                    }
                    return new Rectangle[]
                    {
                        new Rectangle(a.X, a.Y, a.Width, r.Y - a.Y),
                        new Rectangle(r.Right, r.Y, a.Width - r.Width, r.Height)
                    };
                    #endregion
                }
                else
                {
                    #region MyRegion
                    if (a.Width == r.Width)
                    {
                        return new Rectangle[]
                        {
                            new Rectangle(a.X, a.Y, a.Width, a.Height - (r.Y - a.Y)),
                            new Rectangle(a.X, r.Bottom, a.Width, a.Height - (r.Bottom - a.Y))
                        };
                    }
                    return new Rectangle[]
                    {
   开发者_如何学运维                     new Rectangle(a.X, a.Y, a.Width, a.Height - (r.Y - a.Y)),
                        new Rectangle(r.Right, r.Y, a.Width - r.Right, r.Height),
                        new Rectangle(a.X, r.Bottom, a.Width, a.Height - (r.Bottom - a.Y))
                    };
                    #endregion
                }
            }
            else if (r.Y == a.Y)
            {
                if (r.Height == a.Height)
                {
                    #region MyRegion
                    if (r.Right == a.Right)
                    {
                        return new Rectangle[]
                        {
                            new Rectangle(a.X, a.Y, a.Width - r.Width, a.Height)
                        };
                    }
                    return new Rectangle[]
                    {
                        new Rectangle(a.X, a.Y, r.X - a.X, a.Height),
                        new Rectangle(r.Right, a.Y, a.Right - r.Right, a.Height)
                    };
                    #endregion
                }
                else
                {
                    #region MyRegion
                    if (r.Right == a.Right)
                    {
                        return new Rectangle[]
                        {
                            new Rectangle(a.X, a.Y, a.Width, r.Y - a.Y),
                            new Rectangle(a.X, r.Y, r.X - a.X, r.Height),
                            new Rectangle(a.X, r.Bottom, a.Width, a.Bottom - r.Bottom)
                        };
                    }
                    return new Rectangle[]
                    {
                        new Rectangle(a.X, a.Y, r.X - a.X, r.Height),
                        Rectangle.FromLTRB(r.Right, a.Y, a.Right, r.Bottom),
                        Rectangle.FromLTRB(a.X, r.Bottom, a.Right, a.Bottom)
                    };
                    #endregion
                }
            }
            else if (r.Right == a.Right)
            {
                #region MyRegion
                if (a.Bottom == r.Bottom)
                {
                    return new Rectangle[]
                    {
                        Rectangle.FromLTRB(a.X, a.Y, a.Right, r.Y),
                        Rectangle.FromLTRB(a.X, r.Y, r.X, r.Bottom)
                    };
                }
                return new Rectangle[]
                {
                    Rectangle.FromLTRB(a.X, a.Y, a.Right, r.Y),
                    Rectangle.FromLTRB(a.X, r.Y, r.X, r.Bottom),
                    Rectangle.FromLTRB(a.X, r.Bottom, a.Right, a.Bottom)
                };
                #endregion
            }
            else if (r.Bottom == a.Bottom)
            {
                #region MyRegion
                return new Rectangle[]
                {
                    Rectangle.FromLTRB(a.X, a.Y, a.Right, r.Y),
                    Rectangle.FromLTRB(a.X, r.Y, r.X, r.Bottom),
                    Rectangle.FromLTRB(r.Right, r.Y, a.Right, a.Bottom)
                };
                #endregion
            } 
            #endregion

            return new Rectangle[]
            {
                Rectangle.FromLTRB(a.X, a.Y, a.Right, r.Y),
                Rectangle.FromLTRB(a.X, r.Y, r.X, r.Bottom),
                Rectangle.FromLTRB(r.Right, r.Y, a.Right, r.Bottom),
                Rectangle.FromLTRB(a.X, r.Bottom, a.Right, a.Bottom)
            };
        }

        public void Compose(EPubWriter writer)
        {
            int mc;
            List<TableItem>[] all = Analyze(out mc);
            if (all.Length < 1)
                return;
            foreach (List<TableItem> item in all)
            {
                writer.BeginRow();

                for (int i = 0; i < item.Count; i++)
                {
                    TableItem ti = item[i];

                    ti.RowSpan = 0; //???? Should Calculate
                    ti.ColSpan = 0; //???? Should Calculate

                    writer.Render(ti.Item, ti.RowSpan, ti.ColSpan);
                }

                writer.EndRow();
            }
        }
    }

What I Need

    public void Compose(EPubWriter writer)
    {
        int mc;
        // Analyze: Calculates item positions, creates
        // empty TableItem s if needs, sorts by y ASC,x ASC
        // Returns array of rows (TR) what contains cells (TD)
        List<TableItem>[] all = Analyze(out mc);
        if (all.Length < 1)
            return;
        foreach (List<TableItem> item in all)
        {
            writer.BeginRow();

            for (int i = 0; i < item.Count; i++)
            {
                TableItem ti = item[i];

                ti.RowSpan = 0; //???? Should Calculate
                ti.ColSpan = 0; //???? Should Calculate

                writer.Render(ti.Item, ti.RowSpan, ti.ColSpan);
            }

            writer.EndRow();
        }
    }

                ti.RowSpan = 0; //???? Should Calculate
                ti.ColSpan = 0; //???? Should Calculate

Thank you..

OK.. I could not find any good solution for table layout.. So i changed the layout style by divs..

I used empty divs for all empty areas and gave them fixed width and height as much as empty area required.. and set their float property to left.

finally i put all divs, spans and images into a container div which width property setted to page width..