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

Last change on this file since 2 was 2, checked in by Eugene Romanenko, 16 years ago

First import

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