Multiple insertion point queue to order and select elements to be processed

• US 6,145,031 A
• Filed: 08/26/1998
• Issued: 11/07/2000
• Est. Priority Date: 08/26/1998
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: International Business Machines Corporation
• Inventors: Xie, Ming, Mastie, Scott David
• Primary Examiner(s): Shin, Christopher B.
• Application Number:
  US09/140,482
• Time in Patent Office: 804 Days
• Field of Search: 395/114, 395/115, 400/61, 710/5-7, 710/40-45, 710/52-57, 711/158
• US Class Current: 710/52
• CPC Class Codes: G06F 3/1211 Improving printing performance
• CPC Class Codes: G06F 3/126 Job scheduling, e.g. queuing, determine appropriate device
• CPC Class Codes: G06F 3/1263 based on job priority, e.g. re-arranging the order of jobs, e.g. the printing sequence
• CPC Class Codes: G06F 3/1288 in client-server-printer device configuration

Abstract

Disclosed is a system for queuing elements, such as print jobs. A processing unit receives an element that is associated with a first factor and a second factor, such as data type and a priority within the data type, that indicates a priority of the element. For each first factor and second factor pair, an entry point addresses a point in the queue associated with the first factor and second factor. The processing unit locates an entry point addressing a point in the queue associated with a first factor and second factor that matches the first factor and second factor associated with the received element. The processing unit then inserts the received element in the queue at the entry point.

Claims

1. A method for queuing elements, comprising:

receiving an element related to a file associated with a first factor and a second factor that indicates a priority of the element, wherein the element is a member of a set of elements consisting of a pointer to a file, a token reference to a file and a file;

providing entry points to a queue of elements, wherein for each first factor and second factor pair, an entry point addresses a point in the queue associated with the first factor and second factor;

locating an entry point addressing a point in the queue associate with a first factor and second factor that matches the first factor and second factor associated with the received element; and

inserting the received element in the queue at the entry point.

2. The method of claim 1, wherein the received elements are associated with additional factors, wherein for each additional factor, an entry point addresses a point in the queue.

3. The method of claim 1, further comprising the steps of:

providing an exit point that addresses an element in the queue according to the priority of the elements in the queue;

processing a request for an element from the queue; and

accessing the element addressed by the exit point to return to the request.

4. The method of claim 1, wherein the first factor comprises a data type and the second factor comprises a priority within the data type, and wherein a priority ordering indicates the priority among the data types.

5. The method of claim 4, wherein the exit point addresses an element having a highest priority data type of the elements in the queue and having a highest priority factor of the elements in the queue of the same data type, further comprising the steps of:

determining an element in the queue by performing the steps of;

(i) determining whether there is an element in the queue having the same data type as the accessed element;

(ii) determining an element in the queue having a data type that is lower priority than the data type of the accessed element after determining that there is no element in the queue having the same data type as the accessed object;

(iii) determining whether there is an element in the queue having the same priority factor as the accessed element after determining that there is an element in the queue having the same data type as the accessed element;

(iv) determining an element in the queue having the same data type and priority factor as the accessed element after determining that there is an element in the queue having the data type of the accessed element; and

(v) determining an element in the queue having the same data type and lower priority factor than the accessed element after determining that there is no element in the queue having the same data type and priority factor as the accessed element; and

modifying the exit point to address the determined element.

6. The method of claim 1, wherein the step of providing entry points further comprises providing a table including an entry for each first factor and second factor pair, wherein there is at least a one-to-one correspondence between entries in the table and entry points in the queue for each first and second factor pair, and wherein the step of locating the entry point comprises locating the entry in the table corresponding to the first and second factor pair and determining the pointer for the located table entry addressing the entry point in the queue.

7. The method of claim 6, wherein the step of inserting the received element in the queue comprises:

determining the table entry point for the first and second factor pair associated with the received data;

inserting the received element at the point in the queue addressed by the pointer for the determined table entry point; and

modifying the pointer for the determined table entry point to address the inserted element.

8. The method of claim 1, wherein the elements in the queue comprise pointers to print files, wherein the print job to which the element points has not been transformed into an output data stream capable of being read by a printer, further comprising the steps of:

determining whether a transform process is available;

accessing an element in the queue after determining the availability of a transform process;

processing the element to locate the print file to which the element points;

transmitting the located print file to the available transform process to transform the print file into an output data stream; and

transmitting the output data stream to a printer for printing.

9. The method of claim 1, wherein the elements in the queue comprise pointers to output data streams that are the result of a transform process on a print file, further comprising the steps of:

accessing an element in the queue according to the priority indicated by the first and second factors;

determining a logical printer having a set of print attributes compatible with print attributes of the accessed element, wherein the logical printer groups physical printers having a common set of print attributes;

determining whether a physical printer grouped by the logical printer is available;

processing the element to locate the output data stream to which the element points; and

transferring the located output data stream to a logical printer queue after determining that a physical printer grouped by the logical printer is available.

10. The method of claim 1, wherein the elements comprise pointers to output data streams that are the result of a transform process on a print file, wherein the queue is a logical printer queue, and wherein a logical printer groups physical printers having a common set of print attributes, further comprising the steps of:

determining whether a physical printer grouped by the logical printer is available;

accessing an element in the logical printer queue after determining the availability of a physical printer;

processing the element to locate the output data stream to which the element points; and

transferring the output data stream to the physical printer for printing.

11. A system for processing elements, comprising:

a processing unit;

a memory device for access by the processing unit including data structures accessible to the processing unit, the data structures comprising;

(i) a queue of elements, wherein each element is associated with a first factor and a second factor that indicates a priority of the element, and wherein the element is a member of a set of elements consisting of a pointer to a file, a token reference to a file and a file;

(ii) entry points to elements in the queue, wherein for each first factor and second factor pair, an entry point addresses a point in the queue associated with the first factor and second factor;

program logic executed by the processing unit, including;

(i) means for receiving an element;

(ii) means for locating an entry point addressing a point in the queue associated with a first factor and second factor that matches the first factor and second factor associated with the received element; and

(iii) means for inserting the received element in the queue at the entry point.

12. The system of claim 11, wherein the received elements are associated with additional factors, wherein for each additional factor, an entry point addresses a point in the queue.

13. The system of claim 11, wherein the data structrues in the memory device further comprise an exit point that addresses an element in the queue according to the priority of the elements in the queue, and wherein the program logic further includes:

means for processing a request for a element from the queue; and

means for accessing the element addressed by the exit point to return to the request.

14. The system of claim 11, wherein the first factor comprises a data type and the second factor comprises a priority within the data type, and wherein a priority ordering indicates the priority among the data types.

15. The system of claim 14, wherein the exit point addresses an element having a highest priority data type of the elements in the queue and having a highest priority factor of the elements in the queue of the same data type, wherein the program logic determines an element in the queue by:

(i) determining whether there is an element in the queue having the same data type as the accessed element;

(ii) determining an element in the queue having a data type that is lower priority than the data type of the accessed element after determining that there is no element in the queue having the same data type as the accessed object;

(iii) determining whether there is an element in the queue having the same priority factor as the accessed element after determining that there is an element in the queue having the same data type as the accessed element;

(iv) determining an element in the queue having the same data type and priority factor as the accessed element after determining that there is an element in the queue having the data type of the accessed element;

(v) determining an element in the queue having the same data type and lower priority factor than the accessed element after determining that there is no element in the queue having the same data type and priority factor as the accessed element; and

wherein the program logic further includes means for modifying the exit point to address the determined element.

16. The system of claim 11, wherein the data structures in the memory device further include a table including an entry for each first factor and second factor pair, wherein there is at least a one-to-one correspondence between entries in the table and entry points in the queue for each first and second factor pair, wherein the program logic locates the entry point by locating the entry in the table corresponding to the first and second factor pair and determining the pointer for the located table entry addressing the entry point in the queue.

17. The system of claim 16, wherein the program logic inserts the received element by:

determining the table entry point for the first and second factor pair associated with the received element;

inserting the received element at the point in the queue addressed by the pointer for the determined table entry point; and

modifying the pointer for the determined table entry point to address the inserted element.

18. The system of claim 11, further including a printer, wherein the elements comprise pointers to print files that have not been transformed into output data streams capable of being read by a printer, wherein the program logic further includes:

means for determining whether a transform process is available;

means for accessing an element in the queue after determining the availability of a transform process;

means for processing the accessed element to locate a print file to which the element points;

means for transmitting the located print file to the available transform process to transform the print file into an output data stream; and

transmitting the output data stream to the printer for printing.

19. The system of claim 11, wherein the elements in the queue comprise pointers to output data streams that are the result of a transform process on a print file, and wherein the data structures include logical printer data structures grouping physical printers having a common set of print attributes, wherein the program logic further includes:

means for accessing an element in the queue according to the priority indicated by the first and second factors;

means for determining a logical printer having a set of print attributes compatible with print attributes of the accessed element;

means for processing the element to locate the output data stream to which the element points;

means for determining whether a physical printer grouped by the logical printer is available; and

means for transferring the located output data stream to a physical printer grouped by the logical printer after determining that a physical printer grouped by the logical printer is available.

20. The system of claim 11, wherein the elements comprise pointers to output data streams that are the result of a transform process on a print file, wherein the queue is a logical printer queue, and wherein the data structures include a logical printer data structure grouping physical printers having a common set of print attributes, wherien the program logic further includes:

means for determining whether a physical printer grouped by the logical printer data structure is available;

means for accessing an element in the logical printer queue after determining the availability of a physical printer;

processing the accessed element to locate the output data stream to which the element points; and

means for transferring the located output data stream to the physical printer for printing.

21. An article of manufacture for use in processing a queue of elements, the article of manufacture comprising computer readable storage media including at least one computer program embedded therein that causes a processing unit to perform the steps of:

receiving an element associated with a first factor and a second factor that indicates a priority of the element, wherein the element is a member of the set of elements consisting of a pointer to a file, a token reference to a file and a file;

providing entry points to a queue of elements, wherein for each first factor and second factor pair, an entry point addresses a point in the queue associated with the first factor and second factor;

locating an entry point addressing a point in the queue associated with a first factor and second factor that matches the first factor and second factor associated with the received element; and

inserting the received element in the queue at the entry point.

22. The article of manufacture of claim 21, wherein the received elements are associated with additional factors, wherein for each additional factor, an entry point addresses a point in the queue.

23. The article of manufacture of claim 21, further comprising the steps of:

providing an exit point that addresses an element in the queue according to the priority of the elements in the queue;

processing a request for an element from the queue; and

accessing the element addressed by the exit point to return to the request.

24. The article of manufacture of claim 21, wherein the first factor comprises a data type and the second factor comprises a priority within the data type, and wherein a priority ordering indicates the priority among the data types.

25. The article of manufacture of claim 21, wherein the exit point addresses an element having a highest priority data type of the elements in the queue and having a highest priority factor of the elements in the queue of the same data type, further comprising the steps of:

determining an element in the queue by performing the steps of;

(i) determining whether there is an element in the queue having the same data type as the accessed element;

(ii) determining an element in the queue having a data type that is lower priority than the data type of the accessed element after determining that there is no element in the queue having the same data type as the accessed object;

(iii) determining whether there is an element in the queue having the same priority factor as the accessed element after determining that there is an element in the queue having the same data type as the accessed element;

(iv) determining an element in the queue having the same data type and priority factor as the accessed element after determining that there is an element in the queue having the data type of the accessed element;

(v) determining an element in the queue having the same data type and lower priority factor than the accessed element after determining that there is no element in the queue having the same data type and priority factor as the accessed element; and

modifying the exit point to address the determined element.

26. The article of manufacture of claim 21, wherein the step of providing entry points further comprises providing a table including an entry for each first factor and second factor pair, wherein there is at least a one-to-one correspondence between entries in the table and entry points in the queue for each first and second factor pair, and wherein the step of locating the entry point comprises locating the entry in the table corresponding to the first and second factor pair and determining the pointer for the located table entry addressing the entry point in the queue.

27. The article of manufacture of claim 26, wherein the step of inserting the received element in the queue comprises:

determining the table entry point for the first and second factor pair associated with the received data;

inserting the received element at the point in the queue addressed by the pointer for the determined table entry point; and

modifying the pointer for the determined table entry point to address the inserted element.

28. The article of manufacture of claim 21, wherein the elements in the queue comprise pointers to print files that have not been transformed into output data streams capable of being read by a printer, further comprising the steps of:

determining whether a transform process is available;

accessing an element in the queue after determining the availability of a transform process;

processing the element to locate the print file to which the element points;

transmitting the located print file to the available transform process to transform the print file into an output data stream; and

transmitting the output data stream to a printer for printing.

29. The article of manufacture of claim 21, wherein the elements in the queue comprise pointers to output data streams that are the result of a transform process on a print file, further comprising the steps of:

accessing an element in the queue according to the priority indicated by the first and second factors;

processing the element to locate the output data stream to which the element points;

determining a logical printer having a set of print attributes compatible with print attributes of the accessed element, wherein the logical printer groups physical printers having a common set of print attributes;

determining whether a physical printer grouped by the logical printer is available; and

transferring the located output data stream to a logical printer queue after determining that a physical printer grouped by the logical printer is available.

30. The article of manufacture of claim 21, wherein the elements in the queue comprise pointers to output data streams that are the result of a transform process on a print file, wherein the queue is a logical printer queue, and wherein a logical printer groups physical printers having a common set of print attributes, further comprising the steps of:

determining whether a physical printer grouped by the logical printer is available;

accessing an element in the logical printer queue after determining the availability of a physical printer;

processing the element to locate the output data stream to which the element points; and

transferring the output data stream to the physical printer for printing.

31. A memory device including a queue data structure queuing elements that is accessible to a processing unit, wherein the data structure is comprised of:

elements related to a file associated with a first factor and a second factor that indicates a priority of the element, wherein the element is a member of a set of elements consisting of a pointer to a file, a token reference to a file and a file; and

entry points to the elements, wherein for each first factor and second factor pair, an entry point addresses a point in the queue associated with the first factor and second factor, wherein the processing unit locates an entry point addressing a point in the queue as associated with a first factor and second factor that matches the first factor and second factor associated with the received element, wherein the processing unit inserts the received element into the queue at the entry point.

32. The memory device of claim 31, further comprising an exit point that addresses an element in the queue according to the priority of the elements in the queue, wherein the processing unit processes a request for an element from the queue;

and in response thereto accesses the element addressed by the exit point to return to the request.

33. The memory device of claim 31, wherein the first factor comprises a data type and the second factor comprises a priority within the data type, and wherein a priority ordering indicates the priority among the data types.