Repository: pdfminer/pdfminer.six (python)

Issue:
Version pdfminer.six 20191107 incorrectly orders some text
Upgrading from version 20181108 to 20191107 pdfminer parses some words out of order.
In version 20181108 the ordering was correct, see first output below.
In version 20191107 the ordering is incorrect, see second output below.

In this pdf: http://unec.edu.az/application/uploads/2014/12/pdf-sample.pdf

The fourth bullet point ends with the word "anyone".  When parsing, "anyone" now ends up at the end of the third bullet point instead (directly following "incompatibilities").

Sample parsing logic:
```
import os
import sys
from io import StringIO
from pprint import pprint

from pdfminer.pdfparser import PDFParser
from pdfminer.pdfdocument import PDFDocument
from pdfminer.pdfpage import PDFPage, PDFTextExtractionNotAllowed
from pdfminer.pdfinterp import PDFResourceManager, PDFPageInterpreter
from pdfminer.layout import LAParams
from pdfminer.converter import TextConverter

def get_text(path):
    fd = open(path, 'rb')

    parser = PDFParser(fd)
    document = PDFDocument(parser)

    # Try to parse the document
    if not document.is_extractable:
        raise PDFTextExtractionNotAllowed

    rsrcmgr = PDFResourceManager()

    text = StringIO()

    device = TextConverter(rsrcmgr, text, codec='utf-8', laparams=LAParams())

    interpreter = PDFPageInterpreter(rsrcmgr, device)

    for page in PDFPage.create_pages(document):
        interpreter.process_page(page)

    return text.getvalue()

txt = get_text(os.path.abspath(sys.argv[1]))
pprint(txt)
```
### 20181108  output
```
$ python testit.py pdf-sample.pdf
('Adobe Acrobat PDF Files\n'
 '\n'
 'Adobe® Portable Document Format (PDF) is a universal file format that '
 'preserves all\n'
 'of the fonts, formatting, colours and graphics of any source document, '
 'regardless of\n'
 'the application and platform used to create it.\n'
 '\n'
 'Adobe PDF is an ideal format for electronic document distribution as it '
 'overcomes the\n'
 'problems commonly encountered with electronic file sharing.\n'
 '\n'
 '•  Anyone, anywhere can open a PDF file. All you need is the free Adobe '
 'Acrobat\n'
 "Reader. Recipients of other file formats sometimes can't open files because "
 'they\n'
 "don't have the applications used to create the documents.\n"
 '\n'
 '•  PDF files always print correctly on any printing device.\n'
 '\n'
 '•  PDF  files  always  display  exactly  as  created,  regardless  of  '
 'fonts,  software,  and\n'
 'operating systems. Fonts, and graphics are not lost due to platform, '
 'software, and\n'
 'version incompatibilities.\n'
 '\n'
 '•  The  free  Acrobat  Reader  is  easy  to  download  and  can  be  freely  '
 'distributed  by\n'
 '\n'
 'anyone.\n'
 '\n'
 '•  Compact  PDF  files  are  smaller  than  their  source  files  and  '
 'download  a\n'
 '\n'
 'page at a time for fast display on the Web.\n'
 '\n'
 '\x0c')
```

### 20191107 output
```
$ python testit.py pdf-sample.pdf
('Adobe Acrobat PDF Files\n'
 '\n'
 'Adobe® Portable Document Format (PDF) is a universal file format that '
 'preserves all\n'
 'of the fonts, formatting, colours and graphics of any source document, '
 'regardless of\n'
 'the application and platform used to create it.\n'
 '\n'
 'Adobe PDF is an ideal format for electronic document distribution as it '
 'overcomes the\n'
 'problems commonly encountered with electronic file sharing.\n'
 '\n'
 '•  Anyone, anywhere can open a PDF file. All you need is the free Adobe '
 'Acrobat\n'
 "Reader. Recipients of other file formats sometimes can't open files because "
 'they\n'
 "don't have the applications used to create the documents.\n"
 '\n'
 '•  PDF files always print correctly on any printing device.\n'
 '\n'
 '•  PDF  files  always  display  exactly  as  created,  regardless  of  '
 'fonts,  software,  and\n'
 'operating systems. Fonts, and graphics are not lost due to platform, '
 'software, and\n'
 'version incompatibilities.\n'
 '\n'
 'anyone.\n'
 '\n'
 '•  The  free  Acrobat  Reader  is  easy  to  download  and  can  be  freely  '
 'distributed  by\n'
 '\n'
 '•  Compact  PDF  files  are  smaller  than  their  source  files  and  '
 'download  a\n'
 '\n'
 'page at a time for fast display on the Web.\n'
 '\n'
 '\x0c')
```

Pull request:
Fix ordering of grouping textboxes. The first grouping of textboxes should be skipped if there are intermediate textboxes.
**Description**

#315 introduces a bug by replacing `0` by `True` and `1` by `False` in the ordening of textbox distances. Consequently, all the text boxes that are checked once (for intermediate textboxes) have priority over those that are never checked. Therefore it merges the same text box over and over again. 

@mikkkee, can you have a look at this?

Fixes #334 

**How Has This Been Tested?**

- [x] I've use the pdf in #334 to check the output
- [x] I've added a debug log statement to see the order in which text boxes are grouped. 
- [x] The doctests in the documentation improved
- [x] Check speedup improvement from #315

**Checklist**

- [x] I have added tests that prove my fix is effective or that my feature works
- [x] I have updated the [README.md](../README.md) and other documentation, or I am sure that this is not necessary
- [x] I have added a consice human-readable description of the change to [CHANGELOG.md](../CHANGELOG.md)
- [x] I have added docstrings to newly created methods and classes
- [x] I have optimized the code at least one time after creating the initial version


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 91bebe0..56997a4 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -5,7 +5,8 @@ The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/).
 
 ## [Unreleased]
 
-Nothing yet
+### Fixed
+- Wrong order of text box grouping introduced by PR #315 ([#335](https://github.com/pdfminer/pdfminer.six/pull/335))
 
 ## [20191107] - 2019-11-07
 
diff --git a/docs/source/tutorials/highlevel.rst b/docs/source/tutorials/highlevel.rst
index 15424b9..d55328d 100644
--- a/docs/source/tutorials/highlevel.rst
+++ b/docs/source/tutorials/highlevel.rst
@@ -17,23 +17,23 @@ The most simple way to extract text from a PDF is to use
 
     >>> text = extract_text('samples/simple1.pdf')
     >>> print(repr(text))
-    'Hello \n\nWorld\n\nWorld\n\nHello \n\nH e l l o  \n\nH e l l o  \n\nW o r l d\n\nW o r l d\n\n\x0c'
+    'Hello \n\nWorld\n\nHello \n\nWorld\n\nH e l l o  \n\nW o r l d\n\nH e l l o  \n\nW o r l d\n\n\x0c'
     >>> print(text)
     ... # doctest: +NORMALIZE_WHITESPACE
     Hello
     <BLANKLINE>
     World
     <BLANKLINE>
-    World
-    <BLANKLINE>
     Hello
     <BLANKLINE>
-    H e l l o
+    World
     <BLANKLINE>
     H e l l o
     <BLANKLINE>
     W o r l d
     <BLANKLINE>
+    H e l l o
+    <BLANKLINE>
     W o r l d
     <BLANKLINE>
 
diff --git a/pdfminer/layout.py b/pdfminer/layout.py
index 8b8e397..bd2b2a7 100644
--- a/pdfminer/layout.py
+++ b/pdfminer/layout.py
@@ -1,6 +1,7 @@
 import heapq
+import logging
 
-from .utils import INF
+from .utils import INF, shorten_str
 from .utils import Plane
 from .utils import apply_matrix_pt
 from .utils import bbox2str
@@ -9,6 +10,8 @@ from .utils import get_bound
 from .utils import matrix2str
 from .utils import uniq
 
+logger = logging.getLogger(__name__)
+
 
 class IndexAssigner(object):
 
@@ -45,7 +48,7 @@ class LAParams(object):
         considered to be part of the same paragraph. The margin is
         specified relative to the height of a line.
     :param boxes_flow: Specifies how much a horizontal and vertical position
-        of a text matters when determining the order of lines. The value
+        of a text matters when determining the order of text boxes. The value
         should be within the range of -1.0 (only horizontal position
         matters) to +1.0 (only vertical position matters).
     :param detect_vertical: If vertical text should be considered during
@@ -505,7 +508,7 @@ class LTTextGroupTBRL(LTTextGroup):
         # reorder the objects from top-right to bottom-left.
         self._objs.sort(key=lambda obj:
                            -(1+laparams.boxes_flow)*(obj.x0+obj.x1)
-                           - (1-laparams.boxes_flow)*(obj.y1))
+                           -(1-laparams.boxes_flow)*(obj.y1))
         return
 
 
@@ -562,6 +565,7 @@ class LTLayoutContainer(LTContainer):
 
                 if ((halign and isinstance(line, LTTextLineHorizontal)) or
                     (valign and isinstance(line, LTTextLineVertical))):
+
                     line.add(obj1)
                 elif line is not None:
                     yield line
@@ -667,18 +671,19 @@ class LTLayoutContainer(LTContainer):
             obj1 = boxes[i]
             for j in range(i+1, len(boxes)):
                 obj2 = boxes[j]
-                dists.append((True, dist(obj1, obj2), id(obj1), id(obj2), obj1, obj2))
+                dists.append((False, dist(obj1, obj2), id(obj1), id(obj2),
+                              obj1, obj2))
         heapq.heapify(dists)
 
         plane = Plane(self.bbox)
         plane.extend(boxes)
         done = set()
         while len(dists) > 0:
-            (is_first, d, id1, id2, obj1, obj2) = heapq.heappop(dists)
+            (skip_isany, d, id1, id2, obj1, obj2) = heapq.heappop(dists)
             # Skip objects that are already merged
             if (id1 not in done) and (id2 not in done):
-                if is_first and isany(obj1, obj2):
-                    heapq.heappush(dists, (False, d, id1, id2, obj1, obj2))
+                if skip_isany and isany(obj1, obj2):
+                    heapq.heappush(dists, (True, d, id1, id2, obj1, obj2))
                     continue
                 if isinstance(obj1, (LTTextBoxVertical, LTTextGroupTBRL)) or \
                         isinstance(obj2, (LTTextBoxVertical, LTTextGroupTBRL)):
diff --git a/pdfminer/utils.py b/pdfminer/utils.py
index 4fb5825..3743b3a 100644
--- a/pdfminer/utils.py
+++ b/pdfminer/utils.py
@@ -32,6 +32,16 @@ def make_compat_str(in_str):
     return in_str
 
 
+def shorten_str(s, size):
+    if size < 7:
+        return s[:size]
+    if len(s) > size:
+        length = (size - 5) // 2
+        return '{} ... {}'.format(s[:length], s[-length:])
+    else:
+        return s
+
+
 def compatible_encode_method(bytesorstring, encoding='utf-8', erraction='ignore'):
     """When Py2 str.encode is called, it often means bytes.encode in Py3. This does either."""
     if six.PY2:


Test patch:
diff --git a/tests/test_highlevel_extracttext.py b/tests/test_highlevel_extracttext.py
index 7062cd8..425c944 100644
--- a/tests/test_highlevel_extracttext.py
+++ b/tests/test_highlevel_extracttext.py
@@ -11,7 +11,7 @@ def run(sample_path):
 
 
 test_strings = {
-    "simple1.pdf": "Hello \n\nWorld\n\nWorld\n\nHello \n\nH e l l o  \n\nH e l l o  \n\nW o r l d\n\nW o r l d\n\n\f",
+    "simple1.pdf": "Hello \n\nWorld\n\nHello \n\nWorld\n\nH e l l o  \n\nW o r l d\n\nH e l l o  \n\nW o r l d\n\n\f",
     "simple2.pdf": "\f",
     "simple3.pdf": "HelloHello\n\nWorld\n\nWorld\n\n\f",
 }
diff --git a/tests/test_utils.py b/tests/test_utils.py
index 5787ac2..edfdaa9 100644
--- a/tests/test_utils.py
+++ b/tests/test_utils.py
@@ -1,7 +1,7 @@
 from nose.tools import assert_equal
 
 from pdfminer.layout import LTComponent
-from pdfminer.utils import Plane
+from pdfminer.utils import Plane, shorten_str
 
 
 class TestPlane(object):
@@ -38,3 +38,16 @@ class TestPlane(object):
         obj = LTComponent((0, 0, object_size, object_size))
         plane.add(obj)
         return plane, obj
+
+
+class TestFunctions(object):
+    def test_shorten_str(self):
+        s = shorten_str('Hello there World', 15)
+        assert_equal(s, 'Hello ... World')
+
+    def test_shorten_short_str_is_same(self):
+        s = 'Hello World'
+        assert_equal(s, shorten_str(s, 50))
+
+    def test_shorten_to_really_short(self):
+        assert_equal('Hello', shorten_str('Hello World', 5))
\ No newline at end of file