US6919890B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Grid and table layout using elastics
Assignee: SCSK Corp
•
Filing: 2001-09-27
•
Granted: 2005-07-19
•
Expires: 2021-09-27
Abstract
Abstract A system and method of grid layout generates a fiducial graph for a grid or table in a given dimension and uses the fiducial graph to determine size preferences and fiducial positions of the grid and its grid elements along that dimension. Fiducial positions may include origin fiducials of grids and grid elements as well as fiducial positions of attached grid elements. Types of fiducial graphs include series-parallel fiducial graphs and non-series-parallel fiducial graphs (e.g., partially reduced fiducial graphs), which have different algorithms for computing size preferences and fiducial positions.
Inventors
- 👤 Robert H. Halstead, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:19
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/60
Claims Analysis
Total Claims: 93
Claim 1
Independent Claim
97 words
A method for processing grid layout, comprising: generating a fiducial graph for a grid in a given dimension, the fiducial graph comprising fiducials and constraints of the grid, each constraint having a size preference, the size preference comprising a size and elastic properties; traversing the fiducial graph, combining the size preferences of the constraints into a size preference for the grid in the given dimension; assigning a size to the grid; and assigning positions to the grid fiducials by traversing the fiducial graph, allocating sizes within the grid size to the grid constraints in the given dimension.
Claim 2
Independent Claim
97 words
A method for processing grid layout, comprising: generating a fiducial graph for a grid in a given dimension, the fiducial graph comprising fiducials and constraints of the grid, each constraint having a size preference, the size preference comprising a size and elastic properties; traversing the fiducial graph, combining the size preferences of the constraints into a size preference for the grid in the given dimension; assigning a size to the grid; and assigning positions to the grid fiducials by traversing the fiducial graph, allocating sizes within the grid size to the grid constraints in the given dimension.
Claim 3
Dependent Claim
44 words
The method of claim 1 , wherein generating the fiducial graph further comprises: grouping constraints into parallel constraints if the constraints are between a pair of fiducials; and grouping constraints into series constraints if a first constraint is in series with a second constraint.
Claim 4
Dependent Claim
44 words
The method of claim 2 , wherein the fiducial graph is a series-parallel fiducial graph and generating the fiducial graph further comprises: grouping constraints from the fiducial graph into a series-parallel composition tree having a root constraint being either a parallel or series constraint.
Claim 5
Dependent Claim
59 words
The method of claim 3 , wherein combining the size preferences of the constraints into the size preference for the grid further comprises: computing a size preference for each constituent constraint of the series-parallel composition tree culminating with a size preference for the root constraint, the size preference of the root constraint being the size preference for the grid.
Claim 6
Dependent Claim
32 words
The method of claim 4 , wherein computing the size preference for a parallel constraint comprises: applying a max operation to the size preferences of the constraints grouped within the parallel constraint.
Claim 7
Dependent Claim
32 words
The method of claim 4 , wherein computing the size preference for a series constraint comprises: applying an add operation to the size preferences of the constraints grouped within the series constraint.
Claim 8
Dependent Claim
52 words
The method of claim 3 , wherein assigning positions to the grid fiducials further comprises: allocating a size within the grid size to each constraint; and assigning a position to a fiducial such that the distance between the fiducial and a head fiducial of a constraint is the size of the constraint.
Claim 9
Dependent Claim
88 words
The method of claim 7 , wherein allocating a size to each constraint comprises: dividing the grid size among each constituent constraint of the series-parallel composition tree, the size allocated to a constraint grouped within a parallel constraint being the size allocated to the parallel constraint, the size allocated to a constraint grouped within a series constraint being computed by applying a divide operation to size preferences of constituent constraints within the series constraint and to an overall size allocated to the constituent constraints within the series constraint.
Claim 10
Dependent Claim
72 words
The method of claim 1 , wherein the fiducial graph is a non-series-parallel fiducial graph and combining the size preferences of the constraints into a size preference for the grid further comprises: assigning an initial size preference to each fiducial in the fiducial graph; and traversing constraints in forward and reverse traversals to accumulate size preferences at each fiducial, resulting in an accumulated size preference between each fiducial and a designated fiducial.
Claim 11
Dependent Claim
36 words
The method of claim 9 , wherein the designated fiducial is the head fiducial of the grid, and the size preference of the grid is the accumulated size preference at the tail fiducial of the grid.
Claim 12
Dependent Claim
36 words
The method of claim 9 , wherein the designated fiducial is the tail fiducial of the grid, and the size preference of the grid is the accumulated size preference at the head fiducial of the grid.
Claim 13
Dependent Claim
94 words
The method of claim 9 , wherein accumulating size preferences comprises: combining the size preference of a fiducial with the size preference of a constraint having the fiducial as its head fiducial, resulting in a first resultant size preference; combining the first resultant size preference with the size preference of the tail fiducial of the constraint, resulting in a second resultant size preference; and replacing the size preference of the tail fiducial with the second resultant size preference if the second resultant size preference is different from the size preference of the tail fiducial.
Claim 14
Dependent Claim
32 words
The method of claim 12 , wherein the first resultant size preference results from applying an add operation to the size preference of the fiducial and the size preference of the constraint.
Claim 15
Dependent Claim
35 words
The method of claim 12 , wherein the second resultant size preference results from applying a max operation to the first resultant size preference and the size preference of the tail fiducial of the constraint.
Claim 16
Dependent Claim
94 words
The method of claim 9 , wherein accumulating size preferences comprises: combining the size preference of a fiducial with the size preference of a constraint having the fiducial as its tail fiducial, resulting in a first resultant size preference; combining the first resultant size preference with the size preference of the head fiducial of the constraint, resulting in a second resultant size preference; and replacing the size preference of the head fiducial with the second resultant size preference if the second resultant size preference is different from the size preference of the head fiducial.
Claim 17
Dependent Claim
32 words
The method of claim 15 , wherein the first resultant size preference results from applying a subtraction operation subtracting the size preference of the constraint from the size preference of the fiducial.
Claim 18
Dependent Claim
35 words
The method of claim 15 , wherein the second resultant size preference results from applying a max operation to the first resultant size preference and the size preference of the head fiducial of the constraint.
Claim 19
Dependent Claim
22 words
The method of claim 9 , wherein the fiducial graph is traversed until the accumulated size preference at each fiducial is constant.
Claim 20
Dependent Claim
19 words
The method of claim 9 , wherein the initial size preference of the designated fiducial has rigid elastic properties.
Claim 21
Dependent Claim
19 words
The method of claim 9 , wherein the initial size preference of a non-designated fiducial has stretchy elastic properties.
Claim 22
Dependent Claim
57 words
The method of claim 9 , further comprising: storing a set of back-links for each fiducial in the fiducial graph; and adding a constraint to the set of back-links for a fiducial if a backward traversal of the constraint contributed to the accumulated size preference of the fiducial, each back-link preventing subsequent backward traversals of a constraint.
Claim 23
Dependent Claim
81 words
The method of claim 21 , wherein preventing subsequent backward traversals of a constraint comprises: storing a set of disabled back-links for the fiducial graph; adding a constraint to the set of disabled back-links for the fiducial graph if a backward traversal is attempted from a fiducial on a constraint that is stored in a set of back-links associated with the fiducial; and restarting calculation of the grid size preference, avoiding backward traversal of constraints in the set of disabled back-links.
Claim 24
Dependent Claim
30 words
The method of claim 9 , further comprising: for each fiducial, storing a predecessor fiducial in a chain of fiducials that contributed to the accumulated size preference of the fiducial.
Claim 25
Dependent Claim
31 words
The method of claim 9 , further comprising: marking fiducials during a forward or backward traversal to prevent loops in which a traversal path passes through a fiducial more than once.
Claim 26
Dependent Claim
32 words
The method of claim 9 , further comprising: sorting constraints in order of increasing elastic properties prior to traversal, traversing constraints that most rigidly constrain the size preferences of other fiducials first.
Claim 27
Dependent Claim
53 words
The method of claim 9 , further comprising: constraining the size preference of a fiducial having an assigned position, the size preference comprising rigid elastic properties and a minimum size and a preferred size both equal to the distance between the position of the designated fiducial and the assigned position of the fiducial.
Claim 28
Dependent Claim
116 words
The method of claim 1 , wherein the fiducial graph is a non-series-parallel fiducial graph and assigning positions to the grid fiducials further comprises: pre-assigning positions to the head and tail fiducials of the grid such that the distance between the head and tail fiducials is the size allocated to the grid; traversing constraints in forward and reverse traversals accumulating size preferences at each fiducial, resulting in accumulated size preferences between each fiducial and the head fiducial and between each fiducial and the tail fiducial; and assigning positions for each non-assigned fiducial such that a position for a fiducial is computed after computing positions for each non-assigned successor fiducial in critical chains extending from the fiducial.
Claim 29
Dependent Claim
58 words
The method of claim 27 , further comprising: assigning positions for each non-assigned fiducial such that a non-assigned fiducial is assigned a position after assigning a position for each successor fiducial that can be reached from the non-assigned fiducial by a forward traversal of a constraint, unless the successor fiducial precedes the non-assigned fiducial in a critical chain.
Claim 30
Dependent Claim
103 words
The method of claim 27 , wherein computing a position for a fiducial comprises: dividing the grid size between a first size preference and a second size preference resulting in an allocated size, the first size preference comprising the size preference between the non-assigned fiducial and the head fiducial, the second size preference comprising the size preference between the non-assigned fiducial and the tail fiducial, the allocated size being the distance between the head fiducial and the non-assigned fiducial; and assigning a position to the non-assigned fiducial such that the distance between the non-assigned fiducial and the head fiducial is the allocated size.
Claim 31
Dependent Claim
20 words
The method of claim 27 , further comprising: pre-assigning a position to a grid origin fiducial in the given dimension.
Claim 32
Dependent Claim
35 words
The method of claim 27 , wherein assigning a position for a non-assigned fiducial comprises: constraining the position assigned to the non-assigned fiducial to be no less than a position assigned to a predecessor fiducial.
Claim 33
Dependent Claim
35 words
The method of claim 27 , wherein assigning a position for a non-assigned fiducial comprises: constraining the position assigned to the non-assigned fiducial to be no greater than a position assigned to a successor fiducial.
Claim 34
Dependent Claim
54 words
The method of claim 27 , wherein assigning a position for a non-assigned fiducial comprises: constraining the position assigned to the non-assigned fiducial to be no less than a position assigned to a predecessor fiducial plus a minimum size of the size preference associated with a constraint between the fiducial and the predecessor fiducial.
Claim 35
Dependent Claim
54 words
The method of claim 27 , wherein assigning a position for a non-assigned fiducial comprises: constraining the position assigned to the non-assigned fiducial to be no greater than a position assigned to a successor fiducial minus a minimum size of the size preference associated with the constraint between the fiducial and the successor fiducial.
Claim 36
Dependent Claim
50 words
The method of claim 27 , wherein assigning a position for a non-assigned fiducial comprises: constraining the position assigned to the non-assigned fiducial to be no less than a position assigned to the head fiducial plus a minimum size of the size preference from the head fiducial to the fiducial.
Claim 37
Dependent Claim
50 words
The method of claim 27 , wherein assigning a position for a non-assigned fiducial comprises: constraining the position assigned to the non-assigned fiducial to be no greater than a position assigned to the tail fiducial minus a minimum size of the size preference to the tail fiducial from the fiducial.
Claim 38
Dependent Claim
73 words
The method of claim 1 , wherein a grid element has an origin coupled to a fiducial in the given dimension, and the fiducial graph comprises a first constraint and a second constraint for the grid element, the first constraint having a size preference from a head fiducial of the grid element to the origin, the second constraint having a size preference from the origin to a tail fiducial of the grid element.
Claim 39
Dependent Claim
153 words
The method of claim 1 , wherein a grid element has an origin not coupled to a fiducial in the given dimension, and the fiducial graph comprises a constraint for the grid element having a total size preference being a result of applying an add operation to a first size preference and a second size preference, the first size preference being a size preference from a head fiducial of the grid element to the origin, and the second size preference being a size preference from the origin to a tail fiducial of the grid element, the method further comprising: dividing a total size allocated to the grid element between the first size preference and the second size preference resulting in an allocated size; and assigning a position to the origin in the given dimension such that the distance between the origin and the head fiducial of the grid element is the allocated size.
Claim 40
Dependent Claim
57 words
The method of claim 1 , wherein the grid further comprises an origin, the fiducial graph comprising an origin fiducial in the given dimension, further comprising: computing a size preference from the head fiducial of the grid to the origin fiducial; and computing a size preference from the origin fiducial to the tail fiducial of the grid.
Claim 41
Dependent Claim
46 words
The method of claim 39 , further comprising: adjusting the size preferences before and after the origin fiducial such that the result of applying an add operation to the size preferences equals the size preference from the head fiducial to the tail fiducial of the grid.
Claim 42
Dependent Claim
62 words
The method of claim 1 , wherein the grid represents a table having table elements, each table element having an origin in the given dimension further comprising: aligning the origins of one or more table elements in the given dimension by creating a fiducial in the underlying grid and attaching the origins of the one or more table elements to the fiducial.
Claim 43
Independent Claim
112 words
A system for processing grid layout, comprising: a layout processor, the layout processor generating a fiducial graph for a grid in a given dimension, the fiducial graph comprising fiducials and constraints of the grid, each constraint having a size preference, the size preference comprising a size and elastic properties; the layout processor traversing the fiducial graph, combining the size preferences of the constraints into a size preference for the grid in the given dimension; the layout processor assigning a size to the grid; and the layout processor assigning positions to the grid fiducials by traversing the fiducial graph, allocating sizes within the grid size to the grid constraints in the given dimension.
Claim 44
Independent Claim
112 words
A system for processing grid layout, comprising: a layout processor, the layout processor generating a fiducial graph for a grid in a given dimension, the fiducial graph comprising fiducials and constraints of the grid, each constraint having a size preference, the size preference comprising a size and elastic properties; the layout processor traversing the fiducial graph, combining the size preferences of the constraints into a size preference for the grid in the given dimension; the layout processor assigning a size to the grid; and the layout processor assigning positions to the grid fiducials by traversing the fiducial graph, allocating sizes within the grid size to the grid constraints in the given dimension.
Claim 45
Dependent Claim
50 words
The system of claim 42 , wherein the fiducial graph is a series-parallel fiducial graph and the layout processor generating a fiducial graph further comprises: the layout processor grouping constraints from the fiducial graph into a series-parallel composition tree having a root constraint being either a parallel or series constraint.
Claim 46
Dependent Claim
65 words
The system of claim 43 , wherein the layout processor combining the size preferences of the constraints into the size preference for the grid further comprises: the layout processor computing a size preference for each constituent constraint of the series-parallel composition tree culminating with a size preference for the root constraint, the size preference of the root constraint being the size preference for the grid.
Claim 47
Dependent Claim
38 words
The system of claim 44 , wherein the layout processor computing the size preference for a parallel constraint comprises: the layout processor applying a max operation to the size preferences of the constraints grouped within the parallel constraint.
Claim 48
Dependent Claim
38 words
The system of claim 44 , wherein the layout processor computing the size preference for a series constraint comprises: the layout processor applying an add operation to the size preferences of the constraints grouped within the series constraint.
Claim 49
Dependent Claim
61 words
The system of claim 43 , wherein the layout processor assigning positions to the grid fiducials further comprises: the layout processor allocating a size within the grid size to each constraint; and the layout processor assigning a position to a fiducial such that the distance between the fiducial and a head fiducial of a constraint is the size of the constraint.
Claim 50
Dependent Claim
97 words
The system of claim 47 , wherein the layout processor allocating a size to each constraint comprises: the layout processor dividing the grid size among each constituent constraint of the series-parallel composition tree, the size allocated to a constraint grouped within a parallel constraint being the size allocated to the parallel constraint, the size allocated to a constraint grouped within a series constraint being computed by the layout processor applying a divide operation to size preferences of constituent constraints within the series constraint and to an overall size allocated to the constituent constraints within the series constraint.
Claim 51
Dependent Claim
81 words
The system of claim 42 , wherein the fiducial graph is a non-series-parallel fiducial graph and the layout processor combining the size preferences of the constraints into a size preference for the grid further comprises: the layout processor assigning an initial size preference to each fiducial in the fiducial graph; and the layout processor traversing constraints in forward and reverse traversals to accumulate size preferences at each fiducial, resulting in an accumulated size preference between each fiducial and a designated fiducial.
Claim 52
Dependent Claim
106 words
The system of claim 49 , wherein the layout processor accumulating size preferences comprises: the layout processor combining the size preference of a fiducial with the size preference of a constraint having the fiducial as its head fiducial, resulting in a first resultant size preference; the layout processor combining the first resultant size preference with the size preference of the tail fiducial of the constraint, resulting in a second resultant size preference; and the layout processor replacing the size preference of the tail fiducial with the second resultant size preference if the second resultant size preference is different from the size preference of the tail fiducial.
Claim 53
Dependent Claim
106 words
The system of claim 49 , wherein the layout processor accumulating size preferences comprises: the layout processor combining the size preference of a fiducial with the size preference of a constraint having the fiducial as its tail fiducial, resulting in a first resultant size preference; the layout processor combining the first resultant size preference with the size preference of the head fiducial of the constraint, resulting in a second resultant size preference; and the layout processor replacing the size preference of the head fiducial with the second resultant size preference if the second resultant size preference is different from the size preference of the head fiducial.
Claim 54
Dependent Claim
35 words
The system of claim 51 , wherein the first resultant size preference results from the layout processor applying a subtraction operation subtracting the size preference of the constraint from the size preference of the fiducial.
Claim 55
Dependent Claim
63 words
The system of claim 49 , further comprising: the layout processor storing a set of back-links for each fiducial in the fiducial graph; and the layout processor adding a constraint to the set of back-links for a fiducial if a backward traversal of the constraint contributed to the accumulated size preference of the fiducial, each back-link preventing subsequent backward traversals of a constraint.
Claim 56
Dependent Claim
33 words
The system of claim 49 , further comprising: for each fiducial, the layout processor storing a predecessor fiducial in a chain of fiducials that contributed to the accumulated size preference of the fiducial.
Claim 57
Dependent Claim
34 words
The system of claim 49 , further comprising: the layout processor marking fiducials during a forward or backward traversal to prevent loops in which a traversal path passes through a fiducial more than once.
Claim 58
Dependent Claim
38 words
The system of claim 49 , further comprising: the layout processor sorting constraints in order of increasing elastic properties prior to traversal, the layout processor traversing constraints that most rigidly constrain the size preferences of other fiducials first.
Claim 59
Dependent Claim
56 words
The system of claim 49 , further comprising: the layout processor constraining the size preference of a fiducial having an assigned position, the size preference comprising rigid elastic properties and a minimum size and a preferred size both equal to the distance between the position of the designated fiducial and the assigned position of the fiducial.
Claim 60
Dependent Claim
128 words
The system of claim 42 , wherein the fiducial graph is a non-series-parallel fiducial graph and the layout processor assigning positions to the grid fiducials further comprises: the layout processor pre-assigning positions to the head and tail fiducials of the grid such that the distance between the head and tail fiducials is the size allocated to the grid; the layout processor traversing constraints in forward and reverse traversals accumulating size preferences at each fiducial, resulting in accumulated size preferences between each fiducial and the head fiducial and between each fiducial and the tail fiducial; and the layout processor assigning positions for each non-assigned fiducial such that a position for a fiducial is computed after computing positions for each non-assigned successor fiducial in critical chains extending from the fiducial.
Claim 61
Dependent Claim
73 words
The system of claim 42 , wherein a grid element has an origin coupled to a fiducial in the given dimension, and the fiducial graph comprises a first constraint and a second constraint for the grid element, the first constraint having a size preference from a head fiducial of the grid element to the origin, the second constraint having a size preference from the origin to a tail fiducial of the grid element.
Claim 62
Dependent Claim
162 words
The system of claim 42 , wherein a grid element has an origin not coupled to a fiducial in the given dimension, and the fiducial graph comprises a constraint for the grid element having a total size preference being a result of the layout processor applying an add operation to a first size preference and a second size preference, the first size preference being a size preference from a head fiducial of the grid element to the origin, and the second size preference being a size preference from the origin to a tail fiducial of the grid element, the system further comprising: the layout processor dividing a total size allocated to the grid element between the first size preference and the second size preference resulting in an allocated size; and the layout processor assigning a position to the origin in the given dimension such that the distance between the origin and the head fiducial of the grid element is the allocated size.
Claim 63
Dependent Claim
63 words
The system of claim 42 , wherein the grid further comprises an origin, the fiducial graph comprising an origin fiducial in the given dimension, further comprising: the layout processor computing a size preference from the head fiducial of the grid to the origin fiducial; and the layout processor computing a size preference from the origin fiducial to the tail fiducial of the grid.
Claim 64
Dependent Claim
65 words
The system of claim 42 , wherein the grid represents a table having table elements, each table element having an origin in the given dimension further comprising: the layout processor aligning the origins of one or more table elements in the given dimension by creating a fiducial in the underlying grid and attaching the origins of the one or more table elements to the fiducial.
Claim 65
Dependent Claim
117 words
A computer program product comprising: a computer-usable medium; a set of computer operating instructions embodied on the medium, including instructions for processing grid layout, comprising instructions for: generating a fiducial graph for a grid in a given dimension, the fiducial graph comprising fiducials and constraints of the grid, each constraint having a size preference, the size preference comprising a size and elastic properties; traversing the fiducial graph, combining the size preferences of the constraints into a size preference for the grid in the given dimension; assigning a size to the grid; and assigning positions to the grid fiducials by traversing the fiducial graph, allocating sizes within the grid size to the grid constraints in the given dimension.
Claim 66
Dependent Claim
117 words
A computer program product comprising: a computer-usable medium; a set of computer operating instructions embodied on the medium, including instructions for processing grid layout, comprising instructions for: generating a fiducial graph for a grid in a given dimension, the fiducial graph comprising fiducials and constraints of the grid, each constraint having a size preference, the size preference comprising a size and elastic properties; traversing the fiducial graph, combining the size preferences of the constraints into a size preference for the grid in the given dimension; assigning a size to the grid; and assigning positions to the grid fiducials by traversing the fiducial graph, allocating sizes within the grid size to the grid constraints in the given dimension.
Claim 67
Dependent Claim
51 words
The computer program product of claim 63 , wherein the fiducial graph is a series-parallel fiducial graph and the instructions for generating the fiducial graph comprise further instructions for: grouping constraints from the fiducial graph into a series-parallel composition tree having a root constraint being either a parallel or series constraint.
Claim 68
Dependent Claim
66 words
The computer program product of claim 64 , wherein the instructions for combining the size preferences of the constraints into the size preference for the grid comprise further instructions for: computing a size preference for each constituent constraint of the series-parallel composition tree culminating with a size preference for the root constraint, the size preference of the root constraint being the size preference for the grid.
Claim 69
Dependent Claim
59 words
The computer program product of claim 64 , wherein the instructions for assigning positions to the grid fiducials comprise further instructions for: allocating a size within the grid size to each constraint; and assigning a position to a fiducial such that the distance between the fiducial and a head fiducial of a constraint is the size of the constraint.
Claim 70
Dependent Claim
79 words
The computer program product of claim 63 , wherein the fiducial graph is a non-series-parallel fiducial graph and the instructions for combining the size preferences of the constraints into a size preference for the grid comprise further instructions for: assigning an initial size preference to each fiducial in the fiducial graph; and traversing constraints in forward and reverse traversals to accumulate size preferences at each fiducial, resulting in an accumulated size preference between each fiducial and a designated fiducial.
Claim 71
Dependent Claim
102 words
The computer program product of claim 67 , wherein the instructions for accumulating size preferences comprise further instructions for: combining the size preference of a fiducial with the size preference of a constraint having the fiducial as its head fiducial, resulting in a first resultant size preference; combining the first resultant size preference with the size preference of the tail fiducial of the constraint, resulting in a second resultant size preference; and replacing the size preference of the tail fiducial with the second resultant size preference if the second resultant size preference is different from the size preference of the tail fiducial.
Claim 72
Dependent Claim
102 words
The computer program product of claim 67 , wherein the instructions for accumulating size preferences comprise further instructions for: combining the size preference of a fiducial with the size preference of a constraint having the fiducial as its tail fiducial, resulting in a first resultant size preference; combining the first resultant size preference with the size preference of the head fiducial of the constraint, resulting in a second resultant size preference; and replacing the size preference of the head fiducial with the second resultant size preference if the second resultant size preference is different from the size preference of the head fiducial.
Claim 73
Dependent Claim
61 words
The computer program product of claim 67 , further comprising instructions for: storing a set of back-links for each fiducial in the fiducial graph; and adding a constraint to the set of back-links for a fiducial if a backward traversal of the constraint contributed to the accumulated size preference of the fiducial, each back-link preventing subsequent backward traversals of a constraint.
Claim 74
Dependent Claim
34 words
The computer program product of claim 67 , further comprising instructions for: for each fiducial, storing a predecessor fiducial in a chain of fiducials that contributed to the accumulated size preference of the fiducial.
Claim 75
Dependent Claim
35 words
The computer program product of claim 67 , further comprising instructions for: marking fiducials during a forward or backward traversal to prevent loops in which a traversal path passes through a fiducial more than once.
Claim 76
Dependent Claim
123 words
The computer program product of claim 63 , wherein the fiducial graph is a non-series-parallel fiducial graph and the instructions for assigning positions to the grid fiducials comprise further instructions for: pre-assigning positions to the head and tail fiducials of the grid such that the distance between the head and tail fiducials is the size allocated to the grid; traversing constraints in forward and reverse traversals accumulating size preferences at each fiducial, resulting in accumulated size preferences between each fiducial and the head fiducial and between each fiducial and the tail fiducial; and assigning positions for each non-assigned fiducial such that a position for a fiducial is computed after computing positions for each non-assigned successor fiducial in critical chains extending from the fiducial.
Claim 77
Dependent Claim
75 words
The computer program product of claim 63 , wherein a grid element has an origin coupled to a fiducial in the given dimension, and the fiducial graph comprises a first constraint and a second constraint for the grid element, the first constraint having a size preference from a head fiducial of the grid element to the origin, the second constraint having a size preference from the origin to a tail fiducial of the grid element.
Claim 78
Dependent Claim
155 words
The computer program product of claim 63 , wherein a grid element has an origin not coupled to a fiducial in the given dimension, and the fiducial graph comprises a constraint for the grid element having a total size preference being a result of applying an add operation to a first size preference and a second size preference, the first size preference being a size preference from a head fiducial of the grid element to the origin, and the second size preference being a size preference from the origin to a tail fiducial of the grid element, further comprising instructions for: dividing a total size allocated to the grid element between the first size preference and the second size preference resulting in an allocated size; and assigning a position to the origin in the given dimension such that the distance between the origin and the head fiducial of the grid element is the allocated size.
Claim 79
Dependent Claim
61 words
The computer program product of claim 63 , wherein the grid further comprises an origin, the fiducial graph comprising an origin fiducial in the given dimension, further comprising instructions for: computing a size preference from the head fiducial of the grid to the origin fiducial; and computing a size preference from the origin fiducial to the tail fiducial of the grid.
Claim 80
Dependent Claim
66 words
The computer program product of claim 63 , wherein the grid represents a table having table elements, each table element having an origin in the given dimension, further comprising instructions for: aligning the origins of one or more table elements in the given dimension by creating a fiducial in the underlying grid and attaching the origins of the one or more table elements to the fiducial.
Claim 81
Dependent Claim
113 words
A computer data signal embodied in a carrier wave comprising a code segment for processing grid layout, the code segment comprising instructions for: generating a fiducial graph for a grid in a given dimension, the fiducial graph comprising fiducials and constraints of the grid, each constraint having a size preference, the size preference comprising a size and elastic properties; traversing the fiducial graph, combining the size preferences of the constraints into a size preference for the grid in the given dimension; assigning a size to the grid; and assigning positions to the grid fiducials by traversing the fiducial graph, allocating sizes within the grid size to the grid constraints in the given dimension.
Claim 82
Dependent Claim
113 words
A computer data signal embodied in a carrier wave comprising a code segment for processing grid layout, the code segment comprising instructions for: generating a fiducial graph for a grid in a given dimension, the fiducial graph comprising fiducials and constraints of the grid, each constraint having a size preference, the size preference comprising a size and elastic properties; traversing the fiducial graph, combining the size preferences of the constraints into a size preference for the grid in the given dimension; assigning a size to the grid; and assigning positions to the grid fiducials by traversing the fiducial graph, allocating sizes within the grid size to the grid constraints in the given dimension.
Claim 83
Dependent Claim
55 words
The computer data signal of claim 78 , wherein the fiducial graph is a series-parallel fiducial graph and the instructions of the code segment for generating the fiducial graph comprise further instructions for: grouping constraints from the fiducial graph into a series-parallel composition tree having a root constraint being either a parallel or series constraint.
Claim 84
Dependent Claim
70 words
The computer data signal of claim 79 , wherein the instructions of the code segment for combining the size preferences of the constraints into the size preference for the grid comprise further instructions for: computing a size preference for each constituent constraint of the series-parallel composition tree culminating with a size preference for the root constraint, the size preference of the root constraint being the size preference for the grid.
Claim 85
Dependent Claim
63 words
The computer data signal of claim 79 , wherein the instructions of the code segment for assigning positions to the grid fiducials comprise further instructions for: allocating a size within the grid size to each constraint; and assigning a position to a fiducial such that the distance between the fiducial and a head fiducial of a constraint is the size of the constraint.
Claim 86
Dependent Claim
83 words
The computer data signal of claim 78 , wherein the fiducial graph is a non-series-parallel fiducial graph and the instructions of the code segment for combining the size preferences of the constraints into a size preference for the grid comprise further instructions for: assigning an initial size preference to each fiducial in the fiducial graph; and traversing constraints in forward and reverse traversals to accumulate size preferences at each fiducial, resulting in an accumulated size preference between each fiducial and a designated fiducial.
Claim 87
Dependent Claim
106 words
The computer data signal of claim 82 , wherein the instructions of the code segment for accumulating size preferences comprise further instructions for: combining the size preference of a fiducial with the size preference of a constraint having the fiducial as its head fiducial, resulting in a first resultant size preference; combining the first resultant size preference with the size preference of the tail fiducial of the constraint, resulting in a second resultant size preference; and replacing the size preference of the tail fiducial with the second resultant size preference if the second resultant size preference is different from the size preference of the tail fiducial.
Claim 88
Dependent Claim
106 words
The computer data signal of claim 82 , wherein the instructions of the code segment for accumulating size preferences comprise further instructions for: combining the size preference of a fiducial with the size preference of a constraint having the fiducial as its tail fiducial, resulting in a first resultant size preference; combining the first resultant size preference with the size preference of the head fiducial of the constraint, resulting in a second resultant size preference; and replacing the size preference of the head fiducial with the second resultant size preference if the second resultant size preference is different from the size preference of the head fiducial.
Claim 89
Dependent Claim
127 words
The computer data signal of claim 78 , wherein the fiducial graph is a non-series-parallel fiducial graph and the instructions of the code segment for assigning positions to the grid fiducials comprise further instructions for: pre-assigning positions to the head and tail fiducials of the grid such that the distance between the head and tail fiducials is the size allocated to the grid; traversing constraints in forward and reverse traversals accumulating size preferences at each fiducial, resulting in accumulated size preferences between each fiducial and the head fiducial and between each fiducial and the tail fiducial; and assigning positions for each non-assigned fiducial such that a position for a fiducial is computed after computing positions for each non-assigned successor fiducial in critical chains extending from the fiducial.
Claim 90
Dependent Claim
75 words
The computer data signal of claim 78 , wherein a grid element has an origin coupled to a fiducial in the given dimension, and the fiducial graph comprises a first constraint and a second constraint for the grid element, the first constraint having a size preference from a head fiducial of the grid element to the origin, the second constraint having a size preference from the origin to a tail fiducial of the grid element.
Claim 91
Dependent Claim
158 words
The computer data signal of claim 78 , wherein a grid element has an origin not coupled to a fiducial in the given dimension, and the fiducial graph comprises a constraint for the grid element having a total size preference being a result of applying an add operation to a first size preference and a second size preference, the first size preference being a size preference from a head fiducial of the grid element to the origin, and the second size preference being a size preference from the origin to a tail fiducial of the grid element, the code segment further comprising instructions for: dividing a total size allocated to the grid element between the first size preference and the second size preference resulting in an allocated size; and assigning a position to the origin in the given dimension such that the distance between the origin and the head fiducial of the grid element is the allocated size.
Claim 92
Dependent Claim
64 words
The computer data signal of claim 78 , wherein the grid further comprises an origin, the fiducial graph comprising an origin fiducial in the given dimension, the code segment further comprising instructions for: computing a size preference from the head fiducial of the grid to the origin fiducial; and computing a size preference from the origin fiducial to the tail fiducial of the grid.
Claim 93
Dependent Claim
69 words
The computer data signal of claim 78 , wherein the grid represents a table having table elements, each table element having an origin in the given dimension, the code segment further comprising instructions for: aligning the origins of one or more table elements in the given dimension by creating a fiducial in the underlying grid and attaching the origins of the one or more table elements to the fiducial.
References Cited (Backward Citations)
US4608664A
Cited
US4799172A
Cited
US5148520A
Cited
US5208906A
Cited
US5237312A
Cited
US5060170A
Cited
US5953735A
Cited
US5341466A
Cited
US5649216A
Cited
US5293475A
Cited
US5335290A
Cited
US5577189A
Cited
US5371847A
Cited
US5353401A
Cited
US5796402A
Cited
US5513342A
Cited
US5721848A
Cited
US5636129A
Cited
US5577187A
Cited
JPH08287117A
Cited
US5754873A
Cited
US5838317A
Cited
US6043817A
Cited
US5873106A
Cited
US5712995A
Cited
US5838318A
Cited
EP0821313A1
Cited
US6125385A
Cited
US5796401A
Cited
US5760772A
Cited
US5765176A
Cited
EP0848351A2
Cited
US6154757A
Cited
WO1998036630A2
Cited
US6111573A
Cited
US6002446A
Cited
US6057842A
Cited
US6181838B1
Cited
US5886694A
Cited
US6339434B1
Cited
US6330004B1
Cited
US6785866B1
Cited
US6185589B1
Cited
US6396500B1
Cited
US6414698B1
Cited
US6356279B1
Cited
US6473093B1
Cited
US6504544B1
Cited
US6667750B1
Cited
US6380940B1
Cited
US20040189709A1
Cited
US6750887B1
Cited
US20020111969A1
Cited
US20020118193A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2008-07-18 | 2009-01-17 | 2009-07-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2012-07-18 | 2013-01-17 | 2013-07-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2016-07-18 | 2017-01-17 | 2017-07-19 | $7700.00 | Window Closed / Lapsed |