A first attempt to wrap paragraphs

In the last chapter, we justified text, but only one line at the time. In this chapter, we will try to wrap an entire paragraph to create the lines. Normally, this kind algorithms do not run in PostScript, but we can program it in PostScript.

There are many sophisticated algorithms for this, including the Knuth-Plass line-breaking algorithm that optimize the spaces playing with the knowledge of all lines and using also hyphenation.

We keep it very simple. Our algorithm works like a typewriter. We write each word after another and when we see that the next word does not fit into the line width, we go to the next line.

First, we need some operators. neg negates a number (-1 mul), roll allows to access deeper elements of the stack by rolling the top elements of the stack and newpath explicitly starts a new path.

Javascript Editor

operators.neg = function(context) {
    const [x] = context.pop("number");
    if (!x) return context;
    context.stack.push(new rpnNumber(-x.value));
    return context;
};
unitTest("2 neg", "-2")
unitTest("-2 neg", "2")
unitTest("0 neg", "0")

operators.roll = function(context) {
    const [roll, n] = context.pop("number", "number");
    if (context.stack.length < n.value) {
        return context.error("stackunderflow"); 
    }
    const thisstack = context.stack.slice(context.stack.length - n.value);
    const rootstack = context.stack.slice(0,context.stack.length-n.value);
 
    if (roll.value > 0) {
        for (var i = 0; i < roll.value; i++) {
     thisstack.unshift(thisstack.pop());
 }
    }
    if (roll.value < 0) {
        for (var i = 0; i< -roll.value; i++) {
            thisstack.push(thisstack.shift());
 }
    }
 
    for(var i = 0; i < n.value; i++) context.stack.pop();
    for(var i = 0; i < n.value; i++) context.stack.push(thisstack.shift());
    return context;
};
unitTest("1 2 3 4 3 1 roll", "1 4 2 3")
unitTest("1 2 3 4 3 -1 roll", "1 3 4 2")

operators.newpath = function(context) {
    context.path = [];
    return context;
};

This is quite a program, therefore we try also to document it with comments. A well structured PostScript program separates the definition of operators (the prologue) from the actual content.

For each operator, we write a comment line that describes the stack input on the left and the stack output of the left.

We need to define max because there is actually no PostScript operator for this. This is rather easy. We copy the 2 top elements of the stack, compare and then keep one element and pop the other.

We already have defined countblanks and justifyshow. They are straightforward. We compare the actual width with the target width, divide the difference by the number of blanks. Here we need max, because we do not want to divide by zero if there are no blanks.

showjustifyblock at the end is also straightforward, combining wordwrap with justifyshow.

The main piece is wraptext. We search the next word and calculate the stringwidth and add it to the linewidth. If it is smaller than the maximal width, we add spacewidth and count also the characters. At the end, we push on the stack the text after (post), the target width and the selected text. Wraptext can then be reused to produce one line at a time.

Javascript Editor

postScriptEditor(`% prologue
% support procedures
% n1 n2 max result
/max { 2 copy gt { pop } { exch pop } ifelse } def

% text countblanks n
/countblanks { 10 dict begin /c 0 def { ( ) search { /c c 1 add def pop pop } { pop c end exit } ifelse } loop } def

% text width justifyshow -
/justifyshow { exch dup stringwidth pop 3 -1 roll exch sub exch dup countblanks 1 max 3 -1 roll exch div 0 32 4 -1 roll widthshow } def

% text width wraptext post width pre 
/wraptext { 10 dict begin /maxwidth exch def /text exch def
/linewidth 0 def
/linelength 0 def
/spacewidth 0 0 moveto ( ) stringwidth pop def
text
{
% search leaves the post on the stack, so we assign it to currenttext
dup /currenttext exch def
( ) search { 
% add word width and check if linewidth is still not bigger than max
dup stringwidth pop linewidth add dup maxwidth le 
% add space and count characters
{ spacewidth add /linewidth exch def 
length 1 add linelength add /linelength exch def
pop } 
% clear stack
{ pop pop pop pop exit } ifelse
} 
% no space found we are at the last word
{ pop text length /linelength exch def /currenttext () def exit } ifelse } loop
% remove trailing space character if not empty text
currenttext length { /linelength linelength 1 sub def } if 
% set text if only one word
linelength 0 le { /linelength currenttext length def } if 
% output 
currenttext maxwidth text 0 linelength getinterval end
} def

% text x y w l showjustifyblock y
/showjustifyblock { 
/l exch def
/w exch def
/y exch def
/x exch def w
{ wraptext 3 -1 roll dup 4 1 roll length { newpath x y moveto w justifyshow y l sub /y exch def } { x y moveto show pop pop exit } ifelse } loop y } def

% parameter
/bodystart 300 def
/linespace 33 def
/LM 20 def 
/RM 570 def
(CMUSerif-Roman) run
/CMUSerif-Roman findfont 33 scalefont setfont

% main
/linewidth RM LM sub def
/nextline bodystart def
(Acme Widgets was founded in 1952 by Dippy and Daffy Acme to produce high technology widgets for the growing aerospace market. Acme was quickly recognized as being the best widget works in the country. Continued investment in new technology and manufacturing methods has kept Acme Widgets in the forefront of this industry.)
LM nextline linewidth linespace showjustifyblock pop

showpage
`);

The result works but it is not very pretty for short lines. You see the spaces. We will not start to hyphenate but try a second algorithm to wrap which is still rather simple. Above we only enlarged the space. But we also have the option to make the space smaller. Let's permit the space to shrink by 50% also.

So when it is too big, we check a second time if the text matches with the word and half the space width, we pass.

Javascript Editor

postScriptEditor(`
% prologue
% support procedures
% n1 n2 max result
/max { 2 copy gt { pop } { exch pop } ifelse } def

% text countblanks n
/countblanks { 10 dict begin /c 0 def { ( ) search { /c c 1 add def pop pop } { pop c end exit } ifelse } loop } def

% text width justifyshow -
/justifyshow { exch dup stringwidth pop 3 -1 roll exch sub exch dup countblanks 1 max 3 -1 roll exch div 0 32 4 -1 roll widthshow } def

% text width wraptext post width pre 
/wraptext { 10 dict begin /maxwidth exch def /text exch def
/linewidth 0 def
/linelength 0 def
/spaces 0 def
/spacewidth 0 0 moveto ( ) stringwidth pop def
text
{
% search leaves the post on the stack, so we assign it to currenttext
dup /currenttext exch def
( ) search { 
% add word width and check if linewidth is still not bigger than max
dup stringwidth pop linewidth add dup spaces add maxwidth le 
% add space and count characters
{ /linewidth exch def 
length 1 add linelength add /linelength exch def
/spaces spaces spacewidth add def
pop } 
% check if half space ok
{ 
spaces 2 div add maxwidth le
{ length 1 add linelength add /linelength exch def exit}
{ pop pop pop exit }
ifelse

} ifelse
} 
% no space found we are at the last word
{ pop text length /linelength exch def /currenttext () def exit } ifelse } loop
% remove trailing space character if not empty text
currenttext length { /linelength linelength 1 sub def } if 
% set text if only one word
linelength 0 le { /linelength currenttext length def } if 
% output 
currenttext maxwidth text 0 linelength getinterval end
} def

% parameter
/bodystart 300 def
/linespace 33 def
/LM 20 def 
/RM 570 def
(CMUSerif-Roman) run
/CMUSerif-Roman findfont 33 scalefont setfont

showpage
`);

Well, the difference is subtle. The first line includes "by", but the big spaces in the lower lines are inevitable with the long words, when you cannot hyphenate them.

The current code base is now 2021 lines. I made some changes to the console, cutting long texts and two reference count errors. ps20240828.js

My Journey to PostScript