Table allocating apparatus and method

• US 5,808,914 A
• Filed: 04/07/1995
• Issued: 09/15/1998
• Est. Priority Date: 04/11/1994
• Status: Expired due to Fees

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Shin, Kil-Ho, Kobayashi, Kenichi, Suzuki, Akira
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): ROBERTS, ANDREW S
• Application Number:
  US08/418,400
• Time in Patent Office: 1,257 Days
• Field of Search: 395/770, 395/600, 395/500, 364/943, 364/943.44, 364/943.5
• US Class Current: 703/2
• CPC Class Codes: G06F 40/177 of tables; using ruled lines

Abstract

A table allocating apparatus for producing a layout of a table. In the apparatus, both of a linear equation for representing a column width of a table or a row height thereof by employing a parameter, and a section constraint condition corresponding to a combination of conditions for satisfying the parameter in order that a height or a width of a rectangle becomes constant when each of texts arranged in a table item column is allocated are set, then a layout evaluation formula expressed by the linear equation with employment of the parameter and indicative of better states of a layout for each of the section constraint conditions is calculated. Further, such a linear programming problem that the section constraint condition is used as a restriction condition and the layout evaluation formula corresponding to each of the section constraint conditions is used as an objective function is solved, thereby obtaining a set of an optimum layout evaluation value and a parameter corresponding to the optimum layout evaluation value, or an infeasible solution of the problem, and when the set of the optimum layout evaluation value and the parameter corresponding thereto is acquired, a set of the optimum layout evaluation value and the parameter corresponding thereto based on the acquired result among all of the linear programming problems are retrieved, whereby a table layout is determined based upon the set of the optimum layout evaluation value and the parameter corresponding thereto.

Claims

1. A table layout apparatus for providing a layout of a table having rows and columns, comprising:

text holding means for holding at least one text to be laid out within the table;

connector holding means for holding at least one linear function with respect to parameters, each linear function being associated with a column of the table and representing a width of the column;

sectional constraint holding means for holding a sectional constraint for each text held by the text holding means, the sectional constraint including at least one linear inequality for which values for the parameters should satisfy in order that a height of a layout box, which is a rectangular area for laying out the text, remains constant;

layout evaluation means for receiving the height of the layout box and for calculating a target function in accordance with the received height of the layout box and the at least one linear function held by the connector holding means, the target function being linear with respect to the width of the columns of the table;

linear programming problem solution engine means for receiving the sectional constraint and, under the received sectional constraint, for finding optimal solutions for the parameter that yield a minimum/maximum value for the target function calculated by the layout evaluation means by solving a linear programming problem determined by the target function and the sectional constraint; and

linear programming problem managing means for finding optimal solutions for the parameters by repeating the following steps until at least one optimal solution is found;

selecting a sectional constraint held by the sectional constraint holding means;

inputting the selected sectional constraint to the linear programming problem solution engine means; and

receiving an output from the linear programming problem solution engine means, wherein the output is a pair of the optimal solutions for the parameters under the condition of the inputted sectional constraint and the value of the target function.

2. The table layout apparatus as claimed in claim 1, further comprising generic constraint holding means for holding a generic constraint, which is at least one linear inequality for which the values of the parameters always satisfy, and

wherein the linear programming problem solution engine means attempts to find optimal solutions within a range determined by the generic constraint held by the generic constraint holding means in addition to the given sectional constraint.

3. The table layout apparatus as claimed in claim 1, further comprising:

text classifying means for grouping the texts held by the text holding means into at least one text class such that every text belonging to a particular text class shares a common homogeneous part of the linear function with respect to the parameters,

wherein the common homogeneous part of the linear function represents a width of a layout box of the text and is determined from the linear functions held by the connector holding means, and

wherein the sectional condition holding means calculates and holds a sectional constraint for each text class.

4. The table layout apparatus as claimed in claim 1, wherein the linear programming problem solution engine means calculates a simplex table for each of the linear programming problems, the table layout apparatus further comprising:

shared part holding means for holding the shared part of a plurality of simplex tables which the linear programming problem solution engine means registers when the linear problem solution engine means calculates a simplex table at first, and in commencing to solve a new given linear programming problem, the linear programming problem solution means uses a shared part to complete a simple table.

5. The table layout apparatus as claimed in claim 1, wherein the target function calculated by said layout evaluation means corresponds to a formula based upon a summation of areas of the space regions after the text has been allocated to the item column in the table.

6. The table layout apparatus as claimed in claim 1, further comprising linear programming problem status holding means for holding a status to indicate that a feasibility of each of the linear programming problems is at least "feasible", "infeasible", or "unknown", and linear programming problem status calculating means for updating the status held in said linear programming problem status holding means as to a plurality of linear programming problems every time said linear programming problem status holding means judges the feasibility of each linear programming problem, wherein at least a linear programming problem having a status of "infeasible" is not processed.

7. The table layout apparatus as claimed in claim 6, wherein the statuses held in said linear programming problem status holding means include priority orders, and said linear programming problem managing means includes linear programming problem selecting means for determining an order along which the linear programming problems are solved based on the priority order of said status.

8. The table layout apparatus as claimed in claim 1, wherein the linear programming problem solution engine means includes adjoining basic feasible solution calculating means and adjoining basic feasible solution holding means,

wherein, whenever the linear programming problem solution engine means calculates a combination of a feasible base and an associated basic feasible solution, the adjoining basic feasible solution calculating means calculates the combination of the feasible base and the associated basic feasible solution for each of the other linear programming problems that are adjacent to the linear programming problem for which the linear programming problem solution engine means has processed, and

wherein the adjoining basic feasible solution holding means holds the combination of the feasible base and the associated basic feasible solution that the adjoining basic feasible solution holding means calculates, and in commencing to solve a new linear programming problem, the linear programming problem solution engine means retrieves a combination of a feasible base and an associated basic feasible solution, if present, from the adjoining basic feasible solution holding means and then uses it as the initial combination of the feasible base and the basic feasible solution.

9. The table layout apparatus as claimed in claim 8, further comprising:

linear programming problem status holding means for holding a status to indicate that a feasibility of each of the linear programming problems is at least one of "solved", "basic solution being held", "feasible", "infeasible", and "unknown"; and

linear programming problem status calculating means for updating the status held in said linear programming problem status holding means as to a plurality of linear programming problems every time said linear programming problem status holding means judges the feasibility of each linear programming problem, wherein at least a linear programming problem having a status of "infeasible" is not processed, and a linear programming problem having a status of "basic solution being held" is solved by employing the feasible base and the basic solution, which correspond to the linear programming problem and are held in said adjoining basic feasible solution holding means.

10. A table layout method for producing a layout of a table having rows and columns, comprising the steps of:

setting at least one text to be laid out within the table;

setting at least one linear function with respect to parameters, wherein each linear function is associated with a column of the table and represents a width of the column;

setting a sectional constraint for each text, the sectional constraint including at least one linear inequality for which values for the parameters should satisfy in order that a height of a layout box, which is a rectangular area in the table for laying out the text, remains constant;

finding optimal solutions for the parameters by repeating the following steps until at least one optimal solution is found;

selecting one of the sectional constraints;

calculating a target function for the selected sectional constraint in accordance with the height of the layout box and the at least one linear function, the target function being linear with respect to the width of the columns of the table; and

under the selected sectional constraint, finding optimal solutions for the parameters which yield a minimum/maximum value for the target function by solving a linear programming problem determined by the selected sectional constraint and the calculated target function.