backend/djvu/djvu-text-page.c

   1 /*
   2  * Implements search and copy functionality for Djvu files.
   3  * Copyright (C) 2006 Michael Hofmann <mh21@piware.de>
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2, or (at your option)
   8  * any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18  */
  19
  20 #include <config.h>
  21 #include <string.h>
  22 #include <glib.h>
  23 #include <libdjvu/miniexp.h>
  24 #include "djvu-text-page.h"
  25
  26
  27 /**
  28  * djvu_text_page_selection_process:
  29  * @page: #DjvuTextPage instance
  30  * @p: s-expression to append
  31  * @delimit: character/word/... delimiter
  32  *
  33  * Appends the string in @p to the page text.
  34  *
  35  * Returns: whether the end was not reached in this s-expression
  36  */
  37 static gboolean
  38 djvu_text_page_selection_process (DjvuTextPage *page,
  39                                   miniexp_t     p,
  40                                   int           delimit)
  41 {
  42         if (page->text || p == page->start) {
  43                 char *token_text = (char *) miniexp_to_str (miniexp_nth (5, p));
  44                 if (page->text) {
  45                         char *new_text =
  46                             g_strjoin (delimit & 2 ? "\n" :
  47                                        delimit & 1 ? " " : NULL,
  48                                        page->text, token_text,
  49                                        NULL);
  50                         g_free (page->text);
  51                         page->text = new_text;
  52                 } else
  53                         page->text = g_strdup (token_text);
  54                 if (p == page->end)
  55                         return FALSE;
  56         }
  57         return TRUE;
  58 }
  59
  60 /**
  61  * djvu_text_page_selection:
  62  * @page: #DjvuTextPage instance
  63  * @p: tree to append
  64  * @delimit: character/word/... delimiter
  65  *
  66  * Walks the tree in @p and appends the text with
  67  * djvu_text_page_selection_process() for all s-expressions
  68  * between the start and end fields.
  69  *
  70  * Returns: whether the end was not reached in this subtree
  71  */
  72 static gboolean
  73 djvu_text_page_selection (DjvuTextPage *page,
  74                           miniexp_t     p,
  75                           int           delimit)
  76 {
  77         g_return_val_if_fail (miniexp_consp (p) && miniexp_symbolp
  78                               (miniexp_car (p)), FALSE);
  79
  80         if (miniexp_car (p) != page->char_symbol)
  81                 delimit |= miniexp_car (p) == page->word_symbol ? 1 : 2;
  82
  83         miniexp_t deeper = miniexp_cddr (miniexp_cdddr (p));
  84         while (deeper != miniexp_nil) {
  85                 miniexp_t str = miniexp_car (deeper);
  86                 if (miniexp_stringp (str)) {
  87                         if (!djvu_text_page_selection_process
  88                             (page, p, delimit))
  89                                 return FALSE;
  90                 } else {
  91                         if (!djvu_text_page_selection
  92                             (page, str, delimit))
  93                                 return FALSE;
  94                 }
  95                 delimit = 0;
  96                 deeper = miniexp_cdr (deeper);
  97         }
  98         return TRUE;
  99 }
 100
 101 static void
 102 djvu_text_page_limits_process (DjvuTextPage *page,
 103                                miniexp_t     p,
 104                                EvRectangle  *rect)
 105 {
 106         EvRectangle current;
 107
 108         current.x1 = miniexp_to_int (miniexp_nth (1, p));
 109         current.y1 = miniexp_to_int (miniexp_nth (2, p));
 110         current.x2 = miniexp_to_int (miniexp_nth (3, p));
 111         current.y2 = miniexp_to_int (miniexp_nth (4, p));
 112         if (current.x2 >= rect->x1 && current.y1 <= rect->y2 &&
 113             current.x1 <= rect->x2 && current.y2 >= rect->y1) {
 114                 if (page->start == miniexp_nil)
 115                         page->start = p;
 116                 page->end = p;
 117         }
 118 }
 119
 120
 121 static void
 122 djvu_text_page_limits (DjvuTextPage *page,
 123                           miniexp_t     p,
 124                           EvRectangle  *rect)
 125 {
 126         char *token_text;
 127
 128         g_return_if_fail (miniexp_consp (p) &&
 129                           miniexp_symbolp (miniexp_car (p)));
 130
 131         miniexp_t deeper = miniexp_cddr (miniexp_cdddr (p));
 132         while (deeper != miniexp_nil) {
 133                 miniexp_t str = miniexp_car (deeper);
 134                 if (miniexp_stringp (str))
 135                         djvu_text_page_limits_process (page, p, rect);
 136                 else
 137                         djvu_text_page_limits (page, str, rect);
 138
 139                 deeper = miniexp_cdr (deeper);
 140         }
 141 }
 142
 143 char *
 144 djvu_text_page_copy (DjvuTextPage *page,
 145                      EvRectangle  *rectangle)
 146 {
 147         char* text;
 148
 149         page->start = miniexp_nil;
 150         page->end = miniexp_nil;
 151         djvu_text_page_limits (page, page->text_structure, rectangle);
 152         djvu_text_page_selection (page, page->text_structure, 0);
 153
 154         /* Do not free the string */
 155         text = page->text;
 156         page->text = NULL;
 157
 158         return text;
 159 }
 160
 161 /**
 162  * djvu_text_page_position:
 163  * @page: #DjvuTextPage instance
 164  * @position: index in the page text
 165  *
 166  * Returns the closest s-expression that contains the given position in
 167  * the page text.
 168  *
 169  * Returns: closest s-expression
 170  */
 171 static miniexp_t
 172 djvu_text_page_position (DjvuTextPage *page,
 173                          int           position)
 174 {
 175         GArray *links = page->links;
 176         int low = 0;
 177         int hi = links->len - 1;
 178         int mid = 0;
 179
 180         g_return_val_if_fail (hi >= 0, miniexp_nil);
 181
 182         /* Shamelessly copied from GNU classpath */
 183         while (low <= hi) {
 184                 mid = (low + hi) >> 1;
 185                 DjvuTextLink *link =
 186                     &g_array_index (links, DjvuTextLink, mid);
 187                 if (link->position == position)
 188                         break;
 189                 else if (link->position > position)
 190                         hi = --mid;
 191                 else
 192                         low = mid + 1;
 193         }
 194
 195         return g_array_index (page->links, DjvuTextLink, mid).pair;
 196 }
 197
 198 /**
 199  * djvu_text_page_union:
 200  * @target: first rectangle and result
 201  * @source: second rectangle
 202  *
 203  * Calculates the bounding box of two rectangles and stores the reuslt
 204  * in the first.
 205  */
 206 static void
 207 djvu_text_page_union (EvRectangle *target,
 208                       EvRectangle *source)
 209 {
 210         if (source->x1 < target->x1)
 211                 target->x1 = source->x1;
 212         if (source->x2 > target->x2)
 213                 target->x2 = source->x2;
 214         if (source->y1 < target->y1)
 215                 target->y1 = source->y1;
 216         if (source->y2 > target->y2)
 217                 target->y2 = source->y2;
 218 }
 219
 220 /**
 221  * djvu_text_page_sexpr_process:
 222  * @page: #DjvuTextPage instance
 223  * @p: s-expression to append
 224  * @start: first s-expression in the selection
 225  * @end: last s-expression in the selection
 226  *
 227  * Appends the rectangle defined by @p to the internal bounding box rectangle.
 228  *
 229  * Returns: whether the end was not reached in this s-expression
 230  */
 231 static gboolean
 232 djvu_text_page_sexpr_process (DjvuTextPage *page,
 233                               miniexp_t     p,
 234                               miniexp_t     start,
 235                               miniexp_t     end)
 236 {
 237         if (page->bounding_box || p == start) {
 238                 EvRectangle *new_rectangle = g_new (EvRectangle, 1);
 239                 new_rectangle->x1 = miniexp_to_int (miniexp_nth (1, p));
 240                 new_rectangle->y1 = miniexp_to_int (miniexp_nth (2, p));
 241                 new_rectangle->x2 = miniexp_to_int (miniexp_nth (3, p));
 242                 new_rectangle->y2 = miniexp_to_int (miniexp_nth (4, p));
 243                 if (page->bounding_box) {
 244                         djvu_text_page_union (page->bounding_box,
 245                                               new_rectangle);
 246                         g_free (new_rectangle);
 247                 } else
 248                         page->bounding_box = new_rectangle;
 249                 if (p == end)
 250                         return FALSE;
 251         }
 252         return TRUE;
 253 }
 254
 255 /**
 256  * djvu_text_page_sexpr:
 257  * @page: #DjvuTextPage instance
 258  * @p: tree to append
 259  * @start: first s-expression in the selection
 260  * @end: last s-expression in the selection
 261  *
 262  * Walks the tree in @p and extends the rectangle with
 263  * djvu_text_page_process() for all s-expressions between @start and @end.
 264  *
 265  * Returns: whether the end was not reached in this subtree
 266  */
 267 static gboolean
 268 djvu_text_page_sexpr (DjvuTextPage *page,
 269                       miniexp_t p,
 270                       miniexp_t start,
 271                       miniexp_t end)
 272 {
 273         g_return_val_if_fail (miniexp_consp (p) && miniexp_symbolp
 274                               (miniexp_car (p)), FALSE);
 275
 276         miniexp_t deeper = miniexp_cddr (miniexp_cdddr (p));
 277         while (deeper != miniexp_nil) {
 278                 miniexp_t str = miniexp_car (deeper);
 279                 if (miniexp_stringp (str)) {
 280                         if (!djvu_text_page_sexpr_process
 281                             (page, p, start, end))
 282                                 return FALSE;
 283                 } else {
 284                         if (!djvu_text_page_sexpr
 285                             (page, str, start, end))
 286                                 return FALSE;
 287                 }
 288                 deeper = miniexp_cdr (deeper);
 289         }
 290         return TRUE;
 291 }
 292
 293 /**
 294  * djvu_text_page_box:
 295  * @page: #DjvuTextPage instance
 296  * @start: first s-expression in the selection
 297  * @end: last s-expression in the selection
 298  *
 299  * Builds a rectangle that contains all s-expressions in the given range.
 300  */
 301 static EvRectangle *
 302 djvu_text_page_box (DjvuTextPage *page,
 303                     miniexp_t     start,
 304                     miniexp_t     end)
 305 {
 306         page->bounding_box = NULL;
 307         djvu_text_page_sexpr (page, page->text_structure, start, end);
 308         return page->bounding_box;
 309 }
 310
 311 /**
 312  * djvu_text_page_append_search:
 313  * @page: #DjvuTextPage instance
 314  * @p: tree to append
 315  * @case_sensitive: do not ignore case
 316  * @delimit: insert spaces because of higher (sentence/paragraph/...) break
 317  *
 318  * Appends the tree in @p to the internal text string.
 319  */
 320 static void
 321 djvu_text_page_append_text (DjvuTextPage *page,
 322                             miniexp_t     p,
 323                             gboolean      case_sensitive,
 324                             gboolean      delimit)
 325 {
 326         char *token_text;
 327
 328         g_return_if_fail (miniexp_consp (p) &&
 329                           miniexp_symbolp (miniexp_car (p)));
 330
 331         delimit |= page->char_symbol != miniexp_car (p);
 332
 333         miniexp_t deeper = miniexp_cddr (miniexp_cdddr (p));
 334         while (deeper != miniexp_nil) {
 335                 miniexp_t data = miniexp_car (deeper);
 336                 if (miniexp_stringp (data)) {
 337                         DjvuTextLink link;
 338                         link.position = page->text == NULL ? 0 :
 339                             strlen (page->text);
 340                         link.pair = p;
 341                         g_array_append_val (page->links, link);
 342
 343                         token_text = (char *) miniexp_to_str (data);
 344                         if (!case_sensitive)
 345                                 token_text = g_utf8_casefold (token_text, -1);
 346                         if (page->text == NULL)
 347                                 page->text = g_strdup (token_text);
 348                         else {
 349                                 char *new_text =
 350                                     g_strjoin (delimit ? " " : NULL,
 351                                                page->text, token_text,
 352                                                NULL);
 353                                 g_free (page->text);
 354                                 page->text = new_text;
 355                         }
 356                         if (!case_sensitive)
 357                                 g_free (token_text);
 358                 } else
 359                         djvu_text_page_append_text (page, data,
 360                                                     case_sensitive, delimit);
 361                 delimit = FALSE;
 362                 deeper = miniexp_cdr (deeper);
 363         }
 364 }
 365
 366 /**
 367  * djvu_text_page_search:
 368  * @page: #DjvuTextPage instance
 369  * @text: text to search
 370  *
 371  * Searches the page for the given text. The results list has to be
 372  * externally freed afterwards.
 373  */
 374 void
 375 djvu_text_page_search (DjvuTextPage *page,
 376                        char         *text)
 377 {
 378         char *haystack = page->text;
 379         int search_len;
 380         EvRectangle *result;
 381         if (page->links->len == 0)
 382                 return;
 383
 384         search_len = strlen (text);
 385         while ((haystack = strstr (haystack, text)) != NULL) {
 386                 int start_p = haystack - page->text;
 387                 miniexp_t start = djvu_text_page_position (page, start_p);
 388                 int end_p = start_p + search_len - 1;
 389                 miniexp_t end = djvu_text_page_position (page, end_p);
 390                 result = djvu_text_page_box (page, start, end);
 391                 g_assert (result);
 392                 page->results = g_list_prepend (page->results, result);
 393                 haystack = haystack + search_len;
 394         }
 395         page->results = g_list_reverse (page->results);
 396 }
 397
 398
 399 /**
 400  * djvu_text_page_prepare_search:
 401  * @page: #DjvuTextPage instance
 402  * @case_sensitive: do not ignore case
 403  *
 404  * Indexes the page text and prepares the page for subsequent searches.
 405  */
 406 void
 407 djvu_text_page_prepare_search (DjvuTextPage *page,
 408                                gboolean      case_sensitive)
 409 {
 410         djvu_text_page_append_text (page, page->text_structure,
 411                                     case_sensitive, FALSE);
 412 }
 413
 414 /**
 415  * djvu_text_page_new:
 416  * @text: S-expression of the page text
 417  *
 418  * Creates a new page to search.
 419  *
 420  * Returns: new #DjvuTextPage instance
 421  */
 422 DjvuTextPage *
 423 djvu_text_page_new (miniexp_t text)
 424 {
 425         DjvuTextPage *page;
 426
 427         page = g_new0 (DjvuTextPage, 1);
 428         page->links = g_array_new (FALSE, FALSE, sizeof (DjvuTextLink));
 429         page->char_symbol = miniexp_symbol ("char");
 430         page->word_symbol = miniexp_symbol ("word");
 431         page->text_structure = text;
 432         return page;
 433 }
 434
 435 /**
 436  * djvu_text_page_free:
 437  * @page: #DjvuTextPage instance
 438  *
 439  * Frees the given #DjvuTextPage instance.
 440  */
 441 void
 442 djvu_text_page_free (DjvuTextPage *page)
 443 {
 444         g_free (page->text);
 445         g_array_free (page->links, TRUE);
 446         g_free (page);
 447 }