Traversing a hierarchical layout template

• US 7,415,452 B1
• Filed: 06/21/2002
• Issued: 08/19/2008
• Est. Priority Date: 06/21/2002
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Ayers, Robert M.
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Black; Linh
• Application Number:
  US10/177,576
• Time in Patent Office: 2,251 Days
• Field of Search: 707 1-1041, 707/200, 709/204, 345/854
• US Class Current: 1/1
• CPC Class Codes: G06F 40/106 Display of layout of documents; Previewing
• CPC Class Codes: G06F 40/117 Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/14 Tree-structured documents parsing G06F40/205; validation G06F40/226
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

Methods and apparatus implementing systems and techniques for traversing a hierarchical layout template to accelerate a constraint-driven backtracking search for a solution of the layout template. In general, in one implementation, the techniques include identifying a shared content element constraint that defines a content requirement common to all layout structures possible in a choice substructure in a hierarchical layout template, and associating the shared content element constraint with a root node of the choice substructure in the hierarchical layout template. In another aspect, the techniques include receiving content elements to be presented according to a hierarchical layout template that includes a choice substructure including a root node having a shared content element constraint that defines a content requirement common to all layout structures possible in the choice substructure, and traversing the hierarchical layout template to generate a layout structure that accommodates the content elements, said traversing including traversing the hierarchical layout template based at least in part on the shared content element constraint associated with the root node.

Claims

1. A method comprising:

identifying a shared content element constraint that defines a content requirement common to all layout structures possible in a choice substructure in a hierarchical layout template; and

associating the shared content element constraint with a root node of the choice substructure in the hierarchical layout template;

wherein the content requirement common to all layout structures possible in the choice substructure corresponds to input content required by a node of the hierarchical layout template during generation of a page layout structure to format content to produce a document that combines layout and content;

the method further comprising;

receiving content elements to be presented according to the layout template; and

traversing the layout template to generate a layout structure that accommodates the content elements, said traversing including traversing the hierarchical layout template based at least in part on the shared content element constraint associated with the root node;

wherein said traversing the hierarchical layout template comprises generating a preferred layout based on penalty values associated with selected layout substructures.

2. The method of claim 1, wherein said identifying the shared content element constraint comprises:

in a programmable machine, identifying one or more content constraints in one or more leaf nodes of the choice substructure in the hierarchical layout template; and

in a programmable machine, discovering commonality in the one or more content constraints in the choice substructure.

3. The method of claim 2, wherein said identifying the one or more content constraints comprises identifying a single content constraint in a single leaf node.

4. The method of claim 1, further comprising creating the hierarchical layout template.

5. The method of claim 4, wherein said creating the hierarchical layout template comprises creating a data structure.

6. The method of claim 4, wherein said creating the hierarchical layout template comprises creating structured text-based data.

7. The method of claim 1, wherein said traversing the hierarchical layout template comprises comparing at least one of the content elements with the shared content element constraint associated with the root node to avoid traversing at least a portion of the choice substructure.

8. The method of claim 1, wherein said traversing the hierarchical layout template comprises:

selecting among template choices in the hierarchical layout template; and

generating the layout structure based on the selected template choices.

9. A software product tangibly stored on a machine-readable medium, the software product comprising instructions operable to cause one or more programmable processors to perform operations comprising:

identifying a shared content element constraint that defines a content requirement common to all layout structures possible in a choice substructure in a hierarchical layout template; and

associating the shared content element constraint with a root node of the choice substructure in the hierarchical layout template;

wherein the content requirement common to all layout structures possible in the choice substructure corresponds to input content required by a node of the hierarchical layout template during generation of a page layout structure to format content to produce a document that combines layout and content;

wherein the operations further comprise;

receiving content elements to be presented according to the hierarchical layout template; and

traversing the hierarchical layout template to generate a layout structure that accommodates the content elements, said traversing including traversing the hierarchical layout template based at least in part on the shared content element constraint associated with the root node;

wherein said traversing the hierarchical layout template comprises generating a preferred layout based on penalty values associated with selected layout substructures.

10. The software product of claim 9, wherein said identifying the shared content element constraint comprises:

identifying one or more content constraints in one or more leaf nodes of the choice substructure in the hierarchical layout template; and

discovering commonality in the one or more content constraints in the choice substructure.

11. The software product of claim 9, wherein the operations further comprise creating the hierarchical layout template.

12. The software product of claim 11, wherein said creating the hierarchical layout template comprises creating structured text-based data.

13. The software product of claim 9, wherein said traversing the hierarchical layout template comprises comparing at least one of the content elements with the shared content element constraint associated with the root node to avoid traversing at least a portion of the choice substructure.

14. A method comprising:

receiving content elements to be presented according to a hierarchical layout template that includes a choice substructure including a root node having shared content element constraint that defines a content requirement common to all layout structures possible in the choice substructure; and

traversing the hierarchical layout template to generate a layout structure that accommodates the content elements, said traversing including traversing the hierarchical layout template based at least in part on the shared content element constraint associated with the root node;

wherein the content requirement common to all layout structures possible in the choice substructure corresponds to input content required by a node of the hierarchical layout template during generation of a page layout structure to format content to produce a document that combines layout and content;

wherein said traversing the hierarchical layout template comprises comparing at least one of the content elements with the shared content element constraint associated with the root node to avoid traversing at least a portion of the choice substructure; and

wherein said traversing the hierarchical layout template comprises determining a preferred layout based on penalty values associated with selected layout substructures.

15. The method of claim 14, wherein said traversing the hierarchical layout template comprises:

selecting among template choices in the hierarchical layout template; and

generating the layout structure based on the selected template choices.

16. The method of claim 14, further comprising obtaining the hierarchical layout template.

17. The method of claim 16, wherein said obtaining the hierarchical layout template comprises loading an Interscript layout template.

18. The method of claim 16, wherein said obtaining the hierarchical layout template comprises:

loading structured text-based data; and

generating the hierarchical layout template from the structured text-based data.

19. A software product tangibly stored on a machine-readable medium, the software product comprising instructions operable to cause one or more programmable processors to perform operations comprising:

receiving content elements to be presented according to a hierarchical layout template that includes a choice substructure including a root node having a shared content element constraint that defines a content requirement common to all layout structures possible in the choice substructure; and

traversing the hierarchical layout template to generate a layout structure that accommodates the content elements, said traversing including traversing the hierarchical layout template based at least in part on the shared content element constraint associated with the root node;

wherein the content requirement common to all layout structures possible in the choice substructure corresponds to input content required by a node of the hierarchical layout template during generation of a page layout structure to format content to produce a document that combines layout and content;

wherein said traversing the hierarchical layout template comprises comparing at least one of the content elements with the shared content element constraint associated with the root node to avoid traversing at least a portion of the choice substructure; and

wherein said traversing the hierarchical layout template comprises determining a preferred layout based on penalty values associated with selected layout substructures.

20. The software product of claim 19, wherein said traversing the hierarchical layout template further comprises:

selecting among template choices in the hierarchical layout template based on said comparing; and

generating the layout structure based on the selected template choices.

21. The software product of claim 19, wherein the operations further comprise obtaining the hierarchical layout template.

22. The software product of claim 21, wherein said obtaining the hierarchical layout template comprises:

loading structured text-based data; and

generating the hierarchical layout template from the structured text-based data.

23. A hierarchical layout template storable on a machine-readable medium, the hierarchical layout template comprising:

template leaf nodes each having one or more content element constrains each defining for an associated leaf node a content requirement for a layout structure using the associated leaf node; and

a choice substructure including a root node and at least one of the template leaf nodes as a descendent of the root node, the root node having an associated shared content element constraint that defines a content requirement common to all layout structures possible in the choice substructure;

wherein the content requirement common to all layout structures possible in the choice substructure corresponds to input content required by a node of the hierarchical layout template during generation of a page layout structure to format content to produce a document that combines layout and content;

wherein the hierarchical layout template is arranged to support traversing the hierarchical layout template comprising;

comparing at least one of content element with the shared content element constraint associated with the root node to avoid traversing at least a portion of the choice substructure, and determining a preferred layout based on penalty values associated with selected layout substructures.

24. The hierarchical layout template of claim 23, further comprising additional leaf nodes without content element constraints.

25. The hierarchical layout template of claim 23, wherein the shared content element constrain is incorporated in the root node.

26. The hierarchical layout template of claim 23, wherein the shared content element constraint defines a negative content requirement common to all layout structures possible in the choice substructure in the hierarchical layout template.

27. The hierarchical layout template of claim 23, wherein the shared content element constraint comprises an abstracted constraint derived from a plurality of content element constraints.

28. The hierarchical layout template of claim 27, wherein the shared content element constraint comprises a complex content element constraint.

29. The hierarchical layout template of claim 23, wherein the template leaf nodes and the choice substructure form at least a portion of a data structure.

30. The hierarchical layout template of claim 23, wherein the template leaf nodes and the choice substructure form at least a portion of an Interscript layout template.

31. The hierarchical layout template of claim 23, wherein the template leaf nodes and the choice substructure form at least a portion of structured text-based data.

32. The hierarchical layout template of claim 31, wherein the structured text-based data comprises linearized text-based tree data.

33. The hierarchical layout template of claim 32, wherein the linearized text-based tree data comprises XML data.