Priority queue: Difference between revisions
Content added Content deleted
(Added uBasic/4tH version) |
|||
Line 6,898: | Line 6,898: | ||
</pre> |
</pre> |
||
=={{header|uBasic/4tH}}== |
|||
This implementation inserts items using a binary search. Hence, no dequeuing is required, since all entries are always in order of priority. It also allows for listing of valid entries. |
|||
<lang>b = -1 ' b points to last entry on the queue |
|||
q = FUNC(_Grab) ' now grab the top value |
|||
' and display it |
|||
Print Peek(q, 0) - Ord("0"), Show(Chop(q, 1)) |
|||
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 |
|||
q = FUNC(_Grab) ' now grab the top value |
|||
Print ' and display it |
|||
Print Peek(q, 0) - Ord("0"), Show(Chop(q, 1)) |
|||
Print |
|||
For x = 0 To b: Proc _List(x) : Next ' list all entries |
|||
End |
|||
_Grab ' return and remove top entry |
|||
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 |
|||
Return (a@) |
|||
_List ' list any (valid) position on queue |
|||
Param (1) |
|||
If (a@ > b) = 0 Then Print Peek(@(a@), 0) - Ord("0"), Show(Chop(@(a@), 1)) |
|||
Return |
|||
_Insert ' insert an entry |
|||
Param (2) ' priority, task |
|||
Local (1) |
|||
c@ = FUNC(_binarySearch(a@, 0, b)) ' search the position |
|||
Proc _MakeRoom (c@) ' make room |
|||
@(c@) = Join(Str(a@), b@) ' assign the entry |
|||
Return |
|||
_binarySearch ' perform a binary search |
|||
Param(3) ' value, start index, end index |
|||
Local(1) ' The middle of the array |
|||
' Ok, signal we didn't find it |
|||
If c@ < b@ Then Return (b@) ' first entry on start |
|||
d@ = SHL(b@ + c@, -1) ' prevent overflow (LOL!) |
|||
If a@ < Peek(@(d@), 0) - Ord("0") Then Return (FUNC(_binarySearch (a@, b@, d@-1))) |
|||
If a@ > Peek(@(d@), 0) - Ord("0") Then Return (FUNC(_binarySearch (a@, d@+1, c@))) |
|||
If a@ = Peek(@(d@), 0) - Ord("0") Then Return (d@) |
|||
Return (-1) ' -1 on error |
|||
_MakeRoom ' make some space |
|||
Param (1) ' starting position |
|||
Local (1) |
|||
' from bottom to top |
|||
For b@ = Set(b, b+1) To a@ + 1 Step -1: @(b@) = @(b@-1) : Next |
|||
Return |
|||
</lang> |
|||
{{Out}} |
|||
First an entry is dequeued from an empty queue. Then all entries are inserted and listed. Finally, another entry is dequeued and the remainder of the entries is listed again. |
|||
<pre>0 No such entry |
|||
1 Solve RC tasks |
|||
2 Tax return |
|||
3 Clear drains |
|||
4 Feed cat |
|||
5 Make tea |
|||
1 Solve RC tasks |
|||
2 Tax return |
|||
3 Clear drains |
|||
4 Feed cat |
|||
5 Make tea |
|||
0 OK, 0:750 |
|||
</pre> |
|||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
<lang VB>Type Tuple |
<lang VB>Type Tuple |