summaryrefslogtreecommitdiff
path: root/dviware/catdvi/layout.c
diff options
context:
space:
mode:
Diffstat (limited to 'dviware/catdvi/layout.c')
-rw-r--r--dviware/catdvi/layout.c1119
1 files changed, 1119 insertions, 0 deletions
diff --git a/dviware/catdvi/layout.c b/dviware/catdvi/layout.c
new file mode 100644
index 0000000000..fa3275c7e3
--- /dev/null
+++ b/dviware/catdvi/layout.c
@@ -0,0 +1,1119 @@
+/* catdvi - get text from DVI files
+ Copyright (C) 1999 Antti-Juhani Kaijanaho <gaia@iki.fi>
+ Copyright (C) 2000-02 Bjoern Brill <brill@fs.math.uni-frankfurt.de>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#include <stdlib.h>
+#include <assert.h>
+#include "layout.h"
+#include "util.h"
+#include "page2.h"
+#include "outenc.h"
+#include "linebuf.h"
+#include "density.h"
+#include "canvas.h"
+#include "vlist.h"
+#include "fontinfo.h"
+
+/* page margins */
+static sint32 left_margin, right_margin;
+static sint32 top_margin, bottom_margin;
+
+/* other page metrics */
+int linecount = 0;
+uint32 boxcount = 0;
+double average_box_width = 0;
+double average_box_totheight = 0;
+
+/* layout parameters */
+sint32 max_col_width, max_row_height;
+double min_col_density, min_line_density;
+scdf_t col_density, line_density;
+scdf_t * x2col, * y2line;
+
+
+/* some obvious stuff about rectangles */
+typedef struct rect_t rect_t;
+struct rect_t {
+ sint32 xmin;
+ sint32 xmax;
+ sint32 ymin;
+ sint32 ymax;
+};
+
+int intervals_intersect(
+ sint32 a, sint32 b,
+ sint32 c, sint32 d
+);
+
+int rect_intersects(const rect_t * this, const rect_t * that);
+
+int rect_contains_point(const rect_t * this, sint32 x, sint32 y);
+
+/* create rect */
+void rect_set(
+ rect_t * this,
+ sint32 xmin,
+ sint32 xmax,
+ sint32 ymin,
+ sint32 ymax
+);
+
+void rect_set_empty(rect_t * this);
+
+int rect_is_empty(const rect_t * this);
+
+/* *this = smallest rect containing *this and *that */
+void rect_union_with(rect_t * this, const rect_t * that);
+
+
+/* a page_word is a sequence of contiguous box_t which should remain
+ * contiguous in printout.
+ */
+typedef struct page_word_t page_word_t;
+struct page_word_t {
+ list_node_t * alpha; /* node of first box in word */
+ list_node_t * omega; /* node of last box in word */
+ linebuf_t * text;
+ rect_t brect; /* bounding rectangle: the smallest rectangle
+ * containing the part _avove the baseline_
+ * of all boxes in the word
+ */
+ sint32 ceiling; /* stuff with y <= ceiling should appear top of
+ * our row in printout.
+ */
+ sint32 right_wall; /* stuff with x >= right_wall should appear right
+ * from our rightmost glyph in printout.
+ */
+ sint32 right_corridor; /* stuff on the same row with x >= right_corridor
+ * should appear trailing_spaces columns right from
+ * our rightmost glyph in printout.
+ */
+ int output_width;
+ int trailing_spaces; /* usually 1, somtetimes 0 */
+ int row;
+ int column;
+};
+
+/* The page has one global list of page_words */
+vlist_t page_words;
+
+/* constructor */
+static void page_word_init(
+ page_word_t * this,
+ list_node_t * alpha,
+ list_node_t * omega,
+ int trailing_spaces
+);
+
+/* destructor */
+static void page_word_done(page_word_t * this);
+
+/* Try to resolve collisions (i.e. situations where the bounding rects of
+ * two words intersect).
+ */
+static void page_words_collide(vitor_t vi, vitor_t vj);
+
+/* Split *this before where; i.e. :
+ * - create a new page_word containing the boxes from where to this->omega
+ * on the heap ("right half")
+ * - shrink *this to the boxes from this->alpha to where->prev ("left half")
+ * - return pointer to new page_word
+ * Both the left and right half are brought into shape by constructor calls,
+ * so any information about ceilings, right walls, etc. gets lost.
+ */
+static page_word_t * page_word_split_at(
+ page_word_t * this,
+ struct list_node_t * where
+);
+
+
+/* Estimate number of spaces from distance between boxes */
+static int decide_space_count(
+ struct list_node_t * prev_p,
+ struct list_node_t * p
+);
+
+/* Look at the midpoints of two boxes. If either midpoint lies in the other
+ * box, the boxes compare "equal". Otherwise, we compare x of midpoints.
+ */
+sint32 box_sloppy_x_cmp(const struct box_t * p1, const struct box_t * p2);
+
+
+static void page_collect_statistics(void);
+
+/* Make an initial pass at cutting the page into words, based on the distance
+ * between adjacent boxes. This will be refined in a later pass.
+ */
+static void page_cut_words(void);
+
+
+/* If the bounding rectangles of two words on the page collide, we have
+ * likely hit a word breaking problem (example: math subscripts are
+ * too thin to cause a word break between adjacent variables). If a
+ * collission occurs, we call a function that tries to resolve it
+ * by introducing additional word breaks.
+ */
+static void page_check_word_collisions(void);
+
+/* The idea: words with x coordinates close to each other and different
+ * y coordinates should appear on different rows in printout.
+ */
+static void page_find_ceilings(void);
+
+/* If two words end up on the same line in printout, then the left one
+ * needs to put its trailing_spaces before the right one starts.
+ * Obviously, this has to be called _after_ we know our rows.
+ */
+static void page_find_right_corridors(void);
+
+/* If the y intervals of the bounding rectangles of two words intersect,
+ * then the left one should end in printout before the right one starts.
+ * This should be called _after_ page_find_right_corridors() because we want
+ * to ensure right_wall <= right_corridor .
+ */
+static void page_find_right_walls(void);
+
+/* Determine on which row in printout words end up. The main vehicle here
+ * is a line density function; we force it to have integral >=1 on the
+ * interval [word->ceiling, word->brect->ymax].
+ * The words are then positioned so that their baseline is in the correct row.
+ */
+static void page_determine_lines(void);
+
+/* Determine on which column in printout words end up. The main vehicle here
+ * is a column density function; we force it to have large enough integrals
+ * on the intervals [word->brect->xmin, word->right_wall] resp.
+ * [word->brect->xmin, word->right_wall] to accomodate word->output_width
+ * resp. word->output_width + word->trailing_spaces columns.
+ * The words are then positioned so that their left boundary is in the correct
+ * column.
+ */
+static void page_determine_cols(void);
+
+
+void page_print_formatted(void)
+{
+ canv_t canvas;
+ vitor_t pwi;
+
+ pmesg(50, "BEGIN page_print_formatted\n");
+
+ /* Life is much easier if we don't have to care for the case
+ * of an empty page all the time.
+ */
+ if(list_head == NULL) {
+ puts("\f\n");
+ pmesg(80, "This page is empty.\n");
+ pmesg(50, "END page_print_formatted\n");
+ return;
+ }
+
+ page_adjust_diacritics();
+ page_adjust_texmext();
+ page_adjust_radicals();
+
+ page_collect_statistics();
+
+ max_col_width = (sint32) (4.0 * average_box_width);
+ max_row_height = (sint32) (3.0 * average_box_totheight);
+ min_col_density = 1.0 / max_col_width;
+ min_line_density = 1.0 / max_row_height;
+ /*
+ * The minimal densities should ensure that large amounts of white space
+ * do not completely get lost. The factors 3.0, 4.0 have been determined
+ * by rules of thumb and experiments.
+ * The (unverified) expectation is that a printout column will be
+ * about average_box_width DVI units wide and a printout row will be
+ * about 1.5 * average_box_totheight DVI units high.
+ */
+ scdf_init(&col_density, left_margin, right_margin, min_col_density);
+ /* col_density measures the column density at every point between
+ * left and right margin which is required to do proper positioning
+ * of every word.
+ */
+ scdf_init(&line_density, top_margin, bottom_margin, min_line_density);
+ /* Similar for line_density and lines */
+
+ vlist_init(&page_words);
+ page_cut_words();
+ page_check_word_collisions();
+
+ page_find_ceilings();
+ page_determine_lines();
+
+ page_find_right_corridors();
+ page_find_right_walls();
+ page_determine_cols();
+
+ /* Now print out everything */
+ canv_init(
+ &canvas,
+ (sint32) scdf_eval(x2col, right_margin) + 1,
+ (sint32) scdf_eval(y2line, bottom_margin) + 1
+ );
+ for(
+ pwi = vlist_begin(&page_words);
+ pwi != vlist_end(&page_words);
+ pwi = pwi->next
+ ) {
+ page_word_t * pw;
+
+ pw = vitor2ptr(pwi, page_word_t);
+ canv_put_linebuf(
+ &canvas,
+ pw->text,
+ pw->column,
+ pw->row,
+ pw->output_width
+ );
+ pw->text = NULL; /* text is now owned by the canvas */
+ }
+ canv_write(&canvas, stdout);
+ puts("\f\n");
+
+ /* clean up */
+
+ canv_done(&canvas);
+
+ for(
+ pwi = vlist_begin(&page_words);
+ pwi != vlist_end(&page_words);
+ pwi = pwi->next
+ ) {
+ page_word_done(pwi->data);
+ free(pwi->data);
+ }
+ vlist_done(&page_words);
+
+ scdf_done(y2line); free(y2line);
+ scdf_done(x2col); free(x2col);
+ scdf_done(&col_density);
+ scdf_done(&line_density);
+
+ pmesg(50, "END page_print_formatted\n");
+}
+
+
+void page_print_sequential(void)
+{
+ struct list_node_t * p;
+ struct box_t prev_box, curr_box;
+
+ sint32 delta_x = 0, delta_y = 0;
+ sint32 dist_x = 0;
+ sint32 epsilon_x = 0, epsilon_y = 0;
+
+ /* begin-of-page flag */
+ int bop = 1;
+ /* begin-of-line flag */
+ int bol = 1;
+
+ int spaces, spaces_by_prev, spaces_by_curr;
+ struct linebuf_t lb;
+
+ pmesg(50, "BEGIN page_print_sequential\n");
+
+ page_adjust_diacritics();
+
+ linebuf_init(&lb, 0);
+ prev_box.width = 1;
+ prev_box.height = 1;
+
+ for (p = list_head; p != 0; p = p->next) {
+
+ pmesg(80, "node: X = %li, Y = %li, glyph = %li (%c), font = %li\n",
+ p->b.x, p->b.y, p->b.glyph, (unsigned char) p->b.glyph, p->b.font);
+
+ curr_box = p->b;
+ if (curr_box.width == 0) curr_box.width = prev_box.width;
+ if (curr_box.height == 0) curr_box.height = prev_box.height;
+
+ if (!bop) {
+ delta_x = curr_box.x - prev_box.x;
+ delta_y = curr_box.y - prev_box.y;
+ dist_x = delta_x - prev_box.width;
+
+ /* (arithmetic mean of current and previous) / 20 */
+ epsilon_x = (curr_box.width + prev_box.width + 39) / 40;
+ epsilon_y = (curr_box.height + prev_box.height + 39) / 40;
+
+ /* check for new line */
+ if (
+ /* new line */
+ delta_y >= 22*epsilon_y ||
+ /* new column */
+ delta_y <= -60*epsilon_y ||
+ /* weird step back */
+ dist_x <= -100*epsilon_x
+ ) {
+ pmesg(80, "end of line\n");
+ outenc_write(stdout, &lb);
+ linebuf_clear(&lb);
+ puts("");
+ bol = 1;
+ }
+
+ /* check for word breaks, but not at the beginning of a line */
+ if ((dist_x > 0) && (!bol)) {
+ spaces_by_prev =
+ font_w_to_space(prev_box.font, dist_x);
+ spaces_by_curr =
+ font_w_to_space(curr_box.font, dist_x);
+ spaces = (spaces_by_prev + spaces_by_curr + 1) / 2;
+
+ if (spaces > 0) {
+ pmesg(80, "setting space\n");
+ linebuf_putg(&lb, ' ');
+ }
+ }
+
+ } /* end if (!bop) */
+
+ linebuf_putg(&lb, curr_box.glyph);
+ prev_box = curr_box;
+ bop = 0;
+ bol = 0;
+ }
+ /* flush line buffer and end page */
+ outenc_write(stdout, &lb);
+ puts("\n\f\n");
+
+ linebuf_done(&lb);
+
+ pmesg(50, "END page_print_sequential\n");
+}
+
+static int decide_space_count(
+ struct list_node_t * prev_p,
+ struct list_node_t * p
+)
+{
+ font_t prev_font, curr_font;
+ sint32 prev_x, prev_width;
+ sint32 curr_x;
+ sint32 delta;
+ int (* const f2spc)(sint32, sint32) = font_w_to_space;
+
+ prev_font = prev_p->b.font;
+ prev_x = prev_p->b.x;
+ prev_width = prev_p->b.width;
+
+ curr_font = p->b.font;
+ curr_x = p->b.x;
+
+ delta = curr_x - (prev_x + prev_width);
+ return (1 + f2spc(curr_font, delta) + f2spc(prev_font, delta)) / 2;
+}
+
+
+/*************** page_word_t method implementations ****************/
+void page_word_init(
+ page_word_t * this,
+ list_node_t * alpha,
+ list_node_t * omega,
+ int trailing_spaces
+)
+{
+ list_node_t * p, * q;
+ rect_t r;
+
+ this->alpha = alpha;
+ this->omega = omega;
+ this->text = xmalloc(sizeof(linebuf_t));
+ linebuf_init(this->text, 20);
+ /* 20 seems a good tradeoff between memory usage and
+ * avoiding reallocs.
+ */
+ rect_set_empty(&(this->brect));
+ this->ceiling = SINT32_MIN;
+ /* The top line has no ceiling -- it fits automatically */
+ this->right_wall = right_margin;
+ this->right_corridor = right_margin;
+ /* this->output_width will be set below */
+ this->trailing_spaces = trailing_spaces;
+ this->row = -1; /* will be filled in later */
+ this->column = -1; /* will be filled in later */
+
+ q = omega->next;
+ for(p = alpha; p != q; p = p->next) {
+ /* add p->b to bounding rect */
+ rect_set(
+ &r,
+ p->b.x,
+ p->b.x + p->b.width,
+ p->b.y - p->b.height,
+ p->b.y
+ );
+ rect_union_with(&(this->brect), &r);
+
+ /* add p->b.glyph to text */
+ linebuf_putg(this->text, p->b.glyph);
+ }
+
+ this->output_width = outenc_get_width(this->text);
+}
+
+
+void page_word_done(page_word_t * this)
+{
+ this->alpha = NULL;
+ this->omega = NULL;
+ /* this->text will be NULL after it has been passed to canvas */
+ if(this->text != NULL) {
+ linebuf_done(this->text);
+ free(this->text);
+ this->text = NULL;
+ }
+}
+
+static void page_words_collide(vitor_t vi, vitor_t vj)
+{
+ page_word_t * wp, * wq;
+ list_node_t * bp, * bq;
+ sint32 c;
+
+ pmesg(60, "BEGIN page_words_collide\n");
+
+ wp = vi->data;
+ wq = vj->data;
+
+ bp = wp->alpha;
+ bq = wq->alpha;
+ if(box_sloppy_x_cmp(&bp->b, &bq->b) > 0) {
+ /* We want to assume that *wp starts left from *wq */
+ pmesg(60, "calling myself with exchanged arguments\n");
+ page_words_collide(vj, vi);
+ pmesg(60, "END page_words_collide\n");
+ return;
+ }
+
+ /* Skip all letters of *wp left of *wq. We allow a certain margin overlap
+ * to accomodate italics correction, kerning, etc.
+ */
+ while(c = box_sloppy_x_cmp(&bp->b, &bq->b), c < 0) {
+ if(bp == wp->omega) {
+ /* We're at the end of *wp, so either really no collision
+ * at all, or only the last box collides. Anyway, nothing
+ * to do.
+ */
+ pmesg(60, "nothing to do\n");
+ pmesg(60, "END page_words_collide\n");
+ return;
+ }
+ bp = bp->next;
+ }
+
+ if(c == 0) {
+ /* Ouch, full crash */
+ pmesg(60, "unresolvable collision\n");
+ pmesg(60, "END page_words_collide\n");
+ return;
+ }
+
+ /* We've moved bp across the beginning of *wq */
+ pmesg(60, "resolving collision by splitting word\n");
+ vlist_insert_after(&page_words, vi, page_word_split_at(wp, bp));
+
+ /* Check for further collisions between *wq and the right piece of *wp */
+ pmesg(60, "checking for further collisions\n");
+ page_words_collide(vj, vi->next);
+ pmesg(60, "END page_words_collide\n");
+}
+
+static page_word_t * page_word_split_at(
+ page_word_t * this,
+ struct list_node_t * where
+)
+{
+ page_word_t * righthalf;
+ list_node_t * alpha;
+
+ /* No splitting with one half empty, please. */
+ assert(where != this->alpha);
+ assert(where != this->omega->next);
+
+ /* create right half */
+ righthalf = xmalloc(sizeof(page_word_t));
+ page_word_init(righthalf, where, this->omega, this->trailing_spaces);
+
+ /* reinit left half (ourselves) */
+ alpha = this->alpha;
+ page_word_done(this);
+ page_word_init(this, alpha, where->prev, 0);
+
+ return righthalf;
+}
+
+
+sint32 box_sloppy_x_cmp(const struct box_t * p1, const struct box_t * p2)
+{
+ sint32 m1, m2; /* midpoints */
+
+ m1 = p1->x + p1->width / 2;
+ m2 = p2->x + p2->width / 2;
+
+ /* If the x midpoint of one box is in the x interval of the other,
+ * the two are considered close together (and compare "equal").
+ * Otherwise, the x midpoints are compared.
+ */
+ if(p1->x <= m2 && m2 <= p1->x + p1->width) return 0;
+ if(p2->x <= m1 && m1 <= p2->x + p2->width) return 0;
+ return m1 - m2;
+}
+
+
+/*************** page layout passes ********************************/
+void page_collect_statistics(void)
+{
+ struct list_node_t * p;
+ sint32 prev_y;
+
+ pmesg(80, "BEGIN page_collect_statistics\n");
+
+ left_margin = SINT32_MAX;
+ right_margin = SINT32_MIN;
+ top_margin = SINT32_MAX;
+ bottom_margin = SINT32_MIN;
+
+ average_box_width = 0;
+ average_box_totheight = 0;
+ linecount = 0;
+ boxcount = 0;
+
+ prev_y = list_head->b.y;
+ for (p = list_head; p != 0; p = p->next) {
+ sint32 x, y, width, height, depth;
+
+ x = p->b.x;
+ y = p->b.y;
+ width = p->b.width;
+ height = p->b.height;
+ depth = p->b.depth;
+
+ left_margin = min(left_margin, x);
+ right_margin = max(right_margin, x + width);
+ top_margin = min(top_margin, y - height);
+ bottom_margin = max(bottom_margin, y + depth);
+
+ if (y > prev_y) {
+ prev_y = y;
+ linecount++;
+ }
+
+ average_box_width += width;
+ average_box_totheight += (height + depth);
+ ++boxcount;
+ }
+ ++linecount; /* The last line hasn't been counted */
+ average_box_width = average_box_width / boxcount;
+ average_box_totheight = average_box_totheight / boxcount;
+
+ pmesg(80, "left margin: %ld, right margin: %ld.\n", \
+ left_margin, right_margin);
+ pmesg(80, "top margin: %ld, bottom margin: %ld.\n", \
+ top_margin, bottom_margin);
+
+ pmesg(80, "END page_collect_statistics\n");
+}
+
+
+void page_cut_words(void)
+{
+ struct list_node_t * p;
+
+ int bop, eop, bol, eol, bow, eow;
+ /* {begin,end} of {page, line, word} flags */
+
+ pmesg(50, "BEGIN page_cut_words\n");
+
+ bop = 1;
+ bol = 1;
+ bow = 1;
+ for (p = list_head; p != NULL; p = p->next) {
+ sint32 y;
+ list_node_t * curr_alpha;
+
+ pmesg(80, "node: X = %li, Y = %li, glyph = %li (%c), font = %li\n",
+ p->b.x, p->b.y, p->b.glyph, (unsigned char) p->b.glyph, p->b.font);
+
+ y = p->b.y;
+ eop = (p->next == NULL);
+ eol = eop || (p->next->b.y != y);
+ eow = eol || (decide_space_count(p, p->next) > 0);
+
+ if(bow) {
+ curr_alpha = p;
+ }
+
+ if(eow) {
+ int trailing_space;
+ page_word_t * new_word;
+
+ if(eol) {
+ trailing_space = 0;
+ }
+ else {
+ trailing_space = 1;
+ }
+
+ /* Make up a page_word_t from the collected data and insert
+ * it into the page_words list
+ */
+ new_word = xmalloc(sizeof(page_word_t));
+ page_word_init(new_word, curr_alpha, p, trailing_space);
+ vlist_push_back(&page_words, new_word);
+ }
+
+ if(eol) {
+ pmesg(80, "end of line\n");
+ }
+
+ bop = 0;
+ bol = eol;
+ bow = eow;
+
+ } /* for p */
+
+ pmesg(50, "END page_cut_words\n");
+
+}
+
+
+static void page_check_word_collisions(void)
+{
+ vitor_t vi, nvi, vj, llvi;
+ page_word_t * p, * np, * q;
+ int eop, eol;
+
+ pmesg(50, "BEGIN page_check_word_collisions\n");
+
+ llvi = vlist_rend(&page_words);
+
+ for(
+ vi = vlist_begin(&page_words);
+ vi != vlist_end(&page_words);
+ vi = nvi
+ ) {
+ p = vi->data;
+ nvi = vi->next;
+ np = nvi->data;
+
+ eop = (nvi == vlist_end(&page_words));
+ eol = eop || np->brect.ymax != p->brect.ymax;
+
+ /* We only need to look upwards, a collision will then always be caught
+ * by the lower one of the colliding words.
+ * Collisions between words on the same baseline cannot occur
+ * (by design of the basic word break algorithm) and shouldn't
+ * result in new word breaks anyway.
+ *
+ * We keep an iterator to the last word in the previous line (upwards)
+ * to avoid repeated skipping backwards over preceding words
+ * on the same baseline.
+ */
+ for(vj = llvi; vj != vlist_rend(&page_words); vj = vj->prev) {
+ q = vj->data;
+ if(q->brect.ymax < p->brect.ymin) break;
+ /* We are too far up to find any more collisions. Note
+ * this happens _immediately_ in the standard (one column
+ * text without intersecting lines) case.
+ */
+ if(!intervals_intersect(
+ p->brect.xmin, p->brect.xmax,
+ q->brect.xmin, q->brect.xmax
+ )) continue;
+ page_words_collide(vi, vj);
+ /* We do _not_ break if q->brect.xmax < p->brect.xmin
+ * because there may be more than one line with
+ * possible collisions.
+ */
+ }
+
+ if(eol) llvi = vi;
+ }
+
+ pmesg(50, "END page_check_word_collisions\n");
+}
+
+
+static void page_find_ceilings(void)
+{
+ vitor_t vi, nvi, vj, llvi;
+ page_word_t * p, * np, * q;
+ int eop, eol;
+
+ pmesg(50, "BEGIN page_find_ceilings\n");
+
+ llvi = vlist_rend(&page_words);
+
+ /* Our policy is the following:
+ * a. Stuff that has its baseline above our head (read p->brect.ymin) must
+ * end up on a higher line.
+ * b. Stuff that is near us in x direction and has its baseline above
+ * ours must end up on a higher line.
+ */
+
+ for(
+ vi = vlist_begin(&page_words);
+ vi != vlist_end(&page_words);
+ vi = nvi
+ ) {
+ sint32 xmin, xmax; /* the x interval we're interested in */
+ sint32 ymin; /* we need not care for stuff higher that that */
+
+ p = vi->data;
+ nvi = vi->next;
+ np = nvi->data;
+
+ xmin = p->brect.xmin - 2 * average_box_width;
+ xmax = p->brect.xmax + 2 * average_box_width;
+ ymin = p->brect.ymax - max_row_height;
+
+ eop = (nvi == vlist_end(&page_words));
+ eol = eop || np->brect.ymax != p->brect.ymax;
+
+ /* We only need to look upwards, and no further than max_row_hight
+ *
+ * We keep an iterator to the last word in the previous line (upwards)
+ * to avoid repeated skipping backwards over preceding words
+ * on the same baseline.
+ * Since the list is traversed bottom-to-top, we can stop looking
+ * as soon as we've found the first ceiling candidate.
+ */
+ for(vj = llvi; vj != vlist_rend(&page_words); vj = vj->prev) {
+ q = vj->data;
+ if(q->brect.ymax < ymin) {
+ /* stuff so high will end up on another line automatically */
+ break;
+ }
+ if(q->brect.ymax < p->brect.ymin) {
+ p->ceiling = q->brect.ymax;
+ break;
+ }
+ if(intervals_intersect(
+ xmin, xmax,
+ q->brect.xmin, q->brect.xmax
+ )) {
+ p->ceiling = q->brect.ymax;
+ break;
+ }
+ }
+
+ if(eol) llvi = vi;
+ }
+
+ pmesg(50, "END page_find_ceilings\n");
+}
+
+
+static void page_find_right_corridors(void)
+{
+ vitor_t vi, nvi, vj, llvi;
+ page_word_t * p, * np, * q;
+ int eop, eol;
+
+ pmesg(50, "BEGIN page_find_right_corridors\n");
+
+ llvi = vlist_rend(&page_words);
+
+ for(
+ vi = vlist_begin(&page_words);
+ vi != vlist_end(&page_words);
+ vi = nvi
+ ) {
+ p = vi->data;
+ nvi = vi->next;
+ np = nvi->data;
+
+ eop = (nvi == vlist_end(&page_words));
+ eol = eop || np->brect.ymax != p->brect.ymax;
+
+ /* first we look directly right */
+ if(!eol) {
+ p->right_corridor = min(p->right_corridor, np->brect.xmin);
+ }
+
+ /* Now we look upwards (left and right).
+ *
+ * We keep an iterator to the last word in the previous line (upwards)
+ * to avoid repeated skipping backwards over preceding words
+ * on the same baseline.
+ */
+ for(vj = llvi; vj != vlist_rend(&page_words); vj = vj->prev) {
+ q = vj->data;
+ if(q->row < p->row) break;
+ /* We need not look further up */
+ if(q->brect.xmin < p->brect.xmin) {
+ q->right_corridor = min(q->right_corridor, p->brect.xmin);
+ }
+ else if(p->brect.xmin < q->brect.xmin) {
+ p->right_corridor = min(p->right_corridor, q->brect.xmin);
+ }
+ }
+
+ if(eol) llvi = vi;
+ }
+
+ pmesg(50, "END page_find_right_corridors\n");
+}
+
+
+static void page_find_right_walls(void)
+{
+ vitor_t vi, nvi, vj, llvi;
+ page_word_t * p, * np, * q;
+ int eop, eol;
+
+ pmesg(50, "BEGIN page_find_right_walls\n");
+
+ llvi = vlist_rend(&page_words);
+
+ for(
+ vi = vlist_begin(&page_words);
+ vi != vlist_end(&page_words);
+ vi = nvi
+ ) {
+ p = vi->data;
+ nvi = vi->next;
+ np = nvi->data;
+
+ eop = (nvi == vlist_end(&page_words));
+ eol = eop || np->brect.ymax != p->brect.ymax;
+
+ /* This has to be done somewhere. The most natural place is here. */
+ p->right_wall = min(p->right_wall, p->right_corridor);
+
+ /* We need not look directly right, we've already done so to
+ * find right_corridor. But if we are at the end of the line,
+ * we want stuff on other lines starting clearly right from where we
+ * end to appear right of us.
+ */
+ if(eol) {
+ p->right_wall = min(
+ p->right_wall,
+ p->brect.xmax + average_box_width
+ );
+ /* FIXME: is average_box_width the right amount of slack? Or
+ * use no slack at all ?
+ */
+ }
+
+ /* Now we look upwards (left and right).
+ *
+ * We keep an iterator to the last word in the previous line (upwards)
+ * to avoid repeated skipping backwards over preceding words
+ * on the same baseline.
+ */
+ for(vj = llvi; vj != vlist_rend(&page_words); vj = vj->prev) {
+ q = vj->data;
+ if(q->brect.ymax < p->brect.ymin) break;
+ /* We need not look further up */
+ if(box_sloppy_x_cmp(&(q->omega->b), &(p->alpha->b)) < 0) {
+ /* *q ends left from *p */
+ q->right_wall = min(q->right_wall, p->brect.xmin);
+ }
+ else if(box_sloppy_x_cmp(&(p->omega->b), &(q->alpha->b)) < 0) {
+ /* *q starts right from *p */
+ p->right_wall = min(p->right_wall, q->brect.xmin);
+ }
+ /* FIXME: what about crashing words? Should we do something here?
+ * And is box_sloppy_x_cmp() really the right criterion?
+ */
+ }
+
+ if(eol) llvi = vi;
+ }
+
+ pmesg(50, "END page_find_right_walls\n");
+}
+
+
+static void page_determine_lines(void)
+{
+ vitor_t vi;
+ page_word_t * p;
+
+ pmesg(50, "BEGIN page_determine_lines\n");
+
+ for(
+ vi = vlist_begin(&page_words);
+ vi != vlist_end(&page_words);
+ vi = vi->next
+ ) {
+ p = vi->data;
+ pmesg(
+ 100,
+ "x = %ld, y = %ld, ceiling = %ld\n",
+ p->brect.xmin,
+ p->brect.ymax,
+ p->ceiling
+ );
+
+ if(p->ceiling >= top_margin) {
+ scdf_force_min_integral(
+ &line_density,
+ p->ceiling,
+ p->brect.ymax,
+ 1
+ );
+ }
+ }
+
+ scdf_normalize(&line_density);
+ y2line = scdf_floor_of_integral(&line_density);
+
+ for(
+ vi = vlist_begin(&page_words);
+ vi != vlist_end(&page_words);
+ vi = vi->next
+ ) {
+ p = vi->data;
+ p->row = (sint32) scdf_eval(y2line, p->brect.ymax);
+ pmesg(100, "word at row %i\n", p->row);
+ }
+
+ pmesg(50, "END page_determine_lines\n");
+}
+
+
+static void page_determine_cols(void)
+{
+ vitor_t vi, vj;
+ page_word_t * p;
+ int eop, eol;
+
+ pmesg(50, "BEGIN page_determine_cols\n");
+
+ for(
+ vi = vlist_begin(&page_words);
+ vi != vlist_end(&page_words);
+ vi = vj
+ ) {
+ p = vi->data;
+ pmesg(
+ 100,
+ "x = %ld, y = %ld, right_wall = %ld, right_corridor = %ld\n",
+ p->brect.xmin,
+ p->brect.ymax,
+ p->right_wall,
+ p->right_corridor
+ );
+ assert(p->right_wall <= p->right_corridor);
+ assert(p->right_corridor <= right_margin);
+
+ if(p->right_wall < p->right_corridor) {
+ scdf_force_min_integral(
+ &col_density,
+ p->brect.xmin,
+ p->right_wall,
+ p->output_width
+ );
+ }
+ if(p->right_wall == p->right_corridor || p->trailing_spaces > 0) {
+ scdf_force_min_integral(
+ &col_density,
+ p->brect.xmin,
+ p->right_corridor,
+ p->output_width + p->trailing_spaces
+ );
+ }
+
+ vj = vi->next;
+ eop = (vj == vlist_end(&page_words));
+ eol = eop || (p->brect.ymax != vitor2ptr(vj, page_word_t)->brect.ymax);
+ if(eol) scdf_normalize(&col_density);
+ }
+
+ x2col = scdf_floor_of_integral(&col_density);
+
+ for(
+ vi = vlist_begin(&page_words);
+ vi != vlist_end(&page_words);
+ vi = vi->next
+ ) {
+ p = vi->data;
+ p->column = (sint32) scdf_eval(x2col, p->brect.xmin);
+ pmesg(100, "word at column %i\n", p->column);
+ }
+
+ pmesg(50, "END page_determine_cols\n");
+}
+
+
+/***************** rect_t method implementations **********************/
+int intervals_intersect(
+ sint32 a, sint32 b,
+ sint32 c, sint32 d
+)
+{
+ if(a > b || c > d) return 0; /* One of the intervals is empty */
+ return c <= b && a <= d; /* yes, this works in ALL remaining cases :) */
+}
+
+int rect_intersects(const rect_t * this, const rect_t * that)
+{
+ return (
+ intervals_intersect(this->xmin, this->xmax, that->xmin, that->xmax)
+ && intervals_intersect(this->ymin, this->ymax, that->ymin, that->ymax)
+ );
+}
+
+int rect_contains_point(const rect_t * this, sint32 x, sint32 y)
+{
+ return (
+ this->xmin <= x && x <= this->xmax
+ && this->ymin <= y && y <= this->ymax
+ );
+}
+
+void rect_set(
+ rect_t * this,
+ sint32 xmin,
+ sint32 xmax,
+ sint32 ymin,
+ sint32 ymax
+)
+{
+ this->xmin = xmin;
+ this->xmax = xmax;
+ this->ymin = ymin;
+ this->ymax = ymax;
+}
+
+void rect_set_empty(rect_t * this)
+{
+ rect_set(this, 1, 0, 1, 0);
+}
+
+int rect_is_empty(const rect_t * this)
+{
+ return this->xmin > this->xmax || this->ymin > this->ymax;
+}
+
+void rect_union_with(rect_t * this, const rect_t * that)
+{
+ if(rect_is_empty(that)) return;
+
+ if(rect_is_empty(this)) *this = *that;
+ else {
+ this->xmin = min(this->xmin, that->xmin);
+ this->xmax = max(this->xmax, that->xmax);
+ this->ymin = min(this->ymin, that->ymin);
+ this->ymax = max(this->ymax, that->ymax);
+ }
+}