path: root/extract/src/boxer.c

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <assert.h>

#include "document.h"
#include "outf.h"

#define DEBUG_WRITE_AS_PS
/* #define DEBUG_PRINT */

typedef struct boxer_s boxer_t;

typedef struct {
    int    len;
    int    max;
    rect_t list[1];
} rectlist_t;

struct boxer_s {
    extract_alloc_t *alloc;
    rect_t           mediabox;
    rectlist_t      *list;
};

static rectlist_t *
rectlist_create(extract_alloc_t *alloc, int max)
{
    rectlist_t *list;

    if (extract_malloc(alloc, &list, sizeof(rectlist_t) + sizeof(rect_t)*(max-1)))
        return NULL;

    list->len = 0;
    list->max = max;

    return list;
}

/* Push box onto rectlist, unless it is completely enclosed by
 * another box, or completely encloses others (in which case they
 * are replaced by it). */
static void
rectlist_append(rectlist_t *list, rect_t *box)
{
    int i;

    for (i = 0; i < list->len; i++)
    {
        rect_t *r = &list->list[i];
        rect_t smaller, larger;
        /* We allow ourselves a fudge factor of 4 points when checking for inclusion. */
        double r_fudge = 4;

        smaller.min.x = r->min.x + r_fudge;
        larger. min.x = r->min.x - r_fudge;
        smaller.min.y = r->min.y + r_fudge;
        larger. min.y = r->min.y - r_fudge;
        smaller.max.x = r->max.x - r_fudge;
        larger. max.x = r->max.x + r_fudge;
        smaller.max.y = r->max.y - r_fudge;
        larger. max.y = r->max.y + r_fudge;

        if (extract_rect_contains_rect(larger, *box))
            return; /* box is enclosed! Nothing to do. */
        if (extract_rect_contains_rect(*box, smaller)) {
            /* box encloses r. Ditch r. */
            /* Shorten the list */
            --list->len;
            /* If the one that just got chopped off wasn't r, move it down. */
            if (i < list->len) {
                memcpy(r, &list->list[list->len], sizeof(*r));
                i--; /* Reconsider this entry next time. */
            }
        }
    }

    assert(list->len < list->max);
    memcpy(&list->list[list->len], box, sizeof(*box));
    list->len++;
}

static boxer_t *
boxer_create_length(extract_alloc_t *alloc, rect_t *mediabox, int len)
{
    boxer_t *boxer;

    if (extract_malloc(alloc, &boxer, sizeof(*boxer)))
        return NULL;

    boxer->alloc = alloc;
    memcpy(&boxer->mediabox, mediabox, sizeof(*mediabox));
    boxer->list = rectlist_create(alloc, len);

    return boxer;
}

/* Create a boxer structure for a page of size mediabox. */
static boxer_t *
boxer_create(extract_alloc_t *alloc, rect_t *mediabox)
{
    boxer_t *boxer = boxer_create_length(alloc, mediabox, 1);

    if (boxer == NULL)
        return NULL;
    rectlist_append(boxer->list, mediabox);

    return boxer;
}

static void
push_if_intersect_suitable(rectlist_t *dst, const rect_t *a, const rect_t *b)
{
    rect_t c;

    /* Intersect a and b. */
    c = extract_rect_intersect(*a, *b);
    /* If no intersection, nothing to push. */
    if (!extract_rect_valid(c))
        return;

    /* If the intersect is too narrow or too tall, ignore it.
     * We don't care about inter character spaces, for example.
     * Arbitrary 4 point threshold. */
#define THRESHOLD 4
    if (c.min.x + THRESHOLD >= c.max.x || c.min.y+THRESHOLD >= c.max.y)
        return;

    rectlist_append(dst, &c);
}

static void
boxlist_feed_intersect(rectlist_t *dst, const rectlist_t *src, const rect_t *box)
{
    int i;

    for (i = 0; i < src->len; i++)
        push_if_intersect_suitable(dst, &src->list[i], box);
}

/* Mark a given box as being occupied (typically by a glyph) */
static int boxer_feed(boxer_t *boxer, rect_t *bbox)
{
    rect_t box;
    /* When we feed a box into a the boxer, we can never make
     * the list more than 4 times as long. */
    rectlist_t *newlist = rectlist_create(boxer->alloc, boxer->list->len * 4);
    if (newlist == NULL)
        return -1;

#ifdef DEBUG_WRITE_AS_PS
    printf("0 0 1 setrgbcolor\n");
    printf("%g %g moveto %g %g lineto %g %g lineto %g %g lineto closepath fill\n",
           bbox->min.x, bbox->min.y,
           bbox->min.x, bbox->max.y,
           bbox->max.x, bbox->max.y,
           bbox->max.x, bbox->min.y
           );
#endif

    /* Left (0,0) (min.x,H) */
    box.min.x = boxer->mediabox.min.x;
    box.min.y = boxer->mediabox.min.y;
    box.max.x = bbox->min.x;
    box.max.y = boxer->mediabox.max.y;
    boxlist_feed_intersect(newlist, boxer->list, &box);

    /* Right (max.x,0) (W,H) */
    box.min.x = bbox->max.x;
    box.min.y = boxer->mediabox.min.y;
    box.max.x = boxer->mediabox.max.x;
    box.max.y = boxer->mediabox.max.y;
    boxlist_feed_intersect(newlist, boxer->list, &box);

    /* Bottom (0,0) (W,min.y) */
    box.min.x = boxer->mediabox.min.x;
    box.min.y = boxer->mediabox.min.y;
    box.max.x = boxer->mediabox.max.x;
    box.max.y = bbox->min.y;
    boxlist_feed_intersect(newlist, boxer->list, &box);

    /* Top (0,max.y) (W,H) */
    box.min.x = boxer->mediabox.min.x;
    box.min.y = bbox->max.y;
    box.max.x = boxer->mediabox.max.x;
    box.max.y = boxer->mediabox.max.y;
    boxlist_feed_intersect(newlist, boxer->list, &box);

    extract_free(boxer->alloc, &boxer->list);
    boxer->list = newlist;

    return 0;
}

static int
compare_areas(const void *a_, const void *b_)
{
    const rect_t *a = (const rect_t *)a_;
    const rect_t *b = (const rect_t *)b_;
    double area_a = (a->max.x-a->min.x) * (a->max.y-a->min.y);
    double area_b = (b->max.x-b->min.x) * (b->max.y-b->min.y);

    if (area_a < area_b)
        return 1;
    else if (area_a > area_b)
        return -1;
    else
        return 0;
}

/* Sort the rectangle list to be largest area first. For ease of humans
 * reading debug output. */
static void boxer_sort(boxer_t *boxer)
{
    qsort(boxer->list->list, boxer->list->len, sizeof(rect_t), compare_areas);
}

/* Get the rectangle list for a given boxer. Return value is the length of
 * the list. Lifespan is until the boxer is modified or freed. */
static int boxer_results(boxer_t *boxer, rect_t **list)
{
    *list = boxer->list->list;
    return boxer->list->len;
}

/* Destroy a boxer. */
static void boxer_destroy(boxer_t *boxer)
{
    if (!boxer)
        return;

    extract_free(boxer->alloc, &boxer->list);
    extract_free(boxer->alloc, &boxer);
}

/* Find the margins for a given boxer. */
static rect_t boxer_margins(boxer_t *boxer)
{
    rectlist_t *list = boxer->list;
    int i;
    rect_t margins = boxer->mediabox;

    for (i = 0; i < list->len; i++)
    {
        rect_t *r = &list->list[i];
        if (r->min.x <= margins.min.x && r->min.y <= margins.min.y && r->max.y >= margins.max.y) {
            margins.min.x = r->max.x; /* Left Margin */
        } else if (r->max.x >= margins.max.x && r->min.y <= margins.min.y && r->max.y >= margins.max.y) {
            margins.max.x = r->min.x; /* Right Margin */
        } else if (r->min.x <= margins.min.x && r->max.x >= margins.max.x && r->min.y <= margins.min.y) {
            margins.min.y = r->max.y; /* Top Margin */
        } else if (r->min.x <= margins.min.x && r->max.x >= margins.max.x && r->max.y >= margins.max.y) {
            margins.max.y = r->min.y; /* Bottom Margin */
        }
    }

    return margins;
}

/* Create a new boxer from a subset of an old one. */
static boxer_t *boxer_subset(boxer_t *boxer, rect_t rect)
{
    boxer_t *new_boxer = boxer_create_length(boxer->alloc, &rect, boxer->list->len);
    int i;

    if (new_boxer == NULL)
        return NULL;

    for (i = 0; i < boxer->list->len; i++) {
        rect_t r = extract_rect_intersect(boxer->list->list[i], rect);

        if (!extract_rect_valid(r))
            continue;
        rectlist_append(new_boxer->list, &r);
    }

    return new_boxer;
}

/* Consider a boxer for subdivision.
 * Returns 0 if no suitable subdivision point found.
 * Returns 1, and sets *boxer1 and *boxer2 to new boxer structures for the the subdivisions
 * if a subdivision point is found.*/
static split_type_t
boxer_subdivide(boxer_t *boxer, boxer_t **boxer1, boxer_t **boxer2)
{
    rectlist_t *list = boxer->list;
    int num_h = 0, num_v = 0;
    double max_h = 0, max_v = 0;
    rect_t best_h = {0}, best_v = {0};
    int i;

    *boxer1 = NULL;
    *boxer2 = NULL;

    for (i = 0; i < list->len; i++) {
        rect_t r = boxer->list->list[i];

        if (r.min.x <= boxer->mediabox.min.x && r.max.x >= boxer->mediabox.max.x) {
            /* Horizontal divider */
            double size = r.max.y - r.min.y;
            if (size > max_h) {
                max_h = size;
                best_h = r;
            }
            num_h++;
        }
        if (r.min.y <= boxer->mediabox.min.y && r.max.y >= boxer->mediabox.max.y) {
            /* Vertical divider */
            double size = r.max.x - r.min.x;
            if (size > max_v) {
                max_v = size;
                best_v = r;
            }
            num_v++;
        }
    }

    outf("num_h=%d num_v=%d\n", num_h, num_v);
    outf("max_h=%g max_v=%g\n", max_h, max_v);

    if (max_h > max_v) {
        rect_t r;
        /* Divider runs horizontally. */
        r = boxer->mediabox;
        r.max.y = best_h.min.y;
        *boxer1 = boxer_subset(boxer, r);
        r = boxer->mediabox;
        r.min.y = best_h.max.y;
        *boxer2 = boxer_subset(boxer, r);
        return SPLIT_VERTICAL;
    } else if (max_v > 0) {
        rect_t r;
        /* Divider runs vertically. */
        r = boxer->mediabox;
        r.max.x = best_v.min.x;
        *boxer1 = boxer_subset(boxer, r);
        r = boxer->mediabox;
        r.min.x = best_v.max.x;
        *boxer2 = boxer_subset(boxer, r);
        return SPLIT_HORIZONTAL;
    }

    return SPLIT_NONE;
}


/* Extract specifics */
static rect_t
extract_span_bbox(span_t *span)
{
    int j;
    rect_t bbox = extract_rect_empty;

    for (j = 0; j < span->chars_num; j++)
    {
        char_t *char_ = &span->chars[j];
        bbox = extract_rect_union(bbox, char_->bbox);
    }
    return bbox;
}


static int
extract_subpage_subset(extract_alloc_t *alloc, extract_page_t *page, subpage_t *subpage, rect_t mediabox)
{
    subpage_t *target;
    int s;

    if (extract_subpage_alloc(alloc, mediabox, page, &target))
    {
        return -1;
    }

    for (s = 0; s < subpage->spans_num; s++)
    {
        rect_t bbox;
        span_t *span = subpage->spans[s];
        if (!span)
            continue;

        bbox = extract_span_bbox(span);

        if (bbox.min.x >= mediabox.min.x && bbox.min.y >= mediabox.min.y && bbox.max.x <= mediabox.max.x && bbox.max.y <= mediabox.max.y) {
            if (subpage_span_append(alloc, target, span))
            {
                return -1;
            }
            subpage->spans[s] = NULL;
        }
    }

    return 0;
}

enum {
    MAX_ANALYSIS_DEPTH = 6
};

static int
analyse_sub(extract_page_t *page, subpage_t *subpage, boxer_t *big_boxer, split_t **psplit, int depth)
{
    rect_t margins;
    boxer_t *boxer;
    boxer_t *boxer1;
    boxer_t *boxer2;
    int ret;
    split_type_t split_type;
    split_t *split;

    margins = boxer_margins(big_boxer);
#ifdef DEBUG_WRITE_AS_PS
    printf("\n\n%% MARGINS %g %g %g %g\n", margins.min.x, margins.min.y, margins.max.x, margins.max.y);
#endif

    boxer = boxer_subset(big_boxer, margins);

    if (depth < MAX_ANALYSIS_DEPTH &&
        (split_type = boxer_subdivide(boxer, &boxer1, &boxer2)) != SPLIT_NONE) {
        if (boxer1 == NULL || boxer2 == NULL ||
            extract_split_alloc(boxer->alloc, split_type, 2, psplit))
        {
            ret = -1;
            goto fail_mid_split;
        }
        split = *psplit;
        outf("depth=%d %s\n", depth, split_type == SPLIT_HORIZONTAL ? "H" : "V");
        ret = analyse_sub(page, subpage, boxer1, &split->split[0], depth+1);
        if (!ret) ret = analyse_sub(page, subpage, boxer2, &split->split[1], depth+1);
        if (!ret)
        {
            if (split_type == SPLIT_HORIZONTAL)
            {
                split->split[0]->weight = boxer1->mediabox.max.x - boxer1->mediabox.min.x;
                split->split[1]->weight = boxer2->mediabox.max.x - boxer2->mediabox.min.x;
            }
            else
            {
                split->split[0]->weight = boxer1->mediabox.max.y - boxer1->mediabox.min.y;
                split->split[1]->weight = boxer2->mediabox.max.y - boxer2->mediabox.min.y;
            }
        }
fail_mid_split:
        boxer_destroy(boxer1);
        boxer_destroy(boxer2);
        boxer_destroy(boxer);
        return ret;
    }

    outf("depth=%d LEAF\n", depth);

    if (extract_split_alloc(boxer->alloc, SPLIT_NONE, 0, psplit))
    {
        boxer_destroy(boxer);
        return -1;
    }
    split = *psplit;

    ret = extract_subpage_subset(boxer->alloc, page, subpage, boxer->mediabox);

#ifdef DEBUG_WRITE_AS_PS
    {
        int i, n;
        rect_t *list;
        boxer_sort(boxer);
        n = boxer_results(boxer, &list);

        printf("%% SUBDIVISION\n");
        for (i = 0; i < n; i++) {
            printf("%% %g %g %g %g\n",
                   list[i].min.x, list[i].min.y, list[i].max.x, list[i].max.y);
        }

        printf("0 0 0 setrgbcolor\n");
        for (i = 0; i < n; i++) {
            printf("%g %g moveto\n%g %g lineto\n%g %g lineto\n%g %g lineto\nclosepath\nstroke\n\n",
                   list[i].min.x, list[i].min.y,
                   list[i].min.x, list[i].max.y,
                   list[i].max.x, list[i].max.y,
                   list[i].max.x, list[i].min.y);
        }

        printf("1 0 0 setrgbcolor\n");
        printf("%g %g moveto\n%g %g lineto\n%g %g lineto\n%g %g lineto\nclosepath\nstroke\n\n",
               margins.min.x, margins.min.y,
               margins.min.x, margins.max.y,
               margins.max.x, margins.max.y,
               margins.max.x, margins.min.y);
    }
#endif
    boxer_destroy(boxer);

    return ret;
}


static int
collate_splits(extract_alloc_t *alloc, split_t **psplit)
{
    split_t *split = *psplit;
    int s;
    int n = 0;
    int i;
    int j;
    split_t *newsplit;

    /* Recurse into all our children to ensure they are collated.
     * Count how many children we'll have once we pull all the
     * children of children that match our type up into us. */
    for (s = 0; s < split->count; s++)
    {
        if (collate_splits(alloc, &split->split[s]))
        {
            return -1;
        }
        if (split->split[s]->type == split->type)
        {
            n += split->split[s]->count;
        }
        else
        {
            n++;
        }
    }

    /* No change in the number of children? Just exit. */
    if (n == split->count)
        return 0;

    if (extract_split_alloc(alloc, split->type, n, &newsplit))
    {
        return -1;
    }

    newsplit->weight = split->weight;

    /* Now, run across our children. */
    i = 0;
    for (s = 0; s < split->count; s++)
    {
        split_t *sub = split->split[s];
        if (sub->type == split->type)
        {
            /* If the type matches, pull the grandchildren into newsplit. */
            for (j = 0; j < sub->count; j++)
            {
                newsplit->split[i++] = sub->split[j];
                sub->split[j] = NULL;
            }
        }
        else
        {
            /* Otherwise just move the child into newsplit. */
            newsplit->split[i++] = sub;
            split->split[s] = NULL;
        }
    }

    extract_split_free(alloc, psplit);
    *psplit = newsplit;

    return 0;
}

int extract_page_analyse(extract_alloc_t *alloc, extract_page_t *page)
{
    boxer_t *boxer;
    int i;
    subpage_t *subpage = page->subpages[0];

    /* This code will only work if the page contains a single subpage.
     * This should always be the case if we're called from a page
     * generated via extract_page_begin. */
    if (page->subpages_num != 1) return 0;

    /* Take the old subpages out from the page. */
    page->subpages_num = 0;
    extract_free(alloc, &page->subpages);

#ifdef DEBUG_WRITE_AS_PS
    printf("1 -1 scale 0 -%g translate\n", page->mediabox.max.y-page->mediabox.min.y);
#endif

    boxer = boxer_create(alloc, (rect_t *)&subpage->mediabox);

    for (i = 0; i < subpage->spans_num; i++)
    {
        span_t *span = subpage->spans[i];
        rect_t bbox = extract_span_bbox(span);
        if (boxer_feed(boxer, &bbox))
        {
            goto fail;
        }
    }

    if (analyse_sub(page, subpage, boxer, &page->split, 0))
    {
        goto fail;
    }

    if (collate_splits(boxer->alloc, &page->split))
    {
        goto fail;
    }

#ifdef DEBUG_WRITE_AS_PS
    printf("showpage\n");
#endif

    boxer_destroy(boxer);
    extract_subpage_free(alloc, &subpage);

    return 0;

fail:
    outf("Analysis failed!\n");
    boxer_destroy(boxer);
    extract_subpage_free(alloc, &subpage);

    return -1;
}