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

Last change on this file since 261 was 261, checked in by Eugene Romanenko, 13 years ago

PDF plugin: Poppler library updated to version 0.10.2

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