116 lines
4.0 KiB
Plaintext
116 lines
4.0 KiB
Plaintext
Module UnOrderedArray {
|
|
Class PriorityQueue {
|
|
Private:
|
|
Dim Item()
|
|
many=0, level=0, first
|
|
cmp = lambda->0
|
|
Module Reduce {
|
|
if .many<.first*2 then exit
|
|
if .level<.many/2 then .many/=2 : Dim .Item(.many)
|
|
}
|
|
Public:
|
|
Module Clear {
|
|
Dim .Item() \\ erase all
|
|
.many<=0 \\ default
|
|
.Level<=0
|
|
}
|
|
Module Add {
|
|
if .level=.many then
|
|
if .many=0 then Error "Define Size First"
|
|
Dim .Item(.many*2)
|
|
.many*=2
|
|
end if
|
|
Read Item
|
|
if .level=0 then
|
|
.Item(0)=Item
|
|
else.If .cmp(.Item(0), Item)=-1 then \\ Item is max
|
|
.Item(.level)=Item
|
|
swap .Item(0), .Item(.level)
|
|
else
|
|
.Item(.level)=Item
|
|
end if
|
|
.level++
|
|
}
|
|
Function Peek {
|
|
if .level=0 then error "empty"
|
|
=.Item(0)
|
|
}
|
|
Function Poll {
|
|
if .level=0 then error "empty"
|
|
=.Item(0)
|
|
if .level=2 then
|
|
swap .Item(0), .Item(1)
|
|
.Item(1)=0
|
|
.Level<=1
|
|
else.If .level>2 then
|
|
.Level--
|
|
Swap .Item(.level), .Item(0)
|
|
.Item(.level)=0
|
|
for I=.level-1 to 1
|
|
if .cmp(.Item(I), .Item(I-1))=1 then Swap .Item(I), .Item(I-1)
|
|
next
|
|
else
|
|
.level<=0 : .Item(0)=0
|
|
end if
|
|
.Reduce
|
|
}
|
|
Module Remove {
|
|
if .level=0 then error "empty"
|
|
Read Item
|
|
k=true
|
|
if .cmp(.Item(0), Item)=0 then
|
|
Item=.Poll()
|
|
K~ \\ k=false
|
|
else.If .Level>1 then
|
|
I2=.Level-1
|
|
for I=1 to I2
|
|
if k then
|
|
if .cmp(.Item(I), Item)=0 then
|
|
if I<I2 then Swap .Item(I), .Item(I2)
|
|
.Item(I2)=0
|
|
k=false
|
|
end if
|
|
else
|
|
exit
|
|
end if
|
|
next
|
|
.Level--
|
|
end if
|
|
if k then Error "Not Found"
|
|
.Reduce
|
|
}
|
|
Function Size {
|
|
if .many=0 then Error "Define Size First"
|
|
=.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$
|
|
End Sub
|
|
}
|
|
UnOrderedArray
|