-- TexJust.mesa

-- last written by Doug Wyatt, December 18, 1979  11:03 PM

-- the TEX justification machinery

DIRECTORY
	TexDebugDefs: FROM "TexDebugDefs",
	TexDefs: FROM "TexDefs",
	TexErrorDefs: FROM "TexErrorDefs",
	TexFontDefs: FROM "TexFontDefs",
	TexGlueDefs: FROM "TexGlueDefs",
	TexJustifyDefs: FROM "TexJustifyDefs",
	TexMemDefs: FROM "TexMemDefs",
	TexNodeDefs: FROM "TexNodeDefs",
	TexPackDefs: FROM "TexPackDefs",
	TexTableDefs: FROM "TexTableDefs",
	InlineDefs: FROM "InlineDefs";

TexJust: PROGRAM
IMPORTS TexDebugDefs,TexErrorDefs,TexFontDefs,TexGlueDefs,TexJustifyDefs,
	TexMemDefs,TexNodeDefs,TexPackDefs,TexTableDefs,InlineDefs
EXPORTS TexJustifyDefs =
BEGIN OPEN TexGlueDefs,TexNodeDefs,TexDefs,TexJustifyDefs;

BreakNode: TYPE = RECORD
	[
	link: BreakPtr, -- points to prev break, sorted by target
	nlines: CARDINAL, -- number of lines so far, up to this break
	width: BigDimn, -- accumulated width up to this break
	flex: FlexSums, -- accumulated stretch/shrink up to this break
	node: NodePtr, -- points to place in hlist after which break occurs
	next: BreakPtr, -- points to breaknode for best preceding break
	totbad: TotBad, -- accumulated sum of badness squares
	target: BigDimn -- best curwd for the next break after here
	];

-- N.B.: in this implementation, the interpretation of node differs
-- from that of curbrk in the Sail version. Here node points to the
-- last node to be INCLUDED in the current hlist. Another way to say
-- this is that the break occurs between prevp and p (when TryBreak
-- is called). In the Sail version, curbrk=p; in this version,
-- node=prevp and node.link=p.

BreakPtr: TYPE = POINTER TO BreakNode;

-- allocation for break nodes
jzone: TexMemDefs.ZonePtr←NIL;

JustInit: PROCEDURE =
	BEGIN
	jzone←TexMemDefs.CreateZone[init: 2, grow: 9];
	END;

AllocBreakNode: PROCEDURE RETURNS[p: BreakPtr] = INLINE
	BEGIN RETURN[TexMemDefs.Alloc[jzone,SIZE[BreakNode]]] END;

TotBad: TYPE = LONG INTEGER; -- sum of badness squares
maxTotBad: TotBad = LAST[LONG INTEGER]; -- largest LONG INTEGER
-- Note: TotBad is INTEGER instead of CARDINAL since the badness
-- computation sometimes SUBTRACTS penalty↑2 for a negative penalty

ShortDimn: PROCEDURE[dd: BigDimn] RETURNS[Dimn] = --INLINE--
	BEGIN
	-- ***** for debugging, perhaps this should test for overflow
	RETURN[InlineDefs.LowHalf[dd]];
	END;

DeltaFlex: PROCEDURE[a,b: FlexVecPtr] RETURNS[Flex] =
	BEGIN
	ord: FlexOrder;
	v: FlexVal;
	FOR ord DECREASING IN FlexOrder
		DO IF (v←a[ord]-b[ord])#0 THEN RETURN[[ord,v]] ENDLOOP;
	RETURN[zeroFlex];
	END;


ComputeTotBad: PROCEDURE[bad,pen: Penalty] RETURNS[TotBad] = --INLINE--
	BEGIN
	-- ***** test for bad<0?
	t,u: LONG INTEGER;
	epsilon: INTEGER=1; -- *****???*****
	IF pen>=0 THEN BEGIN t←bad+pen+epsilon; RETURN[t*t] END
	ELSE BEGIN t←bad+epsilon; u←pen; RETURN[t*t-u*u] END;
	END;

AddEliminatedNodes: PROCEDURE[p: NodePtr, q: BreakPtr] = --INLINE--
	BEGIN
	r: NodePtr←p;
	-- add width, str, shr from nodes to be eliminated between lines
	WHILE r#NIL
		DO
		WITH rr:r SELECT FROM
			glue =>
				BEGIN
				t: GluePtr←rr.g;
				q.width←q.width+t.space;
				SumFlex[t, @q.flex];
				END;
			penalty,disc => NULL;
			kern,space => q.width←q.width+rr.s;
			eject => IF r#p THEN EXIT;
			ENDCASE => EXIT;
		r←r.link;
		ENDLOOP;
	END;

Justification: PUBLIC PROCEDURE[list: NodeListPtr,
	LineWidth: LineWidthProc, NewLine: NewLineProc]
	RETURNS[lastwidth: Dimn] =
	BEGIN
	q, bestplace: BreakPtr←NIL;
	finalglue: GluePtr←NIL;
	first,widow,brokenline: BOOLEAN;
	inserts: NodeListPtr;
	b: BoxNodePtr←NIL;
	lines: CARDINAL;
	ragged: CARDINAL; -- raggedness
	justpar: Penalty; -- maximum penalty to be considered for a possible break
	penPen,hPen: Penalty;
	thresholdPenalty: Penalty=1000;
	topopen,botopen: BreakPtr←NIL;
	autobreaking: BOOLEAN; -- automatic line breaking not shut off by hyphnode
	curwd: BigDimn;
	curflex: FlexSums;
	p,prevp: NodePtr←NIL; -- current and preceding nodes in hlist
	TryBreak: PROCEDURE[w: BigDimn, pen: Penalty←0, eject: BOOLEAN←FALSE] =
		BEGIN
		-- decides if p might be a reasonable place to break, and updates
		-- the break node table. This procedure is called when p points
		-- to a permissible break in an hlist, corresponding to an additional
		-- penalty as specified. Parameter w is the current width to be used
		-- in badness calculations; it differs from curwd if an inserted
		-- hyphen would appear at the break. If this is a potentially useful
		-- break, a new break node is created. The value of botopen is
		-- adjusted to "close" break nodes that are no longer relevant.
		r: BreakPtr←topopen;
		prevr: BreakPtr←NIL;
		bestplace: BreakPtr←NIL;
		bestscore: TotBad←maxTotBad;
		delta: Dimn; -- difference between current target and w
		dir: FlexDir;
		flex: Flex;
		badness: Penalty; -- penalty for breaking at r

		-- Look at all open break nodes to see if there are any which lead to
		-- a badness<=justpar at the current position, and close break nodes
		-- using the fact that r.link.target<=r.target
			DO
			delta←ShortDimn[r.target-w];
			dir←IF delta<0 THEN shr ELSE str;
			flex←DeltaFlex[@curflex[dir], @r.flex[dir]];
			badness←GluePenalty[[dir: dir, order: flex.order,
				num: ABS[delta], den: flex.val]];
			IF badness=maxPenalty AND dir=shr THEN
				BEGIN -- can't shrink this much
				IF prevr#NIL THEN botopen←prevr
				ELSE -- a bad break was inevitable
					BEGIN
					bestplace←botopen←r; bestscore←0; -- any value is ok here
					END;
				EXIT; -- no more feasible breaks
				END;
			-- now badness is the stretch/shrink penalty at the attempted break
			BEGIN
			totbad: TotBad;
			IF badness>justpar AND NOT eject THEN GOTO NoGood;
			totbad←r.totbad+ComputeTotBad[badness,pen];
			IF eject AND bestplace=NIL AND totbad>bestscore THEN totbad←bestscore;
			-- additional penalty for two hyphens in a row, or in 2nd-last line
			IF r.node.link.type=disc
			 AND (p=NIL OR p.link=NIL OR p.type=disc) THEN totbad←totbad+penPen;
			IF totbad<=bestscore THEN
				BEGIN bestplace←r; bestscore←totbad END;
			EXITS NoGood => NULL END;
			IF r=botopen THEN EXIT;
			prevr←r; r←r.link;
			ENDLOOP;
		IF p=NIL AND bestplace=NIL THEN
			bestplace←topopen; -- make the best of a bad case
		IF bestplace#NIL THEN AddNewBreak[bestplace, bestscore];
		END;
	TryHyphenation: PROCEDURE = --INLINE--
		BEGIN
		prevq,q: NodePtr;
		w: Dimn←0;
		f: Font; -- the font of the first letter
		n: CARDINAL←0; -- n will be the number of letters passed
		prevq←p; q←p.link;
		IF q=NIL THEN RETURN;
		WITH qq:q SELECT FROM
			char => f←qq.c.font;
			ENDCASE => RETURN;
		WHILE (q←prevq.link)#NIL
			DO
			WITH qq:q SELECT FROM
				char => IF qq.c.font=f AND qq.c.char IN['a..'z]
					THEN BEGIN w←w+TexFontDefs.CharWd[qq.c]; n←n+1 END
					ELSE EXIT;
				kern => w←w+qq.s;
				ENDCASE => EXIT;
			prevq←q;
			ENDLOOP;
		IF n>=5 AND EndsHyphWord[q] AND StraddlesTarget[w] THEN
			Hyphenate[p.link, n, HyphenChar[f]]
		ELSE BEGIN curwd←curwd+w; p←prevq END;
		END;
	StraddlesTarget: PROCEDURE[w: Dimn] RETURNS[BOOLEAN] = --INLINE--
		BEGIN
		s: BigDimn←curwd+w;
		r: BreakPtr;
		FOR r←topopen, r.link UNTIL r.target<s
			DO IF r=botopen THEN RETURN[FALSE] ENDLOOP;
		RETURN[r.target>curwd];
		END;
	AddNewBreak: PROCEDURE[bestplace: BreakPtr, bestscore: TotBad] = --INLINE--
		BEGIN
		-- a new break was found and bestplace is the best lead-in
		q: BreakPtr←AllocBreakNode[]; -- create a new break node
		q↑←[link: , nlines: bestplace.nlines+1, width: curwd, flex: curflex,
			node: prevp --N.B.!--, next: bestplace, totbad: bestscore, target: ];
		-- add width, str, shr from nodes to be eliminated between lines
		AddEliminatedNodes[p, q];
		q.target←q.width+LineWidth[q.nlines];
		IF q.target>=topopen.target THEN
			BEGIN q.link←topopen; topopen←q END
		ELSE
			BEGIN
			-- This case can arise only in weird circumstances due to
			-- changing line lengths or boxes of negative width
			p: BreakPtr←topopen;
			WHILE p#botopen AND p.link.target>q.target DO p←p.link ENDLOOP;
			q.link←p.link; p.link←q;
			IF p=botopen THEN botopen←q;
			END;
		END;
	ChooseFinalBreak: PROCEDURE
		RETURNS[bestplace: BreakPtr, finalglue: GluePtr] = --INLINE--
		BEGIN
		-- choose either the break at the parfillglue ending the paragraph
		-- or break at the end of the paragraph
		q: BreakPtr←topopen;
		r: NodePtr←q.node.link; -- node following q's break
		g: GluePtr←NIL;
		TryBreak[curwd]; -- try a break including parfillglue
		IF r.link#NIL OR topopen.totbad<q.totbad THEN
			q←topopen; -- last line includes the parfillglue
		r←q.node; -- node at end of last line
		WITH rr:r SELECT FROM glue => g←rr.g; ENDCASE;
		RETURN[bestplace: q, finalglue: g];
		END;
	PackageLine: PROCEDURE[q: BreakPtr, inserts: NodeListPtr]
		RETURNS[b: BoxNodePtr, broken: BOOLEAN] = --INLINE--
		BEGIN
		brk,nextbrk: NodePtr;
		l: CARDINAL; -- line number
		line: NodeListPtr←RemoveNodeList[list,q.node];
		-- if break is at a discretionary hyphen, add a real hyphen
		IF (brk←list.link)#NIL THEN WITH bb:brk SELECT FROM
			disc => BEGIN StoreNode[line,MakeCharNode[bb.c]]; broken←TRUE END;
			ENDCASE => broken←FALSE;
		-- now prune unwanted nodes at the break
		nextbrk←IF q.link#NIL THEN q.link.node ELSE NIL;
		PruneNodes[nextbrk];
		-- and package the line into a box
		l←q.nlines-1;
		b←TexPackDefs.HPackage[list: line, desiredwidth: LineWidth[l],
			xpand: FALSE, inserts: inserts];
		IF ragged>0 THEN MakeRagged[b,ragged];
		END;
	PruneNodes: PROCEDURE[brk: NodePtr] = --INLINE--
		BEGIN
		t: NodePtr;
		WHILE (t←list.link)#NIL
			DO
			IF t=brk THEN EXIT; -- don't delete a chosen break
			SELECT t.type FROM
				glue,kern,space,penalty,disc => DsNode[RemoveNode[list]];
				ENDCASE => EXIT;
			ENDLOOP;
		END;

	-- the justification procedure starts here
	lastwidth←0;
	IF list.link=NIL THEN
		BEGIN FreeNodeList[list]; RETURN[lastwidth] END; -- empty hlist

	BEGIN OPEN TexTableDefs;
	r: TexPar←TexParam[ragged];
	WITH rr:r SELECT ragged FROM ragged=>ragged←rr.ragged; ENDCASE;
	justpar←CurPenalty[jpar];
	penPen←CurPenalty[penpen];
	hPen←CurPenalty[hpen];
	END;

	TexMemDefs.OpenZone[jzone];
	lines←0;
	prevp←list; -- This code is fussier about prevp than the Sail version:
		-- it should always be true that prevp.link=p.
	autobreaking←TRUE;
	curwd←0; ClearFlexSums[@curflex];
	topopen←botopen←AllocBreakNode[];
	topopen↑←[link: NIL, nlines: 0, width: curwd, flex: curflex,
		node: list, next: NIL, totbad: 0, target: LineWidth[0]];

	-- we go through the hlist calling TryBreak at each permissible break
	WHILE (p←prevp.link)#NIL
		DO
		WITH pp:p SELECT FROM
			char => curwd←curwd+TexFontDefs.CharWd[pp.c];
			box => curwd←curwd+pp.width;
			rule => curwd←curwd+pp.width;
			glue =>
				BEGIN
				t: GluePtr=pp.g;
				IF autobreaking THEN SELECT prevp.type FROM
					char,box,hyph,disc,ins => TryBreak[curwd];
					ENDCASE;
				curwd←curwd+t.space;
				SumFlex[t, @curflex];
				IF autobreaking THEN TryHyphenation;
				END;
			leader,ins => NULL;
			kern,space => curwd←curwd+pp.s; -- ***** allow break at space Nodes?
			hyph => autobreaking←(pp.auto=on);
			penalty =>
				BEGIN pen: Penalty←pp.pts;
				IF pen<thresholdPenalty THEN TryBreak[curwd, pen];
				END;
			disc => TryBreak[curwd+TexFontDefs.CharWd[pp.c], hPen];
			eject =>
				BEGIN
				-- this opens a new break for sure
				TryBreak[curwd, 0, TRUE];
				botopen←topopen; -- and we also close all the others
				END;
			ENDCASE => ERROR TexErrorDefs.Confusion; -- bad Node type
		prevp←p;
		ENDLOOP;

	-- now choose either the break at the parfillglue ending the paragraph
	-- or break at the end of the paragraph
	[bestplace, finalglue]←ChooseFinalBreak[];
	lines←bestplace.nlines;

	-- Now we have found the best sequence of breaks, namely to break into
	-- "lines" lines, the last break coming at "bestplace" and the break nodes
	-- telling where to break after that. The next step is to link up the
	-- break nodes in forward order, using their next fields for this purpose
	q←LinkForward[bestplace];

	-- During the finishing-up phase, which breaks up the hlist into
	-- packages that go into the output vlist, q points to the break node
	-- specifying the end of the current line, and p heads the hlist of
	-- nodes remaining to be output
	b←NIL;
	WHILE (q←q.next)#NIL
		DO
		inserts←InitNodeList[];
		[b, brokenline]←PackageLine[q, inserts];
		first←q.nlines=1;
		widow←lines>1 AND (first OR q.nlines=lines-1);
		NewLine[b,inserts,[first:first, widow:widow, broken:brokenline]];
		ENDLOOP;
	IF b#NIL THEN
		BEGIN
		lastwidth←b.width+b.shiftamt;
		IF finalglue#NIL THEN
			lastwidth←lastwidth-FixGlue[finalglue, b.glueset];
		END;
	TexDebugDefs.ShowZone[jzone,"Justification"];
	[]←TexMemDefs.CloseZone[jzone]; -- free all the break nodes
	FreeNodeList[list];
	RETURN[lastwidth];
	END;


EndsHyphWord: PROCEDURE[q: NodePtr] RETURNS[BOOLEAN] = --INLINE--
	BEGIN OPEN TexTableDefs;
	IF q#NIL THEN WITH qq:q SELECT FROM
		char => RETURN[SfTable[qq.c.char]#sfOne];
		glue => RETURN[TRUE];
		ENDCASE;
	RETURN[FALSE];
	END;

HyphenChar: PROCEDURE[f: Font] RETURNS[FChar] = --INLINE--
	BEGIN RETURN[[f,'-]] END;

LinkForward: PROCEDURE[p: BreakPtr] RETURNS[BreakPtr] = --INLINE--
	BEGIN
	q,r: BreakPtr;
	q←NIL;
	WHILE p#NIL DO r←p.next; p.next←q; q←p; p←r ENDLOOP;
	RETURN[q];
	END;

MakeRagged: PROCEDURE[b: BoxNodePtr, ragged: CARDINAL] = --INLINE--
	BEGIN OPEN InlineDefs;
	n: Dimn←b.glueset.num;
	IF n>0 THEN b.glueset.num←LongDiv[LongMult[100,n],100+ragged];
	END;

JustInit;

END.