diff options
Diffstat (limited to 'dviware/catdvi/layout.c')
-rw-r--r-- | dviware/catdvi/layout.c | 1119 |
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); + } +} |