pdf/xpdf/TextOutputDev.cc

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