Method and apparatus for paginating electronic documents

• US 9,727,293 B1
• Filed: 12/21/2010
• Issued: 08/08/2017
• Est. Priority Date: 12/21/2010
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: White, Christopher A., Zuromski, Joseph A., Wang, Fei
• Primary Examiner(s): Paula, Cesar
• Assistant Examiner(s): Huang, Jian
• Application Number:
  US12/975,282
• Time in Patent Office: 2,422 Days
• Field of Search: 707704, 707234, 709218, 709203, 715201, 715251, 715247, 715256, 719103, 2354621
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents
• CPC Class Codes: G06F 3/14 Digital output to display device ; Cooperation and interconnection of the display device with other functional units
• CPC Class Codes: G06F 7/10 Selecting, i.e. obtaining data of one kind from those record carriers which are identifiable by data of a second kind from a mass of ordered or randomly- distributed record carriers
• CPC Class Codes: G09G 2340/14 Solving problems related to the presentation of information to be displayed

Abstract

A method and apparatus for paginating documents such as html documents is disclosed. A document viewing engine generates a preliminary layout for the, the preliminary layout having a layout width that is equivalent to a viewport width of a viewport on which the document will be displayed. The document viewing engine computes a final layout for the document based on determining a plurality of horizontal pixel lines where page breaks can be placed without cutting off any element in the document and assigns page breaks to one or more of the plurality of horizontal pixel lines based on a height of the viewport. The document viewing engine identifies, for a current page, one or more visual elements that will not be fully within the viewport if painted. The document viewing engine paints the current page without painting the identified one or more visual elements. After changing from the current page to a new page, the document viewing engine paints the contents of the new page without re-computing the final layout of the document.

Claims

1. A method of paginating an electronic document comprising:

receiving, by a processor of a user electronic device comprising a viewport for viewing the electronic document, the electronic document in an unpaginated format;

generating, by the processor, a preliminary layout for the electronic document in the unpaginated format, the preliminary layout having a layout width that is equivalent to a viewport width of the viewport of the user electronic device, the viewport configured to display the electronic document, wherein generating the preliminary layout comprises;

generating a Document Object Model (DOM) tree comprising first byte offset information for a first visual element of the electronic document in the unpaginated format and second byte offset information for a second visual element of the electronic document in the unpaginated format;

determining the second byte offset information for the second visual element indicates an element width that is greater than a width threshold;

reducing the element width of the second visual element to less than or equal to the width threshold; and

generating a second DOM tree with updated second byte offset information in response to the reducing;

computing, by the processor, a final layout for the electronic document in a paginated format based at least in part on;

reviewing the preliminary layout to identify a plurality of horizontal areas to assign one or more page breaks without a visual element spanning multiple pages of the electronic document; and

assigning a page break to one or more of the plurality of horizontal areas;

rendering, by the processor, a current page in the viewport in accordance with the final layout, wherein the current page excludes the first visual element comprising at least a portion excluded by the page break from display within the viewport; and

after changing from the current page to a new page, rendering, by the processor, the new page without re-computing the final layout of the electronic document, wherein the new page includes the first visual element.

2. The method of claim 1, further comprising:

scanning the DOM tree to identify the second visual element having the element width that is greater than the width threshold.

3. The method of claim 1, further comprising:

adding byte offsets for each of a plurality of tags to nodes of the DOM tree.

4. The method of claim 1, further comprising:

generating a render tree from the second DOM tree, wherein the render tree is used to generate the preliminary layout.

5. The method of claim 1, further comprising:

recording third byte offset information for a tag associated with a third visual element in the electronic document that is located at an upper left corner of the new page before closing the electronic document; and

upon reopening the electronic document, using the third byte offset information to open the electronic document to the new page.

6. The method of claim 1, further comprising:

receiving a command to change a property of the electronic document;

recording third byte offset information for a tag associated with a third visual element in the electronic document that is located at an upper left corner of the new page;

and

rendering an updated page that includes the third visual element in an upper left corner of the updated page.

7. The method of claim 1, wherein the preliminary layout and the final layout are platform independent.

8. The method of claim 1, wherein the preliminary layout and final layout include placement of floating elements.

9. The method of claim 1, wherein the electronic document is a hypertext markup language (html) document.

10. A user device comprising:

a memory to store instructions; and

a processor of a user electronic device comprising a viewport for viewing the electronic document, the processor to execute the instructions to cause the processor to;

receive an electronic document in an unpaginated format;

generate a Document Object Model (DOM) tree comprising first byte offset information for a first visual element of the electronic document in the unpaginated format and second byte offset information for a second visual element of the electronic document in the unpaginated format;

determine the second byte offset information for the second visual element indicates an element width that is greater than a width threshold;

reduce the element width of the second visual element to less than or equal to the width threshold; and

generate a second DOM tree with updated second byte offset information in response to the reducing;

compute a preliminary layout for the electronic document in the unpaginated format using the DOM tree;

identify a plurality of horizontal areas to assign one or more page breaks without a visual element spanning multiple pages of the preliminary layout of the electronic document;

compute a final layout comprising a first page break assigned at a first horizontal area of the plurality of horizontal areas; and

render a current page in the viewport in accordance with the final layout, wherein the current page excludes the first visual element comprising at least a portion excluded by the first page break from display within the viewport.

11. The user device of claim 10, the processor to:

scan the DOM tree to identify the second visual element having the element width that is greater than the width threshold.

12. The user device of claim 10, the processor to:

add byte offset information for each of a plurality of tags to nodes of the DOM tree.

13. The user device of claim 10, the processor to:

generate a render tree from the second DOM tree, wherein the render tree is used to generate the preliminary layout.

14. The user device of claim 10, the processor to:

record third byte offset information for a tag associated with a third visual element in the electronic document that is located at an upper left corner of a new page before closing the electronic document; and

upon reopening the electronic document, use the third byte offset information to open the electronic document to the new page.

15. The user device of claim 10, further comprising the instructions to cause the processor to:

receive a command to change a property of the electronic document;

record third byte offset information for a tag associated with a third visual element in the electronic document that is located at the upper left corner of a new page;

and

render an updated page that includes the third visual element in an upper left corner of the updated page.

16. The user device of claim 10, wherein the preliminary layout and the final layout are platform independent.

17. A non-transitory computer readable storage medium including instructions that, when executed by a processor, cause the processor to perform a method of paginating an electronic document comprising:

receiving, by the processor of a user electronic device comprising a viewport for viewing the electronic document, the electronic document in an unpaginated format;

generating, by the processor, a preliminary layout for the electronic document in the unpaginated format, including assigning a layout width, determining sizes and positions of visual elements included in the electronic document, wherein generating the preliminary layout comprises;

generating a Document Object Model (DOM) tree comprising first byte offset information for a first visual element of the electronic document in the unpaginated format and second byte offset information for a second visual element of the electronic document in the unpaginated format;

determining the second byte offset information for the second visual element indicates an element width that is greater than a width threshold;

reducing the element width of the second visual element to less than or equal to the width threshold; and

generating a second DOM tree with updated second byte offset information in response to the reducing;

computing, by the processor, a final layout for the electronic document in a paginated format based at least in part on;

reviewing the preliminary layout to identify a plurality of horizontal areas to assign one or more page breaks without a visual element spanning multiple pages of the electronic document; and

assigning a page break to one or more of the plurality of horizontal areas;

rendering, by the processor, a current page in the viewport in accordance with the final layout, wherein the current page excludes the first visual element comprising at least a portion excluded by the page break from display within the viewport; and

after changing from the current page to a new page, rendering, by the processor, the new page without re-computing the final layout of the electronic document, wherein the new page includes the first visual element.

18. The non-transitory computer readable storage medium of claim 17, the method further comprising:

scanning the DOM tree to identify the second visual element having the element width that is greater than the width threshold.

19. The non-transitory computer readable storage medium of claim 17, the method further comprising:

adding byte offsets for each of a plurality of tags to nodes of the DOM tree.

20. The non-transitory computer readable storage medium of claim 17, the method further comprising:

recording third byte offset information for a tag associated with a third visual element in the electronic document that is located at an upper left corner of the new page before closing the electronic document; and

upon reopening the electronic document, using the third byte offset information to open the electronic document to the new page.

21. The non-transitory computer readable storage medium of claim 17, the method further comprising:

receiving a command to change a property of the electronic document;

recording third byte offset information for a tag associated with a third visual element in the electronic document that is located at an upper left corner of the new page;

and

rendering an updated page that includes the third visual element in an upper left corner of the updated page.

22. The non-transitory computer readable storage medium of claim 19, wherein the layout is platform independent.