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

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

PDF plugin: Poppler library updated to version 0.10.0

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