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

Last change on this file since 461 was 461, checked in by Silvan Scherrer, 11 years ago

poppler update to 0.14.2

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