/* 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 */