Priority queues for computer simulations
AssigneeThe United States of America as represented by the Administrator of the National Aeronautics and Space Administration
InventorJeffrey S. Steinman
Life of this patent
Estimating the term…
Abstract
The present invention is embodied in new priority queue data structures for event list management of computer simulations, and includes a new priority queue data structure and an improved event horizon applied to priority queue data structures. The new priority queue data structure is a Qheap and is made out of linked lists for robust, fast, reliable, and stable event list management and uses a temporary unsorted list to store all items until one of the items is needed. Then the list is sorted, next, the highest priority item is removed, and then the rest of the list is inserted in the Qheap. Also, an event horizon is applied to binary tree and splay tree priority queue data structures to form the improved event horizon for event management.
Claims29
A computer-implemented process for managing events within a priority queue stored on a computer, comprising the steps of:
- a) limiting the priority queue to having only S elements;
- b) directly inserting an element into the priority queue at a predetermined first event occurrence and at a certain value of S;
- c) directly removing an element from the priority queue at a predetermined second event occurrence and at a certain value of S;
- and
- d) metasizing the priority queue into a single metaitem after a trigger value of S is realized and an element needs to be inserted, and assigning a sort value determined by a first element located in the priority queue, wherein metasizing the priority queue into a single metaitem is performed prior to insertion of a new element, and wherein said process provides fast and predicable event list management for computer simulation systems.
An event manager for managing events, comprising:
- a programmable computer having memory;
- a priority queue interactive with said events, said priority queue and said events stored on said computer in said memory;
- and
- at least one element located within said priority queue;
- wherein said priority queue being limited to having only S elements, wherein said elements are comprised of real event items and metasized metaitems only when a trigger value of S is realized and at a predetermined event occurrence, and wherein said computer being directed by said priority queue to manage said events.
An event manager for managing events for computer simulation systems, comprising:
- a) a programmable computer having memory;
- b) a priority queue interactive with said events and limited to having only S elements, said priority queue and said events stored on said computer in said memory;
- c) means for directly inserting an element into the priority queue only at a certain value of S and at a predetermined first event occurrence;
- d) means for directly removing an element from the priority queue only at a certain value of S and at a predetermined first event occurrence;
- and
- e) means for metasizing the priority queue into a single metaitem when a trigger value of S is realized and at a predetermined first event occurrence, means for assigning a sort value determined by a first element located in the priority queue, wherein the priority queue is metasized prior to insertion of a new element.
A computer-implemented process for managing events within a priority queue stored on a computer, said priority queue interactive with an event horizon defined by events processed in successive cycles, said computer-implemented process comprising the steps of:
- a) directly inserting an element into a temporary queue at a predetermined first event occurrence and when the event horizon has not been crossed so that a next event to be processed is not in the temporary queue, wherein said temporary queue is comprised of a top item and successive items;
- b) directly removing an element from the temporary queue at a predetermined second event occurrence and when the event horizon has not been crossed;
- and
- c) sorting the temporary queue when the event horizon is crossed, by removing the top item and naming it a next event, metasizing the successive items in the list, and then inserting an element into the queue that needs to be inserted, wherein said process provides fast and predicable event list management for computer simulation systems.
A computer-implemented process for managing events within a priority queue stored on a computer, said priority queue interactive with an event horizon defined by events processed in successive cycles, said computer-implemented process comprising the steps of:
- a) continually maintaining a primary list and a secondary list for said priority queue which is comprised of a tree with a starting root forming paths diverging from the root;
- b) sorting only the primary list at a first predetermined time;
- c) traversing along one of the paths as an event is removed until the event is removed and traversing along one of the paths as an event is inserted until the event is inserted;
- d) recursively placing a new event into the secondary list and applying a balancing heuristic at each node along the traversed path when a new event is scheduled to be inserted;
- e) preserving an earliest event scheduled to occur in the secondary list;
- and
- f) sorting the secondary list at a second predetermined time and then merging the secondary list into the primary list, wherein said process provides fast and predicable event list management for computer simulation systems.
A computer-readable medium for causing a computer system to manage events for computer simulation systems, comprising:
- a computer-readable storage medium;
- a computer program stored on said medium;
- wherein said computer program operates on said computer system and performs event management, wherein said computer program comprises,
- a priority queue interactive with said events, and
- at least one element located within said priority queue,
- wherein said priority queue being limited to having only S elements, wherein said elements are comprised of real event items and metasized metaitems at a predetermined event occurrence and after a trigger value of S is realized.
Dependencies are inferred from the claim text.