Attachment 31141 Details for Bug 3188 – remove existing reading-order sort

[patch] remove existing reading-order sort

0002-Separate-flow-construction-from-reading-order.patch (text/plain), 4.85 KB, created by Brian Ewins on 2009-11-12 13:46:13 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Brian Ewins

Created: 2009-11-12 13:46:13 UTC

Size: 4.85 KB

patch

obsolete

>From 24841d2dc29635ff70943a964f20ccc2cb894984 Mon Sep 17 00:00:00 2001
>From: Brian Ewins <brian.ewins@gmail.com>
>Date: Mon, 9 Nov 2009 06:24:51 +0000
>Subject: [PATCH] Separate flow construction from reading order
>
>If the blocks were already in reading order, then
>constructing flows is simplified, since blocks
>cannot be picked out-of-order. Make this change
>first in preparation for adding a reading-order
>sort.
>
>Signed-off-by: Brian Ewins <brian.ewins@gmail.com>
>---
> poppler/TextOutputDev.cc |   98 ++++++++-------------------------------------
> 1 files changed, 18 insertions(+), 80 deletions(-)
>
>diff --git a/poppler/TextOutputDev.cc b/poppler/TextOutputDev.cc
>index a11260b..aeb4f37 100644
>--- a/poppler/TextOutputDev.cc
>+++ b/poppler/TextOutputDev.cc
>@@ -2183,8 +2183,7 @@ void TextPage::coalesce(GBool physLayout, GBool doHTML) {
>   TextPool *pool;
>   TextWord *word0, *word1, *word2;
>   TextLine *line;
>-  TextBlock *blkList, *blkStack, *blk, *lastBlk, *blk0, *blk1;
>-  TextBlock **blkArray;
>+  TextBlock *blkList, *blk, *lastBlk, *blk0, *blk1;
>   TextFlow *flow, *lastFlow;
>   TextUnderline *underline;
>   TextLink *link;
>@@ -2194,7 +2193,6 @@ void TextPage::coalesce(GBool physLayout, GBool doHTML) {
>   GBool found;
>   int count[4];
>   int lrCount;
>-  int firstBlkIdx, nBlocksLeft;
>   int col1, col2;
>   int i, j, n;
> 
>@@ -2841,8 +2839,8 @@ void TextPage::coalesce(GBool physLayout, GBool doHTML) {
> 
>   //----- reading order sort
> 
>-  // sort blocks into yx order (in preparation for reading order sort)
>-  qsort(blocks, nBlocks, sizeof(TextBlock *), &TextBlock::cmpYXPrimaryRot);
>+  // sort blocks into xy order (in preparation for reading order sort)
>+  qsort(blocks, nBlocks, sizeof(TextBlock *), &TextBlock::cmpXYPrimaryRot);
> 
>   // compute space on left and right sides of each block
>   for (i = 0; i < nBlocks; ++i) {
>@@ -2881,39 +2879,28 @@ void TextPage::coalesce(GBool physLayout, GBool doHTML) {
>   // 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 **)gmallocn(nBlocks, sizeof(TextBlock *));
>-  memcpy(blkArray, blocks, nBlocks * sizeof(TextBlock *));
>+  flow = NULL;
>   while (flows) {
>     flow = flows;
>     flows = flows->next;
>     delete flow;
>   }
>   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;
>-	}
>-	if (blk1->primaryCmp(blk) < 0) {
>-	  i = j;
>-	  blk = blk1;
>-	}
>-      }
>-    }
>-    blkArray[i] = NULL;
>-    --nBlocksLeft;
>+  // assume blocks are already in reading order,
>+  // and construct flows accordingly.
>+  for (i = 0; i < nBlocks; i++) {
>+    blk = blocks[i];
>     blk->next = NULL;
>-
>-    // create a new flow, starting with the upper-left-most block
>+    if (flow) {
>+      blk1 = blocks[i - 1];
>+      blkSpace = maxBlockSpacing * blk1->lines->words->fontSize;
>+      if (blk1->secondaryDelta(blk) <= blkSpace &&
>+	  blk->isBelow(blk1) &&
>+	  flow->blockFits(blk, blk1)) {
>+	flow->addBlock(blk);
>+	continue;
>+      } 
>+    } 
>     flow = new TextFlow(this, blk);
>     if (lastFlow) {
>       lastFlow->next = flow;
>@@ -2921,56 +2908,7 @@ void TextPage::coalesce(GBool physLayout, GBool doHTML) {
>       flows = flow;
>     }
>     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 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");
>-- 
>1.5.6.6
>

Actions: View | Splinter Review

Attachments on bug 3188: 23584 | 23585 | 23691 | 24739 | 24748 | 24749 | 24922 | 24928 | 24938 | 24983 | 25026 | 30821 | 30822 | 31140 | 31141 | 31143 | 31162 | 31217 | 31218 | 31219 | 31220 | 31404 | 31405 | 31406 | 31407 | 31408 | 33251 | 35494 | 35559 | 35560 | 40056 | 40061 | 40124 | 40308 | 97356 | 121848

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.