Method and system for processing formatting information in a spreadsheet5231577Abstract A method and system wherein characters in cells of a spreadsheet may be assigned character attribute information, such as font type, font size, bold, italics, underline, etc., wherein the character attribute information is referred to as an extended format. Each possible extended format combination is stored in an extended format table comprising a linked list of extended format combinations. When a new extended format combination is created, its position in the XF table is calculated according to a predetermined hash function. If two extended format combinations hash to the same location, the conflicting extended format is placed in an overflow table. Each cell in the spreadsheet contains an internal index which references a cell to an entry in the extended format table. Character format information is not stored in individual cells, and cells may share the same format combinations by merely setting the cell index to point to a desired format combination. Claims We claim: Description TECHNICAL FIELD
______________________________________
fEntry (1 bit) This bit indicates whether a
particular format entry contains a valid
format.
ifxeNext (12 bits) This is a pointer to the next XF
in the linked list of XF's.
ifmt: (6 bits) This contains an index into the
"Number Format" for the cell (e.g., the
number of decimal points, etc.).
ifnt (8 bits) This indicates font attributes
such as bold, italic, color, etc.
alc: (3 bits) Cell alignment.
borders: (4 bits - fLeft, fRight, fTop and fBottom.)
Individual cell borders.
fShade: (1 bit) Individual cell shading.
fLocked: (1 bit) Cell can't be changed when sheet
is locked.
fHidden: (1 bit) Cell formula is not displayed when
sheet is locked.
fRefer (1 bit) This bit indicates whether this
particular cell format is referenced by a
cell.
______________________________________
In the preferred practice of the present invention, the XF table contains 61 table entries wherein indices into the XF table 114 are generated according to a predetermined hash function. When the XF table 114 is first allocated, a default extended format 118 is installed in the XF table 114 in accordance with the generated hash index for the default format 118 wherein the index for each cell in the worksheet 100 is initialized with the value of the index for the default format. In addition to the main XF table, an overflow table 120 is provided wherein additional extended formats may be stored. The overflow table is also used for storing extended formats which hash to values which already point to locations in the extended format table. The overflow table 120 is preferably of variable size, wherein the size of the table is incrementally expanded in groups of thirty two-table entries to reduce the need for continuously recalculating the size of the overflow area 120. Referring now to FIG. 2, whenever the system 100 is first activated, process 202 is invoked to initialize a spreadsheet or worksheet. Once initialized, control passes to item 204 to wait for a user command. When a user input is received, the command is tested by decisions 206, 210 and 214, wherein control passes to process 208 if a "change cell format" command is detected; control passes to process 212 if a "save worksheet" command is detected; and control passes to process 216 if a load worksheet command is detected. Once a desired task is completed, control returns to item 204 to wait for the next user command. Referring now to FIG. 3, process 202 is invoked to initialize a worksheet. When invoked, the process 302 is called to allocate the XF table 114. Control then passes to item 304 to recall a default XF format. In the preferred practice of the present invention, the default XF format comprises a font type of Helvetica, 10 point, plain style, and a cell type of no borders, black color, etc. Item 306 then installs the default XF format in the XF table in accordance with the index generated by the IxfeFromXF routine according to the predetermined hash function. Control then passes to item 308 to return the index to the cell. Referring now to FIG. 4, the process 208 is invoked to change a cell format. When invoked, item 402 fetches the current cell format by recalling the format in the XF table pointed to by the index of the cell. Item 404 then copies the current cell format into a temporary location. Control then passes to item 406 to change the relevant bits in the extended format of interest Process 408 is then invoked to install the modified extended format in the XF table and to generate an index for the newly created cell by hashing the new extended format in accordance with the hashing function. Item 410 then returns the index to the cell of interest. Referring now to FIG. 5, the routine 212 is invoked to save an existing worksheet which may have been modified. When invoked, process 502 first marks cells referenced to indicate which extended formats are currently used by worksheet cells. Item 504 then saves the size of the current XF table, and item 506 saves the number of currently used extended formats. Next, process 508 is invoked to save used extended formats preceded by the current extended format index in the array of extended formats. Once the extended formats are written in the extended format table, process 510 is invoked to write the data stored in individual cells, along with their current extended format indices. Referring now to FIG. 6, the process 216 is invoked to load an existing worksheet. When invoked, item 602 reads the size of the old XF table, and item 604 allocates a mapping table having the same number of entries as the old XF table. Item 606 then reads the number of used extended formats in the file. Once the number of used extended formats is determined, item 608 allocates a new XF table with either the size of the maximum number of used extended formats or the size of the default XF table. Process 610 is then invoked to load the extended formats from the file of interest. Once the XF table is loaded, process 612 is invoked to read the cell data and to load the cells in row major order while applying table mapping. Item 614 then deallocates the mapping table. Referring now to FIGS. 7a-7c, the IxfeFromXf(xf) routine 306, 408 is invoked whenever a new extended format is created. The routine 306, 408 calculates an index for the new extended format, installs the new extended format in the XF table and returns the newly calculated index to the cell of interest. The overall function of the routine 306, 408 may be explained as follows. As noted above, the default XF table is allocated with 61 main table positions and 32 overflow positions. When a new extended format combination is created, its position in the XF table is calculated according to a predetermined hash function. If two extended format combinations hash to the same location, the conflicting extended format is placed in the overflow table. If the overflow table is full, the routine 306, 408 expands the overflow table to accommodate new extended formats. When invoked, item 702 determines the index of the first entry in the XF table according to the hash function. Those skilled in the art will appreciate that any of a number of well-known hashing algorithms would function satisfactorily in the system of the present invention. Item 704 then sets the index for the newly created XF table entry equal to the index for the first entry in the XF table. Decision 706 then determines whether the "fEntry" flag in the extended format pointed to by the retrieved index is set to determine whether the referenced extended format is currently used. If not, the extended format is installed in that location in the XF table. If the "fEntry" bit is set, control passes to loop 719 which traverses the XF table to find a matching extended format in the XF table. If one is not found, the extended format is installed in the overflow table. If the result of decision 706 is negative, i.e., the extended format is not used, item 708 sets the value of the collision pointer XF[ixfe].ixfeNext equal to Null to initialize the hash collision pointer for that XF table entry. Item 710 then sets the value of XF[ixfe] equal to the value of XF to copy the new extended format into the XF table. Control then passes to item 712 to set the value of XF[ixfe].fEntry equal to true to indicate that the extended format of interest is referenced and used. Process 713 is then invoked to install the extended format as the first or second entry of the XF table. This function is performed to ensure that frequently used extended formats tend to appear at the beginning of their hash collision list. In practice, each extended format is part of a hash collision list. The entries stored in the main body of the XF table comprise the head elements of the hash collision lists and entries in the overflow area of the XF table comprise the successive elements in the hash collision list. Therefore, as shown in FIG. 1, if for example, a new XF hashed to the same position as XF 117, its ixfeNext index would be adjusted to point to the next available entry in the overflow table. When invoked, decision 714 determines whether the new extended format is being inserted in the initial hash position by testing whether the index ixfe equals ixfeHead. If not, item 716 sets the value of XF[ixfe].ixfeNext equal to XF[ixfeHead].ixfeNext to copy the hash collision pointer from the head element to the collision pointer of the new element. Item 718 then sets the value of XF[ixfeHead] .ifeNext equal to ixfe, thus installing the next XF entry as the second XF entry in the hash collision list. If the result of decision 714 is affirmative or at the completion of item 718, the routine returns the value of ixfe, the index of the installed XF. Referring now to FIG. 7b, the routine 719 is entered whenever a newly created table entry's hash index matches an existing table entry's index. Therefore, the routine 719 may be thought of as a collision resolution routine. The variable ixfeLast will be used to point to the previous XF entry as the hash collision list is traversed. When invoked, item 720 sets the pointer ixfeLast equal to a null value to indicate no elements have been scanned. Decision 722 then determines whether the extended format pointed to by ixfe is equal to the desired extended format. If so, decision 724 determines whether the IfxeLast pointer equals null, thus indicating the first entry in the XF table is equal to the extended format of interest. If so, control passes to decision 714, previously discussed. Otherwise, control passes to item 726 which sets the value XF[ixfeLast].ixfeNext equal to XF[ixfe].ixfeNext. This step is performed to remove the matched XF entry from its current location in its hash collision list, wherein its new position in the hash collision list is set by process 713. If the result of decision 722 is negative, a match has not yet been found, and control passes to decision 728 which determines whether the value of XF[ixfe].ixfeNext=Null, thus indicating the end of the hash collision list has been reached. If the result of decision 728 is positive, control passes to decision 734 to allocate a new entry from the overflow table. Otherwise, control passes to items 730 and 732 which fetch the next table entry pointer and save the value of the table pointer of the XF table entry currently referenced by first setting the value of IxfeLast equal to Ixfe and then setting the value of Ixfe equal to the value of XF[Ixfe].IxfeNext. Control then returns to decision 722. Referring now to FIG. 7c, the process 733 is entered to allocate an entry from the overflow table. The variable, ixfeFree is used as a pointer to the next available location in the overflow portion of the XF table. The variable IxfeMax is used as a pointer to one location past the last location in the overflow portion of the XF table. When invoked, decision 734 determines whether the variable IxfeFree equals IxfeMax, thus indicating there are no further entries available in the XF table. If the result of decision 734 is affirmative, control passes to process 736 to reallocate the XF table. Otherwise, control passes to item 78 to install the XF in the location of the overflow table pointed to by IxfeFree. Item 740 then increments the variable IxfeFree and the control returns to item 710. Referring now to FIG. 8, the routine 510 is invoked to write cells to a file when saving a worksheet. Loop 806 is entered to write the worksheet cells (including the index into the XF table) to the file. When loop 806 is entered, item 808 initializes a worksheet cell index to point to the first cell in the worksheet. Item 810 then selects the cell pointed to by the index. Control then passes to item 812 which writes the cell contents to the file. The cell index is then incremented by item 814 to point to the next cell in the worksheet. Decision 816 then determines whether the cell index is pointing past the last cell in the worksheet. If not, control returns to item 810 to select the next cell in the worksheet. Otherwise, control returns to the calling routine. Referring now to FIG. 9, the routine 502 is invoked by the routine of FIG. 5 to scan the current worksheet to determine which entries in the XF table are referenced by cells in the worksheet so that only used XF's are written with a file when the file is saved. When invoked, item 902 sets the fRefer bit in each XF table entry to an initial state, which indicates the XF table entry is not referenced. Item 904 then initializes an index to point to the first cell in the worksheet. Next, item 906 selects the cell pointed to by the index. Item 908 sets the fRefer bit in the XF table entry of interest. Control then passes to item 910 to increment the index. Once the index is incremented, decision 912 determines whether the index has been incremented past the last cell in the worksheet. If so, control returns to the calling routine. Otherwise, control returns to item 906 to process the next cell. Referring now to FIG. 10, the routine 508 is invoked to write used XF's whenever a worksheet is saved. When invoked, item 1002 initializes an internal counter to zero wherein the counter comprises an index into the XF table. Item 1004 then selects the XF entry pointed to by the index. Once selected, decision 1006 determines whether the XF table entry pointed to by the index is referenced by testing the fRefer bit in the XF entry. If fRefer is not set, control passes to item 1012 to increment the index. Otherwise, control passes to item 1008 which writes the current index to the file. Item 1010 then writes the corresponding XF table entry to the file. Control then passes to item 1012 which increments the index. Next, decision 1014 determines whether the index has been incremented past the last entry in the XF table. If not, control returns to item 1004 to select the next entry in the XF table. Otherwise, control returns to the calling routine. Referring now to FIGS. 11a and 11b, the routine 610 is invoked to load XF table entries from a file when opening a worksheet. During this process, previously used XF's may no longer be referenced. Therefore, one function of routine 610 is to recalculate the indices for currently referenced XF table entries and to update the index entries in worksheet cells to point to the proper entries in the XF table. When invoked, item 1102 initializes an index into the XF's stored in the file; decision 1104 then determines whether the value of the index is equal to the maximum number of table entries in the file. If so, routine 610 returns to the calling routine. Otherwise, item 1106 reads the old index from the file. Item 1108 then reads the XF from the file. A new index is generated in item 1110 by invoking the IxfeFromXf routine shown in FIG. 7. The new index is loaded into the table rgmpOldNew by item 1112 at the location specified by the old index to provide a mapping from the old index to the new index to be used when mapping the spreadsheet cells as shown in FIG. 10b. The index into the XF's stored in the file is then incremented by item 1114 and control returns to decision 1104. Referring now to FIG. 12, the routine 612 is invoked to read cells from a file when opening an existing worksheet. When invoked, item 1201 initializes an internal counter to zero. Decision 1202 then determines whether an index comprising an internal counter is pointing to the last cell in the worksheet. If so, the routine returns. Otherwise, control passes to item 1204 which reads the next cell in the file and stores the cell in the appropriate worksheet location. Recall that cells are written and recalled in row major order. Item 1206 then resets the current cell index to a value equal to the new cell index mapped by routine 610. In other words, indices stored with cells in a file refer to old XF table locations when the file was saved. When XF's are read from a file, they may be placed in new locations by process 610. Item 1206 remaps the old index to point to the new correct location via the rgmpOldNew mapping table. Item 1208 then increments the internal counter to point to the next cell in the worksheet and control returns to decision 1202. Referring now to FIG. 13, the routine 302 is invoked to allocate a new XF table when a new worksheet is created. When invoked, item 1302 allocates an array in memory which is of sufficient size to accommodate 61 XF table entries as well as 32 overflow table entries. Item 1304 then sets the variable IxfeFree equal to 61 and sets the variable IxfeMax equal to 93. Item 1306 sets all of the fEntry bits to false to indicate none of the allocated cells are yet in use. The routine then returns. Referring now to FIG. 14, the routine 736 is invoked by the IxfeFromXF(xf) routine to reallocate a table when the table must be expanded to accommodate new table entries, wherein, in the preferred practice of the present invention, the XF table may be expanded to accommodate a maximum of approximately 4,000 table entries. Preferably, the XF table is expanded in increments of 32 table positions at a time. When invoked, item 1402 allocates a new XF table which contains 32 more positions than the previous XF table. Item 1404 then copies the contents of the old XF table (XF) into the newly allocated XF table (XF.sub.N). Next, item 1406 increments the variable IxfeMax by 32. Item 1408 then deallocates the original XF table. Item 1410 then resets the head of the table to point to the head of the new table in memory and the routine returns. Referring now to FIG. 15, the routine 1500 is invoked to display the cells of a worksheet. While the routine 1500 is discussed in terms of a single cell, those skilled in the art will appreciate that the routine 1500 may be invoked repetitively to display an entire worksheet. When invoked, item 1502 selects a cell of interest. Item 1504 then uses the index within the cell to read the cell format from the XF table. Item 1506 then applies the format bits to the cell and the cell is displayed by item 1508. The present invention optimizes the speed of this process invention since display format characteristics are determined by a simple table look-up mechanism. Accordingly, an improved method and system for applying enhanced formatting information to the data in cells of a worksheet has been described. In accordance with the principles of the present invention, a wide variety of formatting information may be associated with a worksheet cell without significantly increasing the size and memory requirements of the worksheet. The principles of the present invention are also readily applicable to virtually any type of computer application, such as word processors, data bases, etc. Accordingly, other uses and modifications of the present invention will be apparent to persons of ordinary skill without departing from the spirit and scope of the present invention, and all of such uses and modifications are intended to fall within the scope of the appended claims.
|
Same subclass Same class Consider this |
||||||||||