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

Last change on this file since 367 was 367, checked in by dmik, 11 years ago

Merged bramches/kmk (r294:365) to trunk.

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