Utility Corner: Word Wrap

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 22

Utility Corner: Word Wrap¶

(The purpose of this column is to make you more productive by introducing you to utility functions. Think of utility functions as APL functions that have names instead of symbols. By expanding your function vocabulary, you’ll be able to write APL code that’s more concise, more efficient, and more readable.)

In the last Limbering Up column (re-printed in Vector 20:3), you were asked to define a dyadic utility function WRAP that does word wrap. Its right argument is the character vector to be wrapped. Its left argument is the width within which the text is to be wrapped. Its result is a character vector with new-line (carriage return) characters inserted in such a way that the text wraps appropriately when displayed. For example:

      17 WRAP 'This is a sample. The last nonblank character in
each line fits within the specified width.'

This is a sample.
The last nonblank
character in each
line fits within
the specified
width.

The piece of text is broken into subsets, without breaking any words, so that each subset is no longer than the specified width, in this case 17.

The result of WRAP has the same length as the right argument. The newline character (⎕TCNL or ⎕TC[2]) replaces the last blank after the last word in each line.

If the right argument already contains newline characters, they are not ignored or removed. Each one begins a new line. In a sense, existing newlines are “paragraph” delimiters.

Each group of contiguous nonblank characters is considered a word. The aim is to wrap the text without breaking any words. However, if any “word” is longer than the specified width, WRAP inserts one or more newline characters within it to break it into pieces whose length equals the width. If this is the case, the result will naturally be longer than the right argument.

Your primary objective was to write a function that worked. You were offered extra credit (a pat on the back) if your function was efficient, clever, simple, elegant, or could leap tall buildings in a single bound.

In the “leap tall buildings in a single bound category” was the following entry:

     ∇ R←WID WRAP CVEC;C;I;J;M;P;TCNL;⎕IO
[1]   ⍝ Wrap text CVEC into lines of width
[2]   ⍝ WID or less by inserting newline
[3]   ⍝ Characters.
[4]    ⎕IO←1 ⍝ Origin 1
[5]    TCNL←⎕TCNL ⍝ APL*PLUS newline
[6]   ⍝ TCNL←⎕TC[2] ⍝ APL2
[7]   ⍝ Algorithm needs start/end blanks:
[8]    CVEC←' ',CVEC,' '
[9]   ⍝ Indices of blanks
[10]   J←(CVEC=' ')/⍳⍴CVEC
[11]  ⍝ 1s mark blanks past the cutoff:
[12]   P←(J+WID+1)∘.<J
[13]  ⍝ Mark last blank that fits on line
[14]   M←P<1⌽P
[15]   I←(⍴M)⍴1,(1↓⍴M)⍴0 ⍝ Identity matrix
[16]   C←⌹I-M ⍝ Transitive closure of M
[17]  ⍝ Insert the line breaks:
[18]   CVEC[C[1;]/J]←TCNL
[19]  ⍝ Drop the blanks we added
[20]   R←1↓¯1↓CVEC
     ∇

Since the algorithm employed in the WRAP function is intuitively obvious (especially line [16]), we won’t waste space or time explaining it.

Well… maybe we’ll say a few words. This algorithm was originally presented in the mid-1970s by Bob Smith of Scientific Time Sharing Corporation in response to a challenge like this one in the Sharp APL newsletter. The solution is non-looping by virtue of its use of ⌹ to compute the transitive closure of a Boolean matrix.

The algorithm was resurrected for this Limbering Up exercise by Jim Weigang and Bob Smith. Bob Smith even offered a page of explanation, which appeared to be in English. Copies are available for the masochistic. Write to us.

Rex Swain recognized that the Bob Smith solution, as expressed above, does not solve the Limbering Up task. Specifically, it does not handle multiple contiguous blanks or words that are longer than the specified width. So he fixed it, without sacrificing its non-looping nature.

     ∇ R←WID WRAP CVEC;A;B;C;D;E;I;L;P;TCNL;Z;⎕IO
[1]   ⍝ Wrap text CVEC into lines of width
[2]   ⍝ WID or less by inserting newline
[3]   ⍝ characters.
[4]    ⎕IO←1 ⍝ Origin 1
[5]    TCNL←⎕TCNL ⍝ APL*PLUS newline
[6]   ⍝ TCNL←⎕TC[2] ⍝ APL2
[7]    B←CVEC=' ' ⍝ Flag blanks
[8]   ⍝ Flag all but the last letter in
[9]   ⍝ each word:
[10]   A←B⍱1↓B,1
[11]  ⍝ Partition words with more than one
[12]  ⍝ letter
[13]   P←A/¯1↓1,B
[14]  ⍝ Point to the left of those "long"
[15]  ⍝ words
[16]   C←¯1+P/⍳⍴P
[17]  ⍝ Lengths of those words:
[18]   C←C-¯1↓0,C
[19]  ⍝ Treat breakpoints in long words as
[20]  ⍝ blanks
[21]   B←B∨A\0=WID|+\1-P\C
[22]  ⍝ Right-hand blanks in sequences of
[23]  ⍝ blanks:
[24]   Z←B>1↓B,0
[25]  ⍝ Left-hand blanks in sequences of
[26]  ⍝ blanks:
[27]   L←B>¯1↓0,B
[28]  ⍝ For each A, the corresponding
[29]  ⍝ value in C is the index in A of
[30]  ⍝ the right-most blank within WID+1
[31]  ⍝ characters
[32]   C←+/((WID+1)+0,Z/⍳⍴Z)∘.≥0,(L/⍳⍴L),1+⍴L
[33]  ⍝ Ye olde identity matrix:
[34]   I←(2⍴⍴C)⍴(1+⍴C)↑1
[35]  ⍝ Key is transitive closure:
[36]   A←(Z\1=1↓((⍴C)↑1)⌹I-(⍳⍴C)∘.=C)/⍳⍴CVEC
[37]  ⍝ Now A points to blanks that should
[38]  ⍝ be replaced with newlines, except
[39]  ⍝ in too-long words, where we want
[40]  ⍝ to insert the newlines after the
[41]  ⍝ character:
[42]   I←CVEC[A]≠' ' ⍝ Need to insert?
[43]  ⍝ Where NLs go (after expansion)
[44]   A←A++\I
[45]  ⍝ Expansion vector
[46]   E←((⍴CVEC)++/I)⍴1
[47]  ⍝ Need extras here for inserted NLs:
[48]   E[I/A]←0
[49]   R←E\CVEC ⍝ Do the expansion
[50]  ⍝ Replace and/or insert NLs
[51]   R[A]←TCNL
     ∇

Unfortunately, this function still does not properly handle the existence of embedded newlines. But hey! Who cares? These functions can’t be used for practical problems anyhow. They’re too dang slow. The first function can be likened to driving in a thumb tack with a nuclear warhead. The second function embellishes upon that by requiring that a lead vest be worn during the process.

Jim Weigang, recognizing that a practical solution was also needed, offered one:

     ∇ R←WID WRAP CVEC;B;C;E;I;J;N;S;T;TCNL;⎕IO
[1]   ⍝ Wrap text CVEC into lines of width
[2]   ⍝ WID or less by inserting newline
[3]   ⍝ characters.
[4]    ⎕IO←1 ⍝ Origin 1
[5]    TCNL←⎕TCNL ⍝ APL*PLUS newline
[6]   ⍝ TCNL←⎕TC[2] ⍝ APL2
[7]   ⍝ Simplify edge conditions
[8]    CVEC←' ',CVEC,' '
[9]   ⍝ Mark blanks and newlines:
[10]   B←CVEC∊' ',TCNL
[11]  ⍝ Last of each group of blanks
[12]   C←(B>1↓B,0)/⍳⍴B
[13]  ⍝ Nonblank before each grp of blnks:
[14]   E←¯1+(B>¯1↓0,B)/⍳⍴B
[15]  ⍝ Indices of newlines:
[16]   N←(CVEC=TCNL)/⍳⍴CVEC
[17]   I←⍳0 ⍝ Where to insert add'l TCNL's
[18]  ⍝ Index of character before start of
[19]  ⍝ current line:
[20]   S←1
[21]  ⍝ Loop for each line. Find word that
[22]  ⍝ Extends past line end, & back up:
[23]  L1:J←¯1+(E>S+WID)⍳1
[24]   →(J=⍴E)/L4 ⍝ Quit if at end
[25]  ⍝ Newlines within this line:
[26]   →(0=⍴T←((S<N)∧N≤C[J])/N)/L2
[27]  ⍝ Use last one as new base; repeat:
[28]   S←¯1↑T
[29]   →L1
[30]  L2:T←S ⍝ Save old base
[31]   S←C[J] ⍝ New base (break point)
[32]   →(S>T)/L3 ⍝ Branch if okay
[33]  ⍝ Else word is too long; remember to
[34]  ⍝ insert a newline past S:
[35]   I←I,S←T+WID
[36]   →L1
[37]  ⍝ Else, replace blank w/ newline:
[38]  L3:CVEC[S]←TCNL
[39]   →L1
[40]  ⍝ Branch unless some newlines need
[41]  ⍝ inserting (long words)
[42]  L4:→(0=⍴I)/L5
[43]   E←((⍴CVEC)+⍴I)⍴1 ⍝ Form expand mask
[44]   E[I←I+⍳⍴I]←0 ⍝ ...where newlines go
[45]   CVEC←E\CVEC ⍝ Insert spaces
[46]   CVEC[I]←TCNL ⍝ Put in newlines
[47]  L5:R←1↓¯1↓CVEC ⍝ Drop blanks added
     ∇

A looper. Jim’s approach is to find the indices of the starts (C) and ends (E) of words and of the embedded newlines (N). He then loops, doing one line at a time.

On line [23], he looks ahead WID characters to find the end of the current line. If there’s a newline within the next WID characters, he starts from that newline to look ahead again (line [28]). If there are no newlines, he finds the end of the last word and replaces the (last) blank after that word with a newline character (line [38]). If there is no last word because the line is just one long word, he makes a note to insert a newline character in the middle of the word (lines [35,42-46]) and proceeds to the next line.

Bill Chelew also offered a looping solution:

     ∇ R←WID WRAP CVEC;N;TCNL;V;⎕IO
[1]   ⍝ Wrap text CVEC into lines of width
[2]   ⍝ WID or less by inserting newline
[3]   ⍝ characters.
[4]    ⎕IO←1 ⍝ Origin 1
[5]    TCNL←⎕TCNL ⍝ APL*PLUS newline
[6]   ⍝ TCNL←⎕TC[2] ⍝ APL2
[7]    R←''
[8]   ⍝ Exit if nothing left:
[9]   LOOP:→(N←⍴CVEC)↓0
[10]  ⍝ Grab up to WID+1 chars:
[11]   V←(N←N⌊WID+1)↑CVEC
[12]  ⍝ Done if no more than WID:
[13]   →(N>WID)/L1
[14]   R←R,V
[15]   →0
[16]  ⍝ Any newlines in this string?
[17]  L1:→(TCNL∊V)↓L2
[18]  ⍝ If so, keep up to it and go back:
[19]   R←R,(N←V⍳TCNL)↑V
[20]   CVEC←N↓CVEC
[21]   →LOOP
[22]  ⍝ Branch if last char is blank:
[23]  L2:→(' '=¯1↑V)/L4
[24]  ⍝ Index of last blank in V
[25]   N←(WID+2)-(⌽V)⍳' '
[26]   →(N=0)/L3 ⍝ Branch if no blanks
[27]   V[N]←TCNL
[28]   R←R,N↑V
[29]   CVEC←N↓CVEC
[30]   →LOOP
[31]  ⍝ Use full WID if no blanks
[32]  L3:R←R,(WID↑V),TCNL
[33]   CVEC←WID↓CVEC
[34]   →LOOP
[35]  ⍝ Branch if any nonblanks
[36]  L4:→(∨/V≠' ')/L5
[37]   R←R,TCNL ⍝ Newline if all blanks
[38]   →L6
[39]  L5:V[WID+1]←TCNL
[40]   R←R,V
[41]   CVEC←(WID+1)↓CVEC
[42]  ⍝ Go back if no leading blanks
[43]   →(' '≠1↑CVEC)/LOOP
[44]  ⍝ Delete leading blanks
[45]  L6:N←(CVEC≠' ')⍳1
[46]   CVEC←(N-1)↓CVEC
[47]   →LOOP
     ∇

Bill’s approach was to build the result by catenating to it one line at a time. At each iteration, he looks ahead WID+1 characters. If there aren’t that many left, he’s done (lines [12-15]). If the line of characters contains a newline, he grabs all the characters up to and including the newline, catenates them to the result, and goes back for the next line ([16-21]).

If the line contains no newlines, he finds the last blank before the last nonblank and inserts a newline character there ([27-30]), catenating those characters to the result. If there are no blanks in the line, he breaks the long word after WID characters, inserting a newline ([31-34]) and catenating it to the result. If the line is all blank, he catenates a newline to the result and discards all subsequent blanks ([36-38] and [44-47]).

If the line ends on a word that is followed by multiple blanks, and if those blanks extend beyond the specified width, the first WID characters are catenated to the result along with a newline, and the remaining blanks are discarded ([39-47]).

These last two functions seem to handle all practical examples you would be likely to throw at them. To find out which was faster, we timed them (as well as the first two functions, for the chuckles).

Here’s what we found:

1 = Nonlooping ⌹ version
2 = Doctored up ⌹ version
3 = Loop, inserting newlines
4 = Loop, catenating to result

For each size of problem (200, 2000, 20000 elements), the timings were converted to multiples of the fastest algorithm. For example, the fastest algorithm for a 200-element character vector was algorithm 4 when the character vector contained occasional newline characters. Algorithm 1 took 40.8 times longer to run.

For a 2000-element character vector, algorithm 4 was faster when the vector did not contain newline characters than when it did.

The fastest algorithm for the 2000-element vector took 6.59 times longer to run than the fastest algorithm for the 200-element vector. The fastest algorithm for the 20000-element vector took 111 times longer to run than the fastest algorithm for the 200-element vector.

Limbering Up: Permutations and Anagrams¶

(The purpose of this column is to work some flab off your APL midsection. Like muscles, your APL skills can atrophy if not exercised with adequate frequency and variety. This column presents a task for you to perform. Set aside a few minutes from your busy schedule and work the task. Mail in your solution and stay tuned for the results.)

In the 1992 Quarter 2 issue of the Zark APL Tutor News, a highly efficient (though obscure) function for constructing combinations was presented:

     ∇ R←M COMBIN N;D;E;F;G;P
[1]   ⍝ Returns a matrix of every possible
[2]   ⍝ combination of M elements from the
[3]   ⍝ vector ⍳N. That is, returns a ma-
[4]   ⍝ trix with M!N rows and N columns.
[5]   ⍝
[6]    E←(⍳P←N-R←M-1)-⎕IO
[7]    D←R+⍳P
[8]    R←(P,1)⍴D
[9]    P←P⍴1
[10]  L1:→(⎕IO>1↑D←D-1)⍴0
[11]   P←+\P
[12]   G←+\¯1↓0,F←⌽P
[13]   E←F/E-G
[14]   R←(F/D),R[E+⍳⍴E;]
[15]   E←G
[16]   →L1
     ∇

      3 COMBIN 5
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Your task is to write a monadic function PERMUTE, whose argument is a positive integer N and whose result is an N-column, (!N)-row matrix, in which each row is a different permutation of ⍳N.

      PERMUTE 3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Try to make the function as efficient as possible. In case you don’t find this exercise adequately limbering, your second task is to write a monadic function ANAGRAM, whose argument is a character vector, and whose result is a character matrix in which each row is a different arrangement of the argument’s letters. (ANAGRAM calls PERMUTE.)

      ANAGRAM 'SMSI'
IMSS
ISMS
ISSM
MISS
MSIS
MSSI
SIMS
SISM
SMIS
SMSI
SSIM
SSMI

Send your solution to:

Vector Production
Brook House
Gilling East
York YO62 4JJ
UK email apl385@compuserve.com

The notable functions and their authors’ names will be printed in the next issue of Vector. Good luck and happy limbering.

Reprinted with kind permission from Zark APL Tutor News, a quarterly publication of Zark Incorporated, 23 Ketchbrook Lane, Ellington, CT06029, USA