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