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

Last change on this file since 134 was 134, checked in by Eugene Romanenko, 15 years ago

poppler updated to version 0.5.4

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