1; void adt_HeapSiftDown(uint start, void **array, uint n, void *compare)
2; 03.2003, 08.2005 aralbrec
3
4SECTION code_clib
5PUBLIC ADTHeapSiftDown
6EXTERN l_jpix
7
8; enter:  DE = start index * 2 (offset into array in bytes)
9;         BC = array address
10;         IX = compare (de) < (hl)? set carry if true  MUST PRESERVE BC,DE,HL,IX
11;         HL = N * 2 (number of items in array * 2)
12; uses :  AF,DE,HL,AF'
13
14
15.ADTHeapSiftDown
16   push hl                     ; stack = N * 2
17   ld l,e
18   ld h,d
19   add hl,hl
20   ex de,hl                    ; de = child index * 2
21   add hl,bc
22   ex (sp),hl                  ; hl = N * 2, stack = &array[parent]
23
24; de = child index * 2
25; hl = N * 2
26; bc = array address
27; stack = &array[parent]
28
29.while
30   ld a,d                      ; if child < N not done yet
31   cp h
32   jr c, cont
33   jr nz, done
34   ld a,e
35   cp l
36   jr nc, done
37
38.cont
39   ex (sp),hl
40   push hl
41   push de                     ; stack = N * 2, &array[parent], child index * 2
42
43   ex de,hl
44   add hl,bc
45   ld e,l
46   ld d,h                      ; de = &array[child]
47   inc hl
48   inc hl                      ; hl = &array[child+1]
49   call l_jpix                 ; is child < child+1? (de) < (hl)?
50   pop hl
51   jr c, skip                  ; branch if child smaller
52   inc hl
53   inc hl                      ; hl = child+1 index * 2
54   inc de
55   inc de                      ; de = &array[child+1]
56
57.skip                          ; hl = child index * 2; de = &array[child]; stack = N * 2, &array[parent]
58   ex (sp),hl                  ; hl = &array[parent]; stack = N * 2, child index * 2
59   call l_jpix                 ; is child < parent? (de) < (hl)
60   jr nc, done2                ; if parent smaller it's in right place so done
61
62   ld a,(de)                   ; swap(child, parent)
63   ex af,af
64   ld a,(hl)
65   ld (de),a
66   ex af,af
67   ld (hl),a
68   inc hl
69   inc de
70   ld a,(de)
71   ex af,af
72   ld a,(hl)
73   ld (de),a
74   ex af,af
75   ld (hl),a
76
77   pop hl
78   add hl,hl                   ; hl = new child index * 2
79   dec de                      ; de = &array[new parent which was old child]
80   ex de,hl                    ; hl = &array[parent], de = child index * 2
81   ex (sp),hl                  ; hl = N * 2, stack = &array[parent]
82   jp while
83
84.done                          ; one last item to worry about
85   sbc hl,de                   ; carry reset at this point
86   jr nz, reallydone           ; if child != N we are really done, otherwise one more compare to do
87
88   ex de,hl
89   add hl,bc                   ; hl = &array[child]
90   pop de                      ; de = &array[parent]
91   ex de,hl                    ; hl = &array[parent], de = &array[child]
92   call l_jpix                 ; is child < parent? (de) < (hl)?
93   ret nc                      ; if no, things are as they should be
94
95   ld a,(de)                   ; swap(child, parent)
96   ex af,af
97   ld a,(hl)
98   ld (de),a
99   ex af,af
100   ld (hl),a
101   inc hl
102   inc de
103   ld a,(de)
104   ex af,af
105   ld a,(hl)
106   ld (de),a
107   ex af,af
108   ld (hl),a
109   ret
110
111.done2
112   pop af
113.reallydone
114   pop af
115   ret
116