How to output multicolumn html without "widows"?

Question

I need to output to HTML a list of categorized links in exactly three columns of text. They must be displayed similar to columns in a newspaper or magazine. So, for example, if there are 20 lines total the first and second columns would contain 7 lines and the last column would contain 6. The list must be dynamic; it will be regularly changed.

The tricky part is that the links are categorized with a title and this title cannot be a "widow". If you have a page layout background you'll know that this means the titles cannot be displayed at the bottom of the column -- they must have at least one link underneath them, otherwise they should bump to the next column (I know, technically it should be two lines if I were actually doing page layout, but in this case one is acceptable). I'm having a difficult time figuring out how to get this done.

Here's an example of what I mean:

Shopping     Link 3      Link1
Link 1       Link 4      Link2
Link 2                   Link 3
Link 3       Cars
             Link 1      Music
Games        Link 2      Link 1
Link 1              
Link 2       News

As you can see, the "News" title is at the bottom of the middle column, and so is a "widow". This is unacceptable. I could bump it to the next column, but that would create an unnecessarily large amount of white space at the bottom of the second column. Instead, the entire list needs to be re-balanced.

I'm wondering if anyone has any tips for how to accomplish this, or perhaps source code or a plug in. Python is preferable, but any language is fine. I'm just trying to get the general concept down.

Answer 1

The general gist is to build a master list of all "flowable" items (including categories), then go through the list, adjusting rows per column as needed such that no categories remain widowed (or whatever other conditions you may have.)

Module Module1

    Dim Categories As New Dictionary(Of String, List(Of String))

    Sub Main()

        Const Columns As Integer = 3

        ' create the category items
        Dim ShoppingList As New List(Of String)
        Dim GamesList As New List(Of String)
        Dim CarsList As New List(Of String)
        Dim NewsList As New List(Of String)
        Dim MusicList As New List(Of String)

        ShoppingList.Add("Link1")
        ShoppingList.Add("Link2")
        ShoppingList.Add("Link3")

        GamesList.Add("Link1")
        GamesList.Add("Link2")
        GamesList.Add("Link3")
        GamesList.Add("Link4")

        CarsList.Add("Link1")
        CarsList.Add("Link2")

        NewsList.Add("Link1")
        NewsList.Add("Link2")
        NewsList.Add("Link3")

        MusicList.Add("Link1")

        ' create the categories
        Categories.Add("Shopping", ShoppingList)
        Categories.Add("Games", GamesList)
        Categories.Add("Cars", CarsList)
        Categories.Add("News", NewsList)
        Categories.Add("Music", MusicList)

        ' count each category and its items
        Dim TotalRows As Integer = Categories.Count
        For Each kvp As KeyValuePair(Of String, List(Of String)) In Categories
            TotalRows += kvp.Value.Count
        Next

        ' add a space between each category
        TotalRows += (Categories.Count - 1)

        ' determine the number of rows per column
        Dim RowsPerColumn As Integer = Int(TotalRows / Columns) + If((TotalRows Mod Columns) > 0, 1, 0)

        ' build a master list
        Dim master As New List(Of String)
        For Each kvp As KeyValuePair(Of String, List(Of String)) In Categories
            master.Add(kvp.Key)
            For Each item As String In kvp.Value
                master.Add(item)
            Next
            master.Add(" ")
        Next

        ' remove the last invalid blank item
        master.RemoveAt(master.Count - 1)

        ' ensure that the RowsPerColumn'th-item in the list is not a category
        Dim adjusted As Boolean
        Do
            adjusted = False
            For i As Integer = 1 To master.Count - 1 Step RowsPerColumn - 1
                If Categories.Keys.Contains(master(i)) Then
                    RowsPerColumn += 1 ' adjust rows per column (could go up or down)
                    adjusted = True
                End If
            Next
        Loop While adjusted

        ' output resulting table
        Using sw As New IO.StreamWriter("test.htm")
            sw.WriteLine("<html>")
            sw.WriteLine("<body>")
            sw.WriteLine("<table cellspacing=""0"" cellpadding=""3"" border=""1"">")
            For j As Integer = 0 To RowsPerColumn - 1
                sw.WriteLine("<tr>")
                Dim columnCount As Integer = 0 ' columns written
                For i As Integer = j To master.Count - 1 Step RowsPerColumn
                    sw.WriteLine("<td>" & master(i) & "</td>")
                    columnCount += 1
                Next
                ' if the number of columns actually written was less than Columns constant
                If columnCount < Columns Then
                    For c As Integer = 0 To Columns - columnCount - 1
                        sw.WriteLine("<td>&nbsp;</td>")
                    Next
                End If
                sw.WriteLine("</tr>")
            Next
            sw.WriteLine("</table>")
            sw.WriteLine("</body>")
            sw.WriteLine("</html>")
        End Using

    End Sub

End Module