SortedStack.TXT

\ SortedStack.TXT
0 [IF]
Kode i Forth til at oprette og bruge en form for "stack"med Max 81 entries
hvor entry position afhænger af tal værdi i entry. m.a.o.
en sorteret liste hvor øverste, d.v s den med laveste adresse i
RAM indeholder entry med laveste indholds værdi.
flere entries kan have samme værdi.
Tages øverste entry den med laveste værdi ud,
skal der peges på den næste i "stakken"


Her er et enkelt eksempel på en sorteret “stack” i Forth,
implementeret som et array med maks 81 entries (indeks 0..80).
Laveste værdi ligger altid på laveste adresse;
flere entries kan have samme værdi, og “toppen” er altid element 0.
[THEN]

\ Grundlæggende datastruktur

81 CONSTANT MAX-ENTRIES

CREATE s-array   MAX-ENTRIES CELLS ALLOT  \ selve feltet
VARIABLE s-count                     \ antal brugte entries (0..MAX-ENTRIES)

\ s-array rummer op til 81 celler, og s-count fortæller hvor
\ mange der aktuelt er i brug (0 betyder tom).

\ Hjælpeord til at få adresse på element i (0‑baseret indeks):

: s-cell   ( i -- addr )
   CELLS s-array + ;

\ Indsæt værdi sorteret (laveste først)
\ Når vi indsætter en værdi x, finder vi første element der er større end x,
\ skubber resten én plads ned og lægger x ind dér:


: s-insert   ( x -- )
   s-count @ MAX-ENTRIES = IF
      DROP EXIT        \ fuld, ignorer eller håndter fejl
   THEN

   \ find indsætningsposition i (første > x)
   s-count @ 0 ?DO
      DUP              \ x
      I s-cell @       \ x a[i]
      > IF             \ hvis a[i] > x, så indsæt her
         DROP I LEAVE
      THEN
   LOOP                \ her ligger indekset i på stakken

   \ i = indsætningsposition
   DUP >R              \ gem i på returstack
   s-count @           \ s-count i
   BEGIN
      DUP R@ >         \ j > i ?
   WHILE
      DUP 1-           \ j j-1
      2DUP             \ j j-1 j j-1
      s-cell @         \ j j-1 val
      SWAP s-cell !    \ flyt val fra j-1 til j
      1-               \ j--
   REPEAT
   DROP R>             \ fjern j, hent i

   \ læg værdien ind
   s-cell !            \ i s-cell ! (x var i DUP’en øverst)

   \ opdatér count
   s-count @ 1+ s-count ! ;

\ Brug: 42 s-insert indsætter 42 på korrekt sorteret plads.

\ Hent og fjern “øverste” (mindste) entry
\ Øverste entry er altid element 0; når vi tager den ud,
\ skubber vi resten én plads op:

: s-pop   ( -- x | )  \ returnerer mindste værdi, eller gør intet hvis tom
   s-count @ 0= IF
      EXIT            \ tom
   THEN

   \ tag mindste værdi
   0 s-cell @

   \ skub resten op
   s-count @ 1- 0 ?DO
      I 1+ s-cell @
      I     s-cell !
   LOOP

   \ opdatér count
   s-count @ 1- s-count ! ;

\ Brug:

10 s-insert
5  s-insert
20 s-insert

s-pop .    \ skriver 5
s-pop .    \ skriver 10
s-pop .    \ skriver 20