Algorithm to layout a table of contents on a fixed-sized page (multi-column)

Question

I'm writing a table of contents to a standard 8.5in x 11in page. Orientation (landscape versus portrait) is a variable. I can write my TOC to an inner region when x-inch margins are applied to the page (where x is variable).

The raw data is a table with two columns: Topic and Page (i.e. { "Animals" , 1 } , { "Big Plants" , 2 } , { "Small Plants" , 2 } ). This is not a nested TOC - there are no "subtopics". All topics are at the same level of importance and font size is fixed for all text.

I want to allow for 1 or more columns of TOC per page and I'm allowing multiple pages of TOC if needed. The layout is completely dependent on text in the Topic column. If the topics are short, you can imagine putting 2 columns in portrait orientation, or 3 columns in landscape orentation. If there are long topic names, then maybe only 1 column will fit (if very long, then its ok to use multiple lines for a topic). If there are many topics, then I might spill over to multiple pages. The goal is to put as much TOC info as possible on each page.

I realize this is a hard problem. There's a number of details that I haven't explored (i.e. do all pages have to have the same number of columns?). I'm just looking for a start...something simple enough to implement in an hour or two that does the job. Anything semi-intelligent is better than forcing a 1-column TOC with character counts to determine how many rows to place on a page.

Answer 1

First you need a few variables:

• Line_hight (inches per TOC line)
• Max_TOC_width (inches of the longest TOC name)
• Max_pagenum_width (inches width of the largest page number when printed)
• Left, Right, Top, Bottom _border (inches of the border around the page)

Then it's pretty easy to calculated.

Lines_Per_Page = Floor( (Page_Height - Top_Border - Bottom_Border) / Line_Height )

Columns_Per_Page = Floor( (Page_Width - Left_Border - Right_Border) / (Max_TOC_Width + Max_PageNum_Width) )

Total_TOC_Per_Page = Lines_Per_Page * Columns_Per_Page

FYI: Floor( ) means round down to the nearest integer. Floor(5.9) = 5, Floor(0.1) = 0

Answer 2

Assuming you want all columns to be the same width:

1. Do one pass through the table finding the (printed) width of the longest TOC entry.
2. Divide the page width minus margins and take the floor to figure out how many columns you can fit.
3. Divide the page height minus margins by the height of a line and take the floor to figure out how many lines per column.
4. Repeat steps 2 and 3 in the other page orientation (e.g., landscape).
5. Choose the one that gives the most slots (rows times columns).

The math is slightly more complicated, since you need to account for a "gutter" between the columns. This is easily accomplished by padding your widest value.