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