Scroll at the top of the page when changing page

[evince.git] / pdf / xpdf / TextOutputDev.cc

diff --git a/pdf/xpdf/TextOutputDev.cc b/pdf/xpdf/TextOutputDev.cc
index 891752cc7df1a84982b38a2cf22fb972c4e667fe..a492e7f3e178c2b1c4d90bb2953af97059acacb8 100644 (file)
--- a/pdf/xpdf/TextOutputDev.cc
+++ b/pdf/xpdf/TextOutputDev.cc
@@ -2,7 +2,7 @@
 //
 // TextOutputDev.cc
 //
 //
 // TextOutputDev.cc
 //

-// Copyright 1997-2002 Glyph & Cog, LLC
+// Copyright 1997-2003 Glyph & Cog, LLC

 //
 //========================================================================
 
 //
 //========================================================================
 


@@ -17,12 +17,18 @@
 #include <stddef.h>
 #include <math.h>
 #include <ctype.h>
 #include <stddef.h>
 #include <math.h>
 #include <ctype.h>

-#include "GString.h"
+#ifdef WIN32
+#include <fcntl.h> // for O_BINARY
+#include <io.h>    // for setmode
+#endif

 #include "gmem.h"
 #include "gmem.h"

-#include "config.h"
+#include "GString.h"
+#include "GList.h"
+#include "xpdfconfig.h"

 #include "Error.h"
 #include "GlobalParams.h"
 #include "UnicodeMap.h"
 #include "Error.h"
 #include "GlobalParams.h"
 #include "UnicodeMap.h"

+#include "UnicodeTypeTable.h"

 #include "GfxState.h"
 #include "TextOutputDev.h"
 
 #include "GfxState.h"
 #include "TextOutputDev.h"
 


@@ -31,173 +37,1683 @@
 #include "ICSupport.h"
 #endif
 
 #include "ICSupport.h"
 #endif
 

+//------------------------------------------------------------------------
+// parameters

 //------------------------------------------------------------------------
 
 //------------------------------------------------------------------------
 

-#define textOutSpace    0.2
-#define textOutColSpace 0.2
+// Each bucket in a text pool includes baselines within a range of
+// this many points.
+#define textPoolStep 4
+
+// Inter-character space width which will cause addChar to start a new
+// word.
+#define minWordBreakSpace 0.1
+
+// Negative inter-character space width, i.e., overlap, which will
+// cause addChar to start a new word.
+#define minDupBreakOverlap 0.2
+
+// Max distance between baselines of two lines within a block, as a
+// fraction of the font size.
+#define maxLineSpacingDelta 1.5
+
+// Max difference in primary font sizes on two lines in the same
+// block.  Delta1 is used when examining new lines above and below the
+// current block; delta2 is used when examining text that overlaps the
+// current block; delta3 is used when examining text to the left and
+// right of the current block.
+#define maxBlockFontSizeDelta1 0.05
+#define maxBlockFontSizeDelta2 0.6
+#define maxBlockFontSizeDelta3 0.2
+
+// Max difference in font sizes inside a word.
+#define maxWordFontSizeDelta 0.05
+
+// Maximum distance between baselines of two words on the same line,
+// e.g., distance between subscript or superscript and the primary
+// baseline, as a fraction of the font size.
+#define maxIntraLineDelta 0.5
+
+// Minimum inter-word spacing, as a fraction of the font size.  (Only
+// used for raw ordering.)
+#define minWordSpacing 0.15
+
+// Maximum inter-word spacing, as a fraction of the font size.
+#define maxWordSpacing 1.5
+
+// Maximum horizontal spacing which will allow a word to be pulled
+// into a block.
+#define minColSpacing1 0.3
+
+// Minimum spacing between columns, as a fraction of the font size.
+#define minColSpacing2 1.0
+
+// Maximum vertical spacing between blocks within a flow, as a
+// multiple of the font size.
+#define maxBlockSpacing 2.5
+
+// Minimum spacing between characters within a word, as a fraction of
+// the font size.
+#define minCharSpacing -0.2
+
+// Maximum spacing between characters within a word, as a fraction of
+// the font size, when there is no obvious extra-wide character
+// spacing.
+#define maxCharSpacing 0.03
+
+// When extra-wide character spacing is detected, the inter-character
+// space threshold is set to the minimum inter-character space
+// multiplied by this constant.
+#define maxWideCharSpacingMul 1.3
+
+// Max difference in primary,secondary coordinates (as a fraction of
+// the font size) allowed for duplicated text (fake boldface, drop
+// shadows) which is to be discarded.
+#define dupMaxPriDelta 0.1
+#define dupMaxSecDelta 0.2

 
 

+//------------------------------------------------------------------------
+// TextFontInfo

 //------------------------------------------------------------------------
 
 //------------------------------------------------------------------------
 

-struct TextOutColumnEdge {
-  double x, y0, y1;
-};
+TextFontInfo::TextFontInfo(GfxState *state) {
+  gfxFont = state->getFont();
+#if TEXTOUT_WORD_LIST
+  fontName = (gfxFont && gfxFont->getOrigName())
+                 ? gfxFont->getOrigName()->copy()
+                 : (GString *)NULL;
+#endif
+}
+
+TextFontInfo::~TextFontInfo() {
+#if TEXTOUT_WORD_LIST
+  if (fontName) {
+    delete fontName;
+  }
+#endif
+}
+
+GBool TextFontInfo::matches(GfxState *state) {
+  return state->getFont() == gfxFont;
+}

 
 //------------------------------------------------------------------------
 
 //------------------------------------------------------------------------

-// TextBlock
+// TextWord

 //------------------------------------------------------------------------
 
 //------------------------------------------------------------------------
 

-class TextBlock {
-public:
+TextWord::TextWord(GfxState *state, int rotA, double x0, double y0,
+                  int charPosA, TextFontInfo *fontA, double fontSizeA) {
+  GfxFont *gfxFont;
+  double x, y, ascent, descent;

 
 

-  TextBlock();
-  ~TextBlock();
+  rot = rotA;
+  charPos = charPosA;
+  charLen = 0;
+  font = fontA;
+  fontSize = fontSizeA;
+  state->transform(x0, y0, &x, &y);
+  if ((gfxFont = font->gfxFont)) {
+    ascent = gfxFont->getAscent() * fontSize;
+    descent = gfxFont->getDescent() * fontSize;
+  } else {
+    // this means that the PDF file draws text without a current font,
+    // which should never happen
+    ascent = 0.95 * fontSize;
+    descent = -0.35 * fontSize;
+  }
+  switch (rot) {
+  case 0:
+    yMin = y - ascent;
+    yMax = y - descent;
+    if (yMin == yMax) {
+      // this is a sanity check for a case that shouldn't happen -- but
+      // if it does happen, we want to avoid dividing by zero later
+      yMin = y;
+      yMax = y + 1;
+    }
+    base = y;
+    break;
+  case 1:
+    xMin = x + descent;
+    xMax = x + ascent;
+    if (xMin == xMax) {
+      // this is a sanity check for a case that shouldn't happen -- but
+      // if it does happen, we want to avoid dividing by zero later
+      xMin = x;
+      xMax = x + 1;
+    }
+    base = x;
+    break;
+  case 2:
+    yMin = y + descent;
+    yMax = y + ascent;
+    if (yMin == yMax) {
+      // this is a sanity check for a case that shouldn't happen -- but
+      // if it does happen, we want to avoid dividing by zero later
+      yMin = y;
+      yMax = y + 1;
+    }
+    base = y;
+    break;
+  case 3:
+    xMin = x - ascent;
+    xMax = x - descent;
+    if (xMin == xMax) {
+      // this is a sanity check for a case that shouldn't happen -- but
+      // if it does happen, we want to avoid dividing by zero later
+      xMin = x;
+      xMax = x + 1;
+    }
+    base = x;
+    break;
+  }
+  text = NULL;
+  edge = NULL;
+  len = size = 0;
+  spaceAfter = gFalse;
+  next = NULL;

 
 

-  double xMin, xMax;
-  double yMin, yMax;
-  TextString *strings;         // list of strings in the block
-  TextBlock *next;             // next block in line
-  TextBlock *xyNext;           // next block on xyBlocks list
-  Unicode *text;               // Unicode text of the block, including
-                               //   spaces between strings
-  double *xRight;              // right-hand x coord of each char
-  int len;                     // total number of Unicode characters
-  int convertedLen;            // total number of converted characters
-  int *col;                    // starting column number for each
-                               //   Unicode character
-};
+#if TEXTOUT_WORD_LIST
+  GfxRGB rgb;

 
 

-TextBlock::TextBlock() {
-  strings = NULL;
-  next = NULL;
-  xyNext = NULL;
+  if ((state->getRender() & 3) == 1) {
+    state->getStrokeRGB(&rgb);
+  } else {
+    state->getFillRGB(&rgb);
+  }
+  colorR = rgb.r;
+  colorG = rgb.g;
+  colorB = rgb.b;
+#endif
+}
+
+TextWord::~TextWord() {
+  gfree(text);
+  gfree(edge);
+}
+
+void TextWord::addChar(GfxState *state, double x, double y,
+                      double dx, double dy, Unicode u) {
+  if (len == size) {
+    size += 16;
+    text = (Unicode *)grealloc(text, size * sizeof(Unicode));
+    edge = (double *)grealloc(edge, (size + 1) * sizeof(double));
+  }
+  text[len] = u;
+  switch (rot) {
+  case 0:
+    if (len == 0) {
+      xMin = x;
+    }
+    edge[len] = x;
+    xMax = edge[len+1] = x + dx;
+    break;
+  case 1:
+    if (len == 0) {
+      yMin = y;
+    }
+    edge[len] = y;
+    yMax = edge[len+1] = y + dy;
+    break;
+  case 2:
+    if (len == 0) {
+      xMax = x;
+    }
+    edge[len] = x;
+    xMin = edge[len+1] = x + dx;
+    break;
+  case 3:
+    if (len == 0) {
+      yMax = y;
+    }
+    edge[len] = y;
+    yMin = edge[len+1] = y + dy;
+    break;
+  }
+  ++len;
+}
+
+void TextWord::merge(TextWord *word) {
+  int i;
+
+  if (word->xMin < xMin) {
+    xMin = word->xMin;
+  }
+  if (word->yMin < yMin) {
+    yMin = word->yMin;
+  }
+  if (word->xMax > xMax) {
+    xMax = word->xMax;
+  }
+  if (word->yMax > yMax) {
+    yMax = word->yMax;
+  }
+  if (len + word->len > size) {
+    size = len + word->len;
+    text = (Unicode *)grealloc(text, size * sizeof(Unicode));
+    edge = (double *)grealloc(edge, (size + 1) * sizeof(double));
+  }
+  for (i = 0; i < word->len; ++i) {
+    text[len + i] = word->text[i];
+    edge[len + i] = word->edge[i];
+  }
+  edge[len + word->len] = word->edge[word->len];
+  len += word->len;
+  charLen += word->charLen;
+}
+
+inline int TextWord::primaryCmp(TextWord *word) {
+  double cmp;
+
+  cmp = 0; // make gcc happy
+  switch (rot) {
+  case 0:
+    cmp = xMin - word->xMin;
+    break;
+  case 1:
+    cmp = yMin - word->yMin;
+    break;
+  case 2:
+    cmp = word->xMax - xMax;
+    break;
+  case 3:
+    cmp = word->yMax - yMax;
+    break;
+  }
+  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
+}
+
+double TextWord::primaryDelta(TextWord *word) {
+  double delta;
+
+  delta = 0; // make gcc happy
+  switch (rot) {
+  case 0:
+    delta = word->xMin - xMax;
+    break;
+  case 1:
+    delta = word->yMin - yMax;
+    break;
+  case 2:
+    delta = xMin - word->xMax;
+    break;
+  case 3:
+    delta = yMin - word->yMax;
+    break;
+  }
+  return delta;
+}
+
+int TextWord::cmpYX(const void *p1, const void *p2) {
+  TextWord *word1 = *(TextWord **)p1;
+  TextWord *word2 = *(TextWord **)p2;
+  double cmp;
+
+  cmp = word1->yMin - word2->yMin;
+  if (cmp == 0) {
+    cmp = word1->xMin - word2->xMin;
+  }
+  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
+}
+
+#if TEXTOUT_WORD_LIST
+
+GString *TextWord::getText() {
+  GString *s;
+  UnicodeMap *uMap;
+  char buf[8];
+  int n, i;
+
+  s = new GString();
+  if (!(uMap = globalParams->getTextEncoding())) {
+    return s;
+  }
+  for (i = 0; i < len; ++i) {
+    n = uMap->mapUnicode(text[i], buf, sizeof(buf));
+    s->append(buf, n);
+  }
+  uMap->decRefCnt();
+  return s;
+}
+
+#endif // TEXTOUT_WORD_LIST
+
+//------------------------------------------------------------------------
+// TextPool
+//------------------------------------------------------------------------
+
+TextPool::TextPool() {
+  minBaseIdx = 0;
+  maxBaseIdx = -1;
+  pool = NULL;
+  cursor = NULL;
+  cursorBaseIdx = -1;
+}
+
+TextPool::~TextPool() {
+  int baseIdx;
+  TextWord *word, *word2;
+
+  for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
+    for (word = pool[baseIdx - minBaseIdx]; word; word = word2) {
+      word2 = word->next;
+      delete word;
+    }
+  }
+  gfree(pool);
+}
+
+int TextPool::getBaseIdx(double base) {
+  int baseIdx;
+
+  baseIdx = (int)(base / textPoolStep);
+  if (baseIdx < minBaseIdx) {
+    return minBaseIdx;
+  }
+  if (baseIdx > maxBaseIdx) {
+    return maxBaseIdx;
+  }
+  return baseIdx;
+}
+
+void TextPool::addWord(TextWord *word) {
+  TextWord **newPool;
+  int wordBaseIdx, newMinBaseIdx, newMaxBaseIdx, baseIdx;
+  TextWord *w0, *w1;
+
+  // expand the array if needed
+  wordBaseIdx = (int)(word->base / textPoolStep);
+  if (minBaseIdx > maxBaseIdx) {
+    minBaseIdx = wordBaseIdx - 128;
+    maxBaseIdx = wordBaseIdx + 128;
+    pool = (TextWord **)gmalloc((maxBaseIdx - minBaseIdx + 1) *
+                               sizeof(TextWord *));
+    for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
+      pool[baseIdx - minBaseIdx] = NULL;
+    }
+  } else if (wordBaseIdx < minBaseIdx) {
+    newMinBaseIdx = wordBaseIdx - 128;
+    newPool = (TextWord **)gmalloc((maxBaseIdx - newMinBaseIdx + 1) *
+                                  sizeof(TextWord *));
+    for (baseIdx = newMinBaseIdx; baseIdx < minBaseIdx; ++baseIdx) {
+      newPool[baseIdx - newMinBaseIdx] = NULL;
+    }
+    memcpy(&newPool[minBaseIdx - newMinBaseIdx], pool,
+          (maxBaseIdx - minBaseIdx + 1) * sizeof(TextWord *));
+    gfree(pool);
+    pool = newPool;
+    minBaseIdx = newMinBaseIdx;
+  } else if (wordBaseIdx > maxBaseIdx) {
+    newMaxBaseIdx = wordBaseIdx + 128;
+    pool = (TextWord **)grealloc(pool, (newMaxBaseIdx - minBaseIdx + 1) *
+                                        sizeof(TextWord *));
+    for (baseIdx = maxBaseIdx + 1; baseIdx <= newMaxBaseIdx; ++baseIdx) {
+      pool[baseIdx - minBaseIdx] = NULL;
+    }
+    maxBaseIdx = newMaxBaseIdx;
+  }
+
+  // insert the new word
+  if (cursor && wordBaseIdx == cursorBaseIdx &&
+      word->primaryCmp(cursor) > 0) {
+    w0 = cursor;
+    w1 = cursor->next;
+  } else {
+    w0 = NULL;
+    w1 = pool[wordBaseIdx - minBaseIdx];
+  }
+  for (; w1 && word->primaryCmp(w1) > 0; w0 = w1, w1 = w1->next) ;
+  word->next = w1;
+  if (w0) {
+    w0->next = word;
+  } else {
+    pool[wordBaseIdx - minBaseIdx] = word;
+  }
+  cursor = word;
+  cursorBaseIdx = wordBaseIdx;
+}
+
+//------------------------------------------------------------------------
+// TextLine
+//------------------------------------------------------------------------
+
+TextLine::TextLine(TextBlock *blkA, int rotA, double baseA) {
+  blk = blkA;
+  rot = rotA;
+  xMin = yMin = 0;
+  xMax = yMax = -1;
+  base = baseA;
+  words = lastWord = NULL;

   text = NULL;
   text = NULL;

-  xRight = NULL;
+  edge = NULL;

   col = NULL;
   col = NULL;

+  len = 0;
+  convertedLen = 0;
+  hyphenated = gFalse;
+  next = NULL;

 }
 
 }
 

-TextBlock::~TextBlock() {
-  TextString *p1, *p2;
+TextLine::~TextLine() {
+  TextWord *word;

 
 

-  for (p1 = strings; p1; p1 = p2) {
-    p2 = p1->next;
-    delete p1;
+  while (words) {
+    word = words;
+    words = words->next;
+    delete word;

   }
   gfree(text);
   }
   gfree(text);

-  gfree(xRight);
+  gfree(edge);

   gfree(col);
 }
 
   gfree(col);
 }
 

+void TextLine::addWord(TextWord *word) {
+  if (lastWord) {
+    lastWord->next = word;
+  } else {
+    words = word;
+  }
+  lastWord = word;
+
+  if (xMin > xMax) {
+    xMin = word->xMin;
+    xMax = word->xMax;
+    yMin = word->yMin;
+    yMax = word->yMax;
+  } else {
+    if (word->xMin < xMin) {
+      xMin = word->xMin;
+    }
+    if (word->xMax > xMax) {
+      xMax = word->xMax;
+    }
+    if (word->yMin < yMin) {
+      yMin = word->yMin;
+    }
+    if (word->yMax > yMax) {
+      yMax = word->yMax;
+    }
+  }
+}
+
+double TextLine::primaryDelta(TextLine *line) {
+  double delta;
+
+  delta = 0; // make gcc happy
+  switch (rot) {
+  case 0:
+    delta = line->xMin - xMax;
+    break;
+  case 1:
+    delta = line->yMin - yMax;
+    break;
+  case 2:
+    delta = xMin - line->xMax;
+    break;
+  case 3:
+    delta = yMin - line->yMax;
+    break;
+  }
+  return delta;
+}
+
+int TextLine::primaryCmp(TextLine *line) {
+  double cmp;
+
+  cmp = 0; // make gcc happy
+  switch (rot) {
+  case 0:
+    cmp = xMin - line->xMin;
+    break;
+  case 1:
+    cmp = yMin - line->yMin;
+    break;
+  case 2:
+    cmp = line->xMax - xMax;
+    break;
+  case 3:
+    cmp = line->yMax - yMax;
+    break;
+  }
+  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
+}
+
+int TextLine::secondaryCmp(TextLine *line) {
+  double cmp;
+
+  cmp = (rot == 0 || rot == 3) ? base - line->base : line->base - base;
+  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
+}
+
+int TextLine::cmpYX(TextLine *line) {
+  int cmp;
+
+  if ((cmp = secondaryCmp(line))) {
+    return cmp;
+  }
+  return primaryCmp(line);
+}
+
+int TextLine::cmpXY(const void *p1, const void *p2) {
+  TextLine *line1 = *(TextLine **)p1;
+  TextLine *line2 = *(TextLine **)p2;
+  int cmp;
+
+  if ((cmp = line1->primaryCmp(line2))) {
+    return cmp;
+  }
+  return line1->secondaryCmp(line2);
+}
+
+void TextLine::coalesce(UnicodeMap *uMap) {
+  TextWord *word0, *word1;
+  double space, delta, minSpace;
+  GBool isUnicode;
+  char buf[8];
+  int i, j;
+
+  if (words->next) {
+
+    // compute the inter-word space threshold
+    if (words->len > 1 || words->next->len > 1) {
+      minSpace = 0;
+    } else {
+      minSpace = words->primaryDelta(words->next);
+      for (word0 = words->next, word1 = word0->next;
+          word1 && minSpace > 0;
+          word0 = word1, word1 = word0->next) {
+       if (word1->len > 1) {
+         minSpace = 0;
+       }
+       delta = word0->primaryDelta(word1);
+       if (delta < minSpace) {
+         minSpace = delta;
+       }
+      }
+    }
+    if (minSpace <= 0) {
+      space = maxCharSpacing * words->fontSize;
+    } else {
+      space = maxWideCharSpacingMul * minSpace;
+    }
+
+    // merge words
+    word0 = words;
+    word1 = words->next;
+    while (word1) {
+      if (word0->primaryDelta(word1) >= space) {
+       word0->spaceAfter = gTrue;
+       word0 = word1;
+       word1 = word1->next;
+      } else if (word0->font == word1->font &&
+                fabs(word0->fontSize - word1->fontSize) <
+                maxWordFontSizeDelta * words->fontSize &&
+                word1->charPos == word0->charPos + word0->charLen) {
+       word0->merge(word1);
+       word0->next = word1->next;
+       delete word1;
+       word1 = word0->next;
+      } else {
+       word0 = word1;
+       word1 = word1->next;
+      }
+    }
+  }
+
+  // build the line text
+  isUnicode = uMap ? uMap->isUnicode() : gFalse;
+  len = 0;
+  for (word1 = words; word1; word1 = word1->next) {
+    len += word1->len;
+    if (word1->spaceAfter) {
+      ++len;
+    }
+  }
+  text = (Unicode *)gmalloc(len * sizeof(Unicode));
+  edge = (double *)gmalloc((len + 1) * sizeof(double));
+  i = 0;
+  for (word1 = words; word1; word1 = word1->next) {
+    for (j = 0; j < word1->len; ++j) {
+      text[i] = word1->text[j];
+      edge[i] = word1->edge[j];
+      ++i;
+    }
+    edge[i] = word1->edge[word1->len];
+    if (word1->spaceAfter) {
+      text[i] = (Unicode)0x0020;
+      ++i;
+    }
+  }
+
+  // compute convertedLen and set up the col array
+  col = (int *)gmalloc((len + 1) * sizeof(int));
+  convertedLen = 0;
+  for (i = 0; i < len; ++i) {
+    col[i] = convertedLen;
+    if (isUnicode) {
+      ++convertedLen;
+    } else if (uMap) {
+      convertedLen += uMap->mapUnicode(text[i], buf, sizeof(buf));
+    }
+  }
+  col[len] = convertedLen;
+
+  // check for hyphen at end of line
+  //~ need to check for other chars used as hyphens
+  hyphenated = text[len - 1] == (Unicode)'-';
+}
+

 //------------------------------------------------------------------------
 //------------------------------------------------------------------------

-// TextLine
+// TextLineFrag

 //------------------------------------------------------------------------
 
 //------------------------------------------------------------------------
 

-class TextLine {
+class TextLineFrag {

 public:
 
 public:
 

-  TextLine();
-  ~TextLine();
-
-  TextBlock *blocks;
-  TextLine *next;
+  TextLine *line;              // the line object
+  int start, len;              // offset and length of this fragment
+                               //   (in Unicode chars)
+  double xMin, xMax;           // bounding box coordinates

   double yMin, yMax;
   double yMin, yMax;

+  double base;                 // baseline virtual coordinate
+  int col;                     // first column
+
+  void init(TextLine *lineA, int startA, int lenA);
+  void computeCoords(GBool oneRot);
+
+  static int cmpYXPrimaryRot(const void *p1, const void *p2);
+  static int cmpYXLineRot(const void *p1, const void *p2);
+  static int cmpXYLineRot(const void *p1, const void *p2);

 };
 
 };
 

-TextLine::TextLine() {
-  blocks = NULL;
+void TextLineFrag::init(TextLine *lineA, int startA, int lenA) {
+  line = lineA;
+  start = startA;
+  len = lenA;
+  col = line->col[start];
+}
+
+void TextLineFrag::computeCoords(GBool oneRot) {
+  TextBlock *blk;
+  double d0, d1, d2, d3, d4;
+
+  if (oneRot) {
+
+    switch (line->rot) {
+    case 0:
+      xMin = line->edge[start];
+      xMax = line->edge[start + len];
+      yMin = line->yMin;
+      yMax = line->yMax;
+      break;
+    case 1:
+      xMin = line->xMin;
+      xMax = line->xMax;
+      yMin = line->edge[start];
+      yMax = line->edge[start + len];
+      break;
+    case 2:
+      xMin = line->edge[start + len];
+      xMax = line->edge[start];
+      yMin = line->yMin;
+      yMax = line->yMax;
+      break;
+    case 3:
+      xMin = line->xMin;
+      xMax = line->xMax;
+      yMin = line->edge[start + len];
+      yMax = line->edge[start];
+      break;
+    }
+    base = line->base;
+
+  } else {
+
+    if (line->rot == 0 && line->blk->page->primaryRot == 0) {
+
+      xMin = line->edge[start];
+      xMax = line->edge[start + len];
+      yMin = line->yMin;
+      yMax = line->yMax;
+      base = line->base;
+
+    } else {
+
+      blk = line->blk;
+      d0 = line->edge[start];
+      d1 = line->edge[start + len];
+      d2 = d3 = d4 = 0; // make gcc happy
+
+      switch (line->rot) {
+      case 0:
+       d2 = line->yMin;
+       d3 = line->yMax;
+       d4 = line->base;
+       d0 = (d0 - blk->xMin) / (blk->xMax - blk->xMin);
+       d1 = (d1 - blk->xMin) / (blk->xMax - blk->xMin);
+       d2 = (d2 - blk->yMin) / (blk->yMax - blk->yMin);
+       d3 = (d3 - blk->yMin) / (blk->yMax - blk->yMin);
+       d4 = (d4 - blk->yMin) / (blk->yMax - blk->yMin);
+       break;
+      case 1:
+       d2 = line->xMax;
+       d3 = line->xMin;
+       d4 = line->base;
+       d0 = (d0 - blk->yMin) / (blk->yMax - blk->yMin);
+       d1 = (d1 - blk->yMin) / (blk->yMax - blk->yMin);
+       d2 = (blk->xMax - d2) / (blk->xMax - blk->xMin);
+       d3 = (blk->xMax - d3) / (blk->xMax - blk->xMin);
+       d4 = (blk->xMax - d4) / (blk->xMax - blk->xMin);
+       break;
+      case 2:
+       d2 = line->yMax;
+       d3 = line->yMin;
+       d4 = line->base;
+       d0 = (blk->xMax - d0) / (blk->xMax - blk->xMin);
+       d1 = (blk->xMax - d1) / (blk->xMax - blk->xMin);
+       d2 = (blk->yMax - d2) / (blk->yMax - blk->yMin);
+       d3 = (blk->yMax - d3) / (blk->yMax - blk->yMin);
+       d4 = (blk->yMax - d4) / (blk->yMax - blk->yMin);
+       break;
+      case 3:
+       d2 = line->xMin;
+       d3 = line->xMax;
+       d4 = line->base;
+       d0 = (blk->yMax - d0) / (blk->yMax - blk->yMin);
+       d1 = (blk->yMax - d1) / (blk->yMax - blk->yMin);
+       d2 = (d2 - blk->xMin) / (blk->xMax - blk->xMin);
+       d3 = (d3 - blk->xMin) / (blk->xMax - blk->xMin);
+       d4 = (d4 - blk->xMin) / (blk->xMax - blk->xMin);
+       break;
+      }
+
+      switch (line->blk->page->primaryRot) {
+      case 0:
+       xMin = blk->xMin + d0 * (blk->xMax - blk->xMin);
+       xMax = blk->xMin + d1 * (blk->xMax - blk->xMin);
+       yMin = blk->yMin + d2 * (blk->yMax - blk->yMin);
+       yMax = blk->yMin + d3 * (blk->yMax - blk->yMin);
+       base = blk->yMin + base * (blk->yMax - blk->yMin);
+       break;
+      case 1:
+       xMin = blk->xMax - d3 * (blk->xMax - blk->xMin);
+       xMax = blk->xMax - d2 * (blk->xMax - blk->xMin);
+       yMin = blk->yMin + d0 * (blk->yMax - blk->yMin);
+       yMax = blk->yMin + d1 * (blk->yMax - blk->yMin);
+       base = blk->xMax - d4 * (blk->xMax - blk->xMin);
+       break;
+      case 2:
+       xMin = blk->xMax - d1 * (blk->xMax - blk->xMin);
+       xMax = blk->xMax - d0 * (blk->xMax - blk->xMin);
+       yMin = blk->yMax - d3 * (blk->yMax - blk->yMin);
+       yMax = blk->yMax - d2 * (blk->yMax - blk->yMin);
+       base = blk->yMax - d4 * (blk->yMax - blk->yMin);
+       break;
+      case 3:
+       xMin = blk->xMin + d2 * (blk->xMax - blk->xMin);
+       xMax = blk->xMin + d3 * (blk->xMax - blk->xMin);
+       yMin = blk->yMax - d1 * (blk->yMax - blk->yMin);
+       yMax = blk->yMax - d0 * (blk->yMax - blk->yMin);
+       base = blk->xMin + d4 * (blk->xMax - blk->xMin);
+       break;
+      }
+
+    }
+  }
+}
+
+int TextLineFrag::cmpYXPrimaryRot(const void *p1, const void *p2) {
+  TextLineFrag *frag1 = (TextLineFrag *)p1;
+  TextLineFrag *frag2 = (TextLineFrag *)p2;
+  double cmp;
+
+  cmp = 0; // make gcc happy
+  switch (frag1->line->blk->page->primaryRot) {
+  case 0:
+    if ((cmp = frag1->yMin - frag2->yMin) == 0) {
+      cmp = frag1->xMin - frag2->xMin;
+    }
+    break;
+  case 1:
+    if ((cmp = frag2->xMax - frag1->xMax) == 0) {
+      cmp = frag1->yMin - frag2->yMin;
+    }
+    break;
+  case 2:
+    if ((cmp = frag2->yMin - frag1->yMin) == 0) {
+      cmp = frag2->xMax - frag1->xMax;
+    }
+    break;
+  case 3:
+    if ((cmp = frag1->xMax - frag2->xMax) == 0) {
+      cmp = frag2->yMax - frag1->yMax;
+    }
+    break;
+  }
+  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
+}
+
+int TextLineFrag::cmpYXLineRot(const void *p1, const void *p2) {
+  TextLineFrag *frag1 = (TextLineFrag *)p1;
+  TextLineFrag *frag2 = (TextLineFrag *)p2;
+  double cmp;
+
+  cmp = 0; // make gcc happy
+  switch (frag1->line->rot) {
+  case 0:
+    if ((cmp = frag1->yMin - frag2->yMin) == 0) {
+      cmp = frag1->xMin - frag2->xMin;
+    }
+    break;
+  case 1:
+    if ((cmp = frag2->xMax - frag1->xMax) == 0) {
+      cmp = frag1->yMin - frag2->yMin;
+    }
+    break;
+  case 2:
+    if ((cmp = frag2->yMin - frag1->yMin) == 0) {
+      cmp = frag2->xMax - frag1->xMax;
+    }
+    break;
+  case 3:
+    if ((cmp = frag1->xMax - frag2->xMax) == 0) {
+      cmp = frag2->yMax - frag1->yMax;
+    }
+    break;
+  }
+  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
+}
+
+int TextLineFrag::cmpXYLineRot(const void *p1, const void *p2) {
+  TextLineFrag *frag1 = (TextLineFrag *)p1;
+  TextLineFrag *frag2 = (TextLineFrag *)p2;
+  double cmp;
+
+  cmp = 0; // make gcc happy
+  switch (frag1->line->rot) {
+  case 0:
+    if ((cmp = frag1->xMin - frag2->xMin) == 0) {
+      cmp = frag1->yMin - frag2->yMin;
+    }
+    break;
+  case 1:
+    if ((cmp = frag1->yMin - frag2->yMin) == 0) {
+      cmp = frag2->xMax - frag1->xMax;
+    }
+    break;
+  case 2:
+    if ((cmp = frag2->xMax - frag1->xMax) == 0) {
+      cmp = frag2->yMin - frag1->yMin;
+    }
+    break;
+  case 3:
+    if ((cmp = frag2->yMax - frag1->yMax) == 0) {
+      cmp = frag1->xMax - frag2->xMax;
+    }
+    break;
+  }
+  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
+}
+
+//------------------------------------------------------------------------
+// TextBlock
+//------------------------------------------------------------------------
+
+TextBlock::TextBlock(TextPage *pageA, int rotA) {
+  page = pageA;
+  rot = rotA;
+  xMin = yMin = 0;
+  xMax = yMax = -1;
+  priMin = 0;
+  priMax = page->pageWidth;
+  pool = new TextPool();
+  lines = NULL;
+  curLine = NULL;
+  next = NULL;
+  stackNext = NULL;
+}
+
+TextBlock::~TextBlock() {
+  TextLine *line;
+
+  delete pool;
+  while (lines) {
+    line = lines;
+    lines = lines->next;
+    delete line;
+  }
+}
+
+void TextBlock::addWord(TextWord *word) {
+  pool->addWord(word);
+  if (xMin > xMax) {
+    xMin = word->xMin;
+    xMax = word->xMax;
+    yMin = word->yMin;
+    yMax = word->yMax;
+  } else {
+    if (word->xMin < xMin) {
+      xMin = word->xMin;
+    }
+    if (word->xMax > xMax) {
+      xMax = word->xMax;
+    }
+    if (word->yMin < yMin) {
+      yMin = word->yMin;
+    }
+    if (word->yMax > yMax) {
+      yMax = word->yMax;
+    }
+  }
+}
+
+void TextBlock::coalesce(UnicodeMap *uMap) {
+  TextWord *word0, *word1, *word2, *bestWord0, *bestWord1, *lastWord;
+  TextLine *line, *line0, *line1;
+  int poolMinBaseIdx, startBaseIdx, minBaseIdx, maxBaseIdx;
+  int baseIdx, bestWordBaseIdx, idx0, idx1;
+  double minBase, maxBase;
+  double fontSize, delta, priDelta, secDelta;
+  TextLine **lineArray;
+  GBool found;
+  int col1, col2;
+  int i, j, k;
+
+  // discard duplicated text (fake boldface, drop shadows)
+  for (idx0 = pool->minBaseIdx; idx0 <= pool->maxBaseIdx; ++idx0) {
+    word0 = pool->getPool(idx0);
+    while (word0) {
+      priDelta = dupMaxPriDelta * word0->fontSize;
+      secDelta = dupMaxSecDelta * word0->fontSize;
+      if (rot == 0 || rot == 3) {
+       maxBaseIdx = pool->getBaseIdx(word0->base + secDelta);
+      } else {
+       maxBaseIdx = pool->getBaseIdx(word0->base - secDelta);
+      }
+      found = gFalse;
+      word1 = word2 = NULL; // make gcc happy
+      for (idx1 = idx0; idx1 <= maxBaseIdx; ++idx1) {
+       if (idx1 == idx0) {
+         word1 = word0;
+         word2 = word0->next;
+       } else {
+         word1 = NULL;
+         word2 = pool->getPool(idx1);
+       }
+       for (; word2; word1 = word2, word2 = word2->next) {
+         if (word2->len == word0->len &&
+             !memcmp(word2->text, word0->text,
+                     word0->len * sizeof(Unicode))) {
+           switch (rot) {
+           case 0:
+           case 2:
+             found = fabs(word0->xMin - word2->xMin) < priDelta &&
+                     fabs(word0->xMax - word2->xMax) < priDelta &&
+                     fabs(word0->yMin - word2->yMin) < secDelta &&
+                     fabs(word0->yMax - word2->yMax) < secDelta;
+             break;
+           case 1:
+           case 3:
+             found = fabs(word0->xMin - word2->xMin) < secDelta &&
+                     fabs(word0->xMax - word2->xMax) < secDelta &&
+                     fabs(word0->yMin - word2->yMin) < priDelta &&
+                     fabs(word0->yMax - word2->yMax) < priDelta;
+             break;
+           }
+         }
+         if (found) {
+           break;
+         }
+       }
+       if (found) {
+         break;
+       }
+      }
+      if (found) {
+       if (word1) {
+         word1->next = word2->next;
+       } else {
+         pool->setPool(idx1, word2->next);
+       }
+       delete word2;
+      } else {
+       word0 = word0->next;
+      }
+    }
+  }
+
+  // build the lines
+  curLine = NULL;
+  poolMinBaseIdx = pool->minBaseIdx;
+  charCount = 0;
+  nLines = 0;
+  while (1) {
+
+    // find the first non-empty line in the pool
+    for (;
+        poolMinBaseIdx <= pool->maxBaseIdx && !pool->getPool(poolMinBaseIdx);
+        ++poolMinBaseIdx) ;
+    if (poolMinBaseIdx > pool->maxBaseIdx) {
+      break;
+    }
+
+    // look for the left-most word in the first four lines of the
+    // pool -- this avoids starting with a superscript word
+    startBaseIdx = poolMinBaseIdx;
+    for (baseIdx = poolMinBaseIdx + 1;
+        baseIdx < poolMinBaseIdx + 4 && baseIdx <= pool->maxBaseIdx;
+        ++baseIdx) {
+      if (!pool->getPool(baseIdx)) {
+       continue;
+      }
+      if (pool->getPool(baseIdx)->primaryCmp(pool->getPool(startBaseIdx))
+         < 0) {
+       startBaseIdx = baseIdx;
+      }
+    }
+
+    // create a new line
+    word0 = pool->getPool(startBaseIdx);
+    pool->setPool(startBaseIdx, word0->next);
+    word0->next = NULL;
+    line = new TextLine(this, word0->rot, word0->base);
+    line->addWord(word0);
+    lastWord = word0;
+
+    // compute the search range
+    fontSize = word0->fontSize;
+    minBase = word0->base - maxIntraLineDelta * fontSize;
+    maxBase = word0->base + maxIntraLineDelta * fontSize;
+    minBaseIdx = pool->getBaseIdx(minBase);
+    maxBaseIdx = pool->getBaseIdx(maxBase);
+
+    // find the rest of the words in this line
+    while (1) {
+
+      // find the left-most word whose baseline is in the range for
+      // this line
+      bestWordBaseIdx = 0;
+      bestWord0 = bestWord1 = NULL;
+      for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
+       for (word0 = NULL, word1 = pool->getPool(baseIdx);
+            word1;
+            word0 = word1, word1 = word1->next) {
+         if (word1->base >= minBase &&
+             word1->base <= maxBase &&
+             (delta = lastWord->primaryDelta(word1)) >=
+               minCharSpacing * fontSize) {
+           if (delta < maxWordSpacing * fontSize &&
+               (!bestWord1 || word1->primaryCmp(bestWord1) < 0)) {
+             bestWordBaseIdx = baseIdx;
+             bestWord0 = word0;
+             bestWord1 = word1;
+           }
+           break;
+         }
+       }
+      }
+      if (!bestWord1) {
+       break;
+      }
+
+      // remove it from the pool, and add it to the line
+      if (bestWord0) {
+       bestWord0->next = bestWord1->next;
+      } else {
+       pool->setPool(bestWordBaseIdx, bestWord1->next);
+      }
+      bestWord1->next = NULL;
+      line->addWord(bestWord1);
+      lastWord = bestWord1;
+    }
+
+    // add the line
+    if (curLine && line->cmpYX(curLine) > 0) {
+      line0 = curLine;
+      line1 = curLine->next;
+    } else {
+      line0 = NULL;
+      line1 = lines;
+    }
+    for (;
+        line1 && line->cmpYX(line1) > 0;
+        line0 = line1, line1 = line1->next) ;
+    if (line0) {
+      line0->next = line;
+    } else {
+      lines = line;
+    }
+    line->next = line1;
+    curLine = line;
+    line->coalesce(uMap);
+    charCount += line->len;
+    ++nLines;
+  }
+
+  // sort lines into xy order for column assignment
+  lineArray = (TextLine **)gmalloc(nLines * sizeof(TextLine *));
+  for (line = lines, i = 0; line; line = line->next, ++i) {
+    lineArray[i] = line;
+  }
+  qsort(lineArray, nLines, sizeof(TextLine *), &TextLine::cmpXY);
+
+  // column assignment
+  nColumns = 0;
+  for (i = 0; i < nLines; ++i) {
+    line0 = lineArray[i];
+    col1 = 0;
+    for (j = 0; j < i; ++j) {
+      line1 = lineArray[j];
+      if (line1->primaryDelta(line0) >= 0) {
+       col2 = line1->col[line1->len] + 1;
+      } else {
+       k = 0; // make gcc happy
+       switch (rot) {
+       case 0:
+         for (k = 0;
+              k < line1->len &&
+                line0->xMin >= 0.5 * (line1->edge[k] + line1->edge[k+1]);
+              ++k) ;
+         break;
+       case 1:
+         for (k = 0;
+              k < line1->len &&
+                line0->yMin >= 0.5 * (line1->edge[k] + line1->edge[k+1]);
+              ++k) ;
+         break;
+       case 2:
+         for (k = 0;
+              k < line1->len &&
+                line0->xMax <= 0.5 * (line1->edge[k] + line1->edge[k+1]);
+              ++k) ;
+         break;
+       case 3:
+         for (k = 0;
+              k < line1->len &&
+                line0->yMax <= 0.5 * (line1->edge[k] + line1->edge[k+1]);
+              ++k) ;
+         break;
+       }
+       col2 = line1->col[k];
+      }
+      if (col2 > col1) {
+       col1 = col2;
+      }
+    }
+    for (k = 0; k <= line0->len; ++k) {
+      line0->col[k] += col1;
+    }
+    if (line0->col[line0->len] > nColumns) {
+      nColumns = line0->col[line0->len];
+    }
+  }
+  gfree(lineArray);
+}
+
+void TextBlock::updatePriMinMax(TextBlock *blk) {
+  double newPriMin, newPriMax;
+  GBool gotPriMin, gotPriMax;
+
+  gotPriMin = gotPriMax = gFalse;
+  newPriMin = newPriMax = 0; // make gcc happy
+  switch (page->primaryRot) {
+  case 0:
+  case 2:
+    if (blk->yMin < yMax && blk->yMax > yMin) {
+      if (blk->xMin < xMin) {
+       newPriMin = blk->xMax;
+       gotPriMin = gTrue;
+      }
+      if (blk->xMax > xMax) {
+       newPriMax = blk->xMin;
+       gotPriMax = gTrue;
+      }
+    }
+    break;
+  case 1:
+  case 3:
+    if (blk->xMin < xMax && blk->xMax > xMin) {
+      if (blk->yMin < yMin) {
+       newPriMin = blk->yMax;
+       gotPriMin = gTrue;
+      }
+      if (blk->yMax > yMax) {
+       newPriMax = blk->yMin;
+       gotPriMax = gTrue;
+      }
+    }
+    break;
+  }
+  if (gotPriMin) {
+    if (newPriMin > xMin) {
+      newPriMin = xMin;
+    }
+    if (newPriMin > priMin) {
+      priMin = newPriMin;
+    }
+  }
+  if (gotPriMax) {
+    if (newPriMax < xMax) {
+      newPriMax = xMax;
+    }
+    if (newPriMax < priMax) {
+      priMax = newPriMax;
+    }
+  }
+}
+
+int TextBlock::cmpXYPrimaryRot(const void *p1, const void *p2) {
+  TextBlock *blk1 = *(TextBlock **)p1;
+  TextBlock *blk2 = *(TextBlock **)p2;
+  double cmp;
+
+  cmp = 0; // make gcc happy
+  switch (blk1->page->primaryRot) {
+  case 0:
+    if ((cmp = blk1->xMin - blk2->xMin) == 0) {
+      cmp = blk1->yMin - blk2->yMin;
+    }
+    break;
+  case 1:
+    if ((cmp = blk1->yMin - blk2->yMin) == 0) {
+      cmp = blk2->xMax - blk1->xMax;
+    }
+    break;
+  case 2:
+    if ((cmp = blk2->xMax - blk1->xMax) == 0) {
+      cmp = blk2->yMin - blk1->yMin;
+    }
+    break;
+  case 3:
+    if ((cmp = blk2->yMax - blk1->yMax) == 0) {
+      cmp = blk1->xMax - blk2->xMax;
+    }
+    break;
+  }
+  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
+}
+
+int TextBlock::cmpYXPrimaryRot(const void *p1, const void *p2) {
+  TextBlock *blk1 = *(TextBlock **)p1;
+  TextBlock *blk2 = *(TextBlock **)p2;
+  double cmp;
+
+  cmp = 0; // make gcc happy
+  switch (blk1->page->primaryRot) {
+  case 0:
+    if ((cmp = blk1->yMin - blk2->yMin) == 0) {
+      cmp = blk1->xMin - blk2->xMin;
+    }
+    break;
+  case 1:
+    if ((cmp = blk2->xMax - blk1->xMax) == 0) {
+      cmp = blk1->yMin - blk2->yMin;
+    }
+    break;
+  case 2:
+    if ((cmp = blk2->yMin - blk1->yMin) == 0) {
+      cmp = blk2->xMax - blk1->xMax;
+    }
+    break;
+  case 3:
+    if ((cmp = blk1->xMax - blk2->xMax) == 0) {
+      cmp = blk2->yMax - blk1->yMax;
+    }
+    break;
+  }
+  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
+}
+
+int TextBlock::primaryCmp(TextBlock *blk) {
+  double cmp;
+
+  cmp = 0; // make gcc happy
+  switch (rot) {
+  case 0:
+    cmp = xMin - blk->xMin;
+    break;
+  case 1:
+    cmp = yMin - blk->yMin;
+    break;
+  case 2:
+    cmp = blk->xMax - xMax;
+    break;
+  case 3:
+    cmp = blk->yMax - yMax;
+    break;
+  }
+  return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
+}
+
+double TextBlock::secondaryDelta(TextBlock *blk) {
+  double delta;
+
+  delta = 0; // make gcc happy
+  switch (rot) {
+  case 0:
+    delta = blk->yMin - yMax;
+    break;
+  case 1:
+    delta = xMin - blk->xMax;
+    break;
+  case 2:
+    delta = yMin - blk->yMax;
+    break;
+  case 3:
+    delta = blk->xMin - xMax;
+    break;
+  }
+  return delta;
+}
+
+GBool TextBlock::isBelow(TextBlock *blk) {
+  GBool below;
+
+  below = gFalse; // make gcc happy
+  switch (page->primaryRot) {
+  case 0:
+    below = xMin >= blk->priMin && xMax <= blk->priMax &&
+            yMin > blk->yMin;
+    break;
+  case 1:
+    below = yMin >= blk->priMin && yMax <= blk->priMax &&
+            xMax < blk->xMax;
+    break;
+  case 2:
+    below = xMin >= blk->priMin && xMax <= blk->priMax &&
+            yMax < blk->yMax;
+    break;
+  case 3:
+    below = yMin >= blk->priMin && yMax <= blk->priMax &&
+            xMin > blk->xMin;
+    break;
+  }
+
+  return below;
+}
+
+//------------------------------------------------------------------------
+// TextFlow
+//------------------------------------------------------------------------
+
+TextFlow::TextFlow(TextPage *pageA, TextBlock *blk) {
+  page = pageA;
+  xMin = blk->xMin;
+  xMax = blk->xMax;
+  yMin = blk->yMin;
+  yMax = blk->yMax;
+  priMin = blk->priMin;
+  priMax = blk->priMax;
+  blocks = lastBlk = blk;

   next = NULL;
 }
 
   next = NULL;
 }
 

-TextLine::~TextLine() {
-  TextBlock *p1, *p2;
+TextFlow::~TextFlow() {
+  TextBlock *blk;
+
+  while (blocks) {
+    blk = blocks;
+    blocks = blocks->next;
+    delete blk;
+  }
+}
+
+void TextFlow::addBlock(TextBlock *blk) {
+  if (lastBlk) {
+    lastBlk->next = blk;
+  } else {
+    blocks = blk;
+  }
+  lastBlk = blk;
+  if (blk->xMin < xMin) {
+    xMin = blk->xMin;
+  }
+  if (blk->xMax > xMax) {
+    xMax = blk->xMax;
+  }
+  if (blk->yMin < yMin) {
+    yMin = blk->yMin;
+  }
+  if (blk->yMax > yMax) {
+    yMax = blk->yMax;
+  }
+}
+
+GBool TextFlow::blockFits(TextBlock *blk, TextBlock *prevBlk) {
+  GBool fits;

 
 

-  for (p1 = blocks; p1; p1 = p2) {
-    p2 = p1->next;
-    delete p1;
+  // lower blocks must use smaller fonts
+  if (blk->lines->words->fontSize > lastBlk->lines->words->fontSize) {
+    return gFalse;
+  }
+
+  fits = gFalse; // make gcc happy
+  switch (page->primaryRot) {
+  case 0:
+    fits = blk->xMin >= priMin && blk->xMax <= priMax;
+    break;
+  case 1:
+    fits = blk->yMin >= priMin && blk->yMax <= priMax;
+    break;
+  case 2:
+    fits = blk->xMin >= priMin && blk->xMax <= priMax;
+    break;
+  case 3:
+    fits = blk->yMin >= priMin && blk->yMax <= priMax;
+    break;

   }
   }

+  return fits;

 }
 
 }
 

+#if TEXTOUT_WORD_LIST
+

 //------------------------------------------------------------------------
 //------------------------------------------------------------------------

-// TextString
+// TextWordList

 //------------------------------------------------------------------------
 
 //------------------------------------------------------------------------
 

-TextString::TextString(GfxState *state, double x0, double y0,
-                      double fontSize) {
-  GfxFont *font;
-  double x, y;
+TextWordList::TextWordList(TextPage *text, GBool physLayout) {
+  TextFlow *flow;
+  TextBlock *blk;
+  TextLine *line;
+  TextWord *word;
+  TextWord **wordArray;
+  int nWords, i;
+
+  words = new GList();
+
+  if (text->rawOrder) {
+    for (word = text->rawWords; word; word = word->next) {
+      words->append(word);
+    }
+
+  } else if (physLayout) {
+    // this is inefficient, but it's also the least useful of these
+    // three cases
+    nWords = 0;
+    for (flow = text->flows; flow; flow = flow->next) {
+      for (blk = flow->blocks; blk; blk = blk->next) {
+       for (line = blk->lines; line; line = line->next) {
+         for (word = line->words; word; word = word->next) {
+           ++nWords;
+         }
+       }
+      }
+    }
+    wordArray = (TextWord **)gmalloc(nWords * sizeof(TextWord *));
+    i = 0;
+    for (flow = text->flows; flow; flow = flow->next) {
+      for (blk = flow->blocks; blk; blk = blk->next) {
+       for (line = blk->lines; line; line = line->next) {
+         for (word = line->words; word; word = word->next) {
+           wordArray[i++] = word;
+         }
+       }
+      }
+    }
+    qsort(wordArray, nWords, sizeof(TextWord *), &TextWord::cmpYX);
+    for (i = 0; i < nWords; ++i) {
+      words->append(wordArray[i]);
+    }
+    gfree(wordArray);

 
 

-  state->transform(x0, y0, &x, &y);
-  if ((font = state->getFont())) {
-    yMin = y - font->getAscent() * fontSize;
-    yMax = y - font->getDescent() * fontSize;

   } else {
   } else {

-    // this means that the PDF file draws text without a current font,
-    // which should never happen
-    yMin = y - 0.95 * fontSize;
-    yMax = y + 0.35 * fontSize;
-  }
-  if (yMin == yMax) {
-    // this is a sanity check for a case that shouldn't happen -- but
-    // if it does happen, we want to avoid dividing by zero later
-    yMin = y;
-    yMax = y + 1;
+    for (flow = text->flows; flow; flow = flow->next) {
+      for (blk = flow->blocks; blk; blk = blk->next) {
+       for (line = blk->lines; line; line = line->next) {
+         for (word = line->words; word; word = word->next) {
+           words->append(word);
+         }
+       }
+      }
+    }

   }
   }

-  marked = gFalse;
-  text = NULL;
-  xRight = NULL;
-  len = size = 0;
-  next = NULL;

 }
 
 }
 

+TextWordList::~TextWordList() {
+  delete words;
+}

 
 

-TextString::~TextString() {
-  gfree(text);
-  gfree(xRight);
+int TextWordList::getLength() {
+  return words->getLength();

 }
 
 }
 

-void TextString::addChar(GfxState *state, double x, double y,
-                        double dx, double dy, Unicode u) {
-  if (len == size) {
-    size += 16;
-    text = (Unicode *)grealloc(text, size * sizeof(Unicode));
-    xRight = (double *)grealloc(xRight, size * sizeof(double));
+TextWord *TextWordList::get(int idx) {
+  if (idx < 0 || idx >= words->getLength()) {
+    return NULL;

   }
   }

-  text[len] = u;
-  if (len == 0) {
-    xMin = x;
-  }
-  xMax = xRight[len] = x + dx;
-  ++len;
+  return (TextWord *)words->get(idx);

 }
 
 }
 

+#endif // TEXTOUT_WORD_LIST
+

 //------------------------------------------------------------------------
 // TextPage
 //------------------------------------------------------------------------
 
 TextPage::TextPage(GBool rawOrderA) {
 //------------------------------------------------------------------------
 // TextPage
 //------------------------------------------------------------------------
 
 TextPage::TextPage(GBool rawOrderA) {

+  int rot;
+

   rawOrder = rawOrderA;
   rawOrder = rawOrderA;

-  curStr = NULL;
-  fontSize = 0;
-  xyStrings = NULL;
-  xyCur1 = xyCur2 = NULL;
-  lines = NULL;
+  curWord = NULL;
+  charPos = 0;
+  curFont = NULL;
+  curFontSize = 0;

   nest = 0;
   nTinyChars = 0;
   nest = 0;
   nTinyChars = 0;

+  lastCharOverlap = gFalse;
+  if (!rawOrder) {
+    for (rot = 0; rot < 4; ++rot) {
+      pools[rot] = new TextPool();
+    }
+  }
+  flows = NULL;
+  blocks = NULL;
+  rawWords = NULL;
+  rawLastWord = NULL;
+  fonts = new GList();
+  lastFindXMin = lastFindYMin = 0;
+  haveLastFind = gFalse;

 }
 
 TextPage::~TextPage() {
 }
 
 TextPage::~TextPage() {

+  int rot;
+
+  clear();
+  if (!rawOrder) {
+    for (rot = 0; rot < 4; ++rot) {
+      delete pools[rot];
+    }
+  }
+  delete fonts;
+}
+
+void TextPage::startPage(GfxState *state) {

   clear();
   clear();

+  if (state) {
+    pageWidth = state->getPageWidth();
+    pageHeight = state->getPageHeight();
+  } else {
+    pageWidth = pageHeight = 0;
+  }
+}
+
+void TextPage::endPage() {
+  if (curWord) {
+    endWord();
+  }
+}
+
+void TextPage::clear() {
+  int rot;
+  TextFlow *flow;
+  TextWord *word;
+
+  if (curWord) {
+    delete curWord;
+    curWord = NULL;
+  }
+  if (rawOrder) {
+    while (rawWords) {
+      word = rawWords;
+      rawWords = rawWords->next;
+      delete word;
+    }
+  } else {
+    for (rot = 0; rot < 4; ++rot) {
+      delete pools[rot];
+    }
+    while (flows) {
+      flow = flows;
+      flows = flows->next;
+      delete flow;
+    }
+    gfree(blocks);
+  }
+  deleteGList(fonts, TextFontInfo);
+
+  curWord = NULL;
+  charPos = 0;
+  curFont = NULL;
+  curFontSize = 0;
+  nest = 0;
+  nTinyChars = 0;
+  if (!rawOrder) {
+    for (rot = 0; rot < 4; ++rot) {
+      pools[rot] = new TextPool();
+    }
+  }
+  flows = NULL;
+  blocks = NULL;
+  rawWords = NULL;
+  rawLastWord = NULL;
+  fonts = new GList();

 }
 
 void TextPage::updateFont(GfxState *state) {
 }
 
 void TextPage::updateFont(GfxState *state) {

-  GfxFont *font;
+  GfxFont *gfxFont;

   double *fm;
   char *name;
   int code, mCode, letterCode, anyCode;
   double w;
   double *fm;
   char *name;
   int code, mCode, letterCode, anyCode;
   double w;

+  int i;
+
+  // get the font info object
+  curFont = NULL;
+  for (i = 0; i < fonts->getLength(); ++i) {
+    curFont = (TextFontInfo *)fonts->get(i);
+    if (curFont->matches(state)) {
+      break;
+    }
+    curFont = NULL;
+  }
+  if (!curFont) {
+    curFont = new TextFontInfo(state);
+    fonts->append(curFont);
+  }

 
   // adjust the font size
 
   // adjust the font size

-  fontSize = state->getTransformedFontSize();
-  if ((font = state->getFont()) && font->getType() == fontType3) {
+  gfxFont = state->getFont();
+  curFontSize = state->getTransformedFontSize();
+  if (gfxFont && gfxFont->getType() == fontType3) {

     // This is a hack which makes it possible to deal with some Type 3
     // fonts.  The problem is that it's impossible to know what the
     // base coordinate system used in the font is without actually
     // This is a hack which makes it possible to deal with some Type 3
     // fonts.  The problem is that it's impossible to know what the
     // base coordinate system used in the font is without actually


@@ -206,7 +1722,7 @@ void TextPage::updateFont(GfxState *state) {
     // subset that doesn't contain 'm').
     mCode = letterCode = anyCode = -1;
     for (code = 0; code < 256; ++code) {
     // subset that doesn't contain 'm').
     mCode = letterCode = anyCode = -1;
     for (code = 0; code < 256; ++code) {

-      name = ((Gfx8BitFont *)font)->getCharName(code);
+      name = ((Gfx8BitFont *)gfxFont)->getCharName(code);

       if (name && name[0] == 'm' && name[1] == '\0') {
        mCode = code;
       }
       if (name && name[0] == 'm' && name[1] == '\0') {
        mCode = code;
       }


@@ -215,632 +1731,968 @@ void TextPage::updateFont(GfxState *state) {
           (name[0] >= 'a' && name[0] <= 'z'))) {
        letterCode = code;
       }
           (name[0] >= 'a' && name[0] <= 'z'))) {
        letterCode = code;
       }

-      if (anyCode < 0 && name && ((Gfx8BitFont *)font)->getWidth(code) > 0) {
+      if (anyCode < 0 && name &&
+         ((Gfx8BitFont *)gfxFont)->getWidth(code) > 0) {

        anyCode = code;
       }
     }
     if (mCode >= 0 &&
        anyCode = code;
       }
     }
     if (mCode >= 0 &&

-       (w = ((Gfx8BitFont *)font)->getWidth(mCode)) > 0) {
+       (w = ((Gfx8BitFont *)gfxFont)->getWidth(mCode)) > 0) {

       // 0.6 is a generic average 'm' width -- yes, this is a hack
       // 0.6 is a generic average 'm' width -- yes, this is a hack

-      fontSize *= w / 0.6;
+      curFontSize *= w / 0.6;

     } else if (letterCode >= 0 &&
     } else if (letterCode >= 0 &&

-              (w = ((Gfx8BitFont *)font)->getWidth(letterCode)) > 0) {
+              (w = ((Gfx8BitFont *)gfxFont)->getWidth(letterCode)) > 0) {

       // even more of a hack: 0.5 is a generic letter width
       // even more of a hack: 0.5 is a generic letter width

-      fontSize *= w / 0.5;
+      curFontSize *= w / 0.5;

     } else if (anyCode >= 0 &&
     } else if (anyCode >= 0 &&

-              (w = ((Gfx8BitFont *)font)->getWidth(anyCode)) > 0) {
+              (w = ((Gfx8BitFont *)gfxFont)->getWidth(anyCode)) > 0) {

       // better than nothing: 0.5 is a generic character width
       // better than nothing: 0.5 is a generic character width

-      fontSize *= w / 0.5;
+      curFontSize *= w / 0.5;

     }
     }

-    fm = font->getFontMatrix();
+    fm = gfxFont->getFontMatrix();

     if (fm[0] != 0) {
     if (fm[0] != 0) {

-      fontSize *= fabs(fm[3] / fm[0]);
+      curFontSize *= fabs(fm[3] / fm[0]);

     }
   }
 }
 
     }
   }
 }
 

-void TextPage::beginString(GfxState *state, double x0, double y0) {
+void TextPage::beginWord(GfxState *state, double x0, double y0) {
+  double *txtm, *ctm, *fontm;
+  double m[4], m2[4];
+  int rot;
+

   // This check is needed because Type 3 characters can contain
   // This check is needed because Type 3 characters can contain

-  // text-drawing operations.
-  if (curStr) {
+  // text-drawing operations (when TextPage is being used via
+  // {X,Win}SplashOutputDev rather than TextOutputDev).
+  if (curWord) {

     ++nest;
     return;
   }
 
     ++nest;
     return;
   }
 

-  curStr = new TextString(state, x0, y0, fontSize);
+  // compute the rotation
+  txtm = state->getTextMat();
+  ctm = state->getCTM();
+  m[0] = txtm[0] * ctm[0] + txtm[1] * ctm[2];
+  m[1] = txtm[0] * ctm[1] + txtm[1] * ctm[3];
+  m[2] = txtm[2] * ctm[0] + txtm[3] * ctm[2];
+  m[3] = txtm[2] * ctm[1] + txtm[3] * ctm[3];
+  if (state->getFont()->getType() == fontType3) {
+    fontm = state->getFont()->getFontMatrix();
+    m2[0] = fontm[0] * m[0] + fontm[1] * m[2];
+    m2[1] = fontm[0] * m[1] + fontm[1] * m[3];
+    m2[2] = fontm[2] * m[0] + fontm[3] * m[2];
+    m2[3] = fontm[2] * m[1] + fontm[3] * m[3];
+    m[0] = m2[0];
+    m[1] = m2[1];
+    m[2] = m2[2];
+    m[3] = m2[3];
+  }
+  if (fabs(m[0] * m[3]) > fabs(m[1] * m[2])) {
+    rot = (m[3] < 0) ? 0 : 2;
+  } else {
+    rot = (m[2] > 0) ? 1 : 3;
+  }
+
+  curWord = new TextWord(state, rot, x0, y0, charPos, curFont, curFontSize);

 }
 
 void TextPage::addChar(GfxState *state, double x, double y,
 }
 
 void TextPage::addChar(GfxState *state, double x, double y,

-                      double dx, double dy, Unicode *u, int uLen) {
-  double x1, y1, w1, h1, dx2, dy2;
-  int n, i;
+                      double dx, double dy,
+                      CharCode c, Unicode *u, int uLen) {
+  double x1, y1, w1, h1, dx2, dy2, base, sp;
+  int i;
+
+  // if the previous char was a space, addChar will have called
+  // endWord, so we need to start a new word
+  if (!curWord) {
+    beginWord(state, x, y);
+  }

 
 

+  // throw away chars that aren't inside the page bounds

   state->transform(x, y, &x1, &y1);
   state->transform(x, y, &x1, &y1);

-  if (x1 < 0 || x1 > state->getPageWidth() ||
-      y1 < 0 || y1 > state->getPageHeight()) {
+  if (x1 < 0 || x1 > pageWidth ||
+      y1 < 0 || y1 > pageHeight) {

     return;
   }
     return;
   }

-  state->textTransformDelta(state->getCharSpace() * state->getHorizScaling(),
-                           0, &dx2, &dy2);
+
+  // subtract char and word spacing from the dx,dy values
+  sp = state->getCharSpace();
+  if (c == (CharCode)0x20) {
+    sp += state->getWordSpace();
+  }
+  state->textTransformDelta(sp * state->getHorizScaling(), 0, &dx2, &dy2);

   dx -= dx2;
   dy -= dy2;
   state->transformDelta(dx, dy, &w1, &h1);
   dx -= dx2;
   dy -= dy2;
   state->transformDelta(dx, dy, &w1, &h1);

+
+  // check the tiny chars limit

   if (!globalParams->getTextKeepTinyChars() &&
       fabs(w1) < 3 && fabs(h1) < 3) {
   if (!globalParams->getTextKeepTinyChars() &&
       fabs(w1) < 3 && fabs(h1) < 3) {

-    if (++nTinyChars > 20000) {
+    if (++nTinyChars > 50000) {

       return;
     }
   }
       return;
     }
   }

-  n = curStr->len;
-  if (n > 0 && x1 - curStr->xRight[n-1] >
-               0.1 * (curStr->yMax - curStr->yMin)) {
-    // large char spacing is sometimes used to move text around
-    endString();
-    beginString(state, x, y);
-  }
-  if (uLen == 1 && u[0] == (Unicode)0x20 &&
-      w1 > 0.5 * (curStr->yMax - curStr->yMin)) {
-    // large word spacing is sometimes used to move text around
+
+  // break words at space character
+  if (uLen == 1 && u[0] == (Unicode)0x20) {
+    ++curWord->charLen;
+    ++charPos;
+    endWord();

     return;
   }
     return;
   }

+
+  // start a new word if:
+  // (1) this character's baseline doesn't match the current word's
+  //     baseline, or
+  // (2) there is space between the end of the current word and this
+  //     character, or
+  // (3) this character overlaps the previous one (duplicated text), or
+  // (4) the previous character was an overlap (we want each duplicated
+  //     characters to be in a word by itself)
+  base = sp = 0; // make gcc happy
+  if (curWord->len > 0) {
+    switch (curWord->rot) {
+    case 0:
+      base = y1;
+      sp = x1 - curWord->xMax;
+      break;
+    case 1:
+      base = x1;
+      sp = y1 - curWord->yMax;
+      break;
+    case 2:
+      base = y1;
+      sp = curWord->xMin - x1;
+      break;
+    case 3:
+      base = x1;
+      sp = curWord->yMin - y1;
+      break;
+    }
+    if (fabs(base - curWord->base) > 0.5 ||
+       sp > minWordBreakSpace * curWord->fontSize ||
+       sp < -minDupBreakOverlap * curWord->fontSize ||
+       lastCharOverlap) {
+      lastCharOverlap = gTrue;
+      endWord();
+      beginWord(state, x, y);
+    } else {
+      lastCharOverlap = gFalse;
+    }
+  } else {
+    lastCharOverlap = gFalse;
+  }
+
+  // page rotation and/or transform matrices can cause text to be
+  // drawn in reverse order -- in this case, swap the begin/end
+  // coordinates and break text into individual chars
+  if ((curWord->rot == 0 && w1 < 0) ||
+      (curWord->rot == 1 && h1 < 0) ||
+      (curWord->rot == 2 && w1 > 0) ||
+      (curWord->rot == 3 && h1 > 0)) {
+    endWord();
+    beginWord(state, x + dx, y + dy);
+    x1 += w1;
+    y1 += h1;
+    w1 = -w1;
+    h1 = -h1;
+  }
+
+  // add the characters to the current word

   if (uLen != 0) {
     w1 /= uLen;
     h1 /= uLen;
   }
   for (i = 0; i < uLen; ++i) {
   if (uLen != 0) {
     w1 /= uLen;
     h1 /= uLen;
   }
   for (i = 0; i < uLen; ++i) {

-    curStr->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, u[i]);
+    curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, u[i]);

   }
   }

+  ++curWord->charLen;
+  ++charPos;

 }
 
 }
 

-void TextPage::endString() {
+void TextPage::endWord() {

   // This check is needed because Type 3 characters can contain
   // This check is needed because Type 3 characters can contain

-  // text-drawing operations.
+  // text-drawing operations (when TextPage is being used via
+  // {X,Win}SplashOutputDev rather than TextOutputDev).

   if (nest > 0) {
     --nest;
     return;
   }
 
   if (nest > 0) {
     --nest;
     return;
   }
 

-  addString(curStr);
-  curStr = NULL;
+  if (curWord) {
+    addWord(curWord);
+    curWord = NULL;
+  }

 }
 
 }
 

-void TextPage::addString(TextString *str) {
-  TextString *p1, *p2;
-
-  // throw away zero-length strings -- they don't have valid xMin/xMax
+void TextPage::addWord(TextWord *word) {
+  // throw away zero-length words -- they don't have valid xMin/xMax

   // values, and they're useless anyway
   // values, and they're useless anyway

-  if (str->len == 0) {
-    delete str;
+  if (word->len == 0) {
+    delete word;

     return;
   }
 
     return;
   }
 

-  // insert string in xy list

   if (rawOrder) {
   if (rawOrder) {

-    p1 = xyCur1;
-    p2 = NULL;
-  } else if ((!xyCur1 || xyBefore(xyCur1, str)) &&
-            (!xyCur2 || xyBefore(str, xyCur2))) {
-    p1 = xyCur1;
-    p2 = xyCur2;
-  } else if (xyCur1 && xyBefore(xyCur1, str)) {
-    for (p1 = xyCur1, p2 = xyCur2; p2; p1 = p2, p2 = p2->next) {
-      if (xyBefore(str, p2)) {
-       break;
-      }
-    }
-    xyCur2 = p2;
-  } else {
-    for (p1 = NULL, p2 = xyStrings; p2; p1 = p2, p2 = p2->next) {
-      if (xyBefore(str, p2)) {
-       break;
-      }
+    if (rawLastWord) {
+      rawLastWord->next = word;
+    } else {
+      rawWords = word;

     }
     }

-    xyCur2 = p2;
-  }
-  xyCur1 = str;
-  if (p1) {
-    p1->next = str;
+    rawLastWord = word;

   } else {
   } else {

-    xyStrings = str;
+    pools[word->rot]->addWord(word);

   }
   }

-  str->next = p2;

 }
 
 }
 

-void TextPage::coalesce() {
-  TextLine *line, *line0;
-  TextBlock *yxBlocks, *xyBlocks, *blk, *blk0, *blk1, *blk2;
-  TextString *str0, *str1, *str2, *str3, *str4;
-  TextString *str1prev, *str2prev, *str3prev;
-  TextOutColumnEdge *edges;
+void TextPage::coalesce(GBool physLayout) {

   UnicodeMap *uMap;
   UnicodeMap *uMap;

-  GBool isUnicode;
-  char buf[8];
-  int edgesLength, edgesSize;
-  double x, yMin, yMax;
-  double space, fit1, fit2, h;
-  int col1, col2, d;
-  int i, j;
+  TextPool *pool;
+  TextWord *word0, *word1, *word2;
+  TextLine *line;
+  TextBlock *blkList, *blkStack, *blk, *lastBlk, *blk0, *blk1;
+  TextBlock **blkArray;
+  TextFlow *flow, *lastFlow;
+  int rot, poolMinBaseIdx, baseIdx, startBaseIdx;
+  double minBase, maxBase, newMinBase, newMaxBase;
+  double fontSize, colSpace1, colSpace2, lineSpace, intraLineSpace, blkSpace;
+  GBool found;
+  int count[4];
+  int lrCount;
+  int firstBlkIdx, nBlocksLeft;
+  int col1, col2;
+  int i, j, n;

 
 

-#if 0 //~ for debugging
-  for (str1 = xyStrings; str1; str1 = str1->next) {
-    printf("x=%.2f..%.2f  y=%.2f..%.2f  size=%.2f '",
-          str1->xMin, str1->xMax, str1->yMin, str1->yMax,
-          (str1->yMax - str1->yMin));
-    for (i = 0; i < str1->len; ++i) {
-      fputc(str1->text[i] & 0xff, stdout);
+  if (rawOrder) {
+    primaryRot = 0;
+    primaryLR = gTrue;
+    return;
+  }
+
+  uMap = globalParams->getTextEncoding();
+  blkList = NULL;
+  lastBlk = NULL;
+  nBlocks = 0;
+  primaryRot = -1;
+
+#if 0 // for debugging
+  printf("*** initial words ***\n");
+  for (rot = 0; rot < 4; ++rot) {
+    pool = pools[rot];
+    for (baseIdx = pool->minBaseIdx; baseIdx <= pool->maxBaseIdx; ++baseIdx) {
+      for (word0 = pool->getPool(baseIdx); word0; word0 = word0->next) {
+       printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f '",
+              word0->xMin, word0->xMax, word0->yMin, word0->yMax,
+              word0->base, word0->fontSize);
+       for (i = 0; i < word0->len; ++i) {
+         fputc(word0->text[i] & 0xff, stdout);
+       }
+       printf("'\n");
+      }

     }
     }

-    printf("'\n");

   }
   }

-  printf("\n------------------------------------------------------------\n\n");
+  printf("\n");

 #endif
 
 #endif
 

-  // build the list of column edges
-  edges = NULL;
-  edgesLength = edgesSize = 0;
-  if (!rawOrder) {
-    for (str1prev = NULL, str1 = xyStrings;
-        str1;
-        str1prev = str1, str1 = str1->next) {
-      if (str1->marked) {
-       continue;
-      }
-      h = str1->yMax - str1->yMin;
-      if (str1prev && (str1->xMin - str1prev->xMax) / h < textOutColSpace) {
-       continue;
+  //----- assemble the blocks
+
+  //~ add an outer loop for writing mode (vertical text)
+
+  // build blocks for each rotation value
+  for (rot = 0; rot < 4; ++rot) {
+    pool = pools[rot];
+    poolMinBaseIdx = pool->minBaseIdx;
+    count[rot] = 0;
+
+    // add blocks until no more words are left
+    while (1) {
+
+      // find the first non-empty line in the pool
+      for (;
+          poolMinBaseIdx <= pool->maxBaseIdx &&
+            !pool->getPool(poolMinBaseIdx);
+          ++poolMinBaseIdx) ;
+      if (poolMinBaseIdx > pool->maxBaseIdx) {
+       break;

       }
       }

-      x = str1->xMin;
-      yMin = str1->yMin;
-      yMax = str1->yMax;
-      for (str2prev = str1, str2 = str1->next;
-          str2;
-          str2prev = str2, str2 = str2->next) {
-       h = str2->yMax - str2->yMin;
-       if (!str2->marked &&
-           (str2->xMin - str2prev->xMax) / h > textOutColSpace &&
-           fabs(str2->xMin - x) < 0.5 &&
-           str2->yMin - yMax < 0.3 * h &&
-           yMin - str2->yMax < 0.3 * h) {
-         break;
+
+      // look for the left-most word in the first four lines of the
+      // pool -- this avoids starting with a superscript word
+      startBaseIdx = poolMinBaseIdx;
+      for (baseIdx = poolMinBaseIdx + 1;
+          baseIdx < poolMinBaseIdx + 4 && baseIdx <= pool->maxBaseIdx;
+          ++baseIdx) {
+       if (!pool->getPool(baseIdx)) {
+         continue;

        }
        }

-      }
-      if (str2) {
-       if (str2->yMin < yMin) {
-         yMin = str2->yMin;
+       if (pool->getPool(baseIdx)->primaryCmp(pool->getPool(startBaseIdx))
+           < 0) {
+         startBaseIdx = baseIdx;

        }
        }

-       if (str2->yMax > yMax) {
-         yMax = str2->yMax;
+      }
+
+      // create a new block
+      word0 = pool->getPool(startBaseIdx);
+      pool->setPool(startBaseIdx, word0->next);
+      word0->next = NULL;
+      blk = new TextBlock(this, rot);
+      blk->addWord(word0);
+
+      fontSize = word0->fontSize;
+      minBase = maxBase = word0->base;
+      colSpace1 = minColSpacing1 * fontSize;
+      colSpace2 = minColSpacing2 * fontSize;
+      lineSpace = maxLineSpacingDelta * fontSize;
+      intraLineSpace = maxIntraLineDelta * fontSize;
+
+      // add words to the block
+      do {
+       found = gFalse;
+
+       // look for words on the line above the current top edge of
+       // the block
+       newMinBase = minBase;
+       for (baseIdx = pool->getBaseIdx(minBase);
+            baseIdx >= pool->getBaseIdx(minBase - lineSpace);
+            --baseIdx) {
+         word0 = NULL;
+         word1 = pool->getPool(baseIdx);
+         while (word1) {
+           if (word1->base < minBase &&
+               word1->base >= minBase - lineSpace &&
+               ((rot == 0 || rot == 2)
+                ? (word1->xMin < blk->xMax && word1->xMax > blk->xMin)
+                : (word1->yMin < blk->yMax && word1->yMax > blk->yMin)) &&
+               fabs(word1->fontSize - fontSize) <
+                 maxBlockFontSizeDelta1 * fontSize) {
+             word2 = word1;
+             if (word0) {
+               word0->next = word1->next;
+             } else {
+               pool->setPool(baseIdx, word1->next);
+             }
+             word1 = word1->next;
+             word2->next = NULL;
+             blk->addWord(word2);
+             found = gTrue;
+             newMinBase = word2->base;
+           } else {
+             word0 = word1;
+             word1 = word1->next;
+           }
+         }

        }
        }

-       str2->marked = gTrue;
-       for (str3prev = str1, str3 = str1->next;
-            str3;
-            str3prev = str3, str3 = str3->next) {
-         h = str3->yMax - str3->yMin;
-         if (!str3->marked &&
-             (str3->xMin - str3prev->xMax) / h > textOutColSpace &&
-             fabs(str3->xMin - x) < 0.5 &&
-             str3->yMin - yMax < 0.3 * h &&
-             yMin - str3->yMax < 0.3 * h) {
-           break;
+       minBase = newMinBase;
+
+       // look for words on the line below the current bottom edge of
+       // the block
+       newMaxBase = maxBase;
+       for (baseIdx = pool->getBaseIdx(maxBase);
+            baseIdx <= pool->getBaseIdx(maxBase + lineSpace);
+            ++baseIdx) {
+         word0 = NULL;
+         word1 = pool->getPool(baseIdx);
+         while (word1) {
+           if (word1->base > maxBase &&
+               word1->base <= maxBase + lineSpace &&
+               ((rot == 0 || rot == 2)
+                ? (word1->xMin < blk->xMax && word1->xMax > blk->xMin)
+                : (word1->yMin < blk->yMax && word1->yMax > blk->yMin)) &&
+               fabs(word1->fontSize - fontSize) <
+                 maxBlockFontSizeDelta1 * fontSize) {
+             word2 = word1;
+             if (word0) {
+               word0->next = word1->next;
+             } else {
+               pool->setPool(baseIdx, word1->next);
+             }
+             word1 = word1->next;
+             word2->next = NULL;
+             blk->addWord(word2);
+             found = gTrue;
+             newMaxBase = word2->base;
+           } else {
+             word0 = word1;
+             word1 = word1->next;
+           }

          }
        }
          }
        }

-       if (str3) {
-         if (str3->yMin < yMin) {
-           yMin = str3->yMin;
+       maxBase = newMaxBase;
+
+       // look for words that are on lines already in the block, and
+       // that overlap the block horizontally
+       for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
+            baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
+            ++baseIdx) {
+         word0 = NULL;
+         word1 = pool->getPool(baseIdx);
+         while (word1) {
+           if (word1->base >= minBase - intraLineSpace &&
+               word1->base <= maxBase + intraLineSpace &&
+               ((rot == 0 || rot == 2)
+                ? (word1->xMin < blk->xMax + colSpace1 &&
+                   word1->xMax > blk->xMin - colSpace1)
+                : (word1->yMin < blk->yMax + colSpace1 &&
+                   word1->yMax > blk->yMin - colSpace1)) &&
+               fabs(word1->fontSize - fontSize) <
+                 maxBlockFontSizeDelta2 * fontSize) {
+             word2 = word1;
+             if (word0) {
+               word0->next = word1->next;
+             } else {
+               pool->setPool(baseIdx, word1->next);
+             }
+             word1 = word1->next;
+             word2->next = NULL;
+             blk->addWord(word2);
+             found = gTrue;
+           } else {
+             word0 = word1;
+             word1 = word1->next;
+           }

          }
          }

-         if (str3->yMax > yMax) {
-           yMax = str3->yMax;
+       }
+
+       // only check for outlying words (the next two chunks of code)
+       // if we didn't find anything else
+       if (found) {
+         continue;
+       }
+
+       // scan down the left side of the block, looking for words
+       // that are near (but not overlapping) the block; if there are
+       // three or fewer, add them to the block
+       n = 0;
+       for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
+            baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
+            ++baseIdx) {
+         word1 = pool->getPool(baseIdx);
+         while (word1) {
+           if (word1->base >= minBase - intraLineSpace &&
+               word1->base <= maxBase + intraLineSpace &&
+               ((rot == 0 || rot == 2)
+                ? (word1->xMax <= blk->xMin &&
+                   word1->xMax > blk->xMin - colSpace2)
+                : (word1->yMax <= blk->yMin &&
+                   word1->yMax > blk->yMin - colSpace2)) &&
+               fabs(word1->fontSize - fontSize) <
+                 maxBlockFontSizeDelta3 * fontSize) {
+             ++n;
+             break;
+           }
+           word1 = word1->next;

          }
          }

-         str3->marked = gTrue;
-         do {
-           for (str2prev = str1, str2 = str1->next;
-                str2;
-                str2prev = str2, str2 = str2->next) {
-             h = str2->yMax - str2->yMin;
-             if (!str2->marked &&
-                 (str2->xMin - str2prev->xMax) / h > textOutColSpace &&
-                 fabs(str2->xMin - x) < 0.5 &&
-                 str2->yMin - yMax < 0.3 * h &&
-                 yMin - str2->yMax < 0.3 * h) {
-               if (str2->yMin < yMin) {
-                 yMin = str2->yMin;
+       }
+       if (n > 0 && n <= 3) {
+         for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
+              baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
+              ++baseIdx) {
+           word0 = NULL;
+           word1 = pool->getPool(baseIdx);
+           while (word1) {
+             if (word1->base >= minBase - intraLineSpace &&
+                 word1->base <= maxBase + intraLineSpace &&
+                 ((rot == 0 || rot == 2)
+                  ? (word1->xMax <= blk->xMin &&
+                     word1->xMax > blk->xMin - colSpace2)
+                  : (word1->yMax <= blk->yMin &&
+                     word1->yMax > blk->yMin - colSpace2)) &&
+                 fabs(word1->fontSize - fontSize) <
+                   maxBlockFontSizeDelta3 * fontSize) {
+               word2 = word1;
+               if (word0) {
+                 word0->next = word1->next;
+               } else {
+                 pool->setPool(baseIdx, word1->next);

                }
                }

-               if (str2->yMax > yMax) {
-                 yMax = str2->yMax;
+               word1 = word1->next;
+               word2->next = NULL;
+               blk->addWord(word2);
+               if (word2->base < minBase) {
+                 minBase = word2->base;
+               } else if (word2->base > maxBase) {
+                 maxBase = word2->base;

                }
                }

-               str2->marked = gTrue;
+               found = gTrue;

                break;
                break;

+             } else {
+               word0 = word1;
+               word1 = word1->next;

              }
            }
              }
            }

-         } while (str2);
-         if (edgesLength == edgesSize) {
-           edgesSize = edgesSize ? 2 * edgesSize : 16;
-           edges = (TextOutColumnEdge *)
-             grealloc(edges, edgesSize * sizeof(TextOutColumnEdge));

          }
          }

-         edges[edgesLength].x = x;
-         edges[edgesLength].y0 = yMin;
-         edges[edgesLength].y1 = yMax;
-         ++edgesLength;
-       } else {
-         str2->marked = gFalse;

        }
        }

-      }
-      str1->marked = gTrue;
-    }
-  }
-
-#if 0 //~ for debugging
-  printf("column edges:\n");
-  for (i = 0; i < edgesLength; ++i) {
-    printf("%d: x=%.2f y0=%.2f y1=%.2f\n",
-          i, edges[i].x, edges[i].y0, edges[i].y1);
-  }
-  printf("\n------------------------------------------------------------\n\n");
-#endif

 
 

-  // build the blocks
-  yxBlocks = NULL;
-  blk1 = blk2 = NULL;
-  while (xyStrings) {
-
-    // build the block
-    str0 = xyStrings;
-    xyStrings = xyStrings->next;
-    str0->next = NULL;
-    blk = new TextBlock();
-    blk->strings = str0;
-    blk->xMin = str0->xMin;
-    blk->xMax = str0->xMax;
-    blk->yMin = str0->yMin;
-    blk->yMax = str0->yMax;
-    while (xyStrings) {
-      str1 = NULL;
-      str2 = xyStrings;
-      fit1 = coalesceFit(str0, str2);
-      if (!rawOrder) {
-       // look for best-fitting string
-       space = str0->yMax - str0->yMin;
-       for (str3 = xyStrings, str4 = xyStrings->next;
-            str4 && str4->xMin - str0->xMax <= space;
-            str3 = str4, str4 = str4->next) {
-         fit2 = coalesceFit(str0, str4);
-         if (fit2 < fit1) {
-           str1 = str3;
-           str2 = str4;
-           fit1 = fit2;
+       // scan down the right side of the block, looking for words
+       // that are near (but not overlapping) the block; if there are
+       // three or fewer, add them to the block
+       n = 0;
+       for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
+            baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
+            ++baseIdx) {
+         word1 = pool->getPool(baseIdx);
+         while (word1) {
+           if (word1->base >= minBase - intraLineSpace &&
+               word1->base <= maxBase + intraLineSpace &&
+               ((rot == 0 || rot == 2)
+                ? (word1->xMin >= blk->xMax &&
+                   word1->xMin < blk->xMax + colSpace2)
+                : (word1->yMin >= blk->yMax &&
+                   word1->yMin < blk->yMax + colSpace2)) &&
+               fabs(word1->fontSize - fontSize) <
+                 maxBlockFontSizeDelta3 * fontSize) {
+             ++n;
+             break;
+           }
+           word1 = word1->next;

          }
        }
          }
        }

-      }
-      if (fit1 > 1) {
-       // no fit - we're done with this block
-       break;
-      }
-
-      // if we've hit a column edge we're done with this block
-      if (fit1 > 0.2) {
-       for (i = 0; i < edgesLength; ++i) {
-         if (str0->xMax < edges[i].x + 0.5 && edges[i].x - 0.5 < str2->xMin &&
-             str0->yMin < edges[i].y1 && str0->yMax > edges[i].y0 &&
-             str2->yMin < edges[i].y1 && str2->yMax > edges[i].y0) {
-           break;
+       if (n > 0 && n <= 3) {
+         for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
+              baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
+              ++baseIdx) {
+           word0 = NULL;
+           word1 = pool->getPool(baseIdx);
+           while (word1) {
+             if (word1->base >= minBase - intraLineSpace &&
+                 word1->base <= maxBase + intraLineSpace &&
+                 ((rot == 0 || rot == 2)
+                  ? (word1->xMin >= blk->xMax &&
+                     word1->xMin < blk->xMax + colSpace2)
+                  : (word1->yMin >= blk->yMax &&
+                     word1->yMin < blk->yMax + colSpace2)) &&
+                 fabs(word1->fontSize - fontSize) <
+                   maxBlockFontSizeDelta3 * fontSize) {
+               word2 = word1;
+               if (word0) {
+                 word0->next = word1->next;
+               } else {
+                 pool->setPool(baseIdx, word1->next);
+               }
+               word1 = word1->next;
+               word2->next = NULL;
+               blk->addWord(word2);
+               if (word2->base < minBase) {
+                 minBase = word2->base;
+               } else if (word2->base > maxBase) {
+                 maxBase = word2->base;
+               }
+               found = gTrue;
+               break;
+             } else {
+               word0 = word1;
+               word1 = word1->next;
+             }
+           }

          }
        }
          }
        }

-       if (i < edgesLength) {
-         break;
-       }
-      }

 
 

-      if (str1) {
-       str1->next = str2->next;
+      } while (found);
+
+      //~ need to compute the primary writing mode (horiz/vert) in
+      //~ addition to primary rotation
+
+      // coalesce the block, and add it to the list
+      blk->coalesce(uMap);
+      if (lastBlk) {
+       lastBlk->next = blk;

       } else {
       } else {

-       xyStrings = str2->next;
+       blkList = blk;

       }
       }

-      str0->next = str2;
-      str2->next = NULL;
-      if (str2->xMax > blk->xMax) {
-       blk->xMax = str2->xMax;
+      lastBlk = blk;
+      count[rot] += blk->charCount;
+      if (primaryRot < 0 || count[rot] > count[primaryRot]) {
+       primaryRot = rot;

       }
       }

-      if (str2->yMin < blk->yMin) {
-       blk->yMin = str2->yMin;
-      }
-      if (str2->yMax > blk->yMax) {
-       blk->yMax = str2->yMax;
-      }
-      str0 = str2;
-    }
-
-    // insert block on list
-    if (!rawOrder) {
-      // insert block on list in yx order
-      for (blk1 = NULL, blk2 = yxBlocks;
-          blk2 && !yxBefore(blk, blk2);
-          blk1 = blk2, blk2 = blk2->next) ;
+      ++nBlocks;

     }
     }

-    blk->next = blk2;
-    if (blk1) {
-      blk1->next = blk;
-    } else {
-      yxBlocks = blk;
-    }
-    blk1 = blk;

   }
 
   }
 

-  gfree(edges);
-
-  // the strings are now owned by the lines/blocks tree
-  xyStrings = NULL;
+#if 0 // for debugging 
+  printf("*** rotation ***\n");
+  for (rot = 0; rot < 4; ++rot) {
+    printf("  %d: %6d\n", rot, count[rot]);
+  }
+  printf("  primary rot = %d\n", primaryRot);
+  printf("\n");
+#endif

 
 

-  // build the block text
-  uMap = globalParams->getTextEncoding();
-  isUnicode = uMap ? uMap->isUnicode() : gFalse;
-  for (blk = yxBlocks; blk; blk = blk->next) {
-    blk->len = 0;
-    for (str1 = blk->strings; str1; str1 = str1->next) {
-      blk->len += str1->len;
-      if (str1->next && str1->next->xMin - str1->xMax >
-                       textOutSpace * (str1->yMax - str1->yMin)) {
-       str1->spaceAfter = gTrue;
-       ++blk->len;
-      } else {
-       str1->spaceAfter = gFalse;
-      }
-    }
-    blk->text = (Unicode *)gmalloc(blk->len * sizeof(Unicode));
-    blk->xRight = (double *)gmalloc(blk->len * sizeof(double));
-    blk->col = (int *)gmalloc(blk->len * sizeof(int));
-    i = 0;
-    for (str1 = blk->strings; str1; str1 = str1->next) {
-      for (j = 0; j < str1->len; ++j) {
-       blk->text[i] = str1->text[j];
-       blk->xRight[i] = str1->xRight[j];
-       ++i;
-      }
-      if (str1->spaceAfter) {
-       blk->text[i] = (Unicode)0x0020;
-       blk->xRight[i] = str1->next->xMin;
-       ++i;
-      }
-    }
-    blk->convertedLen = 0;
-    for (j = 0; j < blk->len; ++j) {
-      blk->col[j] = blk->convertedLen;
-      if (isUnicode) {
-       ++blk->convertedLen;
-      } else if (uMap) {
-       blk->convertedLen += uMap->mapUnicode(blk->text[j], buf, sizeof(buf));
+#if 0 // for debugging
+  printf("*** blocks ***\n");
+  for (blk = blkList; blk; blk = blk->next) {
+    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f\n",
+          blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax);
+    for (line = blk->lines; line; line = line->next) {
+      printf("  line: x=%.2f..%.2f y=%.2f..%.2f base=%.2f\n",
+            line->xMin, line->xMax, line->yMin, line->yMax, line->base);
+      for (word0 = line->words; word0; word0 = word0->next) {
+       printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
+              word0->xMin, word0->xMax, word0->yMin, word0->yMax,
+              word0->base, word0->fontSize, word0->spaceAfter);
+       for (i = 0; i < word0->len; ++i) {
+         fputc(word0->text[i] & 0xff, stdout);
+       }
+       printf("'\n");

       }
     }
   }
       }
     }
   }

-  if (uMap) {
-    uMap->decRefCnt();
-  }
+  printf("\n");
+#endif

 
 

-#if 0 //~ for debugging
-  for (blk = yxBlocks; blk; blk = blk->next) {
-    printf("[block: x=%.2f..%.2f y=%.2f..%.2f len=%d]\n",
-          blk->xMin, blk->xMax, blk->yMin, blk->yMax, blk->len);
-    TextString *str;
-    for (str = blk->strings; str; str = str->next) {
-      printf("    x=%.2f..%.2f  y=%.2f..%.2f  size=%.2f'",
-            str->xMin, str->xMax, str->yMin, str->yMax,
-            (str->yMax - str->yMin));
-      for (i = 0; i < str->len; ++i) {
-       fputc(str->text[i] & 0xff, stdout);
-      }
-      if (str->spaceAfter) {
-       fputc(' ', stdout);
+  // determine the primary direction
+  lrCount = 0;
+  for (blk = blkList; blk; blk = blk->next) {
+    for (line = blk->lines; line; line = line->next) {
+      for (word0 = line->words; word0; word0 = word0->next) {
+       for (i = 0; i < word0->len; ++i) {
+         if (unicodeTypeL(word0->text[i])) {
+           ++lrCount;
+         } else if (unicodeTypeR(word0->text[i])) {
+           --lrCount;
+         }
+       }

       }
       }

-      printf("'\n");

     }
   }
     }
   }

-  printf("\n------------------------------------------------------------\n\n");
+  primaryLR = lrCount >= 0;
+
+#if 0 // for debugging
+  printf("*** direction ***\n");
+  printf("lrCount = %d\n", lrCount);
+  printf("primaryLR = %d\n", primaryLR);

 #endif
 
 #endif
 

-  // build the lines
-  lines = NULL;
-  line0 = NULL;
-  while (yxBlocks) {
-    blk0 = yxBlocks;
-    yxBlocks = yxBlocks->next;
-    blk0->next = NULL;
-    line = new TextLine();
-    line->blocks = blk0;
-    line->yMin = blk0->yMin;
-    line->yMax = blk0->yMax;
-    while (yxBlocks) {
-
-      // remove duplicated text (fake boldface, shadowed text)
-      h = blk0->yMax - blk0->yMin;
-      if (yxBlocks->len == blk0->len &&
-         !memcmp(yxBlocks->text, blk0->text,
-                 yxBlocks->len * sizeof(Unicode)) &&
-         fabs(yxBlocks->yMin - blk0->yMin) / h < 0.2 &&
-         fabs(yxBlocks->yMax - blk0->yMax) / h < 0.2 &&
-         fabs(yxBlocks->xMin - blk0->xMin) / h < 0.2 &&
-         fabs(yxBlocks->xMax - blk0->xMax) / h < 0.2) {
-       blk1 = yxBlocks;
-       yxBlocks = yxBlocks->next;
-       delete blk1;
-       continue;
-      }
+  //----- column assignment

 
 

-      if (rawOrder && yxBlocks->yMax < blk0->yMin) {
+  // sort blocks into xy order for column assignment
+  blocks = (TextBlock **)gmalloc(nBlocks * sizeof(TextBlock *));
+  for (blk = blkList, i = 0; blk; blk = blk->next, ++i) {
+    blocks[i] = blk;
+  }
+  qsort(blocks, nBlocks, sizeof(TextBlock *), &TextBlock::cmpXYPrimaryRot);
+
+  // column assignment
+  for (i = 0; i < nBlocks; ++i) {
+    blk0 = blocks[i];
+    col1 = 0;
+    for (j = 0; j < i; ++j) {
+      blk1 = blocks[j];
+      col2 = 0; // make gcc happy
+      switch (primaryRot) {
+      case 0:
+       if (blk0->xMin > blk1->xMax) {
+         col2 = blk1->col + blk1->nColumns + 3;
+       } else {
+         col2 = blk1->col + (int)(((blk0->xMin - blk1->xMin) /
+                                   (blk1->xMax - blk1->xMin)) *
+                                  blk1->nColumns);
+       }

        break;
        break;

-      }
-      if (yxBlocks->yMin > 0.2*blk0->yMin + 0.8*blk0->yMax ||
-         yxBlocks->xMin < blk0->xMax) {
+      case 1:
+       if (blk0->yMin > blk1->yMax) {
+         col2 = blk1->col + blk1->nColumns + 3;
+       } else {
+         col2 = blk1->col + (int)(((blk0->yMin - blk1->yMin) /
+                                   (blk1->yMax - blk1->yMin)) *
+                                  blk1->nColumns);
+       }
+       break;
+      case 2:
+       if (blk0->xMax < blk1->xMin) {
+         col2 = blk1->col + blk1->nColumns + 3;
+       } else {
+         col2 = blk1->col + (int)(((blk0->xMax - blk1->xMax) /
+                                   (blk1->xMin - blk1->xMax)) *
+                                  blk1->nColumns);
+       }
+       break;
+      case 3:
+       if (blk0->yMax < blk1->yMin) {
+         col2 = blk1->col + blk1->nColumns + 3;
+       } else {
+         col2 = blk1->col + (int)(((blk0->yMax - blk1->yMax) /
+                                   (blk1->yMin - blk1->yMax)) *
+                                  blk1->nColumns);
+       }

        break;
       }
        break;
       }

-      blk1 = yxBlocks;
-      yxBlocks = yxBlocks->next;
-      blk0->next = blk1;
-      blk1->next = NULL;
-      if (blk1->yMin < line->yMin) {
-       line->yMin = blk1->yMin;
+      if (col2 > col1) {
+       col1 = col2;

       }
       }

-      if (blk1->yMax > line->yMax) {
-       line->yMax = blk1->yMax;
+    }
+    blk0->col = col1;
+    for (line = blk0->lines; line; line = line->next) {
+      for (j = 0; j <= line->len; ++j) {
+       line->col[j] += col1;

       }
       }

-      blk0 = blk1;

     }
     }

-    if (line0) {
-      line0->next = line;
-    } else {
-      lines = line;
+  }
+
+#if 0 // for debugging
+  printf("*** blocks, after column assignment ***\n");
+  for (blk = blkList; blk; blk = blk->next) {
+    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f col=%d nCols=%d\n",
+          blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax, blk->col,
+          blk->nColumns);
+    for (line = blk->lines; line; line = line->next) {
+      printf("  line:\n");
+      for (word0 = line->words; word0; word0 = word0->next) {
+       printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
+              word0->xMin, word0->xMax, word0->yMin, word0->yMax,
+              word0->base, word0->fontSize, word0->spaceAfter);
+       for (i = 0; i < word0->len; ++i) {
+         fputc(word0->text[i] & 0xff, stdout);
+       }
+       printf("'\n");
+      }

     }
     }

-    line->next = NULL;
-    line0 = line;

   }
   }

+  printf("\n");
+#endif

 
 

+  //----- reading order sort

 
 

-  // sort the blocks into xy order
-  xyBlocks = NULL;
-  for (line = lines; line; line = line->next) {
-    for (blk = line->blocks; blk; blk = blk->next) {
-      for (blk1 = NULL, blk2 = xyBlocks;
-          blk2 && !xyBefore(blk, blk2);
-          blk1 = blk2, blk2 = blk2->xyNext) ;
-      blk->xyNext = blk2;
-      if (blk1) {
-       blk1->xyNext = blk;
-      } else {
-       xyBlocks = blk;
+  // sort blocks into yx order (in preparation for reading order sort)
+  qsort(blocks, nBlocks, sizeof(TextBlock *), &TextBlock::cmpYXPrimaryRot);
+
+  // compute space on left and right sides of each block
+  for (i = 0; i < nBlocks; ++i) {
+    blk0 = blocks[i];
+    for (j = 0; j < nBlocks; ++j) {
+      blk1 = blocks[j];
+      if (blk1 != blk0) {
+       blk0->updatePriMinMax(blk1);

       }
     }
   }
 
       }
     }
   }
 

-#if 0 //~ for debugging
-  for (blk = xyBlocks; blk; blk = blk->xyNext) {
-    printf("[block: x=%.2f..%.2f y=%.2f..%.2f len=%d]\n",
-          blk->xMin, blk->xMax, blk->yMin, blk->yMax, blk->len);
-    TextString *str;
-    for (str = blk->strings; str; str = str->next) {
-      printf("    x=%.2f..%.2f  y=%.2f..%.2f  size=%.2f '",
-            str->xMin, str->xMax, str->yMin, str->yMax,
-            (str->yMax - str->yMin));
-      for (i = 0; i < str->len; ++i) {
-       fputc(str->text[i] & 0xff, stdout);
+#if 0 // for debugging
+  printf("*** blocks, after yx sort ***\n");
+  for (i = 0; i < nBlocks; ++i) {
+    blk = blocks[i];
+    printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f space=%.2f..%.2f\n",
+          blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax,
+          blk->priMin, blk->priMax);
+    for (line = blk->lines; line; line = line->next) {
+      printf("  line:\n");
+      for (word0 = line->words; word0; word0 = word0->next) {
+       printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
+              word0->xMin, word0->xMax, word0->yMin, word0->yMax,
+              word0->base, word0->fontSize, word0->spaceAfter);
+       for (j = 0; j < word0->len; ++j) {
+         fputc(word0->text[j] & 0xff, stdout);
+       }
+       printf("'\n");

       }
       }

-      printf("'\n");

     }
   }
     }
   }

-  printf("\n------------------------------------------------------------\n\n");
+  printf("\n");

 #endif
 
 #endif
 

-  // do column assignment
-  for (blk1 = xyBlocks; blk1; blk1 = blk1->xyNext) {
-    col1 = 0;
-    for (blk2 = xyBlocks; blk2 != blk1; blk2 = blk2->xyNext) {
-      if (blk1->xMin >= blk2->xMax) {
-       d = (int)((blk1->xMin - blk2->xMax) /
-                 (0.4 * (blk1->yMax - blk1->yMin)));
-       if (d > 4) {
-         d = 4;
-       }
-       col2 = blk2->col[0] + blk2->convertedLen + d;
-       if (col2 > col1) {
-         col1 = col2;
+  // build the flows
+  //~ this needs to be adjusted for writing mode (vertical text)
+  //~ this also needs to account for right-to-left column ordering
+  blkArray = (TextBlock **)gmalloc(nBlocks * sizeof(TextBlock *));
+  memcpy(blkArray, blocks, nBlocks * sizeof(TextBlock *));
+  flows = lastFlow = NULL;
+  firstBlkIdx = 0;
+  nBlocksLeft = nBlocks;
+  while (nBlocksLeft > 0) {
+
+    // find the upper-left-most block
+    for (; !blkArray[firstBlkIdx]; ++firstBlkIdx) ;
+    i = firstBlkIdx;
+    blk = blkArray[i];
+    for (j = firstBlkIdx + 1; j < nBlocks; ++j) {
+      blk1 = blkArray[j];
+      if (blk1) {
+       if (blk && blk->secondaryDelta(blk1) > 0) {
+         break;

        }
        }

-      } else if (blk1->xMin > blk2->xMin) {
-       for (i = 0; i < blk2->len && blk1->xMin >= blk2->xRight[i]; ++i) ;
-       col2 = blk2->col[i];
-       if (col2 > col1) {
-         col1 = col2;
+       if (blk1->primaryCmp(blk) < 0) {
+         i = j;
+         blk = blk1;

        }
       }
     }
        }
       }
     }

-    for (j = 0; j < blk1->len; ++j) {
-      blk1->col[j] += col1;
+    blkArray[i] = NULL;
+    --nBlocksLeft;
+    blk->next = NULL;
+
+    // create a new flow, starting with the upper-left-most block
+    flow = new TextFlow(this, blk);
+    if (lastFlow) {
+      lastFlow->next = flow;
+    } else {
+      flows = flow;

     }
     }

-  }
-
-#if 0 //~ for debugging
-  for (line = lines; line; line = line->next) {
-    printf("[line]\n");
-    for (blk = line->blocks; blk; blk = blk->next) {
-      printf("[block: col=%d, len=%d]\n", blk->col[0], blk->len);
-      TextString *str;
-      for (str = blk->strings; str; str = str->next) {
-       printf("    x=%.2f..%.2f  y=%.2f..%.2f  size=%.2f '",
-              str->xMin, str->xMax, str->yMin, str->yMax,
-              (str->yMax - str->yMin));
-       for (i = 0; i < str->len; ++i) {
-         fputc(str->text[i] & 0xff, stdout);
+    lastFlow = flow;
+    fontSize = blk->lines->words->fontSize;
+
+    // push the upper-left-most block on the stack
+    blk->stackNext = NULL;
+    blkStack = blk;
+
+    // find the other blocks in this flow
+    while (blkStack) {
+
+      // find the upper-left-most block under (but within
+      // maxBlockSpacing of) the top block on the stack
+      blkSpace = maxBlockSpacing * blkStack->lines->words->fontSize;
+      blk = NULL;
+      i = -1;
+      for (j = firstBlkIdx; j < nBlocks; ++j) {
+       blk1 = blkArray[j];
+       if (blk1) {
+         if (blkStack->secondaryDelta(blk1) > blkSpace) {
+           break;
+         }
+         if (blk && blk->secondaryDelta(blk1) > 0) {
+           break;
+         }
+         if (blk1->isBelow(blkStack) &&
+             (!blk || blk1->primaryCmp(blk) < 0)) {
+           i = j;
+           blk = blk1;
+         }

        }
        }

-       if (str->spaceAfter) {
-         printf(" [space]\n");
+      }
+
+      // if a suitable block was found, add it to the flow and push it
+      // onto the stack
+      if (blk && flow->blockFits(blk, blkStack)) {
+       blkArray[i] = NULL;
+       --nBlocksLeft;
+       blk->next = NULL;
+       flow->addBlock(blk);
+       fontSize = blk->lines->words->fontSize;
+       blk->stackNext = blkStack;
+       blkStack = blk;
+
+      // otherwise (if there is no block under the top block or the
+      // block is not suitable), pop the stack
+      } else {
+       blkStack = blkStack->stackNext;
+      }
+    }
+  }
+  gfree(blkArray);
+
+#if 0 // for debugging
+  printf("*** flows ***\n");
+  for (flow = flows; flow; flow = flow->next) {
+    printf("flow: x=%.2f..%.2f y=%.2f..%.2f pri:%.2f..%.2f\n",
+          flow->xMin, flow->xMax, flow->yMin, flow->yMax,
+          flow->priMin, flow->priMax);
+    for (blk = flow->blocks; blk; blk = blk->next) {
+      printf("  block: rot=%d x=%.2f..%.2f y=%.2f..%.2f pri=%.2f..%.2f\n",
+            blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax,
+            blk->priMin, blk->priMax);
+      for (line = blk->lines; line; line = line->next) {
+       printf("    line:\n");
+       for (word0 = line->words; word0; word0 = word0->next) {
+         printf("      word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
+                word0->xMin, word0->xMax, word0->yMin, word0->yMax,
+                word0->base, word0->fontSize, word0->spaceAfter);
+         for (i = 0; i < word0->len; ++i) {
+           fputc(word0->text[i] & 0xff, stdout);
+         }
+         printf("'\n");

        }
        }

-       printf("'\n");

       }
     }
   }
       }
     }
   }

-  printf("\n------------------------------------------------------------\n\n");
+  printf("\n");

 #endif
 #endif

-}

 
 

+  if (uMap) {
+    uMap->decRefCnt();
+  }
+}

 
 GBool TextPage::findText(Unicode *s, int len,
 
 GBool TextPage::findText(Unicode *s, int len,

-                        GBool top, GBool bottom,
+                        GBool startAtTop, GBool stopAtBottom,
+                        GBool startAtLast, GBool stopAtLast,

                         double *xMin, double *yMin,
                         double *xMax, double *yMax) {
                         double *xMin, double *yMin,
                         double *xMax, double *yMax) {

-  TextLine *line;

   TextBlock *blk;
   TextBlock *blk;

+  TextLine *line;

   Unicode *p;
   Unicode u1, u2;
   Unicode *p;
   Unicode u1, u2;

-  int m, i, j;
-  double x0, x1, x;
+  int m, i, j, k;
+  double xStart, yStart, xStop, yStop;
+  double xMin0, yMin0, xMax0, yMax0;
+  double xMin1, yMin1, xMax1, yMax1;
+  GBool found;

 
 

-  // scan all blocks on page
-  for (line = lines; line; line = line->next) {
-    for (blk = line->blocks; blk; blk = blk->next) {
+  //~ needs to handle right-to-left text

 
 

-      // check: above top limit?
-      if (!top && (blk->yMax < *yMin ||
-                  (blk->yMin < *yMin && blk->xMax <= *xMin))) {
-       continue;
-      }
+  if (rawOrder) {
+    return gFalse;
+  }

 
 

-      // check: below bottom limit?
-      if (!bottom && (blk->yMin > *yMax ||
-                     (blk->yMax > *yMax && blk->xMin >= *xMax))) {
-       return gFalse;
-      }
+  xStart = yStart = xStop = yStop = 0;
+  if (startAtLast && haveLastFind) {
+    xStart = lastFindXMin;
+    yStart = lastFindYMin;
+  } else if (!startAtTop) {
+    xStart = *xMin;
+    yStart = *yMin;
+  }
+  if (stopAtLast && haveLastFind) {
+    xStop = lastFindXMin;
+    yStop = lastFindYMin;
+  } else if (!stopAtBottom) {
+    xStop = *xMax;
+    yStop = *yMax;
+  }

 
 

-      // search each position in this block
-      m = blk->len;
-      for (i = 0, p = blk->text; i <= m - len; ++i, ++p) {
+  found = gFalse;
+  xMin0 = xMax0 = yMin0 = yMax0 = 0; // make gcc happy
+  xMin1 = xMax1 = yMin1 = yMax1 = 0; // make gcc happy

 
 

-       x0 = (i == 0) ? blk->xMin : blk->xRight[i-1];
-       x1 = blk->xRight[i];
-       x = 0.5 * (x0 + x1);
+  for (i = 0; i < nBlocks; ++i) {
+    blk = blocks[i];

 
 

-       // check: above top limit?
-       if (!top && blk->yMin < *yMin) {
-         if (x < *xMin) {
-           continue;
-         }
-       }
+    // check: is the block above the top limit?
+    if (!startAtTop && blk->yMax < yStart) {
+      continue;
+    }

 
 

-       // check: below bottom limit?
-       if (!bottom && blk->yMax > *yMax) {
-         if (x > *xMax) {
-           return gFalse;
-         }
-       }
+    // check: is the block below the bottom limit?
+    if (!stopAtBottom && blk->yMin > yStop) {
+      break;
+    }
+
+    for (line = blk->lines; line; line = line->next) {
+
+      // check: is the line above the top limit?
+      if (!startAtTop && line->yMin < yStart) {
+       continue;
+      }
+
+      // check: is the line below the bottom limit?
+      if (!stopAtBottom && line->yMin > yStop) {
+       continue;
+      }
+
+      // search each position in this line
+      m = line->len;
+      for (j = 0, p = line->text; j <= m - len; ++j, ++p) {

 
        // compare the strings
 
        // compare the strings

-       for (j = 0; j < len; ++j) {
+       for (k = 0; k < len; ++k) {

 #if 1 //~ this lowercases Latin A-Z only -- this will eventually be
 #if 1 //~ this lowercases Latin A-Z only -- this will eventually be

-         //~ extended to handle other character sets
-         if (p[j] >= 0x41 && p[j] <= 0x5a) {
-           u1 = p[j] + 0x20;
+      //~ extended to handle other character sets
+         if (p[k] >= 0x41 && p[k] <= 0x5a) {
+           u1 = p[k] + 0x20;

          } else {
          } else {

-           u1 = p[j];
+           u1 = p[k];

          }
          }

-         if (s[j] >= 0x41 && s[j] <= 0x5a) {
-           u2 = s[j] + 0x20;
+         if (s[k] >= 0x41 && s[k] <= 0x5a) {
+           u2 = s[k] + 0x20;

          } else {
          } else {

-           u2 = s[j];
+           u2 = s[k];

          }
 #endif
          if (u1 != u2) {
          }
 #endif
          if (u1 != u2) {


@@ -849,17 +2701,61 @@ GBool TextPage::findText(Unicode *s, int len,
        }
 
        // found it
        }
 
        // found it

-       if (j == len) {
-         *xMin = x0;
-         *xMax = blk->xRight[i + len - 1];
-         *yMin = blk->yMin;
-         *yMax = blk->yMax;
-         return gTrue;
+       if (k == len) {
+         switch (line->rot) {
+         case 0:
+           xMin1 = line->edge[j];
+           xMax1 = line->edge[j + len];
+           yMin1 = line->yMin;
+           yMax1 = line->yMax;
+           break;
+         case 1:
+           xMin1 = line->xMin;
+           xMax1 = line->xMax;
+           yMin1 = line->edge[j];
+           yMax1 = line->edge[j + len];
+           break;
+         case 2:
+           xMin1 = line->edge[j + len];
+           xMax1 = line->edge[j];
+           yMin1 = line->yMin;
+           yMax1 = line->yMax;
+           break;
+         case 3:
+           xMin1 = line->xMin;
+           xMax1 = line->xMax;
+           yMin1 = line->edge[j + len];
+           yMax1 = line->edge[j];
+           break;
+         }
+         if ((startAtTop ||
+              yMin1 > yStart || (yMin1 == yStart && xMin1 > xStart)) &&
+             (stopAtBottom ||
+              yMin1 < yStop || (yMin1 == yStop && xMin1 < yStop))) {
+           if (!found || yMin1 < yMin0 || (yMin1 == yMin0 && xMin1 < xMin0)) {
+             xMin0 = xMin1;
+             xMax0 = xMax1;
+             yMin0 = yMin1;
+             yMax0 = yMax1;
+             found = gTrue;
+           }
+         }

        }
       }
     }
   }
 
        }
       }
     }
   }
 

+  if (found) {
+    *xMin = xMin0;
+    *xMax = xMax0;
+    *yMin = yMin0;
+    *yMax = yMax0;
+    lastFindXMin = xMin0;
+    lastFindYMin = yMin0;
+    haveLastFind = gTrue;
+    return gTrue;
+  }
+

   return gFalse;
 }
 
   return gFalse;
 }
 


@@ -868,16 +2764,24 @@ GString *TextPage::getText(double xMin, double yMin,
   GString *s;
   UnicodeMap *uMap;
   GBool isUnicode;
   GString *s;
   UnicodeMap *uMap;
   GBool isUnicode;

-  char space[8], eol[16], buf[8];
-  int spaceLen, eolLen, len;
-  TextLine *line;

   TextBlock *blk;
   TextBlock *blk;

-  double x0, x1, y;
-  int firstCol, col, i;
-  GBool multiLine;
+  TextLine *line;
+  TextLineFrag *frags;
+  int nFrags, fragsSize;
+  TextLineFrag *frag;
+  char space[8], eol[16];
+  int spaceLen, eolLen;
+  int lastRot;
+  double x, y;
+  int col, idx0, idx1, i, j;
+  GBool multiLine, oneRot;

 
   s = new GString();
 
 
   s = new GString();
 

+  if (rawOrder) {
+    return s;
+  }
+

   // get the output encoding
   if (!(uMap = globalParams->getTextEncoding())) {
     return s;
   // get the output encoding
   if (!(uMap = globalParams->getTextEncoding())) {
     return s;


@@ -898,125 +2802,282 @@ GString *TextPage::getText(double xMin, double yMin,
     break;
   }
 
     break;
   }
 

-  // find the leftmost column
-  multiLine = gFalse;
-  firstCol = -1;
-  for (line = lines; line; line = line->next) {
-    if (line->yMin > yMax) {
-      break;
-    }
-    if (line->yMax < yMin) {
-      continue;
-    }
-
-    for (blk = line->blocks; blk && blk->xMax < xMin; blk = blk->next) ;
-    if (!blk || blk->xMin > xMax) {
-      continue;
-    }
-
-    y = 0.5 * (blk->yMin + blk->yMax);
-    if (y < yMin || y > yMax) {
-      continue;
-    }
-
-    if (firstCol >= 0) {
-      multiLine = gTrue;
-    }
-
-    i = 0;
-    while (1) {
-      x0 = (i==0) ? blk->xMin : blk->xRight[i-1];
-      x1 = blk->xRight[i];
-      if (0.5 * (x0 + x1) > xMin) {
-       break;
+  //~ writing mode (horiz/vert)
+
+  // collect the line fragments that are in the rectangle
+  fragsSize = 256;
+  frags = (TextLineFrag *)gmalloc(fragsSize * sizeof(TextLineFrag));
+  nFrags = 0;
+  lastRot = -1;
+  oneRot = gTrue;
+  for (i = 0; i < nBlocks; ++i) {
+    blk = blocks[i];
+    if (xMin < blk->xMax && blk->xMin < xMax &&
+       yMin < blk->yMax && blk->yMin < yMax) {
+      for (line = blk->lines; line; line = line->next) {
+       if (xMin < line->xMax && line->xMin < xMax &&
+           yMin < line->yMax && line->yMin < yMax) {
+         idx0 = idx1 = -1;
+         switch (line->rot) {
+         case 0:
+           y = 0.5 * (line->yMin + line->yMax);
+           if (yMin < y && y < yMax) {
+             j = 0;
+             while (j < line->len) {
+               if (0.5 * (line->edge[j] + line->edge[j+1]) > xMin) {
+                 idx0 = j;
+                 break;
+               }
+               ++j;
+             }
+             j = line->len - 1;
+             while (j >= 0) {
+               if (0.5 * (line->edge[j] + line->edge[j+1]) < xMax) {
+                 idx1 = j;
+                 break;
+               }
+               --j;
+             }
+           }
+           break;
+         case 1:
+           x = 0.5 * (line->xMin + line->xMax);
+           if (xMin < x && x < xMax) {
+             j = 0;
+             while (j < line->len) {
+               if (0.5 * (line->edge[j] + line->edge[j+1]) > yMin) {
+                 idx0 = j;
+                 break;
+               }
+               ++j;
+             }
+             j = line->len - 1;
+             while (j >= 0) {
+               if (0.5 * (line->edge[j] + line->edge[j+1]) < yMax) {
+                 idx1 = j;
+                 break;
+               }
+               --j;
+             }
+           }
+           break;
+         case 2:
+           y = 0.5 * (line->yMin + line->yMax);
+           if (yMin < y && y < yMax) {
+             j = 0;
+             while (j < line->len) {
+               if (0.5 * (line->edge[j] + line->edge[j+1]) < xMax) {
+                 idx0 = j;
+                 break;
+               }
+               ++j;
+             }
+             j = line->len - 1;
+             while (j >= 0) {
+               if (0.5 * (line->edge[j] + line->edge[j+1]) > xMin) {
+                 idx1 = j;
+                 break;
+               }
+               --j;
+             }
+           }
+           break;
+         case 3:
+           x = 0.5 * (line->xMin + line->xMax);
+           if (xMin < x && x < xMax) {
+             j = 0;
+             while (j < line->len) {
+               if (0.5 * (line->edge[j] + line->edge[j+1]) < yMax) {
+                 idx0 = j;
+                 break;
+               }
+               ++j;
+             }
+             j = line->len - 1;
+             while (j >= 0) {
+               if (0.5 * (line->edge[j] + line->edge[j+1]) > yMin) {
+                 idx1 = j;
+                 break;
+               }
+               --j;
+             }
+           }
+           break;
+         }
+         if (idx0 >= 0 && idx1 >= 0) {
+           if (nFrags == fragsSize) {
+             fragsSize *= 2;
+             frags = (TextLineFrag *)
+                         grealloc(frags, fragsSize * sizeof(TextLineFrag));
+           }
+           frags[nFrags].init(line, idx0, idx1 - idx0 + 1);
+           ++nFrags;
+           if (lastRot >= 0 && line->rot != lastRot) {
+             oneRot = gFalse;
+           }
+           lastRot = line->rot;
+         }
+       }

       }
       }

-      ++i;
-    }
-    col = blk->col[i];
-
-    if (firstCol < 0 || col < firstCol) {
-      firstCol = col;

     }
   }
 
     }
   }
 

-  // extract the text
-  for (line = lines; line; line = line->next) {
-    if (line->yMin > yMax) {
-      break;
-    }
-    if (line->yMax < yMin) {
-      continue;
-    }
+  // sort the fragments and generate the string
+  if (nFrags > 0) {

 
 

-    for (blk = line->blocks; blk && blk->xMax < xMin; blk = blk->next) ;
-    if (!blk || blk->xMin > xMax) {
-      continue;
+    for (i = 0; i < nFrags; ++i) {
+      frags[i].computeCoords(oneRot);

     }
     }

+    assignColumns(frags, nFrags, oneRot);

 
 

-    y = 0.5 * (blk->yMin + blk->yMax);
-    if (y < yMin || y > yMax) {
-      continue;
+    // if all lines in the region have the same rotation, use it;
+    // otherwise, use the page's primary rotation
+    if (oneRot) {
+      qsort(frags, nFrags, sizeof(TextLineFrag),
+           &TextLineFrag::cmpYXLineRot);
+    } else {
+      qsort(frags, nFrags, sizeof(TextLineFrag),
+           &TextLineFrag::cmpYXPrimaryRot);

     }
 
     }
 

-    i = 0;
-    while (1) {
-      x0 = (i==0) ? blk->xMin : blk->xRight[i-1];
-      x1 = blk->xRight[i];
-      if (0.5 * (x0 + x1) > xMin) {
-       break;
+    col = 0;
+    multiLine = gFalse;
+    for (i = 0; i < nFrags; ++i) {
+      frag = &frags[i];
+
+      // insert a return
+      if (frag->col < col ||
+         (i > 0 && fabs(frag->base - frags[i-1].base) >
+                     maxIntraLineDelta * frags[i-1].line->words->fontSize)) {
+       s->append(eol, eolLen);
+       col = 0;
+       multiLine = gTrue;

       }
       }

-      ++i;
-    }
-
-    col = firstCol;

 
 

-    do {
-
-      // line this block up with the correct column
-      for (; col < blk->col[i]; ++col) {
+      // column alignment
+      for (; col < frag->col; ++col) {

        s->append(space, spaceLen);
       }
 
        s->append(space, spaceLen);
       }
 

-      // print the block
-      for (; i < blk->len; ++i) {
-
-       x0 = (i==0) ? blk->xMin : blk->xRight[i-1];
-       x1 = blk->xRight[i];
-       if (0.5 * (x0 + x1) > xMax) {
-         break;
-       }
-
-       len = uMap->mapUnicode(blk->text[i], buf, sizeof(buf));
-       s->append(buf, len);
-       col += isUnicode ? 1 : len;
-      }
-      if (i < blk->len) {
-       break;
-      }
-
-      // next block
-      blk = blk->next;
-      i = 0;
-
-    } while (blk && blk->xMin < xMax);
+      // get the fragment text
+      col += dumpFragment(frag->line->text + frag->start, frag->len, uMap, s);
+    }

 
     if (multiLine) {
       s->append(eol, eolLen);
     }
   }
 
 
     if (multiLine) {
       s->append(eol, eolLen);
     }
   }
 

+  gfree(frags);

   uMap->decRefCnt();
 
   return s;
 }
 
   uMap->decRefCnt();
 
   return s;
 }
 

-void TextPage::dump(void *outputStream, TextOutputFunc outputFunc) {
-  UnicodeMap *uMap;
-  char space[8], eol[16], eop[8], buf[8];
-  int spaceLen, eolLen, eopLen, len;
+GBool TextPage::findCharRange(int pos, int length,
+                             double *xMin, double *yMin,
+                             double *xMax, double *yMax) {
+  TextBlock *blk;

   TextLine *line;
   TextLine *line;

+  TextWord *word;
+  double xMin0, xMax0, yMin0, yMax0;
+  double xMin1, xMax1, yMin1, yMax1;
+  GBool first;
+  int i, j0, j1;
+
+  if (rawOrder) {
+    return gFalse;
+  }
+
+  //~ this doesn't correctly handle:
+  //~ - ranges split across multiple lines (the highlighted region
+  //~   is the bounding box of all the parts of the range)
+  //~ - cases where characters don't convert one-to-one into Unicode
+  first = gTrue;
+  xMin0 = xMax0 = yMin0 = yMax0 = 0; // make gcc happy
+  xMin1 = xMax1 = yMin1 = yMax1 = 0; // make gcc happy
+  for (i = 0; i < nBlocks; ++i) {
+    blk = blocks[i];
+    for (line = blk->lines; line; line = line->next) {
+      for (word = line->words; word; word = word->next) {
+       if (pos < word->charPos + word->charLen &&
+           word->charPos < pos + length) {
+         j0 = pos - word->charPos;
+         if (j0 < 0) {
+           j0 = 0;
+         }
+         j1 = pos + length - 1 - word->charPos;
+         if (j1 >= word->len) {
+           j1 = word->len - 1;
+         }
+         switch (line->rot) {
+         case 0:
+           xMin1 = word->edge[j0];
+           xMax1 = word->edge[j1 + 1];
+           yMin1 = word->yMin;
+           yMax1 = word->yMax;
+           break;
+         case 1:
+           xMin1 = word->xMin;
+           xMax1 = word->xMax;
+           yMin1 = word->edge[j0];
+           yMax1 = word->edge[j1 + 1];
+           break;
+         case 2:
+           xMin1 = word->edge[j1 + 1];
+           xMax1 = word->edge[j0];
+           yMin1 = word->yMin;
+           yMax1 = word->yMax;
+           break;
+         case 3:
+           xMin1 = word->xMin;
+           xMax1 = word->xMax;
+           yMin1 = word->edge[j1 + 1];
+           yMax1 = word->edge[j0];
+           break;
+         }
+         if (first || xMin1 < xMin0) {
+           xMin0 = xMin1;
+         }
+         if (first || xMax1 > xMax0) {
+           xMax0 = xMax1;
+         }
+         if (first || yMin1 < yMin0) {
+           yMin0 = yMin1;
+         }
+         if (first || yMax1 > yMax0) {
+           yMax0 = yMax1;
+         }
+         first = gFalse;
+       }
+      }
+    }
+  }
+  if (!first) {
+    *xMin = xMin0;
+    *xMax = xMax0;
+    *yMin = yMin0;
+    *yMax = yMax0;
+    return gTrue;
+  }
+  return gFalse;
+}
+
+void TextPage::dump(void *outputStream, TextOutputFunc outputFunc,
+                   GBool physLayout) {
+  UnicodeMap *uMap;
+  TextFlow *flow;

   TextBlock *blk;
   TextBlock *blk;

-  int col, d, i;
+  TextLine *line;
+  TextLineFrag *frags;
+  TextWord *word;
+  int nFrags, fragsSize;
+  TextLineFrag *frag;
+  char space[8], eol[16], eop[8];
+  int spaceLen, eolLen, eopLen;
+  GBool pageBreaks;
+  GString *s;
+  int col, i, d, n;

 
   // get the output encoding
   if (!(uMap = globalParams->getTextEncoding())) {
 
   // get the output encoding
   if (!(uMap = globalParams->getTextEncoding())) {


@@ -1037,143 +3098,318 @@ void TextPage::dump(void *outputStream, TextOutputFunc outputFunc) {
     break;
   }
   eopLen = uMap->mapUnicode(0x0c, eop, sizeof(eop));
     break;
   }
   eopLen = uMap->mapUnicode(0x0c, eop, sizeof(eop));

+  pageBreaks = globalParams->getTextPageBreaks();

 
 

-  // output
-  for (line = lines; line; line = line->next) {
-    col = 0;
-    for (blk = line->blocks; blk; blk = blk->next) {
+  //~ writing mode (horiz/vert)

 
 

-      // line this block up with the correct column
-      if (rawOrder && col == 0) {
-       col = blk->col[0];
-      } else {
-       for (; col < blk->col[0]; ++col) {
+  // output the page in raw (content stream) order
+  if (rawOrder) {
+
+    for (word = rawWords; word; word = word->next) {
+      s = new GString();
+      dumpFragment(word->text, word->len, uMap, s);
+      (*outputFunc)(outputStream, s->getCString(), s->getLength());
+      delete s;
+      if (word->next &&
+         fabs(word->next->base - word->base) <
+           maxIntraLineDelta * word->fontSize) {
+       if (word->next->xMin > word->xMax + minWordSpacing * word->fontSize) {

          (*outputFunc)(outputStream, space, spaceLen);
        }
          (*outputFunc)(outputStream, space, spaceLen);
        }

+      } else {
+       (*outputFunc)(outputStream, eol, eolLen);

       }
       }

+    }

 
 

-      // print the block
-      for (i = 0; i < blk->len; ++i) {
-       len = uMap->mapUnicode(blk->text[i], buf, sizeof(buf));
-       (*outputFunc)(outputStream, buf, len);
+  // output the page, maintaining the original physical layout
+  } else if (physLayout) {
+
+    // collect the line fragments for the page and sort them
+    fragsSize = 256;
+    frags = (TextLineFrag *)gmalloc(fragsSize * sizeof(TextLineFrag));
+    nFrags = 0;
+    for (i = 0; i < nBlocks; ++i) {
+      blk = blocks[i];
+      for (line = blk->lines; line; line = line->next) {
+       if (nFrags == fragsSize) {
+         fragsSize *= 2;
+         frags = (TextLineFrag *)grealloc(frags,
+                                          fragsSize * sizeof(TextLineFrag));
+       }
+       frags[nFrags].init(line, 0, line->len);
+       frags[nFrags].computeCoords(gTrue);
+       ++nFrags;

       }
       }

-      col += blk->convertedLen;

     }
     }

+    qsort(frags, nFrags, sizeof(TextLineFrag), &TextLineFrag::cmpYXPrimaryRot);

 
 

-    // print a return
-    (*outputFunc)(outputStream, eol, eolLen);
+    // generate output
+    col = 0;
+    for (i = 0; i < nFrags; ++i) {
+      frag = &frags[i];

 
 

-    // print extra vertical space if necessary
-    if (line->next) {
-      d = (int)((line->next->yMin - line->yMax) /
-               (line->blocks->strings->yMax - lines->blocks->strings->yMin)
-               + 0.5);
-      // various things (weird font matrices) can result in bogus
-      // values here, so do a sanity check
-      if (rawOrder && d > 2) {
-       d = 2;
-      } else if (!rawOrder && d > 5) {
-       d = 5;
+      // column alignment
+      for (; col < frag->col; ++col) {
+       (*outputFunc)(outputStream, space, spaceLen);

       }
       }

-      for (; d > 0; --d) {
-       (*outputFunc)(outputStream, eol, eolLen);
+
+      // print the line
+      s = new GString();
+      col += dumpFragment(frag->line->text + frag->start, frag->len, uMap, s);
+      (*outputFunc)(outputStream, s->getCString(), s->getLength());
+      delete s;
+
+      // print one or more returns if necessary
+      if (i == nFrags - 1 ||
+         frags[i+1].col < col ||
+         fabs(frags[i+1].base - frag->base) >
+           maxIntraLineDelta * frag->line->words->fontSize) {
+       if (i < nFrags - 1) {
+         d = (int)((frags[i+1].base - frag->base) /
+                   frag->line->words->fontSize);
+         if (d < 1) {
+           d = 1;
+         } else if (d > 5) {
+           d = 5;
+         }
+       } else {
+         d = 1;
+       }
+       for (; d > 0; --d) {
+         (*outputFunc)(outputStream, eol, eolLen);
+       }
+       col = 0;
+      }
+    }
+
+    gfree(frags);
+
+  // output the page, "undoing" the layout
+  } else {
+    for (flow = flows; flow; flow = flow->next) {
+      for (blk = flow->blocks; blk; blk = blk->next) {
+       for (line = blk->lines; line; line = line->next) {
+         n = line->len;
+         if (line->hyphenated && (line->next || blk->next)) {
+           --n;
+         }
+         s = new GString();
+         dumpFragment(line->text, n, uMap, s);
+         (*outputFunc)(outputStream, s->getCString(), s->getLength());
+         delete s;
+         if (!line->hyphenated) {
+           if (line->next) {
+             (*outputFunc)(outputStream, space, spaceLen);
+           } else if (blk->next) {
+             //~ this is a bit of a kludge - we should really do a more
+             //~ intelligent determination of paragraphs
+             if (blk->next->lines->words->fontSize ==
+                 blk->lines->words->fontSize) {
+               (*outputFunc)(outputStream, space, spaceLen);
+             } else {
+               (*outputFunc)(outputStream, eol, eolLen);
+             }
+           }
+         }
+       }

       }
       }

+      (*outputFunc)(outputStream, eol, eolLen);
+      (*outputFunc)(outputStream, eol, eolLen);

     }
   }
 
   // end of page
     }
   }
 
   // end of page

-  (*outputFunc)(outputStream, eol, eolLen);
-  (*outputFunc)(outputStream, eop, eopLen);
-  (*outputFunc)(outputStream, eol, eolLen);
+  if (pageBreaks) {
+    (*outputFunc)(outputStream, eop, eopLen);
+    (*outputFunc)(outputStream, eol, eolLen);
+  }

 
   uMap->decRefCnt();
 }
 
 
   uMap->decRefCnt();
 }
 

-// Returns true if <str1> should be inserted before <str2> in xy
-// order.
-GBool TextPage::xyBefore(TextString *str1, TextString *str2) {
-  return str1->xMin < str2->xMin ||
-        (str1->xMin == str2->xMin && str1->yMin < str2->yMin);
-}
+void TextPage::assignColumns(TextLineFrag *frags, int nFrags, GBool oneRot) {
+  TextLineFrag *frag0, *frag1;
+  int rot, col1, col2, i, j, k;
+
+  // all text in the region has the same rotation -- recompute the
+  // column numbers based only on the text in the region
+  if (oneRot) {
+    qsort(frags, nFrags, sizeof(TextLineFrag), &TextLineFrag::cmpXYLineRot);
+    rot = frags[0].line->rot;
+    for (i = 0; i < nFrags; ++i) {
+      frag0 = &frags[i];
+      col1 = 0;
+      for (j = 0; j < i; ++j) {
+       frag1 = &frags[j];
+       col2 = 0; // make gcc happy
+       switch (rot) {
+       case 0:
+         if (frag0->xMin >= frag1->xMax) {
+           col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
+                                frag1->line->col[frag1->start]) + 1;
+         } else {
+           for (k = frag1->start;
+                k < frag1->start + frag1->len &&
+                  frag0->xMin >= 0.5 * (frag1->line->edge[k] +
+                                        frag1->line->edge[k+1]);
+                ++k) ;
+           col2 = frag1->col +
+                  frag1->line->col[k] - frag1->line->col[frag1->start];
+         }
+         break;
+       case 1:
+         if (frag0->yMin >= frag1->yMax) {
+           col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
+                                frag1->line->col[frag1->start]) + 1;
+         } else {
+           for (k = frag1->start;
+                k < frag1->start + frag1->len &&
+                  frag0->yMin >= 0.5 * (frag1->line->edge[k] +
+                                        frag1->line->edge[k+1]);
+                ++k) ;
+           col2 = frag1->col +
+                  frag1->line->col[k] - frag1->line->col[frag1->start];
+         }
+         break;
+       case 2:
+         if (frag0->xMax <= frag1->xMin) {
+           col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
+                                frag1->line->col[frag1->start]) + 1;
+         } else {
+           for (k = frag1->start;
+                k < frag1->start + frag1->len &&
+                  frag0->xMax <= 0.5 * (frag1->line->edge[k] +
+                                        frag1->line->edge[k+1]);
+                ++k) ;
+           col2 = frag1->col +
+                  frag1->line->col[k] - frag1->line->col[frag1->start];
+         }
+         break;
+       case 3:
+         if (frag0->yMax <= frag1->yMin) {
+           col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
+                                frag1->line->col[frag1->start]) + 1;
+         } else {
+           for (k = frag1->start;
+                k < frag1->start + frag1->len &&
+                  frag0->yMax <= 0.5 * (frag1->line->edge[k] +
+                                        frag1->line->edge[k+1]);
+                ++k) ;
+           col2 = frag1->col +
+                  frag1->line->col[k] - frag1->line->col[frag1->start];
+         }
+         break;
+       }
+       if (col2 > col1) {
+         col1 = col2;
+       }
+      }
+      frag0->col = col1;
+    }

 
 

-// Returns true if <blk1> should be inserted before <blk2> in xy
-// order.
-GBool TextPage::xyBefore(TextBlock *blk1, TextBlock *blk2) {
-  return blk1->xMin < blk2->xMin ||
-        (blk1->xMin == blk2->xMin && blk1->yMin < blk2->yMin);
+  // the region includes text at different rotations -- use the
+  // globally assigned column numbers, offset by the minimum column
+  // number (i.e., shift everything over to column 0)
+  } else {
+    col1 = frags[0].col;
+    for (i = 1; i < nFrags; ++i) {
+      if (frags[i].col < col1) {
+       col1 = frags[i].col;
+      }
+    }
+    for (i = 0; i < nFrags; ++i) {
+      frags[i].col -= col1;
+    }
+  }

 }
 
 }
 

-// Returns true if <blk1> should be inserted before <blk2> in yx
-// order, allowing a little slack for vertically overlapping text.
-GBool TextPage::yxBefore(TextBlock *blk1, TextBlock *blk2) {
-  double h1, h2, overlap;
+int TextPage::dumpFragment(Unicode *text, int len, UnicodeMap *uMap,
+                          GString *s) {
+  char lre[8], rle[8], popdf[8], buf[8];
+  int lreLen, rleLen, popdfLen, n;
+  int nCols, i, j, k;

 
 

-  h1 = blk1->yMax - blk1->yMin;
-  h2 = blk2->yMax - blk2->yMin;
-  overlap = ((blk1->yMax < blk2->yMax ? blk1->yMax : blk2->yMax) -
-            (blk1->yMin > blk2->yMin ? blk1->yMin : blk2->yMin)) /
-            (h1 < h2 ? h1 : h2);
-  if (overlap > 0.6) {
-    return blk1->xMin < blk2->xMin;
-  }
-  return blk1->yMin < blk2->yMin;
-}
+  nCols = 0;

 
 

-double TextPage::coalesceFit(TextString *str1, TextString *str2) {
-  double h1, h2, w1, w2, r, overlap, spacing;
+  if (uMap->isUnicode()) {

 
 

-  h1 = str1->yMax - str1->yMin;
-  h2 = str2->yMax - str2->yMin;
-  w1 = str1->xMax - str1->xMin;
-  w2 = str2->xMax - str2->xMin;
-  r = h1 / h2;
-  if (r < (1.0 / 3.0) || r > 3) {
-    return 10;
-  }
-  overlap = ((str1->yMax < str2->yMax ? str1->yMax : str2->yMax) -
-            (str1->yMin > str2->yMin ? str1->yMin : str2->yMin)) /
-            (h1 < h2 ? h1 : h2);
-  if (overlap < 0.5) {
-    return 10;
-  }
-  spacing = (str2->xMin - str1->xMax) / (h1 > h2 ? h1 : h2);
-  if (spacing < -0.5) {
-    return 10;
-  }
-  // separate text that overlaps - duplicated text (so that fake
-  // boldface and shadowed text can be cleanly removed)
-  if ((str2->xMin - str1->xMax) / (w1 < w2 ? w1 : w2) < -0.7) {
-    return 10;
-  }
-  return spacing;
-}
+    lreLen = uMap->mapUnicode(0x202a, lre, sizeof(lre));
+    rleLen = uMap->mapUnicode(0x202b, rle, sizeof(rle));
+    popdfLen = uMap->mapUnicode(0x202c, popdf, sizeof(popdf));

 
 

-void TextPage::clear() {
-  TextLine *p1, *p2;
-  TextString *s1, *s2;
+    if (primaryLR) {
+
+      i = 0;
+      while (i < len) {
+       // output a left-to-right section
+       for (j = i; j < len && !unicodeTypeR(text[j]); ++j) ;
+       for (k = i; k < j; ++k) {
+         n = uMap->mapUnicode(text[k], buf, sizeof(buf));
+         s->append(buf, n);
+         ++nCols;
+       }
+       i = j;
+       // output a right-to-left section
+       for (j = i; j < len && !unicodeTypeL(text[j]); ++j) ;
+       if (j > i) {
+         s->append(rle, rleLen);
+         for (k = j - 1; k >= i; --k) {
+           n = uMap->mapUnicode(text[k], buf, sizeof(buf));
+           s->append(buf, n);
+           ++nCols;
+         }
+         s->append(popdf, popdfLen);
+         i = j;
+       }
+      }
+
+    } else {
+
+      s->append(rle, rleLen);
+      i = len - 1;
+      while (i >= 0) {
+       // output a right-to-left section
+       for (j = i; j >= 0 && !unicodeTypeL(text[j]); --j) ;
+       for (k = i; k > j; --k) {
+         n = uMap->mapUnicode(text[k], buf, sizeof(buf));
+         s->append(buf, n);
+         ++nCols;
+       }
+       i = j;
+       // output a left-to-right section
+       for (j = i; j >= 0 && !unicodeTypeR(text[j]); --j) ;
+       if (j < i) {
+         s->append(lre, lreLen);
+         for (k = j + 1; k <= i; ++k) {
+           n = uMap->mapUnicode(text[k], buf, sizeof(buf));
+           s->append(buf, n);
+           ++nCols;
+         }
+         s->append(popdf, popdfLen);
+         i = j;
+       }
+      }
+      s->append(popdf, popdfLen);

 
 

-  if (curStr) {
-    delete curStr;
-    curStr = NULL;
-  }
-  if (lines) {
-    for (p1 = lines; p1; p1 = p2) {
-      p2 = p1->next;
-      delete p1;

     }
     }

-  } else if (xyStrings) {
-    for (s1 = xyStrings; s1; s1 = s2) {
-      s2 = s1->next;
-      delete s1;
+
+  } else {
+    for (i = 0; i < len; ++i) {
+      n = uMap->mapUnicode(text[i], buf, sizeof(buf));
+      s->append(buf, n);
+      nCols += n;

     }
   }
     }
   }

-  xyStrings = NULL;
-  xyCur1 = xyCur2 = NULL;
-  lines = NULL;
-  nest = 0;
-  nTinyChars = 0;
+
+  return nCols;

 }
 
 }
 

+#if TEXTOUT_WORD_LIST
+TextWordList *TextPage::makeWordList(GBool physLayout) {
+  return new TextWordList(this, physLayout);
+}
+#endif
+

 //------------------------------------------------------------------------
 // TextOutputDev
 //------------------------------------------------------------------------
 //------------------------------------------------------------------------
 // TextOutputDev
 //------------------------------------------------------------------------


@@ -1182,8 +3418,10 @@ static void outputToFile(void *stream, char *text, int len) {
   fwrite(text, 1, len, (FILE *)stream);
 }
 
   fwrite(text, 1, len, (FILE *)stream);
 }
 

-TextOutputDev::TextOutputDev(char *fileName, GBool rawOrderA, GBool append) {
+TextOutputDev::TextOutputDev(char *fileName, GBool physLayoutA,
+                            GBool rawOrderA, GBool append) {

   text = NULL;
   text = NULL;

+  physLayout = physLayoutA;

   rawOrder = rawOrderA;
   ok = gTrue;
 
   rawOrder = rawOrderA;
   ok = gTrue;
 


@@ -1192,6 +3430,10 @@ TextOutputDev::TextOutputDev(char *fileName, GBool rawOrderA, GBool append) {
   if (fileName) {
     if (!strcmp(fileName, "-")) {
       outputStream = stdout;
   if (fileName) {
     if (!strcmp(fileName, "-")) {
       outputStream = stdout;

+#ifdef WIN32
+      // keep DOS from munging the end-of-line characters
+      setmode(fileno(stdout), O_BINARY);
+#endif

     } else if ((outputStream = fopen(fileName, append ? "ab" : "wb"))) {
       needClose = gTrue;
     } else {
     } else if ((outputStream = fopen(fileName, append ? "ab" : "wb"))) {
       needClose = gTrue;
     } else {


@@ -1205,16 +3447,17 @@ TextOutputDev::TextOutputDev(char *fileName, GBool rawOrderA, GBool append) {
   }
 
   // set up text object
   }
 
   // set up text object

-  text = new TextPage(rawOrder);
+  text = new TextPage(rawOrderA);

 }
 
 TextOutputDev::TextOutputDev(TextOutputFunc func, void *stream,
 }
 
 TextOutputDev::TextOutputDev(TextOutputFunc func, void *stream,

-                            GBool rawOrderA) {
+                            GBool physLayoutA, GBool rawOrderA) {

   outputFunc = func;
   outputStream = stream;
   needClose = gFalse;
   outputFunc = func;
   outputStream = stream;
   needClose = gFalse;

+  physLayout = physLayoutA;

   rawOrder = rawOrderA;
   rawOrder = rawOrderA;

-  text = new TextPage(rawOrder);
+  text = new TextPage(rawOrderA);

   ok = gTrue;
 }
 
   ok = gTrue;
 }
 


@@ -1231,13 +3474,14 @@ TextOutputDev::~TextOutputDev() {
 }
 
 void TextOutputDev::startPage(int pageNum, GfxState *state) {
 }
 
 void TextOutputDev::startPage(int pageNum, GfxState *state) {

-  text->clear();
+  text->startPage(state);

 }
 
 void TextOutputDev::endPage() {
 }
 
 void TextOutputDev::endPage() {

-  text->coalesce();
+  text->endPage();
+  text->coalesce(physLayout);

   if (outputStream) {
   if (outputStream) {

-    text->dump(outputStream, outputFunc);
+    text->dump(outputStream, outputFunc, physLayout);

   }
 }
 
   }
 }
 


@@ -1246,25 +3490,25 @@ void TextOutputDev::updateFont(GfxState *state) {
 }
 
 void TextOutputDev::beginString(GfxState *state, GString *s) {
 }
 
 void TextOutputDev::beginString(GfxState *state, GString *s) {

-  text->beginString(state, state->getCurX(), state->getCurY());

 }
 
 void TextOutputDev::endString(GfxState *state) {
 }
 
 void TextOutputDev::endString(GfxState *state) {

-  text->endString();

 }
 
 void TextOutputDev::drawChar(GfxState *state, double x, double y,
                             double dx, double dy,
                             double originX, double originY,
                             CharCode c, Unicode *u, int uLen) {
 }
 
 void TextOutputDev::drawChar(GfxState *state, double x, double y,
                             double dx, double dy,
                             double originX, double originY,
                             CharCode c, Unicode *u, int uLen) {

-  text->addChar(state, x, y, dx, dy, u, uLen);
+  text->addChar(state, x, y, dx, dy, c, u, uLen);

 }
 
 GBool TextOutputDev::findText(Unicode *s, int len,
 }
 
 GBool TextOutputDev::findText(Unicode *s, int len,

-                             GBool top, GBool bottom,
+                             GBool startAtTop, GBool stopAtBottom,
+                             GBool startAtLast, GBool stopAtLast,

                              double *xMin, double *yMin,
                              double *xMax, double *yMax) {
                              double *xMin, double *yMin,
                              double *xMax, double *yMax) {

-  return text->findText(s, len, top, bottom, xMin, yMin, xMax, yMax);
+  return text->findText(s, len, startAtTop, stopAtBottom,
+                       startAtLast, stopAtLast, xMin, yMin, xMax, yMax);

 }
 
 GString *TextOutputDev::getText(double xMin, double yMin,
 }
 
 GString *TextOutputDev::getText(double xMin, double yMin,


@@ -1272,3 +3516,14 @@ GString *TextOutputDev::getText(double xMin, double yMin,
   return text->getText(xMin, yMin, xMax, yMax);
 }
 
   return text->getText(xMin, yMin, xMax, yMax);
 }
 

+GBool TextOutputDev::findCharRange(int pos, int length,
+                                  double *xMin, double *yMin,
+                                  double *xMax, double *yMax) {
+  return text->findCharRange(pos, length, xMin, yMin, xMax, yMax);
+}
+
+#if TEXTOUT_WORD_LIST
+TextWordList *TextOutputDev::makeWordList() {
+  return text->makeWordList(physLayout);
+}
+#endif