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

Last change on this file since 277 was 277, checked in by rbri, 12 years ago

PDF plugin: Poppler library updated to version 0.12.3

File size: 122.3 KB
Line 
1//========================================================================
2//
3// TextOutputDev.cc
4//
5// Copyright 1997-2003 Glyph & Cog, LLC
6//
7//========================================================================
8
9//========================================================================
10//
11// Modified under the Poppler project - http://poppler.freedesktop.org
12//
13// Copyright (C) 2005-2007 Kristian HÞgsberg <krh@redhat.com>
14// Copyright (C) 2005 Nickolay V. Shmyrev <nshmyrev@yandex.ru>
15// Copyright (C) 2006-2008 Carlos Garcia Campos <carlosgc@gnome.org>
16// Copyright (C) 2006, 2007 Ed Catmur <ed@catmur.co.uk>
17// Copyright (C) 2006 Jeff Muizelaar <jeff@infidigm.net>
18// Copyright (C) 2007, 2008 Adrian Johnson <ajohnson@redneon.com>
19// Copyright (C) 2008 Koji Otani <sho@bbr.jp>
20// Copyright (C) 2008 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
1618//------------------------------------------------------------------------
1619// TextFlow
1620//------------------------------------------------------------------------
1621
1622TextFlow::TextFlow(TextPage *pageA, TextBlock *blk) {
1623  page = pageA;
1624  xMin = blk->xMin;
1625  xMax = blk->xMax;
1626  yMin = blk->yMin;
1627  yMax = blk->yMax;
1628  priMin = blk->priMin;
1629  priMax = blk->priMax;
1630  blocks = lastBlk = blk;
1631  next = NULL;
1632}
1633
1634TextFlow::~TextFlow() {
1635  TextBlock *blk;
1636
1637  while (blocks) {
1638    blk = blocks;
1639    blocks = blocks->next;
1640    delete blk;
1641  }
1642}
1643
1644void TextFlow::addBlock(TextBlock *blk) {
1645  if (lastBlk) {
1646    lastBlk->next = blk;
1647  } else {
1648    blocks = blk;
1649  }
1650  lastBlk = blk;
1651  if (blk->xMin < xMin) {
1652    xMin = blk->xMin;
1653  }
1654  if (blk->xMax > xMax) {
1655    xMax = blk->xMax;
1656  }
1657  if (blk->yMin < yMin) {
1658    yMin = blk->yMin;
1659  }
1660  if (blk->yMax > yMax) {
1661    yMax = blk->yMax;
1662  }
1663}
1664
1665GBool TextFlow::blockFits(TextBlock *blk, TextBlock *prevBlk) {
1666  GBool fits;
1667
1668  // lower blocks must use smaller fonts
1669  if (blk->lines->words->fontSize > lastBlk->lines->words->fontSize) {
1670    return gFalse;
1671  }
1672
1673  fits = gFalse; // make gcc happy
1674  switch (page->primaryRot) {
1675  case 0:
1676    fits = blk->xMin >= priMin && blk->xMax <= priMax;
1677    break;
1678  case 1:
1679    fits = blk->yMin >= priMin && blk->yMax <= priMax;
1680    break;
1681  case 2:
1682    fits = blk->xMin >= priMin && blk->xMax <= priMax;
1683    break;
1684  case 3:
1685    fits = blk->yMin >= priMin && blk->yMax <= priMax;
1686    break;
1687  }
1688  return fits;
1689}
1690
1691#if TEXTOUT_WORD_LIST
1692
1693//------------------------------------------------------------------------
1694// TextWordList
1695//------------------------------------------------------------------------
1696
1697TextWordList::TextWordList(TextPage *text, GBool physLayout) {
1698  TextFlow *flow;
1699  TextBlock *blk;
1700  TextLine *line;
1701  TextWord *word;
1702  TextWord **wordArray;
1703  int nWords, i;
1704
1705  words = new GooList();
1706
1707  if (text->rawOrder) {
1708    for (word = text->rawWords; word; word = word->next) {
1709      words->append(word);
1710    }
1711
1712  } else if (physLayout) {
1713    // this is inefficient, but it's also the least useful of these
1714    // three cases
1715    nWords = 0;
1716    for (flow = text->flows; flow; flow = flow->next) {
1717      for (blk = flow->blocks; blk; blk = blk->next) {
1718        for (line = blk->lines; line; line = line->next) {
1719          for (word = line->words; word; word = word->next) {
1720            ++nWords;
1721          }
1722        }
1723      }
1724    }
1725    wordArray = (TextWord **)gmallocn(nWords, sizeof(TextWord *));
1726    i = 0;
1727    for (flow = text->flows; flow; flow = flow->next) {
1728      for (blk = flow->blocks; blk; blk = blk->next) {
1729        for (line = blk->lines; line; line = line->next) {
1730          for (word = line->words; word; word = word->next) {
1731            wordArray[i++] = word;
1732          }
1733        }
1734      }
1735    }
1736    qsort(wordArray, nWords, sizeof(TextWord *), &TextWord::cmpYX);
1737    for (i = 0; i < nWords; ++i) {
1738      words->append(wordArray[i]);
1739    }
1740    gfree(wordArray);
1741
1742  } else {
1743    for (flow = text->flows; flow; flow = flow->next) {
1744      for (blk = flow->blocks; blk; blk = blk->next) {
1745        for (line = blk->lines; line; line = line->next) {
1746          for (word = line->words; word; word = word->next) {
1747            words->append(word);
1748          }
1749        }
1750      }
1751    }
1752  }
1753}
1754
1755TextWordList::~TextWordList() {
1756  delete words;
1757}
1758
1759int TextWordList::getLength() {
1760  return words->getLength();
1761}
1762
1763TextWord *TextWordList::get(int idx) {
1764  if (idx < 0 || idx >= words->getLength()) {
1765    return NULL;
1766  }
1767  return (TextWord *)words->get(idx);
1768}
1769
1770#endif // TEXTOUT_WORD_LIST
1771
1772//------------------------------------------------------------------------
1773// TextPage
1774//------------------------------------------------------------------------
1775
1776TextPage::TextPage(GBool rawOrderA) {
1777  int rot;
1778
1779  refCnt = 1;
1780  rawOrder = rawOrderA;
1781  curWord = NULL;
1782  charPos = 0;
1783  curFont = NULL;
1784  curFontSize = 0;
1785  nest = 0;
1786  nTinyChars = 0;
1787  lastCharOverlap = gFalse;
1788  if (!rawOrder) {
1789    for (rot = 0; rot < 4; ++rot) {
1790      pools[rot] = new TextPool();
1791    }
1792  }
1793  flows = NULL;
1794  blocks = NULL;
1795  rawWords = NULL;
1796  rawLastWord = NULL;
1797  fonts = new GooList();
1798  lastFindXMin = lastFindYMin = 0;
1799  haveLastFind = gFalse;
1800  underlines = new GooList();
1801  links = new GooList();
1802}
1803
1804TextPage::~TextPage() {
1805  int rot;
1806
1807  clear();
1808  if (!rawOrder) {
1809    for (rot = 0; rot < 4; ++rot) {
1810      delete pools[rot];
1811    }
1812  }
1813  delete fonts;
1814  deleteGooList(underlines, TextUnderline);
1815  deleteGooList(links, TextLink);
1816}
1817
1818void TextPage::incRefCnt() {
1819  refCnt++;
1820}
1821
1822void TextPage::decRefCnt() {
1823  if (--refCnt == 0)
1824    delete this;
1825}
1826
1827void TextPage::startPage(GfxState *state) {
1828  clear();
1829  if (state) {
1830    pageWidth = state->getPageWidth();
1831    pageHeight = state->getPageHeight();
1832  } else {
1833    pageWidth = pageHeight = 0;
1834  }
1835}
1836
1837void TextPage::endPage() {
1838  if (curWord) {
1839    endWord();
1840  }
1841}
1842
1843void TextPage::clear() {
1844  int rot;
1845  TextFlow *flow;
1846  TextWord *word;
1847
1848  if (curWord) {
1849    delete curWord;
1850    curWord = NULL;
1851  }
1852  if (rawOrder) {
1853    while (rawWords) {
1854      word = rawWords;
1855      rawWords = rawWords->next;
1856      delete word;
1857    }
1858  } else {
1859    for (rot = 0; rot < 4; ++rot) {
1860      delete pools[rot];
1861    }
1862    while (flows) {
1863      flow = flows;
1864      flows = flows->next;
1865      delete flow;
1866    }
1867    gfree(blocks);
1868  }
1869  deleteGooList(fonts, TextFontInfo);
1870
1871  curWord = NULL;
1872  charPos = 0;
1873  curFont = NULL;
1874  curFontSize = 0;
1875  nest = 0;
1876  nTinyChars = 0;
1877  if (!rawOrder) {
1878    for (rot = 0; rot < 4; ++rot) {
1879      pools[rot] = new TextPool();
1880    }
1881  }
1882  flows = NULL;
1883  blocks = NULL;
1884  rawWords = NULL;
1885  rawLastWord = NULL;
1886  fonts = new GooList();
1887}
1888
1889void TextPage::updateFont(GfxState *state) {
1890  GfxFont *gfxFont;
1891  double *fm;
1892  char *name;
1893  int code, mCode, letterCode, anyCode;
1894  double w;
1895  int i;
1896
1897  // get the font info object
1898  curFont = NULL;
1899  for (i = 0; i < fonts->getLength(); ++i) {
1900    curFont = (TextFontInfo *)fonts->get(i);
1901    if (curFont->matches(state)) {
1902      break;
1903    }
1904    curFont = NULL;
1905  }
1906  if (!curFont) {
1907    curFont = new TextFontInfo(state);
1908    fonts->append(curFont);
1909  }
1910
1911  // adjust the font size
1912  gfxFont = state->getFont();
1913  curFontSize = state->getTransformedFontSize();
1914  if (gfxFont && gfxFont->getType() == fontType3) {
1915    // This is a hack which makes it possible to deal with some Type 3
1916    // fonts.  The problem is that it's impossible to know what the
1917    // base coordinate system used in the font is without actually
1918    // rendering the font.  This code tries to guess by looking at the
1919    // width of the character 'm' (which breaks if the font is a
1920    // subset that doesn't contain 'm').
1921    mCode = letterCode = anyCode = -1;
1922    for (code = 0; code < 256; ++code) {
1923      name = ((Gfx8BitFont *)gfxFont)->getCharName(code);
1924      if (name && name[0] == 'm' && name[1] == '\0') {
1925        mCode = code;
1926      }
1927      if (letterCode < 0 && name && name[1] == '\0' &&
1928          ((name[0] >= 'A' && name[0] <= 'Z') ||
1929           (name[0] >= 'a' && name[0] <= 'z'))) {
1930        letterCode = code;
1931      }
1932      if (anyCode < 0 && name &&
1933          ((Gfx8BitFont *)gfxFont)->getWidth(code) > 0) {
1934        anyCode = code;
1935      }
1936    }
1937    if (mCode >= 0 &&
1938        (w = ((Gfx8BitFont *)gfxFont)->getWidth(mCode)) > 0) {
1939      // 0.6 is a generic average 'm' width -- yes, this is a hack
1940      curFontSize *= w / 0.6;
1941    } else if (letterCode >= 0 &&
1942               (w = ((Gfx8BitFont *)gfxFont)->getWidth(letterCode)) > 0) {
1943      // even more of a hack: 0.5 is a generic letter width
1944      curFontSize *= w / 0.5;
1945    } else if (anyCode >= 0 &&
1946               (w = ((Gfx8BitFont *)gfxFont)->getWidth(anyCode)) > 0) {
1947      // better than nothing: 0.5 is a generic character width
1948      curFontSize *= w / 0.5;
1949    }
1950    fm = gfxFont->getFontMatrix();
1951    if (fm[0] != 0) {
1952      curFontSize *= fabs(fm[3] / fm[0]);
1953    }
1954  }
1955}
1956
1957void TextPage::beginWord(GfxState *state, double x0, double y0) {
1958  GfxFont *gfxFont;
1959  double *fontm;
1960  double m[4], m2[4];
1961  int rot;
1962
1963  // This check is needed because Type 3 characters can contain
1964  // text-drawing operations (when TextPage is being used via
1965  // {X,Win}SplashOutputDev rather than TextOutputDev).
1966  if (curWord) {
1967    ++nest;
1968    return;
1969  }
1970
1971  // compute the rotation
1972  state->getFontTransMat(&m[0], &m[1], &m[2], &m[3]);
1973  gfxFont = state->getFont();
1974  if (gfxFont && gfxFont->getType() == fontType3) {
1975    fontm = state->getFont()->getFontMatrix();
1976    m2[0] = fontm[0] * m[0] + fontm[1] * m[2];
1977    m2[1] = fontm[0] * m[1] + fontm[1] * m[3];
1978    m2[2] = fontm[2] * m[0] + fontm[3] * m[2];
1979    m2[3] = fontm[2] * m[1] + fontm[3] * m[3];
1980    m[0] = m2[0];
1981    m[1] = m2[1];
1982    m[2] = m2[2];
1983    m[3] = m2[3];
1984  }
1985  if (fabs(m[0] * m[3]) > fabs(m[1] * m[2])) {
1986    rot = (m[3] < 0) ? 0 : 2;
1987  } else {
1988    rot = (m[2] > 0) ? 1 : 3;
1989  }
1990
1991  curWord = new TextWord(state, rot, x0, y0, charPos, curFont, curFontSize);
1992}
1993
1994void TextPage::addChar(GfxState *state, double x, double y,
1995                       double dx, double dy,
1996                       CharCode c, int nBytes, Unicode *u, int uLen) {
1997  double x1, y1, w1, h1, dx2, dy2, base, sp, delta;
1998  GBool overlap;
1999  int i;
2000
2001  // subtract char and word spacing from the dx,dy values
2002  sp = state->getCharSpace();
2003  if (c == (CharCode)0x20) {
2004    sp += state->getWordSpace();
2005  }
2006  state->textTransformDelta(sp * state->getHorizScaling(), 0, &dx2, &dy2);
2007  dx -= dx2;
2008  dy -= dy2;
2009  state->transformDelta(dx, dy, &w1, &h1);
2010
2011  // throw away chars that aren't inside the page bounds
2012  // (and also do a sanity check on the character size)
2013  state->transform(x, y, &x1, &y1);
2014  if (x1 + w1 < 0 || x1 > pageWidth ||
2015      y1 + h1 < 0 || y1 > pageHeight ||
2016      w1 > pageWidth || h1 > pageHeight) {
2017    charPos += nBytes;
2018    return;
2019  }
2020
2021  // check the tiny chars limit
2022  if (!globalParams->getTextKeepTinyChars() &&
2023      fabs(w1) < 3 && fabs(h1) < 3) {
2024    if (++nTinyChars > 50000) {
2025      charPos += nBytes;
2026      return;
2027    }
2028  }
2029
2030  // break words at space character
2031  if (uLen == 1 && u[0] == (Unicode)0x20) {
2032    if (curWord) {
2033      ++curWord->charLen;
2034    }
2035    charPos += nBytes;
2036    endWord();
2037    return;
2038  }
2039
2040  // start a new word if:
2041  // (1) this character doesn't fall in the right place relative to
2042  //     the end of the previous word (this places upper and lower
2043  //     constraints on the position deltas along both the primary
2044  //     and secondary axes), or
2045  // (2) this character overlaps the previous one (duplicated text), or
2046  // (3) the previous character was an overlap (we want each duplicated
2047  //     character to be in a word by itself at this stage),
2048  // (4) the font size has changed
2049  if (curWord && curWord->len > 0) {
2050    base = sp = delta = 0; // make gcc happy
2051    switch (curWord->rot) {
2052    case 0:
2053      base = y1;
2054      sp = x1 - curWord->xMax;
2055      delta = x1 - curWord->edge[curWord->len - 1];
2056      break;
2057    case 1:
2058      base = x1;
2059      sp = y1 - curWord->yMax;
2060      delta = y1 - curWord->edge[curWord->len - 1];
2061      break;
2062    case 2:
2063      base = y1;
2064      sp = curWord->xMin - x1;
2065      delta = curWord->edge[curWord->len - 1] - x1;
2066      break;
2067    case 3:
2068      base = x1;
2069      sp = curWord->yMin - y1;
2070      delta = curWord->edge[curWord->len - 1] - y1;
2071      break;
2072    }
2073    overlap = fabs(delta) < dupMaxPriDelta * curWord->fontSize &&
2074              fabs(base - curWord->base) < dupMaxSecDelta * curWord->fontSize;
2075    if (overlap || lastCharOverlap ||
2076        sp < -minDupBreakOverlap * curWord->fontSize ||
2077        sp > minWordBreakSpace * curWord->fontSize ||
2078        fabs(base - curWord->base) > 0.5 ||
2079        curFontSize != curWord->fontSize) {
2080      endWord();
2081    }
2082    lastCharOverlap = overlap;
2083  } else {
2084    lastCharOverlap = gFalse;
2085  }
2086
2087  if (uLen != 0) {
2088    // start a new word if needed
2089    if (!curWord) {
2090      beginWord(state, x, y);
2091    }
2092
2093  // page rotation and/or transform matrices can cause text to be
2094  // drawn in reverse order -- in this case, swap the begin/end
2095  // coordinates and break text into individual chars
2096  if ((curWord->rot == 0 && w1 < 0) ||
2097      (curWord->rot == 1 && h1 < 0) ||
2098      (curWord->rot == 2 && w1 > 0) ||
2099      (curWord->rot == 3 && h1 > 0)) {
2100    endWord();
2101    beginWord(state, x + dx, y + dy);
2102    x1 += w1;
2103    y1 += h1;
2104    w1 = -w1;
2105    h1 = -h1;
2106  }
2107
2108  // add the characters to the current word
2109    w1 /= uLen;
2110    h1 /= uLen;
2111  for (i = 0; i < uLen; ++i) {
2112      if (u[i] >= 0xd800 && u[i] < 0xdc00) { /* surrogate pair */
2113        if (i + 1 < uLen && u[i+1] >= 0xdc00 && u[i+1] < 0xe000) {
2114          /* next code is a low surrogate */
2115          Unicode uu = (((u[i] & 0x3ff) << 10) | (u[i+1] & 0x3ff)) + 0x10000;
2116          i++;
2117          curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, uu);
2118        } else {
2119            /* missing low surrogate
2120             replace it with REPLACEMENT CHARACTER (U+FFFD) */
2121          curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, 0xfffd);
2122        }
2123      } else if (u[i] >= 0xdc00 && u[i] < 0xe000) {
2124          /* invalid low surrogate
2125           replace it with REPLACEMENT CHARACTER (U+FFFD) */
2126        curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, 0xfffd);
2127      } else {
2128        curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, c, u[i]);
2129      }
2130  }
2131  }
2132  if (curWord) {
2133    curWord->charLen += nBytes;
2134  }
2135  charPos += nBytes;
2136}
2137
2138void TextPage::endWord() {
2139  // This check is needed because Type 3 characters can contain
2140  // text-drawing operations (when TextPage is being used via
2141  // {X,Win}SplashOutputDev rather than TextOutputDev).
2142  if (nest > 0) {
2143    --nest;
2144    return;
2145  }
2146
2147  if (curWord) {
2148    addWord(curWord);
2149    curWord = NULL;
2150  }
2151}
2152
2153void TextPage::addWord(TextWord *word) {
2154  // throw away zero-length words -- they don't have valid xMin/xMax
2155  // values, and they're useless anyway
2156  if (word->len == 0) {
2157    delete word;
2158    return;
2159  }
2160
2161  if (rawOrder) {
2162    if (rawLastWord) {
2163      rawLastWord->next = word;
2164    } else {
2165      rawWords = word;
2166    }
2167    rawLastWord = word;
2168  } else {
2169    pools[word->rot]->addWord(word);
2170  }
2171}
2172
2173void TextPage::addUnderline(double x0, double y0, double x1, double y1) {
2174  underlines->append(new TextUnderline(x0, y0, x1, y1));
2175}
2176
2177void TextPage::addLink(int xMin, int yMin, int xMax, int yMax, Link *link) {
2178  links->append(new TextLink(xMin, yMin, xMax, yMax, link));
2179}
2180
2181void TextPage::coalesce(GBool physLayout, GBool doHTML) {
2182  UnicodeMap *uMap;
2183  TextPool *pool;
2184  TextWord *word0, *word1, *word2;
2185  TextLine *line;
2186  TextBlock *blkList, *blkStack, *blk, *lastBlk, *blk0, *blk1;
2187  TextBlock **blkArray;
2188  TextFlow *flow, *lastFlow;
2189  TextUnderline *underline;
2190  TextLink *link;
2191  int rot, poolMinBaseIdx, baseIdx, startBaseIdx, endBaseIdx;
2192  double minBase, maxBase, newMinBase, newMaxBase;
2193  double fontSize, colSpace1, colSpace2, lineSpace, intraLineSpace, blkSpace;
2194  GBool found;
2195  int count[4];
2196  int lrCount;
2197  int firstBlkIdx, nBlocksLeft;
2198  int col1, col2;
2199  int i, j, n;
2200
2201  if (rawOrder) {
2202    primaryRot = 0;
2203    primaryLR = gTrue;
2204    return;
2205  }
2206
2207  uMap = globalParams->getTextEncoding();
2208  blkList = NULL;
2209  lastBlk = NULL;
2210  nBlocks = 0;
2211  primaryRot = -1;
2212
2213#if 0 // for debugging
2214  printf("*** initial words ***\n");
2215  for (rot = 0; rot < 4; ++rot) {
2216    pool = pools[rot];
2217    for (baseIdx = pool->minBaseIdx; baseIdx <= pool->maxBaseIdx; ++baseIdx) {
2218      for (word0 = pool->getPool(baseIdx); word0; word0 = word0->next) {
2219        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f rot=%d link=%p '",
2220               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2221               word0->base, word0->fontSize, rot*90, word0->link);
2222        for (i = 0; i < word0->len; ++i) {
2223          fputc(word0->text[i] & 0xff, stdout);
2224        }
2225        printf("'\n");
2226      }
2227    }
2228  }
2229  printf("\n");
2230#endif
2231
2232#if 0 //~ for debugging
2233  for (i = 0; i < underlines->getLength(); ++i) {
2234    underline = (TextUnderline *)underlines->get(i);
2235    printf("underline: x=%g..%g y=%g..%g horiz=%d\n",
2236           underline->x0, underline->x1, underline->y0, underline->y1,
2237           underline->horiz);
2238  }
2239#endif
2240
2241  if (doHTML) {
2242
2243    //----- handle underlining
2244    for (i = 0; i < underlines->getLength(); ++i) {
2245      underline = (TextUnderline *)underlines->get(i);
2246      if (underline->horiz) {
2247        // rot = 0
2248        if (pools[0]->minBaseIdx <= pools[0]->maxBaseIdx) {
2249          startBaseIdx = pools[0]->getBaseIdx(underline->y0 + minUnderlineGap);
2250          endBaseIdx = pools[0]->getBaseIdx(underline->y0 + maxUnderlineGap);
2251          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2252            for (word0 = pools[0]->getPool(j); word0; word0 = word0->next) {
2253              //~ need to check the y value against the word baseline
2254              if (underline->x0 < word0->xMin + underlineSlack &&
2255                  word0->xMax - underlineSlack < underline->x1) {
2256                word0->underlined = gTrue;
2257              }
2258            }
2259          }
2260        }
2261
2262        // rot = 2
2263        if (pools[2]->minBaseIdx <= pools[2]->maxBaseIdx) {
2264          startBaseIdx = pools[2]->getBaseIdx(underline->y0 - maxUnderlineGap);
2265          endBaseIdx = pools[2]->getBaseIdx(underline->y0 - minUnderlineGap);
2266          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2267            for (word0 = pools[2]->getPool(j); word0; word0 = word0->next) {
2268              if (underline->x0 < word0->xMin + underlineSlack &&
2269                  word0->xMax - underlineSlack < underline->x1) {
2270                word0->underlined = gTrue;
2271              }
2272            }
2273          }
2274        }
2275      } else {
2276        // rot = 1
2277        if (pools[1]->minBaseIdx <= pools[1]->maxBaseIdx) {
2278          startBaseIdx = pools[1]->getBaseIdx(underline->x0 - maxUnderlineGap);
2279          endBaseIdx = pools[1]->getBaseIdx(underline->x0 - minUnderlineGap);
2280          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2281            for (word0 = pools[1]->getPool(j); word0; word0 = word0->next) {
2282              if (underline->y0 < word0->yMin + underlineSlack &&
2283                  word0->yMax - underlineSlack < underline->y1) {
2284                word0->underlined = gTrue;
2285              }
2286            }
2287          }
2288        }
2289
2290        // rot = 3
2291        if (pools[3]->minBaseIdx <= pools[3]->maxBaseIdx) {
2292          startBaseIdx = pools[3]->getBaseIdx(underline->x0 + minUnderlineGap);
2293          endBaseIdx = pools[3]->getBaseIdx(underline->x0 + maxUnderlineGap);
2294          for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2295            for (word0 = pools[3]->getPool(j); word0; word0 = word0->next) {
2296              if (underline->y0 < word0->yMin + underlineSlack &&
2297                  word0->yMax - underlineSlack < underline->y1) {
2298                word0->underlined = gTrue;
2299              }
2300            }
2301          }
2302        }
2303      }
2304    }
2305
2306    //----- handle links
2307    for (i = 0; i < links->getLength(); ++i) {
2308      link = (TextLink *)links->get(i);
2309
2310      // rot = 0
2311      if (pools[0]->minBaseIdx <= pools[0]->maxBaseIdx) {
2312        startBaseIdx = pools[0]->getBaseIdx(link->yMin);
2313        endBaseIdx = pools[0]->getBaseIdx(link->yMax);
2314        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2315          for (word0 = pools[0]->getPool(j); word0; word0 = word0->next) {
2316            if (link->xMin < word0->xMin + hyperlinkSlack &&
2317                word0->xMax - hyperlinkSlack < link->xMax &&
2318                link->yMin < word0->yMin + hyperlinkSlack &&
2319                word0->yMax - hyperlinkSlack < link->yMax) {
2320              word0->link = link->link;
2321            }
2322          }
2323        }
2324      }
2325
2326      // rot = 2
2327      if (pools[2]->minBaseIdx <= pools[2]->maxBaseIdx) {
2328        startBaseIdx = pools[2]->getBaseIdx(link->yMin);
2329        endBaseIdx = pools[2]->getBaseIdx(link->yMax);
2330        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2331          for (word0 = pools[2]->getPool(j); word0; word0 = word0->next) {
2332            if (link->xMin < word0->xMin + hyperlinkSlack &&
2333                word0->xMax - hyperlinkSlack < link->xMax &&
2334                link->yMin < word0->yMin + hyperlinkSlack &&
2335                word0->yMax - hyperlinkSlack < link->yMax) {
2336              word0->link = link->link;
2337            }
2338          }
2339        }
2340      }
2341
2342      // rot = 1
2343      if (pools[1]->minBaseIdx <= pools[1]->maxBaseIdx) {
2344        startBaseIdx = pools[1]->getBaseIdx(link->xMin);
2345        endBaseIdx = pools[1]->getBaseIdx(link->xMax);
2346        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2347          for (word0 = pools[1]->getPool(j); word0; word0 = word0->next) {
2348            if (link->yMin < word0->yMin + hyperlinkSlack &&
2349                word0->yMax - hyperlinkSlack < link->yMax &&
2350                link->xMin < word0->xMin + hyperlinkSlack &&
2351                word0->xMax - hyperlinkSlack < link->xMax) {
2352              word0->link = link->link;
2353            }
2354          }
2355        }
2356      }
2357
2358      // rot = 3
2359      if (pools[3]->minBaseIdx <= pools[3]->maxBaseIdx) {
2360        startBaseIdx = pools[3]->getBaseIdx(link->xMin);
2361        endBaseIdx = pools[3]->getBaseIdx(link->xMax);
2362        for (j = startBaseIdx; j <= endBaseIdx; ++j) {
2363          for (word0 = pools[3]->getPool(j); word0; word0 = word0->next) {
2364            if (link->yMin < word0->yMin + hyperlinkSlack &&
2365                word0->yMax - hyperlinkSlack < link->yMax &&
2366                link->xMin < word0->xMin + hyperlinkSlack &&
2367                word0->xMax - hyperlinkSlack < link->xMax) {
2368              word0->link = link->link;
2369            }
2370          }
2371        }
2372      }
2373    }
2374  }
2375
2376  //----- assemble the blocks
2377
2378  //~ add an outer loop for writing mode (vertical text)
2379
2380  // build blocks for each rotation value
2381  for (rot = 0; rot < 4; ++rot) {
2382    pool = pools[rot];
2383    poolMinBaseIdx = pool->minBaseIdx;
2384    count[rot] = 0;
2385
2386    // add blocks until no more words are left
2387    while (1) {
2388
2389      // find the first non-empty line in the pool
2390      for (;
2391           poolMinBaseIdx <= pool->maxBaseIdx &&
2392             !pool->getPool(poolMinBaseIdx);
2393           ++poolMinBaseIdx) ;
2394      if (poolMinBaseIdx > pool->maxBaseIdx) {
2395        break;
2396      }
2397
2398      // look for the left-most word in the first four lines of the
2399      // pool -- this avoids starting with a superscript word
2400      startBaseIdx = poolMinBaseIdx;
2401      for (baseIdx = poolMinBaseIdx + 1;
2402           baseIdx < poolMinBaseIdx + 4 && baseIdx <= pool->maxBaseIdx;
2403           ++baseIdx) {
2404        if (!pool->getPool(baseIdx)) {
2405          continue;
2406        }
2407        if (pool->getPool(baseIdx)->primaryCmp(pool->getPool(startBaseIdx))
2408            < 0) {
2409          startBaseIdx = baseIdx;
2410        }
2411      }
2412
2413      // create a new block
2414      word0 = pool->getPool(startBaseIdx);
2415      pool->setPool(startBaseIdx, word0->next);
2416      word0->next = NULL;
2417      blk = new TextBlock(this, rot);
2418      blk->addWord(word0);
2419
2420      fontSize = word0->fontSize;
2421      minBase = maxBase = word0->base;
2422      colSpace1 = minColSpacing1 * fontSize;
2423      colSpace2 = minColSpacing2 * fontSize;
2424      lineSpace = maxLineSpacingDelta * fontSize;
2425      intraLineSpace = maxIntraLineDelta * fontSize;
2426
2427      // add words to the block
2428      do {
2429        found = gFalse;
2430
2431        // look for words on the line above the current top edge of
2432        // the block
2433        newMinBase = minBase;
2434        for (baseIdx = pool->getBaseIdx(minBase);
2435             baseIdx >= pool->getBaseIdx(minBase - lineSpace);
2436             --baseIdx) {
2437          word0 = NULL;
2438          word1 = pool->getPool(baseIdx);
2439          while (word1) {
2440            if (word1->base < minBase &&
2441                word1->base >= minBase - lineSpace &&
2442                ((rot == 0 || rot == 2)
2443                 ? (word1->xMin < blk->xMax && word1->xMax > blk->xMin)
2444                 : (word1->yMin < blk->yMax && word1->yMax > blk->yMin)) &&
2445                fabs(word1->fontSize - fontSize) <
2446                  maxBlockFontSizeDelta1 * fontSize) {
2447              word2 = word1;
2448              if (word0) {
2449                word0->next = word1->next;
2450              } else {
2451                pool->setPool(baseIdx, word1->next);
2452              }
2453              word1 = word1->next;
2454              word2->next = NULL;
2455              blk->addWord(word2);
2456              found = gTrue;
2457              newMinBase = word2->base;
2458            } else {
2459              word0 = word1;
2460              word1 = word1->next;
2461            }
2462          }
2463        }
2464        minBase = newMinBase;
2465
2466        // look for words on the line below the current bottom edge of
2467        // the block
2468        newMaxBase = maxBase;
2469        for (baseIdx = pool->getBaseIdx(maxBase);
2470             baseIdx <= pool->getBaseIdx(maxBase + lineSpace);
2471             ++baseIdx) {
2472          word0 = NULL;
2473          word1 = pool->getPool(baseIdx);
2474          while (word1) {
2475            if (word1->base > maxBase &&
2476                word1->base <= maxBase + lineSpace &&
2477                ((rot == 0 || rot == 2)
2478                 ? (word1->xMin < blk->xMax && word1->xMax > blk->xMin)
2479                 : (word1->yMin < blk->yMax && word1->yMax > blk->yMin)) &&
2480                fabs(word1->fontSize - fontSize) <
2481                  maxBlockFontSizeDelta1 * fontSize) {
2482              word2 = word1;
2483              if (word0) {
2484                word0->next = word1->next;
2485              } else {
2486                pool->setPool(baseIdx, word1->next);
2487              }
2488              word1 = word1->next;
2489              word2->next = NULL;
2490              blk->addWord(word2);
2491              found = gTrue;
2492              newMaxBase = word2->base;
2493            } else {
2494              word0 = word1;
2495              word1 = word1->next;
2496            }
2497          }
2498        }
2499        maxBase = newMaxBase;
2500
2501        // look for words that are on lines already in the block, and
2502        // that overlap the block horizontally
2503        for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2504             baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2505             ++baseIdx) {
2506          word0 = NULL;
2507          word1 = pool->getPool(baseIdx);
2508          while (word1) {
2509            if (word1->base >= minBase - intraLineSpace &&
2510                word1->base <= maxBase + intraLineSpace &&
2511                ((rot == 0 || rot == 2)
2512                 ? (word1->xMin < blk->xMax + colSpace1 &&
2513                    word1->xMax > blk->xMin - colSpace1)
2514                 : (word1->yMin < blk->yMax + colSpace1 &&
2515                    word1->yMax > blk->yMin - colSpace1)) &&
2516                fabs(word1->fontSize - fontSize) <
2517                  maxBlockFontSizeDelta2 * fontSize) {
2518              word2 = word1;
2519              if (word0) {
2520                word0->next = word1->next;
2521              } else {
2522                pool->setPool(baseIdx, word1->next);
2523              }
2524              word1 = word1->next;
2525              word2->next = NULL;
2526              blk->addWord(word2);
2527              found = gTrue;
2528            } else {
2529              word0 = word1;
2530              word1 = word1->next;
2531            }
2532          }
2533        }
2534
2535        // only check for outlying words (the next two chunks of code)
2536        // if we didn't find anything else
2537        if (found) {
2538          continue;
2539        }
2540
2541        // scan down the left side of the block, looking for words
2542        // that are near (but not overlapping) the block; if there are
2543        // three or fewer, add them to the block
2544        n = 0;
2545        for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2546             baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2547             ++baseIdx) {
2548          word1 = pool->getPool(baseIdx);
2549          while (word1) {
2550            if (word1->base >= minBase - intraLineSpace &&
2551                word1->base <= maxBase + intraLineSpace &&
2552                ((rot == 0 || rot == 2)
2553                 ? (word1->xMax <= blk->xMin &&
2554                    word1->xMax > blk->xMin - colSpace2)
2555                 : (word1->yMax <= blk->yMin &&
2556                    word1->yMax > blk->yMin - colSpace2)) &&
2557                fabs(word1->fontSize - fontSize) <
2558                  maxBlockFontSizeDelta3 * fontSize) {
2559              ++n;
2560              break;
2561            }
2562            word1 = word1->next;
2563          }
2564        }
2565        if (n > 0 && n <= 3) {
2566          for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2567               baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2568               ++baseIdx) {
2569            word0 = NULL;
2570            word1 = pool->getPool(baseIdx);
2571            while (word1) {
2572              if (word1->base >= minBase - intraLineSpace &&
2573                  word1->base <= maxBase + intraLineSpace &&
2574                  ((rot == 0 || rot == 2)
2575                   ? (word1->xMax <= blk->xMin &&
2576                      word1->xMax > blk->xMin - colSpace2)
2577                   : (word1->yMax <= blk->yMin &&
2578                      word1->yMax > blk->yMin - colSpace2)) &&
2579                  fabs(word1->fontSize - fontSize) <
2580                    maxBlockFontSizeDelta3 * fontSize) {
2581                word2 = word1;
2582                if (word0) {
2583                  word0->next = word1->next;
2584                } else {
2585                  pool->setPool(baseIdx, word1->next);
2586                }
2587                word1 = word1->next;
2588                word2->next = NULL;
2589                blk->addWord(word2);
2590                if (word2->base < minBase) {
2591                  minBase = word2->base;
2592                } else if (word2->base > maxBase) {
2593                  maxBase = word2->base;
2594                }
2595                found = gTrue;
2596                break;
2597              } else {
2598                word0 = word1;
2599                word1 = word1->next;
2600              }
2601            }
2602          }
2603        }
2604
2605        // scan down the right side of the block, looking for words
2606        // that are near (but not overlapping) the block; if there are
2607        // three or fewer, add them to the block
2608        n = 0;
2609        for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2610             baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2611             ++baseIdx) {
2612          word1 = pool->getPool(baseIdx);
2613          while (word1) {
2614            if (word1->base >= minBase - intraLineSpace &&
2615                word1->base <= maxBase + intraLineSpace &&
2616                ((rot == 0 || rot == 2)
2617                 ? (word1->xMin >= blk->xMax &&
2618                    word1->xMin < blk->xMax + colSpace2)
2619                 : (word1->yMin >= blk->yMax &&
2620                    word1->yMin < blk->yMax + colSpace2)) &&
2621                fabs(word1->fontSize - fontSize) <
2622                  maxBlockFontSizeDelta3 * fontSize) {
2623              ++n;
2624              break;
2625            }
2626            word1 = word1->next;
2627          }
2628        }
2629        if (n > 0 && n <= 3) {
2630          for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2631               baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2632               ++baseIdx) {
2633            word0 = NULL;
2634            word1 = pool->getPool(baseIdx);
2635            while (word1) {
2636              if (word1->base >= minBase - intraLineSpace &&
2637                  word1->base <= maxBase + intraLineSpace &&
2638                  ((rot == 0 || rot == 2)
2639                   ? (word1->xMin >= blk->xMax &&
2640                      word1->xMin < blk->xMax + colSpace2)
2641                   : (word1->yMin >= blk->yMax &&
2642                      word1->yMin < blk->yMax + colSpace2)) &&
2643                  fabs(word1->fontSize - fontSize) <
2644                    maxBlockFontSizeDelta3 * fontSize) {
2645                word2 = word1;
2646                if (word0) {
2647                  word0->next = word1->next;
2648                } else {
2649                  pool->setPool(baseIdx, word1->next);
2650                }
2651                word1 = word1->next;
2652                word2->next = NULL;
2653                blk->addWord(word2);
2654                if (word2->base < minBase) {
2655                  minBase = word2->base;
2656                } else if (word2->base > maxBase) {
2657                  maxBase = word2->base;
2658                }
2659                found = gTrue;
2660                break;
2661              } else {
2662                word0 = word1;
2663                word1 = word1->next;
2664              }
2665            }
2666          }
2667        }
2668
2669      } while (found);
2670
2671      //~ need to compute the primary writing mode (horiz/vert) in
2672      //~ addition to primary rotation
2673
2674      // coalesce the block, and add it to the list
2675      blk->coalesce(uMap);
2676      if (lastBlk) {
2677        lastBlk->next = blk;
2678      } else {
2679        blkList = blk;
2680      }
2681      lastBlk = blk;
2682      count[rot] += blk->charCount;
2683      if (primaryRot < 0 || count[rot] > count[primaryRot]) {
2684        primaryRot = rot;
2685      }
2686      ++nBlocks;
2687    }
2688  }
2689
2690#if 0 // for debugging
2691  printf("*** rotation ***\n");
2692  for (rot = 0; rot < 4; ++rot) {
2693    printf("  %d: %6d\n", rot, count[rot]);
2694  }
2695  printf("  primary rot = %d\n", primaryRot);
2696  printf("\n");
2697#endif
2698
2699#if 0 // for debugging
2700  printf("*** blocks ***\n");
2701  for (blk = blkList; blk; blk = blk->next) {
2702    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f\n",
2703           blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax);
2704    for (line = blk->lines; line; line = line->next) {
2705      printf("  line: x=%.2f..%.2f y=%.2f..%.2f base=%.2f\n",
2706             line->xMin, line->xMax, line->yMin, line->yMax, line->base);
2707      for (word0 = line->words; word0; word0 = word0->next) {
2708        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2709               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2710               word0->base, word0->fontSize, word0->spaceAfter);
2711        for (i = 0; i < word0->len; ++i) {
2712          fputc(word0->text[i] & 0xff, stdout);
2713        }
2714        printf("'\n");
2715      }
2716    }
2717  }
2718  printf("\n");
2719#endif
2720
2721  // determine the primary direction
2722  lrCount = 0;
2723  for (blk = blkList; blk; blk = blk->next) {
2724    for (line = blk->lines; line; line = line->next) {
2725      for (word0 = line->words; word0; word0 = word0->next) {
2726        for (i = 0; i < word0->len; ++i) {
2727          if (unicodeTypeL(word0->text[i])) {
2728            ++lrCount;
2729          } else if (unicodeTypeR(word0->text[i])) {
2730            --lrCount;
2731          }
2732        }
2733      }
2734    }
2735  }
2736  primaryLR = lrCount >= 0;
2737
2738#if 0 // for debugging
2739  printf("*** direction ***\n");
2740  printf("lrCount = %d\n", lrCount);
2741  printf("primaryLR = %d\n", primaryLR);
2742#endif
2743
2744  //----- column assignment
2745
2746  // sort blocks into xy order for column assignment
2747  if (blocks)
2748    gfree (blocks);
2749  blocks = (TextBlock **)gmallocn(nBlocks, sizeof(TextBlock *));
2750  for (blk = blkList, i = 0; blk; blk = blk->next, ++i) {
2751    blocks[i] = blk;
2752  }
2753  qsort(blocks, nBlocks, sizeof(TextBlock *), &TextBlock::cmpXYPrimaryRot);
2754
2755  // column assignment
2756  for (i = 0; i < nBlocks; ++i) {
2757    blk0 = blocks[i];
2758    col1 = 0;
2759    for (j = 0; j < i; ++j) {
2760      blk1 = blocks[j];
2761      col2 = 0; // make gcc happy
2762      switch (primaryRot) {
2763      case 0:
2764        if (blk0->xMin > blk1->xMax) {
2765          col2 = blk1->col + blk1->nColumns + 3;
2766        } else if (blk1->xMax == blk1->xMin) {
2767          col2 = blk1->col;
2768        } else {
2769          col2 = blk1->col + (int)(((blk0->xMin - blk1->xMin) /
2770                                    (blk1->xMax - blk1->xMin)) *
2771                                   blk1->nColumns);
2772        }
2773        break;
2774      case 1:
2775        if (blk0->yMin > blk1->yMax) {
2776          col2 = blk1->col + blk1->nColumns + 3;
2777        } else if (blk1->yMax == blk1->yMin) {
2778          col2 = blk1->col;
2779        } else {
2780          col2 = blk1->col + (int)(((blk0->yMin - blk1->yMin) /
2781                                    (blk1->yMax - blk1->yMin)) *
2782                                   blk1->nColumns);
2783        }
2784        break;
2785      case 2:
2786        if (blk0->xMax < blk1->xMin) {
2787          col2 = blk1->col + blk1->nColumns + 3;
2788        } else if (blk1->xMin == blk1->xMax) {
2789          col2 = blk1->col;
2790        } else {
2791          col2 = blk1->col + (int)(((blk0->xMax - blk1->xMax) /
2792                                    (blk1->xMin - blk1->xMax)) *
2793                                   blk1->nColumns);
2794        }
2795        break;
2796      case 3:
2797        if (blk0->yMax < blk1->yMin) {
2798          col2 = blk1->col + blk1->nColumns + 3;
2799        } else if (blk1->yMin == blk1->yMax) {
2800          col2 = blk1->col;
2801        } else {
2802          col2 = blk1->col + (int)(((blk0->yMax - blk1->yMax) /
2803                                    (blk1->yMin - blk1->yMax)) *
2804                                   blk1->nColumns);
2805        }
2806        break;
2807      }
2808      if (col2 > col1) {
2809        col1 = col2;
2810      }
2811    }
2812    blk0->col = col1;
2813    for (line = blk0->lines; line; line = line->next) {
2814      for (j = 0; j <= line->len; ++j) {
2815        line->col[j] += col1;
2816      }
2817    }
2818  }
2819
2820#if 0 // for debugging
2821  printf("*** blocks, after column assignment ***\n");
2822  for (blk = blkList; blk; blk = blk->next) {
2823    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f col=%d nCols=%d\n",
2824           blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax, blk->col,
2825           blk->nColumns);
2826    for (line = blk->lines; line; line = line->next) {
2827      printf("  line:\n");
2828      for (word0 = line->words; word0; word0 = word0->next) {
2829        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2830               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2831               word0->base, word0->fontSize, word0->spaceAfter);
2832        for (i = 0; i < word0->len; ++i) {
2833          fputc(word0->text[i] & 0xff, stdout);
2834        }
2835        printf("'\n");
2836      }
2837    }
2838  }
2839  printf("\n");
2840#endif
2841
2842  //----- reading order sort
2843
2844  // sort blocks into yx order (in preparation for reading order sort)
2845  qsort(blocks, nBlocks, sizeof(TextBlock *), &TextBlock::cmpYXPrimaryRot);
2846
2847  // compute space on left and right sides of each block
2848  for (i = 0; i < nBlocks; ++i) {
2849    blk0 = blocks[i];
2850    for (j = 0; j < nBlocks; ++j) {
2851      blk1 = blocks[j];
2852      if (blk1 != blk0) {
2853        blk0->updatePriMinMax(blk1);
2854      }
2855    }
2856  }
2857
2858#if 0 // for debugging
2859  printf("*** blocks, after yx sort ***\n");
2860  for (i = 0; i < nBlocks; ++i) {
2861    blk = blocks[i];
2862    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f space=%.2f..%.2f\n",
2863           blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax,
2864           blk->priMin, blk->priMax);
2865    for (line = blk->lines; line; line = line->next) {
2866      printf("  line:\n");
2867      for (word0 = line->words; word0; word0 = word0->next) {
2868        printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2869               word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2870               word0->base, word0->fontSize, word0->spaceAfter);
2871        for (j = 0; j < word0->len; ++j) {
2872          fputc(word0->text[j] & 0xff, stdout);
2873        }
2874        printf("'\n");
2875      }
2876    }
2877  }
2878  printf("\n");
2879#endif
2880
2881  // build the flows
2882  //~ this needs to be adjusted for writing mode (vertical text)
2883  //~ this also needs to account for right-to-left column ordering
2884  blkArray = (TextBlock **)gmallocn(nBlocks, sizeof(TextBlock *));
2885  memcpy(blkArray, blocks, nBlocks * sizeof(TextBlock *));
2886  while (flows) {
2887    flow = flows;
2888    flows = flows->next;
2889    delete flow;
2890  }
2891  flows = lastFlow = NULL;
2892  firstBlkIdx = 0;
2893  nBlocksLeft = nBlocks;
2894  while (nBlocksLeft > 0) {
2895
2896    // find the upper-left-most block
2897    for (; !blkArray[firstBlkIdx]; ++firstBlkIdx) ;
2898    i = firstBlkIdx;
2899    blk = blkArray[i];
2900    for (j = firstBlkIdx + 1; j < nBlocks; ++j) {
2901      blk1 = blkArray[j];
2902      if (blk1) {
2903        if (blk && blk->secondaryDelta(blk1) > 0) {
2904          break;
2905        }
2906        if (blk1->primaryCmp(blk) < 0) {
2907          i = j;
2908          blk = blk1;
2909        }
2910      }
2911    }
2912    blkArray[i] = NULL;
2913    --nBlocksLeft;
2914    blk->next = NULL;
2915
2916    // create a new flow, starting with the upper-left-most block
2917    flow = new TextFlow(this, blk);
2918    if (lastFlow) {
2919      lastFlow->next = flow;
2920    } else {
2921      flows = flow;
2922    }
2923    lastFlow = flow;
2924    fontSize = blk->lines->words->fontSize;
2925
2926    // push the upper-left-most block on the stack
2927    blk->stackNext = NULL;
2928    blkStack = blk;
2929
2930    // find the other blocks in this flow
2931    while (blkStack) {
2932
2933      // find the upper-left-most block under (but within
2934      // maxBlockSpacing of) the top block on the stack
2935      blkSpace = maxBlockSpacing * blkStack->lines->words->fontSize;
2936      blk = NULL;
2937      i = -1;
2938      for (j = firstBlkIdx; j < nBlocks; ++j) {
2939        blk1 = blkArray[j];
2940        if (blk1) {
2941          if (blkStack->secondaryDelta(blk1) > blkSpace) {
2942            break;
2943          }
2944          if (blk && blk->secondaryDelta(blk1) > 0) {
2945            break;
2946          }
2947          if (blk1->isBelow(blkStack) &&
2948              (!blk || blk1->primaryCmp(blk) < 0)) {
2949            i = j;
2950            blk = blk1;
2951          }
2952        }
2953      }
2954
2955      // if a suitable block was found, add it to the flow and push it
2956      // onto the stack
2957      if (blk && flow->blockFits(blk, blkStack)) {
2958        blkArray[i] = NULL;
2959        --nBlocksLeft;
2960        blk->next = NULL;
2961        flow->addBlock(blk);
2962        fontSize = blk->lines->words->fontSize;
2963        blk->stackNext = blkStack;
2964        blkStack = blk;
2965
2966      // otherwise (if there is no block under the top block or the
2967      // block is not suitable), pop the stack
2968      } else {
2969        blkStack = blkStack->stackNext;
2970      }
2971    }
2972  }
2973  gfree(blkArray);
2974
2975#if 0 // for debugging
2976  printf("*** flows ***\n");
2977  for (flow = flows; flow; flow = flow->next) {
2978    printf("flow: x=%.2f..%.2f y=%.2f..%.2f pri:%.2f..%.2f\n",
2979           flow->xMin, flow->xMax, flow->yMin, flow->yMax,
2980           flow->priMin, flow->priMax);
2981    for (blk = flow->blocks; blk; blk = blk->next) {
2982      printf("  block: rot=%d x=%.2f..%.2f y=%.2f..%.2f pri=%.2f..%.2f\n",
2983             blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax,
2984             blk->priMin, blk->priMax);
2985      for (line = blk->lines; line; line = line->next) {
2986        printf("    line:\n");
2987        for (word0 = line->words; word0; word0 = word0->next) {
2988          printf("      word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2989                 word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2990                 word0->base, word0->fontSize, word0->spaceAfter);
2991          for (i = 0; i < word0->len; ++i) {
2992            fputc(word0->text[i] & 0xff, stdout);
2993          }
2994          printf("'\n");
2995        }
2996      }
2997    }
2998  }
2999  printf("\n");
3000#endif
3001
3002  if (uMap) {
3003    uMap->decRefCnt();
3004  }
3005}
3006
3007GBool TextPage::findText(Unicode *s, int len,
3008                         GBool startAtTop, GBool stopAtBottom,
3009                         GBool startAtLast, GBool stopAtLast,
3010                         GBool caseSensitive, GBool backward,
3011                         double *xMin, double *yMin,
3012                         double *xMax, double *yMax) {
3013  TextBlock *blk;
3014  TextLine *line;
3015  Unicode *s2, *txt;
3016  Unicode *p;
3017  int txtSize, m, i, j, k;
3018  double xStart, yStart, xStop, yStop;
3019  double xMin0, yMin0, xMax0, yMax0;
3020  double xMin1, yMin1, xMax1, yMax1;
3021  GBool found;
3022
3023  //~ needs to handle right-to-left text
3024
3025  if (rawOrder) {
3026    return gFalse;
3027  }
3028
3029  // convert the search string to uppercase
3030  if (!caseSensitive) {
3031    s2 = unicodeNormalizeNFKC(s, len, &len, NULL);
3032    for (i = 0; i < len; ++i) {
3033      s2[i] = unicodeToUpper(s2[i]);
3034    }
3035  } else {
3036    s2 = unicodeNormalizeNFKC(s, len, &len, NULL);
3037  }
3038
3039  txt = NULL;
3040  txtSize = 0;
3041
3042  xStart = yStart = xStop = yStop = 0;
3043  if (startAtLast && haveLastFind) {
3044    xStart = lastFindXMin;
3045    yStart = lastFindYMin;
3046  } else if (!startAtTop) {
3047    xStart = *xMin;
3048    yStart = *yMin;
3049  }
3050  if (stopAtLast && haveLastFind) {
3051    xStop = lastFindXMin;
3052    yStop = lastFindYMin;
3053  } else if (!stopAtBottom) {
3054    xStop = *xMax;
3055    yStop = *yMax;
3056  }
3057
3058  found = gFalse;
3059  xMin0 = xMax0 = yMin0 = yMax0 = 0; // make gcc happy
3060  xMin1 = xMax1 = yMin1 = yMax1 = 0; // make gcc happy
3061
3062  for (i = backward ? nBlocks - 1 : 0;
3063       backward ? i >= 0 : i < nBlocks;
3064       i += backward ? -1 : 1) {
3065    blk = blocks[i];
3066
3067    // check: is the block above the top limit?
3068    if (!startAtTop && (backward ? blk->yMin > yStart : blk->yMax < yStart)) {
3069      continue;
3070    }
3071
3072    // check: is the block below the bottom limit?
3073    if (!stopAtBottom && (backward ? blk->yMax < yStop : blk->yMin > yStop)) {
3074      break;
3075    }
3076
3077    for (line = blk->lines; line; line = line->next) {
3078
3079      // check: is the line above the top limit?
3080      if (!startAtTop &&
3081          (backward ? line->yMin > yStart : line->yMin < yStart)) {
3082        continue;
3083      }
3084
3085      // check: is the line below the bottom limit?
3086      if (!stopAtBottom &&
3087          (backward ? line->yMin < yStop : line->yMin > yStop)) {
3088        continue;
3089      }
3090
3091      if (!line->normalized)
3092        line->normalized = unicodeNormalizeNFKC(line->text, line->len, 
3093                                                &line->normalized_len, 
3094                                                &line->normalized_idx);
3095      // convert the line to uppercase
3096      m = line->normalized_len;
3097      if (!caseSensitive) {
3098        if (m > txtSize) {
3099          txt = (Unicode *)greallocn(txt, m, sizeof(Unicode));
3100          txtSize = m;
3101        }
3102        for (k = 0; k < m; ++k) {
3103          txt[k] = unicodeToUpper(line->normalized[k]);
3104          }
3105          } else {
3106        txt = line->normalized;
3107          }
3108
3109      // search each position in this line
3110      j = backward ? m - len : 0;
3111      p = txt + j;
3112      while (backward ? j >= 0 : j <= m - len) {
3113
3114        // compare the strings
3115        for (k = 0; k < len; ++k) {
3116          if (p[k] != s2[k]) {
3117            break;
3118          }
3119        }
3120
3121        // found it
3122        if (k == len) {
3123          // where s2 matches a subsequence of a compatibility equivalence
3124          // decomposition, highlight the entire glyph, since we don't know
3125          // the internal layout of subglyph components
3126          int normStart = line->normalized_idx[j];
3127          int normAfterEnd = line->normalized_idx[j + len - 1] + 1;
3128          switch (line->rot) {
3129          case 0:
3130            xMin1 = line->edge[normStart];
3131            xMax1 = line->edge[normAfterEnd];
3132            yMin1 = line->yMin;
3133            yMax1 = line->yMax;
3134            break;
3135          case 1:
3136            xMin1 = line->xMin;
3137            xMax1 = line->xMax;
3138            yMin1 = line->edge[normStart];
3139            yMax1 = line->edge[normAfterEnd];
3140            break;
3141          case 2:
3142            xMin1 = line->edge[normAfterEnd];
3143            xMax1 = line->edge[normStart];
3144            yMin1 = line->yMin;
3145            yMax1 = line->yMax;
3146            break;
3147          case 3:
3148            xMin1 = line->xMin;
3149            xMax1 = line->xMax;
3150            yMin1 = line->edge[normAfterEnd];
3151            yMax1 = line->edge[normStart];
3152            break;
3153          }
3154          if (backward) {
3155            if ((startAtTop ||
3156                 yMin1 < yStart || (yMin1 == yStart && xMin1 < xStart)) &&
3157                (stopAtBottom ||
3158                 yMin1 > yStop || (yMin1 == yStop && xMin1 > xStop))) {
3159              if (!found ||
3160                  yMin1 > yMin0 || (yMin1 == yMin0 && xMin1 > xMin0)) {
3161                xMin0 = xMin1;
3162                xMax0 = xMax1;
3163                yMin0 = yMin1;
3164                yMax0 = yMax1;
3165                found = gTrue;
3166              }
3167            }
3168          } else {
3169            if ((startAtTop ||
3170                 yMin1 > yStart || (yMin1 == yStart && xMin1 > xStart)) &&
3171                (stopAtBottom ||
3172                 yMin1 < yStop || (yMin1 == yStop && xMin1 < xStop))) {
3173              if (!found ||
3174                  yMin1 < yMin0 || (yMin1 == yMin0 && xMin1 < xMin0)) {
3175                xMin0 = xMin1;
3176                xMax0 = xMax1;
3177                yMin0 = yMin1;
3178                yMax0 = yMax1;
3179                found = gTrue;
3180              }
3181            }
3182          }
3183        }
3184        if (backward) {
3185          --j;
3186          --p;
3187        } else {
3188          ++j;
3189          ++p;
3190        }
3191      }
3192    }
3193    }
3194
3195  gfree(s2);
3196  if (!caseSensitive) {
3197    gfree(txt);
3198  }
3199
3200  if (found) {
3201    *xMin = xMin0;
3202    *xMax = xMax0;
3203    *yMin = yMin0;
3204    *yMax = yMax0;
3205    lastFindXMin = xMin0;
3206    lastFindYMin = yMin0;
3207    haveLastFind = gTrue;
3208    return gTrue;
3209  }
3210
3211  return gFalse;
3212}
3213
3214GooString *TextPage::getText(double xMin, double yMin,
3215                           double xMax, double yMax) {
3216  GooString *s;
3217  UnicodeMap *uMap;
3218  GBool isUnicode;
3219  TextBlock *blk;
3220  TextLine *line;
3221  TextLineFrag *frags;
3222  int nFrags, fragsSize;
3223  TextLineFrag *frag;
3224  char space[8], eol[16];
3225  int spaceLen, eolLen;
3226  int lastRot;
3227  double x, y, delta;
3228  int col, idx0, idx1, i, j;
3229  GBool multiLine, oneRot;
3230
3231  s = new GooString();
3232
3233  if (rawOrder) {
3234    return s;
3235  }
3236
3237  // get the output encoding
3238  if (!(uMap = globalParams->getTextEncoding())) {
3239    return s;
3240  }
3241  isUnicode = uMap->isUnicode();
3242  spaceLen = uMap->mapUnicode(0x20, space, sizeof(space));
3243  eolLen = 0; // make gcc happy
3244  switch (globalParams->getTextEOL()) {
3245  case eolUnix:
3246    eolLen = uMap->mapUnicode(0x0a, eol, sizeof(eol));
3247    break;
3248  case eolDOS:
3249    eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
3250    eolLen += uMap->mapUnicode(0x0a, eol + eolLen, sizeof(eol) - eolLen);
3251    break;
3252  case eolMac:
3253    eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
3254    break;
3255  }
3256
3257  //~ writing mode (horiz/vert)
3258
3259  // collect the line fragments that are in the rectangle
3260  fragsSize = 256;
3261  frags = (TextLineFrag *)gmallocn(fragsSize, sizeof(TextLineFrag));
3262  nFrags = 0;
3263  lastRot = -1;
3264  oneRot = gTrue;
3265  for (i = 0; i < nBlocks; ++i) {
3266    blk = blocks[i];
3267    if (xMin < blk->xMax && blk->xMin < xMax &&
3268        yMin < blk->yMax && blk->yMin < yMax) {
3269      for (line = blk->lines; line; line = line->next) {
3270        if (xMin < line->xMax && line->xMin < xMax &&
3271            yMin < line->yMax && line->yMin < yMax) {
3272          idx0 = idx1 = -1;
3273          switch (line->rot) {
3274          case 0:
3275            y = 0.5 * (line->yMin + line->yMax);
3276            if (yMin < y && y < yMax) {
3277              j = 0;
3278              while (j < line->len) {
3279                if (0.5 * (line->edge[j] + line->edge[j+1]) > xMin) {
3280                  idx0 = j;
3281                  break;
3282                }
3283                ++j;
3284              }
3285              j = line->len - 1;
3286              while (j >= 0) {
3287                if (0.5 * (line->edge[j] + line->edge[j+1]) < xMax) {
3288                  idx1 = j;
3289                  break;
3290                }
3291                --j;
3292              }
3293            }
3294            break;
3295          case 1:
3296            x = 0.5 * (line->xMin + line->xMax);
3297            if (xMin < x && x < xMax) {
3298              j = 0;
3299              while (j < line->len) {
3300                if (0.5 * (line->edge[j] + line->edge[j+1]) > yMin) {
3301                  idx0 = j;
3302                  break;
3303                }
3304                ++j;
3305              }
3306              j = line->len - 1;
3307              while (j >= 0) {
3308                if (0.5 * (line->edge[j] + line->edge[j+1]) < yMax) {
3309                  idx1 = j;
3310                  break;
3311                }
3312                --j;
3313              }
3314            }
3315            break;
3316          case 2:
3317            y = 0.5 * (line->yMin + line->yMax);
3318            if (yMin < y && y < yMax) {
3319              j = 0;
3320              while (j < line->len) {
3321                if (0.5 * (line->edge[j] + line->edge[j+1]) < xMax) {
3322                  idx0 = j;
3323                  break;
3324                }
3325                ++j;
3326              }
3327              j = line->len - 1;
3328              while (j >= 0) {
3329                if (0.5 * (line->edge[j] + line->edge[j+1]) > xMin) {
3330                  idx1 = j;
3331                  break;
3332                }
3333                --j;
3334              }
3335            }
3336            break;
3337          case 3:
3338            x = 0.5 * (line->xMin + line->xMax);
3339            if (xMin < x && x < xMax) {
3340              j = 0;
3341              while (j < line->len) {
3342                if (0.5 * (line->edge[j] + line->edge[j+1]) < yMax) {
3343                  idx0 = j;
3344                  break;
3345                }
3346                ++j;
3347              }
3348              j = line->len - 1;
3349              while (j >= 0) {
3350                if (0.5 * (line->edge[j] + line->edge[j+1]) > yMin) {
3351                  idx1 = j;
3352                  break;
3353                }
3354                --j;
3355              }
3356            }
3357            break;
3358          }
3359          if (idx0 >= 0 && idx1 >= 0) {
3360            if (nFrags == fragsSize) {
3361              fragsSize *= 2;
3362              frags = (TextLineFrag *)
3363                          greallocn(frags, fragsSize, sizeof(TextLineFrag));
3364            }
3365            frags[nFrags].init(line, idx0, idx1 - idx0 + 1);
3366            ++nFrags;
3367            if (lastRot >= 0 && line->rot != lastRot) {
3368              oneRot = gFalse;
3369            }
3370            lastRot = line->rot;
3371          }
3372        }
3373      }
3374    }
3375  }
3376
3377  // sort the fragments and generate the string
3378  if (nFrags > 0) {
3379
3380    for (i = 0; i < nFrags; ++i) {
3381      frags[i].computeCoords(oneRot);
3382    }
3383    assignColumns(frags, nFrags, oneRot);
3384
3385    // if all lines in the region have the same rotation, use it;
3386    // otherwise, use the page's primary rotation
3387    if (oneRot) {
3388      qsort(frags, nFrags, sizeof(TextLineFrag),
3389            &TextLineFrag::cmpYXLineRot);
3390    } else {
3391      qsort(frags, nFrags, sizeof(TextLineFrag),
3392            &TextLineFrag::cmpYXPrimaryRot);
3393    }
3394    i = 0;
3395    while (i < nFrags) {
3396      delta = maxIntraLineDelta * frags[i].line->words->fontSize;
3397      for (j = i+1;
3398           j < nFrags && fabs(frags[j].base - frags[i].base) < delta;
3399           ++j) ;
3400      qsort(frags + i, j - i, sizeof(TextLineFrag),
3401            oneRot ? &TextLineFrag::cmpXYColumnLineRot
3402                   : &TextLineFrag::cmpXYColumnPrimaryRot);
3403      i = j;
3404    }
3405
3406    col = 0;
3407    multiLine = gFalse;
3408    for (i = 0; i < nFrags; ++i) {
3409      frag = &frags[i];
3410
3411      // insert a return
3412      if (frag->col < col ||
3413          (i > 0 && fabs(frag->base - frags[i-1].base) >
3414                      maxIntraLineDelta * frags[i-1].line->words->fontSize)) {
3415        s->append(eol, eolLen);
3416        col = 0;
3417        multiLine = gTrue;
3418      }
3419
3420      // column alignment
3421      for (; col < frag->col; ++col) {
3422        s->append(space, spaceLen);
3423      }
3424
3425      // get the fragment text
3426      col += dumpFragment(frag->line->text + frag->start, frag->len, uMap, s);
3427    }
3428
3429    if (multiLine) {
3430      s->append(eol, eolLen);
3431    }
3432  }
3433
3434  gfree(frags);
3435  uMap->decRefCnt();
3436
3437  return s;
3438}
3439
3440class TextSelectionVisitor {
3441public:
3442  TextSelectionVisitor (TextPage *page);
3443  virtual ~TextSelectionVisitor () { }
3444  virtual void visitBlock (TextBlock *block,
3445                           TextLine *begin,
3446                           TextLine *end,
3447                           PDFRectangle *selection) = 0;
3448  virtual void visitLine (TextLine *line, 
3449                          TextWord *begin,
3450                          TextWord *end,
3451                          int edge_begin,
3452                          int edge_end,
3453                          PDFRectangle *selection) = 0;
3454  virtual void visitWord (TextWord *word, int begin, int end,
3455                          PDFRectangle *selection) = 0;
3456
3457protected:
3458  TextPage *page;
3459};
3460
3461TextSelectionVisitor::TextSelectionVisitor (TextPage *page)
3462  : page(page)
3463{
3464}
3465
3466
3467class TextSelectionDumper : public TextSelectionVisitor {
3468public:
3469  TextSelectionDumper(TextPage *page);
3470  virtual ~TextSelectionDumper();
3471
3472  virtual void visitBlock (TextBlock *block, 
3473                           TextLine *begin,
3474                           TextLine *end,
3475                           PDFRectangle *selection) { };
3476  virtual void visitLine (TextLine *line,
3477                          TextWord *begin,
3478                          TextWord *end,
3479                          int edge_begin,
3480                          int edge_end,
3481                          PDFRectangle *selection);
3482  virtual void visitWord (TextWord *word, int begin, int end,
3483                          PDFRectangle *selection) { };
3484
3485  GooString *getText(void);
3486
3487private:
3488  TextLineFrag *frags;
3489  int nFrags, fragsSize;
3490};
3491
3492TextSelectionDumper::TextSelectionDumper(TextPage *page)
3493    : TextSelectionVisitor(page)
3494{
3495  fragsSize = 256;
3496  frags = (TextLineFrag *)gmallocn(fragsSize, sizeof(TextLineFrag));
3497  nFrags = 0;
3498}
3499
3500TextSelectionDumper::~TextSelectionDumper()
3501{
3502  gfree(frags);
3503}
3504
3505void TextSelectionDumper::visitLine (TextLine *line,
3506                                     TextWord *begin,
3507                                     TextWord *end,
3508                                     int edge_begin,
3509                                     int edge_end,
3510                                     PDFRectangle *selection)
3511{
3512  if (nFrags == fragsSize) {
3513    fragsSize *= 2;
3514    frags = (TextLineFrag *) grealloc(frags, fragsSize * sizeof(TextLineFrag));
3515  }
3516
3517  frags[nFrags].init(line, edge_begin, edge_end - edge_begin);
3518  ++nFrags;
3519
3520}
3521
3522GooString *TextSelectionDumper::getText (void)
3523{
3524  GBool oneRot = gTrue;
3525  GooString *s;
3526  TextLineFrag *frag;
3527  int i, col;
3528  GBool multiLine;
3529  UnicodeMap *uMap;
3530  char space[8], eol[16];
3531  int spaceLen, eolLen;
3532
3533  s = new GooString();
3534
3535  uMap = globalParams->getTextEncoding();
3536
3537  if (uMap == NULL)
3538      return s;
3539
3540  spaceLen = uMap->mapUnicode(0x20, space, sizeof(space));
3541  eolLen = uMap->mapUnicode(0x0a, eol, sizeof(eol));
3542
3543  if (nFrags > 0) {
3544    for (i = 0; i < nFrags; ++i) {
3545      frags[i].computeCoords(oneRot);
3546    }
3547    page->assignColumns(frags, nFrags, oneRot);
3548
3549    // if all lines in the region have the same rotation, use it;
3550    // otherwise, use the page's primary rotation
3551    if (oneRot) {
3552      qsort(frags, nFrags, sizeof(TextLineFrag),
3553            &TextLineFrag::cmpYXLineRot);
3554    } else {
3555      qsort(frags, nFrags, sizeof(TextLineFrag),
3556            &TextLineFrag::cmpYXPrimaryRot);
3557    }
3558
3559    col = 0;
3560    multiLine = gFalse;
3561    for (i = 0; i < nFrags; ++i) {
3562      frag = &frags[i];
3563
3564      // insert a return
3565      if (frag->col < col ||
3566          (i > 0 && fabs(frag->base - frags[i-1].base) >
3567                      maxIntraLineDelta * frags[i-1].line->words->fontSize)) {
3568          s->append(eol, eolLen);
3569        col = 0;
3570        multiLine = gTrue;
3571      }
3572
3573      // column alignment
3574      for (; col < frag->col; ++col) {
3575        s->append(space, spaceLen);
3576      }
3577
3578      // get the fragment text
3579      col += page->dumpFragment(frag->line->text + frag->start, frag->len, uMap, s);
3580    }
3581
3582    if (multiLine) {
3583      s->append(eol, eolLen);
3584    }
3585  }
3586
3587  uMap->decRefCnt();
3588
3589  return s;
3590}
3591
3592class TextSelectionSizer : public TextSelectionVisitor {
3593public:
3594  TextSelectionSizer(TextPage *page, double scale);
3595  ~TextSelectionSizer() { }
3596
3597  virtual void visitBlock (TextBlock *block,
3598                           TextLine *begin,
3599                           TextLine *end,
3600                           PDFRectangle *selection) { };
3601  virtual void visitLine (TextLine *line, 
3602                          TextWord *begin,
3603                          TextWord *end,
3604                          int edge_begin,
3605                          int edge_end,
3606                          PDFRectangle *selection);
3607  virtual void visitWord (TextWord *word, int begin, int end,
3608                          PDFRectangle *selection) { };
3609
3610  GooList *getRegion () { return list; }
3611
3612private:
3613  GooList *list;
3614  double scale;
3615};
3616
3617TextSelectionSizer::TextSelectionSizer(TextPage *page, double scale)
3618  : TextSelectionVisitor(page),
3619    scale(scale)
3620{
3621  list = new GooList();
3622}
3623
3624void TextSelectionSizer::visitLine (TextLine *line, 
3625                                    TextWord *begin,
3626                                    TextWord *end,
3627                                    int edge_begin,
3628                                    int edge_end,
3629                                    PDFRectangle *selection)
3630{
3631  PDFRectangle *rect;
3632  double x1, y1, x2, y2, margin;
3633
3634  margin = (line->yMax - line->yMin) / 8;
3635  x1 = line->edge[edge_begin];
3636  y1 = line->yMin - margin;
3637  x2 = line->edge[edge_end];
3638  y2 = line->yMax + margin;
3639
3640  rect = new PDFRectangle (floor (x1 * scale), 
3641                           floor (y1 * scale),
3642                           ceil (x2 * scale),
3643                           ceil (y2 * scale));
3644  list->append (rect);
3645}
3646
3647
3648class TextSelectionPainter : public TextSelectionVisitor {
3649public:
3650  TextSelectionPainter(TextPage *page,
3651                       double scale,
3652                       int rotation,
3653                       OutputDev *out,
3654                       GfxColor *box_color,
3655                       GfxColor *glyph_color);
3656  ~TextSelectionPainter();
3657
3658  virtual void visitBlock (TextBlock *block,
3659                           TextLine *begin,
3660                           TextLine *end,
3661                           PDFRectangle *selection) { };
3662  virtual void visitLine (TextLine *line, 
3663                          TextWord *begin,
3664                          TextWord *end,
3665                          int edge_begin,
3666                          int edge_end,
3667                          PDFRectangle *selection);
3668  virtual void visitWord (TextWord *word, int begin, int end,
3669                          PDFRectangle *selection);
3670
3671private:
3672  OutputDev *out;
3673  GfxColor *box_color, *glyph_color;
3674  GfxState *state;
3675};
3676
3677TextSelectionPainter::TextSelectionPainter(TextPage *page,
3678                                           double scale,
3679                                           int rotation,
3680                                           OutputDev *out,
3681                                           GfxColor *box_color,
3682                                           GfxColor *glyph_color)
3683  : TextSelectionVisitor(page),
3684    out(out),
3685    box_color(box_color),
3686    glyph_color(glyph_color)
3687{
3688  PDFRectangle box(0, 0, page->pageWidth, page->pageHeight);
3689
3690  state = new GfxState(72 * scale, 72 * scale, &box, rotation, gFalse);
3691
3692  out->startPage (0, state);
3693  out->setDefaultCTM (state->getCTM());
3694
3695  state->setTextMat(1, 0, 0, -1, 0, 0);
3696  state->setFillColorSpace(new GfxDeviceRGBColorSpace());
3697
3698}
3699
3700TextSelectionPainter::~TextSelectionPainter()
3701{
3702  out->endPage ();
3703
3704  delete state;
3705}
3706
3707void TextSelectionPainter::visitLine (TextLine *line,
3708                                      TextWord *begin,
3709                                      TextWord *end,
3710                                      int edge_begin,
3711                                      int edge_end,
3712                                      PDFRectangle *selection)
3713{
3714  double x1, y1, x2, y2, margin;
3715  Matrix ctm, ictm;
3716
3717  state->setFillColor(box_color);
3718  out->updateFillColor(state);
3719
3720  margin = (line->yMax - line->yMin) / 8;
3721  x1 = floor (line->edge[edge_begin]);
3722  y1 = floor (line->yMin - margin);
3723  x2 = ceil (line->edge[edge_end]);
3724  y2 = ceil (line->yMax + margin);
3725
3726  state->getCTM (&ctm);
3727  ctm.transform(line->edge[edge_begin], line->yMin - margin, &x1, &y1);
3728  ctm.transform(line->edge[edge_end], line->yMax + margin, &x2, &y2);
3729
3730  x1 = floor (x1);
3731  y1 = floor (y1);
3732  x2 = ceil (x2);
3733  y2 = ceil (y2);
3734
3735  ctm.invertTo (&ictm);
3736  ictm.transform(x1, y1, &x1, &y1);
3737  ictm.transform(x2, y2, &x2, &y2);
3738
3739  state->moveTo(x1, y1);
3740  state->lineTo(x2, y1);
3741  state->lineTo(x2, y2);
3742  state->lineTo(x1, y2);
3743  state->closePath();
3744
3745  out->fill(state);
3746  state->clearPath();
3747}
3748
3749void TextSelectionPainter::visitWord (TextWord *word, int begin, int end,
3750                                      PDFRectangle *selection)
3751{
3752  GooString *string;
3753  int i;
3754
3755  state->setFillColor(glyph_color);
3756  out->updateFillColor(state);
3757  word->font->gfxFont->incRefCnt();
3758  state->setFont(word->font->gfxFont, word->fontSize);
3759  out->updateFont(state);
3760
3761  /* The only purpose of this string is to let the output device query
3762   * it's length.  Might want to change this interface later. */
3763
3764  string = new GooString ((char *) word->charcode, end - begin);
3765
3766  out->beginString(state, string);
3767
3768  for (i = begin; i < end; i++)
3769    out->drawChar(state, word->edge[i], word->base, 0, 0, 0, 0,
3770                  word->charcode[i], 1, NULL, 0);
3771 
3772  out->endString(state);
3773
3774  delete string;
3775}
3776
3777void TextWord::visitSelection(TextSelectionVisitor *visitor,
3778                              PDFRectangle *selection,
3779                              SelectionStyle style)
3780{
3781  int i, begin, end;
3782  double mid;
3783
3784  begin = len;
3785  end = 0;
3786  for (i = 0; i < len; i++) {
3787    mid = (edge[i] + edge[i + 1]) / 2;
3788    if (selection->x1 < mid || selection->x2 < mid)
3789      if (i < begin)
3790        begin = i;
3791    if (mid < selection->x1 || mid < selection->x2)
3792      end = i + 1;
3793  }
3794
3795  /* Skip empty selection. */
3796  if (end <= begin)
3797    return;
3798
3799  visitor->visitWord (this, begin, end, selection);
3800}
3801
3802void TextLine::visitSelection(TextSelectionVisitor *visitor,
3803                              PDFRectangle *selection,
3804                              SelectionStyle style) {
3805  TextWord *p, *begin, *end, *current;
3806  int i, edge_begin, edge_end;
3807  PDFRectangle child_selection;
3808
3809  begin = NULL;
3810  end = NULL;
3811  current = NULL;
3812  for (p = words; p != NULL; p = p->next) {
3813    if ((selection->x1 < p->xMax && selection->y1 < p->yMax) ||
3814        (selection->x2 < p->xMax && selection->y2 < p->yMax))
3815      if (begin == NULL) 
3816        begin = p;
3817    if (((selection->x1 > p->xMin && selection->y1 > p->yMin) ||
3818         (selection->x2 > p->xMin && selection->y2 > p->yMin)) && (begin != NULL)) {
3819      end = p->next;
3820      current = p;
3821    }
3822  }
3823
3824  if (!current)
3825    current = begin;
3826 
3827  child_selection = *selection;
3828  if (style == selectionStyleWord) {
3829    child_selection.x1 = begin ? begin->xMin : xMin;
3830    if (end && end->xMax != -1) {
3831      child_selection.x2 = current->xMax;
3832    } else {
3833      child_selection.x2 = xMax;
3834    }
3835  }
3836
3837  edge_begin = len;
3838  edge_end = 0;
3839  for (i = 0; i < len; i++) {
3840    double mid = (edge[i] + edge[i + 1]) /  2;
3841    if (child_selection.x1 < mid || child_selection.x2 < mid)
3842      if (i < edge_begin)
3843        edge_begin = i;
3844    if (mid < child_selection.x2 || mid < child_selection.x1)
3845      edge_end = i + 1;
3846  }
3847
3848  /* Skip empty selection. */
3849  if (edge_end <= edge_begin)
3850    return;
3851
3852  visitor->visitLine (this, begin, end, edge_begin, edge_end,
3853                      &child_selection);
3854
3855  for (p = begin; p != end; p = p->next)
3856    p->visitSelection (visitor, &child_selection, style);
3857}
3858
3859void TextBlock::visitSelection(TextSelectionVisitor *visitor,
3860                               PDFRectangle *selection,
3861                               SelectionStyle style) {
3862  TextLine *p, *begin, *end;
3863  PDFRectangle child_selection;
3864  double start_x, start_y, stop_x, stop_y;
3865
3866  begin = NULL;
3867  end = NULL;
3868  start_x = selection->x1;
3869  start_y = selection->y1;
3870  stop_x = selection->x2;
3871  stop_y = selection->y2;
3872 
3873  for (p = lines; p != NULL; p = p->next) {
3874    if (selection->x1 < p->xMax && selection->y1 < p->yMax && 
3875        selection->x2 < p->xMax && selection->y2 < p->yMax && begin == NULL) {
3876      begin = p;
3877      if (selection->x1 < selection->x2) {
3878        start_x = selection->x1;
3879        start_y = selection->y1;
3880        stop_x = selection->x2;
3881        stop_y = selection->y2;
3882      } else {
3883        start_x = selection->x2;
3884        start_y = selection->y2;
3885        stop_x = selection->x1;
3886        stop_y = selection->y1;
3887      }
3888    } else if (selection->x1 < p->xMax && selection->y1 < p->yMax && begin == NULL) {
3889      begin = p;
3890      start_x = selection->x1;
3891      start_y = selection->y1;
3892      stop_x = selection->x2;
3893      stop_y = selection->y2;
3894    } else if (selection->x2 < p->xMax && selection->y2 < p->yMax && begin == NULL) {
3895      begin = p;
3896      start_x = selection->x2;
3897      start_y = selection->y2;
3898      stop_x = selection->x1;
3899      stop_y = selection->y1;
3900    }
3901
3902    if (((selection->x1 > p->xMin && selection->y1 > p->yMin) ||
3903         (selection->x2 > p->xMin && selection->y2 > p->yMin))
3904        && (begin != NULL))
3905      end = p->next;
3906  }
3907
3908  /* Skip empty selection. */
3909  if (end == begin)
3910    return;
3911
3912  visitor->visitBlock (this, begin, end, selection);
3913
3914  for (p = begin; p != end; p = p->next) {
3915    if (p == begin && style != selectionStyleLine) {
3916      child_selection.x1 = start_x;
3917      child_selection.y1 = start_y;
3918    } else {
3919      child_selection.x1 = 0;
3920      child_selection.y1 = 0;
3921    }
3922    if (p->next == end && style != selectionStyleLine) {
3923      child_selection.x2 = stop_x;
3924      child_selection.y2 = stop_y;
3925    } else {
3926      child_selection.x2 = page->pageWidth;
3927      child_selection.y2 = page->pageHeight;
3928    }
3929
3930    p->visitSelection(visitor, &child_selection, style);
3931  }
3932}
3933
3934void TextPage::visitSelection(TextSelectionVisitor *visitor,
3935                              PDFRectangle *selection,
3936                              SelectionStyle style)
3937{
3938  int i, begin, end;
3939  PDFRectangle child_selection;
3940  double start_x, start_y, stop_x, stop_y;
3941  TextBlock *b;
3942
3943  begin = nBlocks;
3944  end = 0;
3945  start_x = selection->x1;
3946  start_y = selection->y1;
3947  stop_x = selection->x2;
3948  stop_y = selection->y2;
3949
3950  for (i = 0; i < nBlocks; i++) {
3951    b = blocks[i];
3952
3953    if (selection->x1 < b->xMax && selection->y1 < b->yMax &&
3954        selection->x2 < b->xMax && selection->y2 < b->yMax && i < begin) {
3955      begin = i;
3956      if (selection->y1 < selection->y2) {
3957        start_x = selection->x1;
3958        start_y = selection->y1;
3959        stop_x = selection->x2;
3960        stop_y = selection->y2;
3961      } else {
3962        start_x = selection->x2;
3963        start_y = selection->y2;
3964        stop_x = selection->x1;
3965        stop_y = selection->y1;
3966      }
3967    } else if (selection->x1 < b->xMax && selection->y1 < b->yMax && i < begin) {
3968      begin = i;
3969      start_x = selection->x1;
3970      start_y = selection->y1;
3971      stop_x = selection->x2;
3972      stop_y = selection->y2;
3973    } else if (selection->x2 < b->xMax && selection->y2 < b->yMax && i < begin) {
3974      begin = i;
3975      start_x = selection->x2;
3976      start_y = selection->y2;
3977      stop_x = selection->x1;
3978      stop_y = selection->y1;
3979    }
3980
3981    if ((selection->x1 > b->xMin && selection->y1 > b->yMin) ||
3982        (selection->x2 > b->xMin && selection->y2 > b->yMin))
3983      end = i + 1;
3984  }
3985
3986  for (i = begin; i < end; i++) {
3987    if (blocks[i]->xMin < start_x && start_x < blocks[i]->xMax &&
3988        blocks[i]->yMin < start_y && start_y < blocks[i]->yMax) {
3989      child_selection.x1 = start_x;
3990      child_selection.y1 = start_y;
3991    } else {
3992      child_selection.x1 = 0;
3993      child_selection.y1 = 0;
3994    }
3995    if (blocks[i]->xMin < stop_x && stop_x < blocks[i]->xMax &&
3996        blocks[i]->yMin < stop_y && stop_y < blocks[i]->yMax) {
3997      child_selection.x2 = stop_x;
3998      child_selection.y2 = stop_y;
3999    } else {
4000      child_selection.x2 = pageWidth;
4001      child_selection.y2 = pageHeight;
4002    }
4003
4004    blocks[i]->visitSelection(visitor, &child_selection, style);
4005  }
4006}
4007
4008void TextPage::drawSelection(OutputDev *out,
4009                             double scale,
4010                             int rotation,
4011                             PDFRectangle *selection,
4012                             SelectionStyle style,
4013                             GfxColor *glyph_color, GfxColor *box_color)
4014{
4015  TextSelectionPainter painter(this, scale, rotation, 
4016                               out, box_color, glyph_color);
4017
4018  visitSelection(&painter, selection, style);
4019}
4020
4021GooList *TextPage::getSelectionRegion(PDFRectangle *selection,
4022                                      SelectionStyle style,
4023                                      double scale) {
4024  TextSelectionSizer sizer(this, scale);
4025
4026  visitSelection(&sizer, selection, style);
4027
4028  return sizer.getRegion();
4029}
4030
4031GooString *TextPage::getSelectionText(PDFRectangle *selection,
4032                                      SelectionStyle style)
4033{
4034  TextSelectionDumper dumper(this);
4035
4036  visitSelection(&dumper, selection, style);
4037
4038  return dumper.getText();
4039}
4040
4041GBool TextPage::findCharRange(int pos, int length,
4042                              double *xMin, double *yMin,
4043                              double *xMax, double *yMax) {
4044  TextBlock *blk;
4045  TextLine *line;
4046  TextWord *word;
4047  double xMin0, xMax0, yMin0, yMax0;
4048  double xMin1, xMax1, yMin1, yMax1;
4049  GBool first;
4050  int i, j0, j1;
4051
4052  if (rawOrder) {
4053    return gFalse;
4054  }
4055
4056  //~ this doesn't correctly handle:
4057  //~ - ranges split across multiple lines (the highlighted region
4058  //~   is the bounding box of all the parts of the range)
4059  //~ - cases where characters don't convert one-to-one into Unicode
4060  first = gTrue;
4061  xMin0 = xMax0 = yMin0 = yMax0 = 0; // make gcc happy
4062  xMin1 = xMax1 = yMin1 = yMax1 = 0; // make gcc happy
4063  for (i = 0; i < nBlocks; ++i) {
4064    blk = blocks[i];
4065    for (line = blk->lines; line; line = line->next) {
4066      for (word = line->words; word; word = word->next) {
4067        if (pos < word->charPos + word->charLen &&
4068            word->charPos < pos + length) {
4069          j0 = pos - word->charPos;
4070          if (j0 < 0) {
4071            j0 = 0;
4072          }
4073          j1 = pos + length - 1 - word->charPos;
4074          if (j1 >= word->len) {
4075            j1 = word->len - 1;
4076          }
4077          switch (line->rot) {
4078          case 0:
4079            xMin1 = word->edge[j0];
4080            xMax1 = word->edge[j1 + 1];
4081            yMin1 = word->yMin;
4082            yMax1 = word->yMax;
4083            break;
4084          case 1:
4085            xMin1 = word->xMin;
4086            xMax1 = word->xMax;
4087            yMin1 = word->edge[j0];
4088            yMax1 = word->edge[j1 + 1];
4089            break;
4090          case 2:
4091            xMin1 = word->edge[j1 + 1];
4092            xMax1 = word->edge[j0];
4093            yMin1 = word->yMin;
4094            yMax1 = word->yMax;
4095            break;
4096          case 3:
4097            xMin1 = word->xMin;
4098            xMax1 = word->xMax;
4099            yMin1 = word->edge[j1 + 1];
4100            yMax1 = word->edge[j0];
4101            break;
4102          }
4103          if (first || xMin1 < xMin0) {
4104            xMin0 = xMin1;
4105          }
4106          if (first || xMax1 > xMax0) {
4107            xMax0 = xMax1;
4108          }
4109          if (first || yMin1 < yMin0) {
4110            yMin0 = yMin1;
4111          }
4112          if (first || yMax1 > yMax0) {
4113            yMax0 = yMax1;
4114          }
4115          first = gFalse;
4116        }
4117      }
4118    }
4119  }
4120  if (!first) {
4121    *xMin = xMin0;
4122    *xMax = xMax0;
4123    *yMin = yMin0;
4124    *yMax = yMax0;
4125    return gTrue;
4126  }
4127  return gFalse;
4128}
4129
4130void TextPage::dump(void *outputStream, TextOutputFunc outputFunc,
4131                    GBool physLayout) {
4132  UnicodeMap *uMap;
4133  TextFlow *flow;
4134  TextBlock *blk;
4135  TextLine *line;
4136  TextLineFrag *frags;
4137  TextWord *word;
4138  int nFrags, fragsSize;
4139  TextLineFrag *frag;
4140  char space[8], eol[16], eop[8];
4141  int spaceLen, eolLen, eopLen;
4142  GBool pageBreaks;
4143  GooString *s;
4144  double delta;
4145  int col, i, j, d, n;
4146
4147  // get the output encoding
4148  if (!(uMap = globalParams->getTextEncoding())) {
4149    return;
4150  }
4151  spaceLen = uMap->mapUnicode(0x20, space, sizeof(space));
4152  eolLen = 0; // make gcc happy
4153  switch (globalParams->getTextEOL()) {
4154  case eolUnix:
4155    eolLen = uMap->mapUnicode(0x0a, eol, sizeof(eol));
4156    break;
4157  case eolDOS:
4158    eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
4159    eolLen += uMap->mapUnicode(0x0a, eol + eolLen, sizeof(eol) - eolLen);
4160    break;
4161  case eolMac:
4162    eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
4163    break;
4164  }
4165  eopLen = uMap->mapUnicode(0x0c, eop, sizeof(eop));
4166  pageBreaks = globalParams->getTextPageBreaks();
4167
4168  //~ writing mode (horiz/vert)
4169
4170  // output the page in raw (content stream) order
4171  if (rawOrder) {
4172
4173    for (word = rawWords; word; word = word->next) {
4174      s = new GooString();
4175      dumpFragment(word->text, word->len, uMap, s);
4176      (*outputFunc)(outputStream, s->getCString(), s->getLength());
4177      delete s;
4178      if (word->next &&
4179          fabs(word->next->base - word->base) <
4180            maxIntraLineDelta * word->fontSize) {
4181        if (word->next->xMin > word->xMax + minWordSpacing * word->fontSize) {
4182          (*outputFunc)(outputStream, space, spaceLen);
4183        }
4184      } else {
4185        (*outputFunc)(outputStream, eol, eolLen);
4186      }
4187    }
4188
4189  // output the page, maintaining the original physical layout
4190  } else if (physLayout) {
4191
4192    // collect the line fragments for the page and sort them
4193    fragsSize = 256;
4194    frags = (TextLineFrag *)gmallocn(fragsSize, sizeof(TextLineFrag));
4195    nFrags = 0;
4196    for (i = 0; i < nBlocks; ++i) {
4197      blk = blocks[i];
4198      for (line = blk->lines; line; line = line->next) {
4199        if (nFrags == fragsSize) {
4200          fragsSize *= 2;
4201          frags = (TextLineFrag *)greallocn(frags,
4202                                            fragsSize, sizeof(TextLineFrag));
4203        }
4204        frags[nFrags].init(line, 0, line->len);
4205        frags[nFrags].computeCoords(gTrue);
4206        ++nFrags;
4207      }
4208    }
4209    qsort(frags, nFrags, sizeof(TextLineFrag), &TextLineFrag::cmpYXPrimaryRot);
4210    i = 0;
4211    while (i < nFrags) {
4212      delta = maxIntraLineDelta * frags[i].line->words->fontSize;
4213      for (j = i+1;
4214           j < nFrags && fabs(frags[j].base - frags[i].base) < delta;
4215           ++j) ;
4216      qsort(frags + i, j - i, sizeof(TextLineFrag),
4217            &TextLineFrag::cmpXYColumnPrimaryRot);
4218      i = j;
4219    }
4220
4221#if 0 // for debugging
4222    printf("*** line fragments ***\n");
4223    for (i = 0; i < nFrags; ++i) {
4224      frag = &frags[i];
4225      printf("frag: x=%.2f..%.2f y=%.2f..%.2f base=%.2f '",
4226             frag->xMin, frag->xMax, frag->yMin, frag->yMax, frag->base);
4227      for (n = 0; n < frag->len; ++n) {
4228        fputc(frag->line->text[frag->start + n] & 0xff, stdout);
4229      }
4230      printf("'\n");
4231    }
4232    printf("\n");
4233#endif
4234
4235    // generate output
4236    col = 0;
4237    for (i = 0; i < nFrags; ++i) {
4238      frag = &frags[i];
4239
4240      // column alignment
4241      for (; col < frag->col; ++col) {
4242        (*outputFunc)(outputStream, space, spaceLen);
4243      }
4244
4245      // print the line
4246      s = new GooString();
4247      col += dumpFragment(frag->line->text + frag->start, frag->len, uMap, s);
4248      (*outputFunc)(outputStream, s->getCString(), s->getLength());
4249      delete s;
4250
4251      // print one or more returns if necessary
4252      if (i == nFrags - 1 ||
4253          frags[i+1].col < col ||
4254          fabs(frags[i+1].base - frag->base) >
4255            maxIntraLineDelta * frag->line->words->fontSize) {
4256        if (i < nFrags - 1) {
4257          d = (int)((frags[i+1].base - frag->base) /
4258                    frag->line->words->fontSize);
4259          if (d < 1) {
4260            d = 1;
4261          } else if (d > 5) {
4262            d = 5;
4263          }
4264        } else {
4265          d = 1;
4266        }
4267        for (; d > 0; --d) {
4268          (*outputFunc)(outputStream, eol, eolLen);
4269        }
4270        col = 0;
4271      }
4272    }
4273
4274    gfree(frags);
4275
4276  // output the page, "undoing" the layout
4277  } else {
4278    for (flow = flows; flow; flow = flow->next) {
4279      for (blk = flow->blocks; blk; blk = blk->next) {
4280        for (line = blk->lines; line; line = line->next) {
4281          n = line->len;
4282          if (line->hyphenated && (line->next || blk->next)) {
4283            --n;
4284          }
4285          s = new GooString();
4286          dumpFragment(line->text, n, uMap, s);
4287          (*outputFunc)(outputStream, s->getCString(), s->getLength());
4288          delete s;
4289          if (!line->hyphenated) {
4290            if (line->next) {
4291              (*outputFunc)(outputStream, space, spaceLen);
4292            } else if (blk->next) {
4293              //~ this is a bit of a kludge - we should really do a more
4294              //~ intelligent determination of paragraphs
4295              if (blk->next->lines->words->fontSize ==
4296                  blk->lines->words->fontSize) {
4297                (*outputFunc)(outputStream, space, spaceLen);
4298              } else {
4299                (*outputFunc)(outputStream, eol, eolLen);
4300              }
4301            }
4302          }
4303        }
4304      }
4305      (*outputFunc)(outputStream, eol, eolLen);
4306      (*outputFunc)(outputStream, eol, eolLen);
4307    }
4308  }
4309
4310  // end of page
4311  if (pageBreaks) {
4312    (*outputFunc)(outputStream, eop, eopLen);
4313  }
4314
4315  uMap->decRefCnt();
4316}
4317
4318void TextPage::assignColumns(TextLineFrag *frags, int nFrags, GBool oneRot) {
4319  TextLineFrag *frag0, *frag1;
4320  int rot, col1, col2, i, j, k;
4321
4322  // all text in the region has the same rotation -- recompute the
4323  // column numbers based only on the text in the region
4324  if (oneRot) {
4325    qsort(frags, nFrags, sizeof(TextLineFrag), &TextLineFrag::cmpXYLineRot);
4326    rot = frags[0].line->rot;
4327    for (i = 0; i < nFrags; ++i) {
4328      frag0 = &frags[i];
4329      col1 = 0;
4330      for (j = 0; j < i; ++j) {
4331        frag1 = &frags[j];
4332        col2 = 0; // make gcc happy
4333        switch (rot) {
4334        case 0:
4335          if (frag0->xMin >= frag1->xMax) {
4336            col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
4337                                 frag1->line->col[frag1->start]) + 1;
4338          } else {
4339            for (k = frag1->start;
4340                 k < frag1->start + frag1->len &&
4341                   frag0->xMin >= 0.5 * (frag1->line->edge[k] +
4342                                         frag1->line->edge[k+1]);
4343                 ++k) ;
4344            col2 = frag1->col +
4345                   frag1->line->col[k] - frag1->line->col[frag1->start];
4346          }
4347          break;
4348        case 1:
4349          if (frag0->yMin >= frag1->yMax) {
4350            col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
4351                                 frag1->line->col[frag1->start]) + 1;
4352          } else {
4353            for (k = frag1->start;
4354                 k < frag1->start + frag1->len &&
4355                   frag0->yMin >= 0.5 * (frag1->line->edge[k] +
4356                                         frag1->line->edge[k+1]);
4357                 ++k) ;
4358            col2 = frag1->col +
4359                   frag1->line->col[k] - frag1->line->col[frag1->start];
4360          }
4361          break;
4362        case 2:
4363          if (frag0->xMax <= frag1->xMin) {
4364            col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
4365                                 frag1->line->col[frag1->start]) + 1;
4366          } else {
4367            for (k = frag1->start;
4368                 k < frag1->start + frag1->len &&
4369                   frag0->xMax <= 0.5 * (frag1->line->edge[k] +
4370                                         frag1->line->edge[k+1]);
4371                 ++k) ;
4372            col2 = frag1->col +
4373                   frag1->line->col[k] - frag1->line->col[frag1->start];
4374          }
4375          break;
4376        case 3:
4377          if (frag0->yMax <= frag1->yMin) {
4378            col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
4379                                 frag1->line->col[frag1->start]) + 1;
4380          } else {
4381            for (k = frag1->start;
4382                 k < frag1->start + frag1->len &&
4383                   frag0->yMax <= 0.5 * (frag1->line->edge[k] +
4384                                         frag1->line->edge[k+1]);
4385                 ++k) ;
4386            col2 = frag1->col +
4387                   frag1->line->col[k] - frag1->line->col[frag1->start];
4388          }
4389          break;
4390        }
4391        if (col2 > col1) {
4392          col1 = col2;
4393        }
4394      }
4395      frag0->col = col1;
4396    }
4397
4398  // the region includes text at different rotations -- use the
4399  // globally assigned column numbers, offset by the minimum column
4400  // number (i.e., shift everything over to column 0)
4401  } else {
4402    col1 = frags[0].col;
4403    for (i = 1; i < nFrags; ++i) {
4404      if (frags[i].col < col1) {
4405        col1 = frags[i].col;
4406      }
4407    }
4408    for (i = 0; i < nFrags; ++i) {
4409      frags[i].col -= col1;
4410    }
4411  }
4412}
4413
4414int TextPage::dumpFragment(Unicode *text, int len, UnicodeMap *uMap,
4415                           GooString *s) {
4416  char lre[8], rle[8], popdf[8], buf[8];
4417  int lreLen, rleLen, popdfLen, n;
4418  int nCols, i, j, k;
4419
4420  nCols = 0;
4421
4422  if (uMap->isUnicode()) {
4423
4424    lreLen = uMap->mapUnicode(0x202a, lre, sizeof(lre));
4425    rleLen = uMap->mapUnicode(0x202b, rle, sizeof(rle));
4426    popdfLen = uMap->mapUnicode(0x202c, popdf, sizeof(popdf));
4427
4428    if (primaryLR) {
4429
4430      i = 0;
4431      while (i < len) {
4432        // output a left-to-right section
4433        for (j = i; j < len && !unicodeTypeR(text[j]); ++j) ;
4434        for (k = i; k < j; ++k) {
4435          n = uMap->mapUnicode(text[k], buf, sizeof(buf));
4436          s->append(buf, n);
4437          ++nCols;
4438        }
4439        i = j;
4440        // output a right-to-left section
4441        for (j = i; j < len && !unicodeTypeL(text[j]); ++j) ;
4442        if (j > i) {
4443          s->append(rle, rleLen);
4444          for (k = j - 1; k >= i; --k) {
4445            n = uMap->mapUnicode(text[k], buf, sizeof(buf));
4446            s->append(buf, n);
4447            ++nCols;
4448          }
4449          s->append(popdf, popdfLen);
4450          i = j;
4451        }
4452      }
4453
4454    } else {
4455
4456      s->append(rle, rleLen);
4457      i = len - 1;
4458      while (i >= 0) {
4459        // output a right-to-left section
4460        for (j = i; j >= 0 && !unicodeTypeL(text[j]); --j) ;
4461        for (k = i; k > j; --k) {
4462          n = uMap->mapUnicode(text[k], buf, sizeof(buf));
4463          s->append(buf, n);
4464          ++nCols;
4465        }
4466        i = j;
4467        // output a left-to-right section
4468        for (j = i; j >= 0 && !unicodeTypeR(text[j]); --j) ;
4469        if (j < i) {
4470          s->append(lre, lreLen);
4471          for (k = j + 1; k <= i; ++k) {
4472            n = uMap->mapUnicode(text[k], buf, sizeof(buf));
4473            s->append(buf, n);
4474            ++nCols;
4475          }
4476          s->append(popdf, popdfLen);
4477          i = j;
4478        }
4479      }
4480      s->append(popdf, popdfLen);
4481
4482    }
4483
4484  } else {
4485    for (i = 0; i < len; ++i) {
4486      n = uMap->mapUnicode(text[i], buf, sizeof(buf));
4487      s->append(buf, n);
4488      nCols += n;
4489    }
4490  }
4491
4492  return nCols;
4493}
4494
4495#if TEXTOUT_WORD_LIST
4496TextWordList *TextPage::makeWordList(GBool physLayout) {
4497  return new TextWordList(this, physLayout);
4498}
4499#endif
4500
4501//------------------------------------------------------------------------
4502// ActualText
4503//------------------------------------------------------------------------
4504ActualText::ActualText(TextPage *out) {
4505  out->incRefCnt();
4506  text = out;
4507  actualText = NULL;
4508  actualTextBMCLevel = 0;
4509}
4510
4511ActualText::~ActualText() {
4512  if (actualText)
4513    delete actualText;
4514  text->decRefCnt();
4515}
4516
4517void ActualText::addChar(GfxState *state, double x, double y,
4518                         double dx, double dy,
4519                         CharCode c, int nBytes, Unicode *u, int uLen) {
4520  if (actualTextBMCLevel == 0) {
4521    text->addChar(state, x, y, dx, dy, c, nBytes, u, uLen);
4522  } else {
4523    // Inside ActualText span.
4524    if (newActualTextSpan) {
4525      actualText_x = x;
4526      actualText_y = y;
4527      actualText_dx = dx;
4528      actualText_dy = dy;
4529      newActualTextSpan = gFalse;
4530    } else {
4531      if (x < actualText_x)
4532        actualText_x = x;
4533      if (y < actualText_y)
4534        actualText_y = y;
4535      if (x + dx > actualText_x + actualText_dx)
4536        actualText_dx = x + dx - actualText_x;
4537      if (y + dy > actualText_y + actualText_dy)
4538        actualText_dy = y + dy - actualText_y;
4539    }
4540  }
4541}
4542
4543void ActualText::beginMC(Dict *properties) {
4544  if (actualTextBMCLevel > 0) {
4545    // Already inside a ActualText span.
4546    actualTextBMCLevel++;
4547    return;
4548  }
4549
4550  Object obj;
4551  if (properties->lookup("ActualText", &obj)) {
4552    if (obj.isString()) {
4553      actualText = obj.getString();
4554      actualTextBMCLevel = 1;
4555      newActualTextSpan = gTrue;
4556    }
4557  }
4558}
4559
4560void ActualText::endMC(GfxState *state) {
4561  char *uniString = NULL;
4562  Unicode *uni;
4563  int length, i;
4564
4565  if (actualTextBMCLevel > 0) {
4566    actualTextBMCLevel--;
4567    if (actualTextBMCLevel == 0) {
4568      // ActualText span closed. Output the span text and the
4569      // extents of all the glyphs inside the span
4570
4571      if (newActualTextSpan) {
4572        // No content inside span.
4573        actualText_x = state->getCurX();
4574        actualText_y = state->getCurY();
4575        actualText_dx = 0;
4576        actualText_dy = 0;
4577      }
4578
4579      if (!actualText->hasUnicodeMarker()) {
4580        if (actualText->getLength() > 0) {
4581          //non-unicode string -- assume pdfDocEncoding and
4582          //try to convert to UTF16BE
4583          uniString = pdfDocEncodingToUTF16(actualText, &length);
4584        } else {
4585          length = 0;
4586        }
4587      } else {
4588        uniString = actualText->getCString();
4589        length = actualText->getLength();
4590      }
4591
4592      if (length < 3)
4593        length = 0;
4594      else
4595        length = length/2 - 1;
4596      uni = new Unicode[length];
4597      for (i = 0 ; i < length; i++)
4598        uni[i] = ((uniString[2 + i*2] & 0xff)<<8)|(uniString[3 + i*2] & 0xff);
4599
4600      text->addChar(state,
4601                    actualText_x, actualText_y,
4602                    actualText_dx, actualText_dy,
4603                    0, 1, uni, length);
4604
4605      delete [] uni;
4606      if (!actualText->hasUnicodeMarker())
4607        delete [] uniString;
4608      delete actualText;
4609      actualText = NULL;
4610    }
4611  }
4612}
4613
4614//------------------------------------------------------------------------
4615// TextOutputDev
4616//------------------------------------------------------------------------
4617
4618static void TextOutputDev_outputToFile(void *stream, char *text, int len) {
4619  fwrite(text, 1, len, (FILE *)stream);
4620}
4621
4622TextOutputDev::TextOutputDev(char *fileName, GBool physLayoutA,
4623                             GBool rawOrderA, GBool append) {
4624  text = NULL;
4625  physLayout = physLayoutA;
4626  rawOrder = rawOrderA;
4627  doHTML = gFalse;
4628  ok = gTrue;
4629
4630  // open file
4631  needClose = gFalse;
4632  if (fileName) {
4633    if (!strcmp(fileName, "-")) {
4634      outputStream = stdout;
4635#ifdef _WIN32
4636      // keep DOS from munging the end-of-line characters
4637      setmode(fileno(stdout), O_BINARY);
4638#endif
4639    } else if ((outputStream = fopen(fileName, append ? "ab" : "wb"))) {
4640      needClose = gTrue;
4641    } else {
4642      error(-1, "Couldn't open text file '%s'", fileName);
4643      ok = gFalse;
4644      return;
4645    }
4646    outputFunc = &TextOutputDev_outputToFile;
4647  } else {
4648    outputStream = NULL;
4649  }
4650
4651  // set up text object
4652  text = new TextPage(rawOrderA);
4653  actualText = new ActualText(text);
4654}
4655
4656TextOutputDev::TextOutputDev(TextOutputFunc func, void *stream,
4657                             GBool physLayoutA, GBool rawOrderA) {
4658  outputFunc = func;
4659  outputStream = stream;
4660  needClose = gFalse;
4661  physLayout = physLayoutA;
4662  rawOrder = rawOrderA;
4663  doHTML = gFalse;
4664  text = new TextPage(rawOrderA);
4665  actualText = new ActualText(text);
4666  ok = gTrue;
4667}
4668
4669TextOutputDev::~TextOutputDev() {
4670  if (needClose) {
4671#ifdef MACOS
4672    ICS_MapRefNumAndAssign((short)((FILE *)outputStream)->handle);
4673#endif
4674    fclose((FILE *)outputStream);
4675  }
4676  if (text) {
4677    text->decRefCnt();
4678  }
4679  delete actualText;
4680}
4681
4682void TextOutputDev::startPage(int pageNum, GfxState *state) {
4683  text->startPage(state);
4684}
4685
4686void TextOutputDev::endPage() {
4687  text->endPage();
4688  text->coalesce(physLayout, doHTML);
4689  if (outputStream) {
4690    text->dump(outputStream, outputFunc, physLayout);
4691  }
4692}
4693
4694void TextOutputDev::updateFont(GfxState *state) {
4695  text->updateFont(state);
4696}
4697
4698void TextOutputDev::beginString(GfxState *state, GooString *s) {
4699}
4700
4701void TextOutputDev::endString(GfxState *state) {
4702}
4703
4704void TextOutputDev::drawChar(GfxState *state, double x, double y,
4705                             double dx, double dy,
4706                             double originX, double originY,
4707                             CharCode c, int nBytes, Unicode *u, int uLen) {
4708  actualText->addChar(state, x, y, dx, dy, c, nBytes, u, uLen);
4709}
4710
4711void TextOutputDev::beginMarkedContent(char *name, Dict *properties)
4712{
4713  actualText->beginMC(properties);
4714}
4715
4716void TextOutputDev::endMarkedContent(GfxState *state)
4717{
4718  actualText->endMC(state);
4719}
4720
4721void TextOutputDev::stroke(GfxState *state) {
4722  GfxPath *path;
4723  GfxSubpath *subpath;
4724  double x[2], y[2];
4725
4726  if (!doHTML) {
4727    return;
4728  }
4729  path = state->getPath();
4730  if (path->getNumSubpaths() != 1) {
4731    return;
4732  }
4733  subpath = path->getSubpath(0);
4734  if (subpath->getNumPoints() != 2) {
4735    return;
4736  }
4737  state->transform(subpath->getX(0), subpath->getY(0), &x[0], &y[0]);
4738  state->transform(subpath->getX(1), subpath->getY(1), &x[1], &y[1]);
4739
4740  // look for a vertical or horizontal line
4741  if (x[0] == x[1] || y[0] == y[1]) {
4742    text->addUnderline(x[0], y[0], x[1], y[1]);
4743  }
4744}
4745
4746void TextOutputDev::fill(GfxState *state) {
4747  GfxPath *path;
4748  GfxSubpath *subpath;
4749  double x[5], y[5];
4750  double rx0, ry0, rx1, ry1, t;
4751  int i;
4752
4753  if (!doHTML) {
4754    return;
4755  }
4756  path = state->getPath();
4757  if (path->getNumSubpaths() != 1) {
4758    return;
4759  }
4760  subpath = path->getSubpath(0);
4761  if (subpath->getNumPoints() != 5) {
4762    return;
4763  }
4764  for (i = 0; i < 5; ++i) {
4765    if (subpath->getCurve(i)) {
4766      return;
4767    }
4768    state->transform(subpath->getX(i), subpath->getY(i), &x[i], &y[i]);
4769  }
4770
4771  // look for a rectangle
4772  if (x[0] == x[1] && y[1] == y[2] && x[2] == x[3] && y[3] == y[4] &&
4773      x[0] == x[4] && y[0] == y[4]) {
4774    rx0 = x[0];
4775    ry0 = y[0];
4776    rx1 = x[2];
4777    ry1 = y[1];
4778  } else if (y[0] == y[1] && x[1] == x[2] && y[2] == y[3] && x[3] == x[4] &&
4779             x[0] == x[4] && y[0] == y[4]) {
4780    rx0 = x[0];
4781    ry0 = y[0];
4782    rx1 = x[1];
4783    ry1 = y[2];
4784  } else {
4785    return;
4786  }
4787  if (rx1 < rx0) {
4788    t = rx0;
4789    rx0 = rx1;
4790    rx1 = t;
4791  }
4792  if (ry1 < ry0) {
4793    t = ry0;
4794    ry0 = ry1;
4795    ry1 = t;
4796  }
4797
4798  // skinny horizontal rectangle
4799  if (ry1 - ry0 < rx1 - rx0) {
4800    if (ry1 - ry0 < maxUnderlineWidth) {
4801      ry0 = 0.5 * (ry0 + ry1);
4802      text->addUnderline(rx0, ry0, rx1, ry0);
4803    }
4804
4805  // skinny vertical rectangle
4806  } else {
4807    if (rx1 - rx0 < maxUnderlineWidth) {
4808      rx0 = 0.5 * (rx0 + rx1);
4809      text->addUnderline(rx0, ry0, rx0, ry1);
4810    }
4811  }
4812}
4813
4814void TextOutputDev::eoFill(GfxState *state) {
4815  if (!doHTML) {
4816    return;
4817  }
4818  fill(state);
4819}
4820
4821void TextOutputDev::processLink(Link *link, Catalog * /*catalog*/) {
4822  double x1, y1, x2, y2;
4823  int xMin, yMin, xMax, yMax, x, y;
4824
4825  if (!doHTML) {
4826    return;
4827  }
4828  link->getRect(&x1, &y1, &x2, &y2);
4829  cvtUserToDev(x1, y1, &x, &y);
4830  xMin = xMax = x;
4831  yMin = yMax = y;
4832  cvtUserToDev(x1, y2, &x, &y);
4833  if (x < xMin) {
4834    xMin = x;
4835  } else if (x > xMax) {
4836    xMax = x;
4837  }
4838  if (y < yMin) {
4839    yMin = y;
4840  } else if (y > yMax) {
4841    yMax = y;
4842  }
4843  cvtUserToDev(x2, y1, &x, &y);
4844  if (x < xMin) {
4845    xMin = x;
4846  } else if (x > xMax) {
4847    xMax = x;
4848  }
4849  if (y < yMin) {
4850    yMin = y;
4851  } else if (y > yMax) {
4852    yMax = y;
4853  }
4854  cvtUserToDev(x2, y2, &x, &y);
4855  if (x < xMin) {
4856    xMin = x;
4857  } else if (x > xMax) {
4858    xMax = x;
4859  }
4860  if (y < yMin) {
4861    yMin = y;
4862  } else if (y > yMax) {
4863    yMax = y;
4864  }
4865  text->addLink(xMin, yMin, xMax, yMax, link);
4866}
4867
4868GBool TextOutputDev::findText(Unicode *s, int len,
4869                              GBool startAtTop, GBool stopAtBottom,
4870                              GBool startAtLast, GBool stopAtLast,
4871                              GBool caseSensitive, GBool backward,
4872                              double *xMin, double *yMin,
4873                              double *xMax, double *yMax) {
4874  return text->findText(s, len, startAtTop, stopAtBottom,
4875                        startAtLast, stopAtLast, caseSensitive, backward,
4876                        xMin, yMin, xMax, yMax);
4877}
4878
4879GooString *TextOutputDev::getText(double xMin, double yMin,
4880                                double xMax, double yMax) {
4881  return text->getText(xMin, yMin, xMax, yMax);
4882}
4883
4884void TextOutputDev::drawSelection(OutputDev *out,
4885                                  double scale,
4886                                  int rotation,
4887                                  PDFRectangle *selection,
4888                                  SelectionStyle style,
4889                                  GfxColor *glyph_color, GfxColor *box_color) {
4890  text->drawSelection(out, scale, rotation, selection, style, glyph_color, box_color);
4891}
4892
4893GooList *TextOutputDev::getSelectionRegion(PDFRectangle *selection,
4894                                           SelectionStyle style,
4895                                           double scale) {
4896  return text->getSelectionRegion(selection, style, scale);
4897}
4898
4899GooString *TextOutputDev::getSelectionText(PDFRectangle *selection,
4900                                           SelectionStyle style)
4901{
4902  return text->getSelectionText(selection, style);
4903}
4904
4905GBool TextOutputDev::findCharRange(int pos, int length,
4906                                   double *xMin, double *yMin,
4907                                   double *xMax, double *yMax) {
4908  return text->findCharRange(pos, length, xMin, yMin, xMax, yMax);
4909}
4910
4911#if TEXTOUT_WORD_LIST
4912TextWordList *TextOutputDev::makeWordList() {
4913  return text->makeWordList(physLayout);
4914}
4915#endif
4916
4917TextPage *TextOutputDev::takeText() {
4918  TextPage *ret;
4919
4920  ret = text;
4921  text = new TextPage(rawOrder);
4922  return ret;
4923}
Note: See TracBrowser for help on using the repository browser.