/* 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);
}
}