(root)/src/nv/heapsort.asm – Rev 109
Rev 73 |
Blame |
Compare with Previous |
Last modification |
View Log
| Download
| RSS feed
;MAIN "HPTST",#16
;working assumptions:
;0000..7FFF -- code area
;8000..BFFF, C000..FFFF -- page switching area
;uses 2 pages for elements, 4 pages for strings
;strings are zero-terminated, cant cross page boundary
;switches pages on its own
;-------------------------------------------------------------------------------
;-------------------------------------------------------------------------------
HPSRT_init ;inits everything for a new sort
; LD HL,#4000
; LD (HS_s0free),HL
; LD (HS_s1free),HL
; LD (HS_s2free),HL
; LD (HS_s3free),HL
; LD H,L ;0
ld hl,0
LD (HS_enum),HL
RET
;HS_strpg DB #20 ;4 pages for strings
;HS_elpg DB #24 ;2 pages for elements
;free spaces in string pages
;HS_s0free DW 0
;HS_s1free DW 0
;HS_s2free DW 0
;HS_s3free DW 0
;elements array free offset
HS_enum DW 0 ;working number of elements
HS_num DW 0 ;final number of elements
HPSRT_add ;adds new element to heap, keeping heap property
;
; DE -- heap element (strptr)
;
;out: CY=1 - no space for the element
;
;kills: every reg
;check if there is place for new element
;max. 8192 els
;EXX
LD HL,(HS_enum)
INC HL
BIT 5,H
;JR Z,$+4
SCF
RET nz ;too many elements
LD (HS_enum),HL
DEC HL
PUSH HL
;num2addr
;ADD HL,HL
ADD HL,HL
;LD A,H
;RLCA
;RLCA
;AND 1
;LD B,A
;LD A,(HS_elpg)
;ADD A,B
PGW3elpg
LD A,#C0
OR H
LD H,A
;EXX
;LD A,D
;EXX
;LD (HL),A
;INC L
;EXX
;LD A,E
;EXX
;LD (HL),A
;INC L
;EXX
if HEAPSORT_LH
LD (HL),e
else
LD (HL),d
endif
;EXX
;LD (HL),A
INC L
;EXX
if HEAPSORT_LH
LD (HL),d
else
LD (HL),e
endif
;EXX
;LD (HL),A
POP HL
CALL HPSRT_upswap
OR A
RET
HPSRT_sort ;sorts array after all additions finished
LD HL,(HS_enum)
LD (HS_num),HL ;final number of elements
HS_s_loop
LD HL,(HS_enum)
;no sort if no elements
LD A,H
OR L
RET Z
;no sort if 1 element
DEC HL
LD A,H
OR L
RET Z
LD (HS_enum),HL ;1 element less to sort next time
;swap last element (in HL) with top
;ADD HL,HL
ADD HL,HL
;LD A,H
;RLCA
;RLCA
;AND 1
;LD B,A
;LD A,(HS_elpg)
;ADD A,B
PGW3elpg
LD A,H
OR #C0
LD H,A
LD DE,#8000
;LD A,(HS_elpg)
PGW2elpg0
DUP 1;3
LD A,(DE)
LD B,(HL)
EXD
LD (DE),A
LD (HL),B
INC E
INC L
EDUP
LD A,(DE)
LD B,(HL)
EXD
LD (DE),A
LD (HL),B
CALL HPSRT_downswap
JR HS_s_loop
;do downswap from the root to HS_enum
HPSRT_downswap
LD DE,0 ;root
HS_s_dswp_loop
;calc left leaf
LD H,D
LD L,E
ADD HL,HL
INC HL ;HL - left leaf
LD BC,(HS_enum) ; size of array
OR A
SBC HL,BC
RET NC ;no leafs
PUSH DE
LD A,H ;if result is #FFFF -
AND L ;only left leaf
ADD HL,BC
INC A
JR Z,HS_s_dswp_left
;have 2 leafs
LD D,H
LD E,L
INC DE ;DE - right leaf
PUSH HL,DE
CALL HPSRT_cmpel
;CY=1 - DE is smaller
;CY=0 - DE is equal or bigger
POP DE,HL
JR C,$+3
EXD
;now in HL is biggest leaf of two
HS_s_dswp_left
POP DE ;root
;HL is leaf to swap with
PUSH HL ;also next root
CALL HPSRT_cmpswap
POP DE
JR C,HS_s_dswp_loop
RET
HPSRT_upswap ;in: HL - number of leaf element to process
; swaps elements up to the root
LD A,H
OR L
RET Z
;calc root
LD D,H
LD E,L
dec de
SRL D
RR E
;JR C,$+3
;DEC DE
PUSH DE ;remember root el for possible recursion
CALL HPSRT_cmpswap
;restore root in HL
POP HL
RET NC ;exit if no swap
;tail recursion
JR HPSRT_upswap
HPSRT_cmpswap ;CY=1 if swap, CY=0 otherwise
;di
;jr $
;ei
EXD
ADD HL,HL
;ADD HL,HL
;LD A,H
;RLCA
;RLCA
;AND 1
;LD B,A
;LD A,(HS_elpg)
;ADD A,B
;PUSH AF ;pg num for root
PGW2elpg
;LD A,H
;AND #3F
;OR #80
;LD H,A
res 6,h
set 7,h
EXD
ADD HL,HL
;ADD HL,HL
;LD A,H
;RLCA
;RLCA
;AND 1
;LD B,A
;LD A,(HS_elpg)
;ADD A,B
;PUSH AF ;pg num for leaf
PGW3elpg
LD A,H
OR #C0
LD H,A
CALL HPSRT_cmp
;CY=0 - de is not smaller, no swap
JR C,HS_us_swp
;no swap - stop
POP HL
POP HL
RET
HS_us_swp
;POP AF
PGW3elpg
;POP AF
PGW2elpg
DUP 1;3
LD A,(DE)
LD B,(HL)
EXD
LD (DE),A
LD (HL),B
INC E
INC L
EDUP
LD A,(DE)
LD B,(HL)
EXD
LD (DE),A
LD (HL),B
SCF
RET
HPSRT_cmpel
;in: DE,HL - elements
;out: CY=1 if de is smaller, otherwise CY=0
;make offsets instead of el numbers, switch pages
; 8000-BFFF - for root el (DE)
; C000-FFFF - for leaf el (HL)
EXD
ADD HL,HL
;ADD HL,HL
LD A,H
RLCA
RLCA
AND 1
;LD B,A
;LD A,(HS_elpg)
;ADD A,B
PGW2elpg
;LD A,H
;AND #3F
;OR #80
;LD H,A
res 6,h
set 7,h
EXD
ADD HL,HL
;ADD HL,HL
LD A,H
RLCA
RLCA
AND 1
;LD B,A
;LD A,(HS_elpg)
;ADD A,B
PGW3elpg
LD A,H
OR #C0
LD H,A
HPSRT_cmp ;compare element pointed by HL
; with element pointed by DE
;we kill pages in W2 and W3
;but retain HL and DE
;out: CY=0 - DE is not smaller (may be upper in tree)
PUSH DE
PUSH HL
;compare dir/file, dir is always smaller
; LD A,(DE)
; XOR (HL)
; JP P,HS_cp_str
; ;signs differ: DE must be file to be greater
; LD A,(HL)
; RLCA
; POP HL
; POP DE
; RET
;HS_alonecmp
;get strings into DE,HL, also paging
EXD
;INC L
;INC L
LD A,(HL)
INC L
if HEAPSORT_LH
LD h,(HL)
LD l,A
;ld a,h
else
LD L,(HL)
LD H,A
endif
;RLCA
;RLCA
;AND 3
ld a,l
and 31
add a,(ix+PANEL.pgadd)
;LD B,A
;LD A,(HS_strpg)
;ADD A,B
PGW2strpg
ld a,l
and 0xe0
ld l,a
;LD A,H
;AND #3F
;OR #80
;LD H,A
res 6,h
set 7,h
EXD
;INC L
;INC L
LD A,(HL)
INC L
if HEAPSORT_LH
LD h,(HL)
LD l,A
;ld a,h
else
LD L,(HL)
LD H,A
endif
;RLCA
;RLCA
;AND 3
ld a,l
and 31
add a,(ix+PANEL.pgadd)
;LD B,A
;LD A,(HS_strpg)
;ADD A,B
PGW3strpg
ld a,l
and 0xe0
ld l,a
LD A,H
OR #C0
LD H,A
call comparer
ccf
pop hl
pop de
ret