Constraint Based Graphics System

1. Field of the Invention

The present invention relates to the field of graphic layout methods and apparatuses, and more particularly to a constraint based graphics system for creating graphic layouts and for generating charts and graphs from data such as computer spreadsheet data.

2. Background Art

Computers are often used for numerical analysis. For these tasks, a computer program or system known as a "spreadsheet" is often used. In a computer spreadsheet system, data is arranged in a two dimensional grid of "cells" arranged in horizontal rows and vertical columns. The data content of cells may consist of text, numerical values, or arithmetic, statistical, or logical formulas that define the content of a cell in terms of the content of certain specified other cells. Examples of well known prior art spreadsheet programs are VisiCalc.RTM. from VisiCorp, Lotus 1-2-3.RTM. from Lotus Development Corporation, Excel.RTM. from Microsoft Corporation, and Quattro.RTM. from Borland International Inc.

FIG. 1 shows an example of a simple spreadsheet containing regional and total sales figures of a hypothetical company for the years 1988, 1989 and 1990. Vertical columns B, C and D contain sales data for each of the years 1988, 1989 and 1990, respectively. Horizontal columns 2-6 contain sales data for each of the North, South, East and West sales regions and for total sales, respectively.

In addition to displaying numerical data in the row and column format shown in FIG. 1, a spreadsheet system will often include subsystems that can display numerical data contained in spreadsheet cells in a graphical form. For example, prior art spreadsheet programs typically are able to generate bar charts, pie charts, and line graphs from data contained in selected spreadsheet cells. FIGS. 2 and 3 show examples of two types of bar charts that may be generated by spreadsheet programs of the prior art using the data of the spreadsheet of FIG. 1.

FIG. 2 shows a bar chart with four groups of vertical bars, one for each of the four sales regions North, South, East and West. Each group of bars contains three vertical bars for each of the sales years 1988, 1989, and 1990. The type of graph shown in FIG. 2 is useful for showing the relative changes in sales for each region over the three year period 1988 to 1990.

FIG. 3 shows a bar chart with a stacked bar for each of the four sales regions. Each stacked bar consists of three bars stacked on top of each other, one for each of the three years of the sales period. The heights of the stacked bars represent the total sales for each of the regions over the three year sales period. The type of graph shown in FIG. 3 is useful for comparing the cumulative sales of each region over the three year sales period.

Generating graphical charts from spreadsheet data involves (1) extracting the relevant numerical and text label data from appropriate spreadsheet cells and (2) transforming the data into a graphic image.

For example, to generate the bar chart of FIG. 2 from the spreadsheet data of FIG. 1, a user first identifies the data that is to be charted, typically by selecting the "range" of cells that contains the data (a "range" is a two dimensional contiguous block of spreadsheet cells). In this example, the appropriate range is is the rectangular group of cells from cell B2 to cell D5.

After the appropriate range of cells is identified, the spreadsheet system extracts the cell data needed to construct the desired graph. Data is typically extracted from the selected range on a row by row basis. For example, for the selected range B2 to D5 in FIG. 1, data may be extracted as four series of data values, one series for each of the four rows 2, 3, 4 and 5. For row 2 the appropriate series would be "19,800", "26,750" and "34,580". For row 3 the appropriate series would be "11,760", "13,450" and "13,760". For row 4 the appropriate series would be "28,670", "30,240" and "29,650". For row 5 the appropriate series would be "25,430", "29,760" and "36,780".

The selected data is transformed into a graphic image of a chart or graph by means of an appropriate "driver". A "driver" is a computer program or system that generates "draw" commands, using the selected data, for the graphic shapes and objects that form the individual components of the graph being created. These draw commands are sent to the computer's drawing subsystem, which, in response, draws geometric objects on the computer's display screen.

For example, the bar chart of FIG. 2 is made up of the following components: (a) rectangles 200a to 2001 that represent the twelve vertical bars; (b) vertical line 205 that represents the vertical axis; (c) horizontal line 210 that represents the horizontal axis; (d) short horizontal line segments 215a to 215e that represent the tick marks on the vertical axis; (e) vertical axis labels 220a to 220e; and (f) horizontal axis labels 225a to 225d. The size, position, and type of each of these components must be determined by the driver, and the proper command to draw each of the components at the correct size and position must be sent to the drawing subsystem. To draw rectangles, such as those that represent the vertical bars, the coordinates of the bottom left and top right corners must typically be provided to the drawing subsystem. For line segments, such as those representing the vertical and horizontal axes, the beginning and end point coordinates must be provided. The vertical axis labels must be calculated (typically by determining the maximum height of the bars, rounding off upwards, and dividing into sections in a predefined manner), and the positions of the text characters making up the horizontal and vertical axis labels must be specified. Information about each component is sent by the driver to the drawing subsystem, which draws the components, one by one, on the display screen.

In the prior art, a different "driver" is required for each type of graph or chart. For example, the stacked chart of FIG. 3 requires a different driver than the bar chart of FIG. 2. Accordingly, the types of graphs and charts available to a user are limited to the graphs and charts for which "drivers" are available. The more sophisticated the chart, the more complex (and therefore more costly, in terms of development time, memory usage, and execution time) the driver.

The present invention consists of a constraint based graphic system for creating graphic layouts of constraint-related graphic objects. The graphic objects are defined in a "constraint hierarchy". The constraint hierarchy defines graphic object in terms of predetermined object "primitives" (such as rectangles, circles and lines) whose parameters may be constants, variables, functions, or parameters of other objects. The invention provides unique grouping, indexing, listing and logic functions that allow individual objects or groups of objects to be defined or constrained by the defining functions of other objects or groups of objects or by constants, variables and other functions. Arguments of the functions provided by the present invention may include single valued and "list valued" variables (a "list valued" variable is a variable that may assume, in a predetermined order, one of a series of values specified in a "list").

One application of the present invention is for creating graphs and charts of spreadsheet data. The invention allows the creation of a large variety of graphs and charts without the need for a special hard coded "driver" for each type of graph. Sophisticated, three dimensional, multi-level charts can be easily created by using the listing, grouping and indexing features of the present invention. Because of the ease of use provided by the present invention, a user is not limited to a fixed number of types of graphs provided by the spreadsheet. Using the system of the present invention, a user can easily create additional chart types or modify existing chart types.

In addition to being useful for generating charts from spreadsheet cell data, the present invention may also be used for other applications that involve the layout of graphic objects. Examples include architectural and engineering design, publishing and page layout, and graphic design.

FIG. 1 illustrates a typical spreadsheet of the prior art.

FIG. 2 illustrates a first type of bar chart created using the data entries of the spreadsheet of FIG. 1.

FIG. 3 illustrates a second type of bar chart created using the data entries of the spreadsheet of FIG. 1.

FIG. 4 illustrates a bar chart consisting of two side-by-side rectangular bars.

FIG. 5 illustrates a first bar chart created using the method of the present invention.

FIG. 6 illustrates a second bar chart created using the method of the present invention.

FIG. 7 illustrates a third bar chart created using the method of the present invention.

FIG. 8 is a block diagram of one embodiment of the apparatus used to implement the present invention.

FIG. 9 is a flow chart illustrating the operation of one embodiment of the present invention.

FIG. 10 is a flow chart illustrating the operation of a further embodiment of the present invention.

A constraint based graphic layout system is presented. In the following description, numerous specific details, such as function names, index labels, etc., are set forth in detail in order to provide a thorough description of the present invention. It will be apparent, however, to one skilled in the art, that the present invention may be practiced without these specific details. In other instances, well known features have not been described in detail so as not to obscure the present invention.

A "constraint based graphics system" is a system in which graphic objects are defined in terms of attributes of other graphic objects, and in terms of variables and constants. In conventional graphics systems each graphic object is defined independently.

For example, to draw an object such as a rectangle using a conventional computer graphics program, the coordinates of the lower left and upper right hand corners of the rectangle must be specified. These coordinates, along with an identifier identifying the object to be drawn as a rectangle, are sent to a drawing subsystem or "engine". For example, an instruction sent to the drawing engine may be "Draw Rectangle (10, 10; 100, 125)". This instruction tells the drawing engine to draw a rectangle having a lower left hand corner at the coordinates "10, 10" and an upper right hand corner at the coordinates "100, 125". The coordinate values generally have to be specified as constants in order for the rectangle to be drawn. To draw two rectangles side by side (as, for example, the first two vertical bars of the bar chart shown in FIG. 2), the coordinates of the lower left and upper right corners for each rectangle must be defined separately.

In a constraint based system, an object is defined in relation to other objects, functions, variables and attributes (an "object" as that term is used herein may be a graphical object, a variable, a group, a function, or an attribute). For example, a rectangle may be defined by a function "RECT (x1,y1; x2,y2)", with one difference from the conventional graphics system described above being that the x and y coordinates in the argument need not be constants. Instead, they can be specified in terms of other objects, other functions and other variables. For example, to define two equally-sized side by side rectangles (or "bars", as in bars of a bar chart), the following notation, which is in the form of a "constraint hierarchy", can be used:

(1)(a) width=a

(b) height=b

(c) space=c

(d) x1=x0

(e) y1=y0

(f) bar1=RECT(x1,y1; x1+width, y1+height)

(g) bar2=RECT(x1+width+space, y1; x1+2*width+space, y1+height)

The two "bars" defined by this hierarchy are shown in FIG. 4.

The advantage of a constraint based system arises when multiple copies of similar objects are drawn. The above notation can be used for rectangles of any size spaced any arbitrary spacing apart simply by specifying different values for x0, y0, a, b and c.

The present invention adds several unique features to the constraint based graphic system described above. These features include (a) listing and series functions that allow variables to be defined in terms of series or lists of other variables or functions; (b) logical and statistical functions that select attributes, functions, constants or variables, according to Boolean criteria, from a list or group of attributes, functions, constants or variables; (c) index variables that relate to particular "instances" of an object, function, variable or attribute that exists in multiple instances, and (d) a hierarchical grouping and indexing notation that allows any object, attribute, function or variable in the hierarchy to be addressed by the defining function of any other object, attribute or variable in the hierarchy. These features are discussed by way of illustrative examples below. However, it will be apparent to those skilled in the art that the invention is not limited to these specific examples.

Series and Listing Functions

The present invention provides series and listing functions that allow (a) variables to be defined in terms of series or lists of other variables or functions, and (b) series or lists to be created from formulas and indexes. Examples of these functions are a "SERIES" function and an "ENUM" function provided by one embodiment of the invention.

The SERIES function is used to define a series of variables from a list of variables, constants or functions. Referring to the spreadsheet example of FIG. 1, the SERIES function can be used to define a variable "sales.sub.-- n" (representing the sales of the North region) by the expression:

This expression defines three "instances" of the variable "sales.sub.-- n" (an "instance" is a particular example of a variable or object that has multiple embodiments, as for example, a list valued variable). One instance is defined to be the number "19,800", and the second and third instances are defined to be the numbers "26,750" and "34,580", respectively. The present invention provides an indexing system that assigns consecutive integer values to consecutive instances of functions, variables and objects that exist in multiple instances. For example, the initial instance of "sales.sub.-- n" (which is defined by equation (2) as the number "19,800") may be designated the "zeroth" instance of the variable "sales.sub.-- n", which may be written "sales.sub.-- n[0]". The next two instances (which are defined in equation (2) as being equal to the numbers 26,750 and 34,580, respectively) are accordingly designated "sales.sub.-- n[1]" and "sales.sub.-- n[2]". In other embodiments, a different integer may be used for the initial instance. For example, the integer "1" may be used instead of the integer "0". If this convention is used, the three instances of "sales.sub.-- n" would be designated "sales.sub.-- n[1]", "sales.sub.-- n[2]" and "sales.sub.-- n[3]".

Variables representing sales in the other regions can be defined in a similar manner. For example, the following expressions may be used:

The argument of the function SERIES may contain variables, functions, objects and attributes of objects in addition to text strings and numerical constants as used in the above examples.

The ENUM function generates a series from an expression. For example, the expression:

generates a series of three values for (or "instances" of) the variable "total". The ENUM function evaluates the argument (that is the content of the parentheses that immediately follow "ENUM") the number of times specified by the integer that immediately follows the parentheses. The general expression used for ENUM is:

where "n" specifies the number of instances of the variable that are being defined.

In the example of equation (6), n is "3". The argument is therefore evaluated three times. The argument in equation (6) consists of the expression "sales.sub.-- n[@]+sales.sub.-- s[@]+sales.sub.-- e[@]+sales.sub.-- w[@]". The "@" character used in this expression is an index acts as a counter for the instance of the function ENUM that is being evaluated. "@" is equal to 0 for the first time the argument of the ENUM function is evaluated. "@" is equal to 1 for the second time the argument of the ENUM function is evaluated. It is incremented by one each time the argument is evaluated.

Equation (6) is evaluated three times. Accordingly, in equation (6), @ takes on the values of 0, 1 and 2. The resulting definitions for the three instances of "total" defined by equation (6) are:

"Total[0]" represents the total sales for 1988, "total[1]" the total sales for 1989, and "total[2]" the total sales for 1990.

Logical and Statistical Functions

The present invention provides logical and statistical functions that select attributes, functions, constants or variables, according to Boolean criteria, from a list or group of attributes, functions, constants or variables. Examples of the logical and statistical functions provided by the present invention include "MAX", "MIN" and "COUNT" functions. The functions provided by the present invention can be used with both single valued and list valued variables.

The "MAX" function of the present invention returns the maximum value of the "MAX" function's argument. For example:

assigns to the variable "ymax" the maximum value of the expression "ENUM(total[@]), 3". As explained above, "ENUM(total[@]), 3" defines the series "total[0]", "total[1]" and "total[2]", which represent the total sales in 1988, 1989 and 1990, respectively. The maximum of these three values will be the maximum yearly sales total over this three year period. This maximum value is defined to be "ymax". Equation (9) may alternatively be written as:

In this case, "total" is recognized as a list valued variable, and the MAX function returns the maximum of the values in the list.

The MIN function operates like the MAX function, except that it returns the minimum value of the elements in the argument.

The general expressions used for the MAX and MIN function are:

The argument for both the MAX and MIN functions can contain both single-valued and list-valued elements. For example, the expression:

returns the value "ymin=0".

The COUNT function returns an integer value equal to the number of individual instances of the list valued variable or series specified in the argument. For example, using the results of equation (6) above, the expression:

assigns a value of "3" to the variable "n". As discussed above, there are three instances of the variable "total", namely "total[0]", "total[1]" and "total[2]". The general expression used for the COUNT function is:

Object and Variable Groups

The present invention provides a system of interrelated "groups" of variables and/or objects, and a unique method for identifying particular members of groups. The expression defining a group takes the general form:

where "N" (which may be a constant or an expression) is the number of instances of the group that are being defined, and the variable, object and/or group definitions are arranged in the form of a constraint hierarchy.

In addition to providing a method for defining a group, the present invention provides a method for identifying particular instances of variables, objects, and/or attributes of objects and/or variables and for using these particular instances to define or constrain other variables, objects and/or attributes. The general forms used in one embodiment of the invention for such identifying particular instances of variables, objects, and attributes include the following:

* indicates that the index is optional if not applicable

Equation (14) identifies a particular instance of an attribute of an object that is contained in the constraint hierarchy for a particular group. Equation (15) identifies a particular instance of a variable within a constraint hierarchy for a particular group, and equation (16) identifies a particular instance of an attribute in a constraint hierarchy for a particular group. The operation of the constraint hierarchy of the present invention is explained in greater detail in the examples below.

Index Variables

The present invention provides index variables that relate to a particular object or group or ENUM function (which may be referred to as the "source" for the index variable). An index variable takes on consecutive integer values corresponding to particular instances of the source.

In one embodiment of the present invention, an index variable is identified by the character "@". The source for the "@" index variable can be an ENUM function, object, or group.

An example of the use of an index variable of the present invention with an ENUM function is illustrated in equation (6) above. Equation (6) is as follows:

The numeral "3" at the end of equation (6) indicates that the argument of the ENUM function is to be evaluated three times, thereby defining three instances of the variable "total". The "@" index variable indicates which instance of the variables "sales.sub.-- n", "sales.sub.-- s", "sales.sub.-- e" and "sales.sub.-- w" are to be used each time the argument of the ENUM function is evaluated. As explained above, the first time the argument of the ENUM function is evaluated (which defines the first instance of the variable "total"), "@" is equal to zero. Accordingly, the result for the first evaluation of equation (6) is:

The second time the ENUM function is evaluated, "@" is equal to 1, and the third time, "@" is equal to 2.

In equation (6) it is implicit that the source for index variable "@" is the ENUM function. In more complex expressions, it may be unclear to which source an index variable relates, or index variables relating to different sources may be used. In that case, it is necessary to specify the source for each index variable used. The convention used in one embodiment of the present invention to designate the source of an index variable is to write the name of the source directly after the index variable.

An index variable having a group or object as a source operates in a similar manner to an index variable that has an ENUM function as its source. For example, an index variable of the present invention may be used to simplify and generalize the notation for specifying the two side by side rectangles of constraint hierarchy (1) above. Instead of using separate expressions for the objects "bar1" and "bar2", the following single expression can be used:

Equation (18) is an example of the group definition method of equation (13) above. It has the general form:

"[N]" specifies the number of instances of the group (group here means one or more than one object) that are being defined by the equation or equations contained in the brackets. "@group" is an index variable that is related to the source "group". In this example, the convention that is followed is that the value of the index variable is initially zero. In equation (18), N=2, indicating that 2 instances of the object "bars" are being defined. For the first instance, the index variable "@bars" is equal to zero, and for the second, "@bars" is equal to "1". Accordingly, the expression for the first instance of "bars" that results from equation (18) is:

This expression, except for the notational format used, is equivalent to equation (1)(f).

For the second instance of the variable "bars" the index variable "@bars" is incremented by 1, and is therefore equal to 1. The expression for the second instance of the variable "bars" becomes:

Except for the specific notation used, this expression is equivalent to equation (1)(g).

The following examples illustrate uses of the method of the present invention in creating various constraint hierarchies that may be used for creating graphic layouts.

The following constraint hierarchy uses the methods provided by the present invention to define a simple bar chart for a variable that has data values of 10, 20, and 15, respectively (that is, a chart having three bars whose heights are 10, 20 and 15, respectively). This bar chart is shown in FIG. 5.

Equations (22)(a), (22)(b) and (22)(c) set the values of the variables "space", "width" and "ystart". "Space", which represents the measurement of the space between each bar and the space between the left edge of the chart and the first bar, is set equal to 10 units. "Width", which represents the width of each bar, is set equal to 15 units. "Ystart", which represents the vertical height of the base of each bar, is set equal to 0 units.

Equation (22)(d) defines the list valued variable "height" which represents the heights of the bars. Equation (22)(d) defines three instances of the variable "height". These three instances, which may be written as "height[0]", "height[1]" and "height[2]", are set equal to 10, 20 and 15, respectively.

Equation (22)(e) uses the group definition method of the present invention to define the bars for the bar chart. The general form of equation (22)(e) is:

where N=the number of "bars"; x1, x2, y1, and y2 are the horizontal and vertical bounds, respectively of the rectangles representing each of the bars; and f1, f2, f3 and f4 are expressions or functions that specify those bounds.

For the above example, N is defined to be equal to "COUNT (height)", which is equal to the number instances that exist of the list-valued variable "height". Equation (22)(d) specifies three instances of the variable "height", equal to the three values 10, 20 and 15, respectively. N therefore is equal to "3".

In equation (22)(e), x1 is defined as being equal to "space+(space+width)*@(bars)". As described above, "@bars" is an index variable whose value is dependent on the specific instance of the expression for "bar" that is being evaluated. As described above, this index variable starts at "0", and is incremented by 1 each time the expression for "bars" is evaluated. Its maximum value is "N-1". In this example, "N"=3. Accordingly, "@bar" will have the values 0, 1, and 2

The following values for x1, y1, x2 and y2 result from the above expression for bars:

First bar "bars[0]" (@bars=0)

Second bar "bars[1]" (@bars=1)

Third bar "bars[2]" (@bars=2)

The resulting bar chart is shown in FIG. 5.

The same expression for "bars" used in equation (22)(e) can generally be used for any list of values. By replacing equation (22)(d) with a different list, a bar chart having different numbers and heights of bars will result. For example, replacing equation (22)(d) with the expression:

results in a bar chart having 8 bars whose relative heights are 5, 12, 10, 16, 23, 13, 26 and 32, respectively.

In a more general application of equation (22), the width and space values can be made to depend on the number of bars and the width of the paper, or display screen.

The following constraint hierarchy, constructed using the methods of the present invention, creates the stacked bar chart shown in FIG. 6. The chart is intended to be displayed on a VGA computer monitor having a resolution of 640 by 480 pixels. The unit of measure used is numbers of pixels.

Equation (35) is the constraint hierarchy that defines the layout of the graphic elements that make up the chart. Equations (25) to (34) assign values to the variables used in equation (35).

Equation (25) sets the variable "maxwidth" to be equal to 640. "Maxwidth" represents the maximum available display width, and therefore the maximum allowable width of the graph.

Equation (26) sets the variable "maxheight" to be equal to 480. "Maxheight" represents the maximum available display height, and therefore the maximum allowable height of the graph.

Equation (27) sets the variable "space2bar" to be equal to 0.25. "Space2bar" represents the ratio of the width of the space between adjacent bars on the bar chart to the width a bar.

Equations (28) to (30) set the values of list valued variables "yvalues1", "yvalues2" and "yvalues3", respectively, to the series of values specified. "Yvalues1" represents the height of the bottom tier of the stacked bars, "yvalues2" the middle tier, and "yvalues3" the top tier. Each series of values may be obtained, for example, from a row of cells in a selected range of cells of a spreadsheet.

Equation (31) determines the maximum number of instances of any of the list valued variables "yvalues1", "yvalues2" and "yvalues3", and sets a variable "n" equal to such maximum number. "n" represents the number of stacked bars that will be displayed. Since each of the "yvalues" variables have eight instances in the present example, "n"=8.

Equation (32) determines the maximum height of the stacked bars that will be displayed by comparing the sum of "yvalues1" plus "yvalues2" plus "yvalues3" for each instance of these variables. Because there are eight instances of each of these values, there are eight sums. Using the data in equations (28) to (30), these sums are equal to 349, 354, 202, 386, 202, 155, 379 and 412, respectively. The maximum value is 412. Accordingly, equation (32) sets the variable "ymax" equal to 412.

Equation (33) sets the value of "barwidth" (the width of each bar) to be equal to "maxwidth/(n+((n+1) * space2bar))". Using the values specified above, "barwidth" is set equal to 640/(8+(9 * 0.25) or 62.43. For the purposes of this example, this number will be rounded off to the number "60", which represents the width of each bar.

Equation (34) sets the value of "spacewidth", the size of the space between each bar, to be equal to "barwidth * space2bar". Using the values of this example, "spacewidth" is equal to 60 * 0.25, or 15.

Equation (35) is a constraint hierarchy that uses the group definition method of the present invention to create the graphic layout that comprises the graph shown in FIG. 6.

Equation (35) is in the general form of equation (13), namely: "groupname={one or more variable, object or group definitions}[N ]". Here, the "groupname" is "bars", "N" is "n" or eight, and the "variable, object and group definitions" are represented by equations (35)(a) to (35)(q). Equations (35)(a) to (35)(q) define three rectangles called "bars1", "bars2" and "bars3", which represent the bottom, middle, and top tier of each stacked bar, respectively. Equations (35)(a) to (35)(q) are evaluated "n" times. Since "n" was calculated to be equal to 8, equations (35)(a) to (35)(q) are evaluated eight times, thus defining the eight stacked bars of the graph. Equation (35) thus provides a concise means of defining the eight groups of stacked rectangles that comprise the bar chart of FIG. 6.

The index variable "@bars" is used to track the instance of group "bars" that is being evaluated. In this example, the convention used is that the index variable "@bars" starts at zero and is incremented by 1 up to and including n-1. Each value of "@bars" will result in a different stacked bar. The first time equations (35)(a) to (35)(q) are evaluated, the index variable "@bars" is equal to zero. This instance of the group "bars" results in the first stacked bar defined by the constraint hierarchy of equation (35). The second time equations (35)(a) to (35)(q) are evaluated, the index variable "@bars" is equal to one, and the second stacked bar is defined. Equations (35)(a) to (35)(q) are evaluated a total of eight times, defining eight stacked bars. The eighth and last time equations (35)(a) to (35)(q) are evaluated, "@bars" is equal to seven.

Either a "top down" or "bottom up" order may be used to evaluate the constraint hierarchy of equation (35). If a "top down" order is used, equation (35)(a) is evaluated first, then (35)(b), (35)(c), and so on. If an equation cannot be evaluated in this sequential order because one of its parameters or variables has not yet been determined, that equation is skipped for the time being and re-evaluated once the missing quantity has been determined. If a "bottom up" order is used, the same general procedure is followed, but the constraint hierarchy is evaluated beginning with equation (35)(q). The evaluation of equation (35) is described below using a "top down" order, but the same general methods are used with a "bottom up" evaluation order.

As described above, for the first instance of the group "bars" (i.e. for the first stacked bar), the index variable "@bars" is equal to zero. Evaluating equation (35)(a) with "@bars" equal to zero, and substituting the values calculated for the relevant variables in equations (25) to (34) yields the following value for x1:

Evaluating equation (35)(b) in a similar fashion yields the following value for x2:

The values for x1 and x2 calculated in equations (35)(a)(0) and (35)(b)(0), respectively, are the values of x1 and x2 for the "zeroth" instance of the group "bars". Using the notation of equation (15) above, these values of x1 and x2 may be written as follows:

Expression (36) means "the value of the variable x1 in the zeroth instance of the group `bars`". Similarly, expression (37) means "the value of the variable x2 in the zeroth instance of the group `bars`".

The next equations in the hierarchy, equations (35)(c) to (35)(s), define the zeroth instance of the object "bars3". "Bars3" is defined as a rectangle ("RECT") having horizontal and vertical bounds x1, x2, y1 and y2 as defined by the expressions contained in the equations. x1 is defined in equation (35)(c) to be equal to "bars[@bars].x1". For this initial instance of "bars", "@bars" is equal to zero. Accordingly, "bars[@bars].x1"becomes "bars[0].x1", or "the value of x1 in the zeroth instance of the group `bars`". This is the value for x1 that was calculated in equation (35)(a)(0) above. Accordingly, x1 in equation (35)(c) is in this instance equal to 15. Similarly, equation (35)(d) defines x2 to be equal to "bars[@bars].x2", or, since "@bars" in this instance is equal to zero, "bars[0].x2". This value for "the value of x2 in the zeroth instance of the group `bars`" was calculated in equation (35)(b)(0) to be equal to 75.

Equation (35)(e) defines the value of y1 for bars3 to be equal to "bars2[@bars].y2". In other words the value of y1 for bars3 (the bottom of the third stacked bar) is equal to y2 for bars2 (the top of the second bar). The value for y2 for bars2 is not defined until equation (35)(k). Equation (35)(e) cannot yet be evaluated. Accordingly, evaluation of equation (35)(e) must be deferred until equation (35)(k) has been evaluated.

The value of y1 defined by equation (35)(e) is needed to calculate the value of y2 defined by equation (35)(f). Since evaluation of equation (35)(e) is deferred, evaluation of equation (35)(f) must also be deferred.

Equation (35)(g) sets the edge pattern and the fill color for the rectangles "bars3". In this example, there are a predetermined number of predefined edge patterns, each of which is designated by a different integer. These edge patterns include solid lines of various thicknesses and colors, dotted lines, shaded lines, etc. The edge pattern specified in equation (35)(g) is edge pattern number "15", which in this example represent a solid black line two pixels in width.

The fill color for "bars3" is set in equation (35)(g) by specifying the amount of red, green and blue shading using the expression "RGB(p,q,r)" where "p", "q", and "r" are the amounts of red, green and blue, respectively. In the current example, p, q, and r can have values between 0 and 255, with 255 the maximum level of color. Equation (35)(g) specified values of 0, 0, and 255 for each of the colors red, green and blue, respectively. The fill color is therefore blue.

The next equations in the hierarchy, equations (35)(h) to (35)(l), define the zeroth instance of the object "bars2" in the same manner that equations (35)(c) to (35)(g) defined the zeroth instance of the object "bars3". "Bars2" is defined as a rectangle ("RECT") having the diagonal corner coordinates x1, y1 and x2, y2 as defined by the expressions contained in the equations. x1 is defined in equation (35)(g) to be equal to "bars[@bars].x1". As shown with respect to equation (35)(c), above, this value is equal to 15. Similarly, equation (35)(h) defines x2 to be equal to "bars[@bars].x2". As shown above, this value is equal to 75.

Equation (35)(j) defines the value of y1 for bar2 to be equal to "bars1[@bars].y2". In other words the value of y1 for bars2 (the bottom of the second stacked bar) is equal to y2 for bars1 (the top of the first bar). The value for y2 for bars1, however, is not defined until equation (35)(p). Equation (35)(j) cannot yet be evaluated. Accordingly, evaluation of equation (35)(j) must be deferred until equation (35)(p) has been evaluated.

The value of y1 defined by equation (35)(j) is needed to calculate the value of y2 defined by equation (35)(k). Since evaluation of equation (35)(j) is deferred, evaluation of equation (35)(k) is also deferred.

Equation (35)(l) sets the edge pattern and fill color of bars2 in the same manner that equation (35)(g) sets the edge pattern and fill color of bars3. The edge pattern specified is the same as that specified in equation (35)(g). The fill color specified is "RGB(255, 255, 0)", which represents the color yellow.

Finally, equations (35)(m) to (35)(q) define the bottom tier of bars for the three-tiered stacked bars of FIG. 6. Like equations (35)(c) and (35)(d), and equations (35)(h) and (35)(i), equations (35)(m) and (35)(n) define x1 and x2 to be equal to "bars[@bars].x1" and "bars[@bars].x2", respectively. Since the bars are stacked directly on top of one another, the horizontal limits are the same for each bar. Equation (35)(o) sets y1 for bars1 (the bottom of the three-tiered stack) to be equal to zero.

Equation (35)(p) defines the top limit of the bottom tier. The equation defines y2 to be equal to "yvalues1[@bars]*(maxheight-10)/ymax". "yvalues1[@bars]" is the instance of the series "yvalues1" (defined in equation (28)) that corresponds to the current value of the index variable "@bars". "(maxheight-10)/ymax" is a scale factor that is a constant for a particular graph. For this example, this scale factor is equal to (480-10)/412 or approximately 1.14. For the first bar, where "@bars" is equal to zero, "yvalues1[0]" equals 142. Accordingly, y2 equals 142*1.14 or approximately 162.

Equation (35)(q) sets the edge pattern and fill color of bars2 in the same manner that equation (35)(g) and (35)(l) set the edge pattern and fill color of bars3 and bars2, respectively. The edge pattern specified is the same as that specified in equations (35)(g) and (35)(l). The fill color specified is "RGB(255, 0, 0)", which represents the color red.

Once the value of "bars1[@bars].y2" has been determined according to equation (35)(p), equations (35)(j), (35)(k), (35)(e) and (35)(f), evaluation of which was deferred, can be evaluated. Equation (35)(j) defines y1 for bars2 to be equal to y2 for bars1. For "@bars" equal to zero, y2 for bars1 has been shown to be equal to 162. Equation (35)(k) defines y2 for bars2 to be equal to ((yvalues2[@bars]*maxheight-10))/ymax)+y1. For "@bars" equal to zero, "yvalues2[@bars]" is the first value in the series "yvalues2" of equation (29), namely 142. As shown in the preceding paragraph, "(maxheight-10)/ymax)" equals approximately 1.14, and y1, according to equation (35)(j) is 162. Accordingly, y2 is equal to 142*1.14+162 or approximately 324. Thus, y1 and y2 for the first instance of bars2 are equal to 162 and 324, respectively.

In a similar manner, equation (35)(e) defines y1 for bars1 to be equal to y2 for bars2. For "@bars" equal to zero, y1 for bars1 equals 324. Equation (35)(f) defines y2 for bars3 to be equal to ((yvalues3[@bars]*maxheight-10))/ymax)+y1. For "@bars" equal to zero, "yvalues3[@bars]" is the first value in the series "yvalues3" of equation (30), namely 65. As shown above, "(maxheight-10)/ymax)" equals approximately 1.14, and y1, according to equation (35)(e) is 324. Accordingly, y2 is equal to 65*1.14+324 or approximately 398. Thus, y1 and y2 for the first instance of bars3 are equal to 324 and 398, respectively.

In summary, equations (35)(a) to (35)(q) define the 3 bars making up the first stacked bar of the bar chart of FIG. 6 as follows:

This first stacked bar is shown in FIG. 7.

According to the method of the present invention, after equations (35)(a) to (35)(q) have been evaluated for "@bars" equal to zero, "@bars" is incremented by 1, and equations (35)(a) to (35)(q) are evaluated again with "@bars" being equal to one. The second stacked bar of FIG. 6 is thereby created. "@bars" is incremented again, and the process continues until equations (35)(a) to (35)(q) have been evaluated for values of "@bars" from 0 to N-1, or in this example, from 0 to 7. The resulting values for x1, x2, y1 and y2 for bars1, bars2 and bars3 are listed on Table 1.

Finally, equation (35)(s) creates a rectangle for the background of the bar chart. The edge pattern is again specified to be type "15". The fill color is "RGB(192, 192, 192)", which represents the color grey.

As this example shows, the present invention allows a sophisticated stacked bar chart to be created using a very concise set of commands. The constraint hierarchy of equations (25) to (35) creates a three tiered bar chart for any three series of values supplied in equations (28) to (30). The height, width and spacing of the bars is automatically adjusted to fit within the designated display area. Furthermore, by making relatively minor changes to equations (25) to (35), the same constraint hierarchy structure can be used to create a variety of other types of charts. For example, additional tiers may be added by defining additional "yvalues" series such as equations (28) to (30) and additional "barsn" objects as in equations (35)(c) to (35)(g). The arrangement of the three tiers of bars can also be easily changed. For example, a grouped side-by-side bar chart of the type shown in FIG. 2, instead of the stacked-bar chart of FIG. 6, can be created by making the following changes to equations (32), (33) and (35) (with all equations not listed below remaining the same):

Evaluating these modified equations in the same manner as described for the original equations results in the bar chart shown in FIG. 7.

Comparing the bar chart of FIG. 7 to the bar chart of FIG. 6 shows that the modifications indicated in equations (32)* to (35)* above have changed the size and shape of the individual rectangles or bars representing the individual data points, and rearranged them into new positions. The method of the present invention thus allows the position, size and shape of the objects being displayed to be easily reshaped and rearranged, while maintaining interrelations between the size, shape, and position of each. The present invention allows the size, shape and location of a displayed object to be so constrained by the size shape and location of other objects through the use of its novel functions, index variables and group definition system.

The constraint hierarchies illustrated in examples A and B, that is the hierarchies represented by equations (22)(e) and (35), respectively, each contain only one index variable, namely "@bars", that is associated with the group "bars". More complex constraint hierarchies may use multiple tiers of groups, each having an associated index variable, with lower tiers embedded in the higher tiers. Equations (41) to (44) below create a simple constraint hierarchy that consists of three tiers of groups. These groups are designated groups "a", "b" and "c". The associated index variables are "@a," "@b" and "@c", respectively.

Equations (41), (42) and (43), respectively, define the values of N1, N2 and N3. Equations (44)(j), (44)(k), and (44)(l) assign N1, N2 and N3 to be the "numerators" for groups a, b and c, respectively. The term "numerator" as used here indicates the number of instances the corresponding group will have, and, accordingly, the number of values that the index variable will take. For example, Equation (41) sets the value of N1 at 2, and equation (44)(l) designates N1 as the numerator for group "a" (group "a" consists of equations (44)(a) to (44)(l)). Since N1 equals 2, index variable @a will have two possible values: 0 and 1. In a similar fashion, the numerator for group b is set equal to 2 by equations (42) and (44)(k), and the numerator for group c is set equal to INT((2+2)/2) or 2 by equations (43) and (44)(j). (Although the numerator may be a variable or expression, as shown by equation (43), its value must always be an integer. Hence the "INT" function is used, which rounds off the value in the argument to the next lowest integer value.)

Since the numerator for group b is two, and since group b, represented by equations (44)(b) to (44)(k), is imbedded in group a, there will be two instances of group b for each instance of group a. Since there are two instances of group a, there will be total of four instances of group b (two for each instance of group a). Accordingly, there will also be four instances of each of attributes "bx1" and "bx2" of group b, which are defined by equations (44)(c) and (44)(d).

In a similar manner, there are two instances of the group c for every instance of group b, or a total of eight instances of group c. Accordingly, there are also eight instances of the attributes x1, x2, y1, and y2 defined by equations (44)(f) to (44)(g), respectively. Using the notation of the present invention described in equations (14) to (16) above, the eight instances of the attribute x1, for example, may be referred to as:

One way to evaluate the constraint hierarchy of equations (44)(a) to (44)(l) is to evaluate equations (44)(c), (44)(d), (44)(f), (44)(g), (44)(h) and (44)(i) for each of the eight instances of group c. The resulting values for the variables bx1, bx2, x1, x2, y1 and y2 are listed on Table 2 below.

Looking at Table 2, it can be seen that not all the variables change for each instance of group c. For example, bx1, x1 and y2 stay the same for instances 1 to 4 (indicated by the first column of Table 2), and variables bx2 and x2 only change when index variable @b changes. Although the hierarchy of equations (44)(a) to (44)(i) is only one example, in many constraint hierarchies used in practice a similar sort of redundancy will occur.

The present invention includes a method for eliminating redundancies like the ones shown in Table 2, thereby improving the speed at which the method of the present invention can be applied. The present invention does so by starting with the lower most tier of the hierarchy, determining which variables are actually desired, determining how the variables in the lower most tier depend on index variables higher in the constraint hierarchy, constructing a relationship "tree" between the indexes in the constraint hierarchy and the variable being determined, and calculating the value of the desired variable according to the relationship described in the tree. If the required relationship tree or a required variable value has already been determined, it need not be recalculated, but may be retrieved from a table of already calculated values.

For example, the first variable that needs to be calculated in the hierarchy of equations (44)(a) to (44)(l) is a[0].b[0].c[0].x1. X1 is defined by equation (44)(f) to be equal to b[@b].bx1, which, in this instance is equal to b[0].bx1. Therefore, the value of bx1 for the zeroth instance of the variable bx1 is required to determine the value of a[0].b[0].c[0].x1. The first step followed by the present invention is to determine whether the relationship tree for this variable already has been determined. If the relationship tree has already been determined and stored in a data table, then the relationship tree is inspected to see whether the value of the variable itself has also been determined and stored in the data table. If the relationship tree is in the table but the desired value of the variable has not yet been calculated, then the variable is calculated according to the relationship tree. If the relationship tree also has not yet been determined, it must be created.

Since in the current example no relationship tree between the variable bx1 and the indexes in the hierarchy has yet been determined, there is no such tree in the data table. This relationship tree is therefore determined. To construct this relationship, the first (that is, the highest level) index variable is inspected to determine whether value of the desired variable, in this case the variable bx1, depends on that index. The highest tiered index in the present example is "@a". Equation (44)(c) sets bx1 equal to "@a". Bx1 therefore is dependent on @a. This relationship is noted in the data table. Since there are two possible values of @a, in addition, two data slots are created for the variable bx1 at the "a" tier level. Next, the next tier in the hierarchy, in this case the "b" tier, is inspected to determine whether the value of bx1 is dependant on "b" tier index variable @b. No relationship is specified in equations (44)(a) to (44)(l) between @b and bx1. Accordingly, no slots in the relationship tree are specified at the b level. Finally, the last tier, the "c" tier is inspected for any relationship between bx1 and @c. No such dependency is specified. Accordingly, the relationship tree specifies that bx1 is dependant on only ga. Since there are only two possible values of @a, there are also only two possible values of bx1: one value for @a=0, and one for @a=1. The two slots established for bx1 in the data table at the a tier level are for these two values of bx1.

Once the relationship tree between bx1 and @a, @b and @c is established, it can be used to calculate the currently desired value of bx1. Bx1 is only dependent on @a, and in the present instance @a is equal to zero. The value of "0" is therefore stored in the data table as the value of bx1 for @a equal to 0.

Continuing with the evaluation of the first instance of group c (i.e. a[0].b[0].c[0]), equation (44)(g) is evaluated to determine the value of x2. Equation (44)(g) defines x2 to be equal to b[@b].bx2. Accordingly, the data table is checked to see whether there is a relationship tree between bx2 and the indexes @a, @b and @c. Since none has yet been specified, it must be determined. Following the procedure described above, the hierarchy is checked for any relationship between @a and bx2. There is none, so the next index, @b is inspected. Equation (44)(d) establishes such a relationship. It specifies that bx2 =@b. That relationship is noted in the relationship tree, and since @b has two possible values, two slots are established for the resulting two possible values of bx2.

Equations (44)(h) and (44)(i) set the variables y1 and y2 to be equal to the current values of index variables @c and @a. Since no other variable values are needed to determine the values of y1 and y2, no relationship tree is needed.

After the values of x1, x2, y1 and y2 have been determined for the first instance of group c, they are determined for the next instance of group c, namely a[0].b[0].c[1]. To determine the value of a[0].b[0].c[1].x1, the value of b[@b].bx1 must be retrieved or calculated. The data table is inspected to see whether there is a relationship tree for bx1. Such a relationship tree now exists, and it specifies that bx1 depends only on @a. @a is currently equal to 0. The data table is inspected to see whether the value of bx1 for @a equals 0 has already been calculated. Since it has been calculated, it is simply retrieved. The steps of establishing the relationship tree and calculating the value of bx1 needed to determine the current value of x1 therefore need not be repeated. In a similar manner, the current value of bx2, needed to calculate the current value of x2, can also simply be retrieved from the data table, since bx2 is dependent only on @b, and @b is still equal to 0.

For the next instance of group c, a[0].b[1].c[0], the value of @b has changed to 1. Again, the value of bx1 needed to calculate x1 can simply be retrieved from the table. To calculate the value of x2 for this instance of group c, however, the current value of the variable bx2 is needed, as specified in equation (44)(f). The data table already contains the relationship tree for bx2, but the slot for bx2 for @b=1 is not yet filled. This value of bx2 is therefore calculated, and stored in that empty slot.

For the next instance of group c, the required values of bx1 and bx2 needed to calculate x1 and x2 already are in the data table and can be simply retrieved. But for the fifth instance, a[1].b[0].c[1], the value of bx1 for @a needs to be calculated. The relationship tree already stored for bx1 is used to calculate the value of bx1 for @a=1, and that value is stored in the table.

For the remaining three instances of c, the required values of bx1 and bx2 are already in the table, and they can simply be retrieved from the table.

Accordingly, the value of bx1 and bx2 are each calculated only two times using the compression scheme of the present invention described above. That compares very favorably to the eight times each that these variables were evaluated using the "brute force" method described above with respect to Table 2.

The same general procedure described above can be used for any constraint hierarchy of any complexity, with resulting processing efficiencies.

FIG. 8 shows one embodiment apparatus that may be used to implement the methods of the present invention. This apparatus may comprise discrete hardware components or may be implemented in a general purpose computer by appropriate software commands. In one embodiment of the invention, the apparatus used is implemented by a software program compiled in an object oriented programming language such as "C++". This software program is preferably run on a pen-based computer using a pen-based operation system such as PenPoint from GO Corporation or Windows for Pen from Microsoft Corporation. The computer preferably uses an Intel 80386 CPU and features a VGA mono LCD display.

The central element of the apparatus shown in FIG. 8 is a data processor 830. Data processor 830 reads and carries out instructions obtained from instruction set 800. The instructions contained in instruction set 800 may be provided by a user, may be supplied by an application program, or may be a combination of both. The instructions may include instructions to create source objects from data source 810. For example, the data source may be a spreadsheet and an instruction may direct data processor 830 to create multiple instances of a source object from data contained in the spreadsheet. The resulting source objects may be stored in object storage means 850, which may be a portion of random access memory of a computer. The instructions contained in instruction set 800 may also direct data processor 830 to create a target object (for example a graphical object) by applying functions contained in function set 820 (which may include functions such as the MAX, ENUM, SERIES, and COUNT functions described above) to data from the data source or objects in object storage means 850. Object storage means 850 may also be used to store relationship trees and corresponding variable slots and values, as described with respect to Example C above. The attributes of the target objects may also be stored in object storage means 850, or may be directly sent to drawing means 860 which displays corresponding images on display means 870. Display means 870 may for example be a display monitor of a computer. The instructions contained in instruction set 800 may define multiple instances of source and target objects. Counter 840 keeps track of the current particular instance of each object existing in multiple instances.

FIG. 9 is a flow chart for one embodiment of the method of the present invention. Source object data, such as spreadsheet cell data, is read at block 900. This raw source object data is divided into separate instances of one or more source objects at block 910. The resulting source objects may for example be the list valued objects such as "yvalues1", "yvalues2", and "yvalues3" defined in equations 28, 29 and 30, above. At block 920, index numbers are assigned to each instance of each source object resulting from the division of data at block 910. At block 930, the expressions are read that define the attributes of each instance of the desired target object, such as a graphical object, in terms of attributes of specific instances of the source objects, and/or in terms of other elements including variables or attributes of other instances of the same or other target objects. These expressions may be in the form of the constraint hierarchy described above. The attributes of the target object are evaluated at block 940, and the resulting graphical object is drawn on a display means at block 950.

FIG. 10 is a flow chart for an embodiment of the present invention incorporating the compression feature described with respect to Example C above. In this embodiment, the constraint hierarchy defining the objects that are to be displayed is read at block 1000. This constraint hierarchy is analyzed at block 1005 and parsed into binary files. The constraint hierarchy will generally contain multi-tiered groups. After the constraint hierarchy has been read and analyzed, external input data is read at block 1010 and evaluation of the constraint hierarchy is begun at block 1015. The convention used in this example is that the lowermost objects in the constraint hierarchy form the bottom layer of the display and are therefore evaluated first. Higher tiered objects are layered on top of already displayed lower tiered layers. In other embodiments of the invention, different conventions may be used.

The first step in evaluating the constraint hierarchy is to determine the variables of the lower most group in the constraint hierarchy that are needed to display any objects specified in that group. The evaluation of these needed variables for the first instance of the first group is begun at block 1020. The variables of other objects that are needed to evaluate the currently needed variables in the current instance of the current group are identified at block 1035. The first required variable is fetched at 1040. To fetch the variable, a data table is first inspected at block 1045 to determine whether a relationship tree for the desired variable has already been created. If the relationship tree is not available, it is created at block 1050 and stored in the data table at block 1052. After the relationship tree has been created, the value of the desired variable is calculated at block 1054, and stored in the data table at block 1056.

If it is determined at block 1045 that the data tree is already available, the data table is inspected at block 1059 to determine whether the desired value of the variable has already been calculated and stored in the data table. If it has not been calculated, it is calculated at block 1058 and stored in the data table at block 1056. If the variable is available at block 1059, or after the variable has been calculated and stored at block 1056, the constraint hierarchy is inspected at block 1060 to determine if any other variables are needed for the current instance of the object to be displayed.

If an additional variable is needed, it is fetched at block 1055, and the analysis of blocks 1045 through 1060 is repeated. If it is determined at block 1060 that no more variables are needed to display the current instance of the current object, the current object is drawn on the display at block 1070.

Next, at block 1075, it is determined whether any further instances of the current group need to be evaluated. If additional instances must be evaluated, the evaluation of the next instance of the current group is initiated at block 1080. The process returns to block 1035 and the steps described above with respect to the first instance of the first group are repeated for the next instance. If there are no more instances of the current group, the hierarchy is checked to see whether there are any other, higher tiered, groups whose variables must be determined. This checking is done at block 1085. If there are such additional groups, the evaluation of the variables of the first instance of such group is begun at block 1090 by once again returning to block 1035. The process described above with respect to the first group is repeated for the next group.

Finally, if it is determined at block 1085 that no other groups need to be evaluated, the process is completed and ends at block 1095.

The method of the present invention can be used to easily and quickly create more sophisticated graphs. Examples include 3-D charts and "icon" charts where the height of an arbitrary icon, rather than a bar, can be used to show the magnitudes of the data values. The present invention can also be used for other layout functions, such as page layout applications, where the size and location of one object is preferably constrained by another. Other uses of the present invention will be apparent to those skilled in the art.

Computer source code for one embodiment of the constraint-based graphics system of the present invention is attached as Appendix A. ##SPC1##