Gap-based style-run array mechanism

• US 6,092,092 A
• Filed: 03/13/1998
• Issued: 07/18/2000
• Est. Priority Date: 03/13/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Felt, Douglas, Raley, John, Gillam, Richard
• Primary Examiner(s): Homere, Jean R.
• Assistant Examiner(s): KHONG, TRI HOANG
• Application Number:
  US09/042,296
• Time in Patent Office: 858 Days
• Field of Search: 395/147, 395/445, 395/805, 707/500, 707/530, 345/472, 345/432, 345/468, 345/467
• US Class Current: 715/207
• CPC Class Codes: G06F 40/109 Font handling; Temporal or kinetic typography

Abstract

Character style information is stored in an array, in parallel with character information stored within another data structure. The style information array has more memory allocated to it than would be required to store the style information. This surplus memory is employed to form a "gap" in the array at a location corresponding to the point at which characters are being modified. The gap permits rapid revisions to character style information, while the array storage mechanism permits rapid random access to the style information of any character. Character style information may be mapped to corresponding characters using a run--array mechanism which associates a style with characters through use of an offset which indicates a starting character to which the style applies and a run length which indicates the number of characters to which the style applies. Additionally, the offset may be related to the beginning or to the end of the document, depending upon whether the associated style run falls before or after the memory gap.

Claims

1. Apparatus for use with a computer system having a memory, the apparatus associating character style information with each character stored in a data structure in the memory and comprising:

an array generator which generates in the memory an array having a plurality of elements, some of the elements storing character style information arranged as a style run and an array gap including at least one empty element;

a mechanism located in each element which associates the element with a contiguous group of characters in the data structure, each character within the contiguous group having the same character style; and

an editor which modifies character style information in an array element by moving the array elements in the array gap to a location adjacent to the array element being modified.

2. The apparatus of claim 1 wherein each style run comprises:

a character style indicator identifying selected character style information;

a location indicator; and

a run length indicator which indicates the number of characters to which the selected character style information applies.

3. The apparatus of claim 2 wherein the location indicator comprises an offset value from the beginning of the data structure to the first character to which the character style information in the style run applies.

4. The apparatus of claim 3 wherein the location indicator comprises a first offset value from the beginning of the data structure to the character location when the character location is within a style run in an element located in the array before the array gap and a second offset value from the end of the data structure to the character location when the character location is within a style run in an element located in the array after the gap.

5. The apparatus of claim 4 wherein the character style information comprises a pointer to a location in the memory containing style information.

6. The apparatus of claim 3 further comprising a search mechanism which locates a style run containing style information associated with a specific character by performing a binary search of the offset values in the style runs until an offset value is found which indicates that the character style information associated with the specific character is contained within the associated style run.

7. The apparatus of claim 6 further comprising a persistent iterator object which stores the array element containing the most recently modified style run.

8. The apparatus of claim 7 wherein the location indicator comprises a first offset value from the beginning of the data structure to the character location when the character location is within a style run in an element located in the array before the array gap and a second offset value from the end of the data structure to the character location when the character location is within a style run in an element located in the array after the gap, the search mechanism employing the persistent iterator to locate a style run containing style information associated with a character of interest whenever style information is modified without adding style runs to or deleting style runs from the style run array and to employ a binary search and the offset values to locate a style run containing style information associated with a character of interest whenever adding style runs to or deleting style runs from the style run array.

9. The apparatus of claim 6 wherein the array generator forms a gap in the array adjacent to the style run associated with a specific character and updates the offset values of style runs affected by forming the gap.

10. A method of associating character style information with each character stored in a data structure in memory, comprising the steps of:

(a) generating an array in the memory having a plurality of elements, some of the elements storing character style information arranged as style runs, and an array gap including at least one empty element; and

(b) modifying the style run associated with a character of interest after moving the gap adjacent to the style run containing style information associated with a character of interest.

11. The method of claim 10 wherein step (b) comprises the step of:

(b1) locating the style run associated with a character of interest.

12. The method of claim 11 wherein each style run in the array contains offset information and run length information and step (b1) comprises:

(b2) matching the character of interest'"'"'s position within the data structure with offset and run length information contained within the style runs.

13. The method of claim 12 wherein the offset information is relative to the beginning of the style run array for style runs situated before the array gap and is relative to the end of the style run array for style runs situated after the array gap.

14. The method of claim 11 wherein each style run includes run length information and the step of locating a style run comprises the step of:

(b3) performing a binary search of offset values.

15. The method of claim 14 comprising the steps of:

(b4) forming a stable iterator configured to indicate the location within the style array most recently modified, and

(b5) locating a style run by examining the style run indicated by the stable iterator and using this style run if it contains the style information of interest, and employing the binary search the offset values as in step (b3) if it does not.

16. The method of claim 15 wherein the step of locating a style run comprises:

(b6) accumulating run lengths from the persistent iterator'"'"'s location whenever style runs are not to be added or deleted, and

(b7) matching the character of interest'"'"'s position within the data structure with offset and run length information contained within the style runs whenever style runs are to be added or deleted, the offset information being relative to the beginning of the data structure for style runs situated before the array gap and relative to the end of the data structure for style runs situated after the array gap.

17. A computer program product for storing and modifying character style information associated with character information stored in a data structure, the computer program product comprising a computer usable medium having computer program code embodied thereon, the program code comprising:

computer program code configured to generate an array in a memory, the array having a plurality of elements, some of the elements storing character style information arranged as style runs, and to form an array gap including at least one empty element; and

computer program code configured to modify the style run associated with a character of interest after moving the gap adjacent to the style run containing style information associated with a character of interest then.

18. The computer program product of claim 17 further comprising computer program code for locating the style run associated with a character of interest.

19. The computer program product of claim 18 further comprising computer program code for matching the character of interest'"'"'s position within the data structure with offset and run length information contained within the style runs.

20. The computer program product of claim 18 further comprising computer program code for establishing offset information which is relative to the beginning of the data structure for style runs situated before the array gap and is relative to the end of the data structure for style runs situated after the array gap.

21. The computer program product of claim 18 wherein each style run comprises run length information and the computer program product comprises code configured to locate a style run by accumulating run lengths.

22. The computer program product of claim 21 further comprising computer program code configured to form a stable iterator which indicates the location within the style array most recently modified, and

computer program code configured to locate a style run by accumulating run lengths from the position indicated.