Structures and methods for representing and processing documents

Claims

What is claimed is:

1. In a document processing system including storage means for storing blocks of data and processing means for processing the data blocks and wherein a document is represented by a chain of text blocks of the data blocks in the storage means which contains test belonging to the document, the chain being formed by means of chaining information in each text block by means of which the processing means locates the following block in the chain, the method of inserting characters into the text contained in the chain at a given position in the text comprising for any insertion of characters the steps of:

(1) immediately following a first text block containing the given position, inserting a second empty text block marked with an insertion mark into the chain by copying the chaining information from the first text block into the second empty text block and setting the chaining information in the first text block to specify the second empty text block;

(2) copying the text which follows the given position in the first text block into the second text block;

(3) deleting the copied text from the first text block;

(4) inserting the characters at the end of the text remaining in the first text block; and

(5) on completion of the insertion, removing the insertion mark.

2. In a data processing system including storage means for storing at least routines and data and processing means for executing the stored routines and processing the data under control thereof, means for processing a document comprising:

(1) a document structure of the data for representing the document and

(2) document management routines that are a subset of the stored routines and are predefined for use by a plurality of application programs for performing operations on behalf of a plurality of application programs, including reading and modifying the document, on the document structure, the document management routines being the only means available in the data processing system for performing operations on the document structure and being employed by any other of the stored routines to perform an operation on the document structure.

3. In the means for processing documents of claim 2 and wherein:

the document structure includes text made up of characters; and the document management routines include

a routine for inserting a character into the document structure,

a routine for copying text contained in the document structure from one position within the document structure to another position within the document structure,

a routine for moving text contained in the document structure from one position within the document structure to another position within the document structure, and

a routine for deleting text contained in the document structure.

4. In a document processing system for processing documents, the document processing system including storage means for storing blocks of data at predetermined locations in the storage means and processing means for locating and processing the data blocks, a document structure for representing a document in the storage means by means of the data blocks and permitting the processing means to locate the data blocks as required to process the document, the document structure comprising:

(1) a plurality of chains of at least one data block, the data blocks in a given chain including chaining information used by the processing means to locate the next data block in the chain when processing the chain, the plurality of chains including

(a) a first chain which represents text belonging to the document;

(b) a second chain which represents a reference specifying information additional to the text of the document;

(3) in a data block of the first chain, a reference specifier specifying the reference; and

(4) a reference index which relates the reference specifier to the location in the storage means of the first data block in the second chain independently of the position of the reference specifier in the first chain and which the processing means employs to locate the reference for processing when the processing means encounters the reference specifier while processing the first chain.

5. In the document structure of claim 4 and wherein:

the block containing the reference specifier includes

a text part containing character codes representing text and

an attribute part containing the reference specifier.

6. In the document structure of claim 5 and wherein:

the text part further contains a non-printable attribute code for indicating the position in the text part at which the reference specified by the reference specifier applies.

7. In the document structure of claim 5 and wherein:

the attribute part contains a plurality of reference specifiers and

the order of the reference specifiers in the attribute part indicates the order in which the references specified by the references specifiers apply to the text part.

8. In the document structure of claim 5 and wherein:

the reference specifier in the attribute part is contained in an attribute word which further includes a location specifier specifying the location in the text part at which the reference specified by the reference specifier applies.

9. In the document structure of claim 4 and wherein:

the reference belongs to one of a plurality of types indicating the function of the reference in the document; and

the reference specifier in the attributable part is contained in an attribute word which further includes a first type specifier indicating the type of the reference specified by the reference specifier.

10. In the document structure of claim 9 and wherein:

each block in the second chain includes a second type specifier indicating the type of the reference.

11. In the document structure of claim 4 and wherein:

the reference specifier is an item number identifying the reference; and

the reference index indexes the reference by item number.

12. In the document structure of claim 4 and wherein:

the document structure further includes at least one index block of the blocks; and

the reference index is contained in the index block.

13. In the document of claim 12 and wherein:

the document structure includes a plurality of references;

the reference index exceeds the capacity of a single index block; and

the reference index includes

a plurality of secondary index blocks in which the processing means locates the references by their reference specifiers; and

a primary index block by which the processing means locates the secondary index blocks.

14. The document structure set forth in claim 4 and wherein:

the document structure further includes

a first plurality of the second chains, each second chain representing one of a plurality of the references, and

a second plurality of the reference specifiers, each of the reference specifiers specifying one of the references;

the reference specifiers are included in certain of the data blocks in both the first chain and the first plurality of second chains; and

the reference index relates each reference specifier to the location of the first data block in the second chain representing the reference specified by the reference specifier.

15. In a document processing system for processing documents, the document processing system including storage means the storing blocks of data and processing means for locating and processing the data blocks, a document structure for representing a document in the storage means by means of the data blocks and permitting the processing means to locate the data blocks as required to process the document, the document structure comprising:

(1) a plurality of chains of data blocks, the data blocks in a given chain including chaining information used by the processing means to locate the next data block in the chain when processing the chain, the plurality of chains including

(a) a page chain of at least one text block of the data blocks, the page chain representing at least one page of text of the document and

(b) a reference chain of at least one reference block of the data blocks which represents a reference specifying information additional to the text of the document;

(2) in a text block, an information attribute word containing an item number referring to the reference;

(3) a page index block of the data blocks which contains page index information relating a certain page number to the page and which the processing means employs to locate the page when the processing means receives the certain page number in the course of processing the document; and

(4) a reference index block of the data blocks which contains reference index information relating the item number to the location of the reference chain representing the reference and which the processing means employs to locate the reference for processing when the processing means encounters the information attribute word in the course of processing the page chain.

16. The document structure as set forth in claim 15 and further comprising:

a name index block of the data blocks which contains name index information relating a character-string name to the certain page number and which the processing means users to locate the page when the processing means receives the character-string name in the course of processing the document.

17. The document structure as set forth in claim 15 and further comprising:

a name index block of the data blocks which contains name index information relating a character-string name to the item number and which the processing means uses to locate the reference when the processing means receives the character-string name in the course of processing the document.

18. The document as set forth in claim 15 and wherein:

each data block has a block number;

the processing means locates data blocks by block numbers, and

the document structure further comprises a name index block of the data blocks which contains name index information relating a character-string name to a block number and which the processing means uses to locate the block when the processing means receives the character-string name in the course of processing the document.

19. The document as set forth in claim 18 and wherein:

the plurality of chains of data blocks further includes a text shelf chain;

the name index information relates the character-string name to the block number of a data block in the text shelf chain; and

the processing means uses the name information to locate the text shelf when the processing means receives the character-string name.

20. The document structure as set forth in claim 18 and wherein:

the document structure further comprises a named mark attribute word in a text block;

the name index information relates the character-string name to the block number of the text block containing the name mark attribute word; and

the processing means uses the name information to locate the text block containing the named mark attribute when the processing means receives the character-string name.

21. The document structure as set forth in claim 16 and wherein:

the text blocks and reference blocks contain codes for characters;

the processing means processes the text blocks and reference blocks by displaying the characters represented by the codes as determined by display fonts represented by font descriptors; and

the document structure further comprises

a font attribute word including a font number representing one of the display fonts in a text block and

a font index block of the data blocks which contains font information relating a font number to a font descriptor for the font represented by the font number and which is used by the processing means when the processing means encounters a font attribute word while processing the page chain to locate the font descriptor represented by the font number in the font attribute word.

22. The document structure set forth in claim 15 and wherein:

the document structure further includes

a first plurality of the reference chains, each reference chain representing one of a plurality of the references, and

a second plurality of the information attribute words, the item number in each of the information attribute words specifying one of the references;

the information attribute words are included in certain of the data blocks in both the first chain and the first reference chains; and

the reference index relates each item number to the location of the reference chain representing the reference specified by the item number.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a data structure for a data processing system and more particularly, to such a structure for the type of system referred to as a word processing or office automation system.

2. Description of the Prior Art

Word Processing and office systems are primarily concerned with the generation, editing and, for example, printing and filing, of documents. Such systems usually fall into two general classes, centralized and distributed.

A centralized system may include a central processor or computer and one or more attached terminals. Data, that is, documents of various types, and routines for operating upon the documents are stored in the central processor memory. Essentially all operations upon the documents are executed in the central processor, with the terminals operating as input and output devices for the central processor.

Distributed systems are based upon a network of smaller, active units, each having memory and processing capabilities. A distributed system may include a central, shared memory unit for storing routines and data and a number of independently operating terminals. Each terminal may include a memory for storing currently active segments of routines and data and a processor for operating upon the currently active segments.

Routine and data segments are transferred between the memory unit and the terminals as required by the operations of the terminals. An exemplary distributed system is shown in U.S. Pat. No. 4,145,739, issued Mar. 20, 1979 and assigned to Wang Laboratories, Inc., the assignee of the present invention.

In any system, whether previously existing or newly designed, the memory and processing capabilities of the system are usually determined and limited by economic and practical considerations. As a result of such limitations, a recurring problem in word processing and office systems is that of implementing increasingly more sophisticated and powerful document processing systems requiring increasingly greater memory and processing capabilities within currently available system limitations. The distributed system described in U.S. Pat. No. 4,145,739 was developed in response to this problem and provided a powerful word processing capability in a system having minimal memory and processing capabilities.

The problem described above may be regarded as being comprised of two related problem areas. The first is the system control structure, that is, a structure which includes and interrelates routines for controlling the operation of the system and routines for generating and manipulating documents. Because of the above described constraints, system control structures of the prior art have either required the use of a large and powerful computer or, in smaller systems, have only allowed document processing systems of limited capabilities. The problem is essentially one of implementing the power and flexibility of a large processor and memory system within a system having limited processing and memory capacity.

A related problem is, that due to the same constraints on memory and processing capability, the control and document processing systems of the prior art have been constructed in such a manner that the system cannot be easily modified. Such modifications frequently result in sever operational problems due to unexpected or unforeseen interactions between the modified and unmodified portions of the systems.

The second problem area is that of providing a document structure having the flexibility and expansion capability to allow the generation and manipulation of very complex documents within the above described constraints on memory and processing capability.

SUMMARY OF THE INVENTION

The present invention relates to a document processing system and in particular to an improved document structure for use in such a document processing system. The document structure of the present invention is made up of equal-sized numbered blocks in a document file. There are four chief classes of blocks: administrative blocks, index blocks, text blocks, and reference blocks. The text in a document is contained in a chain of text blocks. The chain of text blocks may be subdivided into pages. The text characters may have visual/descriptive attributes which determine the manner in which they appear when displayed and font attributes which specify the fonts used to display characters by font number. Locations in the text may also be associated with informational attributes which refer to information contained in chains of reference blocks by means of item numbers. Components of a document are located by means of indexes made up of the index blocks. There are four kinds of indexes: the page index, by which the text blocks at the heads of pages may be located by page number, the item index, by which references may be located by item number, the name index, by which named components of the document may be located by character string names, and the font index, by which descriptors for specific fonts may be located.

The document structure is manipulated by routines in a document manager library. The routines include routines for determining the item number or page number of a component and other routines for receiving an item number, page number, or name, and performing operations on the component so specified. All application programs which manipulate documents in the present invention use the routines in the document manager library.

It is thus an object of the present invention to provide an improved document processing system.

It is another object of the invention to provide an improved document structure for use in a document processing system.

It is an additional object of the invention to provide a document structure permitting access to its components by means of names, item numbers, and pages.

It is a further object of the invention to provide a document structure wherein a text may have descriptive/visual attributes, font attributes, and descriptive attributes.

It is still another object of the invention to provide an improved interface for manipulating the document structure.

Other objects and advantages of the present invention will be understood by those of ordinary skill in the art after referring to the detailed description of a preferred embodiment and the additional detailed description of a preferred embodiment contained herein and to the drawings, wherein:

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram representation of a system incorporating the present invention:

FIG. 2 is a block diagram representation of the control and document structures of the system of FIG. 1:

FIG. 3 is a block diagram representation of the work control and document structure of the system of FIG. 1;

FIG. 4 is a diagrammic representation of the document structure of the present invention.

FIG. 5 is a diagram of the structure of a document file of the present invention.

FIG. 6 is a diagram presenting a detailed overview of the document structure of the present invention.

FIG. 7 is a block diagram of document manipulation in prior-art document processing systems.

FIG. 8 is a block diagram of document manipulation in the document processing system of the present invention.

FIG. 9 is a representation of data structures used in the document processing system.

FIG. 10 is a detailed representation of a text block of the present invention.

FIG. 11 is a detailed representation of attribute words in the present invention.

FIG. 12 is a detailed representation of the format attribute word and the format reference block of the present invention.

FIG. 13 is a detailed representation of columns in the present invention.

Reference numbers in FIGS. 5-13 have three digits, the most significant of which is the number of the figure in which the reference is first illustrated. Thus, the reference with the number 629 is first shown in FIG. 6. Reference numbers for FIGS. 1-5 have only 2 digits and are not related to the figure numbers.

DESCRIPTION OF A PREFERRED EMBODIMENT

The following discussion presents the structure and operation of a document processing system incorporating the present invention. The system and system control and document structures will be detailed first at a block diagram level, followed by more detailed descriptions of these structures and the document structure implemented therein.

1. System Block Diagram Structure and Operation (FIGS. 1 and 2)

Referring to FIG. 1, a block diagram of a distributed System 10 incorporating the present invention is shown. System 10 is similar in structure and overall operation to the data processing system described in U.S. Pat. No. 4,145,739, previously referenced and incorporated herein by reference.

Major elements of System 10 include a Master Unit 12 and one or more Workstations 14 interconnected through System Bus 16. As will be described further below, Master Unit 12 is a system memory and stores a master copy of all routines for controlling operation of the system, including document manipulation operations executed by Workstations 14. Master Unit 12 also stores copes of all segments, active and inactive, of all documents being operated upon by Workstations 14.

Currently active segments of the documents being operated upon by Workstations 14, the document manipulation routines necessary to operate upon the active document segments and the routines necessary to control operation of Workstations 14 reside, as described below, in Workstations 14. The currently active document segments and routines residing in Workstations 14 are, as described further below, subsets of the master copies of the documents and routines residing in Master Unit 12. Document segments and workstation control and document manipulation routines are transferred between Master Unit 12 and Workstations 14 through System Bus 16 as required by the operations of Workstations 14.

A. Master Unit 12 (FIG. 1)

Master Unit 12 is, in the present embodiment, a disc drive memory including a Disc 18 and a Master Disc Controller 20. Master Disc Controller 20 is a microprocessor controlled unit operating under control of routines stored on Disc 18 for controlling transfer of information between Disc 18 and Workstations 14.

Referring to Disc 18, the information residing thereon includes a Master Copy 22 of all routines required to control all operations of System 10, including document manipulation operations, and one or more Document Files 24, which include copies of all segments, active and inactive, of all documents residing in System 10. The routines residing in Master Copy 22 include Master Operating System (MOS) 26, Supervisor Routines (SR) 28 and Overlay Routines (OR) 30. MOS 26 includes the routines controlling overall operation of System 10, for example, the operation of Disc Control 20 and the transfer of information between Master Unit 12 and Workstations 14. SR 28 includes the routines, described further below, for controlling the internal operations of Workstations 14 and essentially comprise an internal operating system for Workstations 14. OR 30, in turn, includes the document manipulation routines, that is, routines executed by Workstations 14 in directly operating upon documents.

Each Document File 24 residing on Disc 18 will include a master copy of a corresponding Document Structure (DS) 32 of a document residing in System 10. If the document currently being operated upon at Workstation 14, a copy of the currently active segments of the document's DS 32 will reside in the Workstation 14 and there will be transfers of document segments between the DS 32 a