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