Esimerkki & kirjasto:
Code: Select all
Type Potilas
Field nimi As String
Field tauti As String
EndType
rekisteri = makeHeap()
alku:
koko = heapSize(rekisteri)
AddText "Potilaita rekisterissä: " + koko
AddText ""
AddText "1. Lisää potilas"
If koko > 0 Then AddText "2. Hae kiireellisin potilas"
Repeat
If KeyHit(cbKey1) Or KeyHit(79) Then
ClearText
ClearKeys
Goto syota
EndIf
If koko > 0 And (KeyHit(cbKey2) Or KeyHit(80)) Then
ClearText
ClearKeys
Goto hae
EndIf
DrawScreen
Forever
syota:
Repeat
nimi$ = Input("Syötä nimi: ")
DrawScreen
Until KeyHit(cbKeyReturn)
CloseInput
AddText "Syötä nimi: " + nimi
Repeat
tauti$ = Input("Syötä tauti: ")
DrawScreen
Until KeyHit(cbKeyReturn)
CloseInput
AddText "Syötä tauti: " + tauti
Repeat
kiire = Input("Syötä kiireellisyys (kokonaisluku): ")
DrawScreen
Until KeyHit(cbKeyReturn)
CloseInput
AddText "Syötä kiireellisyys (kokonaisluku): " + kiire
pot.Potilas = New(Potilas)
pot\nimi = nimi
pot\tauti = tauti
heapAdd(rekisteri, kiire, ConvertToInteger(pot))
AddText "Potilas lisätty! Paina enter poistuaksesi..."
Repeat
DrawScreen
Until KeyHit(cbKeyReturn)
ClearText
Goto alku
hae:
kiire = heapGetFirstKey(rekisteri)
pot.Potilas = ConvertToType(heapGetFirst(rekisteri))
heapPopFirst(rekisteri)
AddText "Potilas " + pot\nimi
AddText "Tauti: " + pot\tauti
AddText "Kiireellisyys: " + kiire
Repeat
DrawScreen
Until KeyHit(cbKeyReturn)
ClearText
Goto alku
//////////////
// Kirjasto //
//////////////
Function makeHeap(reserved = 0)
// Luodaan muistapala keolle
heap = MakeMEMBlock(reserved * 8 + 8)
PokeInt heap, 0, reserved // Varattu koko
PokeInt heap, 0, 0 // Keon oikea koko
Return heap
EndFunction
Function heapAdd(heap, key, value)
reserved = PeekInt(heap, 0)
size = PeekInt(heap, 4)
// Jos keossa ei ole vapaata tilaa
If reserved <= size Then
// Tuplataan varattu tila
reserved = reserved * 2
If reserved = 0 Then reserved = 1
ResizeMEMBlock heap, reserved * 8 + 8
PokeInt heap, 0, reserved
EndIf
// Kokoa on kasvatettu yhdellä
size = size + 1
PokeInt heap, 4, size
// Asetetaan viimeiselle paikalle
PokeInt heap, 8 * size, key
PokeInt heap, 8 * size + 4, value
// Nostetaan keossa ylöspäin paikalleen
heapShiftUp(heap, size)
EndFunction
Function heapGetFirst(heap)
If PeekInt(heap, 4) = 0 Then MakeError "Et voi ottaa tyhjästä keosta!"
Return PeekInt(heap, 12)
EndFunction
Function heapGetFirstKey(heap)
If PeekInt(heap, 4) = 0 Then MakeError "Et voi ottaa tyhjästä keosta!"
Return PeekInt(heap, 8)
EndFunction
Function heapPopFirst(heap)
size = PeekInt(heap, 4)
If size = 0 Then MakeError "Et voi poistaa tyhjästä keosta!"
PokeInt heap, 4, size - 1
// Vaihdetaan viimeinen poistetun tilalle ja järjestetään keko
heapSwap(heap, 1, size)
heapHeapify(heap, 1)
EndFunction
Function heapSize(heap)
Return PeekInt(heap, 4)
EndFunction
// Under the hood (jos koodin sisäinen toiminta ei kiinnosta, älä katso tänne)
// HEAP Muistipalan rakenne
// 0 Keon varattu koko n
// 4 Keon käytetty koko
// 8 Indeksi 1
// 12 Arvo 1
// 16 Indeksi 2
// 24 Arvo 2
// ... ...
// 8n Indeksi n
// 8n+4 Arvo n
// KOKO 8n + 8
Function heapHeapify(heap, i)
size = PeekInt(heap, 4)
l = i * 2
r = i * 2 + 1
j = i
If l <= size Then
If PeekInt(heap, l * 8) < PeekInt(heap, i * 8) Then
j = l
EndIf
EndIf
If r <= size Then
If PeekInt(heap, r * 8) < PeekInt(heap, j * 8) Then
j = r
EndIf
EndIf
If Not i = j Then
heapSwap(heap, i, j)
heapHeapify(heap, j)
EndIf
EndFunction
Function heapShiftUp(heap, i)
l = i / 2
If l > 0 Then
If PeekInt(heap, l * 8) > PeekInt(heap, i * 8) Then
heapSwap(heap, i, l)
heapShiftUp(heap, l)
EndIf
EndIf
EndFunction
Function heapSwap(heap, i, l)
// Otetaan talteen i
tempKey = PeekInt(heap, i * 8)
tempValue = PeekInt(heap, i * 8 + 4)
// Tallennetaan i tilalle l
PokeInt heap, i * 8, PeekInt(heap, l * 8)
PokeInt heap, i * 8 + 4, PeekInt(heap, l * 8 + 4)
// Tallennetaan l tilalle i
PokeInt heap, l * 8, tempKey
PokeInt heap, l * 8 + 4, tempValue
EndFunction