/* minidjvu - library for handling bilevel images with DjVuBitonal support

 *

 * classify.c - classifying patterns

 *

 * Copyright (C) 2005  Ilya Mezhirov

 *

 * 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 *

 * 

 * minidjvu is derived from DjVuLibre (http://djvu.sourceforge.net)

 * All over DjVuLibre there is a patent alert from LizardTech

 * which I guess I should reproduce (don't ask me what does this mean):

 * 

 *  ------------------------------------------------------------------

 * | DjVu (r) Reference Library (v. 3.5)

 * | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.

 * | The DjVu Reference Library is protected by U.S. Pat. No.

 * | 6,058,214 and patents pending.

 * |

 * | This software is subject to, and may be distributed under, the

 * | GNU General Public License, either Version 2 of the license,

 * | or (at your option) any later version. The license should have

 * | accompanied the software or you may obtain a copy of the license

 * | from the Free Software Foundation at http://www.fsf.org .

 * |

 * | The computer code originally released by LizardTech under this

 * | license and unmodified by other parties is deemed "the LIZARDTECH

 * | ORIGINAL CODE."  Subject to any third party intellectual property

 * | claims, LizardTech grants recipient a worldwide, royalty-free, 

 * | non-exclusive license to make, use, sell, or otherwise dispose of 

 * | the LIZARDTECH ORIGINAL CODE or of programs derived from the 

 * | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU 

 * | General Public License.   This grant only confers the right to 

 * | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to 

 * | the extent such infringement is reasonably necessary to enable 

 * | recipient to make, have made, practice, sell, or otherwise dispose 

 * | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to 

 * | any greater extent that may be necessary to utilize further 

 * | modifications or combinations.

 * |

 * | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY

 * | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED

 * | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF

 * | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

 * +------------------------------------------------------------------

 */

#include "mdjvucfg.h"

#include "minidjvu.h"

#include <stdlib.h>

/* Stuff for not using malloc in C++

 * (made by Leon Bottou; has no use in minidjvu,

 * but left here for potential DjVuLibre compatibility)

 */

#ifdef __cplusplus

# define MALLOC(Type)    new Type

# define FREE(p)         delete p

# define MALLOCV(Type,n) new Type[n]

# define FREEV(p)        delete [] p

#else

# define MALLOC(Type)    ((Type*)malloc(sizeof(Type)))

# define FREE(p)         do{if(p)free(p);}while(0)

# define MALLOCV(Type,n) ((Type*)malloc(sizeof(Type)*(n)))

# define FREEV(p)        do{if(p)free(p);}while(0)

#endif

/* Classes are single-linked lists with an additional pointer to the last node.

 * This is an class item.

 */

typedef struct ClassNode

{

    mdjvu_pattern_t ptr;

    struct ClassNode *next;        /* NULL if this node is the last one */

    struct ClassNode *global_next; /* next among all nodes to classify  */

    int32 tag;                     /* filled before the final dumping   */

} ClassNode;

/* Classes themselves are composed in double-linked list. */

typedef struct Class

{

    ClassNode *first, *last;

    struct Class *prev_class;

    struct Class *next_class;

} Class;

typedef struct Classification

{

    Class *first_class;

    ClassNode *first_node, *last_node;

} Classification;

/* Creates an empty class and links it to the list of classes. */

static Class *new_class(Classification *cl)

{

    Class *c = MALLOC(Class);

    c->first = c->last = NULL;

    c->prev_class = NULL;

    c->next_class = cl->first_class;

    if (cl->first_class) cl->first_class->prev_class = c;

    cl->first_class = c;

    return c;

}

/* Unlinks a class and deletes it. Its nodes are not deleted. */

static void delete_class(Classification *cl, Class *c)

{

    Class *prev = c->prev_class, *next = c->next_class;

    if (prev)

        prev->next_class = next;

    else

        cl->first_class = next;

    if (next)

        next->prev_class = prev;

    FREE(c);

}

/* Creates a new node and adds it to the given class. */

static ClassNode *new_node(Classification *cl, Class *c, mdjvu_pattern_t ptr)

{

    ClassNode *n = MALLOC(ClassNode);

    n->ptr = ptr;

    n->next = c->first;

    c->first = n;

    if (!c->last) c->last = n;

    n->global_next = NULL;

    if (cl->last_node)

        cl->last_node->global_next = n;

    else

        cl->first_node = n;

    cl->last_node = n;

    return n;

}

/* Merge two classes and delete one of them. */

static Class *merge(Classification *cl, Class *c1, Class *c2)

{

    if (!c1->first)

    {

        delete_class(cl, c1);

        return c2;

    }

    if (c2->first)

    {

        c1->last->next = c2->first;

        c1->last = c2->last;

    }

    delete_class(cl, c2);

    return c1;

}

/* Puts a tag on each node corresponding to its class. */

static unsigned put_tags(Classification *cl)

{

    int32 tag = 1;

    Class *c = cl->first_class;

    while (c)

    {

        ClassNode *n = c->first;

        while (n)

        {

            n->tag = tag;

            n = n->next;

        }

        c = c->next_class;

        tag++;

    }

    return tag - 1;

}

/* Deletes all classes; nodes are untouched. */

static void delete_all_classes(Classification *cl)

{

    Class *c = cl->first_class;

    while (c)

    {

        Class *t = c;

        c = c->next_class;

        FREE(t);

    }

}

/* Compares p with nodes from c until a meaningful result. */

static int compare_to_class(mdjvu_pattern_t p, Class *c, int32 dpi,

                            mdjvu_matcher_options_t options)

{

    int r = 0;

    ClassNode *n = c->first;

    while(n)

    {

        r = mdjvu_match_patterns(p, n->ptr, dpi, options);

        if (r) break;

        n = n->next;

    }

    return r;

}

static void classify(Classification *cl, mdjvu_pattern_t p,

                     int32 dpi, mdjvu_matcher_options_t options)

{

    Class *class_of_this = NULL;

    Class *c, *next_c = NULL;

    for (c = cl->first_class; c; c = next_c)

    {

        next_c = c->next_class; /* That's because c may be deleted in merging */

        if (class_of_this == c) continue;

        if (compare_to_class(p, c, dpi, options) != 1) continue;

        if (class_of_this)

            class_of_this = merge(cl, class_of_this, c);

        else

            class_of_this = c;

    }

    if (!class_of_this) class_of_this = new_class(cl);

    new_node(cl, class_of_this, p);

}

MDJVU_IMPLEMENT int32 mdjvu_classify_patterns

    (mdjvu_pattern_t *b, int32 *r, int32 n, int32 dpi,

     mdjvu_matcher_options_t options)

{

    int32 i, max_tag;

    ClassNode *node;

    Classification cl;

    cl.first_class = NULL;

    cl.first_node = cl.last_node = NULL;

    for (i = 0; i < n; i++) if (b[i]) classify(&cl, b[i], dpi, options);

    max_tag = put_tags(&cl);

    delete_all_classes(&cl);

    i = 0;

    node = cl.first_node;

    while (node)

    {

        ClassNode *t;

        while (!b[i]) r[i++] = 0;

        r[i++] = node->tag;

        t = node;

        node = node->global_next;

        FREE(t);

    }

    if (i < n) while (i < n) r[i++] = 0;

    return max_tag;

}

#ifndef NO_MINIDJVU

MDJVU_IMPLEMENT int32 mdjvu_classify_bitmaps_in_image

    (mdjvu_image_t image, int32 *result, mdjvu_matcher_options_t options)

{

    int32 i, n = mdjvu_image_get_bitmap_count(image);

    int32 dpi = mdjvu_image_get_resolution(image);

    mdjvu_pattern_t *patterns = MALLOCV(mdjvu_pattern_t, n);

    int32 max_tag;

    for (i = 0; i < n; i++)

    {

        mdjvu_bitmap_t bitmap = mdjvu_image_get_bitmap(image, i);

        if (mdjvu_image_get_no_substitution_flag(image, bitmap))

            patterns[i] = NULL;

        else

            patterns[i] = mdjvu_pattern_create(bitmap);

    }

    max_tag = mdjvu_classify_patterns(patterns, result, n, dpi, options);

    for (i = 0; i < n; i++)

        if (patterns[i]) mdjvu_pattern_destroy(patterns[i]);

    FREEV(patterns);

    return max_tag;

}

#endif /* NO_MINIDJVU */