.include "../platform/c64_0.oph"
.require "../platform/c64kernal.oph"
.outfile "structuredemo.prg"
jsr print'unsorted
jsr insertion'sort
jsr print'list
rts
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Linked list data: head, next, lb, hb.
; lb/hb: Low/high bytes of the data array. These are immutable and
; kept with the program text.
; head: Array index of the first element in the list, or #$FF if the
; list is empty
; next: Array of successor indices. If you've just read element X,
; the value of memory location next+X is the index of the
; next element. If next is #$FF, you've reached the end of
; the list.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
.data
.org $C000
.space head 1
.space next 16
.text
lb: .byte <$838,<$618,<$205,<$984,<$724,<$301,<$249,<$946
.byte <$925,<$043,<$114,<$697,<$985,<$633,<$312,<$086
hb: .byte >$838,>$618,>$205,>$984,>$724,>$301,>$249,>$946
.byte >$925,>$043,>$114,>$697,>$985,>$633,>$312,>$086
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; insertion'sort: Sorts the list defined by head, next, hb, lb.
; Arguments: None.
; Modifies: All registers destroyed, head and next array sorted.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
insertion'sort:
lda #$FF ; Clear list by storing the terminator in 'head'
sta head
ldx #$0 ; Loop through the lb/hb array, adding each
insertion'sort'loop: ; element one at a time
txa
pha
jsr insert_elt
pla
tax
inx
cpx #$10
bne insertion'sort'loop
rts
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; insert_elt: Insert an element into the linked list. Maintains the
; list in sorted, ascending order. Used by
; insertion'sort.
; Arguments: X register holds the index of the element to add.
; Modifies: All registers destroyed; head and next arrays updated
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
.data
.space lbtoinsert 1
.space hbtoinsert 1
.space indextoinsert 1
.text
insert_elt:
ldy head ; If the list is empty, make
cpy #$FF ; head point at it, and return.
bne insert_elt'list'not'empty
stx head
tya
sta next,x
rts
insert_elt'list'not'empty:
lda lb,x ; Cache the data we're inserting
sta lbtoinsert
lda hb,x
sta hbtoinsert
stx indextoinsert
ldy head ; Compare the first value with
sec ; the data. If the data must
lda lb,y ; be inserted at the front...
sbc lbtoinsert
lda hb,y
sbc hbtoinsert
bmi insert_elt'not'smallest
tya ; Set its next pointer to the
sta next,x ; old head, update the head
stx head ; pointer, and return.
rts
insert_elt'not'smallest:
ldx head
insert_elt'loop: ; At this point, we know that
lda next,x ; argument > data[X].
tay
cpy #$FF ; if next[X] = #$FF, insert arg at end.
beq insert_elt'insert'after'current
lda lb,y ; Otherwise, compare arg to
sec ; data[next[X]]. If we insert
sbc lbtoinsert ; before that...
lda hb,y
sbc hbtoinsert
bmi insert_elt'goto'next
insert_elt'insert'after'current: ; Fix up all the next links
tya
ldy indextoinsert
sta next,y
tya
sta next,x
rts ; and return.
insert_elt'goto'next: ; Otherwise, let X = next[X]
tya ; and go looping again.
tax
jmp insert_elt'loop
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; print'unsorted: Steps through the data array and prints each value.
; Standalone procedure.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
print'unsorted:
lda #<unsorted'hdr
ldx #>unsorted'hdr
jsr put'string
ldy #$00
print'unsorted'loop:
lda hb, Y
jsr print'hex
lda lb, y
jsr print'hex
lda #$20
jsr chrout
iny
cpy #$10
bne print'unsorted'loop
lda #$0D
jsr chrout
rts
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; print'list: Starts at head, and prints out every value in the
; linked list.
; Standalone procedure.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
print'list:
lda #<sorted'hdr
ldx #>sorted'hdr
jsr put'string
ldy head
print'list'loop:
cpy #$FF
beq print'list'done
lda hb, y
jsr print'hex
lda lb, y
jsr print'hex
lda #$20
jsr chrout
lda next, Y
tay
jmp print'list'loop
print'list'done:
lda #$0d
jsr chrout
rts
;; String data for the above routines.
unsorted'hdr:
.byte 147 ; Clear screen first!
.byte "UNSORTED DATA:",13,0
sorted'hdr:
.byte "SORTED DATA:",13,0
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; print'hex: outputs a two-character hex representation of a one-
; byte value.
; Arguments: Byte to print in accumulator
; Modifies: .A and .X
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
print'hex:
pha
clc
lsr
lsr
lsr
lsr
tax
lda hexstr,x
jsr chrout
pla
and #$0F
tax
lda hexstr,X
jsr chrout
rts
; Character data array for print'hex.
hexstr: .byte "0123456789ABCDEF"
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; put'string: outputs a C-style null terminated string with length
; less than 256 to the screen. If 256 bytes are written
; without finding a terminator, the routine ends quietly.
; Arguments: Low byte of string address in .A, high byte in .X
; Modifies: .A and .Y
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
.data zp
.space put'string'addr 2
.text
put'string:
sta put'string'addr
stx put'string'addr+1
ldy #$00
put'string'loop:
lda (put'string'addr),y
beq put'string'done
jsr chrout
iny
bne put'string'loop
put'string'done:
rts
|