Priority queue: Difference between revisions

=={{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>