Rosetta Code

Priority queue: Difference between revisions

Page Discussion

Priority queue (view source)

Revision as of 04:21, 9 May 2024

11,579 bytes added ,  1 month ago
m
→‎{{header|Zig}}
 
(13 intermediate revisions by 4 users not shown)
Line 2,392:
4: Feed cat
5: Make tea</pre>
 
=={{header|COBOL}}==
 
===IBM Enterprise COBOL solution===
 
Note that the logic of this implementation follows the C solution above for "Pairing heap w/ generic data types" except that the "generic type" (the TASK record defintion) is sized and allocated in the calling test program instead of in the priority queue subroutines.
 
Note also that each subroutine is declared RECURSIVE though they do not all need it.
 
The subroutines each pass back a return value in their last parameter. The most recent release of the IBM Enterprise COBOL compiler (V6.4 as of the date of this contribution) does, in fact, support user-defined functions, which would make some of this implementation a little easier to write and read, but since many IBM shops are not yet up to the most recent level, this version is offered as one that will work with down-level compiler versions.
 
In the "two pass merge" subroutine (PTYQ2PMG), the final three lines are needed because the COBOL CALL statement does not allow for expressions as arguments, so the arguments to the outer call to the "merge" subroutine must be executed first, and the results of those two calls become the arguments to the final "merge" call.
 
Note also that the subroutines call each other using "PIC X(8)" pseudonyms because the actually recursive subroutines cannot use the "same name" as both the PROGRAM-ID and as a variable name. This could be resolved by simply using "constant" calls (like <code>CALL "PTYQ2PMG" USING . . . </code> but using the pseudonyms allows each of the subroutines to also be separately compiled into an executable module and then dynamically loaded at run time. Many IBM shops will prefer that method to this purely "static" solution.
 
<syntaxhighlight lang="COBOL">
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQTEST
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
* UNCOMMENT WITH DEBUGGING CLAUSE FOR DEBUG LINES TO EXECUTE.
SOURCE-COMPUTER.
Z-SYSTEM
* WITH DEBUGGING MODE
.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 PTYQ-PGMNAMES.
05 PTYQPUSH PIC X(8) VALUE "PTYQPUSH".
05 PTYQPOP PIC X(8) VALUE "PTYQPOP".
 
01 TASK-PTR POINTER.
 
01 TOP-PTR POINTER.
 
01 LINK-KEY PIC S9(8) COMP-5.
 
01 HEAP-PTR POINTER VALUE NULL.
 
01 PUSHD-PTR POINTER VALUE NULL.
 
01 POPPD-PTR POINTER VALUE NULL.
 
LINKAGE SECTION.
01 TASK.
05 TASK-NODE.
10 TASK-KEY PIC S9(8) COMP-5.
10 TASK-NEXT POINTER.
10 TASK-DOWN POINTER.
05 TASK-NAME PIC X(40).
 
PROCEDURE DIVISION.
ALLOCATE TASK RETURNING TASK-PTR
MOVE "EAT SCONES." TO TASK-NAME
MOVE +6 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
ALLOCATE TASK RETURNING TASK-PTR
MOVE "CLEAR DRAINS." TO TASK-NAME
MOVE +3 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
ALLOCATE TASK RETURNING TASK-PTR
MOVE "FEED CAT." TO TASK-NAME
MOVE +4 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
ALLOCATE TASK RETURNING TASK-PTR
MOVE "MAKE TEA." TO TASK-NAME
MOVE +5 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
ALLOCATE TASK RETURNING TASK-PTR
MOVE "SOLVE RC TASKS." TO TASK-NAME
MOVE +1 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
ALLOCATE TASK RETURNING TASK-PTR
MOVE "TAX RETURN." TO TASK-NAME
MOVE +2 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
PERFORM WITH TEST BEFORE UNTIL HEAP-PTR = NULL
SET TOP-PTR TO HEAP-PTR
SET ADDRESS OF TASK TO TOP-PTR
DISPLAY TASK-KEY " " TASK-NAME
CALL PTYQPOP USING HEAP-PTR, POPPD-PTR
SET HEAP-PTR TO POPPD-PTR
FREE TOP-PTR
END-PERFORM
GOBACK.
END PROGRAM PTYQTEST.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQMERG RECURSIVE.
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
* UNCOMMENT WITH DEBUGGING CLAUSE FOR DEBUG LINES TO EXECUTE.
SOURCE-COMPUTER.
Z-SYSTEM
* WITH DEBUGGING MODE
.
 
DATA DIVISION.
 
LINKAGE SECTION.
01 HEAP-PTRA POINTER.
 
01 HEAP-PTRB POINTER.
 
01 MERGD-PTR POINTER.
 
01 HEAPA.
05 HEAPA-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAPA-NEXT POINTER.
05 HEAPA-DOWN POINTER.
 
01 HEAPB.
05 HEAPB-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAPB-NEXT POINTER.
05 HEAPB-DOWN POINTER.
 
PROCEDURE DIVISION USING HEAP-PTRA, HEAP-PTRB, MERGD-PTR.
EVALUATE TRUE
WHEN HEAP-PTRA = NULL
SET MERGD-PTR TO HEAP-PTRB
WHEN HEAP-PTRB = NULL
SET MERGD-PTR TO HEAP-PTRA
WHEN OTHER
SET ADDRESS OF HEAPA TO HEAP-PTRA
SET ADDRESS OF HEAPB TO HEAP-PTRB
IF HEAPA-KEY < HEAPB-KEY
IF HEAPA-DOWN NOT = NULL
SET HEAPB-NEXT TO HEAPA-DOWN
END-IF
SET HEAPA-DOWN TO HEAP-PTRB
SET MERGD-PTR TO HEAP-PTRA
ELSE
IF HEAPB-DOWN NOT = NULL
SET HEAPA-NEXT TO HEAPB-DOWN
END-IF
SET HEAPB-DOWN TO HEAP-PTRA
SET MERGD-PTR TO HEAP-PTRB
END-IF
END-EVALUATE
GOBACK.
END PROGRAM PTYQMERG.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQ2PMG RECURSIVE.
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
* UNCOMMENT WITH DEBUGGING CLAUSE FOR DEBUG LINES TO EXECUTE.
SOURCE-COMPUTER.
Z-SYSTEM
* WITH DEBUGGING MODE
.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 PGMQMERG PIC X(8) VALUE "PTYQMERG".
01 PGMQ2PMG PIC X(8) VALUE "PTYQ2PMG".
 
LOCAL-STORAGE SECTION.
01 HEAP-PTRA POINTER.
 
01 HEAP-PTRB POINTER.
 
01 HEAP-REST POINTER.
 
01 MERG1-PTR POINTER.
 
01 MERG2-PTR POINTER.
 
LINKAGE SECTION.
01 HEAP-PTR POINTER.
 
01 MERGD-PTR POINTER.
 
01 HEAP.
05 HEAP-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAP-NEXT POINTER.
05 HEAP-DOWN POINTER.
 
01 HEAPA.
05 HEAPA-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAPA-NEXT POINTER.
05 HEAPA-DOWN POINTER.
 
01 HEAPB.
05 HEAPB-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAPB-NEXT POINTER.
05 HEAPB-DOWN POINTER.
 
01 REST.
05 REST-KEY PIC S9(8) COMP-5 VALUE +0.
05 REST-NEXT POINTER.
05 REST-DOWN POINTER.
 
PROCEDURE DIVISION USING HEAP-PTR, MERGD-PTR.
SET ADDRESS OF HEAP TO HEAP-PTR
EVALUATE TRUE
WHEN HEAP-PTR = NULL
SET MERGD-PTR TO HEAP-PTR
WHEN HEAP-NEXT = NULL
SET MERGD-PTR TO HEAP-PTR
WHEN OTHER
SET HEAP-PTRA TO HEAP-PTR
SET ADDRESS OF HEAPA TO HEAP-PTRA
SET HEAP-PTRB TO HEAP-NEXT
SET ADDRESS OF HEAPB TO HEAP-PTRB
SET HEAP-REST TO HEAPB-NEXT
SET ADDRESS OF REST TO HEAP-REST
SET HEAPA-NEXT TO NULL
SET HEAPB-NEXT TO NULL
CALL PGMQMERG USING HEAP-PTRA, HEAP-PTRB, MERG1-PTR
CALL PGMQ2PMG USING HEAP-REST, MERG2-PTR
CALL PGMQMERG USING MERG1-PTR, MERG2-PTR, MERGD-PTR
END-EVALUATE
GOBACK.
END PROGRAM PTYQ2PMG.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQPUSH RECURSIVE.
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
* UNCOMMENT WITH DEBUGGING CLAUSE FOR DEBUG LINES TO EXECUTE.
SOURCE-COMPUTER.
Z-SYSTEM
* WITH DEBUGGING MODE
.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 PTYQMERG PIC X(8) VALUE "PTYQMERG".
 
LINKAGE SECTION.
01 NODE-PTR POINTER.
 
01 LINK-KEY PIC S9(8) COMP-5.
 
01 HEAP-PTR POINTER.
 
01 PUSHD-PTR POINTER.
 
01 HEAP.
05 HEAP-KEY PIC S9(8) COMP-5.
05 HEAP-NEXT POINTER.
05 HEAP-DOWN POINTER.
 
01 NODE.
05 NODE-KEY PIC S9(8) COMP-5.
05 NODE-NEXT POINTER.
05 NODE-DOWN POINTER.
 
PROCEDURE DIVISION USING NODE-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR.
SET ADDRESS OF NODE TO NODE-PTR
SET ADDRESS OF HEAP TO HEAP-PTR
SET NODE-NEXT TO NULL
SET NODE-DOWN TO NULL
MOVE LINK-KEY TO NODE-KEY
CALL PTYQMERG USING NODE-PTR, HEAP-PTR, PUSHD-PTR
GOBACK.
END PROGRAM PTY2PUSH.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQPOP RECURSIVE.
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
* UNCOMMENT WITH DEBUGGING CLAUSE FOR DEBUG LINES TO EXECUTE.
SOURCE-COMPUTER.
Z-SYSTEM
* WITH DEBUGGING MODE
.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 PTYQ2PMG PIC X(8) VALUE "PTYQ2PMG".
 
LINKAGE SECTION.
01 HEAP-PTR POINTER.
 
01 POPPD-PTR POINTER.
 
01 HEAP.
05 HEAP-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAP-NEXT POINTER.
05 HEAP-DOWN POINTER.
 
PROCEDURE DIVISION USING HEAP-PTR, POPPD-PTR.
SET ADDRESS OF HEAP TO HEAP-PTR
CALL PTYQ2PMG USING HEAP-DOWN, POPPD-PTR
GOBACK.
END PROGRAM PTYQPOP.
</syntaxhighlight>
 
{{out}}
<pre>
+0000000001 SOLVE RC TASKS.
+0000000002 TAX RETURN.
+0000000003 CLEAR DRAINS.
+0000000004 FEED CAT.
+0000000005 MAKE TEA.
+0000000006 EAT SCONES.
</pre>
 
=={{header|CoffeeScript}}==
Line 4,364 ⟶ 4,677:
=={{header|Logtalk}}==
 
Logtalk comes with a [https://github.com/LogtalkDotOrg/logtalk3/tree/master/library/heaps heap implementation] out of the box. As such it by definition also has a priority queue. It can be used at the toplevel like this (with some formatting changes for clarity, and '<code>%'</code> marking comments that would not be in the output):
 
<syntaxhighlight lang="logtalk">?- logtalk_load(heaps(loader)). % also `{heaps(loader)}.` on most back-ends
Line 4,389 ⟶ 4,702:
heap(<)::top(H4, K4, V4). % K4=2, V4='Tax return'</syntaxhighlight>
 
Since `<code>heap`(Ordering)</code> is a parametrisedparametrized classobject in Logtalk, with the parameter being the ordering predicate, we actually use `<code>heap(<)`</code> object to get min ordering. There are two classesobjects provided in Logtalk that eliminate the unnecessary replication of the two most common orderings:
 
<syntaxhighlight lang="logtalk">:- object(minheap,
Line 4,416 ⟶ 4,729:
:- end_object.</syntaxhighlight>
 
Given the presence of these two classesobjects, all of the example code above could have `<code>heap(<)`</code> replaced with `<code>minheap`</code> for identical results (including identical performance). It also illustrates how quickly and easily other orderings could be provided at need.
 
=={{header|Lua}}==
Line 8,161 ⟶ 8,474:
Print
 
Proc _Insert(3, Dup("Clear drains")) ' insert the whole bunch
Proc _Insert(4, Dup("Feed cat"))
Proc _Insert(5, Dup("Make tea"))
Proc _Insert(1, Dup("Solve RC tasks"))
Proc _Insert(2, Dup("Tax return"))
 
For x = 0 To b: Proc _List(x) : Next ' list all entries
Line 8,181 ⟶ 8,494:
Local (2)
' return dummy on error
If b < 0 Then Return (Dup("0No such entry"))
a@ = @(0)) ' save the top entry
For b@ = 0 To Set(b, b - 1) : @(b@) = @(b@+1): Next
Line 8,448 ⟶ 8,761:
{{libheader|Wren-queue}}
The above module contains a PriorityQueue class. Unlike some other languages here, the higher the number, the higher the priority. So the 'Make tea' task has the highest priority and, thankfully, the cat has a good chance of being fed!
<syntaxhighlight lang="ecmascriptwren">import "./queue" for PriorityQueue
 
var tasks = PriorityQueue.new()
Line 8,662 ⟶ 8,975:
/// fn(T, T) bool
const Comparator = struct {
fn maxCompare(_: void, a: Task, b: Task) boolstd.math.Order {
return std.math.order(a.priority >, b.priority);
}
 
fn minCompare(_: void, a: Task, b: Task) boolstd.math.Order {
return std.math.order(a.priority <, b.priority);
}
};
Line 8,674 ⟶ 8,987:
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
varconst allocator = &arena.allocator();
var pq = PriorityQueue(Task, void, Comparator.maxCompare).init(allocator, {});
 
var pq = PriorityQueue(Task).init(allocator, Comparator.maxCompare);
defer pq.deinit();
 
Line 8,684 ⟶ 8,996:
try pq.add(Task.init(1, "Solve RC tasks"));
try pq.add(Task.init(2, "Tax returns"));
try testing.expectEqual(pq.count(), 5);
 
std.debug.print("\n", .{});
Line 8,691 ⟶ 9,003:
while (pq.count() != 0) {
const task = pq.remove();
std.debug.print("Executing: {s} (priority {d})\n", .{ task.name, task.priority });
}
std.debug.print("\n", .{});
Line 8,699 ⟶ 9,011:
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
varconst allocator = &arena.allocator();
var pq = PriorityQueue(Task, void, Comparator.minCompare).init(allocator, {});
 
var pq = PriorityQueue(Task).init(allocator, Comparator.minCompare);
defer pq.deinit();
 
Line 8,709 ⟶ 9,020:
try pq.add(Task.init(1, "Solve RC tasks"));
try pq.add(Task.init(2, "Tax returns"));
try testing.expectEqual(pq.count(), 5);
 
std.debug.print("\n", .{});
Line 8,716 ⟶ 9,027:
while (pq.count() != 0) {
const task = pq.remove();
std.debug.print("Executing: {s} (priority {d})\n", .{ task.name, task.priority });
}
std.debug.print("\n", .{});
}
 
</syntaxhighlight>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/340174...364343"