← Back to branch summary

~ubuntu-branches/ubuntu/trusty/evince/trusty-proposed

« back to all changes in this revision

Viewing changes to djvu/djvu-text-page.c

Tags: upstream-0.5.1
Import upstream version 0.5.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
}