source: trunk/poppler/mypoppler/poppler/TextOutputDev.cc @ 497

Last change on this file since 497 was 497, checked in by Silvan Scherrer, 10 years ago

Lucide: updated fontconfig and poppler

File size: 137.8 KB
Line 
1//========================================================================
2//
3// TextOutputDev.cc
4//
5// Copyright 1997-2003 Glyph & Cog, LLC
6//
7//========================================================================
8
9//========================================================================
10//
11// Modified under the Poppler project - http://poppler.freedesktop.org
12//
13// All changes made under the Poppler project to this file are licensed
14// under GPL version 2 or later
15//
16// Copyright (C) 2005-2007 Kristian HÞgsberg <krh@redhat.com>
17// Copyright (C) 2005 Nickolay V. Shmyrev <nshmyrev@yandex.ru>
18// Copyright (C) 2006-2008, 2011 Carlos Garcia Campos <carlosgc@gnome.org>
19// Copyright (C) 2006, 2007 Ed Catmur <ed@catmur.co.uk>
20// Copyright (C) 2006 Jeff Muizelaar <jeff@infidigm.net>
21// Copyright (C) 2007, 2008 Adrian Johnson <ajohnson@redneon.com>
22// Copyright (C) 2008 Koji Otani <sho@bbr.jp>
23// Copyright (C) 2008, 2010, 2011 Albert Astals Cid <aacid@kde.org>
24// Copyright (C) 2008 Pino Toscano <pino@kde.org>
25// Copyright (C) 2008, 2010 Hib Eris <hib@hiberis.nl>
26// Copyright (C) 2009 Ross Moore <ross@maths.mq.edu.au>
27// Copyright (C) 2009 Kovid Goyal <kovid@kovidgoyal.net>
28// Copyright (C) 2010 Brian Ewins <brian.ewins@gmail.com>
29// Copyright (C) 2010 Suzuki Toshiya <mpsuzuki@hiroshima-u.ac.jp>
30// Copyright (C) 2011 Sam Liao <phyomh@gmail.com>
31//
32// To see a description of the changes please see the Changelog file that
33// came with your tarball or type make ChangeLog if you are building from git
34//
35//========================================================================
36
37#include <config.h>
38
39#ifdef USE_GCC_PRAGMAS
40#pragma implementation
41#endif
42
43#include <stdio.h>
44#include <stdlib.h>
45#include <stddef.h>
46#include <math.h>
47#include <float.h>
48#include <ctype.h>
49#ifdef _WIN32
50#include <fcntl.h> // for O_BINARY
51#include <io.h>    // for setmode
52#endif
53#include "goo/gmem.h"
54#include "goo/GooString.h"
55#include "goo/GooList.h"
56#include "poppler-config.h"
57#include "Error.h"
58#include "GlobalParams.h"
59#include "UnicodeMap.h"
60#include "UnicodeTypeTable.h"
61#include "Link.h"
62#include "TextOutputDev.h"
63#include "Page.h"
64#include "Annot.h"
65#include "PDFDocEncoding.h"
66
67#ifdef MACOS
68// needed for setting type/creator of MacOS files
69#include "ICSupport.h"
70#endif
71
72//------------------------------------------------------------------------
73// parameters
74//------------------------------------------------------------------------
75
76// Each bucket in a text pool includes baselines within a range of
77// this many points.
78#define textPoolStep 4
79
80// Inter-character space width which will cause addChar to start a new
81// word.
82#define minWordBreakSpace 0.1
83
84// Negative inter-character space width, i.e., overlap, which will
85// cause addChar to start a new word.
86#define minDupBreakOverlap 0.2
87
88// Max distance between baselines of two lines within a block, as a
89// fraction of the font size.
90#define maxLineSpacingDelta 1.5
91
92// Max difference in primary font sizes on two lines in the same
93// block.  Delta1 is used when examining new lines above and below the
94// current block; delta2 is used when examining text that overlaps the
95// current block; delta3 is used when examining text to the left and
96// right of the current block.
97#define maxBlockFontSizeDelta1 0.05
98#define maxBlockFontSizeDelta2 0.6
99#define maxBlockFontSizeDelta3 0.2
100
101// Max difference in font sizes inside a word.
102#define maxWordFontSizeDelta 0.05
103
104// Maximum distance between baselines of two words on the same line,
105// e.g., distance between subscript or superscript and the primary
106// baseline, as a fraction of the font size.
107#define maxIntraLineDelta 0.5
108
109// Minimum inter-word spacing, as a fraction of the font size.  (Only
110// used for raw ordering.)
111#define minWordSpacing 0.15
112
113// Maximum inter-word spacing, as a fraction of the font size.
114#define maxWordSpacing 1.5
115
116// Maximum horizontal spacing which will allow a word to be pulled
117// into a block.
118#define minColSpacing1 0.3
119
120// Minimum spacing between columns, as a fraction of the font size.
121#define minColSpacing2 1.0
122
123// Maximum vertical spacing between blocks within a flow, as a
124// multiple of the font size.
125#define maxBlockSpacing 2.5
126
127// Minimum spacing between characters within a word, as a fraction of
128// the font size.
129#define minCharSpacing -0.2
130
131// Maximum spacing between characters within a word, as a fraction of
132// the font size, when there is no obvious extra-wide character
133// spacing.
134#define maxCharSpacing 0.03
135
136// When extra-wide character spacing is detected, the inter-character
137// space threshold is set to the minimum inter-character space
138// multiplied by this constant.
139#define maxWideCharSpacingMul 1.3
140
141// Upper limit on spacing between characters in a word.
142#define maxWideCharSpacing 0.4
143
144// Max difference in primary,secondary coordinates (as a fraction of
145// the font size) allowed for duplicated text (fake boldface, drop
146// shadows) which is to be discarded.
147#define dupMaxPriDelta 0.1
148#define dupMaxSecDelta 0.2
149
150// Max width of underlines (in points).
151#define maxUnderlineWidth 3
152
153// Min distance between baseline and underline (in points).
154//~ this should be font-size-dependent
155#define minUnderlineGap -2
156
157// Max distance between baseline and underline (in points).
158//~ this should be font-size-dependent
159#define maxUnderlineGap 4
160
161// Max horizontal distance between edge of word and start of underline
162// (in points).
163//~ this should be font-size-dependent
164#define underlineSlack 1
165
166// Max distance between edge of text and edge of link border
167#define hyperlinkSlack 2
168
169//------------------------------------------------------------------------
170// TextUnderline
171//------------------------------------------------------------------------
172
173class TextUnderline {
174public:
175
176  TextUnderline(double x0A, double y0A, double x1A, double y1A)
177    { x0 = x0A; y0 = y0A; x1 = x1A; y1 = y1A; horiz = y0 == y1; }
178  ~TextUnderline() {}
179
180  double x0, y0, x1, y1;
181  GBool horiz;
182};
183
184//------------------------------------------------------------------------
185// TextLink
186//------------------------------------------------------------------------
187
188class TextLink {
189public:
190
191  TextLink(int xMinA, int yMinA, int xMaxA, int yMaxA, AnnotLink *linkA)
192    { xMin = xMinA; yMin = yMinA; xMax = xMaxA; yMax = yMaxA; link = linkA; }
193  ~TextLink() {}
194
195  int xMin, yMin, xMax, yMax;
196  AnnotLink *link;
197};
198
199//------------------------------------------------------------------------
200// TextFontInfo
201//------------------------------------------------------------------------
202
203TextFontInfo::TextFontInfo(GfxState *state) {
204  gfxFont = state->getFont();
205  if (gfxFont)
206    gfxFont->incRefCnt();
207#if TEXTOUT_WORD_LIST
208  fontName = (gfxFont && gfxFont->getOrigName())
209                 ? gfxFont->getOrigName()->copy()
210                 : (GooString *)NULL;
211  flags = gfxFont ? gfxFont->getFlags() : 0;
212#endif
213}
214
215TextFontInfo::~TextFontInfo() {
216  if (gfxFont)
217    gfxFont->decRefCnt();
218#if TEXTOUT_WORD_LIST
219  if (fontName) {
220    delete fontName;
221  }
222#endif
223}
224
225GBool TextFontInfo::matches(GfxState *state) {
226  return state->getFont() == gfxFont;
227}
228
229GBool TextFontInfo::matches(TextFontInfo *fontInfo) {
230  return gfxFont == fontInfo->gfxFont;
231}
232
233//------------------------------------------------------------------------
234// TextWord
235//------------------------------------------------------------------------
236
237TextWord::TextWord(GfxState *state, int rotA, double x0, double y0,
238                   int charPosA, TextFontInfo *fontA, double fontSizeA) {
239  GfxFont *gfxFont;
240  double x, y, ascent, descent;
241
242  rot = rotA;
243  charPos = charPosA;
244  charLen = 0;
245  font = fontA;
246  fontSize = fontSizeA;
247  state->transform(x0, y0, &x, &y);
248  if ((gfxFont = font->gfxFont)) {
249    ascent = gfxFont->getAscent() * fontSize;
250    descent = gfxFont->getDescent() * fontSize;
251  } else {
252    // this means that the PDF file draws text without a current font,
253    // which should never happen
254    ascent = 0.95 * fontSize;
255    descent = -0.35 * fontSize;
256  }
257  switch (rot) {
258  case 0:
259    yMin = y - ascent;
260    yMax = y - descent;
261    if (yMin == yMax) {
262      // this is a sanity check for a case that shouldn't happen -- but
263      // if it does happen, we want to avoid dividing by zero later
264      yMin = y;
265      yMax = y + 1;
266    }
267    base = y;
268    break;
269  case 1:
270    xMin = x + descent;
271    xMax = x + ascent;
272    if (xMin == xMax) {
273      // this is a sanity check for a case that shouldn't happen -- but
274      // if it does happen, we want to avoid dividing by zero later
275      xMin = x;
276      xMax = x + 1;
277    }
278    base = x;
279    break;
280  case 2:
281    yMin = y + descent;
282    yMax = y + ascent;
283    if (yMin == yMax) {
284      // this is a sanity check for a case that shouldn't happen -- but
285      // if it does happen, we want to avoid dividing by zero later
286      yMin = y;
287      yMax = y + 1;
288    }
289    base = y;
290    break;
291  case 3:
292    xMin = x - ascent;
293    xMax = x - descent;
294    if (xMin == xMax) {
295      // this is a sanity check for a case that shouldn't happen -- but
296      // if it does happen, we want to avoid dividing by zero later
297      xMin = x;
298      xMax = x + 1;
299    }
300    base = x;
301    break;
302  }
303  text = NULL;
304  charcode = NULL;
305  edge = NULL;
306  len = size = 0;
307  spaceAfter = gFalse;
308  next = NULL;
309
310#if TEXTOUT_WORD_LIST
311  GfxRGB rgb;
312
313  if ((state->getRender() & 3) == 1) {
314    state->getStrokeRGB(&rgb);
315  } else {
316    state->getFillRGB(&rgb);
317  }
318  colorR = colToDbl(rgb.r);
319  colorG = colToDbl(rgb.g);
320  colorB = colToDbl(rgb.b);
321#endif
322
323  underlined = gFalse;
324  link = NULL;
325}
326
327TextWord::~TextWord() {
328  gfree(text);
329  gfree(charcode);
330  gfree(edge);
331}
332
333void TextWord::addChar(GfxState *state, double x, double y,
334                       double dx, double dy, CharCode c, Unicode u) {
335  if (len == size) {
336    size += 16;
337    text = (Unicode *)greallocn(text, size, sizeof(Unicode));
338    charcode = (Unicode *)greallocn(charcode, size, sizeof(CharCode));
339    edge = (double *)greallocn(edge, (size + 1), sizeof(double));
340  }
341  text[len] = u;
342  charcode[len] = c;
343  switch (rot) {
344  case 0:
345    if (len == 0) {
346      xMin = x;
347    }
348    edge[len] = x;
349    xMax = edge[len+1] = x + dx;
350    break;
351  case 1:
352    if (len == 0) {
353      yMin = y;
354    }
355    edge[len] = y;
356    yMax = edge[len+1] = y + dy;
357    break;
358  case 2:
359    if (len == 0) {
360      xMax = x;
361    }
362    edge[len] = x;
363    xMin = edge[len+1] = x + dx;
364    break;
365  case 3:
366    if (len == 0) {
367      yMax = y;
368    }
369    edge[len] = y;
370    yMin = edge[len+1] = y + dy;
371    break;
372  }
373  ++len;
374}
375
376void TextWord::merge(TextWord *word) {
377  int i;
378
379  if (word->xMin < xMin) {
380    xMin = word->xMin;
381  }
382  if (word->yMin < yMin) {
383    yMin = word->yMin;
384  }
385  if (word->xMax > xMax) {
386    xMax = word->xMax;
387  }
388  if (word->yMax > yMax) {
389    yMax = word->yMax;
390  }
391  if (len + word->len > size) {
392    size = len + word->len;
393    text = (Unicode *)greallocn(text, size, sizeof(Unicode));
394    charcode = (CharCode *)greallocn(charcode, (size + 1), sizeof(CharCode));
395    edge = (double *)greallocn(edge, (size + 1), sizeof(double));
396  }
397  for (i = 0; i < word->len; ++i) {
398    text[len + i] = word->text[i];
399    charcode[len + i] = word->charcode[i];
400    edge[len + i] = word->edge[i];
401  }
402  edge[len + word->len] = word->edge[word->len];
403  len += word->len;
404  charLen += word->charLen;
405}
406
407inline int TextWord::primaryCmp(TextWord *word) {
408  double cmp;
409
410  cmp = 0; // make gcc happy
411  switch (rot) {
412  case 0:
413    cmp = xMin - word->xMin;
414    break;
415  case 1:
416    cmp = yMin - word->yMin;
417    break;
418  case 2:
419    cmp = word->xMax - xMax;
420    break;
421  case 3:
422    cmp = word->yMax - yMax;
423    break;
424  }
425  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
426}
427
428double TextWord::primaryDelta(TextWord *word) {
429  double delta;
430
431  delta = 0; // make gcc happy
432  switch (rot) {
433  case 0:
434    delta = word->xMin - xMax;
435    break;
436  case 1:
437    delta = word->yMin - yMax;
438    break;
439  case 2:
440    delta = xMin - word->xMax;
441    break;
442  case 3:
443    delta = yMin - word->yMax;
444    break;
445  }
446  return delta;
447}
448
449int TextWord::cmpYX(const void *p1, const void *p2) {
450  TextWord *word1 = *(TextWord **)p1;
451  TextWord *word2 = *(TextWord **)p2;
452  double cmp;
453
454  cmp = word1->yMin - word2->yMin;
455  if (cmp == 0) {
456    cmp = word1->xMin - word2->xMin;
457  }
458  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
459}
460
461#if TEXTOUT_WORD_LIST
462
463GooString *TextWord::getText() {
464  GooString *s;
465  UnicodeMap *uMap;
466  char buf[8];
467  int n, i;
468
469  s = new GooString();
470  if (!(uMap = globalParams->getTextEncoding())) {
471    return s;
472  }
473  for (i = 0; i < len; ++i) {
474    n = uMap->mapUnicode(text[i], buf, sizeof(buf));
475    s->append(buf, n);
476  }
477  uMap->decRefCnt();
478  return s;
479}
480
481void TextWord::getCharBBox(int charIdx, double *xMinA, double *yMinA,
482                           double *xMaxA, double *yMaxA) {
483  if (charIdx < 0 || charIdx >= len) {
484    return;
485  }
486  switch (rot) {
487  case 0:
488    *xMinA = edge[charIdx];
489    *xMaxA = edge[charIdx + 1];
490    *yMinA = yMin;
491    *yMaxA = yMax;
492    break;
493  case 1:
494    *xMinA = xMin;
495    *xMaxA = xMax;
496    *yMinA = edge[charIdx];
497    *yMaxA = edge[charIdx + 1];
498    break;
499  case 2:
500    *xMinA = edge[charIdx + 1];
501    *xMaxA = edge[charIdx];
502    *yMinA = yMin;
503    *yMaxA = yMax;
504    break;
505  case 3:
506    *xMinA = xMin;
507    *xMaxA = xMax;
508    *yMinA = edge[charIdx + 1];
509    *yMaxA = edge[charIdx];
510    break;
511  }
512}
513
514#endif // TEXTOUT_WORD_LIST
515
516//------------------------------------------------------------------------
517// TextPool
518//------------------------------------------------------------------------
519
520TextPool::TextPool() {
521  minBaseIdx = 0;
522  maxBaseIdx = -1;
523  pool = NULL;
524  cursor = NULL;
525  cursorBaseIdx = -1;
526}
527
528TextPool::~TextPool() {
529  int baseIdx;
530  TextWord *word, *word2;
531
532  for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
533    for (word = pool[baseIdx - minBaseIdx]; word; word = word2) {
534      word2 = word->next;
535      delete word;
536    }
537  }
538  gfree(pool);
539}
540
541int TextPool::getBaseIdx(double base) {
542  int baseIdx;
543
544  baseIdx = (int)(base / textPoolStep);
545  if (baseIdx < minBaseIdx) {
546    return minBaseIdx;
547  }
548  if (baseIdx > maxBaseIdx) {
549    return maxBaseIdx;
550  }
551  return baseIdx;
552}
553
554void TextPool::addWord(TextWord *word) {
555  TextWord **newPool;
556  int wordBaseIdx, newMinBaseIdx, newMaxBaseIdx, baseIdx;
557  TextWord *w0, *w1;
558
559  // expand the array if needed
560  wordBaseIdx = (int)(word->base / textPoolStep);
561  if (minBaseIdx > maxBaseIdx) {
562    minBaseIdx = wordBaseIdx - 128;
563    maxBaseIdx = wordBaseIdx + 128;
564    pool = (TextWord **)gmallocn(maxBaseIdx - minBaseIdx + 1,
565                                 sizeof(TextWord *));
566    for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
567      pool[baseIdx - minBaseIdx] = NULL;
568    }
569  } else if (wordBaseIdx < minBaseIdx) {
570    newMinBaseIdx = wordBaseIdx - 128;
571    newPool = (TextWord **)gmallocn(maxBaseIdx - newMinBaseIdx + 1,
572                                    sizeof(TextWord *));
573    for (baseIdx = newMinBaseIdx; baseIdx < minBaseIdx; ++baseIdx) {
574      newPool[baseIdx - newMinBaseIdx] = NULL;
575    }
576    memcpy(&newPool[minBaseIdx - newMinBaseIdx], pool,
577           (maxBaseIdx - minBaseIdx + 1) * sizeof(TextWord *));
578    gfree(pool);
579    pool = newPool;
580    minBaseIdx = newMinBaseIdx;
581  } else if (wordBaseIdx > maxBaseIdx) {
582    newMaxBaseIdx = wordBaseIdx + 128;
583    pool = (TextWord **)greallocn(pool, newMaxBaseIdx - minBaseIdx + 1,
584                                  sizeof(TextWord *));
585    for (baseIdx = maxBaseIdx + 1; baseIdx <= newMaxBaseIdx; ++baseIdx) {
586      pool[baseIdx - minBaseIdx] = NULL;
587    }
588    maxBaseIdx = newMaxBaseIdx;
589  }
590
591  // insert the new word
592  if (cursor && wordBaseIdx == cursorBaseIdx &&
593      word->primaryCmp(cursor) > 0) {
594    w0 = cursor;
595    w1 = cursor->next;
596  } else {
597    w0 = NULL;
598    w1 = pool[wordBaseIdx - minBaseIdx];
599  }
600  for (; w1 && word->primaryCmp(w1) > 0; w0 = w1, w1 = w1->next) ;
601  word->next = w1;
602  if (w0) {
603    w0->next = word;
604  } else {
605    pool[wordBaseIdx - minBaseIdx] = word;
606  }
607  cursor = word;
608  cursorBaseIdx = wordBaseIdx;
609}
610
611//------------------------------------------------------------------------
612// TextLine
613//------------------------------------------------------------------------
614
615TextLine::TextLine(TextBlock *blkA, int rotA, double baseA) {
616  blk = blkA;
617  rot = rotA;
618  base = baseA;
619  words = lastWord = NULL;
620  text = NULL;
621  edge = NULL;
622  col = NULL;
623  len = 0;
624  convertedLen = 0;
625  hyphenated = gFalse;
626  next = NULL;
627  xMin = yMin = 0;
628  xMax = yMax = -1;
629  normalized = NULL;
630  normalized_len = 0;
631  normalized_idx = NULL;
632}
633
634TextLine::~TextLine() {
635  TextWord *word;
636
637  while (words) {
638    word = words;
639    words = words->next;
640    delete word;
641  }
642  gfree(text);
643  gfree(edge);
644  gfree(col);
645  if (normalized) {
646    gfree(normalized);
647    gfree(normalized_idx);
648  }
649}
650
651void TextLine::addWord(TextWord *word) {
652  if (lastWord) {
653    lastWord->next = word;
654  } else {
655    words = word;
656  }
657  lastWord = word;
658
659  if (xMin > xMax) {
660    xMin = word->xMin;
661    xMax = word->xMax;
662    yMin = word->yMin;
663    yMax = word->yMax;
664  } else {
665    if (word->xMin < xMin) {
666      xMin = word->xMin;
667    }
668    if (word->xMax > xMax) {
669      xMax = word->xMax;
670    }
671    if (word->yMin < yMin) {
672      yMin = word->yMin;
673    }
674    if (word->yMax > yMax) {
675      yMax = word->yMax;
676    }
677  }
678}
679
680double TextLine::primaryDelta(TextLine *line) {
681  double delta;
682
683  delta = 0; // make gcc happy
684  switch (rot) {
685  case 0:
686    delta = line->xMin - xMax;
687    break;
688  case 1:
689    delta = line->yMin - yMax;
690    break;
691  case 2:
692    delta = xMin - line->xMax;
693    break;
694  case 3:
695    delta = yMin - line->yMax;
696    break;
697  }
698  return delta;
699}
700
701int TextLine::primaryCmp(TextLine *line) {
702  double cmp;
703
704  cmp = 0; // make gcc happy
705  switch (rot) {
706  case 0:
707    cmp = xMin - line->xMin;
708    break;
709  case 1:
710    cmp = yMin - line->yMin;
711    break;
712  case 2:
713    cmp = line->xMax - xMax;
714    break;
715  case 3:
716    cmp = line->yMax - yMax;
717    break;
718  }
719  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
720}
721
722int TextLine::secondaryCmp(TextLine *line) {
723  double cmp;
724
725  cmp = (rot == 0 || rot == 3) ? base - line->base : line->base - base;
726  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
727}
728
729int TextLine::cmpYX(TextLine *line) {
730  int cmp;
731
732  if ((cmp = secondaryCmp(line))) {
733    return cmp;
734  }
735  return primaryCmp(line);
736}
737
738int TextLine::cmpXY(const void *p1, const void *p2) {
739  TextLine *line1 = *(TextLine **)p1;
740  TextLine *line2 = *(TextLine **)p2;
741  int cmp;
742
743  if ((cmp = line1->primaryCmp(line2))) {
744    return cmp;
745  }
746  return line1->secondaryCmp(line2);
747}
748
749void TextLine::coalesce(UnicodeMap *uMap) {
750  TextWord *word0, *word1;
751  double space, delta, minSpace;
752  GBool isUnicode;
753  char buf[8];
754  int i, j;
755
756  if (words->next) {
757
758    // compute the inter-word space threshold
759    if (words->len > 1 || words->next->len > 1) {
760      minSpace = 0;
761    } else {
762      minSpace = words->primaryDelta(words->next);
763      for (word0 = words->next, word1 = word0->next;
764           word1 && minSpace > 0;
765           word0 = word1, word1 = word0->next) {
766        if (word1->len > 1) {
767          minSpace = 0;
768        }
769        delta = word0->primaryDelta(word1);
770        if (delta < minSpace) {
771          minSpace = delta;
772        }
773      }
774    }
775    if (minSpace <= 0) {
776      space = maxCharSpacing * words->fontSize;
777    } else {
778      space = maxWideCharSpacingMul * minSpace;
779      if (space > maxWideCharSpacing * words->fontSize) {
780        space = maxWideCharSpacing * words->fontSize;
781      }
782    }
783
784    // merge words
785    word0 = words;
786    word1 = words->next;
787    while (word1) {
788      if (word0->primaryDelta(word1) >= space) {
789        word0->spaceAfter = gTrue;
790        word0 = word1;
791        word1 = word1->next;
792      } else if (word0->font == word1->font &&
793                 word0->underlined == word1->underlined &&
794                 fabs(word0->fontSize - word1->fontSize) <
795                   maxWordFontSizeDelta * words->fontSize &&
796                 word1->charPos == word0->charPos + word0->charLen) {
797        word0->merge(word1);
798        word0->next = word1->next;
799        delete word1;
800        word1 = word0->next;
801      } else {
802        word0 = word1;
803        word1 = word1->next;
804      }
805    }
806  }
807
808  // build the line text
809  isUnicode = uMap ? uMap->isUnicode() : gFalse;
810  len = 0;
811  for (word1 = words; word1; word1 = word1->next) {
812    len += word1->len;
813    if (word1->spaceAfter) {
814      ++len;
815    }
816  }
817  text = (Unicode *)gmallocn(len, sizeof(Unicode));
818  edge = (double *)gmallocn(len + 1, sizeof(double));
819  i = 0;
820  for (word1 = words; word1; word1 = word1->next) {
821    for (j = 0; j < word1->len; ++j) {
822      text[i] = word1->text[j];
823      edge[i] = word1->edge[j];
824      ++i;
825    }
826    edge[i] = word1->edge[word1->len];
827    if (word1->spaceAfter) {
828      text[i] = (Unicode)0x0020;
829      ++i;
830    }
831  }
832
833  // compute convertedLen and set up the col array
834  col = (int *)gmallocn(len + 1, sizeof(int));
835  convertedLen = 0;
836  for (i = 0; i < len; ++i) {
837    col[i] = convertedLen;
838    if (isUnicode) {
839      ++convertedLen;
840    } else if (uMap) {
841      convertedLen += uMap->mapUnicode(text[i], buf, sizeof(buf));
842    }
843  }
844  col[len] = convertedLen;
845
846  // check for hyphen at end of line
847  //~ need to check for other chars used as hyphens
848  hyphenated = text[len - 1] == (Unicode)'-';
849}
850
851//------------------------------------------------------------------------
852// TextLineFrag
853//------------------------------------------------------------------------
854
855class TextLineFrag {
856public:
857
858  TextLine *line;               // the line object
859  int start, len;               // offset and length of this fragment
860                                //   (in Unicode chars)
861  double xMin, xMax;            // bounding box coordinates
862  double yMin, yMax;
863  double base;                  // baseline virtual coordinate
864  int col;                      // first column
865
866  void init(TextLine *lineA, int startA, int lenA);
867  void computeCoords(GBool oneRot);
868
869  static int cmpYXPrimaryRot(const void *p1, const void *p2);
870  static int cmpYXLineRot(const void *p1, const void *p2);
871  static int cmpXYLineRot(const void *p1, const void *p2);
872  static int cmpXYColumnPrimaryRot(const void *p1, const void *p2);
873  static int cmpXYColumnLineRot(const void *p1, const void *p2);
874};
875
876void TextLineFrag::init(TextLine *lineA, int startA, int lenA) {
877  line = lineA;
878  start = startA;
879  len = lenA;
880  col = line->col[start];
881}
882
883void TextLineFrag::computeCoords(GBool oneRot) {
884  TextBlock *blk;
885  double d0, d1, d2, d3, d4;
886
887  if (oneRot) {
888
889    switch (line->rot) {
890    case 0:
891      xMin = line->edge[start];
892      xMax = line->edge[start + len];
893      yMin = line->yMin;
894      yMax = line->yMax;
895      break;
896    case 1:
897      xMin = line->xMin;
898      xMax = line->xMax;
899      yMin = line->edge[start];
900      yMax = line->edge[start + len];
901      break;
902    case 2:
903      xMin = line->edge[start + len];
904      xMax = line->edge[start];
905      yMin = line->yMin;
906      yMax = line->yMax;
907      break;
908    case 3:
909      xMin = line->xMin;
910      xMax = line->xMax;
911      yMin = line->edge[start + len];
912      yMax = line->edge[start];
913      break;
914    }
915    base = line->base;
916
917  } else {
918
919    if (line->rot == 0 && line->blk->page->primaryRot == 0) {
920
921      xMin = line->edge[start];
922      xMax = line->edge[start + len];
923      yMin = line->yMin;
924      yMax = line->yMax;
925      base = line->base;
926
927    } else {
928
929      blk = line->blk;
930      d0 = line->edge[start];
931      d1 = line->edge[start + len];
932      d2 = d3 = d4 = 0; // make gcc happy
933
934      switch (line->rot) {
935      case 0:
936        d2 = line->yMin;
937        d3 = line->yMax;
938        d4 = line->base;
939        d0 = (d0 - blk->xMin) / (blk->xMax - blk->xMin);
940        d1 = (d1 - blk->xMin) / (blk->xMax - blk->xMin);
941        d2 = (d2 - blk->yMin) / (blk->yMax - blk->yMin);
942        d3 = (d3 - blk->yMin) / (blk->yMax - blk->yMin);
943        d4 = (d4 - blk->yMin) / (blk->yMax - blk->yMin);
944        break;
945      case 1:
946        d2 = line->xMax;
947        d3 = line->xMin;
948        d4 = line->base;
949        d0 = (d0 - blk->yMin) / (blk->yMax - blk->yMin);
950        d1 = (d1 - blk->yMin) / (blk->yMax - blk->yMin);
951        d2 = (blk->xMax - d2) / (blk->xMax - blk->xMin);
952        d3 = (blk->xMax - d3) / (blk->xMax - blk->xMin);
953        d4 = (blk->xMax - d4) / (blk->xMax - blk->xMin);
954        break;
955      case 2:
956        d2 = line->yMax;
957        d3 = line->yMin;
958        d4 = line->base;
959        d0 = (blk->xMax - d0) / (blk->xMax - blk->xMin);
960        d1 = (blk->xMax - d1) / (blk->xMax - blk->xMin);
961        d2 = (blk->yMax - d2) / (blk->yMax - blk->yMin);
962        d3 = (blk->yMax - d3) / (blk->yMax - blk->yMin);
963        d4 = (blk->yMax - d4) / (blk->yMax - blk->yMin);
964        break;
965      case 3:
966        d2 = line->xMin;
967        d3 = line->xMax;
968        d4 = line->base;
969        d0 = (blk->yMax - d0) / (blk->yMax - blk->yMin);
970        d1 = (blk->yMax - d1) / (blk->yMax - blk->yMin);
971        d2 = (d2 - blk->xMin) / (blk->xMax - blk->xMin);
972        d3 = (d3 - blk->xMin) / (blk->xMax - blk->xMin);
973        d4 = (d4 - blk->xMin) / (blk->xMax - blk->xMin);
974        break;
975      }
976
977      switch (line->blk->page->primaryRot) {
978      case 0:
979        xMin = blk->xMin + d0 * (blk->xMax - blk->xMin);
980        xMax = blk->xMin + d1 * (blk->xMax - blk->xMin);
981        yMin = blk->yMin + d2 * (blk->yMax - blk->yMin);
982        yMax = blk->yMin + d3 * (blk->yMax - blk->yMin);
983        base = blk->yMin + base * (blk->yMax - blk->yMin);
984        break;
985      case 1:
986        xMin = blk->xMax - d3 * (blk->xMax - blk->xMin);
987        xMax = blk->xMax - d2 * (blk->xMax - blk->xMin);
988        yMin = blk->yMin + d0 * (blk->yMax - blk->yMin);
989        yMax = blk->yMin + d1 * (blk->yMax - blk->yMin);
990        base = blk->xMax - d4 * (blk->xMax - blk->xMin);
991        break;
992      case 2:
993        xMin = blk->xMax - d1 * (blk->xMax - blk->xMin);
994        xMax = blk->xMax - d0 * (blk->xMax - blk->xMin);
995        yMin = blk->yMax - d3 * (blk->yMax - blk->yMin);
996        yMax = blk->yMax - d2 * (blk->yMax - blk->yMin);
997        base = blk->yMax - d4 * (blk->yMax - blk->yMin);
998        break;
999      case 3:
1000        xMin = blk->xMin + d2 * (blk->xMax - blk->xMin);
1001        xMax = blk->xMin + d3 * (blk->xMax - blk->xMin);
1002        yMin = blk->yMax - d1 * (blk->yMax - blk->yMin);
1003        yMax = blk->yMax - d0 * (blk->yMax - blk->yMin);
1004        base = blk->xMin + d4 * (blk->xMax - blk->xMin);
1005        break;
1006      }
1007
1008    }
1009  }
1010}
1011
1012int TextLineFrag::cmpYXPrimaryRot(const void *p1, const void *p2) {
1013  TextLineFrag *frag1 = (TextLineFrag *)p1;
1014  TextLineFrag *frag2 = (TextLineFrag *)p2;
1015  double cmp;
1016
1017  cmp = 0; // make gcc happy
1018  switch (frag1->line->blk->page->primaryRot) {
1019  case 0:
1020    if (fabs(cmp = frag1->yMin - frag2->yMin) < 0.01) {
1021      cmp = frag1->xMin - frag2->xMin;
1022    }
1023    break;
1024  case 1:
1025    if (fabs(cmp = frag2->xMax - frag1->xMax) < 0.01) {
1026      cmp = frag1->yMin - frag2->yMin;
1027    }
1028    break;
1029  case 2:
1030    if (fabs(cmp = frag2->yMin - frag1->yMin) < 0.01) {
1031      cmp = frag2->xMax - frag1->xMax;
1032    }
1033    break;
1034  case 3:
1035    if (fabs(cmp = frag1->xMax - frag2->xMax) < 0.01) {
1036      cmp = frag2->yMax - frag1->yMax;
1037    }
1038    break;
1039  }
1040  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1041}
1042
1043int TextLineFrag::cmpYXLineRot(const void *p1, const void *p2) {
1044  TextLineFrag *frag1 = (TextLineFrag *)p1;
1045  TextLineFrag *frag2 = (TextLineFrag *)p2;
1046  double cmp;
1047
1048  cmp = 0; // make gcc happy
1049  switch (frag1->line->rot) {
1050  case 0:
1051    if ((cmp = frag1->yMin - frag2->yMin) == 0) {
1052      cmp = frag1->xMin - frag2->xMin;
1053    }
1054    break;
1055  case 1:
1056    if ((cmp = frag2->xMax - frag1->xMax) == 0) {
1057      cmp = frag1->yMin - frag2->yMin;
1058    }
1059    break;
1060  case 2:
1061    if ((cmp = frag2->yMin - frag1->yMin) == 0) {
1062      cmp = frag2->xMax - frag1->xMax;
1063    }
1064    break;
1065  case 3:
1066    if ((cmp = frag1->xMax - frag2->xMax) == 0) {
1067      cmp = frag2->yMax - frag1->yMax;
1068    }
1069    break;
1070  }
1071  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1072}
1073
1074int TextLineFrag::cmpXYLineRot(const void *p1, const void *p2) {
1075  TextLineFrag *frag1 = (TextLineFrag *)p1;
1076  TextLineFrag *frag2 = (TextLineFrag *)p2;
1077  double cmp;
1078
1079  cmp = 0; // make gcc happy
1080  switch (frag1->line->rot) {
1081  case 0:
1082    if ((cmp = frag1->xMin - frag2->xMin) == 0) {
1083      cmp = frag1->yMin - frag2->yMin;
1084    }
1085    break;
1086  case 1:
1087    if ((cmp = frag1->yMin - frag2->yMin) == 0) {
1088      cmp = frag2->xMax - frag1->xMax;
1089    }
1090    break;
1091  case 2:
1092    if ((cmp = frag2->xMax - frag1->xMax) == 0) {
1093      cmp = frag2->yMin - frag1->yMin;
1094    }
1095    break;
1096  case 3:
1097    if ((cmp = frag2->yMax - frag1->yMax) == 0) {
1098      cmp = frag1->xMax - frag2->xMax;
1099    }
1100    break;
1101  }
1102  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1103}
1104
1105int TextLineFrag::cmpXYColumnPrimaryRot(const void *p1, const void *p2) {
1106  TextLineFrag *frag1 = (TextLineFrag *)p1;
1107  TextLineFrag *frag2 = (TextLineFrag *)p2;
1108  double cmp;
1109
1110  // if columns overlap, compare y values
1111  if (frag1->col < frag2->col + (frag2->line->col[frag2->start + frag2->len] -
1112                                 frag2->line->col[frag2->start]) &&
1113      frag2->col < frag1->col + (frag1->line->col[frag1->start + frag1->len] -
1114                                 frag1->line->col[frag1->start])) {
1115    cmp = 0; // make gcc happy
1116    switch (frag1->line->blk->page->primaryRot) {
1117    case 0: cmp = frag1->yMin - frag2->yMin; break;
1118    case 1: cmp = frag2->xMax - frag1->xMax; break;
1119    case 2: cmp = frag2->yMin - frag1->yMin; break;
1120    case 3: cmp = frag1->xMax - frag2->xMax; break;
1121    }
1122    return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1123  }
1124
1125  // otherwise, compare starting column
1126  return frag1->col - frag2->col;
1127}
1128
1129int TextLineFrag::cmpXYColumnLineRot(const void *p1, const void *p2) {
1130  TextLineFrag *frag1 = (TextLineFrag *)p1;
1131  TextLineFrag *frag2 = (TextLineFrag *)p2;
1132  double cmp;
1133
1134  // if columns overlap, compare y values
1135  if (frag1->col < frag2->col + (frag2->line->col[frag2->start + frag2->len] -
1136                                 frag2->line->col[frag2->start]) &&
1137      frag2->col < frag1->col + (frag1->line->col[frag1->start + frag1->len] -
1138                                 frag1->line->col[frag1->start])) {
1139    cmp = 0; // make gcc happy
1140    switch (frag1->line->rot) {
1141    case 0: cmp = frag1->yMin - frag2->yMin; break;
1142    case 1: cmp = frag2->xMax - frag1->xMax; break;
1143    case 2: cmp = frag2->yMin - frag1->yMin; break;
1144    case 3: cmp = frag1->xMax - frag2->xMax; break;
1145    }
1146    return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1147  }
1148
1149  // otherwise, compare starting column
1150  return frag1->col - frag2->col;
1151}
1152
1153//------------------------------------------------------------------------
1154// TextBlock
1155//------------------------------------------------------------------------
1156
1157TextBlock::TextBlock(TextPage *pageA, int rotA) {
1158  page = pageA;
1159  rot = rotA;
1160  xMin = yMin = 0;
1161  xMax = yMax = -1;
1162  priMin = 0;
1163  priMax = page->pageWidth;
1164  pool = new TextPool();
1165  lines = NULL;
1166  curLine = NULL;
1167  next = NULL;
1168  stackNext = NULL;
1169  tableId = -1;
1170  tableEnd = gFalse;
1171}
1172
1173TextBlock::~TextBlock() {
1174  TextLine *line;
1175
1176  delete pool;
1177  while (lines) {
1178    line = lines;
1179    lines = lines->next;
1180    delete line;
1181  }
1182}
1183
1184void TextBlock::addWord(TextWord *word) {
1185  pool->addWord(word);
1186  if (xMin > xMax) {
1187    xMin = word->xMin;
1188    xMax = word->xMax;
1189    yMin = word->yMin;
1190    yMax = word->yMax;
1191  } else {
1192    if (word->xMin < xMin) {
1193      xMin = word->xMin;
1194    }
1195    if (word->xMax > xMax) {
1196      xMax = word->xMax;
1197    }
1198    if (word->yMin < yMin) {
1199      yMin = word->yMin;
1200    }
1201    if (word->yMax > yMax) {
1202      yMax = word->yMax;
1203    }
1204  }
1205}
1206
1207void TextBlock::coalesce(UnicodeMap *uMap) {
1208  TextWord *word0, *word1, *word2, *bestWord0, *bestWord1, *lastWord;
1209  TextLine *line, *line0, *line1;
1210  int poolMinBaseIdx, startBaseIdx, minBaseIdx, maxBaseIdx;
1211  int baseIdx, bestWordBaseIdx, idx0, idx1;
1212  double minBase, maxBase;
1213  double fontSize, delta, priDelta, secDelta;
1214  TextLine **lineArray;
1215  GBool found;
1216  int col1, col2;
1217  int i, j, k;
1218
1219  // discard duplicated text (fake boldface, drop shadows)
1220  for (idx0 = pool->minBaseIdx; idx0 <= pool->maxBaseIdx; ++idx0) {
1221    word0 = pool->getPool(idx0);
1222    while (word0) {
1223      priDelta = dupMaxPriDelta * word0->fontSize;
1224      secDelta = dupMaxSecDelta * word0->fontSize;
1225      if (rot == 0 || rot == 3) {
1226        maxBaseIdx = pool->getBaseIdx(word0->base + secDelta);
1227      } else {
1228        maxBaseIdx = pool->getBaseIdx(word0->base - secDelta);
1229      }
1230      found = gFalse;
1231      word1 = word2 = NULL; // make gcc happy
1232      for (idx1 = idx0; idx1 <= maxBaseIdx; ++idx1) {
1233        if (idx1 == idx0) {
1234          word1 = word0;
1235          word2 = word0->next;
1236        } else {
1237          word1 = NULL;
1238          word2 = pool->getPool(idx1);
1239        }
1240        for (; word2; word1 = word2, word2 = word2->next) {
1241          if (word2->len == word0->len &&
1242              !memcmp(word2->text, word0->text,
1243                      word0->len * sizeof(Unicode))) {
1244            switch (rot) {
1245            case 0:
1246            case 2:
1247              found = fabs(word0->xMin - word2->xMin) < priDelta &&
1248                      fabs(word0->xMax - word2->xMax) < priDelta &&
1249                      fabs(word0->yMin - word2->yMin) < secDelta &&
1250                      fabs(word0->yMax - word2->yMax) < secDelta;
1251              break;
1252            case 1:
1253            case 3:
1254              found = fabs(word0->xMin - word2->xMin) < secDelta &&
1255                      fabs(word0->xMax - word2->xMax) < secDelta &&
1256                      fabs(word0->yMin - word2->yMin) < priDelta &&
1257                      fabs(word0->yMax - word2->yMax) < priDelta;
1258              break;
1259            }
1260          }
1261          if (found) {
1262            break;
1263          }
1264        }
1265        if (found) {
1266          break;
1267        }
1268      }
1269      if (found) {
1270        if (word1) {
1271          word1->next = word2->next;
1272        } else {
1273          pool->setPool(idx1, word2->next);
1274        }
1275        delete word2;
1276      } else {
1277        word0 = word0->next;
1278      }
1279    }
1280  }
1281
1282  // build the lines
1283  curLine = NULL;
1284  poolMinBaseIdx = pool->minBaseIdx;
1285  charCount = 0;
1286  nLines = 0;
1287  while (1) {
1288
1289    // find the first non-empty line in the pool
1290    for (;
1291         poolMinBaseIdx <= pool->maxBaseIdx && !pool->getPool(poolMinBaseIdx);
1292         ++poolMinBaseIdx) ;
1293    if (poolMinBaseIdx > pool->maxBaseIdx) {
1294      break;
1295    }
1296
1297    // look for the left-most word in the first four lines of the
1298    // pool -- this avoids starting with a superscript word
1299    startBaseIdx = poolMinBaseIdx;
1300    for (baseIdx = poolMinBaseIdx + 1;
1301         baseIdx < poolMinBaseIdx + 4 && baseIdx <= pool->maxBaseIdx;
1302         ++baseIdx) {
1303      if (!pool->getPool(baseIdx)) {
1304        continue;
1305      }
1306      if (pool->getPool(baseIdx)->primaryCmp(pool->getPool(startBaseIdx))
1307          < 0) {
1308        startBaseIdx = baseIdx;
1309      }
1310    }
1311
1312    // create a new line
1313    word0 = pool->getPool(startBaseIdx);
1314    pool->setPool(startBaseIdx, word0->next);
1315    word0->next = NULL;
1316    line = new TextLine(this, word0->rot, word0->base);
1317    line->addWord(word0);
1318    lastWord = word0;
1319
1320    // compute the search range
1321    fontSize = word0->fontSize;
1322    minBase = word0->base - maxIntraLineDelta * fontSize;
1323    maxBase = word0->base + maxIntraLineDelta * fontSize;
1324    minBaseIdx = pool->getBaseIdx(minBase);
1325    maxBaseIdx = pool->getBaseIdx(maxBase);
1326
1327    // find the rest of the words in this line
1328    while (1) {
1329
1330      // find the left-most word whose baseline is in the range for
1331      // this line
1332      bestWordBaseIdx = 0;
1333      bestWord0 = bestWord1 = NULL;
1334      for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
1335        for (word0 = NULL, word1 = pool->getPool(baseIdx);
1336             word1;
1337             word0 = word1, word1 = word1->next) {
1338          if (word1->base >= minBase &&
1339              word1->base <= maxBase &&
1340              (delta = lastWord->primaryDelta(word1)) >=
1341                minCharSpacing * fontSize) {
1342            if (delta < maxWordSpacing * fontSize &&
1343                (!bestWord1 || word1->primaryCmp(bestWord1) < 0)) {
1344              bestWordBaseIdx = baseIdx;
1345              bestWord0 = word0;
1346              bestWord1 = word1;
1347            }
1348            break;
1349          }
1350        }
1351      }
1352      if (!bestWord1) {
1353        break;
1354      }
1355
1356      // remove it from the pool, and add it to the line
1357      if (bestWord0) {
1358        bestWord0->next = bestWord1->next;
1359      } else {
1360        pool->setPool(bestWordBaseIdx, bestWord1->next);
1361      }
1362      bestWord1->next = NULL;
1363      line->addWord(bestWord1);
1364      lastWord = bestWord1;
1365    }
1366
1367    // add the line
1368    if (curLine && line->cmpYX(curLine) > 0) {
1369      line0 = curLine;
1370      line1 = curLine->next;
1371    } else {
1372      line0 = NULL;
1373      line1 = lines;
1374    }
1375    for (;
1376         line1 && line->cmpYX(line1) > 0;
1377         line0 = line1, line1 = line1->next) ;
1378    if (line0) {
1379      line0->next = line;
1380    } else {
1381      lines = line;
1382    }
1383    line->next = line1;
1384    curLine = line;
1385    line->coalesce(uMap);
1386    charCount += line->len;
1387    ++nLines;
1388  }
1389
1390  // sort lines into xy order for column assignment
1391  lineArray = (TextLine **)gmallocn(nLines, sizeof(TextLine *));
1392  for (line = lines, i = 0; line; line = line->next, ++i) {
1393    lineArray[i] = line;
1394  }
1395  qsort(lineArray, nLines, sizeof(TextLine *), &TextLine::cmpXY);
1396
1397  // column assignment
1398  nColumns = 0;
1399  for (i = 0; i < nLines; ++i) {
1400    line0 = lineArray[i];
1401    col1 = 0;
1402    for (j = 0; j < i; ++j) {
1403      line1 = lineArray[j];
1404      if (line1->primaryDelta(line0) >= 0) {
1405        col2 = line1->col[line1->len] + 1;
1406      } else {
1407        k = 0; // make gcc happy
1408        switch (rot) {
1409        case 0:
1410          for (k = 0;
1411               k < line1->len &&
1412                 line0->xMin >= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1413               ++k) ;
1414          break;
1415        case 1:
1416          for (k = 0;
1417               k < line1->len &&
1418                 line0->yMin >= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1419               ++k) ;
1420          break;
1421        case 2:
1422          for (k = 0;
1423               k < line1->len &&
1424                 line0->xMax <= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1425               ++k) ;
1426          break;
1427        case 3:
1428          for (k = 0;
1429               k < line1->len &&
1430                 line0->yMax <= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1431               ++k) ;
1432          break;
1433        }
1434        col2 = line1->col[k];
1435      }
1436      if (col2 > col1) {
1437        col1 = col2;
1438      }
1439    }
1440    for (k = 0; k <= line0->len; ++k) {
1441      line0->col[k] += col1;
1442    }
1443    if (line0->col[line0->len] > nColumns) {
1444      nColumns = line0->col[line0->len];
1445    }
1446  }
1447  gfree(lineArray);
1448}
1449
1450void TextBlock::updatePriMinMax(TextBlock *blk) {
1451  double newPriMin, newPriMax;
1452  GBool gotPriMin, gotPriMax;
1453
1454  gotPriMin = gotPriMax = gFalse;
1455  newPriMin = newPriMax = 0; // make gcc happy
1456  switch (page->primaryRot) {
1457  case 0:
1458  case 2:
1459    if (blk->yMin < yMax && blk->yMax > yMin) {
1460      if (blk->xMin < xMin) {
1461        newPriMin = blk->xMax;
1462        gotPriMin = gTrue;
1463      }
1464      if (blk->xMax > xMax) {
1465        newPriMax = blk->xMin;
1466        gotPriMax = gTrue;
1467      }
1468    }
1469    break;
1470  case 1:
1471  case 3:
1472    if (blk->xMin < xMax && blk->xMax > xMin) {
1473      if (blk->yMin < yMin) {
1474        newPriMin = blk->yMax;
1475        gotPriMin = gTrue;
1476      }
1477      if (blk->yMax > yMax) {
1478        newPriMax = blk->yMin;
1479        gotPriMax = gTrue;
1480      }
1481    }
1482    break;
1483  }
1484  if (gotPriMin) {
1485    if (newPriMin > xMin) {
1486      newPriMin = xMin;
1487    }
1488    if (newPriMin > priMin) {
1489      priMin = newPriMin;
1490    }
1491  }
1492  if (gotPriMax) {
1493    if (newPriMax < xMax) {
1494      newPriMax = xMax;
1495    }
1496    if (newPriMax < priMax) {
1497      priMax = newPriMax;
1498    }
1499  }
1500}
1501
1502int TextBlock::cmpXYPrimaryRot(const void *p1, const void *p2) {
1503  TextBlock *blk1 = *(TextBlock **)p1;
1504  TextBlock *blk2 = *(TextBlock **)p2;
1505  double cmp;
1506
1507  cmp = 0; // make gcc happy
1508  switch (blk1->page->primaryRot) {
1509  case 0:
1510    if ((cmp = blk1->xMin - blk2->xMin) == 0) {
1511      cmp = blk1->yMin - blk2->yMin;
1512    }
1513    break;
1514  case 1:
1515    if ((cmp = blk1->yMin - blk2->yMin) == 0) {
1516      cmp = blk2->xMax - blk1->xMax;
1517    }
1518    break;
1519  case 2:
1520    if ((cmp = blk2->xMax - blk1->xMax) == 0) {
1521      cmp = blk2->yMin - blk1->yMin;
1522    }
1523    break;
1524  case 3:
1525    if ((cmp = blk2->yMax - blk1->yMax) == 0) {
1526      cmp = blk1->xMax - blk2->xMax;
1527    }
1528    break;
1529  }
1530  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1531}
1532
1533int TextBlock::cmpYXPrimaryRot(const void *p1, const void *p2) {
1534  TextBlock *blk1 = *(TextBlock **)p1;
1535  TextBlock *blk2 = *(TextBlock **)p2;
1536  double cmp;
1537
1538  cmp = 0; // make gcc happy
1539  switch (blk1->page->primaryRot) {
1540  case 0:
1541    if ((cmp = blk1->yMin - blk2->yMin) == 0) {
1542      cmp = blk1->xMin - blk2->xMin;
1543    }
1544    break;
1545  case 1:
1546    if ((cmp = blk2->xMax - blk1->xMax) == 0) {
1547      cmp = blk1->yMin - blk2->yMin;
1548    }
1549    break;
1550  case 2:
1551    if ((cmp = blk2->yMin - blk1->yMin) == 0) {
1552      cmp = blk2->xMax - blk1->xMax;
1553    }
1554    break;
1555  case 3:
1556    if ((cmp = blk1->xMax - blk2->xMax) == 0) {
1557      cmp = blk2->yMax - blk1->yMax;
1558    }
1559    break;
1560  }
1561  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1562}
1563
1564int TextBlock::primaryCmp(TextBlock *blk) {
1565  double cmp;
1566
1567  cmp = 0; // make gcc happy
1568  switch (rot) {
1569  case 0:
1570    cmp = xMin - blk->xMin;
1571    break;
1572  case 1:
1573    cmp = yMin - blk->yMin;
1574    break;
1575  case 2:
1576    cmp = blk->xMax - xMax;
1577    break;
1578  case 3:
1579    cmp = blk->yMax - yMax;
1580    break;
1581  }
1582  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1583}
1584
1585double TextBlock::secondaryDelta(TextBlock *blk) {
1586  double delta;
1587
1588  delta = 0; // make gcc happy
1589  switch (rot) {
1590  case 0:
1591    delta = blk->yMin - yMax;
1592    break;
1593  case 1:
1594    delta = xMin - blk->xMax;
1595    break;
1596  case 2:
1597    delta = yMin - blk->yMax;
1598    break;
1599  case 3:
1600    delta = blk->xMin - xMax;
1601    break;
1602  }
1603  return delta;
1604}
1605
1606GBool TextBlock::isBelow(TextBlock *blk) {
1607  GBool below;
1608
1609  below = gFalse; // make gcc happy
1610  switch (page->primaryRot) {
1611  case 0:
1612    below = xMin >= blk->priMin && xMax <= blk->priMax &&
1613            yMin > blk->yMin;
1614    break;
1615  case 1:
1616    below = yMin >= blk->priMin && yMax <= blk->priMax &&
1617            xMax < blk->xMax;
1618    break;
1619  case 2:
1620    below = xMin >= blk->priMin && xMax <= blk->priMax &&
1621            yMax < blk->yMax;
1622    break;
1623  case 3:
1624    below = yMin >= blk->priMin && yMax <= blk->priMax &&
1625            xMin > blk->xMin;
1626    break;
1627  }
1628
1629  return below;
1630}
1631
1632GBool TextBlock::isBeforeByRule1(TextBlock *blk1) {
1633  GBool before = gFalse;
1634  GBool overlap = gFalse;
1635
1636  switch (this->page->primaryRot) {
1637  case 0:
1638  case 2:
1639    overlap = ((this->ExMin <= blk1->ExMin) &&
1640               (blk1->ExMin <= this->ExMax)) ||
1641      ((blk1->ExMin <= this->ExMin) &&
1642       (this->ExMin <= blk1->ExMax));
1643    break;
1644  case 1:
1645  case 3:
1646    overlap = ((this->EyMin <= blk1->EyMin) &&
1647               (blk1->EyMin <= this->EyMax)) ||
1648      ((blk1->EyMin <= this->EyMin) &&
1649       (this->EyMin <= blk1->EyMax));
1650    break;
1651  }
1652  switch (this->page->primaryRot) {
1653  case 0:
1654    before = overlap && this->EyMin < blk1->EyMin;
1655    break;
1656  case 1:
1657    before = overlap && this->ExMax > blk1->ExMax;
1658    break;
1659  case 2:
1660    before = overlap && this->EyMax > blk1->EyMax;
1661    break;
1662  case 3:
1663    before = overlap && this->ExMin < blk1->ExMin;
1664    break;
1665  }
1666  return before;
1667}
1668
1669GBool TextBlock::isBeforeByRule2(TextBlock *blk1) {
1670  double cmp = 0;
1671  int rotLR = rot;
1672
1673  if (!page->primaryLR) {
1674    rotLR = (rotLR + 2) % 4;
1675  }
1676
1677  switch (rotLR) {
1678  case 0:
1679    cmp = ExMax - blk1->ExMin;
1680    break;
1681  case 1:
1682    cmp = EyMin - blk1->EyMax;
1683    break;
1684  case 2:
1685    cmp = blk1->ExMax - ExMin;
1686    break;
1687  case 3:
1688    cmp = blk1->EyMin - EyMax;
1689    break;
1690  }
1691  return cmp <= 0;
1692}
1693
1694// Sort into reading order by performing a topological sort using the rules
1695// given in "High Performance Document Layout Analysis", T.M. Breuel, 2003.
1696// See http://pubs.iupr.org/#2003-breuel-sdiut
1697// Topological sort is done by depth first search, see
1698// http://en.wikipedia.org/wiki/Topological_sorting
1699int TextBlock::visitDepthFirst(TextBlock *blkList, int pos1,
1700                               TextBlock **sorted, int sortPos,
1701                               GBool* visited) {
1702  int pos2;
1703  TextBlock *blk1, *blk2, *blk3;
1704  GBool before;
1705
1706  if (visited[pos1]) {
1707    return sortPos;
1708  }
1709
1710  blk1 = this;
1711
1712#if 0 // for debugging
1713  printf("visited: %d %.2f..%.2f %.2f..%.2f\n",
1714         sortPos, blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax);
1715#endif
1716  visited[pos1] = gTrue;
1717  pos2 = -1;
1718  for (blk2 = blkList; blk2; blk2 = blk2->next) {
1719    pos2++;
1720    if (visited[pos2]) {
1721      // skip visited nodes
1722      continue;
1723    }
1724    before = gFalse;
1725
1726    // is blk2 before blk1? (for table entries)
1727    if (blk1->tableId >= 0 && blk1->tableId == blk2->tableId) {
1728      if (page->primaryLR) {
1729        if (blk2->xMax <= blk1->xMin &&
1730            blk2->yMin <= blk1->yMax &&
1731            blk2->yMax >= blk1->yMin)
1732          before = gTrue;
1733      } else {
1734        if (blk2->xMin >= blk1->xMax &&
1735            blk2->yMin <= blk1->yMax &&
1736            blk2->yMax >= blk1->yMin)
1737          before = gTrue;
1738      }
1739
1740      if (blk2->yMax <= blk1->yMin)
1741        before = gTrue;
1742    } else {
1743      if (blk2->isBeforeByRule1(blk1)) {
1744        // Rule (1) blk1 and blk2 overlap, and blk2 is above blk1.
1745        before = gTrue;
1746#if 0   // for debugging
1747        printf("rule1: %.2f..%.2f %.2f..%.2f %.2f..%.2f %.2f..%.2f\n",
1748               blk2->ExMin, blk2->ExMax, blk2->EyMin, blk2->EyMax,
1749               blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax);
1750#endif
1751      } else if (blk2->isBeforeByRule2(blk1)) {
1752        // Rule (2) blk2 left of blk1, and no intervening blk3
1753        //          such that blk1 is before blk3 by rule 1,
1754        //          and blk3 is before blk2 by rule 1.
1755        before = gTrue;
1756        for (blk3 = blkList; blk3; blk3 = blk3->next) {
1757          if (blk3 == blk2 || blk3 == blk1) {
1758            continue;
1759          }
1760          if (blk1->isBeforeByRule1(blk3) &&
1761              blk3->isBeforeByRule1(blk2)) {
1762            before = gFalse;
1763            break;
1764          }
1765        }
1766#if 0 // for debugging
1767        if (before) {
1768          printf("rule2: %.2f..%.2f %.2f..%.2f %.2f..%.2f %.2f..%.2f\n",
1769                 blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax,
1770                 blk2->ExMin, blk2->ExMax, blk2->EyMin, blk2->EyMax);
1771        }
1772#endif
1773      }
1774    }
1775    if (before) {
1776      // blk2 is before blk1, so it needs to be visited
1777      // before we can add blk1 to the sorted list.
1778      sortPos = blk2->visitDepthFirst(blkList, pos2, sorted, sortPos, visited);
1779    }
1780  }
1781#if 0 // for debugging
1782  printf("sorted: %d %.2f..%.2f %.2f..%.2f\n",
1783         sortPos, blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax);
1784#endif
1785  sorted[sortPos++] = blk1;
1786  return sortPos;
1787}
1788
1789//------------------------------------------------------------------------
1790// TextFlow
1791//------------------------------------------------------------------------
1792
1793TextFlow::TextFlow(TextPage *pageA, TextBlock *blk) {
1794  page = pageA;
1795  xMin = blk->xMin;
1796  xMax = blk->xMax;
1797  yMin = blk->yMin;
1798  yMax = blk->yMax;
1799  priMin = blk->priMin;
1800  priMax = blk->priMax;
1801  blocks = lastBlk = blk;
1802  next = NULL;
1803}
1804
1805TextFlow::~TextFlow() {
1806  TextBlock *blk;
1807
1808  while (blocks) {
1809    blk = blocks;
1810    blocks = blocks->next;
1811    delete blk;
1812  }
1813}
1814
1815void TextFlow::addBlock(TextBlock *blk) {
1816  if (lastBlk) {
1817    lastBlk->next = blk;
1818  } else {
1819    blocks = blk;
1820  }
1821  lastBlk = blk;
1822  if (blk->xMin < xMin) {
1823    xMin = blk->xMin;
1824  }
1825  if (blk->xMax > xMax) {
1826    xMax = blk->xMax;
1827  }
1828  if (blk->yMin < yMin) {
1829    yMin = blk->yMin;
1830  }
1831  if (blk->yMax > yMax) {
1832    yMax = blk->yMax;
1833  }
1834}
1835
1836GBool TextFlow::blockFits(TextBlock *blk, TextBlock *prevBlk) {
1837  GBool fits;
1838
1839  // lower blocks must use smaller fonts
1840  if (blk->lines->words->fontSize > lastBlk->lines->words->fontSize) {
1841    return gFalse;
1842  }
1843
1844  fits = gFalse; // make gcc happy
1845  switch (page->primaryRot) {
1846  case 0:
1847    fits = blk->xMin >= priMin && blk->xMax <= priMax;
1848    break;
1849  case 1:
1850    fits = blk->yMin >= priMin && blk->yMax <= priMax;
1851    break;
1852  case 2:
1853    fits = blk->xMin >= priMin && blk->xMax <= priMax;
1854    break;
1855  case 3:
1856    fits = blk->yMin >= priMin && blk->yMax <= priMax;
1857    break;
1858  }
1859  return fits;
1860}
1861
1862#if TEXTOUT_WORD_LIST
1863
1864//------------------------------------------------------------------------
1865// TextWordList
1866//------------------------------------------------------------------------
1867
1868TextWordList::TextWordList(TextPage *text, GBool physLayout) {
1869  TextFlow *flow;
1870  TextBlock *blk;
1871  TextLine *line;
1872  TextWord *word;
1873  TextWord **wordArray;
1874  int nWords, i;
1875
1876  words = new GooList();
1877
1878  if (text->rawOrder) {
1879    for (word = text->rawWords; word; word = word->next) {
1880      words->append(word);
1881    }
1882
1883  } else if (physLayout) {
1884    // this is inefficient, but it's also the least useful of these
1885    // three cases
1886    nWords = 0;
1887    for (flow = text->flows; flow; flow = flow->next) {
1888      for (blk = flow->blocks; blk; blk = blk->next) {
1889        for (line = blk->lines; line; line = line->next) {
1890          for (word = line->words; word; word = word->next) {
1891            ++nWords;
1892          }
1893        }
1894      }
1895    }
1896    wordArray = (TextWord **)gmallocn(nWords, sizeof(TextWord *));
1897    i = 0;
1898    for (flow = text->flows; flow; flow = flow->next) {
1899      for (blk = flow->blocks; blk; blk = blk->next) {
1900        for (line = blk->lines; line; line = line->next) {
1901          for (word = line->words; word; word = word->next) {
1902            wordArray[i++] = word;
1903          }
1904        }
1905      }
1906    }
1907    qsort(wordArray, nWords, sizeof(TextWord *), &TextWord::cmpYX);
1908    for (i = 0; i < nWords; ++i) {
1909      words->append(wordArray[i]);
1910    }
1911    gfree(wordArray);
1912
1913  } else {
1914    for (flow = text->flows; flow; flow = flow->next) {
1915      for (blk = flow->blocks; blk; blk = blk->next) {
1916        for (line = blk->lines; line; line = line->next) {
1917          for (word = line->words; word; word = word->next) {
1918            words->append(word);
1919          }
1920        }
1921      }
1922    }
1923  }
1924}
1925
1926TextWordList::~TextWordList() {
1927  delete words;
1928}
1929
1930int TextWordList::getLength() {
1931  return words->getLength();
1932}
1933
1934TextWord *TextWordList::get(int idx) {
1935  if (idx < 0 || idx >= words->getLength()) {
1936    return NULL;
1937  }
1938  return (TextWord *)words->get(idx);
1939}
1940
1941#endif // TEXTOUT_WORD_LIST
1942
1943//------------------------------------------------------------------------
1944// TextPage
1945//------------------------------------------------------------------------
1946
1947TextPage::TextPage(GBool rawOrderA) {
1948  int rot;
1949
1950  refCnt = 1;
1951  rawOrder = rawOrderA;
1952  curWord = NULL;
1953  charPos = 0;
1954  curFont = NULL;
1955  curFontSize = 0;
1956  nest = 0;
1957  nTinyChars = 0;
1958  lastCharOverlap = gFalse;
1959  if (!rawOrder) {
1960    for (rot = 0; rot < 4; ++rot) {
1961      pools[rot] = new TextPool();
1962    }
1963  }
1964  flows = NULL;
1965  blocks = NULL;
1966  rawWords = NULL;
1967  rawLastWord = NULL;
1968  fonts = new GooList();
1969  lastFindXMin = lastFindYMin = 0;
1970  haveLastFind = gFalse;
1971  underlines = new GooList();
1972  links = new GooList();
1973}
1974
1975TextPage::~TextPage() {
1976  int rot;
1977
1978  clear();
1979  if (!rawOrder) {
1980    for (rot = 0; rot < 4; ++rot) {
1981      delete pools[rot];
1982    }
1983  }
1984  delete fonts;
1985  deleteGooList(underlines, TextUnderline);
1986  deleteGooList(links, TextLink);
1987}
1988
1989void TextPage::incRefCnt() {
1990  refCnt++;
1991}
1992
1993void TextPage::decRefCnt() {
1994  if (--refCnt == 0)
1995    delete this;
1996}
1997
1998void TextPage::startPage(GfxState *state) {
1999  clear();
2000  if (state) {
2001    pageWidth = state->getPageWidth();
2002    pageHeight = state->getPageHeight();
2003  } else {
2004    pageWidth = pageHeight = 0;
2005  }
2006}
2007
2008void TextPage::endPage() {
2009  if (curWord) {
2010    endWord();
2011  }
2012}
2013
2014void TextPage::clear() {
2015  int rot;
2016  TextFlow *flow;
2017  TextWord *word;
2018
2019  if (curWord) {
2020    delete curWord;
2021    curWord = NULL;
2022  }
2023  if (rawOrder) {
2024    while (rawWords) {
2025      word = rawWords;
2026      rawWords = rawWords->next;
2027      delete word;
2028    }
2029  } else {
2030    for (rot = 0; rot < 4; ++rot) {
2031      delete pools[rot];
2032    }
2033    while (flows) {
2034      flow = flows;
2035      flows = flows->next;
2036      delete flow;
2037    }
2038    gfree(blocks);
2039  }
2040  deleteGooList(fonts, TextFontInfo);
2041
2042  curWord = NULL;
2043  charPos = 0;
2044  curFont = NULL;
2045  curFontSize = 0;
2046  nest = 0;
2047  nTinyChars = 0;
2048  if (!rawOrder) {
2049    for (rot = 0; rot < 4; ++rot) {
2050      pools[rot] = new TextPool();
2051    }
2052  }
2053  flows = NULL;
2054  blocks = NULL;
2055  rawWords = NULL;
2056  rawLastWord = NULL;
2057  fonts = new GooList();
2058}
2059
2060void TextPage::updateFont(GfxState *state) {
2061  GfxFont *gfxFont;
2062  double *fm;
2063  char *name;
2064  int code, mCode, letterCode, anyCode;
2065  double w;
2066  int i;
2067
2068  // get the font info object
2069  curFont = NULL;
2070  for (i = 0; i < fonts->getLength(); ++i) {
2071    curFont = (TextFontInfo *)fonts->get(i);
2072    if (curFont->matches(state)) {
2073      break;
2074    }
2075    curFont = NULL;
2076  }
2077  if (!curFont) {
2078    curFont = new TextFontInfo(state);
2079    fonts->append(curFont);
2080  }
2081
2082  // adjust the font size
2083  gfxFont = state->getFont();
2084  curFontSize = state->getTransformedFontSize();
2085  if (gfxFont && gfxFont->getType() == fontType3) {
2086    // This is a hack which makes it possible to deal with some Type 3
2087    // fonts.  The problem is that it's impossible to know what the
2088    // base coordinate system used in the font is without actually
2089    // rendering the font.  This code tries to guess by looking at the
2090    // width of the character 'm' (which breaks if the font is a
2091    // subset that doesn't contain 'm').
2092    mCode = letterCode = anyCode = -1;
2093    for (code = 0; code < 256; ++code) {
2094      name = ((Gfx8BitFont *)gfxFont)->getCharName(code);
2095      if (name && name[0] == 'm' && name[1] == '\0') {
2096        mCode = code;
2097      }
2098      if (letterCode < 0 && name && name[1] == '\0' &&
2099          ((name[0] >= 'A' && name[0] <= 'Z') ||
2100           (name[0] >= 'a' && name[0] <= 'z'))) {
2101        letterCode = code;
2102      }
2103      if (anyCode < 0 && name &&
2104          ((Gfx8BitFont *)gfxFont)->getWidth(code) > 0) {
2105        anyCode = code;
2106      }
2107    }
2108    if (mCode >= 0 &&
2109        (w = ((Gfx8BitFont *)gfxFont)->getWidth(mCode)) > 0) {
2110      // 0.6 is a generic average 'm' width -- yes, this is a hack
2111      curFontSize *= w / 0.6;
2112    } else if (letterCode >= 0 &&
2113               (w = ((Gfx8BitFont *)gfxFont)->getWidth(letterCode)) > 0) {
2114      // even more of a hack: 0.5 is a generic letter width
2115      curFontSize *= w / 0.5;
2116    } else if (anyCode >= 0 &&
2117               (w = ((Gfx8BitFont *)gfxFont)->getWidth(anyCode)) > 0) {
2118      // better than nothing: 0.5 is a generic character width
2119      curFontSize *= w / 0.5;
2120    }
2121    fm = gfxFont->getFontMatrix();
2122    if (fm[0] != 0) {
2123      curFontSize *= fabs(fm[3] / fm[0]);
2124    }
2125  }
2126}
2127
2128void TextPage::beginWord(GfxState *state, double x0, double y0) {
2129  GfxFont *gfxFont;
2130  double *fontm;
2131  double m[4], m2[4];
2132  int rot;
2133
2134  // This check is needed because Type 3 characters can contain
2135  // text-drawing operations (when TextPage is being used via
2136  // {X,Win}SplashOutputDev rather than TextOutputDev).
2137  if (curWord) {
2138    ++nest;
2139    return;
2140  }
2141
2142  // compute the rotation
2143  state->getFontTransMat(&m[0], &m[1], &m[2], &m[3]);
2144  gfxFont = state->getFont();
2145  if (gfxFont && gfxFont->getType() == fontType3) {
2146    fontm = state->getFont()->getFontMatrix();
2147    m2[0] = fontm[0] * m[0] + fontm[1] * m[2];
2148    m2[1] = fontm[0] * m[1] + fontm[1] * m[3];
2149    m2[2] = fontm[2] * m[0] + fontm[3] * m[2];
2150    m2[3] = fontm[2] * m[1] + fontm[3] * m[3];
2151    m[0] = m2[0];
2152    m[1] = m2[1];
2153    m[2] = m2[2];
2154    m[3] = m2[3];
2155  }
2156  if (fabs(m[0] * m[3]) > fabs(m[1] * m[2])) {
2157    rot = (m[3] < 0) ? 0 : 2;
2158  } else {
2159    rot = (m[2] > 0) ? 1 : 3;
2160  }
2161
2162  curWord = new TextWord(state, rot, x0, y0, charPos, curFont, curFontSize);
2163}
2164
2165void TextPage::addChar(GfxState *state, double x, double y,
2166                       double dx, double dy,
2167                       CharCode c, int nBytes, Unicode *u, int uLen) {
2168  double x1, y1, w1, h1, dx2, dy2, base, sp, delta;
2169  GBool overlap;
2170  int i;
2171
2172  // subtract char and word spacing from the dx,dy values
2173  sp = state->getCharSpace();
2174  if (c == (CharCode)0x20) {
2175    sp += state->getWordSpace();
2176  }
2177  state->textTransformDelta(sp * state->getHorizScaling(), 0, &dx2, &dy2);
2178  dx -= dx2;
2179  dy -= dy2;
2180  state->transformDelta(dx, dy, &w1, &h1);
2181
2182  // throw away chars that aren't inside the page bounds
2183  // (and also do a sanity check on the character size)
2184  state->transform(x, y, &x1, &y1);
2185  if (x1 + w1 < 0 || x1 > pageWidth ||
2186      y1 + h1 < 0 || y1 > pageHeight ||
2187      w1 > pageWidth || h1 > pageHeight) {
2188    charPos += nBytes;
2189    return;
2190  }
2191
2192  // check the tiny chars limit
2193  if (!globalParams->getTextKeepTinyChars() &&
2194      fabs(w1) < 3 && fabs(h1) < 3) {
2195    if (++nTinyChars > 50000) {
2196      charPos += nBytes;
2197      return;
2198    }
2199  }
2200
2201  // break words at space character
2202  if (uLen == 1 && u[0] == (Unicode)0x20) {
2203    if (curWord) {
2204      ++curWord->charLen;
2205    }
2206    charPos += nBytes;
2207    endWord();
2208    return;
2209  }
2210
2211  // start a new word if:
2212  // (1) this character doesn't fall in the right place relative to
2213  //     the end of the previous word (this places upper and lower
2214  //     constraints on the position deltas along both the primary
2215  //     and secondary axes), or
2216  // (2) this character overlaps the previous one (duplicated text), or
2217  // (3) the previous character was an overlap (we want each duplicated
2218  //     character to be in a word by itself at this stage),
2219  // (4) the font size has changed
2220  if (curWord && curWord->len > 0) {
2221    base = sp = delta = 0; // make gcc happy
2222    switch (curWord->rot) {
2223    case 0:
2224      base = y1;
2225      sp = x1 - curWord->xMax;
2226      delta = x1 - curWord->edge[curWord->len - 1];
2227      break;
2228    case 1:
2229      base = x1;
2230      sp = y1 - curWord->yMax;
2231      delta = y1 - curWord->edge[curWord->len - 1];
2232      break;
2233    case 2:
2234      base = y1;
2235      sp = curWord->xMin - x1;
2236      delta = curWord->edge[curWord->len - 1] - x1;
2237      break;
2238    case 3:
2239      base = x1;
2240      sp = curWord->yMin - y1;
2241      delta = curWord->edge[curWord->len - 1] - y1;
2242      break;
2243    }
2244    overlap = fabs(delta) < dupMaxPriDelta * curWord->fontSize &&
2245              fabs(base - curWord->base) < dupMaxSecDelta * curWord->fontSize;
2246    if (overlap || lastCharOverlap ||
2247        sp < -minDupBreakOverlap * curWord->fontSize ||
2248        sp > minWordBreakSpace * curWord->fontSize ||
2249        fabs(base - curWord->base) > 0.5 ||
2250        curFontSize != curWord->fontSize) {
2251      endWord();
2252    }
2253    lastCharOverlap = overlap;
2254  } else {
2255    lastCharOverlap = gFalse;
2256  }
2257
2258  if (uLen != 0) {
2259    // start a new word if needed
2260    if (!curWord) {
2261      beginWord(state, x, y);
2262    }
2263
2264    // page rotation and/or transform matrices can cause text to be
2265    // drawn in reverse order -- in this case, swap the begin/end
2266    // coordinates and break text into individual chars
2267    if ((curWord->rot == 0 && w1 < 0) ||
2268        (curWord->rot == 1 && h1 < 0) ||
2269        (curWord->rot == 2 && w1 > 0) ||
2270        (curWord->rot == 3 && h1 > 0)) {
2271      endWord();
2272      beginWord(state, x + dx, y + dy);
2273      x1 += w1;
2274      y1 += h1;
2275      w1 = -w1;
2276      h1 = -h1;
2277    }
2278
2279    // add the characters to the current word
2280    w1 /= uLen;
2281    h1 /= uLen;
2282    for (i = 0; i < uLen; ++i) {
2283      if (u[i] >= 0xd800 && u[i] < 0xdc00) { /* surrogate pair */
2284        if (i + 1 < uLen && u[i+1] >= 0xdc00 && u[i+1] < 0xe000) {
2285          /* next code is a low surrogate */
2286          Unicode uu = (((u[i] & 0x3ff) << 10) | (u[i+1] & 0x3ff)) + 0x10000;
2287          i++;
2288          curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, uu);
2289        } else {
2290            /* missing low surrogate
2291             replace it with REPLACEMENT CHARACTER (U+FFFD) */
2292          curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, 0xfffd);
2293        }
2294      } else if (u[i] >= 0xdc00 && u[i] < 0xe000) {
2295          /* invalid low surrogate
2296           replace it with REPLACEMENT CHARACTER (U+FFFD) */
2297        curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, 0xfffd);
2298      } else {
2299        curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, u[i]);
2300      }
2301    }
2302  }
2303  if (curWord) {
2304    curWord->charLen += nBytes;
2305  }
2306  charPos += nBytes;
2307}
2308
2309void TextPage::endWord() {
2310  // This check is needed because Type 3 characters can contain
2311  // text-drawing operations (when TextPage is being used via
2312  // {X,Win}SplashOutputDev rather than TextOutputDev).
2313  if (nest > 0) {
2314    --nest;
2315    return;
2316  }
2317
2318  if (curWord) {
2319    addWord(curWord);
2320    curWord = NULL;
2321  }
2322}
2323
2324void TextPage::addWord(TextWord *word) {
2325  // throw away zero-length words -- they don't have valid xMin/xMax
2326  // values, and they're useless anyway
2327  if (word->len == 0) {
2328    delete word;
2329    return;
2330  }
2331
2332  if (rawOrder) {
2333    if (rawLastWord) {
2334      rawLastWord->next = word;
2335    } else {
2336      rawWords = word;
2337    }
2338    rawLastWord = word;
2339  } else {
2340    pools[word->rot]->addWord(word);
2341  }
2342}
2343
2344void TextPage::addUnderline(double x0, double y0, double x1, double y1) {
2345  underlines->append(new TextUnderline(x0, y0, x1, y1));
2346}
2347
2348void TextPage::addLink(int xMin, int yMin, int xMax, int yMax, AnnotLink *link) {
2349  links->append(new TextLink(xMin, yMin, xMax, yMax, link));
2350}
2351
2352void TextPage::coalesce(GBool physLayout, GBool doHTML) {
2353  UnicodeMap *uMap;
2354  TextPool *pool;
2355  TextWord *word0, *word1, *word2;
2356  TextLine *line;
2357  TextBlock *blkList, *blk, *lastBlk, *blk0, *blk1, *blk2;
2358  TextFlow *flow, *lastFlow;
2359  TextUnderline *underline;
2360  TextLink *link;
2361  int rot, poolMinBaseIdx, baseIdx, startBaseIdx, endBaseIdx;
2362  double minBase, maxBase, newMinBase, newMaxBase;
2363  double fontSize, colSpace1, colSpace2, lineSpace, intraLineSpace, blkSpace;
2364  GBool found;
2365  int count[4];
2366  int lrCount;
2367  int col1, col2;
2368  int i, j, n;
2369
2370  if (rawOrder) {
2371    primaryRot = 0;
2372    primaryLR = gTrue;
2373    return;
2374  }
2375
2376  uMap = globalParams->getTextEncoding();
2377  blkList = NULL;
2378  lastBlk = NULL;
2379  nBlocks = 0;
2380  primaryRot = -1;
2381
2382#if 0 // for debugging
2383  printf("*** initial words ***\n");
2384  for (rot = 0; rot < 4; ++rot) {
2385    pool = pools[rot];
2386    for (baseIdx = pool->minBaseIdx; baseIdx <= pool->maxBaseIdx; ++baseIdx) {
2387      for (word0 = pool->getPool(baseIdx); word0; word0 = word0->next) {
2388        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f rot=%d link=%p '",
2389               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2390               word0->base, word0->fontSize, rot*90, word0->link);
2391        for (i = 0; i < word0->len; ++i) {
2392          fputc(word0->text[i] & 0xff, stdout);
2393        }
2394        printf("'\n");
2395      }
2396    }
2397  }
2398  printf("\n");
2399#endif
2400
2401#if 0 //~ for debugging
2402  for (i = 0; i < underlines->getLength(); ++i) {
2403    underline = (TextUnderline *)underlines->get(i);
2404    printf("underline: x=%g..%g y=%g..%g horiz=%d\n",
2405           underline->x0, underline->x1, underline->y0, underline->y1,
2406           underline->horiz);
2407  }
2408#endif
2409
2410  if (doHTML) {
2411
2412    //----- handle underlining
2413    for (i = 0; i < underlines->getLength(); ++i) {
2414      underline = (TextUnderline *)underlines->get(i);
2415      if (underline->horiz) {
2416        // rot = 0
2417        if (pools[0]->minBaseIdx <= pools[0]->maxBaseIdx) {
2418          startBaseIdx = pools[0]->getBaseIdx(underline->y0 + minUnderlineGap);
2419          endBaseIdx = pools[0]->getBaseIdx(underline->y0 + maxUnderlineGap);
2420          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2421            for (word0 = pools[0]->getPool(j); word0; word0 = word0->next) {
2422              //~ need to check the y value against the word baseline
2423              if (underline->x0 < word0->xMin + underlineSlack &&
2424                  word0->xMax - underlineSlack < underline->x1) {
2425                word0->underlined = gTrue;
2426              }
2427            }
2428          }
2429        }
2430
2431        // rot = 2
2432        if (pools[2]->minBaseIdx <= pools[2]->maxBaseIdx) {
2433          startBaseIdx = pools[2]->getBaseIdx(underline->y0 - maxUnderlineGap);
2434          endBaseIdx = pools[2]->getBaseIdx(underline->y0 - minUnderlineGap);
2435          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2436            for (word0 = pools[2]->getPool(j); word0; word0 = word0->next) {
2437              if (underline->x0 < word0->xMin + underlineSlack &&
2438                  word0->xMax - underlineSlack < underline->x1) {
2439                word0->underlined = gTrue;
2440              }
2441            }
2442          }
2443        }
2444      } else {
2445        // rot = 1
2446        if (pools[1]->minBaseIdx <= pools[1]->maxBaseIdx) {
2447          startBaseIdx = pools[1]->getBaseIdx(underline->x0 - maxUnderlineGap);
2448          endBaseIdx = pools[1]->getBaseIdx(underline->x0 - minUnderlineGap);
2449          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2450            for (word0 = pools[1]->getPool(j); word0; word0 = word0->next) {
2451              if (underline->y0 < word0->yMin + underlineSlack &&
2452                  word0->yMax - underlineSlack < underline->y1) {
2453                word0->underlined = gTrue;
2454              }
2455            }
2456          }
2457        }
2458
2459        // rot = 3
2460        if (pools[3]->minBaseIdx <= pools[3]->maxBaseIdx) {
2461          startBaseIdx = pools[3]->getBaseIdx(underline->x0 + minUnderlineGap);
2462          endBaseIdx = pools[3]->getBaseIdx(underline->x0 + maxUnderlineGap);
2463          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2464            for (word0 = pools[3]->getPool(j); word0; word0 = word0->next) {
2465              if (underline->y0 < word0->yMin + underlineSlack &&
2466                  word0->yMax - underlineSlack < underline->y1) {
2467                word0->underlined = gTrue;
2468              }
2469            }
2470          }
2471        }
2472      }
2473    }
2474
2475    //----- handle links
2476    for (i = 0; i < links->getLength(); ++i) {
2477      link = (TextLink *)links->get(i);
2478
2479      // rot = 0
2480      if (pools[0]->minBaseIdx <= pools[0]->maxBaseIdx) {
2481        startBaseIdx = pools[0]->getBaseIdx(link->yMin);
2482        endBaseIdx = pools[0]->getBaseIdx(link->yMax);
2483        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2484          for (word0 = pools[0]->getPool(j); word0; word0 = word0->next) {
2485            if (link->xMin < word0->xMin + hyperlinkSlack &&
2486                word0->xMax - hyperlinkSlack < link->xMax &&
2487                link->yMin < word0->yMin + hyperlinkSlack &&
2488                word0->yMax - hyperlinkSlack < link->yMax) {
2489              word0->link = link->link;
2490            }
2491          }
2492        }
2493      }
2494
2495      // rot = 2
2496      if (pools[2]->minBaseIdx <= pools[2]->maxBaseIdx) {
2497        startBaseIdx = pools[2]->getBaseIdx(link->yMin);
2498        endBaseIdx = pools[2]->getBaseIdx(link->yMax);
2499        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2500          for (word0 = pools[2]->getPool(j); word0; word0 = word0->next) {
2501            if (link->xMin < word0->xMin + hyperlinkSlack &&
2502                word0->xMax - hyperlinkSlack < link->xMax &&
2503                link->yMin < word0->yMin + hyperlinkSlack &&
2504                word0->yMax - hyperlinkSlack < link->yMax) {
2505              word0->link = link->link;
2506            }
2507          }
2508        }
2509      }
2510
2511      // rot = 1
2512      if (pools[1]->minBaseIdx <= pools[1]->maxBaseIdx) {
2513        startBaseIdx = pools[1]->getBaseIdx(link->xMin);
2514        endBaseIdx = pools[1]->getBaseIdx(link->xMax);
2515        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2516          for (word0 = pools[1]->getPool(j); word0; word0 = word0->next) {
2517            if (link->yMin < word0->yMin + hyperlinkSlack &&
2518                word0->yMax - hyperlinkSlack < link->yMax &&
2519                link->xMin < word0->xMin + hyperlinkSlack &&
2520                word0->xMax - hyperlinkSlack < link->xMax) {
2521              word0->link = link->link;
2522            }
2523          }
2524        }
2525      }
2526
2527      // rot = 3
2528      if (pools[3]->minBaseIdx <= pools[3]->maxBaseIdx) {
2529        startBaseIdx = pools[3]->getBaseIdx(link->xMin);
2530        endBaseIdx = pools[3]->getBaseIdx(link->xMax);
2531        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2532          for (word0 = pools[3]->getPool(j); word0; word0 = word0->next) {
2533            if (link->yMin < word0->yMin + hyperlinkSlack &&
2534                word0->yMax - hyperlinkSlack < link->yMax &&
2535                link->xMin < word0->xMin + hyperlinkSlack &&
2536                word0->xMax - hyperlinkSlack < link->xMax) {
2537              word0->link = link->link;
2538            }
2539          }
2540        }
2541      }
2542    }
2543  }
2544
2545  //----- assemble the blocks
2546
2547  //~ add an outer loop for writing mode (vertical text)
2548
2549  // build blocks for each rotation value
2550  for (rot = 0; rot < 4; ++rot) {
2551    pool = pools[rot];
2552    poolMinBaseIdx = pool->minBaseIdx;
2553    count[rot] = 0;
2554
2555    // add blocks until no more words are left
2556    while (1) {
2557
2558      // find the first non-empty line in the pool
2559      for (;
2560           poolMinBaseIdx <= pool->maxBaseIdx &&
2561             !pool->getPool(poolMinBaseIdx);
2562           ++poolMinBaseIdx) ;
2563      if (poolMinBaseIdx > pool->maxBaseIdx) {
2564        break;
2565      }
2566
2567      // look for the left-most word in the first four lines of the
2568      // pool -- this avoids starting with a superscript word
2569      startBaseIdx = poolMinBaseIdx;
2570      for (baseIdx = poolMinBaseIdx + 1;
2571           baseIdx < poolMinBaseIdx + 4 && baseIdx <= pool->maxBaseIdx;
2572           ++baseIdx) {
2573        if (!pool->getPool(baseIdx)) {
2574          continue;
2575        }
2576        if (pool->getPool(baseIdx)->primaryCmp(pool->getPool(startBaseIdx))
2577            < 0) {
2578          startBaseIdx = baseIdx;
2579        }
2580      }
2581
2582      // create a new block
2583      word0 = pool->getPool(startBaseIdx);
2584      pool->setPool(startBaseIdx, word0->next);
2585      word0->next = NULL;
2586      blk = new TextBlock(this, rot);
2587      blk->addWord(word0);
2588
2589      fontSize = word0->fontSize;
2590      minBase = maxBase = word0->base;
2591      colSpace1 = minColSpacing1 * fontSize;
2592      colSpace2 = minColSpacing2 * fontSize;
2593      lineSpace = maxLineSpacingDelta * fontSize;
2594      intraLineSpace = maxIntraLineDelta * fontSize;
2595
2596      // add words to the block
2597      do {
2598        found = gFalse;
2599
2600        // look for words on the line above the current top edge of
2601        // the block
2602        newMinBase = minBase;
2603        for (baseIdx = pool->getBaseIdx(minBase);
2604             baseIdx >= pool->getBaseIdx(minBase - lineSpace);
2605             --baseIdx) {
2606          word0 = NULL;
2607          word1 = pool->getPool(baseIdx);
2608          while (word1) {
2609            if (word1->base < minBase &&
2610                word1->base >= minBase - lineSpace &&
2611                ((rot == 0 || rot == 2)
2612                 ? (word1->xMin < blk->xMax && word1->xMax > blk->xMin)
2613                 : (word1->yMin < blk->yMax && word1->yMax > blk->yMin)) &&
2614                fabs(word1->fontSize - fontSize) <
2615                  maxBlockFontSizeDelta1 * fontSize) {
2616              word2 = word1;
2617              if (word0) {
2618                word0->next = word1->next;
2619              } else {
2620                pool->setPool(baseIdx, word1->next);
2621              }
2622              word1 = word1->next;
2623              word2->next = NULL;
2624              blk->addWord(word2);
2625              found = gTrue;
2626              newMinBase = word2->base;
2627            } else {
2628              word0 = word1;
2629              word1 = word1->next;
2630            }
2631          }
2632        }
2633        minBase = newMinBase;
2634
2635        // look for words on the line below the current bottom edge of
2636        // the block
2637        newMaxBase = maxBase;
2638        for (baseIdx = pool->getBaseIdx(maxBase);
2639             baseIdx <= pool->getBaseIdx(maxBase + lineSpace);
2640             ++baseIdx) {
2641          word0 = NULL;
2642          word1 = pool->getPool(baseIdx);
2643          while (word1) {
2644            if (word1->base > maxBase &&
2645                word1->base <= maxBase + lineSpace &&
2646                ((rot == 0 || rot == 2)
2647                 ? (word1->xMin < blk->xMax && word1->xMax > blk->xMin)
2648                 : (word1->yMin < blk->yMax && word1->yMax > blk->yMin)) &&
2649                fabs(word1->fontSize - fontSize) <
2650                  maxBlockFontSizeDelta1 * fontSize) {
2651              word2 = word1;
2652              if (word0) {
2653                word0->next = word1->next;
2654              } else {
2655                pool->setPool(baseIdx, word1->next);
2656              }
2657              word1 = word1->next;
2658              word2->next = NULL;
2659              blk->addWord(word2);
2660              found = gTrue;
2661              newMaxBase = word2->base;
2662            } else {
2663              word0 = word1;
2664              word1 = word1->next;
2665            }
2666          }
2667        }
2668        maxBase = newMaxBase;
2669
2670        // look for words that are on lines already in the block, and
2671        // that overlap the block horizontally
2672        for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2673             baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2674             ++baseIdx) {
2675          word0 = NULL;
2676          word1 = pool->getPool(baseIdx);
2677          while (word1) {
2678            if (word1->base >= minBase - intraLineSpace &&
2679                word1->base <= maxBase + intraLineSpace &&
2680                ((rot == 0 || rot == 2)
2681                 ? (word1->xMin < blk->xMax + colSpace1 &&
2682                    word1->xMax > blk->xMin - colSpace1)
2683                 : (word1->yMin < blk->yMax + colSpace1 &&
2684                    word1->yMax > blk->yMin - colSpace1)) &&
2685                fabs(word1->fontSize - fontSize) <
2686                  maxBlockFontSizeDelta2 * fontSize) {
2687              word2 = word1;
2688              if (word0) {
2689                word0->next = word1->next;
2690              } else {
2691                pool->setPool(baseIdx, word1->next);
2692              }
2693              word1 = word1->next;
2694              word2->next = NULL;
2695              blk->addWord(word2);
2696              found = gTrue;
2697            } else {
2698              word0 = word1;
2699              word1 = word1->next;
2700            }
2701          }
2702        }
2703
2704        // only check for outlying words (the next two chunks of code)
2705        // if we didn't find anything else
2706        if (found) {
2707          continue;
2708        }
2709
2710        // scan down the left side of the block, looking for words
2711        // that are near (but not overlapping) the block; if there are
2712        // three or fewer, add them to the block
2713        n = 0;
2714        for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2715             baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2716             ++baseIdx) {
2717          word1 = pool->getPool(baseIdx);
2718          while (word1) {
2719            if (word1->base >= minBase - intraLineSpace &&
2720                word1->base <= maxBase + intraLineSpace &&
2721                ((rot == 0 || rot == 2)
2722                 ? (word1->xMax <= blk->xMin &&
2723                    word1->xMax > blk->xMin - colSpace2)
2724                 : (word1->yMax <= blk->yMin &&
2725                    word1->yMax > blk->yMin - colSpace2)) &&
2726                fabs(word1->fontSize - fontSize) <
2727                  maxBlockFontSizeDelta3 * fontSize) {
2728              ++n;
2729              break;
2730            }
2731            word1 = word1->next;
2732          }
2733        }
2734        if (n > 0 && n <= 3) {
2735          for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2736               baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2737               ++baseIdx) {
2738            word0 = NULL;
2739            word1 = pool->getPool(baseIdx);
2740            while (word1) {
2741              if (word1->base >= minBase - intraLineSpace &&
2742                  word1->base <= maxBase + intraLineSpace &&
2743                  ((rot == 0 || rot == 2)
2744                   ? (word1->xMax <= blk->xMin &&
2745                      word1->xMax > blk->xMin - colSpace2)
2746                   : (word1->yMax <= blk->yMin &&
2747                      word1->yMax > blk->yMin - colSpace2)) &&
2748                  fabs(word1->fontSize - fontSize) <
2749                    maxBlockFontSizeDelta3 * fontSize) {
2750                word2 = word1;
2751                if (word0) {
2752                  word0->next = word1->next;
2753                } else {
2754                  pool->setPool(baseIdx, word1->next);
2755                }
2756                word1 = word1->next;
2757                word2->next = NULL;
2758                blk->addWord(word2);
2759                if (word2->base < minBase) {
2760                  minBase = word2->base;
2761                } else if (word2->base > maxBase) {
2762                  maxBase = word2->base;
2763                }
2764                found = gTrue;
2765                break;
2766              } else {
2767                word0 = word1;
2768                word1 = word1->next;
2769              }
2770            }
2771          }
2772        }
2773
2774        // scan down the right side of the block, looking for words
2775        // that are near (but not overlapping) the block; if there are
2776        // three or fewer, add them to the block
2777        n = 0;
2778        for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2779             baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2780             ++baseIdx) {
2781          word1 = pool->getPool(baseIdx);
2782          while (word1) {
2783            if (word1->base >= minBase - intraLineSpace &&
2784                word1->base <= maxBase + intraLineSpace &&
2785                ((rot == 0 || rot == 2)
2786                 ? (word1->xMin >= blk->xMax &&
2787                    word1->xMin < blk->xMax + colSpace2)
2788                 : (word1->yMin >= blk->yMax &&
2789                    word1->yMin < blk->yMax + colSpace2)) &&
2790                fabs(word1->fontSize - fontSize) <
2791                  maxBlockFontSizeDelta3 * fontSize) {
2792              ++n;
2793              break;
2794            }
2795            word1 = word1->next;
2796          }
2797        }
2798        if (n > 0 && n <= 3) {
2799          for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2800               baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2801               ++baseIdx) {
2802            word0 = NULL;
2803            word1 = pool->getPool(baseIdx);
2804            while (word1) {
2805              if (word1->base >= minBase - intraLineSpace &&
2806                  word1->base <= maxBase + intraLineSpace &&
2807                  ((rot == 0 || rot == 2)
2808                   ? (word1->xMin >= blk->xMax &&
2809                      word1->xMin < blk->xMax + colSpace2)
2810                   : (word1->yMin >= blk->yMax &&
2811                      word1->yMin < blk->yMax + colSpace2)) &&
2812                  fabs(word1->fontSize - fontSize) <
2813                    maxBlockFontSizeDelta3 * fontSize) {
2814                word2 = word1;
2815                if (word0) {
2816                  word0->next = word1->next;
2817                } else {
2818                  pool->setPool(baseIdx, word1->next);
2819                }
2820                word1 = word1->next;
2821                word2->next = NULL;
2822                blk->addWord(word2);
2823                if (word2->base < minBase) {
2824                  minBase = word2->base;
2825                } else if (word2->base > maxBase) {
2826                  maxBase = word2->base;
2827                }
2828                found = gTrue;
2829                break;
2830              } else {
2831                word0 = word1;
2832                word1 = word1->next;
2833              }
2834            }
2835          }
2836        }
2837
2838      } while (found);
2839
2840      //~ need to compute the primary writing mode (horiz/vert) in
2841      //~ addition to primary rotation
2842
2843      // coalesce the block, and add it to the list
2844      blk->coalesce(uMap);
2845      if (lastBlk) {
2846        lastBlk->next = blk;
2847      } else {
2848        blkList = blk;
2849      }
2850      lastBlk = blk;
2851      count[rot] += blk->charCount;
2852      if (primaryRot < 0 || count[rot] > count[primaryRot]) {
2853        primaryRot = rot;
2854      }
2855      ++nBlocks;
2856    }
2857  }
2858
2859#if 0 // for debugging
2860  printf("*** rotation ***\n");
2861  for (rot = 0; rot < 4; ++rot) {
2862    printf("  %d: %6d\n", rot, count[rot]);
2863  }
2864  printf("  primary rot = %d\n", primaryRot);
2865  printf("\n");
2866#endif
2867
2868#if 0 // for debugging
2869  printf("*** blocks ***\n");
2870  for (blk = blkList; blk; blk = blk->next) {
2871    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f\n",
2872           blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax);
2873    for (line = blk->lines; line; line = line->next) {
2874      printf("  line: x=%.2f..%.2f y=%.2f..%.2f base=%.2f\n",
2875             line->xMin, line->xMax, line->yMin, line->yMax, line->base);
2876      for (word0 = line->words; word0; word0 = word0->next) {
2877        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2878               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2879               word0->base, word0->fontSize, word0->spaceAfter);
2880        for (i = 0; i < word0->len; ++i) {
2881          fputc(word0->text[i] & 0xff, stdout);
2882        }
2883        printf("'\n");
2884      }
2885    }
2886  }
2887  printf("\n");
2888#endif
2889
2890  // determine the primary direction
2891  lrCount = 0;
2892  for (blk = blkList; blk; blk = blk->next) {
2893    for (line = blk->lines; line; line = line->next) {
2894      for (word0 = line->words; word0; word0 = word0->next) {
2895        for (i = 0; i < word0->len; ++i) {
2896          if (unicodeTypeL(word0->text[i])) {
2897            ++lrCount;
2898          } else if (unicodeTypeR(word0->text[i])) {
2899            --lrCount;
2900          }
2901        }
2902      }
2903    }
2904  }
2905  primaryLR = lrCount >= 0;
2906
2907#if 0 // for debugging
2908  printf("*** direction ***\n");
2909  printf("lrCount = %d\n", lrCount);
2910  printf("primaryLR = %d\n", primaryLR);
2911#endif
2912
2913  //----- column assignment
2914
2915  // sort blocks into xy order for column assignment
2916  if (blocks)
2917    gfree (blocks);
2918  blocks = (TextBlock **)gmallocn(nBlocks, sizeof(TextBlock *));
2919  for (blk = blkList, i = 0; blk; blk = blk->next, ++i) {
2920    blocks[i] = blk;
2921  }
2922  qsort(blocks, nBlocks, sizeof(TextBlock *), &TextBlock::cmpXYPrimaryRot);
2923
2924  // column assignment
2925  for (i = 0; i < nBlocks; ++i) {
2926    blk0 = blocks[i];
2927    col1 = 0;
2928    for (j = 0; j < i; ++j) {
2929      blk1 = blocks[j];
2930      col2 = 0; // make gcc happy
2931      switch (primaryRot) {
2932      case 0:
2933        if (blk0->xMin > blk1->xMax) {
2934          col2 = blk1->col + blk1->nColumns + 3;
2935        } else if (blk1->xMax == blk1->xMin) {
2936          col2 = blk1->col;
2937        } else {
2938          col2 = blk1->col + (int)(((blk0->xMin - blk1->xMin) /
2939                                    (blk1->xMax - blk1->xMin)) *
2940                                   blk1->nColumns);
2941        }
2942        break;
2943      case 1:
2944        if (blk0->yMin > blk1->yMax) {
2945          col2 = blk1->col + blk1->nColumns + 3;
2946        } else if (blk1->yMax == blk1->yMin) {
2947          col2 = blk1->col;
2948        } else {
2949          col2 = blk1->col + (int)(((blk0->yMin - blk1->yMin) /
2950                                    (blk1->yMax - blk1->yMin)) *
2951                                   blk1->nColumns);
2952        }
2953        break;
2954      case 2:
2955        if (blk0->xMax < blk1->xMin) {
2956          col2 = blk1->col + blk1->nColumns + 3;
2957        } else if (blk1->xMin == blk1->xMax) {
2958          col2 = blk1->col;
2959        } else {
2960          col2 = blk1->col + (int)(((blk0->xMax - blk1->xMax) /
2961                                    (blk1->xMin - blk1->xMax)) *
2962                                   blk1->nColumns);
2963        }
2964        break;
2965      case 3:
2966        if (blk0->yMax < blk1->yMin) {
2967          col2 = blk1->col + blk1->nColumns + 3;
2968        } else if (blk1->yMin == blk1->yMax) {
2969          col2 = blk1->col;
2970        } else {
2971          col2 = blk1->col + (int)(((blk0->yMax - blk1->yMax) /
2972                                    (blk1->yMin - blk1->yMax)) *
2973                                   blk1->nColumns);
2974        }
2975        break;
2976      }
2977      if (col2 > col1) {
2978        col1 = col2;
2979      }
2980    }
2981    blk0->col = col1;
2982    for (line = blk0->lines; line; line = line->next) {
2983      for (j = 0; j <= line->len; ++j) {
2984        line->col[j] += col1;
2985      }
2986    }
2987  }
2988
2989#if 0 // for debugging
2990  printf("*** blocks, after column assignment ***\n");
2991  for (blk = blkList; blk; blk = blk->next) {
2992    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f col=%d nCols=%d\n",
2993           blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax, blk->col,
2994           blk->nColumns);
2995    for (line = blk->lines; line; line = line->next) {
2996      printf("  line:\n");
2997      for (word0 = line->words; word0; word0 = word0->next) {
2998        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2999               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
3000               word0->base, word0->fontSize, word0->spaceAfter);
3001        for (i = 0; i < word0->len; ++i) {
3002          fputc(word0->text[i] & 0xff, stdout);
3003        }
3004        printf("'\n");
3005      }
3006    }
3007  }
3008  printf("\n");
3009#endif
3010
3011  //----- reading order sort
3012
3013  // compute space on left and right sides of each block
3014  for (i = 0; i < nBlocks; ++i) {
3015    blk0 = blocks[i];
3016    for (j = 0; j < nBlocks; ++j) {
3017      blk1 = blocks[j];
3018      if (blk1 != blk0) {
3019        blk0->updatePriMinMax(blk1);
3020      }
3021    }
3022  }
3023
3024#if 0 // for debugging
3025  printf("PAGE\n");
3026#endif
3027
3028  int sortPos = 0;
3029  GBool *visited = (GBool *)gmallocn(nBlocks, sizeof(GBool));
3030  for (i = 0; i < nBlocks; i++) {
3031    visited[i] = gFalse;
3032  }
3033
3034  double bxMin0, byMin0, bxMin1, byMin1;
3035  int numTables = 0;
3036  int tableId = -1;
3037  int correspondenceX, correspondenceY;
3038  double xCentre1, yCentre1, xCentre2, yCentre2;
3039  double xCentre3, yCentre3, xCentre4, yCentre4;
3040  double deltaX, deltaY;
3041  TextBlock *fblk2 = NULL, *fblk3 = NULL, *fblk4 = NULL;
3042
3043  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3044    blk1->ExMin = blk1->xMin;
3045    blk1->ExMax = blk1->xMax;
3046    blk1->EyMin = blk1->yMin;
3047    blk1->EyMax = blk1->yMax;
3048
3049    bxMin0 = DBL_MAX;
3050    byMin0 = DBL_MAX;
3051    bxMin1 = DBL_MAX;
3052    byMin1 = DBL_MAX;
3053
3054    fblk2 = NULL;
3055    fblk3 = NULL;
3056    fblk4 = NULL;
3057
3058    /*  find fblk2, fblk3 and fblk4 so that
3059     *  fblk2 is on the right of blk1 and overlap with blk1 in y axis
3060     *  fblk3 is under blk1 and overlap with blk1 in x axis
3061     *  fblk4 is under blk1 and on the right of blk1
3062     *  and they are closest to blk1
3063     */
3064    for (blk2 = blkList; blk2; blk2 = blk2->next) {
3065      if (blk2 != blk1) {
3066        if (blk2->yMin <= blk1->yMax &&
3067            blk2->yMax >= blk1->yMin &&
3068            blk2->xMin > blk1->xMax &&
3069            blk2->xMin < bxMin0) {
3070          bxMin0 = blk2->xMin;
3071          fblk2 = blk2;
3072        } else if (blk2->xMin <= blk1->xMax &&
3073                   blk2->xMax >= blk1->xMin &&
3074                   blk2->yMin > blk1->yMax &&
3075                   blk2->yMin < byMin0) {
3076          byMin0 = blk2->yMin;
3077          fblk3 = blk2;
3078        } else if (blk2->xMin > blk1->xMax &&
3079                   blk2->xMin < bxMin1 &&
3080                   blk2->yMin > blk1->yMax &&
3081                   blk2->yMin < byMin1) {
3082          bxMin1 = blk2->xMin;
3083          byMin1 = blk2->yMin;
3084          fblk4 = blk2;
3085        }
3086      }
3087    }
3088
3089    /*  fblk4 can not overlap with fblk3 in x and with fblk2 in y
3090     *  fblk2 can not overlap with fblk3 in x and y
3091     *  fblk4 has to overlap with fblk3 in y and with fblk2 in x
3092     */
3093    if (fblk2 != NULL &&
3094        fblk3 != NULL &&
3095        fblk4 != NULL) {
3096      if (((fblk3->xMin <= fblk4->xMax && fblk3->xMax >= fblk4->xMin) ||
3097           (fblk2->yMin <= fblk4->yMax && fblk2->yMax >= fblk4->yMin) ||
3098           (fblk2->xMin <= fblk3->xMax && fblk2->xMax >= fblk3->xMin) ||
3099           (fblk2->yMin <= fblk3->yMax && fblk2->yMax >= fblk3->yMin)) ||
3100          !(fblk4->xMin <= fblk2->xMax && fblk4->xMax >= fblk2->xMin &&
3101            fblk4->yMin <= fblk3->yMax && fblk4->yMax >= fblk3->yMin)) {
3102        fblk2 = NULL;
3103        fblk3 = NULL;
3104        fblk4 = NULL;
3105      }
3106    }
3107
3108    // if we found any then look whether they form a table
3109    if (fblk2 != NULL &&
3110        fblk3 != NULL &&
3111        fblk4 != NULL) {
3112      tableId = -1;
3113      correspondenceX = 0;
3114      correspondenceY = 0;
3115      deltaX = 0.0;
3116      deltaY = 0.0;
3117
3118      if (blk1->lines && blk1->lines->words)
3119        deltaX = blk1->lines->words->getFontSize();
3120      if (fblk2->lines && fblk2->lines->words)
3121        deltaX = deltaX < fblk2->lines->words->getFontSize() ?
3122                   deltaX : fblk2->lines->words->getFontSize();
3123      if (fblk3->lines && fblk3->lines->words)
3124        deltaX = deltaX < fblk3->lines->words->getFontSize() ?
3125                   deltaX : fblk3->lines->words->getFontSize();
3126      if (fblk4->lines && fblk4->lines->words)
3127        deltaX = deltaX < fblk4->lines->words->getFontSize() ?
3128                   deltaX : fblk4->lines->words->getFontSize();
3129
3130      deltaY = deltaX;
3131
3132      deltaX *= minColSpacing1;
3133      deltaY *= maxIntraLineDelta;
3134
3135      xCentre1 = (blk1->xMax + blk1->xMin) / 2.0;
3136      yCentre1 = (blk1->yMax + blk1->yMin) / 2.0;
3137      xCentre2 = (fblk2->xMax + fblk2->xMin) / 2.0;
3138      yCentre2 = (fblk2->yMax + fblk2->yMin) / 2.0;
3139      xCentre3 = (fblk3->xMax + fblk3->xMin) / 2.0;
3140      yCentre3 = (fblk3->yMax + fblk3->yMin) / 2.0;
3141      xCentre4 = (fblk4->xMax + fblk4->xMin) / 2.0;
3142      yCentre4 = (fblk4->yMax + fblk4->yMin) / 2.0;
3143
3144      // are blocks centrally aligned in x ?
3145      if (fabs (xCentre1 - xCentre3) <= deltaX &&
3146          fabs (xCentre2 - xCentre4) <= deltaX)
3147        correspondenceX++;
3148
3149      // are blocks centrally aligned in y ?
3150      if (fabs (yCentre1 - yCentre2) <= deltaY &&
3151          fabs (yCentre3 - yCentre4) <= deltaY)
3152        correspondenceY++;
3153
3154      // are blocks aligned to the left ?
3155      if (fabs (blk1->xMin - fblk3->xMin) <= deltaX &&
3156          fabs (fblk2->xMin - fblk4->xMin) <= deltaX)
3157        correspondenceX++;
3158
3159      // are blocks aligned to the right ?
3160      if (fabs (blk1->xMax - fblk3->xMax) <= deltaX &&
3161          fabs (fblk2->xMax - fblk4->xMax) <= deltaX)
3162        correspondenceX++;
3163
3164      // are blocks aligned to the top ?
3165      if (fabs (blk1->yMin - fblk2->yMin) <= deltaY &&
3166          fabs (fblk3->yMin - fblk4->yMin) <= deltaY)
3167        correspondenceY++;
3168
3169      // are blocks aligned to the bottom ?
3170      if (fabs (blk1->yMax - fblk2->yMax) <= deltaY &&
3171          fabs (fblk3->yMax - fblk4->yMax) <= deltaY)
3172        correspondenceY++;
3173
3174      // are blocks aligned in x and y ?
3175      if (correspondenceX > 0 &&
3176          correspondenceY > 0) {
3177
3178        // find maximal tableId
3179        tableId = tableId < fblk4->tableId ? fblk4->tableId : tableId;
3180        tableId = tableId < fblk3->tableId ? fblk3->tableId : tableId;
3181        tableId = tableId < fblk2->tableId ? fblk2->tableId : tableId;
3182        tableId = tableId < blk1->tableId ? blk1->tableId : tableId;
3183
3184        // if the tableId is -1, then we found new table
3185        if (tableId < 0) {
3186          tableId = numTables;
3187          numTables++;
3188        }
3189
3190        blk1->tableId = tableId;
3191        fblk2->tableId = tableId;
3192        fblk3->tableId = tableId;
3193        fblk4->tableId = tableId;
3194      }
3195    }
3196  }
3197
3198  /*  set extended bounding boxes of all table entries
3199   *  so that they contain whole table
3200   *  (we need to process whole table size when comparing it
3201   *   with regular text blocks)
3202   */
3203  PDFRectangle *envelopes = new PDFRectangle [numTables];
3204  TextBlock **ending_blocks = new TextBlock* [numTables];
3205
3206  for (i = 0; i < numTables; i++) {
3207    envelopes[i].x1 = DBL_MAX;
3208    envelopes[i].x2 = DBL_MIN;
3209    envelopes[i].y1 = DBL_MAX;
3210    envelopes[i].y2 = DBL_MIN;
3211  }
3212
3213  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3214    if (blk1->tableId >= 0) {
3215      if (blk1->ExMin < envelopes[blk1->tableId].x1) {
3216        envelopes[blk1->tableId].x1 = blk1->ExMin;
3217        if (!blk1->page->primaryLR)
3218          ending_blocks[blk1->tableId] = blk1;
3219      }
3220
3221      if (blk1->ExMax > envelopes[blk1->tableId].x2) {
3222        envelopes[blk1->tableId].x2 = blk1->ExMax;
3223        if (blk1->page->primaryLR)
3224          ending_blocks[blk1->tableId] = blk1;
3225      }
3226
3227      envelopes[blk1->tableId].y1 = blk1->EyMin < envelopes[blk1->tableId].y1 ?
3228                                      blk1->EyMin : envelopes[blk1->tableId].y1;
3229      envelopes[blk1->tableId].y2 = blk1->EyMax > envelopes[blk1->tableId].y2 ?
3230                                      blk1->EyMax : envelopes[blk1->tableId].y2;
3231    }
3232  }
3233
3234  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3235    if (blk1->tableId >= 0 &&
3236        blk1->xMin <= ending_blocks[blk1->tableId]->xMax &&
3237        blk1->xMax >= ending_blocks[blk1->tableId]->xMin) {
3238      blk1->tableEnd = gTrue;
3239    }
3240  }
3241
3242  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3243    if (blk1->tableId >= 0) {
3244      blk1->ExMin = envelopes[blk1->tableId].x1;
3245      blk1->ExMax = envelopes[blk1->tableId].x2;
3246      blk1->EyMin = envelopes[blk1->tableId].y1;
3247      blk1->EyMax = envelopes[blk1->tableId].y2;
3248    }
3249  }
3250  delete[] envelopes;
3251  delete[] ending_blocks;
3252
3253
3254  /*  set extended bounding boxes of all other blocks
3255   *  so that they extend in x without hitting neighbours
3256   */
3257  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3258    if (!blk1->tableId >= 0) {
3259      double xMax = DBL_MAX;
3260      double xMin = DBL_MIN;
3261
3262      for (blk2 = blkList; blk2; blk2 = blk2->next) {
3263        if (blk2 == blk1)
3264           continue;
3265
3266        if (blk1->yMin <= blk2->yMax && blk1->yMax >= blk2->yMin) {
3267          if (blk2->xMin < xMax && blk2->xMin > blk1->xMax)
3268            xMax = blk2->xMin;
3269
3270          if (blk2->xMax > xMin && blk2->xMax < blk1->xMin)
3271            xMin = blk2->xMax;
3272        }
3273      }
3274
3275      for (blk2 = blkList; blk2; blk2 = blk2->next) {
3276        if (blk2 == blk1)
3277           continue;
3278
3279        if (blk2->xMax > blk1->ExMax &&
3280            blk2->xMax <= xMax &&
3281            blk2->yMin >= blk1->yMax) {
3282          blk1->ExMax = blk2->xMax;
3283        }
3284
3285        if (blk2->xMin < blk1->ExMin &&
3286            blk2->xMin >= xMin &&
3287            blk2->yMin >= blk1->yMax)
3288          blk1->ExMin = blk2->xMin;
3289      }
3290    }
3291  }
3292
3293  i = -1;
3294  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3295    i++;
3296    sortPos = blk1->visitDepthFirst(blkList, i, blocks, sortPos, visited);
3297  }
3298  if (visited) {
3299    gfree(visited);
3300  }
3301
3302#if 0 // for debugging
3303  printf("*** blocks, after ro sort ***\n");
3304  for (i = 0; i < nBlocks; ++i) {
3305    blk = blocks[i];
3306    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f space=%.2f..%.2f\n",
3307           blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax,
3308           blk->priMin, blk->priMax);
3309    for (line = blk->lines; line; line = line->next) {
3310      printf("  line:\n");
3311      for (word0 = line->words; word0; word0 = word0->next) {
3312        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
3313               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
3314               word0->base, word0->fontSize, word0->spaceAfter);
3315        for (j = 0; j < word0->len; ++j) {
3316          fputc(word0->text[j] & 0xff, stdout);
3317        }
3318        printf("'\n");
3319      }
3320    }
3321  }
3322  printf("\n");
3323  fflush(stdout);
3324#endif
3325
3326  // build the flows
3327  //~ this needs to be adjusted for writing mode (vertical text)
3328  //~ this also needs to account for right-to-left column ordering
3329  flow = NULL;
3330  while (flows) {
3331    flow = flows;
3332    flows = flows->next;
3333    delete flow;
3334  }
3335  flows = lastFlow = NULL;
3336  // assume blocks are already in reading order,
3337  // and construct flows accordingly.
3338  for (i = 0; i < nBlocks; i++) {
3339    blk = blocks[i];
3340    blk->next = NULL;
3341    if (flow) {
3342      blk1 = blocks[i - 1];
3343      blkSpace = maxBlockSpacing * blk1->lines->words->fontSize;
3344      if (blk1->secondaryDelta(blk) <= blkSpace &&
3345          blk->isBelow(blk1) &&
3346          flow->blockFits(blk, blk1)) {
3347        flow->addBlock(blk);
3348        continue;
3349      }
3350    }
3351    flow = new TextFlow(this, blk);
3352    if (lastFlow) {
3353      lastFlow->next = flow;
3354    } else {
3355      flows = flow;
3356    }
3357    lastFlow = flow;
3358  }
3359
3360#if 0 // for debugging
3361  printf("*** flows ***\n");
3362  for (flow = flows; flow; flow = flow->next) {
3363    printf("flow: x=%.2f..%.2f y=%.2f..%.2f pri:%.2f..%.2f\n",
3364           flow->xMin, flow->xMax, flow->yMin, flow->yMax,
3365           flow->priMin, flow->priMax);
3366    for (blk = flow->blocks; blk; blk = blk->next) {
3367      printf("  block: rot=%d x=%.2f..%.2f y=%.2f..%.2f pri=%.2f..%.2f\n",
3368             blk->rot, blk->ExMin, blk->ExMax, blk->EyMin, blk->EyMax,
3369             blk->priMin, blk->priMax);
3370      for (line = blk->lines; line; line = line->next) {
3371        printf("    line:\n");
3372        for (word0 = line->words; word0; word0 = word0->next) {
3373          printf("      word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
3374                 word0->xMin, word0->xMax, word0->yMin, word0->yMax,
3375                 word0->base, word0->fontSize, word0->spaceAfter);
3376          for (i = 0; i < word0->len; ++i) {
3377            fputc(word0->text[i] & 0xff, stdout);
3378          }
3379          printf("'\n");
3380        }
3381      }
3382    }
3383  }
3384  printf("\n");
3385#endif
3386
3387  if (uMap) {
3388    uMap->decRefCnt();
3389  }
3390}
3391
3392GBool TextPage::findText(Unicode *s, int len,
3393                         GBool startAtTop, GBool stopAtBottom,
3394                         GBool startAtLast, GBool stopAtLast,
3395                         GBool caseSensitive, GBool backward,
3396                         double *xMin, double *yMin,
3397                         double *xMax, double *yMax) {
3398  TextBlock *blk;
3399  TextLine *line;
3400  Unicode *s2, *txt;
3401  Unicode *p;
3402  int txtSize, m, i, j, k;
3403  double xStart, yStart, xStop, yStop;
3404  double xMin0, yMin0, xMax0, yMax0;
3405  double xMin1, yMin1, xMax1, yMax1;
3406  GBool found;
3407
3408  //~ needs to handle right-to-left text
3409
3410  if (rawOrder) {
3411    return gFalse;
3412  }
3413
3414  // convert the search string to uppercase
3415  if (!caseSensitive) {
3416    s2 = unicodeNormalizeNFKC(s, len, &len, NULL);
3417    for (i = 0; i < len; ++i) {
3418      s2[i] = unicodeToUpper(s2[i]);
3419    }
3420  } else {
3421    s2 = unicodeNormalizeNFKC(s, len, &len, NULL);
3422  }
3423
3424  txt = NULL;
3425  txtSize = 0;
3426
3427  xStart = yStart = xStop = yStop = 0;
3428  if (startAtLast && haveLastFind) {
3429    xStart = lastFindXMin;
3430    yStart = lastFindYMin;
3431  } else if (!startAtTop) {
3432    xStart = *xMin;
3433    yStart = *yMin;
3434  }
3435  if (stopAtLast && haveLastFind) {
3436    xStop = lastFindXMin;
3437    yStop = lastFindYMin;
3438  } else if (!stopAtBottom) {
3439    xStop = *xMax;
3440    yStop = *yMax;
3441  }
3442
3443  found = gFalse;
3444  xMin0 = xMax0 = yMin0 = yMax0 = 0; // make gcc happy
3445  xMin1 = xMax1 = yMin1 = yMax1 = 0; // make gcc happy
3446
3447  for (i = backward ? nBlocks - 1 : 0;
3448       backward ? i >= 0 : i < nBlocks;
3449       i += backward ? -1 : 1) {
3450    blk = blocks[i];
3451
3452    // check: is the block above the top limit?
3453    if (!startAtTop && (backward ? blk->yMin > yStart : blk->yMax < yStart)) {
3454      continue;
3455    }
3456
3457    // check: is the block below the bottom limit?
3458    if (!stopAtBottom && (backward ? blk->yMax < yStop : blk->yMin > yStop)) {
3459      break;
3460    }
3461
3462    for (line = blk->lines; line; line = line->next) {
3463
3464      // check: is the line above the top limit?
3465      if (!startAtTop &&
3466          (backward ? line->yMin > yStart : line->yMin < yStart)) {
3467        continue;
3468      }
3469
3470      // check: is the line below the bottom limit?
3471      if (!stopAtBottom &&
3472          (backward ? line->yMin < yStop : line->yMin > yStop)) {
3473        continue;
3474      }
3475
3476      if (!line->normalized)
3477        line->normalized = unicodeNormalizeNFKC(line->text, line->len, 
3478                                                &line->normalized_len, 
3479                                                &line->normalized_idx);
3480      // convert the line to uppercase
3481      m = line->normalized_len;
3482      if (!caseSensitive) {
3483        if (m > txtSize) {
3484          txt = (Unicode *)greallocn(txt, m, sizeof(Unicode));
3485          txtSize = m;
3486        }
3487        for (k = 0; k < m; ++k) {
3488          txt[k] = unicodeToUpper(line->normalized[k]);
3489          }
3490          } else {
3491        txt = line->normalized;
3492          }
3493
3494      // search each position in this line
3495      j = backward ? m - len : 0;
3496      p = txt + j;
3497      while (backward ? j >= 0 : j <= m - len) {
3498
3499        // compare the strings
3500        for (k = 0; k < len; ++k) {
3501          if (p[k] != s2[k]) {
3502            break;
3503          }
3504        }
3505
3506        // found it
3507        if (k == len) {
3508          // where s2 matches a subsequence of a compatibility equivalence
3509          // decomposition, highlight the entire glyph, since we don't know
3510          // the internal layout of subglyph components
3511          int normStart = line->normalized_idx[j];
3512          int normAfterEnd = line->normalized_idx[j + len - 1] + 1;
3513          switch (line->rot) {
3514          case 0:
3515            xMin1 = line->edge[normStart];
3516            xMax1 = line->edge[normAfterEnd];
3517            yMin1 = line->yMin;
3518            yMax1 = line->yMax;
3519            break;
3520          case 1:
3521            xMin1 = line->xMin;
3522            xMax1 = line->xMax;
3523            yMin1 = line->edge[normStart];
3524            yMax1 = line->edge[normAfterEnd];
3525            break;
3526          case 2:
3527            xMin1 = line->edge[normAfterEnd];
3528            xMax1 = line->edge[normStart];
3529            yMin1 = line->yMin;
3530            yMax1 = line->yMax;
3531            break;
3532          case 3:
3533            xMin1 = line->xMin;
3534            xMax1 = line->xMax;
3535            yMin1 = line->edge[normAfterEnd];
3536            yMax1 = line->edge[normStart];
3537            break;
3538          }
3539          if (backward) {
3540            if ((startAtTop ||
3541                 yMin1 < yStart || (yMin1 == yStart && xMin1 < xStart)) &&
3542                (stopAtBottom ||
3543                 yMin1 > yStop || (yMin1 == yStop && xMin1 > xStop))) {
3544              if (!found ||
3545                  yMin1 > yMin0 || (yMin1 == yMin0 && xMin1 > xMin0)) {
3546                xMin0 = xMin1;
3547                xMax0 = xMax1;
3548                yMin0 = yMin1;
3549                yMax0 = yMax1;
3550                found = gTrue;
3551              }
3552            }
3553          } else {
3554            if ((startAtTop ||
3555                 yMin1 > yStart || (yMin1 == yStart && xMin1 > xStart)) &&
3556                (stopAtBottom ||
3557                 yMin1 < yStop || (yMin1 == yStop && xMin1 < xStop))) {
3558              if (!found ||
3559                  yMin1 < yMin0 || (yMin1 == yMin0 && xMin1 < xMin0)) {
3560                xMin0 = xMin1;
3561                xMax0 = xMax1;
3562                yMin0 = yMin1;
3563                yMax0 = yMax1;
3564                found = gTrue;
3565              }
3566            }
3567          }
3568        }
3569        if (backward) {
3570          --j;
3571          --p;
3572        } else {
3573          ++j;
3574          ++p;
3575        }
3576      }
3577    }
3578    }
3579
3580  gfree(s2);
3581  if (!caseSensitive) {
3582    gfree(txt);
3583  }
3584
3585  if (found) {
3586    *xMin = xMin0;
3587    *xMax = xMax0;
3588    *yMin = yMin0;
3589    *yMax = yMax0;
3590    lastFindXMin = xMin0;
3591    lastFindYMin = yMin0;
3592    haveLastFind = gTrue;
3593    return gTrue;
3594  }
3595
3596  return gFalse;
3597}
3598
3599GooString *TextPage::getText(double xMin, double yMin,
3600                           double xMax, double yMax) {
3601  GooString *s;
3602  UnicodeMap *uMap;
3603  TextBlock *blk;
3604  TextLine *line;
3605  TextLineFrag *frags;
3606  int nFrags, fragsSize;
3607  TextLineFrag *frag;
3608  char space[8], eol[16];
3609  int spaceLen, eolLen;
3610  int lastRot;
3611  double x, y, delta;
3612  int col, idx0, idx1, i, j;
3613  GBool multiLine, oneRot;
3614
3615  s = new GooString();
3616
3617  // get the output encoding
3618  if (!(uMap = globalParams->getTextEncoding())) {
3619    return s;
3620  }
3621
3622  if (rawOrder) {
3623    TextWord*  word;
3624    char mbc[16];
3625    int  mbc_len;
3626
3627    for (word = rawWords; word && word <= rawLastWord; word = word->next) {
3628      for (j = 0; j < word->getLength(); ++j) {
3629        double gXMin, gXMax, gYMin, gYMax;
3630        word->getCharBBox(j, &gXMin, &gYMin, &gXMax, &gYMax);
3631        if (xMin <= gXMin && gXMax <= xMax && yMin <= gYMin && gYMax <= yMax)
3632        {
3633          mbc_len = uMap->mapUnicode( *(word->getChar(j)), mbc, sizeof(mbc) );
3634          s->append(mbc, mbc_len);
3635        }
3636      }
3637    }
3638    return s;
3639  }
3640
3641  spaceLen = uMap->mapUnicode(0x20, space, sizeof(space));
3642  eolLen = 0; // make gcc happy
3643  switch (globalParams->getTextEOL()) {
3644  case eolUnix:
3645    eolLen = uMap->mapUnicode(0x0a, eol, sizeof(eol));
3646    break;
3647  case eolDOS:
3648    eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
3649    eolLen += uMap->mapUnicode(0x0a, eol + eolLen, sizeof(eol) - eolLen);
3650    break;
3651  case eolMac:
3652    eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
3653    break;
3654  }
3655
3656  //~ writing mode (horiz/vert)
3657
3658  // collect the line fragments that are in the rectangle
3659  fragsSize = 256;
3660  frags = (TextLineFrag *)gmallocn(fragsSize, sizeof(TextLineFrag));
3661  nFrags = 0;
3662  lastRot = -1;
3663  oneRot = gTrue;
3664  for (i = 0; i < nBlocks; ++i) {
3665    blk = blocks[i];
3666    if (xMin < blk->xMax && blk->xMin < xMax &&
3667        yMin < blk->yMax && blk->yMin < yMax) {
3668      for (line = blk->lines; line; line = line->next) {
3669        if (xMin < line->xMax && line->xMin < xMax &&
3670            yMin < line->yMax && line->yMin < yMax) {
3671          idx0 = idx1 = -1;
3672          switch (line->rot) {
3673          case 0:
3674            y = 0.5 * (line->yMin + line->yMax);
3675            if (yMin < y && y < yMax) {
3676              j = 0;
3677              while (j < line->len) {
3678                if (0.5 * (line->edge[j] + line->edge[j+1]) > xMin) {
3679                  idx0 = j;
3680                  break;
3681                }
3682                ++j;
3683              }
3684              j = line->len - 1;
3685              while (j >= 0) {
3686                if (0.5 * (line->edge[j] + line->edge[j+1]) < xMax) {
3687                  idx1 = j;
3688                  break;
3689                }
3690                --j;
3691              }
3692            }
3693            break;
3694          case 1:
3695            x = 0.5 * (line->xMin + line->xMax);
3696            if (xMin < x && x < xMax) {
3697              j = 0;
3698              while (j < line->len) {
3699                if (0.5 * (line->edge[j] + line->edge[j+1]) > yMin) {
3700                  idx0 = j;
3701                  break;
3702                }
3703                ++j;
3704              }
3705              j = line->len - 1;
3706              while (j >= 0) {
3707                if (0.5 * (line->edge[j] + line->edge[j+1]) < yMax) {
3708                  idx1 = j;
3709                  break;
3710                }
3711                --j;
3712              }
3713            }
3714            break;
3715          case 2:
3716            y = 0.5 * (line->yMin + line->yMax);
3717            if (yMin < y && y < yMax) {
3718              j = 0;
3719              while (j < line->len) {
3720                if (0.5 * (line->edge[j] + line->edge[j+1]) < xMax) {
3721                  idx0 = j;
3722                  break;
3723                }
3724                ++j;
3725              }
3726              j = line->len - 1;
3727              while (j >= 0) {
3728                if (0.5 * (line->edge[j] + line->edge[j+1]) > xMin) {
3729                  idx1 = j;
3730                  break;
3731                }
3732                --j;
3733              }
3734            }
3735            break;
3736          case 3:
3737            x = 0.5 * (line->xMin + line->xMax);
3738            if (xMin < x && x < xMax) {
3739              j = 0;
3740              while (j < line->len) {
3741                if (0.5 * (line->edge[j] + line->edge[j+1]) < yMax) {
3742                  idx0 = j;
3743                  break;
3744                }
3745                ++j;
3746              }
3747              j = line->len - 1;
3748              while (j >= 0) {
3749                if (0.5 * (line->edge[j] + line->edge[j+1]) > yMin) {
3750                  idx1 = j;
3751                  break;
3752                }
3753                --j;
3754              }
3755            }
3756            break;
3757          }
3758          if (idx0 >= 0 && idx1 >= 0) {
3759            if (nFrags == fragsSize) {
3760              fragsSize *= 2;
3761              frags = (TextLineFrag *)
3762                          greallocn(frags, fragsSize, sizeof(TextLineFrag));
3763            }
3764            frags[nFrags].init(line, idx0, idx1 - idx0 + 1);
3765            ++nFrags;
3766            if (lastRot >= 0 && line->rot != lastRot) {
3767              oneRot = gFalse;
3768            }
3769            lastRot = line->rot;
3770          }
3771        }
3772      }
3773    }
3774  }
3775
3776  // sort the fragments and generate the string
3777  if (nFrags > 0) {
3778
3779    for (i = 0; i < nFrags; ++i) {
3780      frags[i].computeCoords(oneRot);
3781    }
3782    assignColumns(frags, nFrags, oneRot);
3783
3784    // if all lines in the region have the same rotation, use it;
3785    // otherwise, use the page's primary rotation
3786    if (oneRot) {
3787      qsort(frags, nFrags, sizeof(TextLineFrag),
3788            &TextLineFrag::cmpYXLineRot);
3789    } else {
3790      qsort(frags, nFrags, sizeof(TextLineFrag),
3791            &TextLineFrag::cmpYXPrimaryRot);
3792    }
3793    i = 0;
3794    while (i < nFrags) {
3795      delta = maxIntraLineDelta * frags[i].line->words->fontSize;
3796      for (j = i+1;
3797           j < nFrags && fabs(frags[j].base - frags[i].base) < delta;
3798           ++j) ;
3799      qsort(frags + i, j - i, sizeof(TextLineFrag),
3800            oneRot ? &TextLineFrag::cmpXYColumnLineRot
3801                   : &TextLineFrag::cmpXYColumnPrimaryRot);
3802      i = j;
3803    }
3804
3805    col = 0;
3806    multiLine = gFalse;
3807    for (i = 0; i < nFrags; ++i) {
3808      frag = &frags[i];
3809
3810      // insert a return
3811      if (frag->col < col ||
3812          (i > 0 && fabs(frag->base - frags[i-1].base) >
3813                      maxIntraLineDelta * frags[i-1].line->words->fontSize)) {
3814        s->append(eol, eolLen);
3815        col = 0;
3816        multiLine = gTrue;
3817      }
3818
3819      // column alignment
3820      for (; col < frag->col; ++col) {
3821        s->append(space, spaceLen);
3822      }
3823
3824      // get the fragment text
3825      col += dumpFragment(frag->line->text + frag->start, frag->len, uMap, s);
3826    }
3827
3828    if (multiLine) {
3829      s->append(eol, eolLen);
3830    }
3831  }
3832
3833  gfree(frags);
3834  uMap->decRefCnt();
3835
3836  return s;
3837}
3838
3839class TextSelectionVisitor {
3840public:
3841  TextSelectionVisitor (TextPage *page);
3842  virtual ~TextSelectionVisitor () { }
3843  virtual void visitBlock (TextBlock *block,
3844                           TextLine *begin,
3845                           TextLine *end,
3846                           PDFRectangle *selection) = 0;
3847  virtual void visitLine (TextLine *line, 
3848                          TextWord *begin,
3849                          TextWord *end,
3850                          int edge_begin,
3851                          int edge_end,
3852                          PDFRectangle *selection) = 0;
3853  virtual void visitWord (TextWord *word, int begin, int end,
3854                          PDFRectangle *selection) = 0;
3855
3856protected:
3857  TextPage *page;
3858};
3859
3860TextSelectionVisitor::TextSelectionVisitor (TextPage *page)
3861  : page(page)
3862{
3863}
3864
3865
3866class TextSelectionDumper : public TextSelectionVisitor {
3867public:
3868  TextSelectionDumper(TextPage *page);
3869  virtual ~TextSelectionDumper();
3870
3871  virtual void visitBlock (TextBlock *block, 
3872                           TextLine *begin,
3873                           TextLine *end,
3874                           PDFRectangle *selection) { };
3875  virtual void visitLine (TextLine *line,
3876                          TextWord *begin,
3877                          TextWord *end,
3878                          int edge_begin,
3879                          int edge_end,
3880                          PDFRectangle *selection);
3881  virtual void visitWord (TextWord *word, int begin, int end,
3882                          PDFRectangle *selection) { };
3883
3884  GooString *getText(void);
3885
3886private:
3887  TextLineFrag *frags;
3888  int nFrags, fragsSize;
3889};
3890
3891TextSelectionDumper::TextSelectionDumper(TextPage *page)
3892    : TextSelectionVisitor(page)
3893{
3894  fragsSize = 256;
3895  frags = (TextLineFrag *)gmallocn(fragsSize, sizeof(TextLineFrag));
3896  nFrags = 0;
3897}
3898
3899TextSelectionDumper::~TextSelectionDumper()
3900{
3901  gfree(frags);
3902}
3903
3904void TextSelectionDumper::visitLine (TextLine *line,
3905                                     TextWord *begin,
3906                                     TextWord *end,
3907                                     int edge_begin,
3908                                     int edge_end,
3909                                     PDFRectangle *selection)
3910{
3911  if (nFrags == fragsSize) {
3912    fragsSize *= 2;
3913    frags = (TextLineFrag *) grealloc(frags, fragsSize * sizeof(TextLineFrag));
3914  }
3915
3916  frags[nFrags].init(line, edge_begin, edge_end - edge_begin);
3917  ++nFrags;
3918
3919}
3920
3921GooString *TextSelectionDumper::getText (void)
3922{
3923  GooString *s;
3924  TextLineFrag *frag;
3925  int i, j;
3926  UnicodeMap *uMap;
3927  char space[8], eol[16];
3928  int spaceLen, eolLen;
3929  GooList *strings = NULL;
3930  int actual_table = -1;
3931  int actual_line = -1;
3932  int last_length = 0;
3933  TextBlock *actual_block = NULL;
3934
3935  s = new GooString();
3936
3937  uMap = globalParams->getTextEncoding();
3938
3939  if (uMap == NULL)
3940      return s;
3941
3942  spaceLen = uMap->mapUnicode(0x20, space, sizeof(space));
3943  eolLen = uMap->mapUnicode(0x0a, eol, sizeof(eol));
3944
3945  if (nFrags > 0) {
3946    for (i = 0; i < nFrags; ++i) {
3947      frag = &frags[i];
3948
3949      if (actual_table >= 0 && frag->line->blk->tableId < 0) {
3950        for (j = 0; j < strings->getLength (); j++) {
3951          s->append ((GooString*) strings->get (j));
3952          s->append (eol, eolLen);
3953          delete ((GooString*) strings->get (j));
3954        }
3955        delete strings;
3956        strings = NULL;
3957        actual_table = -1;
3958        actual_line = -1;
3959        actual_block = NULL;
3960      }
3961
3962      // a table
3963      if (frag->line->blk->tableId >= 0) {
3964        if (actual_table == -1) {
3965          strings = new GooList();
3966          actual_table = frag->line->blk->tableId;
3967          actual_block = frag->line->blk;
3968          actual_line = -1;
3969        }
3970
3971        // the same block
3972        if (actual_block == frag->line->blk) {
3973          actual_line++;
3974          if (actual_line >= strings->getLength ()) {
3975            GooString *t = new GooString ();
3976            // add some spaces to have this block correctly aligned
3977            if (actual_line > 0)
3978              for (j = 0; j < ((GooString*) (strings->get (actual_line - 1)))->getLength() - last_length - 1; j++)
3979                t->append (space, spaceLen);
3980            strings->append (t);
3981          }
3982        }
3983        // another block
3984        else {
3985          // previous block ended its row
3986          if (actual_block->tableEnd) {
3987            for (j = 0; j < strings->getLength (); j++) {
3988              s->append ((GooString*) strings->get (j));
3989              s->append (eol, eolLen);
3990              delete ((GooString*) strings->get (j));
3991            }
3992            delete strings;
3993
3994            strings = new GooList();
3995            GooString *t = new GooString ();
3996            strings->append (t);
3997          }
3998          actual_block = frag->line->blk;
3999          actual_line = 0;
4000        }
4001
4002        page->dumpFragment(frag->line->text + frag->start, frag->len, uMap, ((GooString*) strings->get (actual_line)));
4003        last_length = frag->len;
4004
4005        if (!frag->line->blk->tableEnd) {
4006          ((GooString*) strings->get (actual_line))->append (space, spaceLen);
4007        }
4008      }
4009      // not a table
4010      else {
4011        page->dumpFragment (frag->line->text + frag->start, frag->len, uMap, s);
4012        s->append (eol, eolLen);
4013      }
4014    }
4015
4016    if (strings != NULL) {
4017      for (j = 0; j < strings->getLength (); j++) {
4018        s->append((GooString*) strings->get (j));
4019        s->append(eol, eolLen);
4020        delete ((GooString*) strings->get (j));
4021      }
4022      delete strings;
4023      strings = NULL;
4024      actual_table = -1;
4025      actual_line = -1;
4026      actual_block = NULL;
4027    }
4028  }
4029
4030  uMap->decRefCnt();
4031
4032  return s;
4033}
4034
4035class TextSelectionSizer : public TextSelectionVisitor {
4036public:
4037  TextSelectionSizer(TextPage *page, double scale);
4038  ~TextSelectionSizer() { }
4039
4040  virtual void visitBlock (TextBlock *block,
4041                           TextLine *begin,
4042                           TextLine *end,
4043                           PDFRectangle *selection) { };
4044  virtual void visitLine (TextLine *line, 
4045                          TextWord *begin,
4046                          TextWord *end,
4047                          int edge_begin,
4048                          int edge_end,
4049                          PDFRectangle *selection);
4050  virtual void visitWord (TextWord *word, int begin, int end,
4051                          PDFRectangle *selection) { };
4052
4053  GooList *getRegion () { return list; }
4054
4055private:
4056  GooList *list;
4057  double scale;
4058};
4059
4060TextSelectionSizer::TextSelectionSizer(TextPage *page, double scale)
4061  : TextSelectionVisitor(page),
4062    scale(scale)
4063{
4064  list = new GooList();
4065}
4066
4067void TextSelectionSizer::visitLine (TextLine *line, 
4068                                    TextWord *begin,
4069                                    TextWord *end,
4070                                    int edge_begin,
4071                                    int edge_end,
4072                                    PDFRectangle *selection)
4073{
4074  PDFRectangle *rect;
4075  double x1, y1, x2, y2, margin;
4076
4077  margin = (line->yMax - line->yMin) / 8;
4078  x1 = line->edge[edge_begin];
4079  y1 = line->yMin - margin;
4080  x2 = line->edge[edge_end];
4081  y2 = line->yMax + margin;
4082
4083  rect = new PDFRectangle (floor (x1 * scale), 
4084                           floor (y1 * scale),
4085                           ceil (x2 * scale),
4086                           ceil (y2 * scale));
4087  list->append (rect);
4088}
4089
4090
4091class TextSelectionPainter : public TextSelectionVisitor {
4092public:
4093  TextSelectionPainter(TextPage *page,
4094                       double scale,
4095                       int rotation,
4096                       OutputDev *out,
4097                       GfxColor *box_color,
4098                       GfxColor *glyph_color);
4099  ~TextSelectionPainter();
4100
4101  virtual void visitBlock (TextBlock *block,
4102                           TextLine *begin,
4103                           TextLine *end,
4104                           PDFRectangle *selection) { };
4105  virtual void visitLine (TextLine *line, 
4106                          TextWord *begin,
4107                          TextWord *end,
4108                          int edge_begin,
4109                          int edge_end,
4110                          PDFRectangle *selection);
4111  virtual void visitWord (TextWord *word, int begin, int end,
4112                          PDFRectangle *selection);
4113
4114private:
4115  OutputDev *out;
4116  GfxColor *box_color, *glyph_color;
4117  GfxState *state;
4118};
4119
4120TextSelectionPainter::TextSelectionPainter(TextPage *page,
4121                                           double scale,
4122                                           int rotation,
4123                                           OutputDev *out,
4124                                           GfxColor *box_color,
4125                                           GfxColor *glyph_color)
4126  : TextSelectionVisitor(page),
4127    out(out),
4128    box_color(box_color),
4129    glyph_color(glyph_color)
4130{
4131  PDFRectangle box(0, 0, page->pageWidth, page->pageHeight);
4132
4133  state = new GfxState(72 * scale, 72 * scale, &box, rotation, gFalse);
4134
4135  out->startPage (0, state);
4136  out->setDefaultCTM (state->getCTM());
4137
4138  state->setTextMat(1, 0, 0, -1, 0, 0);
4139  state->setFillColorSpace(new GfxDeviceRGBColorSpace());
4140
4141}
4142
4143TextSelectionPainter::~TextSelectionPainter()
4144{
4145  out->endPage ();
4146
4147  delete state;
4148}
4149
4150void TextSelectionPainter::visitLine (TextLine *line,
4151                                      TextWord *begin,
4152                                      TextWord *end,
4153                                      int edge_begin,
4154                                      int edge_end,
4155                                      PDFRectangle *selection)
4156{
4157  double x1, y1, x2, y2, margin;
4158  Matrix ctm, ictm;
4159
4160  state->setFillColor(box_color);
4161  out->updateFillColor(state);
4162
4163  margin = (line->yMax - line->yMin) / 8;
4164  x1 = floor (line->edge[edge_begin]);
4165  y1 = floor (line->yMin - margin);
4166  x2 = ceil (line->edge[edge_end]);
4167  y2 = ceil (line->yMax + margin);
4168
4169  state->getCTM (&ctm);
4170  ctm.transform(line->edge[edge_begin], line->yMin - margin, &x1, &y1);
4171  ctm.transform(line->edge[edge_end], line->yMax + margin, &x2, &y2);
4172
4173  x1 = floor (x1);
4174  y1 = floor (y1);
4175  x2 = ceil (x2);
4176  y2 = ceil (y2);
4177
4178  ctm.invertTo (&ictm);
4179  ictm.transform(x1, y1, &x1, &y1);
4180  ictm.transform(x2, y2, &x2, &y2);
4181
4182  state->moveTo(x1, y1);
4183  state->lineTo(x2, y1);
4184  state->lineTo(x2, y2);
4185  state->lineTo(x1, y2);
4186  state->closePath();
4187
4188  out->fill(state);
4189  state->clearPath();
4190}
4191
4192void TextSelectionPainter::visitWord (TextWord *word, int begin, int end,
4193                                      PDFRectangle *selection)
4194{
4195  GooString *string;
4196  int i;
4197
4198  state->setFillColor(glyph_color);
4199  out->updateFillColor(state);
4200  word->font->gfxFont->incRefCnt();
4201  state->setFont(word->font->gfxFont, word->fontSize);
4202  out->updateFont(state);
4203
4204  /* The only purpose of this string is to let the output device query
4205   * it's length.  Might want to change this interface later. */
4206
4207  string = new GooString ((char *) word->charcode, end - begin);
4208
4209  out->beginString(state, string);
4210
4211  for (i = begin; i < end; i++)
4212    out->drawChar(state, word->edge[i], word->base, 0, 0, 0, 0,
4213                  word->charcode[i], 1, NULL, 0);
4214 
4215  out->endString(state);
4216
4217  delete string;
4218}
4219
4220void TextWord::visitSelection(TextSelectionVisitor *visitor,
4221                              PDFRectangle *selection,
4222                              SelectionStyle style)
4223{
4224  int i, begin, end;
4225  double mid;
4226
4227  begin = len;
4228  end = 0;
4229  for (i = 0; i < len; i++) {
4230    mid = (edge[i] + edge[i + 1]) / 2;
4231    if (selection->x1 < mid || selection->x2 < mid)
4232      if (i < begin)
4233        begin = i;
4234    if (mid < selection->x1 || mid < selection->x2)
4235      end = i + 1;
4236  }
4237
4238  /* Skip empty selection. */
4239  if (end <= begin)
4240    return;
4241
4242  visitor->visitWord (this, begin, end, selection);
4243}
4244
4245void TextLine::visitSelection(TextSelectionVisitor *visitor,
4246                              PDFRectangle *selection,
4247                              SelectionStyle style) {
4248  TextWord *p, *begin, *end, *current;
4249  int i, edge_begin, edge_end;
4250  PDFRectangle child_selection;
4251
4252  begin = NULL;
4253  end = NULL;
4254  current = NULL;
4255  for (p = words; p != NULL; p = p->next) {
4256    if (blk->page->primaryLR) {
4257      if ((selection->x1 < p->xMax) ||
4258          (selection->x2 < p->xMax))
4259        if (begin == NULL) 
4260          begin = p;
4261
4262      if (((selection->x1 > p->xMin) ||
4263           (selection->x2 > p->xMin)) && (begin != NULL)) {
4264        end = p->next;
4265        current = p;
4266      }
4267    } else {
4268      if ((selection->x1 > p->xMin) ||
4269          (selection->x2 > p->xMin))
4270        if (begin == NULL) 
4271          begin = p;
4272
4273      if (((selection->x1 < p->xMax) ||
4274           (selection->x2 < p->xMax)) && (begin != NULL)) {
4275        end = p->next;
4276        current = p;
4277      }
4278    }
4279  }
4280
4281  if (!current)
4282    current = begin;
4283 
4284  child_selection = *selection;
4285  if (style == selectionStyleWord) {
4286    child_selection.x1 = begin ? begin->xMin : xMin;
4287    if (end && end->xMax != -1) {
4288      child_selection.x2 = current->xMax;
4289    } else {
4290      child_selection.x2 = xMax;
4291    }
4292  }
4293
4294  edge_begin = len;
4295  edge_end = 0;
4296  for (i = 0; i < len; i++) {
4297    double mid = (edge[i] + edge[i + 1]) /  2;
4298    if (child_selection.x1 < mid || child_selection.x2 < mid)
4299      if (i < edge_begin)
4300        edge_begin = i;
4301    if (mid < child_selection.x2 || mid < child_selection.x1)
4302      edge_end = i + 1;
4303  }
4304
4305  /* Skip empty selection. */
4306  if (edge_end <= edge_begin)
4307    return;
4308
4309  visitor->visitLine (this, begin, end, edge_begin, edge_end,
4310                      &child_selection);
4311
4312  for (p = begin; p != end; p = p->next)
4313    p->visitSelection (visitor, &child_selection, style);
4314}
4315
4316void TextBlock::visitSelection(TextSelectionVisitor *visitor,
4317                               PDFRectangle *selection,
4318                               SelectionStyle style) {
4319  PDFRectangle child_selection;
4320  double x[2], y[2], d, best_d[2];
4321  TextLine *p, *best_line[2];
4322  int i, count = 0, best_count[2], start, stop;
4323  GBool all[2];
4324
4325  x[0] = selection->x1;
4326  y[0] = selection->y1;
4327  x[1] = selection->x2;
4328  y[1] = selection->y2;
4329
4330  for (i = 0; i < 2; i++) {
4331    // the first/last lines are often not nearest
4332    // the corners, so we have to force them to be
4333    // selected when the selection runs outside this
4334    // block.
4335    if (page->primaryLR) {
4336      all[i] = x[i] >= this->xMax && y[i] >= this->yMax;
4337      if (x[i] <= this->xMin && y[i] <= this->yMin) {
4338        best_line[i] = this->lines;
4339        best_count[i] = 1;
4340      } else {
4341        best_line[i] = NULL;
4342        best_count[i] = 0;
4343      }
4344    } else {
4345      all[i] = x[i] <= this->xMin && y[i] >= this->yMax;
4346      if (x[i] >= this->xMax && y[i] <= this->yMin) {
4347        best_line[i] = this->lines;
4348        best_count[i] = 1;
4349      } else {
4350        best_line[i] = NULL;
4351        best_count[i] = 0;
4352      }
4353    }
4354    best_d[i] = 0;
4355  }
4356
4357  // find the nearest line to the selection points
4358  // using the manhattan distance.
4359  for (p = this->lines; p; p = p->next) {
4360    count++;
4361    for (i = 0; i < 2; i++) {
4362      d = fmax(p->xMin - x[i], 0.0) +
4363        fmax(x[i] - p->xMax, 0.0) +
4364        fmax(p->yMin - y[i], 0.0) +
4365        fmax(y[i] - p->yMax, 0.0);
4366      if (!best_line[i] || all[i] ||
4367          d < best_d[i]) {
4368        best_line[i] = p;
4369        best_count[i] = count;
4370        best_d[i] = d;
4371      }
4372    }
4373  }
4374  // assert: best is always set.
4375  if (!best_line[0] || !best_line[1]) {
4376    return;
4377  }
4378
4379  // Now decide which point was first.
4380  if (best_count[0] < best_count[1] ||
4381      (best_count[0] == best_count[1] &&
4382       y[0] < y[1])) {
4383    start = 0;
4384    stop = 1;
4385  } else {
4386    start = 1;
4387    stop = 0;
4388  }
4389
4390  visitor->visitBlock(this, best_line[start], best_line[stop], selection);
4391
4392  for (p = best_line[start]; p; p = p->next) {
4393    if (page->primaryLR) {
4394      child_selection.x1 = p->xMin;
4395      child_selection.x2 = p->xMax;
4396    } else {
4397      child_selection.x1 = p->xMax;
4398      child_selection.x2 = p->xMin;
4399    }
4400    child_selection.y1 = p->yMin;
4401    child_selection.y2 = p->yMax;
4402    if (style == selectionStyleLine) {
4403      if (p == best_line[start]) {
4404        child_selection.x1 = 0;
4405        child_selection.y1 = 0;
4406      }
4407      if (p == best_line[stop]) {
4408        child_selection.x2 = page->pageWidth;
4409        child_selection.y2 = page->pageHeight;
4410      }
4411    } else {
4412      if (p == best_line[start]) {
4413        child_selection.x1 = fmax(p->xMin, fmin(p->xMax, x[start]));
4414        child_selection.y1 = fmax(p->yMin, fmin(p->yMax, y[start]));
4415      }
4416      if (p == best_line[stop]) {
4417        child_selection.x2 = fmax(p->xMin, fmin(p->xMax, x[stop]));
4418        child_selection.y2 = fmax(p->yMin, fmin(p->yMax, y[stop]));
4419      }
4420    }
4421    p->visitSelection(visitor, &child_selection, style);
4422    if (p == best_line[stop]) {
4423      return;
4424    }
4425  }
4426}
4427
4428void TextPage::visitSelection(TextSelectionVisitor *visitor,
4429                              PDFRectangle *selection,
4430                              SelectionStyle style)
4431{
4432  PDFRectangle child_selection;
4433  double x[2], y[2], d, best_d[2];
4434  double xMin, yMin, xMax, yMax;
4435  TextFlow *flow, *best_flow[2];
4436  TextBlock *blk, *best_block[2];
4437  int i, count = 0, best_count[2], start, stop;
4438
4439  if (!flows)
4440    return;
4441
4442  x[0] = selection->x1;
4443  y[0] = selection->y1;
4444  x[1] = selection->x2;
4445  y[1] = selection->y2;
4446
4447  xMin = pageWidth;
4448  yMin = pageHeight;
4449  xMax = 0.0;
4450  yMax = 0.0;
4451
4452  for (i = 0; i < 2; i++) {
4453    best_block[i] = NULL;
4454    best_flow[i] = NULL;
4455    best_count[i] = 0;
4456    best_d[i] = 0;
4457  }
4458
4459  // find the nearest blocks to the selection points
4460  // using the manhattan distance.
4461  for (flow = flows; flow; flow = flow->next) {
4462    for (blk = flow->blocks; blk; blk = blk->next) {
4463      count++;
4464      // the first/last blocks in reading order are
4465      // often not the closest to the page corners;
4466      // track the corners, force those blocks to
4467      // be selected if the selection runs across
4468      // multiple pages.
4469      xMin = fmin(xMin, blk->xMin);
4470      yMin = fmin(yMin, blk->yMin);
4471      xMax = fmax(xMax, blk->xMax);
4472      yMax = fmax(yMax, blk->yMax);
4473      for (i = 0; i < 2; i++) {
4474        d = fmax(blk->xMin - x[i], 0.0) +
4475          fmax(x[i] - blk->xMax, 0.0) +
4476          fmax(blk->yMin - y[i], 0.0) +
4477          fmax(y[i] - blk->yMax, 0.0);
4478        if (!best_block[i] ||
4479            d < best_d[i] ||
4480            (!blk->next && !flow->next &&
4481             x[i] > xMax && y[i] > yMax)) {
4482          best_block[i] = blk;
4483          best_flow[i] = flow;
4484          best_count[i] = count;
4485          best_d[i] = d;
4486        }
4487      }
4488    }
4489  }
4490  for (i = 0; i < 2; i++) {
4491    if (primaryLR) {
4492      if (x[i] < xMin && y[i] < yMin) {
4493        best_block[i] = flows->blocks;
4494        best_flow[i] = flows;
4495        best_count[i] = 1;
4496      }
4497    } else {
4498      if (x[i] > xMax && y[i] < yMin) {
4499        best_block[i] = flows->blocks;
4500        best_flow[i] = flows;
4501        best_count[i] = 1;
4502      }
4503    }
4504  }
4505  // assert: best is always set.
4506  if (!best_block[0] || !best_block[1]) {
4507    return;
4508  }
4509
4510  // Now decide which point was first.
4511  if (best_count[0] < best_count[1] ||
4512      (best_count[0] == best_count[1] && y[0] < y[1])) {
4513    start = 0;
4514    stop = 1;
4515  } else {
4516    start = 1;
4517    stop = 0;
4518  }
4519
4520  for (flow = best_flow[start]; flow; flow = flow->next) {
4521    if (flow == best_flow[start]) {
4522      blk = best_block[start];
4523    } else {
4524      blk = flow->blocks;
4525    }
4526    for (; blk; blk = blk->next) {
4527      if (primaryLR) {
4528        child_selection.x1 = blk->xMin;
4529        child_selection.x2 = blk->xMax;
4530      } else {
4531        child_selection.x1 = blk->xMax;
4532        child_selection.x2 = blk->xMin;
4533      }
4534      child_selection.y1 = blk->yMin;
4535      child_selection.y2 = blk->yMax;
4536      if (blk == best_block[start]) {
4537        child_selection.x1 = fmax(blk->xMin, fmin(blk->xMax, x[start]));
4538        child_selection.y1 = fmax(blk->yMin, fmin(blk->yMax, y[start]));
4539      }
4540      if (blk == best_block[stop]) {
4541        child_selection.x2 = fmax(blk->xMin, fmin(blk->xMax, x[stop]));
4542        child_selection.y2 = fmax(blk->yMin, fmin(blk->yMax, y[stop]));
4543        blk->visitSelection(visitor, &child_selection, style);
4544        return;
4545      }
4546      blk->visitSelection(visitor, &child_selection, style);
4547    }
4548  }
4549}
4550
4551void TextPage::drawSelection(OutputDev *out,
4552                             double scale,
4553                             int rotation,
4554                             PDFRectangle *selection,
4555                             SelectionStyle style,
4556                             GfxColor *glyph_color, GfxColor *box_color)
4557{
4558  TextSelectionPainter painter(this, scale, rotation, 
4559                               out, box_color, glyph_color);
4560
4561  visitSelection(&painter, selection, style);
4562}
4563
4564GooList *TextPage::getSelectionRegion(PDFRectangle *selection,
4565                                      SelectionStyle style,
4566                                      double scale) {
4567  TextSelectionSizer sizer(this, scale);
4568
4569  visitSelection(&sizer, selection, style);
4570
4571  return sizer.getRegion();
4572}
4573
4574GooString *TextPage::getSelectionText(PDFRectangle *selection,
4575                                      SelectionStyle style)
4576{
4577  TextSelectionDumper dumper(this);
4578
4579  visitSelection(&dumper, selection, style);
4580
4581  return dumper.getText();
4582}
4583
4584GBool TextPage::findCharRange(int pos, int length,
4585                              double *xMin, double *yMin,
4586                              double *xMax, double *yMax) {
4587  TextBlock *blk;
4588  TextLine *line;
4589  TextWord *word;
4590  double xMin0, xMax0, yMin0, yMax0;
4591  double xMin1, xMax1, yMin1, yMax1;
4592  GBool first;
4593  int i, j0, j1;
4594
4595  if (rawOrder) {
4596    return gFalse;
4597  }
4598
4599  //~ this doesn't correctly handle:
4600  //~ - ranges split across multiple lines (the highlighted region
4601  //~   is the bounding box of all the parts of the range)
4602  //~ - cases where characters don't convert one-to-one into Unicode
4603  first = gTrue;
4604  xMin0 = xMax0 = yMin0 = yMax0 = 0; // make gcc happy
4605  xMin1 = xMax1 = yMin1 = yMax1 = 0; // make gcc happy
4606  for (i = 0; i < nBlocks; ++i) {
4607    blk = blocks[i];
4608    for (line = blk->lines; line; line = line->next) {
4609      for (word = line->words; word; word = word->next) {
4610        if (pos < word->charPos + word->charLen &&
4611            word->charPos < pos + length) {
4612          j0 = pos - word->charPos;
4613          if (j0 < 0) {
4614            j0 = 0;
4615          }
4616          j1 = pos + length - 1 - word->charPos;
4617          if (j1 >= word->len) {
4618            j1 = word->len - 1;
4619          }
4620          switch (line->rot) {
4621          case 0:
4622            xMin1 = word->edge[j0];
4623            xMax1 = word->edge[j1 + 1];
4624            yMin1 = word->yMin;
4625            yMax1 = word->yMax;
4626            break;
4627          case 1:
4628            xMin1 = word->xMin;
4629            xMax1 = word->xMax;
4630            yMin1 = word->edge[j0];
4631            yMax1 = word->edge[j1 + 1];
4632            break;
4633          case 2:
4634            xMin1 = word->edge[j1 + 1];
4635            xMax1 = word->edge[j0];
4636            yMin1 = word->yMin;
4637            yMax1 = word->yMax;
4638            break;
4639          case 3:
4640            xMin1 = word->xMin;
4641            xMax1 = word->xMax;
4642            yMin1 = word->edge[j1 + 1];
4643            yMax1 = word->edge[j0];
4644            break;
4645          }
4646          if (first || xMin1 < xMin0) {
4647            xMin0 = xMin1;
4648          }
4649          if (first || xMax1 > xMax0) {
4650            xMax0 = xMax1;
4651          }
4652          if (first || yMin1 < yMin0) {
4653            yMin0 = yMin1;
4654          }
4655          if (first || yMax1 > yMax0) {
4656            yMax0 = yMax1;
4657          }
4658          first = gFalse;
4659        }
4660      }
4661    }
4662  }
4663  if (!first) {
4664    *xMin = xMin0;
4665    *xMax = xMax0;
4666    *yMin = yMin0;
4667    *yMax = yMax0;
4668    return gTrue;
4669  }
4670  return gFalse;
4671}
4672
4673void TextPage::dump(void *outputStream, TextOutputFunc outputFunc,
4674                    GBool physLayout) {
4675  UnicodeMap *uMap;
4676  TextFlow *flow;
4677  TextBlock *blk;
4678  TextLine *line;
4679  TextLineFrag *frags;
4680  TextWord *word;
4681  int nFrags, fragsSize;
4682  TextLineFrag *frag;
4683  char space[8], eol[16], eop[8];
4684  int spaceLen, eolLen, eopLen;
4685  GBool pageBreaks;
4686  GooString *s;
4687  double delta;
4688  int col, i, j, d, n;
4689
4690  // get the output encoding
4691  if (!(uMap = globalParams->getTextEncoding())) {
4692    return;
4693  }
4694  spaceLen = uMap->mapUnicode(0x20, space, sizeof(space));
4695  eolLen = 0; // make gcc happy
4696  switch (globalParams->getTextEOL()) {
4697  case eolUnix:
4698    eolLen = uMap->mapUnicode(0x0a, eol, sizeof(eol));
4699    break;
4700  case eolDOS:
4701    eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
4702    eolLen += uMap->mapUnicode(0x0a, eol + eolLen, sizeof(eol) - eolLen);
4703    break;
4704  case eolMac:
4705    eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
4706    break;
4707  }
4708  eopLen = uMap->mapUnicode(0x0c, eop, sizeof(eop));
4709  pageBreaks = globalParams->getTextPageBreaks();
4710
4711  //~ writing mode (horiz/vert)
4712
4713  // output the page in raw (content stream) order
4714  if (rawOrder) {
4715
4716    for (word = rawWords; word; word = word->next) {
4717      s = new GooString();
4718      dumpFragment(word->text, word->len, uMap, s);
4719      (*outputFunc)(outputStream, s->getCString(), s->getLength());
4720      delete s;
4721      if (word->next &&
4722          fabs(word->next->base - word->base) <
4723            maxIntraLineDelta * word->fontSize) {
4724        if (word->next->xMin > word->xMax + minWordSpacing * word->fontSize) {
4725          (*outputFunc)(outputStream, space, spaceLen);
4726        }
4727      } else {
4728        (*outputFunc)(outputStream, eol, eolLen);
4729      }
4730    }
4731
4732  // output the page, maintaining the original physical layout
4733  } else if (physLayout) {
4734
4735    // collect the line fragments for the page and sort them
4736    fragsSize = 256;
4737    frags = (TextLineFrag *)gmallocn(fragsSize, sizeof(TextLineFrag));
4738    nFrags = 0;
4739    for (i = 0; i < nBlocks; ++i) {
4740      blk = blocks[i];
4741      for (line = blk->lines; line; line = line->next) {
4742        if (nFrags == fragsSize) {
4743          fragsSize *= 2;
4744          frags = (TextLineFrag *)greallocn(frags,
4745                                            fragsSize, sizeof(TextLineFrag));
4746        }
4747        frags[nFrags].init(line, 0, line->len);
4748        frags[nFrags].computeCoords(gTrue);
4749        ++nFrags;
4750      }
4751    }
4752    qsort(frags, nFrags, sizeof(TextLineFrag), &TextLineFrag::cmpYXPrimaryRot);
4753    i = 0;
4754    while (i < nFrags) {
4755      delta = maxIntraLineDelta * frags[i].line->words->fontSize;
4756      for (j = i+1;
4757           j < nFrags && fabs(frags[j].base - frags[i].base) < delta;
4758           ++j) ;
4759      qsort(frags + i, j - i, sizeof(TextLineFrag),
4760            &TextLineFrag::cmpXYColumnPrimaryRot);
4761      i = j;
4762    }
4763
4764#if 0 // for debugging
4765    printf("*** line fragments ***\n");
4766    for (i = 0; i < nFrags; ++i) {
4767      frag = &frags[i];
4768      printf("frag: x=%.2f..%.2f y=%.2f..%.2f base=%.2f '",
4769             frag->xMin, frag->xMax, frag->yMin, frag->yMax, frag->base);
4770      for (n = 0; n < frag->len; ++n) {
4771        fputc(frag->line->text[frag->start + n] & 0xff, stdout);
4772      }
4773      printf("'\n");
4774    }
4775    printf("\n");
4776#endif
4777
4778    // generate output
4779    col = 0;
4780    for (i = 0; i < nFrags; ++i) {
4781      frag = &frags[i];
4782
4783      // column alignment
4784      for (; col < frag->col; ++col) {
4785        (*outputFunc)(outputStream, space, spaceLen);
4786      }
4787
4788      // print the line
4789      s = new GooString();
4790      col += dumpFragment(frag->line->text + frag->start, frag->len, uMap, s);
4791      (*outputFunc)(outputStream, s->getCString(), s->getLength());
4792      delete s;
4793
4794      // print one or more returns if necessary
4795      if (i == nFrags - 1 ||
4796          frags[i+1].col < col ||
4797          fabs(frags[i+1].base - frag->base) >
4798            maxIntraLineDelta * frag->line->words->fontSize) {
4799        if (i < nFrags - 1) {
4800          d = (int)((frags[i+1].base - frag->base) /
4801                    frag->line->words->fontSize);
4802          if (d < 1) {
4803            d = 1;
4804          } else if (d > 5) {
4805            d = 5;
4806          }
4807        } else {
4808          d = 1;
4809        }
4810        for (; d > 0; --d) {
4811          (*outputFunc)(outputStream, eol, eolLen);
4812        }
4813        col = 0;
4814      }
4815    }
4816
4817    gfree(frags);
4818
4819  // output the page, "undoing" the layout
4820  } else {
4821    for (flow = flows; flow; flow = flow->next) {
4822      for (blk = flow->blocks; blk; blk = blk->next) {
4823        for (line = blk->lines; line; line = line->next) {
4824          n = line->len;
4825          if (line->hyphenated && (line->next || blk->next)) {
4826            --n;
4827          }
4828          s = new GooString();
4829          dumpFragment(line->text, n, uMap, s);
4830          (*outputFunc)(outputStream, s->getCString(), s->getLength());
4831          delete s;
4832          // output a newline when a hyphen is not suppressed
4833          if (n == line->len) {
4834            (*outputFunc)(outputStream, eol, eolLen);
4835          }
4836        }
4837      }
4838      (*outputFunc)(outputStream, eol, eolLen);
4839    }
4840  }
4841
4842  // end of page
4843  if (pageBreaks) {
4844    (*outputFunc)(outputStream, eop, eopLen);
4845  }
4846
4847  uMap->decRefCnt();
4848}
4849
4850void TextPage::assignColumns(TextLineFrag *frags, int nFrags, GBool oneRot) {
4851  TextLineFrag *frag0, *frag1;
4852  int rot, col1, col2, i, j, k;
4853
4854  // all text in the region has the same rotation -- recompute the
4855  // column numbers based only on the text in the region
4856  if (oneRot) {
4857    qsort(frags, nFrags, sizeof(TextLineFrag), &TextLineFrag::cmpXYLineRot);
4858    rot = frags[0].line->rot;
4859    for (i = 0; i < nFrags; ++i) {
4860      frag0 = &frags[i];
4861      col1 = 0;
4862      for (j = 0; j < i; ++j) {
4863        frag1 = &frags[j];
4864        col2 = 0; // make gcc happy
4865        switch (rot) {
4866        case 0:
4867          if (frag0->xMin >= frag1->xMax) {
4868            col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
4869                                 frag1->line->col[frag1->start]) + 1;
4870          } else {
4871            for (k = frag1->start;
4872                 k < frag1->start + frag1->len &&
4873                   frag0->xMin >= 0.5 * (frag1->line->edge[k] +
4874                                         frag1->line->edge[k+1]);
4875                 ++k) ;
4876            col2 = frag1->col +
4877                   frag1->line->col[k] - frag1->line->col[frag1->start];
4878          }
4879          break;
4880        case 1:
4881          if (frag0->yMin >= frag1->yMax) {
4882            col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
4883                                 frag1->line->col[frag1->start]) + 1;
4884          } else {
4885            for (k = frag1->start;
4886                 k < frag1->start + frag1->len &&
4887                   frag0->yMin >= 0.5 * (frag1->line->edge[k] +
4888                                         frag1->line->edge[k+1]);
4889                 ++k) ;
4890            col2 = frag1->col +
4891                   frag1->line->col[k] - frag1->line->col[frag1->start];
4892          }
4893          break;
4894        case 2:
4895          if (frag0->xMax <= frag1->xMin) {
4896            col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
4897                                 frag1->line->col[frag1->start]) + 1;
4898          } else {
4899            for (k = frag1->start;
4900                 k < frag1->start + frag1->len &&
4901                   frag0->xMax <= 0.5 * (frag1->line->edge[k] +
4902                                         frag1->line->edge[k+1]);
4903                 ++k) ;
4904            col2 = frag1->col +
4905                   frag1->line->col[k] - frag1->line->col[frag1->start];
4906          }
4907          break;
4908        case 3:
4909          if (frag0->yMax <= frag1->yMin) {
4910            col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
4911                                 frag1->line->col[frag1->start]) + 1;
4912          } else {
4913            for (k = frag1->start;
4914                 k < frag1->start + frag1->len &&
4915                   frag0->yMax <= 0.5 * (frag1->line->edge[k] +
4916                                         frag1->line->edge[k+1]);
4917                 ++k) ;
4918            col2 = frag1->col +
4919                   frag1->line->col[k] - frag1->line->col[frag1->start];
4920          }
4921          break;
4922        }
4923        if (col2 > col1) {
4924          col1 = col2;
4925        }
4926      }
4927      frag0->col = col1;
4928    }
4929
4930  // the region includes text at different rotations -- use the
4931  // globally assigned column numbers, offset by the minimum column
4932  // number (i.e., shift everything over to column 0)
4933  } else {
4934    col1 = frags[0].col;
4935    for (i = 1; i < nFrags; ++i) {
4936      if (frags[i].col < col1) {
4937        col1 = frags[i].col;
4938      }
4939    }
4940    for (i = 0; i < nFrags; ++i) {
4941      frags[i].col -= col1;
4942    }
4943  }
4944}
4945
4946int TextPage::dumpFragment(Unicode *text, int len, UnicodeMap *uMap,
4947                           GooString *s) {
4948  char lre[8], rle[8], popdf[8], buf[8];
4949  int lreLen, rleLen, popdfLen, n;
4950  int nCols, i, j, k;
4951
4952  nCols = 0;
4953
4954  if (uMap->isUnicode()) {
4955
4956    lreLen = uMap->mapUnicode(0x202a, lre, sizeof(lre));
4957    rleLen = uMap->mapUnicode(0x202b, rle, sizeof(rle));
4958    popdfLen = uMap->mapUnicode(0x202c, popdf, sizeof(popdf));
4959
4960    if (primaryLR) {
4961
4962      i = 0;
4963      while (i < len) {
4964        // output a left-to-right section
4965        for (j = i; j < len && !unicodeTypeR(text[j]); ++j) ;
4966        for (k = i; k < j; ++k) {
4967          n = uMap->mapUnicode(text[k], buf, sizeof(buf));
4968          s->append(buf, n);
4969          ++nCols;
4970        }
4971        i = j;
4972        // output a right-to-left section
4973        for (j = i; j < len && !unicodeTypeL(text[j]); ++j) ;
4974        if (j > i) {
4975          s->append(rle, rleLen);
4976          for (k = j - 1; k >= i; --k) {
4977            n = uMap->mapUnicode(text[k], buf, sizeof(buf));
4978            s->append(buf, n);
4979            ++nCols;
4980          }
4981          s->append(popdf, popdfLen);
4982          i = j;
4983        }
4984      }
4985
4986    } else {
4987
4988      s->append(rle, rleLen);
4989      i = len - 1;
4990      while (i >= 0) {
4991        // output a right-to-left section
4992        for (j = i; j >= 0 && !unicodeTypeL(text[j]); --j) ;
4993        for (k = i; k > j; --k) {
4994          n = uMap->mapUnicode(text[k], buf, sizeof(buf));
4995          s->append(buf, n);
4996          ++nCols;
4997        }
4998        i = j;
4999        // output a left-to-right section
5000        for (j = i; j >= 0 && !unicodeTypeR(text[j]); --j) ;
5001        if (j < i) {
5002          s->append(lre, lreLen);
5003          for (k = j + 1; k <= i; ++k) {
5004            n = uMap->mapUnicode(text[k], buf, sizeof(buf));
5005            s->append(buf, n);
5006            ++nCols;
5007          }
5008          s->append(popdf, popdfLen);
5009          i = j;
5010        }
5011      }
5012      s->append(popdf, popdfLen);
5013
5014    }
5015
5016  } else {
5017    for (i = 0; i < len; ++i) {
5018      n = uMap->mapUnicode(text[i], buf, sizeof(buf));
5019      s->append(buf, n);
5020      nCols += n;
5021    }
5022  }
5023
5024  return nCols;
5025}
5026
5027#if TEXTOUT_WORD_LIST
5028TextWordList *TextPage::makeWordList(GBool physLayout) {
5029  return new TextWordList(this, physLayout);
5030}
5031#endif
5032
5033//------------------------------------------------------------------------
5034// ActualText
5035//------------------------------------------------------------------------
5036ActualText::ActualText(TextPage *out) {
5037  out->incRefCnt();
5038  text = out;
5039  actualText = NULL;
5040  actualTextBMCLevel = 0;
5041}
5042
5043ActualText::~ActualText() {
5044  if (actualText)
5045    delete actualText;
5046  text->decRefCnt();
5047}
5048
5049void ActualText::addChar(GfxState *state, double x, double y,
5050                         double dx, double dy,
5051                         CharCode c, int nBytes, Unicode *u, int uLen) {
5052  if (actualTextBMCLevel == 0) {
5053    text->addChar(state, x, y, dx, dy, c, nBytes, u, uLen);
5054  } else {
5055    // Inside ActualText span.
5056    if (newActualTextSpan) {
5057      actualText_x = x;
5058      actualText_y = y;
5059      actualText_dx = dx;
5060      actualText_dy = dy;
5061      newActualTextSpan = gFalse;
5062    } else {
5063      if (x < actualText_x)
5064        actualText_x = x;
5065      if (y < actualText_y)
5066        actualText_y = y;
5067      if (x + dx > actualText_x + actualText_dx)
5068        actualText_dx = x + dx - actualText_x;
5069      if (y + dy > actualText_y + actualText_dy)
5070        actualText_dy = y + dy - actualText_y;
5071    }
5072  }
5073}
5074
5075void ActualText::beginMC(Dict *properties) {
5076  if (actualTextBMCLevel > 0) {
5077    // Already inside a ActualText span.
5078    actualTextBMCLevel++;
5079    return;
5080  }
5081
5082  Object obj;
5083  if (properties && properties->lookup("ActualText", &obj)) {
5084    if (obj.isString()) {
5085      actualText = obj.getString();
5086      actualTextBMCLevel = 1;
5087      newActualTextSpan = gTrue;
5088    }
5089  }
5090}
5091
5092void ActualText::endMC(GfxState *state) {
5093  char *uniString = NULL;
5094  Unicode *uni;
5095  int length, i;
5096
5097  if (actualTextBMCLevel > 0) {
5098    actualTextBMCLevel--;
5099    if (actualTextBMCLevel == 0) {
5100      // ActualText span closed. Output the span text and the
5101      // extents of all the glyphs inside the span
5102
5103      if (newActualTextSpan) {
5104        // No content inside span.
5105        actualText_x = state->getCurX();
5106        actualText_y = state->getCurY();
5107        actualText_dx = 0;
5108        actualText_dy = 0;
5109      }
5110
5111      if (!actualText->hasUnicodeMarker()) {
5112        if (actualText->getLength() > 0) {
5113          //non-unicode string -- assume pdfDocEncoding and
5114          //try to convert to UTF16BE
5115          uniString = pdfDocEncodingToUTF16(actualText, &length);
5116        } else {
5117          length = 0;
5118        }
5119      } else {
5120        uniString = actualText->getCString();
5121        length = actualText->getLength();
5122      }
5123
5124      if (length < 3)
5125        length = 0;
5126      else
5127        length = length/2 - 1;
5128      uni = new Unicode[length];
5129      for (i = 0 ; i < length; i++)
5130        uni[i] = ((uniString[2 + i*2] & 0xff)<<8)|(uniString[3 + i*2] & 0xff);
5131
5132      text->addChar(state,
5133                    actualText_x, actualText_y,
5134                    actualText_dx, actualText_dy,
5135                    0, 1, uni, length);
5136
5137      delete [] uni;
5138      if (!actualText->hasUnicodeMarker())
5139        delete [] uniString;
5140      delete actualText;
5141      actualText = NULL;
5142    }
5143  }
5144}
5145
5146//------------------------------------------------------------------------
5147// TextOutputDev
5148//------------------------------------------------------------------------
5149
5150static void TextOutputDev_outputToFile(void *stream, char *text, int len) {
5151  fwrite(text, 1, len, (FILE *)stream);
5152}
5153
5154TextOutputDev::TextOutputDev(char *fileName, GBool physLayoutA,
5155                             GBool rawOrderA, GBool append) {
5156  text = NULL;
5157  physLayout = physLayoutA;
5158  rawOrder = rawOrderA;
5159  doHTML = gFalse;
5160  ok = gTrue;
5161
5162  // open file
5163  needClose = gFalse;
5164  if (fileName) {
5165    if (!strcmp(fileName, "-")) {
5166      outputStream = stdout;
5167#ifdef _WIN32
5168      // keep DOS from munging the end-of-line characters
5169      setmode(fileno(stdout), O_BINARY);
5170#endif
5171    } else if ((outputStream = fopen(fileName, append ? "ab" : "wb"))) {
5172      needClose = gTrue;
5173    } else {
5174      error(-1, "Couldn't open text file '%s'", fileName);
5175      ok = gFalse;
5176      actualText = NULL;
5177      return;
5178    }
5179    outputFunc = &TextOutputDev_outputToFile;
5180  } else {
5181    outputStream = NULL;
5182  }
5183
5184  // set up text object
5185  text = new TextPage(rawOrderA);
5186  actualText = new ActualText(text);
5187}
5188
5189TextOutputDev::TextOutputDev(TextOutputFunc func, void *stream,
5190                             GBool physLayoutA, GBool rawOrderA) {
5191  outputFunc = func;
5192  outputStream = stream;
5193  needClose = gFalse;
5194  physLayout = physLayoutA;
5195  rawOrder = rawOrderA;
5196  doHTML = gFalse;
5197  text = new TextPage(rawOrderA);
5198  actualText = new ActualText(text);
5199  ok = gTrue;
5200}
5201
5202TextOutputDev::~TextOutputDev() {
5203  if (needClose) {
5204#ifdef MACOS
5205    ICS_MapRefNumAndAssign((short)((FILE *)outputStream)->handle);
5206#endif
5207    fclose((FILE *)outputStream);
5208  }
5209  if (text) {
5210    text->decRefCnt();
5211  }
5212  delete actualText;
5213}
5214
5215void TextOutputDev::startPage(int pageNum, GfxState *state) {
5216  text->startPage(state);
5217}
5218
5219void TextOutputDev::endPage() {
5220  text->endPage();
5221  text->coalesce(physLayout, doHTML);
5222  if (outputStream) {
5223    text->dump(outputStream, outputFunc, physLayout);
5224  }
5225}
5226
5227void TextOutputDev::updateFont(GfxState *state) {
5228  text->updateFont(state);
5229}
5230
5231void TextOutputDev::beginString(GfxState *state, GooString *s) {
5232}
5233
5234void TextOutputDev::endString(GfxState *state) {
5235}
5236
5237void TextOutputDev::drawChar(GfxState *state, double x, double y,
5238                             double dx, double dy,
5239                             double originX, double originY,
5240                             CharCode c, int nBytes, Unicode *u, int uLen) {
5241  actualText->addChar(state, x, y, dx, dy, c, nBytes, u, uLen);
5242}
5243
5244void TextOutputDev::beginMarkedContent(char *name, Dict *properties)
5245{
5246  actualText->beginMC(properties);
5247}
5248
5249void TextOutputDev::endMarkedContent(GfxState *state)
5250{
5251  actualText->endMC(state);
5252}
5253
5254void TextOutputDev::stroke(GfxState *state) {
5255  GfxPath *path;
5256  GfxSubpath *subpath;
5257  double x[2], y[2];
5258
5259  if (!doHTML) {
5260    return;
5261  }
5262  path = state->getPath();
5263  if (path->getNumSubpaths() != 1) {
5264    return;
5265  }
5266  subpath = path->getSubpath(0);
5267  if (subpath->getNumPoints() != 2) {
5268    return;
5269  }
5270  state->transform(subpath->getX(0), subpath->getY(0), &x[0], &y[0]);
5271  state->transform(subpath->getX(1), subpath->getY(1), &x[1], &y[1]);
5272
5273  // look for a vertical or horizontal line
5274  if (x[0] == x[1] || y[0] == y[1]) {
5275    text->addUnderline(x[0], y[0], x[1], y[1]);
5276  }
5277}
5278
5279void TextOutputDev::fill(GfxState *state) {
5280  GfxPath *path;
5281  GfxSubpath *subpath;
5282  double x[5], y[5];
5283  double rx0, ry0, rx1, ry1, t;
5284  int i;
5285
5286  if (!doHTML) {
5287    return;
5288  }
5289  path = state->getPath();
5290  if (path->getNumSubpaths() != 1) {
5291    return;
5292  }
5293  subpath = path->getSubpath(0);
5294  if (subpath->getNumPoints() != 5) {
5295    return;
5296  }
5297  for (i = 0; i < 5; ++i) {
5298    if (subpath->getCurve(i)) {
5299      return;
5300    }
5301    state->transform(subpath->getX(i), subpath->getY(i), &x[i], &y[i]);
5302  }
5303
5304  // look for a rectangle
5305  if (x[0] == x[1] && y[1] == y[2] && x[2] == x[3] && y[3] == y[4] &&
5306      x[0] == x[4] && y[0] == y[4]) {
5307    rx0 = x[0];
5308    ry0 = y[0];
5309    rx1 = x[2];
5310    ry1 = y[1];
5311  } else if (y[0] == y[1] && x[1] == x[2] && y[2] == y[3] && x[3] == x[4] &&
5312             x[0] == x[4] && y[0] == y[4]) {
5313    rx0 = x[0];
5314    ry0 = y[0];
5315    rx1 = x[1];
5316    ry1 = y[2];
5317  } else {
5318    return;
5319  }
5320  if (rx1 < rx0) {
5321    t = rx0;
5322    rx0 = rx1;
5323    rx1 = t;
5324  }
5325  if (ry1 < ry0) {
5326    t = ry0;
5327    ry0 = ry1;
5328    ry1 = t;
5329  }
5330
5331  // skinny horizontal rectangle
5332  if (ry1 - ry0 < rx1 - rx0) {
5333    if (ry1 - ry0 < maxUnderlineWidth) {
5334      ry0 = 0.5 * (ry0 + ry1);
5335      text->addUnderline(rx0, ry0, rx1, ry0);
5336    }
5337
5338  // skinny vertical rectangle
5339  } else {
5340    if (rx1 - rx0 < maxUnderlineWidth) {
5341      rx0 = 0.5 * (rx0 + rx1);
5342      text->addUnderline(rx0, ry0, rx0, ry1);
5343    }
5344  }
5345}
5346
5347void TextOutputDev::eoFill(GfxState *state) {
5348  if (!doHTML) {
5349    return;
5350  }
5351  fill(state);
5352}
5353
5354void TextOutputDev::processLink(AnnotLink *link, Catalog * /*catalog*/) {
5355  double x1, y1, x2, y2;
5356  int xMin, yMin, xMax, yMax, x, y;
5357
5358  if (!doHTML) {
5359    return;
5360  }
5361  link->getRect(&x1, &y1, &x2, &y2);
5362  cvtUserToDev(x1, y1, &x, &y);
5363  xMin = xMax = x;
5364  yMin = yMax = y;
5365  cvtUserToDev(x1, y2, &x, &y);
5366  if (x < xMin) {
5367    xMin = x;
5368  } else if (x > xMax) {
5369    xMax = x;
5370  }
5371  if (y < yMin) {
5372    yMin = y;
5373  } else if (y > yMax) {
5374    yMax = y;
5375  }
5376  cvtUserToDev(x2, y1, &x, &y);
5377  if (x < xMin) {
5378    xMin = x;
5379  } else if (x > xMax) {
5380    xMax = x;
5381  }
5382  if (y < yMin) {
5383    yMin = y;
5384  } else if (y > yMax) {
5385    yMax = y;
5386  }
5387  cvtUserToDev(x2, y2, &x, &y);
5388  if (x < xMin) {
5389    xMin = x;
5390  } else if (x > xMax) {
5391    xMax = x;
5392  }
5393  if (y < yMin) {
5394    yMin = y;
5395  } else if (y > yMax) {
5396    yMax = y;
5397  }
5398  text->addLink(xMin, yMin, xMax, yMax, link);
5399}
5400
5401GBool TextOutputDev::findText(Unicode *s, int len,
5402                              GBool startAtTop, GBool stopAtBottom,
5403                              GBool startAtLast, GBool stopAtLast,
5404                              GBool caseSensitive, GBool backward,
5405                              double *xMin, double *yMin,
5406                              double *xMax, double *yMax) {
5407  return text->findText(s, len, startAtTop, stopAtBottom,
5408                        startAtLast, stopAtLast, caseSensitive, backward,
5409                        xMin, yMin, xMax, yMax);
5410}
5411
5412GooString *TextOutputDev::getText(double xMin, double yMin,
5413                                double xMax, double yMax) {
5414  return text->getText(xMin, yMin, xMax, yMax);
5415}
5416
5417void TextOutputDev::drawSelection(OutputDev *out,
5418                                  double scale,
5419                                  int rotation,
5420                                  PDFRectangle *selection,
5421                                  SelectionStyle style,
5422                                  GfxColor *glyph_color, GfxColor *box_color) {
5423  text->drawSelection(out, scale, rotation, selection, style, glyph_color, box_color);
5424}
5425
5426GooList *TextOutputDev::getSelectionRegion(PDFRectangle *selection,
5427                                           SelectionStyle style,
5428                                           double scale) {
5429  return text->getSelectionRegion(selection, style, scale);
5430}
5431
5432GooString *TextOutputDev::getSelectionText(PDFRectangle *selection,
5433                                           SelectionStyle style)
5434{
5435  return text->getSelectionText(selection, style);
5436}
5437
5438GBool TextOutputDev::findCharRange(int pos, int length,
5439                                   double *xMin, double *yMin,
5440                                   double *xMax, double *yMax) {
5441  return text->findCharRange(pos, length, xMin, yMin, xMax, yMax);
5442}
5443
5444#if TEXTOUT_WORD_LIST
5445TextWordList *TextOutputDev::makeWordList() {
5446  return text->makeWordList(physLayout);
5447}
5448#endif
5449
5450TextPage *TextOutputDev::takeText() {
5451  TextPage *ret;
5452
5453  ret = text;
5454  text = new TextPage(rawOrder);
5455  return ret;
5456}
Note: See TracBrowser for help on using the repository browser.