Odd-shaped stories are often used in newspapers to utilize all available space on a page--often because ads have cluttered the page. Odd-shaped articles cause uneven wraps of text and tend to make the design more complex. Therefore, all articles are formatted into a rectangular shape.
In order to fit the article into a grid, the height of an article is adjusted at the end of the formatting process. By adjusting the position of the headline, tags and paragraphs, the formatter fills in extra white space, if any.
The output of the formatter is the same as the input: a "datfile". The fact that datfiles handle the same information in different forms is somewhat intriguing. The icon pixmap is stored as a subdatfile of the rendered article.
The formatter always outputs the whole article. If the front page layout scheme is changed to sometimes display partial articles, the formatter will have to be changed.
Since the formatting process never breaks a paragraph, the same algorithm can be used to equalize the columns First, let us generalize the problem into building blocks and towers. Given a set of blocks with different heights, their relative positions (we don't want the words to change position), and the number of allowed towers, how do we stack the blocks to minimize the height of the highest tower, i.e. optimize the blocks with regard to white space? The following pseudo-code outlines the blocktimize algorithm I settled upon: { tower_id pre_lo, pre_hi;8.9 Blocktimize Algorithm
The blocktimize algorithm was initially developed to assist in laying out the headline. Multiline headlines should be equalized with regard to length to balance. The problem might seem trivial, but I have found no simple algorithm that guarantees the optimal solution.
tower_height pre_height, post_height;
boolean finished;
build_one_tall_tower_containing_all_blocks();
finished = false;
do
{
pre_lo=lowest_tower();
pre_hi=highest_tower();
pre_height=height_of_tower(pre_hi);
propagate_block_from_to_tower(pre_hi,pre_lo);
post_height=height_of_heighest_tower();
if (post_height > pre_height) /* no improvement */
{
propagate_block_from_to_tower(pre_lo,pre_hi);
finished = true;
}
} while(not finished);
}
The algorithm is visualized in figure 21.
When using blocktimize to split headlines, the word lengths become blocks and the lines in the headline becomes towers. If blocktimize is used to balance columns, column heights are blocks, while the columns are towers.
When formatting an article, blocktimize is called repeatedly with different number of towers, i.e. lines or columns, to find the optimal solution.
* It allows the main process to devote it's attention to events from the user and the window system. * The soft fonts can be loaded and processed by the main process when it starts up--each formatting process will automatically be given a copy. * The formatting process is quite complex in terms of memory allocation--by letting it die after finishing formatting the article, memory leaks can be ignored. This simplifies programming and testing, but is not acceptable as a long term solution. * To conserve CPU cycles and virtual memory, only one formatting process run at a time. When the formatting process is finished, a signal is sent to the parent process8.10 Implementation
The Electronic Broadsheet is an interactive system, while the formatting process is one that can run off-line. To keep all parts of the system on one machine while preserving interactivity, a formatting process is forked
off the main process for each article that is formatted. This scheme has several advantages:
, and the parent process reads the output file that now contains an image of the formatted article.
Generated with CERN WebMaker
