Priority queue: Difference between revisions
m
→{{header|M2000 Interpreter}}
(Frink) |
|||
Line 4,415:
Module Reduce {
if .many<.first*2 then exit
}
Public:
Module Clear {
Dim .Item() \\ erase all
.many<=0 \\ default
.Level<=0
}
Module Add {
Dim .Item(.many*2)
.many*=2
Read Item
.Item(0)=Item
.Item(.level)=Item
swap .Item(0), .Item(.level)
.Item(.level)=Item
end if
.level++
}
Function Peek {
=.Item(0)
}
Function Poll {
=.Item(0)
swap .Item(0), .Item(1)
.Item(1)=0
.Level<=1
.Level--
Swap .Item(.level), .Item(0)
.Item(.level)=0
.level<=0 : .Item(0)=0
end if
.Reduce
}
Module Remove {
Read Item
k=true
Item=.Poll()
K~ \\ k=false
I2=.Level-1
.Item(I2)=0
k=false
end if
next
.Level--
.Reduce
}
Function Size {
=.Level
}
Class:
Module PriorityQueue {
if .many>0 then Error "Clear List First"
Read .many, .cmp
.first<=.many
Dim .Item(.many)
}
}
Class Item { X, S$
Class: // constructor as temporary definition
Module Item {Read .X, .S$}
}
Queue=PriorityQueue(100, Lambda -> {Read A,B : =Compare(A.X,B.X)})
Queue.Add Item(3, "Clear drains") : Gosub PrintTop()
Queue.Add Item(4 ,"Feed cat") : PrintTop()
Queue.Add Item(5 ,"Make tea") : PrintTop()
Queue.Add Item(1 ,"Solve RC tasks") : PrintTop()
Queue.Add Item(2 ,"Tax return") : PrintTop()
Print "remove items"
While true
MM=Queue.Poll() :Print MM.X, MM.S$,,"Size="; Queue.Size()
if Queue.Size()=0 then exit
PrintTop()
End While
Sub PrintTop()
M=Queue.Peek() : Print "Item ";M.X, M.S$
}
UnOrderedArray
Line 4,526 ⟶ 4,525:
===Using a stack with arrays as elements===
Every insertion push item using binary search in proper position. Pop is very fast. Cons() used for demo purposes, make a new array from a series of arrays (a=cons(a,a) add to a an a . Variable a is a pointer to array (a tuple)
<syntaxhighlight lang="m2000 interpreter">
Module PriorityQueue {
a= (
a=cons(a, ((1 ,"Solve RC tasks"), ( 2 , "Tax return")))
b=stack
comp=lambda (a, b) ->
module InsertPQ (a, n, &comp) {
if len(a)=0 then stack a {data n} : exit
Line 4,541 ⟶ 4,540:
t=2: b=len(a)
m=b
while t<=b
t1=m
m=(b+t) div 2
Line 4,548 ⟶ 4,547:
b=m-1
m=b
if m>1 then shiftback m
}
Line 4,554 ⟶ 4,553:
n=each(a)
while n
InsertPq b, array(n), &comp
n1=each(b)
while n1
m=stackitem(n1)
\\ Peek topitem (without popping)
\\ Pop item
Stack b {
Read old
}
Function Pop$(a) {
stack a {
Line 4,578 ⟶ 4,577:
}
}
while not
}
PriorityQueue
</syntaxhighlight>
Line 4,598 ⟶ 4,594:
class obj {
x, s$
module obj (.x, .s$) {}
}
Line 4,650 ⟶ 4,646:
Print Pop$(b)
}
}
PriorityQueueForGroups
</syntaxhighlight>
===Using a stack with pointers to Groups as elements===
Now we use pointer to group, and use of Subs and simple Functions (called using @ prefix). Also we have a global countmany (is a long type, see 0&) to check how many objects exist. We have use "as *obj" to declare a parameter to stay as pointer and to check the type (here is obj). The remove method of object called when object has to be removed. The constructor module obj called once and not exist in the final object obj (it is a part under Class: label, and this part define things for construction time only). Property toString$ is a group which return value (a string value), and we can use it with or without parameter. Because it is a group, we have to link parent properties/functions (but not modules) to get access.
<syntaxhighlight lang="m2000 interpreter">
// using pointers to objects
global countmany=0&
class obj {
x, s$
property toString$ {
value (sp=8) {
link parent x, s$ to x, s$
value$=format$("{0::-5}"+string$(" ", sp)+"{1:20}", x, s$)
}
}
remove {
countmany--
}
class:
module obj (.x, .s$) {countmany++}
}
// obj() return object as value (using a special pointer)
function global g(priority, task$) {
// here we return an object using nonrmal pointer
// try to change -> to = to see the error
->obj(priority, task$)
}
Module PriorityQueueForGroups {
Flush ' empty current stack
Data g(3, "Clear drains"),g(4 ,"Feed cat"), g( 5 , "Make tea")
Data g( 1 ,"Solve RC tasks"), g( 2 , "Tax return")
ObjectCount()
b=stack
while not empty
InsertPQ(b) // top of stack is b then objects follow
end while
ObjectCount()
Print "Using Peek to Examine Priority Queue"
n1=each(b)
Header()
while n1
Print @Peek$(n1)
end while
ObjectCount()
Header()
while not @isEmpty(b)
Print @Pop(b)=>tostring$
end while
ObjectCount()
// here are the subs/simple functions
// these are static parts of module
sub Header()
Print " Priority Task"
Print "========== ================"
end sub
sub ObjectCount()
Print "There are ";countmany;" objects of type obj"
end sub
sub InsertPQ(a, n as *obj)
Print "Insert:";n=>tostring$(1)
if len(a)=0 then stack a {data n} : exit sub
if @comp(n, stackitem(a)) then stack a {push n} : exit sub
stack a {
push n
local t=2, b=len(a)
local m=b
while t<=b
t1=m
m=(b+t) div 2
if m=0 then m=t1 : exit
If @comp(stackitem(m),n) then t=m+1: continue
b=m-1
m=b
end while
if m>1 then shiftback m
}
end sub
function comp(a as *obj, b as *obj)
=a=>x<b=>x
end function
function Peek$(a as stack)
=stackitem(a)=>toString$
end function
function IsEmpty(a)
=len(a)=0
end function
Function Pop(a)
// Group make a copy
stack a {=Group}
end function
}
PriorityQueueForGroups
| |||