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

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

poppler, jpeg, freetype lib updates

File size: 137.6 KB
RevLine 
[2]1//========================================================================
2//
3// TextOutputDev.cc
4//
5// Copyright 1997-2003 Glyph & Cog, LLC
6//
7//========================================================================
8
[257]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>
[261]15// Copyright (C) 2006-2008 Carlos Garcia Campos <carlosgc@gnome.org>
[257]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>
[461]20// Copyright (C) 2008, 2010 Albert Astals Cid <aacid@kde.org>
[277]21// Copyright (C) 2008 Pino Toscano <pino@kde.org>
[461]22// Copyright (C) 2008, 2010 Hib Eris <hib@hiberis.nl>
[277]23// Copyright (C) 2009 Ross Moore <ross@maths.mq.edu.au>
24// Copyright (C) 2009 Kovid Goyal <kovid@kovidgoyal.net>
[461]25// Copyright (C) 2010 Brian Ewins <brian.ewins@gmail.com>
[470]26// Copyright (C) 2010 Suzuki Toshiya <mpsuzuki@hiroshima-u.ac.jp>
[257]27//
28// To see a description of the changes please see the Changelog file that
29// came with your tarball or type make ChangeLog if you are building from git
30//
31//========================================================================
32
[2]33#include <config.h>
34
35#ifdef USE_GCC_PRAGMAS
36#pragma implementation
37#endif
38
39#include <stdio.h>
40#include <stdlib.h>
41#include <stddef.h>
42#include <math.h>
[461]43#include <float.h>
[2]44#include <ctype.h>
[277]45#ifdef _WIN32
[2]46#include <fcntl.h> // for O_BINARY
47#include <io.h>    // for setmode
48#endif
49#include "goo/gmem.h"
50#include "goo/GooString.h"
51#include "goo/GooList.h"
52#include "poppler-config.h"
53#include "Error.h"
54#include "GlobalParams.h"
55#include "UnicodeMap.h"
56#include "UnicodeTypeTable.h"
[250]57#include "Link.h"
[2]58#include "TextOutputDev.h"
59#include "Page.h"
[250]60#include "PDFDocEncoding.h"
[2]61
62#ifdef MACOS
63// needed for setting type/creator of MacOS files
64#include "ICSupport.h"
65#endif
66
67//------------------------------------------------------------------------
68// parameters
69//------------------------------------------------------------------------
70
71// Each bucket in a text pool includes baselines within a range of
72// this many points.
73#define textPoolStep 4
74
75// Inter-character space width which will cause addChar to start a new
76// word.
77#define minWordBreakSpace 0.1
78
79// Negative inter-character space width, i.e., overlap, which will
80// cause addChar to start a new word.
81#define minDupBreakOverlap 0.2
82
83// Max distance between baselines of two lines within a block, as a
84// fraction of the font size.
85#define maxLineSpacingDelta 1.5
86
87// Max difference in primary font sizes on two lines in the same
88// block.  Delta1 is used when examining new lines above and below the
89// current block; delta2 is used when examining text that overlaps the
90// current block; delta3 is used when examining text to the left and
91// right of the current block.
92#define maxBlockFontSizeDelta1 0.05
93#define maxBlockFontSizeDelta2 0.6
94#define maxBlockFontSizeDelta3 0.2
95
96// Max difference in font sizes inside a word.
97#define maxWordFontSizeDelta 0.05
98
99// Maximum distance between baselines of two words on the same line,
100// e.g., distance between subscript or superscript and the primary
101// baseline, as a fraction of the font size.
102#define maxIntraLineDelta 0.5
103
104// Minimum inter-word spacing, as a fraction of the font size.  (Only
105// used for raw ordering.)
106#define minWordSpacing 0.15
107
108// Maximum inter-word spacing, as a fraction of the font size.
109#define maxWordSpacing 1.5
110
111// Maximum horizontal spacing which will allow a word to be pulled
112// into a block.
113#define minColSpacing1 0.3
114
115// Minimum spacing between columns, as a fraction of the font size.
116#define minColSpacing2 1.0
117
118// Maximum vertical spacing between blocks within a flow, as a
119// multiple of the font size.
120#define maxBlockSpacing 2.5
121
122// Minimum spacing between characters within a word, as a fraction of
123// the font size.
124#define minCharSpacing -0.2
125
126// Maximum spacing between characters within a word, as a fraction of
127// the font size, when there is no obvious extra-wide character
128// spacing.
129#define maxCharSpacing 0.03
130
131// When extra-wide character spacing is detected, the inter-character
132// space threshold is set to the minimum inter-character space
133// multiplied by this constant.
134#define maxWideCharSpacingMul 1.3
135
[250]136// Upper limit on spacing between characters in a word.
137#define maxWideCharSpacing 0.4
138
[2]139// Max difference in primary,secondary coordinates (as a fraction of
140// the font size) allowed for duplicated text (fake boldface, drop
141// shadows) which is to be discarded.
142#define dupMaxPriDelta 0.1
143#define dupMaxSecDelta 0.2
144
[250]145// Max width of underlines (in points).
146#define maxUnderlineWidth 3
147
148// Min distance between baseline and underline (in points).
149//~ this should be font-size-dependent
150#define minUnderlineGap -2
151
152// Max distance between baseline and underline (in points).
153//~ this should be font-size-dependent
154#define maxUnderlineGap 4
155
156// Max horizontal distance between edge of word and start of underline
157// (in points).
158//~ this should be font-size-dependent
159#define underlineSlack 1
160
161// Max distance between edge of text and edge of link border
162#define hyperlinkSlack 2
163
[2]164//------------------------------------------------------------------------
[250]165// TextUnderline
166//------------------------------------------------------------------------
167
168class TextUnderline {
169public:
170
171  TextUnderline(double x0A, double y0A, double x1A, double y1A)
172    { x0 = x0A; y0 = y0A; x1 = x1A; y1 = y1A; horiz = y0 == y1; }
173  ~TextUnderline() {}
174
175  double x0, y0, x1, y1;
176  GBool horiz;
177};
178
179//------------------------------------------------------------------------
180// TextLink
181//------------------------------------------------------------------------
182
183class TextLink {
184public:
185
186  TextLink(int xMinA, int yMinA, int xMaxA, int yMaxA, Link *linkA)
187    { xMin = xMinA; yMin = yMinA; xMax = xMaxA; yMax = yMaxA; link = linkA; }
188  ~TextLink() {}
189
190  int xMin, yMin, xMax, yMax;
191  Link *link;
192};
193
194//------------------------------------------------------------------------
[2]195// TextFontInfo
196//------------------------------------------------------------------------
197
198TextFontInfo::TextFontInfo(GfxState *state) {
199  gfxFont = state->getFont();
[134]200  if (gfxFont)
201    gfxFont->incRefCnt();
[2]202#if TEXTOUT_WORD_LIST
203  fontName = (gfxFont && gfxFont->getOrigName())
204                 ? gfxFont->getOrigName()->copy()
205                 : (GooString *)NULL;
[250]206  flags = gfxFont ? gfxFont->getFlags() : 0;
[2]207#endif
208}
209
210TextFontInfo::~TextFontInfo() {
[134]211  if (gfxFont)
212    gfxFont->decRefCnt();
[2]213#if TEXTOUT_WORD_LIST
214  if (fontName) {
215    delete fontName;
216  }
217#endif
218}
219
220GBool TextFontInfo::matches(GfxState *state) {
221  return state->getFont() == gfxFont;
222}
223
224//------------------------------------------------------------------------
225// TextWord
226//------------------------------------------------------------------------
227
228TextWord::TextWord(GfxState *state, int rotA, double x0, double y0,
229                   int charPosA, TextFontInfo *fontA, double fontSizeA) {
230  GfxFont *gfxFont;
231  double x, y, ascent, descent;
232
233  rot = rotA;
234  charPos = charPosA;
235  charLen = 0;
236  font = fontA;
237  fontSize = fontSizeA;
238  state->transform(x0, y0, &x, &y);
239  if ((gfxFont = font->gfxFont)) {
240    ascent = gfxFont->getAscent() * fontSize;
241    descent = gfxFont->getDescent() * fontSize;
242  } else {
243    // this means that the PDF file draws text without a current font,
244    // which should never happen
245    ascent = 0.95 * fontSize;
246    descent = -0.35 * fontSize;
247  }
248  switch (rot) {
249  case 0:
250    yMin = y - ascent;
251    yMax = y - descent;
252    if (yMin == yMax) {
253      // this is a sanity check for a case that shouldn't happen -- but
254      // if it does happen, we want to avoid dividing by zero later
255      yMin = y;
256      yMax = y + 1;
257    }
258    base = y;
259    break;
260  case 1:
261    xMin = x + descent;
262    xMax = x + ascent;
263    if (xMin == xMax) {
264      // this is a sanity check for a case that shouldn't happen -- but
265      // if it does happen, we want to avoid dividing by zero later
266      xMin = x;
267      xMax = x + 1;
268    }
269    base = x;
270    break;
271  case 2:
272    yMin = y + descent;
273    yMax = y + ascent;
274    if (yMin == yMax) {
275      // this is a sanity check for a case that shouldn't happen -- but
276      // if it does happen, we want to avoid dividing by zero later
277      yMin = y;
278      yMax = y + 1;
279    }
280    base = y;
281    break;
282  case 3:
283    xMin = x - ascent;
284    xMax = x - descent;
285    if (xMin == xMax) {
286      // this is a sanity check for a case that shouldn't happen -- but
287      // if it does happen, we want to avoid dividing by zero later
288      xMin = x;
289      xMax = x + 1;
290    }
291    base = x;
292    break;
293  }
294  text = NULL;
295  charcode = NULL;
296  edge = NULL;
297  len = size = 0;
298  spaceAfter = gFalse;
299  next = NULL;
300
301#if TEXTOUT_WORD_LIST
302  GfxRGB rgb;
303
304  if ((state->getRender() & 3) == 1) {
305    state->getStrokeRGB(&rgb);
306  } else {
307    state->getFillRGB(&rgb);
308  }
309  colorR = colToDbl(rgb.r);
310  colorG = colToDbl(rgb.g);
311  colorB = colToDbl(rgb.b);
312#endif
[250]313
314  underlined = gFalse;
315  link = NULL;
[2]316}
317
318TextWord::~TextWord() {
319  gfree(text);
320  gfree(charcode);
321  gfree(edge);
322}
323
324void TextWord::addChar(GfxState *state, double x, double y,
325                       double dx, double dy, CharCode c, Unicode u) {
326  if (len == size) {
327    size += 16;
328    text = (Unicode *)greallocn(text, size, sizeof(Unicode));
329    charcode = (Unicode *)greallocn(charcode, size, sizeof(CharCode));
330    edge = (double *)greallocn(edge, (size + 1), sizeof(double));
331  }
332  text[len] = u;
333  charcode[len] = c;
334  switch (rot) {
335  case 0:
336    if (len == 0) {
337      xMin = x;
338    }
339    edge[len] = x;
340    xMax = edge[len+1] = x + dx;
341    break;
342  case 1:
343    if (len == 0) {
344      yMin = y;
345    }
346    edge[len] = y;
347    yMax = edge[len+1] = y + dy;
348    break;
349  case 2:
350    if (len == 0) {
351      xMax = x;
352    }
353    edge[len] = x;
354    xMin = edge[len+1] = x + dx;
355    break;
356  case 3:
357    if (len == 0) {
358      yMax = y;
359    }
360    edge[len] = y;
361    yMin = edge[len+1] = y + dy;
362    break;
363  }
364  ++len;
365}
366
367void TextWord::merge(TextWord *word) {
368  int i;
369
370  if (word->xMin < xMin) {
371    xMin = word->xMin;
372  }
373  if (word->yMin < yMin) {
374    yMin = word->yMin;
375  }
376  if (word->xMax > xMax) {
377    xMax = word->xMax;
378  }
379  if (word->yMax > yMax) {
380    yMax = word->yMax;
381  }
382  if (len + word->len > size) {
383    size = len + word->len;
384    text = (Unicode *)greallocn(text, size, sizeof(Unicode));
385    charcode = (CharCode *)greallocn(charcode, (size + 1), sizeof(CharCode));
386    edge = (double *)greallocn(edge, (size + 1), sizeof(double));
387  }
388  for (i = 0; i < word->len; ++i) {
389    text[len + i] = word->text[i];
390    charcode[len + i] = word->charcode[i];
391    edge[len + i] = word->edge[i];
392  }
393  edge[len + word->len] = word->edge[word->len];
394  len += word->len;
395  charLen += word->charLen;
396}
397
398inline int TextWord::primaryCmp(TextWord *word) {
399  double cmp;
400
401  cmp = 0; // make gcc happy
402  switch (rot) {
403  case 0:
404    cmp = xMin - word->xMin;
405    break;
406  case 1:
407    cmp = yMin - word->yMin;
408    break;
409  case 2:
410    cmp = word->xMax - xMax;
411    break;
412  case 3:
413    cmp = word->yMax - yMax;
414    break;
415  }
416  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
417}
418
419double TextWord::primaryDelta(TextWord *word) {
420  double delta;
421
422  delta = 0; // make gcc happy
423  switch (rot) {
424  case 0:
425    delta = word->xMin - xMax;
426    break;
427  case 1:
428    delta = word->yMin - yMax;
429    break;
430  case 2:
431    delta = xMin - word->xMax;
432    break;
433  case 3:
434    delta = yMin - word->yMax;
435    break;
436  }
437  return delta;
438}
439
440int TextWord::cmpYX(const void *p1, const void *p2) {
441  TextWord *word1 = *(TextWord **)p1;
442  TextWord *word2 = *(TextWord **)p2;
443  double cmp;
444
445  cmp = word1->yMin - word2->yMin;
446  if (cmp == 0) {
447    cmp = word1->xMin - word2->xMin;
448  }
449  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
450}
451
452#if TEXTOUT_WORD_LIST
453
454GooString *TextWord::getText() {
455  GooString *s;
456  UnicodeMap *uMap;
457  char buf[8];
458  int n, i;
459
460  s = new GooString();
461  if (!(uMap = globalParams->getTextEncoding())) {
462    return s;
463  }
464  for (i = 0; i < len; ++i) {
465    n = uMap->mapUnicode(text[i], buf, sizeof(buf));
466    s->append(buf, n);
467  }
468  uMap->decRefCnt();
469  return s;
470}
471
[250]472void TextWord::getCharBBox(int charIdx, double *xMinA, double *yMinA,
473                           double *xMaxA, double *yMaxA) {
474  if (charIdx < 0 || charIdx >= len) {
475    return;
476  }
477  switch (rot) {
478  case 0:
479    *xMinA = edge[charIdx];
480    *xMaxA = edge[charIdx + 1];
481    *yMinA = yMin;
482    *yMaxA = yMax;
483    break;
484  case 1:
485    *xMinA = xMin;
486    *xMaxA = xMax;
487    *yMinA = edge[charIdx];
488    *yMaxA = edge[charIdx + 1];
489    break;
490  case 2:
491    *xMinA = edge[charIdx + 1];
492    *xMaxA = edge[charIdx];
493    *yMinA = yMin;
494    *yMaxA = yMax;
495    break;
496  case 3:
497    *xMinA = xMin;
498    *xMaxA = xMax;
499    *yMinA = edge[charIdx + 1];
500    *yMaxA = edge[charIdx];
501    break;
502  }
503}
504
[2]505#endif // TEXTOUT_WORD_LIST
506
507//------------------------------------------------------------------------
508// TextPool
509//------------------------------------------------------------------------
510
511TextPool::TextPool() {
512  minBaseIdx = 0;
513  maxBaseIdx = -1;
514  pool = NULL;
515  cursor = NULL;
516  cursorBaseIdx = -1;
517}
518
519TextPool::~TextPool() {
520  int baseIdx;
521  TextWord *word, *word2;
522
523  for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
524    for (word = pool[baseIdx - minBaseIdx]; word; word = word2) {
525      word2 = word->next;
526      delete word;
527    }
528  }
529  gfree(pool);
530}
531
532int TextPool::getBaseIdx(double base) {
533  int baseIdx;
534
535  baseIdx = (int)(base / textPoolStep);
536  if (baseIdx < minBaseIdx) {
537    return minBaseIdx;
538  }
539  if (baseIdx > maxBaseIdx) {
540    return maxBaseIdx;
541  }
542  return baseIdx;
543}
544
545void TextPool::addWord(TextWord *word) {
546  TextWord **newPool;
547  int wordBaseIdx, newMinBaseIdx, newMaxBaseIdx, baseIdx;
548  TextWord *w0, *w1;
549
550  // expand the array if needed
551  wordBaseIdx = (int)(word->base / textPoolStep);
552  if (minBaseIdx > maxBaseIdx) {
553    minBaseIdx = wordBaseIdx - 128;
554    maxBaseIdx = wordBaseIdx + 128;
555    pool = (TextWord **)gmallocn(maxBaseIdx - minBaseIdx + 1,
556                                 sizeof(TextWord *));
557    for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
558      pool[baseIdx - minBaseIdx] = NULL;
559    }
560  } else if (wordBaseIdx < minBaseIdx) {
561    newMinBaseIdx = wordBaseIdx - 128;
562    newPool = (TextWord **)gmallocn(maxBaseIdx - newMinBaseIdx + 1,
563                                    sizeof(TextWord *));
564    for (baseIdx = newMinBaseIdx; baseIdx < minBaseIdx; ++baseIdx) {
565      newPool[baseIdx - newMinBaseIdx] = NULL;
566    }
567    memcpy(&newPool[minBaseIdx - newMinBaseIdx], pool,
568           (maxBaseIdx - minBaseIdx + 1) * sizeof(TextWord *));
569    gfree(pool);
570    pool = newPool;
571    minBaseIdx = newMinBaseIdx;
572  } else if (wordBaseIdx > maxBaseIdx) {
573    newMaxBaseIdx = wordBaseIdx + 128;
574    pool = (TextWord **)greallocn(pool, newMaxBaseIdx - minBaseIdx + 1,
575                                  sizeof(TextWord *));
576    for (baseIdx = maxBaseIdx + 1; baseIdx <= newMaxBaseIdx; ++baseIdx) {
577      pool[baseIdx - minBaseIdx] = NULL;
578    }
579    maxBaseIdx = newMaxBaseIdx;
580  }
581
582  // insert the new word
583  if (cursor && wordBaseIdx == cursorBaseIdx &&
584      word->primaryCmp(cursor) > 0) {
585    w0 = cursor;
586    w1 = cursor->next;
587  } else {
588    w0 = NULL;
589    w1 = pool[wordBaseIdx - minBaseIdx];
590  }
591  for (; w1 && word->primaryCmp(w1) > 0; w0 = w1, w1 = w1->next) ;
592  word->next = w1;
593  if (w0) {
594    w0->next = word;
595  } else {
596    pool[wordBaseIdx - minBaseIdx] = word;
597  }
598  cursor = word;
599  cursorBaseIdx = wordBaseIdx;
600}
601
602//------------------------------------------------------------------------
603// TextLine
604//------------------------------------------------------------------------
605
606TextLine::TextLine(TextBlock *blkA, int rotA, double baseA) {
607  blk = blkA;
608  rot = rotA;
609  base = baseA;
610  words = lastWord = NULL;
611  text = NULL;
612  edge = NULL;
613  col = NULL;
614  len = 0;
615  convertedLen = 0;
616  hyphenated = gFalse;
617  next = NULL;
618  xMin = yMin = 0;
619  xMax = yMax = -1;
[27]620  normalized = NULL;
621  normalized_len = 0;
622  normalized_idx = NULL;
[2]623}
624
625TextLine::~TextLine() {
626  TextWord *word;
627
628  while (words) {
629    word = words;
630    words = words->next;
631    delete word;
632  }
633  gfree(text);
634  gfree(edge);
635  gfree(col);
[27]636  if (normalized) {
637    gfree(normalized);
638    gfree(normalized_idx);
639  }
[2]640}
641
642void TextLine::addWord(TextWord *word) {
643  if (lastWord) {
644    lastWord->next = word;
645  } else {
646    words = word;
647  }
648  lastWord = word;
649
650  if (xMin > xMax) {
651    xMin = word->xMin;
652    xMax = word->xMax;
653    yMin = word->yMin;
654    yMax = word->yMax;
655  } else {
656    if (word->xMin < xMin) {
657      xMin = word->xMin;
658    }
659    if (word->xMax > xMax) {
660      xMax = word->xMax;
661    }
662    if (word->yMin < yMin) {
663      yMin = word->yMin;
664    }
665    if (word->yMax > yMax) {
666      yMax = word->yMax;
667    }
668  }
669}
670
671double TextLine::primaryDelta(TextLine *line) {
672  double delta;
673
674  delta = 0; // make gcc happy
675  switch (rot) {
676  case 0:
677    delta = line->xMin - xMax;
678    break;
679  case 1:
680    delta = line->yMin - yMax;
681    break;
682  case 2:
683    delta = xMin - line->xMax;
684    break;
685  case 3:
686    delta = yMin - line->yMax;
687    break;
688  }
689  return delta;
690}
691
692int TextLine::primaryCmp(TextLine *line) {
693  double cmp;
694
695  cmp = 0; // make gcc happy
696  switch (rot) {
697  case 0:
698    cmp = xMin - line->xMin;
699    break;
700  case 1:
701    cmp = yMin - line->yMin;
702    break;
703  case 2:
704    cmp = line->xMax - xMax;
705    break;
706  case 3:
707    cmp = line->yMax - yMax;
708    break;
709  }
710  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
711}
712
713int TextLine::secondaryCmp(TextLine *line) {
714  double cmp;
715
716  cmp = (rot == 0 || rot == 3) ? base - line->base : line->base - base;
717  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
718}
719
720int TextLine::cmpYX(TextLine *line) {
721  int cmp;
722
723  if ((cmp = secondaryCmp(line))) {
724    return cmp;
725  }
726  return primaryCmp(line);
727}
728
729int TextLine::cmpXY(const void *p1, const void *p2) {
730  TextLine *line1 = *(TextLine **)p1;
731  TextLine *line2 = *(TextLine **)p2;
732  int cmp;
733
734  if ((cmp = line1->primaryCmp(line2))) {
735    return cmp;
736  }
737  return line1->secondaryCmp(line2);
738}
739
740void TextLine::coalesce(UnicodeMap *uMap) {
741  TextWord *word0, *word1;
742  double space, delta, minSpace;
743  GBool isUnicode;
744  char buf[8];
745  int i, j;
746
747  if (words->next) {
748
749    // compute the inter-word space threshold
750    if (words->len > 1 || words->next->len > 1) {
751      minSpace = 0;
752    } else {
753      minSpace = words->primaryDelta(words->next);
754      for (word0 = words->next, word1 = word0->next;
755           word1 && minSpace > 0;
756           word0 = word1, word1 = word0->next) {
757        if (word1->len > 1) {
758          minSpace = 0;
759        }
760        delta = word0->primaryDelta(word1);
761        if (delta < minSpace) {
762          minSpace = delta;
763        }
764      }
765    }
766    if (minSpace <= 0) {
767      space = maxCharSpacing * words->fontSize;
768    } else {
769      space = maxWideCharSpacingMul * minSpace;
[250]770      if (space > maxWideCharSpacing * words->fontSize) {
771        space = maxWideCharSpacing * words->fontSize;
772      }
[2]773    }
774
775    // merge words
776    word0 = words;
777    word1 = words->next;
778    while (word1) {
779      if (word0->primaryDelta(word1) >= space) {
780        word0->spaceAfter = gTrue;
781        word0 = word1;
782        word1 = word1->next;
783      } else if (word0->font == word1->font &&
[250]784                 word0->underlined == word1->underlined &&
[2]785                 fabs(word0->fontSize - word1->fontSize) <
[250]786                   maxWordFontSizeDelta * words->fontSize &&
[2]787                 word1->charPos == word0->charPos + word0->charLen) {
788        word0->merge(word1);
789        word0->next = word1->next;
790        delete word1;
791        word1 = word0->next;
792      } else {
793        word0 = word1;
794        word1 = word1->next;
795      }
796    }
797  }
798
799  // build the line text
800  isUnicode = uMap ? uMap->isUnicode() : gFalse;
801  len = 0;
802  for (word1 = words; word1; word1 = word1->next) {
803    len += word1->len;
804    if (word1->spaceAfter) {
805      ++len;
806    }
807  }
808  text = (Unicode *)gmallocn(len, sizeof(Unicode));
809  edge = (double *)gmallocn(len + 1, sizeof(double));
810  i = 0;
811  for (word1 = words; word1; word1 = word1->next) {
812    for (j = 0; j < word1->len; ++j) {
813      text[i] = word1->text[j];
814      edge[i] = word1->edge[j];
815      ++i;
816    }
817    edge[i] = word1->edge[word1->len];
818    if (word1->spaceAfter) {
819      text[i] = (Unicode)0x0020;
820      ++i;
821    }
822  }
823
824  // compute convertedLen and set up the col array
825  col = (int *)gmallocn(len + 1, sizeof(int));
826  convertedLen = 0;
827  for (i = 0; i < len; ++i) {
828    col[i] = convertedLen;
829    if (isUnicode) {
830      ++convertedLen;
831    } else if (uMap) {
832      convertedLen += uMap->mapUnicode(text[i], buf, sizeof(buf));
833    }
834  }
835  col[len] = convertedLen;
836
837  // check for hyphen at end of line
838  //~ need to check for other chars used as hyphens
839  hyphenated = text[len - 1] == (Unicode)'-';
840}
841
842//------------------------------------------------------------------------
843// TextLineFrag
844//------------------------------------------------------------------------
845
846class TextLineFrag {
847public:
848
849  TextLine *line;               // the line object
850  int start, len;               // offset and length of this fragment
851                                //   (in Unicode chars)
852  double xMin, xMax;            // bounding box coordinates
853  double yMin, yMax;
854  double base;                  // baseline virtual coordinate
855  int col;                      // first column
856
857  void init(TextLine *lineA, int startA, int lenA);
858  void computeCoords(GBool oneRot);
859
860  static int cmpYXPrimaryRot(const void *p1, const void *p2);
861  static int cmpYXLineRot(const void *p1, const void *p2);
862  static int cmpXYLineRot(const void *p1, const void *p2);
[250]863  static int cmpXYColumnPrimaryRot(const void *p1, const void *p2);
864  static int cmpXYColumnLineRot(const void *p1, const void *p2);
[2]865};
866
867void TextLineFrag::init(TextLine *lineA, int startA, int lenA) {
868  line = lineA;
869  start = startA;
870  len = lenA;
871  col = line->col[start];
872}
873
874void TextLineFrag::computeCoords(GBool oneRot) {
875  TextBlock *blk;
876  double d0, d1, d2, d3, d4;
877
878  if (oneRot) {
879
880    switch (line->rot) {
881    case 0:
882      xMin = line->edge[start];
883      xMax = line->edge[start + len];
884      yMin = line->yMin;
885      yMax = line->yMax;
886      break;
887    case 1:
888      xMin = line->xMin;
889      xMax = line->xMax;
890      yMin = line->edge[start];
891      yMax = line->edge[start + len];
892      break;
893    case 2:
894      xMin = line->edge[start + len];
895      xMax = line->edge[start];
896      yMin = line->yMin;
897      yMax = line->yMax;
898      break;
899    case 3:
900      xMin = line->xMin;
901      xMax = line->xMax;
902      yMin = line->edge[start + len];
903      yMax = line->edge[start];
904      break;
905    }
906    base = line->base;
907
908  } else {
909
910    if (line->rot == 0 && line->blk->page->primaryRot == 0) {
911
912      xMin = line->edge[start];
913      xMax = line->edge[start + len];
914      yMin = line->yMin;
915      yMax = line->yMax;
916      base = line->base;
917
918    } else {
919
920      blk = line->blk;
921      d0 = line->edge[start];
922      d1 = line->edge[start + len];
923      d2 = d3 = d4 = 0; // make gcc happy
924
925      switch (line->rot) {
926      case 0:
927        d2 = line->yMin;
928        d3 = line->yMax;
929        d4 = line->base;
930        d0 = (d0 - blk->xMin) / (blk->xMax - blk->xMin);
931        d1 = (d1 - blk->xMin) / (blk->xMax - blk->xMin);
932        d2 = (d2 - blk->yMin) / (blk->yMax - blk->yMin);
933        d3 = (d3 - blk->yMin) / (blk->yMax - blk->yMin);
934        d4 = (d4 - blk->yMin) / (blk->yMax - blk->yMin);
935        break;
936      case 1:
937        d2 = line->xMax;
938        d3 = line->xMin;
939        d4 = line->base;
940        d0 = (d0 - blk->yMin) / (blk->yMax - blk->yMin);
941        d1 = (d1 - blk->yMin) / (blk->yMax - blk->yMin);
942        d2 = (blk->xMax - d2) / (blk->xMax - blk->xMin);
943        d3 = (blk->xMax - d3) / (blk->xMax - blk->xMin);
944        d4 = (blk->xMax - d4) / (blk->xMax - blk->xMin);
945        break;
946      case 2:
947        d2 = line->yMax;
948        d3 = line->yMin;
949        d4 = line->base;
950        d0 = (blk->xMax - d0) / (blk->xMax - blk->xMin);
951        d1 = (blk->xMax - d1) / (blk->xMax - blk->xMin);
952        d2 = (blk->yMax - d2) / (blk->yMax - blk->yMin);
953        d3 = (blk->yMax - d3) / (blk->yMax - blk->yMin);
954        d4 = (blk->yMax - d4) / (blk->yMax - blk->yMin);
955        break;
956      case 3:
957        d2 = line->xMin;
958        d3 = line->xMax;
959        d4 = line->base;
960        d0 = (blk->yMax - d0) / (blk->yMax - blk->yMin);
961        d1 = (blk->yMax - d1) / (blk->yMax - blk->yMin);
962        d2 = (d2 - blk->xMin) / (blk->xMax - blk->xMin);
963        d3 = (d3 - blk->xMin) / (blk->xMax - blk->xMin);
964        d4 = (d4 - blk->xMin) / (blk->xMax - blk->xMin);
965        break;
966      }
967
968      switch (line->blk->page->primaryRot) {
969      case 0:
970        xMin = blk->xMin + d0 * (blk->xMax - blk->xMin);
971        xMax = blk->xMin + d1 * (blk->xMax - blk->xMin);
972        yMin = blk->yMin + d2 * (blk->yMax - blk->yMin);
973        yMax = blk->yMin + d3 * (blk->yMax - blk->yMin);
974        base = blk->yMin + base * (blk->yMax - blk->yMin);
975        break;
976      case 1:
977        xMin = blk->xMax - d3 * (blk->xMax - blk->xMin);
978        xMax = blk->xMax - d2 * (blk->xMax - blk->xMin);
979        yMin = blk->yMin + d0 * (blk->yMax - blk->yMin);
980        yMax = blk->yMin + d1 * (blk->yMax - blk->yMin);
981        base = blk->xMax - d4 * (blk->xMax - blk->xMin);
982        break;
983      case 2:
984        xMin = blk->xMax - d1 * (blk->xMax - blk->xMin);
985        xMax = blk->xMax - d0 * (blk->xMax - blk->xMin);
986        yMin = blk->yMax - d3 * (blk->yMax - blk->yMin);
987        yMax = blk->yMax - d2 * (blk->yMax - blk->yMin);
988        base = blk->yMax - d4 * (blk->yMax - blk->yMin);
989        break;
990      case 3:
991        xMin = blk->xMin + d2 * (blk->xMax - blk->xMin);
992        xMax = blk->xMin + d3 * (blk->xMax - blk->xMin);
993        yMin = blk->yMax - d1 * (blk->yMax - blk->yMin);
994        yMax = blk->yMax - d0 * (blk->yMax - blk->yMin);
995        base = blk->xMin + d4 * (blk->xMax - blk->xMin);
996        break;
997      }
998
999    }
1000  }
1001}
1002
1003int TextLineFrag::cmpYXPrimaryRot(const void *p1, const void *p2) {
1004  TextLineFrag *frag1 = (TextLineFrag *)p1;
1005  TextLineFrag *frag2 = (TextLineFrag *)p2;
1006  double cmp;
1007
1008  cmp = 0; // make gcc happy
1009  switch (frag1->line->blk->page->primaryRot) {
1010  case 0:
1011    if (fabs(cmp = frag1->yMin - frag2->yMin) < 0.01) {
1012      cmp = frag1->xMin - frag2->xMin;
1013    }
1014    break;
1015  case 1:
1016    if (fabs(cmp = frag2->xMax - frag1->xMax) < 0.01) {
1017      cmp = frag1->yMin - frag2->yMin;
1018    }
1019    break;
1020  case 2:
1021    if (fabs(cmp = frag2->yMin - frag1->yMin) < 0.01) {
1022      cmp = frag2->xMax - frag1->xMax;
1023    }
1024    break;
1025  case 3:
1026    if (fabs(cmp = frag1->xMax - frag2->xMax) < 0.01) {
1027      cmp = frag2->yMax - frag1->yMax;
1028    }
1029    break;
1030  }
1031  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1032}
1033
1034int TextLineFrag::cmpYXLineRot(const void *p1, const void *p2) {
1035  TextLineFrag *frag1 = (TextLineFrag *)p1;
1036  TextLineFrag *frag2 = (TextLineFrag *)p2;
1037  double cmp;
1038
1039  cmp = 0; // make gcc happy
1040  switch (frag1->line->rot) {
1041  case 0:
1042    if ((cmp = frag1->yMin - frag2->yMin) == 0) {
1043      cmp = frag1->xMin - frag2->xMin;
1044    }
1045    break;
1046  case 1:
1047    if ((cmp = frag2->xMax - frag1->xMax) == 0) {
1048      cmp = frag1->yMin - frag2->yMin;
1049    }
1050    break;
1051  case 2:
1052    if ((cmp = frag2->yMin - frag1->yMin) == 0) {
1053      cmp = frag2->xMax - frag1->xMax;
1054    }
1055    break;
1056  case 3:
1057    if ((cmp = frag1->xMax - frag2->xMax) == 0) {
1058      cmp = frag2->yMax - frag1->yMax;
1059    }
1060    break;
1061  }
1062  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1063}
1064
1065int TextLineFrag::cmpXYLineRot(const void *p1, const void *p2) {
1066  TextLineFrag *frag1 = (TextLineFrag *)p1;
1067  TextLineFrag *frag2 = (TextLineFrag *)p2;
1068  double cmp;
1069
1070  cmp = 0; // make gcc happy
1071  switch (frag1->line->rot) {
1072  case 0:
1073    if ((cmp = frag1->xMin - frag2->xMin) == 0) {
1074      cmp = frag1->yMin - frag2->yMin;
1075    }
1076    break;
1077  case 1:
1078    if ((cmp = frag1->yMin - frag2->yMin) == 0) {
1079      cmp = frag2->xMax - frag1->xMax;
1080    }
1081    break;
1082  case 2:
1083    if ((cmp = frag2->xMax - frag1->xMax) == 0) {
1084      cmp = frag2->yMin - frag1->yMin;
1085    }
1086    break;
1087  case 3:
1088    if ((cmp = frag2->yMax - frag1->yMax) == 0) {
1089      cmp = frag1->xMax - frag2->xMax;
1090    }
1091    break;
1092  }
1093  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1094}
1095
[250]1096int TextLineFrag::cmpXYColumnPrimaryRot(const void *p1, const void *p2) {
1097  TextLineFrag *frag1 = (TextLineFrag *)p1;
1098  TextLineFrag *frag2 = (TextLineFrag *)p2;
1099  double cmp;
1100
1101  // if columns overlap, compare y values
1102  if (frag1->col < frag2->col + (frag2->line->col[frag2->start + frag2->len] -
1103                                 frag2->line->col[frag2->start]) &&
1104      frag2->col < frag1->col + (frag1->line->col[frag1->start + frag1->len] -
1105                                 frag1->line->col[frag1->start])) {
1106    cmp = 0; // make gcc happy
1107    switch (frag1->line->blk->page->primaryRot) {
1108    case 0: cmp = frag1->yMin - frag2->yMin; break;
1109    case 1: cmp = frag2->xMax - frag1->xMax; break;
1110    case 2: cmp = frag2->yMin - frag1->yMin; break;
1111    case 3: cmp = frag1->xMax - frag2->xMax; break;
1112    }
1113    return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1114  }
1115
1116  // otherwise, compare starting column
1117  return frag1->col - frag2->col;
1118}
1119
1120int TextLineFrag::cmpXYColumnLineRot(const void *p1, const void *p2) {
1121  TextLineFrag *frag1 = (TextLineFrag *)p1;
1122  TextLineFrag *frag2 = (TextLineFrag *)p2;
1123  double cmp;
1124
1125  // if columns overlap, compare y values
1126  if (frag1->col < frag2->col + (frag2->line->col[frag2->start + frag2->len] -
1127                                 frag2->line->col[frag2->start]) &&
1128      frag2->col < frag1->col + (frag1->line->col[frag1->start + frag1->len] -
1129                                 frag1->line->col[frag1->start])) {
1130    cmp = 0; // make gcc happy
1131    switch (frag1->line->rot) {
1132    case 0: cmp = frag1->yMin - frag2->yMin; break;
1133    case 1: cmp = frag2->xMax - frag1->xMax; break;
1134    case 2: cmp = frag2->yMin - frag1->yMin; break;
1135    case 3: cmp = frag1->xMax - frag2->xMax; break;
1136    }
1137    return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1138  }
1139
1140  // otherwise, compare starting column
1141  return frag1->col - frag2->col;
1142}
1143
[2]1144//------------------------------------------------------------------------
1145// TextBlock
1146//------------------------------------------------------------------------
1147
1148TextBlock::TextBlock(TextPage *pageA, int rotA) {
1149  page = pageA;
1150  rot = rotA;
1151  xMin = yMin = 0;
1152  xMax = yMax = -1;
1153  priMin = 0;
1154  priMax = page->pageWidth;
1155  pool = new TextPool();
1156  lines = NULL;
1157  curLine = NULL;
1158  next = NULL;
1159  stackNext = NULL;
[461]1160  tableId = -1;
1161  tableEnd = gFalse;
[2]1162}
1163
1164TextBlock::~TextBlock() {
1165  TextLine *line;
1166
1167  delete pool;
1168  while (lines) {
1169    line = lines;
1170    lines = lines->next;
1171    delete line;
1172  }
1173}
1174
1175void TextBlock::addWord(TextWord *word) {
1176  pool->addWord(word);
1177  if (xMin > xMax) {
1178    xMin = word->xMin;
1179    xMax = word->xMax;
1180    yMin = word->yMin;
1181    yMax = word->yMax;
1182  } else {
1183    if (word->xMin < xMin) {
1184      xMin = word->xMin;
1185    }
1186    if (word->xMax > xMax) {
1187      xMax = word->xMax;
1188    }
1189    if (word->yMin < yMin) {
1190      yMin = word->yMin;
1191    }
1192    if (word->yMax > yMax) {
1193      yMax = word->yMax;
1194    }
1195  }
1196}
1197
1198void TextBlock::coalesce(UnicodeMap *uMap) {
1199  TextWord *word0, *word1, *word2, *bestWord0, *bestWord1, *lastWord;
1200  TextLine *line, *line0, *line1;
1201  int poolMinBaseIdx, startBaseIdx, minBaseIdx, maxBaseIdx;
1202  int baseIdx, bestWordBaseIdx, idx0, idx1;
1203  double minBase, maxBase;
1204  double fontSize, delta, priDelta, secDelta;
1205  TextLine **lineArray;
1206  GBool found;
1207  int col1, col2;
1208  int i, j, k;
1209
1210  // discard duplicated text (fake boldface, drop shadows)
1211  for (idx0 = pool->minBaseIdx; idx0 <= pool->maxBaseIdx; ++idx0) {
1212    word0 = pool->getPool(idx0);
1213    while (word0) {
1214      priDelta = dupMaxPriDelta * word0->fontSize;
1215      secDelta = dupMaxSecDelta * word0->fontSize;
1216      if (rot == 0 || rot == 3) {
1217        maxBaseIdx = pool->getBaseIdx(word0->base + secDelta);
1218      } else {
1219        maxBaseIdx = pool->getBaseIdx(word0->base - secDelta);
1220      }
1221      found = gFalse;
1222      word1 = word2 = NULL; // make gcc happy
1223      for (idx1 = idx0; idx1 <= maxBaseIdx; ++idx1) {
1224        if (idx1 == idx0) {
1225          word1 = word0;
1226          word2 = word0->next;
1227        } else {
1228          word1 = NULL;
1229          word2 = pool->getPool(idx1);
1230        }
1231        for (; word2; word1 = word2, word2 = word2->next) {
1232          if (word2->len == word0->len &&
1233              !memcmp(word2->text, word0->text,
1234                      word0->len * sizeof(Unicode))) {
1235            switch (rot) {
1236            case 0:
1237            case 2:
1238              found = fabs(word0->xMin - word2->xMin) < priDelta &&
1239                      fabs(word0->xMax - word2->xMax) < priDelta &&
1240                      fabs(word0->yMin - word2->yMin) < secDelta &&
1241                      fabs(word0->yMax - word2->yMax) < secDelta;
1242              break;
1243            case 1:
1244            case 3:
1245              found = fabs(word0->xMin - word2->xMin) < secDelta &&
1246                      fabs(word0->xMax - word2->xMax) < secDelta &&
1247                      fabs(word0->yMin - word2->yMin) < priDelta &&
1248                      fabs(word0->yMax - word2->yMax) < priDelta;
1249              break;
1250            }
1251          }
1252          if (found) {
1253            break;
1254          }
1255        }
1256        if (found) {
1257          break;
1258        }
1259      }
1260      if (found) {
1261        if (word1) {
1262          word1->next = word2->next;
1263        } else {
1264          pool->setPool(idx1, word2->next);
1265        }
1266        delete word2;
1267      } else {
1268        word0 = word0->next;
1269      }
1270    }
1271  }
1272
1273  // build the lines
1274  curLine = NULL;
1275  poolMinBaseIdx = pool->minBaseIdx;
1276  charCount = 0;
1277  nLines = 0;
1278  while (1) {
1279
1280    // find the first non-empty line in the pool
1281    for (;
1282         poolMinBaseIdx <= pool->maxBaseIdx && !pool->getPool(poolMinBaseIdx);
1283         ++poolMinBaseIdx) ;
1284    if (poolMinBaseIdx > pool->maxBaseIdx) {
1285      break;
1286    }
1287
1288    // look for the left-most word in the first four lines of the
1289    // pool -- this avoids starting with a superscript word
1290    startBaseIdx = poolMinBaseIdx;
1291    for (baseIdx = poolMinBaseIdx + 1;
1292         baseIdx < poolMinBaseIdx + 4 && baseIdx <= pool->maxBaseIdx;
1293         ++baseIdx) {
1294      if (!pool->getPool(baseIdx)) {
1295        continue;
1296      }
1297      if (pool->getPool(baseIdx)->primaryCmp(pool->getPool(startBaseIdx))
1298          < 0) {
1299        startBaseIdx = baseIdx;
1300      }
1301    }
1302
1303    // create a new line
1304    word0 = pool->getPool(startBaseIdx);
1305    pool->setPool(startBaseIdx, word0->next);
1306    word0->next = NULL;
1307    line = new TextLine(this, word0->rot, word0->base);
1308    line->addWord(word0);
1309    lastWord = word0;
1310
1311    // compute the search range
1312    fontSize = word0->fontSize;
1313    minBase = word0->base - maxIntraLineDelta * fontSize;
1314    maxBase = word0->base + maxIntraLineDelta * fontSize;
1315    minBaseIdx = pool->getBaseIdx(minBase);
1316    maxBaseIdx = pool->getBaseIdx(maxBase);
1317
1318    // find the rest of the words in this line
1319    while (1) {
1320
1321      // find the left-most word whose baseline is in the range for
1322      // this line
1323      bestWordBaseIdx = 0;
1324      bestWord0 = bestWord1 = NULL;
1325      for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
1326        for (word0 = NULL, word1 = pool->getPool(baseIdx);
1327             word1;
1328             word0 = word1, word1 = word1->next) {
1329          if (word1->base >= minBase &&
1330              word1->base <= maxBase &&
1331              (delta = lastWord->primaryDelta(word1)) >=
1332                minCharSpacing * fontSize) {
1333            if (delta < maxWordSpacing * fontSize &&
1334                (!bestWord1 || word1->primaryCmp(bestWord1) < 0)) {
1335              bestWordBaseIdx = baseIdx;
1336              bestWord0 = word0;
1337              bestWord1 = word1;
1338            }
1339            break;
1340          }
1341        }
1342      }
1343      if (!bestWord1) {
1344        break;
1345      }
1346
1347      // remove it from the pool, and add it to the line
1348      if (bestWord0) {
1349        bestWord0->next = bestWord1->next;
1350      } else {
1351        pool->setPool(bestWordBaseIdx, bestWord1->next);
1352      }
1353      bestWord1->next = NULL;
1354      line->addWord(bestWord1);
1355      lastWord = bestWord1;
1356    }
1357
1358    // add the line
1359    if (curLine && line->cmpYX(curLine) > 0) {
1360      line0 = curLine;
1361      line1 = curLine->next;
1362    } else {
1363      line0 = NULL;
1364      line1 = lines;
1365    }
1366    for (;
1367         line1 && line->cmpYX(line1) > 0;
1368         line0 = line1, line1 = line1->next) ;
1369    if (line0) {
1370      line0->next = line;
1371    } else {
1372      lines = line;
1373    }
1374    line->next = line1;
1375    curLine = line;
1376    line->coalesce(uMap);
1377    charCount += line->len;
1378    ++nLines;
1379  }
1380
1381  // sort lines into xy order for column assignment
1382  lineArray = (TextLine **)gmallocn(nLines, sizeof(TextLine *));
1383  for (line = lines, i = 0; line; line = line->next, ++i) {
1384    lineArray[i] = line;
1385  }
1386  qsort(lineArray, nLines, sizeof(TextLine *), &TextLine::cmpXY);
1387
1388  // column assignment
1389  nColumns = 0;
1390  for (i = 0; i < nLines; ++i) {
1391    line0 = lineArray[i];
1392    col1 = 0;
1393    for (j = 0; j < i; ++j) {
1394      line1 = lineArray[j];
1395      if (line1->primaryDelta(line0) >= 0) {
1396        col2 = line1->col[line1->len] + 1;
1397      } else {
1398        k = 0; // make gcc happy
1399        switch (rot) {
1400        case 0:
1401          for (k = 0;
1402               k < line1->len &&
1403                 line0->xMin >= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1404               ++k) ;
1405          break;
1406        case 1:
1407          for (k = 0;
1408               k < line1->len &&
1409                 line0->yMin >= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1410               ++k) ;
1411          break;
1412        case 2:
1413          for (k = 0;
1414               k < line1->len &&
1415                 line0->xMax <= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1416               ++k) ;
1417          break;
1418        case 3:
1419          for (k = 0;
1420               k < line1->len &&
1421                 line0->yMax <= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1422               ++k) ;
1423          break;
1424        }
1425        col2 = line1->col[k];
1426      }
1427      if (col2 > col1) {
1428        col1 = col2;
1429      }
1430    }
1431    for (k = 0; k <= line0->len; ++k) {
1432      line0->col[k] += col1;
1433    }
1434    if (line0->col[line0->len] > nColumns) {
1435      nColumns = line0->col[line0->len];
1436    }
1437  }
1438  gfree(lineArray);
1439}
1440
1441void TextBlock::updatePriMinMax(TextBlock *blk) {
1442  double newPriMin, newPriMax;
1443  GBool gotPriMin, gotPriMax;
1444
1445  gotPriMin = gotPriMax = gFalse;
1446  newPriMin = newPriMax = 0; // make gcc happy
1447  switch (page->primaryRot) {
1448  case 0:
1449  case 2:
1450    if (blk->yMin < yMax && blk->yMax > yMin) {
1451      if (blk->xMin < xMin) {
1452        newPriMin = blk->xMax;
1453        gotPriMin = gTrue;
1454      }
1455      if (blk->xMax > xMax) {
1456        newPriMax = blk->xMin;
1457        gotPriMax = gTrue;
1458      }
1459    }
1460    break;
1461  case 1:
1462  case 3:
1463    if (blk->xMin < xMax && blk->xMax > xMin) {
1464      if (blk->yMin < yMin) {
1465        newPriMin = blk->yMax;
1466        gotPriMin = gTrue;
1467      }
1468      if (blk->yMax > yMax) {
1469        newPriMax = blk->yMin;
1470        gotPriMax = gTrue;
1471      }
1472    }
1473    break;
1474  }
1475  if (gotPriMin) {
1476    if (newPriMin > xMin) {
1477      newPriMin = xMin;
1478    }
1479    if (newPriMin > priMin) {
1480      priMin = newPriMin;
1481    }
1482  }
1483  if (gotPriMax) {
1484    if (newPriMax < xMax) {
1485      newPriMax = xMax;
1486    }
1487    if (newPriMax < priMax) {
1488      priMax = newPriMax;
1489    }
1490  }
1491}
1492
1493int TextBlock::cmpXYPrimaryRot(const void *p1, const void *p2) {
1494  TextBlock *blk1 = *(TextBlock **)p1;
1495  TextBlock *blk2 = *(TextBlock **)p2;
1496  double cmp;
1497
1498  cmp = 0; // make gcc happy
1499  switch (blk1->page->primaryRot) {
1500  case 0:
1501    if ((cmp = blk1->xMin - blk2->xMin) == 0) {
1502      cmp = blk1->yMin - blk2->yMin;
1503    }
1504    break;
1505  case 1:
1506    if ((cmp = blk1->yMin - blk2->yMin) == 0) {
1507      cmp = blk2->xMax - blk1->xMax;
1508    }
1509    break;
1510  case 2:
1511    if ((cmp = blk2->xMax - blk1->xMax) == 0) {
1512      cmp = blk2->yMin - blk1->yMin;
1513    }
1514    break;
1515  case 3:
1516    if ((cmp = blk2->yMax - blk1->yMax) == 0) {
1517      cmp = blk1->xMax - blk2->xMax;
1518    }
1519    break;
1520  }
1521  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1522}
1523
1524int TextBlock::cmpYXPrimaryRot(const void *p1, const void *p2) {
1525  TextBlock *blk1 = *(TextBlock **)p1;
1526  TextBlock *blk2 = *(TextBlock **)p2;
1527  double cmp;
1528
1529  cmp = 0; // make gcc happy
1530  switch (blk1->page->primaryRot) {
1531  case 0:
1532    if ((cmp = blk1->yMin - blk2->yMin) == 0) {
1533      cmp = blk1->xMin - blk2->xMin;
1534    }
1535    break;
1536  case 1:
1537    if ((cmp = blk2->xMax - blk1->xMax) == 0) {
1538      cmp = blk1->yMin - blk2->yMin;
1539    }
1540    break;
1541  case 2:
1542    if ((cmp = blk2->yMin - blk1->yMin) == 0) {
1543      cmp = blk2->xMax - blk1->xMax;
1544    }
1545    break;
1546  case 3:
1547    if ((cmp = blk1->xMax - blk2->xMax) == 0) {
1548      cmp = blk2->yMax - blk1->yMax;
1549    }
1550    break;
1551  }
1552  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1553}
1554
1555int TextBlock::primaryCmp(TextBlock *blk) {
1556  double cmp;
1557
1558  cmp = 0; // make gcc happy
1559  switch (rot) {
1560  case 0:
1561    cmp = xMin - blk->xMin;
1562    break;
1563  case 1:
1564    cmp = yMin - blk->yMin;
1565    break;
1566  case 2:
1567    cmp = blk->xMax - xMax;
1568    break;
1569  case 3:
1570    cmp = blk->yMax - yMax;
1571    break;
1572  }
1573  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1574}
1575
1576double TextBlock::secondaryDelta(TextBlock *blk) {
1577  double delta;
1578
1579  delta = 0; // make gcc happy
1580  switch (rot) {
1581  case 0:
1582    delta = blk->yMin - yMax;
1583    break;
1584  case 1:
1585    delta = xMin - blk->xMax;
1586    break;
1587  case 2:
1588    delta = yMin - blk->yMax;
1589    break;
1590  case 3:
1591    delta = blk->xMin - xMax;
1592    break;
1593  }
1594  return delta;
1595}
1596
1597GBool TextBlock::isBelow(TextBlock *blk) {
1598  GBool below;
1599
1600  below = gFalse; // make gcc happy
1601  switch (page->primaryRot) {
1602  case 0:
1603    below = xMin >= blk->priMin && xMax <= blk->priMax &&
1604            yMin > blk->yMin;
1605    break;
1606  case 1:
1607    below = yMin >= blk->priMin && yMax <= blk->priMax &&
1608            xMax < blk->xMax;
1609    break;
1610  case 2:
1611    below = xMin >= blk->priMin && xMax <= blk->priMax &&
1612            yMax < blk->yMax;
1613    break;
1614  case 3:
1615    below = yMin >= blk->priMin && yMax <= blk->priMax &&
1616            xMin > blk->xMin;
1617    break;
1618  }
1619
1620  return below;
1621}
1622
[367]1623GBool TextBlock::isBeforeByRule1(TextBlock *blk1) {
1624  GBool before = gFalse;
1625  GBool overlap = gFalse;
1626
1627  switch (this->page->primaryRot) {
1628  case 0:
1629  case 2:
[461]1630    overlap = ((this->ExMin <= blk1->ExMin) &&
1631               (blk1->ExMin <= this->ExMax)) ||
1632      ((blk1->ExMin <= this->ExMin) &&
1633       (this->ExMin <= blk1->ExMax));
[367]1634    break;
1635  case 1:
1636  case 3:
[461]1637    overlap = ((this->EyMin <= blk1->EyMin) &&
1638               (blk1->EyMin <= this->EyMax)) ||
1639      ((blk1->EyMin <= this->EyMin) &&
1640       (this->EyMin <= blk1->EyMax));
[367]1641    break;
1642  }
1643  switch (this->page->primaryRot) {
1644  case 0:
[461]1645    before = overlap && this->EyMin < blk1->EyMin;
[367]1646    break;
1647  case 1:
[461]1648    before = overlap && this->ExMax > blk1->ExMax;
[367]1649    break;
1650  case 2:
[461]1651    before = overlap && this->EyMax > blk1->EyMax;
[367]1652    break;
1653  case 3:
[461]1654    before = overlap && this->ExMin < blk1->ExMin;
[367]1655    break;
1656  }
1657  return before;
1658}
1659
1660GBool TextBlock::isBeforeByRule2(TextBlock *blk1) {
1661  double cmp = 0;
1662  int rotLR = rot;
1663
1664  if (!page->primaryLR) {
1665    rotLR = (rotLR + 2) % 4;
1666  }
1667
1668  switch (rotLR) {
1669  case 0:
[461]1670    cmp = ExMax - blk1->ExMin;
[367]1671    break;
1672  case 1:
[461]1673    cmp = EyMin - blk1->EyMax;
[367]1674    break;
1675  case 2:
[461]1676    cmp = blk1->ExMax - ExMin;
[367]1677    break;
1678  case 3:
[461]1679    cmp = blk1->EyMin - EyMax;
[367]1680    break;
1681  }
1682  return cmp <= 0;
1683}
1684
1685// Sort into reading order by performing a topological sort using the rules
1686// given in "High Performance Document Layout Analysis", T.M. Breuel, 2003.
1687// See http://pubs.iupr.org/#2003-breuel-sdiut
1688// Topological sort is done by depth first search, see
1689// http://en.wikipedia.org/wiki/Topological_sorting
1690int TextBlock::visitDepthFirst(TextBlock *blkList, int pos1,
1691                               TextBlock **sorted, int sortPos,
1692                               GBool* visited) {
1693  int pos2;
1694  TextBlock *blk1, *blk2, *blk3;
1695  GBool before;
1696
1697  if (visited[pos1]) {
1698    return sortPos;
1699  }
1700
1701  blk1 = this;
1702
1703#if 0 // for debugging
1704  printf("visited: %d %.2f..%.2f %.2f..%.2f\n",
[461]1705         sortPos, blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax);
[367]1706#endif
1707  visited[pos1] = gTrue;
1708  pos2 = -1;
1709  for (blk2 = blkList; blk2; blk2 = blk2->next) {
1710    pos2++;
1711    if (visited[pos2]) {
1712      // skip visited nodes
1713      continue;
1714    }
1715    before = gFalse;
[461]1716
1717    // is blk2 before blk1? (for table entries)
1718    if (blk1->tableId >= 0 && blk1->tableId == blk2->tableId) {
1719      if (page->primaryLR) {
1720        if (blk2->xMax <= blk1->xMin &&
1721            blk2->yMin <= blk1->yMax &&
1722            blk2->yMax >= blk1->yMin)
1723          before = gTrue;
1724      } else {
1725        if (blk2->xMin >= blk1->xMax &&
1726            blk2->yMin <= blk1->yMax &&
1727            blk2->yMax >= blk1->yMin)
1728          before = gTrue;
1729      }
1730
1731      if (blk2->yMax <= blk1->yMin)
1732        before = gTrue;
1733    } else {
1734      if (blk2->isBeforeByRule1(blk1)) {
1735        // Rule (1) blk1 and blk2 overlap, and blk2 is above blk1.
1736        before = gTrue;
1737#if 0   // for debugging
1738        printf("rule1: %.2f..%.2f %.2f..%.2f %.2f..%.2f %.2f..%.2f\n",
1739               blk2->ExMin, blk2->ExMax, blk2->EyMin, blk2->EyMax,
1740               blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax);
1741#endif
1742      } else if (blk2->isBeforeByRule2(blk1)) {
1743        // Rule (2) blk2 left of blk1, and no intervening blk3
1744        //          such that blk1 is before blk3 by rule 1,
1745        //          and blk3 is before blk2 by rule 1.
1746        before = gTrue;
1747        for (blk3 = blkList; blk3; blk3 = blk3->next) {
1748          if (blk3 == blk2 || blk3 == blk1) {
1749            continue;
1750          }
1751          if (blk1->isBeforeByRule1(blk3) &&
1752              blk3->isBeforeByRule1(blk2)) {
1753            before = gFalse;
1754            break;
1755          }
1756        }
[367]1757#if 0 // for debugging
[461]1758        if (before) {
1759          printf("rule2: %.2f..%.2f %.2f..%.2f %.2f..%.2f %.2f..%.2f\n",
1760                 blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax,
1761                 blk2->ExMin, blk2->ExMax, blk2->EyMin, blk2->EyMax);
1762        }
[367]1763#endif
1764      }
1765    }
1766    if (before) {
1767      // blk2 is before blk1, so it needs to be visited
1768      // before we can add blk1 to the sorted list.
1769      sortPos = blk2->visitDepthFirst(blkList, pos2, sorted, sortPos, visited);
1770    }
1771  }
1772#if 0 // for debugging
1773  printf("sorted: %d %.2f..%.2f %.2f..%.2f\n",
[461]1774         sortPos, blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax);
[367]1775#endif
1776  sorted[sortPos++] = blk1;
1777  return sortPos;
1778}
1779
[2]1780//------------------------------------------------------------------------
1781// TextFlow
1782//------------------------------------------------------------------------
1783
1784TextFlow::TextFlow(TextPage *pageA, TextBlock *blk) {
1785  page = pageA;
1786  xMin = blk->xMin;
1787  xMax = blk->xMax;
1788  yMin = blk->yMin;
1789  yMax = blk->yMax;
1790  priMin = blk->priMin;
1791  priMax = blk->priMax;
1792  blocks = lastBlk = blk;
1793  next = NULL;
1794}
1795
1796TextFlow::~TextFlow() {
1797  TextBlock *blk;
1798
1799  while (blocks) {
1800    blk = blocks;
1801    blocks = blocks->next;
1802    delete blk;
1803  }
1804}
1805
1806void TextFlow::addBlock(TextBlock *blk) {
1807  if (lastBlk) {
1808    lastBlk->next = blk;
1809  } else {
1810    blocks = blk;
1811  }
1812  lastBlk = blk;
1813  if (blk->xMin < xMin) {
1814    xMin = blk->xMin;
1815  }
1816  if (blk->xMax > xMax) {
1817    xMax = blk->xMax;
1818  }
1819  if (blk->yMin < yMin) {
1820    yMin = blk->yMin;
1821  }
1822  if (blk->yMax > yMax) {
1823    yMax = blk->yMax;
1824  }
1825}
1826
1827GBool TextFlow::blockFits(TextBlock *blk, TextBlock *prevBlk) {
1828  GBool fits;
1829
1830  // lower blocks must use smaller fonts
1831  if (blk->lines->words->fontSize > lastBlk->lines->words->fontSize) {
1832    return gFalse;
1833  }
1834
1835  fits = gFalse; // make gcc happy
1836  switch (page->primaryRot) {
1837  case 0:
1838    fits = blk->xMin >= priMin && blk->xMax <= priMax;
1839    break;
1840  case 1:
1841    fits = blk->yMin >= priMin && blk->yMax <= priMax;
1842    break;
1843  case 2:
1844    fits = blk->xMin >= priMin && blk->xMax <= priMax;
1845    break;
1846  case 3:
1847    fits = blk->yMin >= priMin && blk->yMax <= priMax;
1848    break;
1849  }
1850  return fits;
1851}
1852
1853#if TEXTOUT_WORD_LIST
1854
1855//------------------------------------------------------------------------
1856// TextWordList
1857//------------------------------------------------------------------------
1858
1859TextWordList::TextWordList(TextPage *text, GBool physLayout) {
1860  TextFlow *flow;
1861  TextBlock *blk;
1862  TextLine *line;
1863  TextWord *word;
1864  TextWord **wordArray;
1865  int nWords, i;
1866
1867  words = new GooList();
1868
1869  if (text->rawOrder) {
1870    for (word = text->rawWords; word; word = word->next) {
1871      words->append(word);
1872    }
1873
1874  } else if (physLayout) {
1875    // this is inefficient, but it's also the least useful of these
1876    // three cases
1877    nWords = 0;
1878    for (flow = text->flows; flow; flow = flow->next) {
1879      for (blk = flow->blocks; blk; blk = blk->next) {
1880        for (line = blk->lines; line; line = line->next) {
1881          for (word = line->words; word; word = word->next) {
1882            ++nWords;
1883          }
1884        }
1885      }
1886    }
1887    wordArray = (TextWord **)gmallocn(nWords, sizeof(TextWord *));
1888    i = 0;
1889    for (flow = text->flows; flow; flow = flow->next) {
1890      for (blk = flow->blocks; blk; blk = blk->next) {
1891        for (line = blk->lines; line; line = line->next) {
1892          for (word = line->words; word; word = word->next) {
1893            wordArray[i++] = word;
1894          }
1895        }
1896      }
1897    }
1898    qsort(wordArray, nWords, sizeof(TextWord *), &TextWord::cmpYX);
1899    for (i = 0; i < nWords; ++i) {
1900      words->append(wordArray[i]);
1901    }
1902    gfree(wordArray);
1903
1904  } else {
1905    for (flow = text->flows; flow; flow = flow->next) {
1906      for (blk = flow->blocks; blk; blk = blk->next) {
1907        for (line = blk->lines; line; line = line->next) {
1908          for (word = line->words; word; word = word->next) {
1909            words->append(word);
1910          }
1911        }
1912      }
1913    }
1914  }
1915}
1916
1917TextWordList::~TextWordList() {
1918  delete words;
1919}
1920
1921int TextWordList::getLength() {
1922  return words->getLength();
1923}
1924
1925TextWord *TextWordList::get(int idx) {
1926  if (idx < 0 || idx >= words->getLength()) {
1927    return NULL;
1928  }
1929  return (TextWord *)words->get(idx);
1930}
1931
1932#endif // TEXTOUT_WORD_LIST
1933
1934//------------------------------------------------------------------------
1935// TextPage
1936//------------------------------------------------------------------------
1937
1938TextPage::TextPage(GBool rawOrderA) {
1939  int rot;
1940
[277]1941  refCnt = 1;
[2]1942  rawOrder = rawOrderA;
1943  curWord = NULL;
1944  charPos = 0;
1945  curFont = NULL;
1946  curFontSize = 0;
1947  nest = 0;
1948  nTinyChars = 0;
1949  lastCharOverlap = gFalse;
1950  if (!rawOrder) {
1951    for (rot = 0; rot < 4; ++rot) {
1952      pools[rot] = new TextPool();
1953    }
1954  }
1955  flows = NULL;
1956  blocks = NULL;
1957  rawWords = NULL;
1958  rawLastWord = NULL;
1959  fonts = new GooList();
1960  lastFindXMin = lastFindYMin = 0;
1961  haveLastFind = gFalse;
[250]1962  underlines = new GooList();
1963  links = new GooList();
[2]1964}
1965
1966TextPage::~TextPage() {
1967  int rot;
1968
1969  clear();
1970  if (!rawOrder) {
1971    for (rot = 0; rot < 4; ++rot) {
1972      delete pools[rot];
1973    }
1974  }
1975  delete fonts;
[250]1976  deleteGooList(underlines, TextUnderline);
1977  deleteGooList(links, TextLink);
[2]1978}
1979
[277]1980void TextPage::incRefCnt() {
1981  refCnt++;
1982}
1983
1984void TextPage::decRefCnt() {
1985  if (--refCnt == 0)
1986    delete this;
1987}
1988
[2]1989void TextPage::startPage(GfxState *state) {
1990  clear();
1991  if (state) {
1992    pageWidth = state->getPageWidth();
1993    pageHeight = state->getPageHeight();
1994  } else {
1995    pageWidth = pageHeight = 0;
1996  }
1997}
1998
1999void TextPage::endPage() {
2000  if (curWord) {
2001    endWord();
2002  }
2003}
2004
2005void TextPage::clear() {
2006  int rot;
2007  TextFlow *flow;
2008  TextWord *word;
2009
2010  if (curWord) {
2011    delete curWord;
2012    curWord = NULL;
2013  }
2014  if (rawOrder) {
2015    while (rawWords) {
2016      word = rawWords;
2017      rawWords = rawWords->next;
2018      delete word;
2019    }
2020  } else {
2021    for (rot = 0; rot < 4; ++rot) {
2022      delete pools[rot];
2023    }
2024    while (flows) {
2025      flow = flows;
2026      flows = flows->next;
2027      delete flow;
2028    }
2029    gfree(blocks);
2030  }
2031  deleteGooList(fonts, TextFontInfo);
2032
2033  curWord = NULL;
2034  charPos = 0;
2035  curFont = NULL;
2036  curFontSize = 0;
2037  nest = 0;
2038  nTinyChars = 0;
2039  if (!rawOrder) {
2040    for (rot = 0; rot < 4; ++rot) {
2041      pools[rot] = new TextPool();
2042    }
2043  }
2044  flows = NULL;
2045  blocks = NULL;
2046  rawWords = NULL;
2047  rawLastWord = NULL;
2048  fonts = new GooList();
2049}
2050
2051void TextPage::updateFont(GfxState *state) {
2052  GfxFont *gfxFont;
2053  double *fm;
2054  char *name;
2055  int code, mCode, letterCode, anyCode;
2056  double w;
2057  int i;
2058
2059  // get the font info object
2060  curFont = NULL;
2061  for (i = 0; i < fonts->getLength(); ++i) {
2062    curFont = (TextFontInfo *)fonts->get(i);
2063    if (curFont->matches(state)) {
2064      break;
2065    }
2066    curFont = NULL;
2067  }
2068  if (!curFont) {
2069    curFont = new TextFontInfo(state);
2070    fonts->append(curFont);
2071  }
2072
2073  // adjust the font size
2074  gfxFont = state->getFont();
2075  curFontSize = state->getTransformedFontSize();
2076  if (gfxFont && gfxFont->getType() == fontType3) {
2077    // This is a hack which makes it possible to deal with some Type 3
2078    // fonts.  The problem is that it's impossible to know what the
2079    // base coordinate system used in the font is without actually
2080    // rendering the font.  This code tries to guess by looking at the
2081    // width of the character 'm' (which breaks if the font is a
2082    // subset that doesn't contain 'm').
2083    mCode = letterCode = anyCode = -1;
2084    for (code = 0; code < 256; ++code) {
2085      name = ((Gfx8BitFont *)gfxFont)->getCharName(code);
2086      if (name && name[0] == 'm' && name[1] == '\0') {
2087        mCode = code;
2088      }
2089      if (letterCode < 0 && name && name[1] == '\0' &&
2090          ((name[0] >= 'A' && name[0] <= 'Z') ||
2091           (name[0] >= 'a' && name[0] <= 'z'))) {
2092        letterCode = code;
2093      }
2094      if (anyCode < 0 && name &&
2095          ((Gfx8BitFont *)gfxFont)->getWidth(code) > 0) {
2096        anyCode = code;
2097      }
2098    }
2099    if (mCode >= 0 &&
2100        (w = ((Gfx8BitFont *)gfxFont)->getWidth(mCode)) > 0) {
2101      // 0.6 is a generic average 'm' width -- yes, this is a hack
2102      curFontSize *= w / 0.6;
2103    } else if (letterCode >= 0 &&
2104               (w = ((Gfx8BitFont *)gfxFont)->getWidth(letterCode)) > 0) {
2105      // even more of a hack: 0.5 is a generic letter width
2106      curFontSize *= w / 0.5;
2107    } else if (anyCode >= 0 &&
2108               (w = ((Gfx8BitFont *)gfxFont)->getWidth(anyCode)) > 0) {
2109      // better than nothing: 0.5 is a generic character width
2110      curFontSize *= w / 0.5;
2111    }
2112    fm = gfxFont->getFontMatrix();
2113    if (fm[0] != 0) {
2114      curFontSize *= fabs(fm[3] / fm[0]);
2115    }
2116  }
2117}
2118
2119void TextPage::beginWord(GfxState *state, double x0, double y0) {
[261]2120  GfxFont *gfxFont;
[2]2121  double *fontm;
2122  double m[4], m2[4];
2123  int rot;
2124
2125  // This check is needed because Type 3 characters can contain
2126  // text-drawing operations (when TextPage is being used via
2127  // {X,Win}SplashOutputDev rather than TextOutputDev).
2128  if (curWord) {
2129    ++nest;
2130    return;
2131  }
2132
2133  // compute the rotation
2134  state->getFontTransMat(&m[0], &m[1], &m[2], &m[3]);
[261]2135  gfxFont = state->getFont();
2136  if (gfxFont && gfxFont->getType() == fontType3) {
[2]2137    fontm = state->getFont()->getFontMatrix();
2138    m2[0] = fontm[0] * m[0] + fontm[1] * m[2];
2139    m2[1] = fontm[0] * m[1] + fontm[1] * m[3];
2140    m2[2] = fontm[2] * m[0] + fontm[3] * m[2];
2141    m2[3] = fontm[2] * m[1] + fontm[3] * m[3];
2142    m[0] = m2[0];
2143    m[1] = m2[1];
2144    m[2] = m2[2];
2145    m[3] = m2[3];
2146  }
2147  if (fabs(m[0] * m[3]) > fabs(m[1] * m[2])) {
2148    rot = (m[3] < 0) ? 0 : 2;
2149  } else {
2150    rot = (m[2] > 0) ? 1 : 3;
2151  }
2152
2153  curWord = new TextWord(state, rot, x0, y0, charPos, curFont, curFontSize);
2154}
2155
2156void TextPage::addChar(GfxState *state, double x, double y,
2157                       double dx, double dy,
2158                       CharCode c, int nBytes, Unicode *u, int uLen) {
2159  double x1, y1, w1, h1, dx2, dy2, base, sp, delta;
2160  GBool overlap;
2161  int i;
2162
2163  // subtract char and word spacing from the dx,dy values
2164  sp = state->getCharSpace();
2165  if (c == (CharCode)0x20) {
2166    sp += state->getWordSpace();
2167  }
2168  state->textTransformDelta(sp * state->getHorizScaling(), 0, &dx2, &dy2);
2169  dx -= dx2;
2170  dy -= dy2;
2171  state->transformDelta(dx, dy, &w1, &h1);
2172
[250]2173  // throw away chars that aren't inside the page bounds
2174  // (and also do a sanity check on the character size)
2175  state->transform(x, y, &x1, &y1);
2176  if (x1 + w1 < 0 || x1 > pageWidth ||
2177      y1 + h1 < 0 || y1 > pageHeight ||
2178      w1 > pageWidth || h1 > pageHeight) {
2179    charPos += nBytes;
2180    return;
2181  }
2182
[2]2183  // check the tiny chars limit
2184  if (!globalParams->getTextKeepTinyChars() &&
2185      fabs(w1) < 3 && fabs(h1) < 3) {
2186    if (++nTinyChars > 50000) {
2187      charPos += nBytes;
2188      return;
2189    }
2190  }
2191
2192  // break words at space character
2193  if (uLen == 1 && u[0] == (Unicode)0x20) {
2194    if (curWord) {
[250]2195      ++curWord->charLen;
[2]2196    }
2197    charPos += nBytes;
2198    endWord();
2199    return;
2200  }
2201
2202  // start a new word if:
2203  // (1) this character doesn't fall in the right place relative to
2204  //     the end of the previous word (this places upper and lower
2205  //     constraints on the position deltas along both the primary
2206  //     and secondary axes), or
2207  // (2) this character overlaps the previous one (duplicated text), or
2208  // (3) the previous character was an overlap (we want each duplicated
[250]2209  //     character to be in a word by itself at this stage),
2210  // (4) the font size has changed
[2]2211  if (curWord && curWord->len > 0) {
2212    base = sp = delta = 0; // make gcc happy
2213    switch (curWord->rot) {
2214    case 0:
2215      base = y1;
2216      sp = x1 - curWord->xMax;
2217      delta = x1 - curWord->edge[curWord->len - 1];
2218      break;
2219    case 1:
2220      base = x1;
2221      sp = y1 - curWord->yMax;
2222      delta = y1 - curWord->edge[curWord->len - 1];
2223      break;
2224    case 2:
2225      base = y1;
2226      sp = curWord->xMin - x1;
2227      delta = curWord->edge[curWord->len - 1] - x1;
2228      break;
2229    case 3:
2230      base = x1;
2231      sp = curWord->yMin - y1;
2232      delta = curWord->edge[curWord->len - 1] - y1;
2233      break;
2234    }
2235    overlap = fabs(delta) < dupMaxPriDelta * curWord->fontSize &&
2236              fabs(base - curWord->base) < dupMaxSecDelta * curWord->fontSize;
2237    if (overlap || lastCharOverlap ||
2238        sp < -minDupBreakOverlap * curWord->fontSize ||
2239        sp > minWordBreakSpace * curWord->fontSize ||
[250]2240        fabs(base - curWord->base) > 0.5 ||
2241        curFontSize != curWord->fontSize) {
[2]2242      endWord();
2243    }
2244    lastCharOverlap = overlap;
2245  } else {
2246    lastCharOverlap = gFalse;
2247  }
2248
2249  if (uLen != 0) {
2250    // start a new word if needed
2251    if (!curWord) {
2252      beginWord(state, x, y);
2253    }
2254
[461]2255    // page rotation and/or transform matrices can cause text to be
2256    // drawn in reverse order -- in this case, swap the begin/end
2257    // coordinates and break text into individual chars
2258    if ((curWord->rot == 0 && w1 < 0) ||
2259        (curWord->rot == 1 && h1 < 0) ||
2260        (curWord->rot == 2 && w1 > 0) ||
2261        (curWord->rot == 3 && h1 > 0)) {
2262      endWord();
2263      beginWord(state, x + dx, y + dy);
2264      x1 += w1;
2265      y1 += h1;
2266      w1 = -w1;
2267      h1 = -h1;
2268    }
[2]2269
[461]2270    // add the characters to the current word
[2]2271    w1 /= uLen;
2272    h1 /= uLen;
[461]2273    for (i = 0; i < uLen; ++i) {
[250]2274      if (u[i] >= 0xd800 && u[i] < 0xdc00) { /* surrogate pair */
2275        if (i + 1 < uLen && u[i+1] >= 0xdc00 && u[i+1] < 0xe000) {
2276          /* next code is a low surrogate */
2277          Unicode uu = (((u[i] & 0x3ff) << 10) | (u[i+1] & 0x3ff)) + 0x10000;
2278          i++;
2279          curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, uu);
2280        } else {
2281            /* missing low surrogate
2282             replace it with REPLACEMENT CHARACTER (U+FFFD) */
2283          curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, 0xfffd);
2284        }
2285      } else if (u[i] >= 0xdc00 && u[i] < 0xe000) {
2286          /* invalid low surrogate
2287           replace it with REPLACEMENT CHARACTER (U+FFFD) */
2288        curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, 0xfffd);
2289      } else {
2290        curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, u[i]);
2291      }
[461]2292    }
[2]2293  }
2294  if (curWord) {
2295    curWord->charLen += nBytes;
2296  }
2297  charPos += nBytes;
2298}
2299
2300void TextPage::endWord() {
2301  // This check is needed because Type 3 characters can contain
2302  // text-drawing operations (when TextPage is being used via
2303  // {X,Win}SplashOutputDev rather than TextOutputDev).
2304  if (nest > 0) {
2305    --nest;
2306    return;
2307  }
2308
2309  if (curWord) {
2310    addWord(curWord);
2311    curWord = NULL;
2312  }
2313}
2314
2315void TextPage::addWord(TextWord *word) {
2316  // throw away zero-length words -- they don't have valid xMin/xMax
2317  // values, and they're useless anyway
2318  if (word->len == 0) {
2319    delete word;
2320    return;
2321  }
2322
2323  if (rawOrder) {
2324    if (rawLastWord) {
2325      rawLastWord->next = word;
2326    } else {
2327      rawWords = word;
2328    }
2329    rawLastWord = word;
2330  } else {
2331    pools[word->rot]->addWord(word);
2332  }
2333}
2334
[250]2335void TextPage::addUnderline(double x0, double y0, double x1, double y1) {
2336  underlines->append(new TextUnderline(x0, y0, x1, y1));
2337}
2338
2339void TextPage::addLink(int xMin, int yMin, int xMax, int yMax, Link *link) {
2340  links->append(new TextLink(xMin, yMin, xMax, yMax, link));
2341}
2342
2343void TextPage::coalesce(GBool physLayout, GBool doHTML) {
[2]2344  UnicodeMap *uMap;
2345  TextPool *pool;
2346  TextWord *word0, *word1, *word2;
2347  TextLine *line;
[461]2348  TextBlock *blkList, *blk, *lastBlk, *blk0, *blk1, *blk2;
[2]2349  TextFlow *flow, *lastFlow;
[250]2350  TextUnderline *underline;
2351  TextLink *link;
2352  int rot, poolMinBaseIdx, baseIdx, startBaseIdx, endBaseIdx;
[2]2353  double minBase, maxBase, newMinBase, newMaxBase;
2354  double fontSize, colSpace1, colSpace2, lineSpace, intraLineSpace, blkSpace;
2355  GBool found;
2356  int count[4];
2357  int lrCount;
2358  int col1, col2;
2359  int i, j, n;
2360
2361  if (rawOrder) {
2362    primaryRot = 0;
2363    primaryLR = gTrue;
2364    return;
2365  }
2366
2367  uMap = globalParams->getTextEncoding();
2368  blkList = NULL;
2369  lastBlk = NULL;
2370  nBlocks = 0;
2371  primaryRot = -1;
2372
2373#if 0 // for debugging
2374  printf("*** initial words ***\n");
2375  for (rot = 0; rot < 4; ++rot) {
2376    pool = pools[rot];
2377    for (baseIdx = pool->minBaseIdx; baseIdx <= pool->maxBaseIdx; ++baseIdx) {
2378      for (word0 = pool->getPool(baseIdx); word0; word0 = word0->next) {
[250]2379        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f rot=%d link=%p '",
[2]2380               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
[250]2381               word0->base, word0->fontSize, rot*90, word0->link);
[2]2382        for (i = 0; i < word0->len; ++i) {
2383          fputc(word0->text[i] & 0xff, stdout);
2384        }
2385        printf("'\n");
2386      }
2387    }
2388  }
2389  printf("\n");
2390#endif
2391
[250]2392#if 0 //~ for debugging
2393  for (i = 0; i < underlines->getLength(); ++i) {
2394    underline = (TextUnderline *)underlines->get(i);
2395    printf("underline: x=%g..%g y=%g..%g horiz=%d\n",
2396           underline->x0, underline->x1, underline->y0, underline->y1,
2397           underline->horiz);
2398  }
2399#endif
2400
2401  if (doHTML) {
2402
2403    //----- handle underlining
2404    for (i = 0; i < underlines->getLength(); ++i) {
2405      underline = (TextUnderline *)underlines->get(i);
2406      if (underline->horiz) {
2407        // rot = 0
2408        if (pools[0]->minBaseIdx <= pools[0]->maxBaseIdx) {
2409          startBaseIdx = pools[0]->getBaseIdx(underline->y0 + minUnderlineGap);
2410          endBaseIdx = pools[0]->getBaseIdx(underline->y0 + maxUnderlineGap);
2411          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2412            for (word0 = pools[0]->getPool(j); word0; word0 = word0->next) {
2413              //~ need to check the y value against the word baseline
2414              if (underline->x0 < word0->xMin + underlineSlack &&
2415                  word0->xMax - underlineSlack < underline->x1) {
2416                word0->underlined = gTrue;
2417              }
2418            }
2419          }
2420        }
2421
2422        // rot = 2
2423        if (pools[2]->minBaseIdx <= pools[2]->maxBaseIdx) {
2424          startBaseIdx = pools[2]->getBaseIdx(underline->y0 - maxUnderlineGap);
2425          endBaseIdx = pools[2]->getBaseIdx(underline->y0 - minUnderlineGap);
2426          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2427            for (word0 = pools[2]->getPool(j); word0; word0 = word0->next) {
2428              if (underline->x0 < word0->xMin + underlineSlack &&
2429                  word0->xMax - underlineSlack < underline->x1) {
2430                word0->underlined = gTrue;
2431              }
2432            }
2433          }
2434        }
2435      } else {
2436        // rot = 1
2437        if (pools[1]->minBaseIdx <= pools[1]->maxBaseIdx) {
2438          startBaseIdx = pools[1]->getBaseIdx(underline->x0 - maxUnderlineGap);
2439          endBaseIdx = pools[1]->getBaseIdx(underline->x0 - minUnderlineGap);
2440          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2441            for (word0 = pools[1]->getPool(j); word0; word0 = word0->next) {
2442              if (underline->y0 < word0->yMin + underlineSlack &&
2443                  word0->yMax - underlineSlack < underline->y1) {
2444                word0->underlined = gTrue;
2445              }
2446            }
2447          }
2448        }
2449
2450        // rot = 3
2451        if (pools[3]->minBaseIdx <= pools[3]->maxBaseIdx) {
2452          startBaseIdx = pools[3]->getBaseIdx(underline->x0 + minUnderlineGap);
2453          endBaseIdx = pools[3]->getBaseIdx(underline->x0 + maxUnderlineGap);
2454          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2455            for (word0 = pools[3]->getPool(j); word0; word0 = word0->next) {
2456              if (underline->y0 < word0->yMin + underlineSlack &&
2457                  word0->yMax - underlineSlack < underline->y1) {
2458                word0->underlined = gTrue;
2459              }
2460            }
2461          }
2462        }
2463      }
2464    }
2465
2466    //----- handle links
2467    for (i = 0; i < links->getLength(); ++i) {
2468      link = (TextLink *)links->get(i);
2469
2470      // rot = 0
2471      if (pools[0]->minBaseIdx <= pools[0]->maxBaseIdx) {
2472        startBaseIdx = pools[0]->getBaseIdx(link->yMin);
2473        endBaseIdx = pools[0]->getBaseIdx(link->yMax);
2474        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2475          for (word0 = pools[0]->getPool(j); word0; word0 = word0->next) {
2476            if (link->xMin < word0->xMin + hyperlinkSlack &&
2477                word0->xMax - hyperlinkSlack < link->xMax &&
2478                link->yMin < word0->yMin + hyperlinkSlack &&
2479                word0->yMax - hyperlinkSlack < link->yMax) {
2480              word0->link = link->link;
2481            }
2482          }
2483        }
2484      }
2485
2486      // rot = 2
2487      if (pools[2]->minBaseIdx <= pools[2]->maxBaseIdx) {
2488        startBaseIdx = pools[2]->getBaseIdx(link->yMin);
2489        endBaseIdx = pools[2]->getBaseIdx(link->yMax);
2490        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2491          for (word0 = pools[2]->getPool(j); word0; word0 = word0->next) {
2492            if (link->xMin < word0->xMin + hyperlinkSlack &&
2493                word0->xMax - hyperlinkSlack < link->xMax &&
2494                link->yMin < word0->yMin + hyperlinkSlack &&
2495                word0->yMax - hyperlinkSlack < link->yMax) {
2496              word0->link = link->link;
2497            }
2498          }
2499        }
2500      }
2501
2502      // rot = 1
2503      if (pools[1]->minBaseIdx <= pools[1]->maxBaseIdx) {
2504        startBaseIdx = pools[1]->getBaseIdx(link->xMin);
2505        endBaseIdx = pools[1]->getBaseIdx(link->xMax);
2506        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2507          for (word0 = pools[1]->getPool(j); word0; word0 = word0->next) {
2508            if (link->yMin < word0->yMin + hyperlinkSlack &&
2509                word0->yMax - hyperlinkSlack < link->yMax &&
2510                link->xMin < word0->xMin + hyperlinkSlack &&
2511                word0->xMax - hyperlinkSlack < link->xMax) {
2512              word0->link = link->link;
2513            }
2514          }
2515        }
2516      }
2517
2518      // rot = 3
2519      if (pools[3]->minBaseIdx <= pools[3]->maxBaseIdx) {
2520        startBaseIdx = pools[3]->getBaseIdx(link->xMin);
2521        endBaseIdx = pools[3]->getBaseIdx(link->xMax);
2522        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2523          for (word0 = pools[3]->getPool(j); word0; word0 = word0->next) {
2524            if (link->yMin < word0->yMin + hyperlinkSlack &&
2525                word0->yMax - hyperlinkSlack < link->yMax &&
2526                link->xMin < word0->xMin + hyperlinkSlack &&
2527                word0->xMax - hyperlinkSlack < link->xMax) {
2528              word0->link = link->link;
2529            }
2530          }
2531        }
2532      }
2533    }
2534  }
2535
[2]2536  //----- assemble the blocks
2537
2538  //~ add an outer loop for writing mode (vertical text)
2539
2540  // build blocks for each rotation value
2541  for (rot = 0; rot < 4; ++rot) {
2542    pool = pools[rot];
2543    poolMinBaseIdx = pool->minBaseIdx;
2544    count[rot] = 0;
2545
2546    // add blocks until no more words are left
2547    while (1) {
2548
2549      // find the first non-empty line in the pool
2550      for (;
2551           poolMinBaseIdx <= pool->maxBaseIdx &&
2552             !pool->getPool(poolMinBaseIdx);
2553           ++poolMinBaseIdx) ;
2554      if (poolMinBaseIdx > pool->maxBaseIdx) {
2555        break;
2556      }
2557
2558      // look for the left-most word in the first four lines of the
2559      // pool -- this avoids starting with a superscript word
2560      startBaseIdx = poolMinBaseIdx;
2561      for (baseIdx = poolMinBaseIdx + 1;
2562           baseIdx < poolMinBaseIdx + 4 && baseIdx <= pool->maxBaseIdx;
2563           ++baseIdx) {
2564        if (!pool->getPool(baseIdx)) {
2565          continue;
2566        }
2567        if (pool->getPool(baseIdx)->primaryCmp(pool->getPool(startBaseIdx))
2568            < 0) {
2569          startBaseIdx = baseIdx;
2570        }
2571      }
2572
2573      // create a new block
2574      word0 = pool->getPool(startBaseIdx);
2575      pool->setPool(startBaseIdx, word0->next);
2576      word0->next = NULL;
2577      blk = new TextBlock(this, rot);
2578      blk->addWord(word0);
2579
2580      fontSize = word0->fontSize;
2581      minBase = maxBase = word0->base;
2582      colSpace1 = minColSpacing1 * fontSize;
2583      colSpace2 = minColSpacing2 * fontSize;
2584      lineSpace = maxLineSpacingDelta * fontSize;
2585      intraLineSpace = maxIntraLineDelta * fontSize;
2586
2587      // add words to the block
2588      do {
2589        found = gFalse;
2590
2591        // look for words on the line above the current top edge of
2592        // the block
2593        newMinBase = minBase;
2594        for (baseIdx = pool->getBaseIdx(minBase);
2595             baseIdx >= pool->getBaseIdx(minBase - lineSpace);
2596             --baseIdx) {
2597          word0 = NULL;
2598          word1 = pool->getPool(baseIdx);
2599          while (word1) {
2600            if (word1->base < minBase &&
2601                word1->base >= minBase - lineSpace &&
2602                ((rot == 0 || rot == 2)
2603                 ? (word1->xMin < blk->xMax && word1->xMax > blk->xMin)
2604                 : (word1->yMin < blk->yMax && word1->yMax > blk->yMin)) &&
2605                fabs(word1->fontSize - fontSize) <
2606                  maxBlockFontSizeDelta1 * fontSize) {
2607              word2 = word1;
2608              if (word0) {
2609                word0->next = word1->next;
2610              } else {
2611                pool->setPool(baseIdx, word1->next);
2612              }
2613              word1 = word1->next;
2614              word2->next = NULL;
2615              blk->addWord(word2);
2616              found = gTrue;
2617              newMinBase = word2->base;
2618            } else {
2619              word0 = word1;
2620              word1 = word1->next;
2621            }
2622          }
2623        }
2624        minBase = newMinBase;
2625
2626        // look for words on the line below the current bottom edge of
2627        // the block
2628        newMaxBase = maxBase;
2629        for (baseIdx = pool->getBaseIdx(maxBase);
2630             baseIdx <= pool->getBaseIdx(maxBase + lineSpace);
2631             ++baseIdx) {
2632          word0 = NULL;
2633          word1 = pool->getPool(baseIdx);
2634          while (word1) {
2635            if (word1->base > maxBase &&
2636                word1->base <= maxBase + lineSpace &&
2637                ((rot == 0 || rot == 2)
2638                 ? (word1->xMin < blk->xMax && word1->xMax > blk->xMin)
2639                 : (word1->yMin < blk->yMax && word1->yMax > blk->yMin)) &&
2640                fabs(word1->fontSize - fontSize) <
2641                  maxBlockFontSizeDelta1 * fontSize) {
2642              word2 = word1;
2643              if (word0) {
2644                word0->next = word1->next;
2645              } else {
2646                pool->setPool(baseIdx, word1->next);
2647              }
2648              word1 = word1->next;
2649              word2->next = NULL;
2650              blk->addWord(word2);
2651              found = gTrue;
2652              newMaxBase = word2->base;
2653            } else {
2654              word0 = word1;
2655              word1 = word1->next;
2656            }
2657          }
2658        }
2659        maxBase = newMaxBase;
2660
2661        // look for words that are on lines already in the block, and
2662        // that overlap the block horizontally
2663        for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2664             baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2665             ++baseIdx) {
2666          word0 = NULL;
2667          word1 = pool->getPool(baseIdx);
2668          while (word1) {
2669            if (word1->base >= minBase - intraLineSpace &&
2670                word1->base <= maxBase + intraLineSpace &&
2671                ((rot == 0 || rot == 2)
2672                 ? (word1->xMin < blk->xMax + colSpace1 &&
2673                    word1->xMax > blk->xMin - colSpace1)
2674                 : (word1->yMin < blk->yMax + colSpace1 &&
2675                    word1->yMax > blk->yMin - colSpace1)) &&
2676                fabs(word1->fontSize - fontSize) <
2677                  maxBlockFontSizeDelta2 * fontSize) {
2678              word2 = word1;
2679              if (word0) {
2680                word0->next = word1->next;
2681              } else {
2682                pool->setPool(baseIdx, word1->next);
2683              }
2684              word1 = word1->next;
2685              word2->next = NULL;
2686              blk->addWord(word2);
2687              found = gTrue;
2688            } else {
2689              word0 = word1;
2690              word1 = word1->next;
2691            }
2692          }
2693        }
2694
2695        // only check for outlying words (the next two chunks of code)
2696        // if we didn't find anything else
2697        if (found) {
2698          continue;
2699        }
2700
2701        // scan down the left side of the block, looking for words
2702        // that are near (but not overlapping) the block; if there are
2703        // three or fewer, add them to the block
2704        n = 0;
2705        for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2706             baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2707             ++baseIdx) {
2708          word1 = pool->getPool(baseIdx);
2709          while (word1) {
2710            if (word1->base >= minBase - intraLineSpace &&
2711                word1->base <= maxBase + intraLineSpace &&
2712                ((rot == 0 || rot == 2)
2713                 ? (word1->xMax <= blk->xMin &&
2714                    word1->xMax > blk->xMin - colSpace2)
2715                 : (word1->yMax <= blk->yMin &&
2716                    word1->yMax > blk->yMin - colSpace2)) &&
2717                fabs(word1->fontSize - fontSize) <
2718                  maxBlockFontSizeDelta3 * fontSize) {
2719              ++n;
2720              break;
2721            }
2722            word1 = word1->next;
2723          }
2724        }
2725        if (n > 0 && n <= 3) {
2726          for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2727               baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2728               ++baseIdx) {
2729            word0 = NULL;
2730            word1 = pool->getPool(baseIdx);
2731            while (word1) {
2732              if (word1->base >= minBase - intraLineSpace &&
2733                  word1->base <= maxBase + intraLineSpace &&
2734                  ((rot == 0 || rot == 2)
2735                   ? (word1->xMax <= blk->xMin &&
2736                      word1->xMax > blk->xMin - colSpace2)
2737                   : (word1->yMax <= blk->yMin &&
2738                      word1->yMax > blk->yMin - colSpace2)) &&
2739                  fabs(word1->fontSize - fontSize) <
2740                    maxBlockFontSizeDelta3 * fontSize) {
2741                word2 = word1;
2742                if (word0) {
2743                  word0->next = word1->next;
2744                } else {
2745                  pool->setPool(baseIdx, word1->next);
2746                }
2747                word1 = word1->next;
2748                word2->next = NULL;
2749                blk->addWord(word2);
2750                if (word2->base < minBase) {
2751                  minBase = word2->base;
2752                } else if (word2->base > maxBase) {
2753                  maxBase = word2->base;
2754                }
2755                found = gTrue;
2756                break;
2757              } else {
2758                word0 = word1;
2759                word1 = word1->next;
2760              }
2761            }
2762          }
2763        }
2764
2765        // scan down the right side of the block, looking for words
2766        // that are near (but not overlapping) the block; if there are
2767        // three or fewer, add them to the block
2768        n = 0;
2769        for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2770             baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2771             ++baseIdx) {
2772          word1 = pool->getPool(baseIdx);
2773          while (word1) {
2774            if (word1->base >= minBase - intraLineSpace &&
2775                word1->base <= maxBase + intraLineSpace &&
2776                ((rot == 0 || rot == 2)
2777                 ? (word1->xMin >= blk->xMax &&
2778                    word1->xMin < blk->xMax + colSpace2)
2779                 : (word1->yMin >= blk->yMax &&
2780                    word1->yMin < blk->yMax + colSpace2)) &&
2781                fabs(word1->fontSize - fontSize) <
2782                  maxBlockFontSizeDelta3 * fontSize) {
2783              ++n;
2784              break;
2785            }
2786            word1 = word1->next;
2787          }
2788        }
2789        if (n > 0 && n <= 3) {
2790          for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2791               baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2792               ++baseIdx) {
2793            word0 = NULL;
2794            word1 = pool->getPool(baseIdx);
2795            while (word1) {
2796              if (word1->base >= minBase - intraLineSpace &&
2797                  word1->base <= maxBase + intraLineSpace &&
2798                  ((rot == 0 || rot == 2)
2799                   ? (word1->xMin >= blk->xMax &&
2800                      word1->xMin < blk->xMax + colSpace2)
2801                   : (word1->yMin >= blk->yMax &&
2802                      word1->yMin < blk->yMax + colSpace2)) &&
2803                  fabs(word1->fontSize - fontSize) <
2804                    maxBlockFontSizeDelta3 * fontSize) {
2805                word2 = word1;
2806                if (word0) {
2807                  word0->next = word1->next;
2808                } else {
2809                  pool->setPool(baseIdx, word1->next);
2810                }
2811                word1 = word1->next;
2812                word2->next = NULL;
2813                blk->addWord(word2);
2814                if (word2->base < minBase) {
2815                  minBase = word2->base;
2816                } else if (word2->base > maxBase) {
2817                  maxBase = word2->base;
2818                }
2819                found = gTrue;
2820                break;
2821              } else {
2822                word0 = word1;
2823                word1 = word1->next;
2824              }
2825            }
2826          }
2827        }
2828
2829      } while (found);
2830
2831      //~ need to compute the primary writing mode (horiz/vert) in
2832      //~ addition to primary rotation
2833
2834      // coalesce the block, and add it to the list
2835      blk->coalesce(uMap);
2836      if (lastBlk) {
2837        lastBlk->next = blk;
2838      } else {
2839        blkList = blk;
2840      }
2841      lastBlk = blk;
2842      count[rot] += blk->charCount;
2843      if (primaryRot < 0 || count[rot] > count[primaryRot]) {
2844        primaryRot = rot;
2845      }
2846      ++nBlocks;
2847    }
2848  }
2849
[367]2850#if 0 // for debugging
[2]2851  printf("*** rotation ***\n");
2852  for (rot = 0; rot < 4; ++rot) {
2853    printf("  %d: %6d\n", rot, count[rot]);
2854  }
2855  printf("  primary rot = %d\n", primaryRot);
2856  printf("\n");
2857#endif
2858
2859#if 0 // for debugging
2860  printf("*** blocks ***\n");
2861  for (blk = blkList; blk; blk = blk->next) {
2862    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f\n",
2863           blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax);
2864    for (line = blk->lines; line; line = line->next) {
2865      printf("  line: x=%.2f..%.2f y=%.2f..%.2f base=%.2f\n",
2866             line->xMin, line->xMax, line->yMin, line->yMax, line->base);
2867      for (word0 = line->words; word0; word0 = word0->next) {
2868        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2869               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2870               word0->base, word0->fontSize, word0->spaceAfter);
2871        for (i = 0; i < word0->len; ++i) {
2872          fputc(word0->text[i] & 0xff, stdout);
2873        }
2874        printf("'\n");
2875      }
2876    }
2877  }
2878  printf("\n");
2879#endif
2880
2881  // determine the primary direction
2882  lrCount = 0;
2883  for (blk = blkList; blk; blk = blk->next) {
2884    for (line = blk->lines; line; line = line->next) {
2885      for (word0 = line->words; word0; word0 = word0->next) {
2886        for (i = 0; i < word0->len; ++i) {
2887          if (unicodeTypeL(word0->text[i])) {
2888            ++lrCount;
2889          } else if (unicodeTypeR(word0->text[i])) {
2890            --lrCount;
2891          }
2892        }
2893      }
2894    }
2895  }
2896  primaryLR = lrCount >= 0;
2897
2898#if 0 // for debugging
2899  printf("*** direction ***\n");
2900  printf("lrCount = %d\n", lrCount);
2901  printf("primaryLR = %d\n", primaryLR);
2902#endif
2903
2904  //----- column assignment
2905
2906  // sort blocks into xy order for column assignment
[27]2907  if (blocks)
2908    gfree (blocks);
[2]2909  blocks = (TextBlock **)gmallocn(nBlocks, sizeof(TextBlock *));
2910  for (blk = blkList, i = 0; blk; blk = blk->next, ++i) {
2911    blocks[i] = blk;
2912  }
2913  qsort(blocks, nBlocks, sizeof(TextBlock *), &TextBlock::cmpXYPrimaryRot);
2914
2915  // column assignment
2916  for (i = 0; i < nBlocks; ++i) {
2917    blk0 = blocks[i];
2918    col1 = 0;
2919    for (j = 0; j < i; ++j) {
2920      blk1 = blocks[j];
2921      col2 = 0; // make gcc happy
2922      switch (primaryRot) {
2923      case 0:
2924        if (blk0->xMin > blk1->xMax) {
2925          col2 = blk1->col + blk1->nColumns + 3;
2926        } else if (blk1->xMax == blk1->xMin) {
2927          col2 = blk1->col;
2928        } else {
2929          col2 = blk1->col + (int)(((blk0->xMin - blk1->xMin) /
2930                                    (blk1->xMax - blk1->xMin)) *
2931                                   blk1->nColumns);
2932        }
2933        break;
2934      case 1:
2935        if (blk0->yMin > blk1->yMax) {
2936          col2 = blk1->col + blk1->nColumns + 3;
2937        } else if (blk1->yMax == blk1->yMin) {
2938          col2 = blk1->col;
2939        } else {
2940          col2 = blk1->col + (int)(((blk0->yMin - blk1->yMin) /
2941                                    (blk1->yMax - blk1->yMin)) *
2942                                   blk1->nColumns);
2943        }
2944        break;
2945      case 2:
2946        if (blk0->xMax < blk1->xMin) {
2947          col2 = blk1->col + blk1->nColumns + 3;
2948        } else if (blk1->xMin == blk1->xMax) {
2949          col2 = blk1->col;
2950        } else {
2951          col2 = blk1->col + (int)(((blk0->xMax - blk1->xMax) /
2952                                    (blk1->xMin - blk1->xMax)) *
2953                                   blk1->nColumns);
2954        }
2955        break;
2956      case 3:
2957        if (blk0->yMax < blk1->yMin) {
2958          col2 = blk1->col + blk1->nColumns + 3;
2959        } else if (blk1->yMin == blk1->yMax) {
2960          col2 = blk1->col;
2961        } else {
2962          col2 = blk1->col + (int)(((blk0->yMax - blk1->yMax) /
2963                                    (blk1->yMin - blk1->yMax)) *
2964                                   blk1->nColumns);
2965        }
2966        break;
2967      }
2968      if (col2 > col1) {
2969        col1 = col2;
2970      }
2971    }
2972    blk0->col = col1;
2973    for (line = blk0->lines; line; line = line->next) {
2974      for (j = 0; j <= line->len; ++j) {
2975        line->col[j] += col1;
2976      }
2977    }
2978  }
2979
2980#if 0 // for debugging
2981  printf("*** blocks, after column assignment ***\n");
2982  for (blk = blkList; blk; blk = blk->next) {
2983    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f col=%d nCols=%d\n",
2984           blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax, blk->col,
2985           blk->nColumns);
2986    for (line = blk->lines; line; line = line->next) {
2987      printf("  line:\n");
2988      for (word0 = line->words; word0; word0 = word0->next) {
2989        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2990               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2991               word0->base, word0->fontSize, word0->spaceAfter);
2992        for (i = 0; i < word0->len; ++i) {
2993          fputc(word0->text[i] & 0xff, stdout);
2994        }
2995        printf("'\n");
2996      }
2997    }
2998  }
2999  printf("\n");
3000#endif
3001
3002  //----- reading order sort
3003
3004  // compute space on left and right sides of each block
3005  for (i = 0; i < nBlocks; ++i) {
3006    blk0 = blocks[i];
3007    for (j = 0; j < nBlocks; ++j) {
3008      blk1 = blocks[j];
3009      if (blk1 != blk0) {
3010        blk0->updatePriMinMax(blk1);
3011      }
3012    }
3013  }
3014
3015#if 0 // for debugging
[367]3016  printf("PAGE\n");
3017#endif
3018
3019  int sortPos = 0;
3020  GBool *visited = (GBool *)gmallocn(nBlocks, sizeof(GBool));
3021  for (i = 0; i < nBlocks; i++) {
3022    visited[i] = gFalse;
3023  }
[461]3024
3025  double bxMin0, byMin0, bxMin1, byMin1;
3026  int numTables = 0;
3027  int tableId = -1;
3028  int correspondenceX, correspondenceY;
3029  double xCentre1, yCentre1, xCentre2, yCentre2;
3030  double xCentre3, yCentre3, xCentre4, yCentre4;
3031  double deltaX, deltaY;
3032  TextBlock *fblk2 = NULL, *fblk3 = NULL, *fblk4 = NULL;
3033
3034  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3035    blk1->ExMin = blk1->xMin;
3036    blk1->ExMax = blk1->xMax;
3037    blk1->EyMin = blk1->yMin;
3038    blk1->EyMax = blk1->yMax;
3039
3040    bxMin0 = DBL_MAX;
3041    byMin0 = DBL_MAX;
3042    bxMin1 = DBL_MAX;
3043    byMin1 = DBL_MAX;
3044
3045    fblk2 = NULL;
3046    fblk3 = NULL;
3047    fblk4 = NULL;
3048
3049    /*  find fblk2, fblk3 and fblk4 so that
3050     *  fblk2 is on the right of blk1 and overlap with blk1 in y axis
3051     *  fblk3 is under blk1 and overlap with blk1 in x axis
3052     *  fblk4 is under blk1 and on the right of blk1
3053     *  and they are closest to blk1
3054     */
3055    for (blk2 = blkList; blk2; blk2 = blk2->next) {
3056      if (blk2 != blk1) {
3057        if (blk2->yMin <= blk1->yMax &&
3058            blk2->yMax >= blk1->yMin &&
3059            blk2->xMin > blk1->xMax &&
3060            blk2->xMin < bxMin0) {
3061          bxMin0 = blk2->xMin;
3062          fblk2 = blk2;
3063        } else if (blk2->xMin <= blk1->xMax &&
3064                   blk2->xMax >= blk1->xMin &&
3065                   blk2->yMin > blk1->yMax &&
3066                   blk2->yMin < byMin0) {
3067          byMin0 = blk2->yMin;
3068          fblk3 = blk2;
3069        } else if (blk2->xMin > blk1->xMax &&
3070                   blk2->xMin < bxMin1 &&
3071                   blk2->yMin > blk1->yMax &&
3072                   blk2->yMin < byMin1) {
3073          bxMin1 = blk2->xMin;
3074          byMin1 = blk2->yMin;
3075          fblk4 = blk2;
3076        }
3077      }
3078    }
3079
3080    /*  fblk4 can not overlap with fblk3 in x and with fblk2 in y
3081     *  fblk2 can not overlap with fblk3 in x and y
3082     *  fblk4 has to overlap with fblk3 in y and with fblk2 in x
3083     */
3084    if (fblk2 != NULL &&
3085        fblk3 != NULL &&
3086        fblk4 != NULL) {
3087      if (((fblk3->xMin <= fblk4->xMax && fblk3->xMax >= fblk4->xMin) ||
3088           (fblk2->yMin <= fblk4->yMax && fblk2->yMax >= fblk4->yMin) ||
3089           (fblk2->xMin <= fblk3->xMax && fblk2->xMax >= fblk3->xMin) ||
3090           (fblk2->yMin <= fblk3->yMax && fblk2->yMax >= fblk3->yMin)) ||
3091          !(fblk4->xMin <= fblk2->xMax && fblk4->xMax >= fblk2->xMin &&
3092            fblk4->yMin <= fblk3->yMax && fblk4->yMax >= fblk3->yMin)) {
3093        fblk2 = NULL;
3094        fblk3 = NULL;
3095        fblk4 = NULL;
3096      }
3097    }
3098
3099    // if we found any then look whether they form a table
3100    if (fblk2 != NULL &&
3101        fblk3 != NULL &&
3102        fblk4 != NULL) {
3103      tableId = -1;
3104      correspondenceX = 0;
3105      correspondenceY = 0;
3106      deltaX = 0.0;
3107      deltaY = 0.0;
3108
3109      if (blk1->lines && blk1->lines->words)
3110        deltaX = blk1->lines->words->getFontSize();
3111      if (fblk2->lines && fblk2->lines->words)
3112        deltaX = deltaX < fblk2->lines->words->getFontSize() ?
3113                   deltaX : fblk2->lines->words->getFontSize();
3114      if (fblk3->lines && fblk3->lines->words)
3115        deltaX = deltaX < fblk3->lines->words->getFontSize() ?
3116                   deltaX : fblk3->lines->words->getFontSize();
3117      if (fblk4->lines && fblk4->lines->words)
3118        deltaX = deltaX < fblk4->lines->words->getFontSize() ?
3119                   deltaX : fblk4->lines->words->getFontSize();
3120
3121      deltaY = deltaX;
3122
3123      deltaX *= minColSpacing1;
3124      deltaY *= maxIntraLineDelta;
3125
3126      xCentre1 = (blk1->xMax + blk1->xMin) / 2.0;
3127      yCentre1 = (blk1->yMax + blk1->yMin) / 2.0;
3128      xCentre2 = (fblk2->xMax + fblk2->xMin) / 2.0;
3129      yCentre2 = (fblk2->yMax + fblk2->yMin) / 2.0;
3130      xCentre3 = (fblk3->xMax + fblk3->xMin) / 2.0;
3131      yCentre3 = (fblk3->yMax + fblk3->yMin) / 2.0;
3132      xCentre4 = (fblk4->xMax + fblk4->xMin) / 2.0;
3133      yCentre4 = (fblk4->yMax + fblk4->yMin) / 2.0;
3134
3135      // are blocks centrally aligned in x ?
3136      if (fabs (xCentre1 - xCentre3) <= deltaX &&
3137          fabs (xCentre2 - xCentre4) <= deltaX)
3138        correspondenceX++;
3139
3140      // are blocks centrally aligned in y ?
3141      if (fabs (yCentre1 - yCentre2) <= deltaY &&
3142          fabs (yCentre3 - yCentre4) <= deltaY)
3143        correspondenceY++;
3144
3145      // are blocks aligned to the left ?
3146      if (fabs (blk1->xMin - fblk3->xMin) <= deltaX &&
3147          fabs (fblk2->xMin - fblk4->xMin) <= deltaX)
3148        correspondenceX++;
3149
3150      // are blocks aligned to the right ?
3151      if (fabs (blk1->xMax - fblk3->xMax) <= deltaX &&
3152          fabs (fblk2->xMax - fblk4->xMax) <= deltaX)
3153        correspondenceX++;
3154
3155      // are blocks aligned to the top ?
3156      if (fabs (blk1->yMin - fblk2->yMin) <= deltaY &&
3157          fabs (fblk3->yMin - fblk4->yMin) <= deltaY)
3158        correspondenceY++;
3159
3160      // are blocks aligned to the bottom ?
3161      if (fabs (blk1->yMax - fblk2->yMax) <= deltaY &&
3162          fabs (fblk3->yMax - fblk4->yMax) <= deltaY)
3163        correspondenceY++;
3164
3165      // are blocks aligned in x and y ?
3166      if (correspondenceX > 0 &&
3167          correspondenceY > 0) {
3168
3169        // find maximal tableId
3170        tableId = tableId < fblk4->tableId ? fblk4->tableId : tableId;
3171        tableId = tableId < fblk3->tableId ? fblk3->tableId : tableId;
3172        tableId = tableId < fblk2->tableId ? fblk2->tableId : tableId;
3173        tableId = tableId < blk1->tableId ? blk1->tableId : tableId;
3174
3175        // if the tableId is -1, then we found new table
3176        if (tableId < 0) {
3177          tableId = numTables;
3178          numTables++;
3179        }
3180
3181        blk1->tableId = tableId;
3182        fblk2->tableId = tableId;
3183        fblk3->tableId = tableId;
3184        fblk4->tableId = tableId;
3185      }
3186    }
3187  }
3188
3189  /*  set extended bounding boxes of all table entries
3190   *  so that they contain whole table
3191   *  (we need to process whole table size when comparing it
3192   *   with regular text blocks)
3193   */
3194  PDFRectangle *envelopes = new PDFRectangle [numTables];
3195  TextBlock **ending_blocks = new TextBlock* [numTables];
3196
3197  for (i = 0; i < numTables; i++) {
3198    envelopes[i].x1 = DBL_MAX;
3199    envelopes[i].x2 = DBL_MIN;
3200    envelopes[i].y1 = DBL_MAX;
3201    envelopes[i].y2 = DBL_MIN;
3202  }
3203
3204  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3205    if (blk1->tableId >= 0) {
3206      if (blk1->ExMin < envelopes[blk1->tableId].x1) {
3207        envelopes[blk1->tableId].x1 = blk1->ExMin;
3208        if (!blk1->page->primaryLR)
3209          ending_blocks[blk1->tableId] = blk1;
3210      }
3211
3212      if (blk1->ExMax > envelopes[blk1->tableId].x2) {
3213        envelopes[blk1->tableId].x2 = blk1->ExMax;
3214        if (blk1->page->primaryLR)
3215          ending_blocks[blk1->tableId] = blk1;
3216      }
3217
3218      envelopes[blk1->tableId].y1 = blk1->EyMin < envelopes[blk1->tableId].y1 ?
3219                                      blk1->EyMin : envelopes[blk1->tableId].y1;
3220      envelopes[blk1->tableId].y2 = blk1->EyMax > envelopes[blk1->tableId].y2 ?
3221                                      blk1->EyMax : envelopes[blk1->tableId].y2;
3222    }
3223  }
3224
3225  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3226    if (blk1->tableId >= 0 &&
3227        blk1->xMin <= ending_blocks[blk1->tableId]->xMax &&
3228        blk1->xMax >= ending_blocks[blk1->tableId]->xMin) {
3229      blk1->tableEnd = gTrue;
3230    }
3231  }
3232
3233  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3234    if (blk1->tableId >= 0) {
3235      blk1->ExMin = envelopes[blk1->tableId].x1;
3236      blk1->ExMax = envelopes[blk1->tableId].x2;
3237      blk1->EyMin = envelopes[blk1->tableId].y1;
3238      blk1->EyMax = envelopes[blk1->tableId].y2;
3239    }
3240  }
3241  delete[] envelopes;
3242  delete[] ending_blocks;
3243
3244
3245  /*  set extended bounding boxes of all other blocks
3246   *  so that they extend in x without hitting neighbours
3247   */
3248  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3249    if (!blk1->tableId >= 0) {
3250      double xMax = DBL_MAX;
3251      double xMin = DBL_MIN;
3252
3253      for (blk2 = blkList; blk2; blk2 = blk2->next) {
3254        if (blk2 == blk1)
3255           continue;
3256
3257        if (blk1->yMin <= blk2->yMax && blk1->yMax >= blk2->yMin) {
3258          if (blk2->xMin < xMax && blk2->xMin > blk1->xMax)
3259            xMax = blk2->xMin;
3260
3261          if (blk2->xMax > xMin && blk2->xMax < blk1->xMin)
3262            xMin = blk2->xMax;
3263        }
3264      }
3265
3266      for (blk2 = blkList; blk2; blk2 = blk2->next) {
3267        if (blk2 == blk1)
3268           continue;
3269
3270        if (blk2->xMax > blk1->ExMax &&
3271            blk2->xMax <= xMax &&
3272            blk2->yMin >= blk1->yMax) {
3273          blk1->ExMax = blk2->xMax;
3274        }
3275
3276        if (blk2->xMin < blk1->ExMin &&
3277            blk2->xMin >= xMin &&
3278            blk2->yMin >= blk1->yMax)
3279          blk1->ExMin = blk2->xMin;
3280      }
3281    }
3282  }
3283
[367]3284  i = -1;
3285  for (blk1 = blkList; blk1; blk1 = blk1->next) {
3286    i++;
3287    sortPos = blk1->visitDepthFirst(blkList, i, blocks, sortPos, visited);
3288  }
3289  if (visited) {
3290    gfree(visited);
3291  }
3292
3293#if 0 // for debugging
3294  printf("*** blocks, after ro sort ***\n");
[2]3295  for (i = 0; i < nBlocks; ++i) {
3296    blk = blocks[i];
3297    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f space=%.2f..%.2f\n",
3298           blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax,
3299           blk->priMin, blk->priMax);
3300    for (line = blk->lines; line; line = line->next) {
3301      printf("  line:\n");
3302      for (word0 = line->words; word0; word0 = word0->next) {
3303        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
3304               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
3305               word0->base, word0->fontSize, word0->spaceAfter);
3306        for (j = 0; j < word0->len; ++j) {
3307          fputc(word0->text[j] & 0xff, stdout);
3308        }
3309        printf("'\n");
3310      }
3311    }
3312  }
3313  printf("\n");
[367]3314  fflush(stdout);
[2]3315#endif
3316
3317  // build the flows
3318  //~ this needs to be adjusted for writing mode (vertical text)
3319  //~ this also needs to account for right-to-left column ordering
[367]3320  flow = NULL;
[27]3321  while (flows) {
3322    flow = flows;
3323    flows = flows->next;
3324    delete flow;
3325  }
[2]3326  flows = lastFlow = NULL;
[367]3327  // assume blocks are already in reading order,
3328  // and construct flows accordingly.
3329  for (i = 0; i < nBlocks; i++) {
3330    blk = blocks[i];
3331    blk->next = NULL;
3332    if (flow) {
3333      blk1 = blocks[i - 1];
3334      blkSpace = maxBlockSpacing * blk1->lines->words->fontSize;
3335      if (blk1->secondaryDelta(blk) <= blkSpace &&
3336          blk->isBelow(blk1) &&
3337          flow->blockFits(blk, blk1)) {
3338        flow->addBlock(blk);
3339        continue;
[2]3340      }
3341    }
3342    flow = new TextFlow(this, blk);
3343    if (lastFlow) {
3344      lastFlow->next = flow;
3345    } else {
3346      flows = flow;
3347    }
3348    lastFlow = flow;
3349  }
3350
3351#if 0 // for debugging
3352  printf("*** flows ***\n");
3353  for (flow = flows; flow; flow = flow->next) {
3354    printf("flow: x=%.2f..%.2f y=%.2f..%.2f pri:%.2f..%.2f\n",
3355           flow->xMin, flow->xMax, flow->yMin, flow->yMax,
3356           flow->priMin, flow->priMax);
3357    for (blk = flow->blocks; blk; blk = blk->next) {
3358      printf("  block: rot=%d x=%.2f..%.2f y=%.2f..%.2f pri=%.2f..%.2f\n",
[461]3359             blk->rot, blk->ExMin, blk->ExMax, blk->EyMin, blk->EyMax,
[2]3360             blk->priMin, blk->priMax);
3361      for (line = blk->lines; line; line = line->next) {
3362        printf("    line:\n");
3363        for (word0 = line->words; word0; word0 = word0->next) {
3364          printf("      word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
3365                 word0->xMin, word0->xMax, word0->yMin, word0->yMax,
3366                 word0->base, word0->fontSize, word0->spaceAfter);
3367          for (i = 0; i < word0->len; ++i) {
3368            fputc(word0->text[i] & 0xff, stdout);
3369          }
3370          printf("'\n");
3371        }
3372      }
3373    }
3374  }
3375  printf("\n");
3376#endif
3377
3378  if (uMap) {
3379    uMap->decRefCnt();
3380  }
3381}
3382
3383GBool TextPage::findText(Unicode *s, int len,
3384                         GBool startAtTop, GBool stopAtBottom,
3385                         GBool startAtLast, GBool stopAtLast,
3386                         GBool caseSensitive, GBool backward,
3387                         double *xMin, double *yMin,
3388                         double *xMax, double *yMax) {
3389  TextBlock *blk;
3390  TextLine *line;
3391  Unicode *s2, *txt;
3392  Unicode *p;
3393  int txtSize, m, i, j, k;
3394  double xStart, yStart, xStop, yStop;
3395  double xMin0, yMin0, xMax0, yMax0;
3396  double xMin1, yMin1, xMax1, yMax1;
3397  GBool found;
3398
3399  //~ needs to handle right-to-left text
3400
3401  if (rawOrder) {
3402    return gFalse;
3403  }
3404
3405  // convert the search string to uppercase
3406  if (!caseSensitive) {
[27]3407    s2 = unicodeNormalizeNFKC(s, len, &len, NULL);
[2]3408    for (i = 0; i < len; ++i) {
[27]3409      s2[i] = unicodeToUpper(s2[i]);
[2]3410    }
3411  } else {
[27]3412    s2 = unicodeNormalizeNFKC(s, len, &len, NULL);
[2]3413  }
3414
3415  txt = NULL;
3416  txtSize = 0;
3417
3418  xStart = yStart = xStop = yStop = 0;
3419  if (startAtLast && haveLastFind) {
3420    xStart = lastFindXMin;
3421    yStart = lastFindYMin;
3422  } else if (!startAtTop) {
3423    xStart = *xMin;
3424    yStart = *yMin;
3425  }
3426  if (stopAtLast && haveLastFind) {
3427    xStop = lastFindXMin;
3428    yStop = lastFindYMin;
3429  } else if (!stopAtBottom) {
3430    xStop = *xMax;
3431    yStop = *yMax;
3432  }
3433
3434  found = gFalse;
3435  xMin0 = xMax0 = yMin0 = yMax0 = 0; // make gcc happy
3436  xMin1 = xMax1 = yMin1 = yMax1 = 0; // make gcc happy
3437
3438  for (i = backward ? nBlocks - 1 : 0;
3439       backward ? i >= 0 : i < nBlocks;
3440       i += backward ? -1 : 1) {
3441    blk = blocks[i];
3442
3443    // check: is the block above the top limit?
3444    if (!startAtTop && (backward ? blk->yMin > yStart : blk->yMax < yStart)) {
3445      continue;
3446    }
3447
3448    // check: is the block below the bottom limit?
3449    if (!stopAtBottom && (backward ? blk->yMax < yStop : blk->yMin > yStop)) {
3450      break;
3451    }
3452
3453    for (line = blk->lines; line; line = line->next) {
3454
3455      // check: is the line above the top limit?
3456      if (!startAtTop &&
3457          (backward ? line->yMin > yStart : line->yMin < yStart)) {
3458        continue;
3459      }
3460
3461      // check: is the line below the bottom limit?
3462      if (!stopAtBottom &&
3463          (backward ? line->yMin < yStop : line->yMin > yStop)) {
3464        continue;
3465      }
3466
[27]3467      if (!line->normalized)
3468        line->normalized = unicodeNormalizeNFKC(line->text, line->len, 
3469                                                &line->normalized_len, 
3470                                                &line->normalized_idx);
[2]3471      // convert the line to uppercase
[27]3472      m = line->normalized_len;
[2]3473      if (!caseSensitive) {
3474        if (m > txtSize) {
3475          txt = (Unicode *)greallocn(txt, m, sizeof(Unicode));
3476          txtSize = m;
3477        }
3478        for (k = 0; k < m; ++k) {
[27]3479          txt[k] = unicodeToUpper(line->normalized[k]);
[2]3480          }
3481          } else {
[27]3482        txt = line->normalized;
[2]3483          }
3484
3485      // search each position in this line
3486      j = backward ? m - len : 0;
3487      p = txt + j;
3488      while (backward ? j >= 0 : j <= m - len) {
3489
3490        // compare the strings
3491        for (k = 0; k < len; ++k) {
3492          if (p[k] != s2[k]) {
3493            break;
3494          }
3495        }
3496
3497        // found it
3498        if (k == len) {
[250]3499          // where s2 matches a subsequence of a compatibility equivalence
3500          // decomposition, highlight the entire glyph, since we don't know
3501          // the internal layout of subglyph components
3502          int normStart = line->normalized_idx[j];
3503          int normAfterEnd = line->normalized_idx[j + len - 1] + 1;
[2]3504          switch (line->rot) {
3505          case 0:
[250]3506            xMin1 = line->edge[normStart];
3507            xMax1 = line->edge[normAfterEnd];
[2]3508            yMin1 = line->yMin;
3509            yMax1 = line->yMax;
3510            break;
3511          case 1:
3512            xMin1 = line->xMin;
3513            xMax1 = line->xMax;
[250]3514            yMin1 = line->edge[normStart];
3515            yMax1 = line->edge[normAfterEnd];
[2]3516            break;
3517          case 2:
[250]3518            xMin1 = line->edge[normAfterEnd];
3519            xMax1 = line->edge[normStart];
[2]3520            yMin1 = line->yMin;
3521            yMax1 = line->yMax;
3522            break;
3523          case 3:
3524            xMin1 = line->xMin;
3525            xMax1 = line->xMax;
[250]3526            yMin1 = line->edge[normAfterEnd];
3527            yMax1 = line->edge[normStart];
[2]3528            break;
3529          }
3530          if (backward) {
3531            if ((startAtTop ||
3532                 yMin1 < yStart || (yMin1 == yStart && xMin1 < xStart)) &&
3533                (stopAtBottom ||
3534                 yMin1 > yStop || (yMin1 == yStop && xMin1 > xStop))) {
3535              if (!found ||
3536                  yMin1 > yMin0 || (yMin1 == yMin0 && xMin1 > xMin0)) {
3537                xMin0 = xMin1;
3538                xMax0 = xMax1;
3539                yMin0 = yMin1;
3540                yMax0 = yMax1;
3541                found = gTrue;
3542              }
3543            }
3544          } else {
[250]3545            if ((startAtTop ||
3546                 yMin1 > yStart || (yMin1 == yStart && xMin1 > xStart)) &&
3547                (stopAtBottom ||
[2]3548                 yMin1 < yStop || (yMin1 == yStop && xMin1 < xStop))) {
3549              if (!found ||
3550                  yMin1 < yMin0 || (yMin1 == yMin0 && xMin1 < xMin0)) {
[250]3551                xMin0 = xMin1;
3552                xMax0 = xMax1;
3553                yMin0 = yMin1;
3554                yMax0 = yMax1;
3555                found = gTrue;
3556              }
[2]3557            }
3558          }
3559        }
3560        if (backward) {
3561          --j;
3562          --p;
3563        } else {
3564          ++j;
3565          ++p;
3566        }
3567      }
3568    }
3569    }
3570
[27]3571  gfree(s2);
[2]3572  if (!caseSensitive) {
3573    gfree(txt);
3574  }
3575
3576  if (found) {
3577    *xMin = xMin0;
3578    *xMax = xMax0;
3579    *yMin = yMin0;
3580    *yMax = yMax0;
3581    lastFindXMin = xMin0;
3582    lastFindYMin = yMin0;
3583    haveLastFind = gTrue;
3584    return gTrue;
3585  }
3586
3587  return gFalse;
3588}
3589
3590GooString *TextPage::getText(double xMin, double yMin,
3591                           double xMax, double yMax) {
3592  GooString *s;
3593  UnicodeMap *uMap;
3594  GBool isUnicode;
3595  TextBlock *blk;
3596  TextLine *line;
3597  TextLineFrag *frags;
3598  int nFrags, fragsSize;
3599  TextLineFrag *frag;
3600  char space[8], eol[16];
3601  int spaceLen, eolLen;
3602  int lastRot;
[250]3603  double x, y, delta;
[2]3604  int col, idx0, idx1, i, j;
3605  GBool multiLine, oneRot;
3606
3607  s = new GooString();
3608
[470]3609  // get the output encoding
3610  if (!(uMap = globalParams->getTextEncoding())) {
[2]3611    return s;
3612  }
3613
[470]3614  if (rawOrder) {
3615    TextWord*  word;
3616    char mbc[16];
3617    int  mbc_len;
3618
3619    for (word = rawWords; word && word <= rawLastWord; word = word->next) {
3620      for (j = 0; j < word->getLength(); ++j) {
3621        double gXMin, gXMax, gYMin, gYMax;
3622        word->getCharBBox(j, &gXMin, &gYMin, &gXMax, &gYMax);
3623        if (xMin <= gXMin && gXMax <= xMax && yMin <= gYMin && gYMax <= yMax)
3624        {
3625          mbc_len = uMap->mapUnicode( *(word->getChar(j)), mbc, sizeof(mbc) );
3626          s->append(mbc, mbc_len);
3627        }
3628      }
3629    }
[2]3630    return s;
3631  }
[470]3632
[2]3633  isUnicode = uMap->isUnicode();
3634  spaceLen = uMap->mapUnicode(0x20, space, sizeof(space));
3635  eolLen = 0; // make gcc happy
3636  switch (globalParams->getTextEOL()) {
3637  case eolUnix:
3638    eolLen = uMap->mapUnicode(0x0a, eol, sizeof(eol));
3639    break;
3640  case eolDOS:
3641    eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
3642    eolLen += uMap->mapUnicode(0x0a, eol + eolLen, sizeof(eol) - eolLen);
3643    break;
3644  case eolMac:
3645    eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
3646    break;
3647  }
3648
3649  //~ writing mode (horiz/vert)
3650
3651  // collect the line fragments that are in the rectangle
3652  fragsSize = 256;
3653  frags = (TextLineFrag *)gmallocn(fragsSize, sizeof(TextLineFrag));
3654  nFrags = 0;
3655  lastRot = -1;
3656  oneRot = gTrue;
3657  for (i = 0; i < nBlocks; ++i) {
3658    blk = blocks[i];
3659    if (xMin < blk->xMax && blk->xMin < xMax &&
3660        yMin < blk->yMax && blk->yMin < yMax) {
3661      for (line = blk->lines; line; line = line->next) {
3662        if (xMin < line->xMax && line->xMin < xMax &&
3663            yMin < line->yMax && line->yMin < yMax) {
3664          idx0 = idx1 = -1;
3665          switch (line->rot) {
3666          case 0:
3667            y = 0.5 * (line->yMin + line->yMax);
3668            if (yMin < y && y < yMax) {
3669              j = 0;
3670              while (j < line->len) {
3671                if (0.5 * (line->edge[j] + line->edge[j+1]) > xMin) {
3672                  idx0 = j;
3673                  break;
3674                }
3675                ++j;
3676              }
3677              j = line->len - 1;
3678              while (j >= 0) {
3679                if (0.5 * (line->edge[j] + line->edge[j+1]) < xMax) {
3680                  idx1 = j;
3681                  break;
3682                }
3683                --j;
3684              }
3685            }
3686            break;
3687          case 1:
3688            x = 0.5 * (line->xMin + line->xMax);
3689            if (xMin < x && x < xMax) {
3690              j = 0;
3691              while (j < line->len) {
3692                if (0.5 * (line->edge[j] + line->edge[j+1]) > yMin) {
3693                  idx0 = j;
3694                  break;
3695                }
3696                ++j;
3697              }
3698              j = line->len - 1;
3699              while (j >= 0) {
3700                if (0.5 * (line->edge[j] + line->edge[j+1]) < yMax) {
3701                  idx1 = j;
3702                  break;
3703                }
3704                --j;
3705              }
3706            }
3707            break;
3708          case 2:
3709            y = 0.5 * (line->yMin + line->yMax);
3710            if (yMin < y && y < yMax) {
3711              j = 0;
3712              while (j < line->len) {
3713                if (0.5 * (line->edge[j] + line->edge[j+1]) < xMax) {
3714                  idx0 = j;
3715                  break;
3716                }
3717                ++j;
3718              }
3719              j = line->len - 1;
3720              while (j >= 0) {
3721                if (0.5 * (line->edge[j] + line->edge[j+1]) > xMin) {
3722                  idx1 = j;
3723                  break;
3724                }
3725                --j;
3726              }
3727            }
3728            break;
3729          case 3:
3730            x = 0.5 * (line->xMin + line->xMax);
3731            if (xMin < x && x < xMax) {
3732              j = 0;
3733              while (j < line->len) {
3734                if (0.5 * (line->edge[j] + line->edge[j+1]) < yMax) {
3735                  idx0 = j;
3736                  break;
3737                }
3738                ++j;
3739              }
3740              j = line->len - 1;
3741              while (j >= 0) {
3742                if (0.5 * (line->edge[j] + line->edge[j+1]) > yMin) {
3743                  idx1 = j;
3744                  break;
3745                }
3746                --j;
3747              }
3748            }
3749            break;
3750          }
3751          if (idx0 >= 0 && idx1 >= 0) {