comparison lab4/test/ptr.p @ 0:bfdcc3820b32

Basis
author Mike Spivey <mike@cs.ox.ac.uk>
date Thu, 05 Oct 2017 08:04:15 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:bfdcc3820b32
1 (* Pointer-linked trees *)
2
3 type
4 tree = pointer to node;
5 node = record left, right: tree end;
6
7 proc build(n: integer): tree;
8 var t: tree;
9 begin
10 if n <= 1 then
11 return nil
12 else
13 new(t);
14 t^.left := build(n-2);
15 t^.right := build(n-1);
16 return t
17 end
18 end;
19
20 proc print(t: tree);
21 var tt: tree;
22 begin
23 tt := t;
24 if tt = nil then
25 print_char('.')
26 else
27 print_char('(');
28 print(tt^.left);
29 print(tt^.right);
30 print_char(')')
31 end
32 end;
33
34 proc count(t: tree): integer;
35 var tt: tree;
36 begin
37 tt := t;
38 if tt = nil then
39 return 1
40 else
41 return count(tt^.left) + count(tt^.right)
42 end
43 end;
44
45 var n: integer; p: tree;
46
47 begin
48 for n := 0 to 7 do
49 p := build(n);
50 print_num(count(p)); print_char(' ');
51 print(p); newline()
52 end
53 end.
54
55 (*<<
56 1 .
57 1 .
58 2 (..)
59 3 (.(..))
60 5 ((..)(.(..)))
61 8 ((.(..))((..)(.(..))))
62 13 (((..)(.(..)))((.(..))((..)(.(..)))))
63 21 (((.(..))((..)(.(..))))(((..)(.(..)))((.(..))((..)(.(..))))))
64 >>*)
65
66 (*[[
67 @ picoPascal compiler output
68 .include "fixup.s"
69 .global pmain
70
71 @ proc build(n: integer): tree;
72 .text
73 _build:
74 mov ip, sp
75 stmfd sp!, {r0-r1}
76 stmfd sp!, {r4-r10, fp, ip, lr}
77 mov fp, sp
78 @ if n <= 1 then
79 ldr r0, [fp, #40]
80 cmp r0, #1
81 bgt .L3
82 @ return nil
83 mov r0, #0
84 b .L1
85 .L3:
86 @ new(t);
87 mov r0, #8
88 bl new
89 mov r4, r0
90 @ t^.left := build(n-2);
91 ldr r0, [fp, #40]
92 sub r0, r0, #2
93 bl _build
94 str r0, [r4]
95 @ t^.right := build(n-1);
96 ldr r0, [fp, #40]
97 sub r0, r0, #1
98 bl _build
99 str r0, [r4, #4]
100 @ return t
101 mov r0, r4
102 .L1:
103 ldmfd fp, {r4-r10, fp, sp, pc}
104 .ltorg
105
106 @ proc print(t: tree);
107 _print:
108 mov ip, sp
109 stmfd sp!, {r0-r1}
110 stmfd sp!, {r4-r10, fp, ip, lr}
111 mov fp, sp
112 @ tt := t;
113 ldr r4, [fp, #40]
114 @ if tt = nil then
115 cmp r4, #0
116 bne .L7
117 @ print_char('.')
118 mov r0, #46
119 bl print_char
120 b .L5
121 .L7:
122 @ print_char('(');
123 mov r0, #40
124 bl print_char
125 @ print(tt^.left);
126 ldr r0, [r4]
127 bl _print
128 @ print(tt^.right);
129 ldr r0, [r4, #4]
130 bl _print
131 @ print_char(')')
132 mov r0, #41
133 bl print_char
134 .L5:
135 ldmfd fp, {r4-r10, fp, sp, pc}
136 .ltorg
137
138 @ proc count(t: tree): integer;
139 _count:
140 mov ip, sp
141 stmfd sp!, {r0-r1}
142 stmfd sp!, {r4-r10, fp, ip, lr}
143 mov fp, sp
144 @ tt := t;
145 ldr r4, [fp, #40]
146 @ if tt = nil then
147 cmp r4, #0
148 bne .L11
149 @ return 1
150 mov r0, #1
151 b .L9
152 .L11:
153 @ return count(tt^.left) + count(tt^.right)
154 ldr r0, [r4]
155 bl _count
156 mov r5, r0
157 ldr r0, [r4, #4]
158 bl _count
159 add r0, r5, r0
160 .L9:
161 ldmfd fp, {r4-r10, fp, sp, pc}
162 .ltorg
163
164 pmain:
165 mov ip, sp
166 stmfd sp!, {r4-r10, fp, ip, lr}
167 mov fp, sp
168 @ for n := 0 to 7 do
169 mov r0, #0
170 set r1, _n
171 str r0, [r1]
172 mov r4, #7
173 .L14:
174 set r0, _n
175 ldr r5, [r0]
176 cmp r5, r4
177 bgt .L13
178 @ p := build(n);
179 mov r0, r5
180 bl _build
181 set r1, _p
182 str r0, [r1]
183 @ print_num(count(p)); print_char(' ');
184 bl _count
185 bl print_num
186 mov r0, #32
187 bl print_char
188 @ print(p); newline()
189 set r0, _p
190 ldr r0, [r0]
191 bl _print
192 bl newline
193 set r5, _n
194 ldr r0, [r5]
195 add r0, r0, #1
196 str r0, [r5]
197 b .L14
198 .L13:
199 ldmfd fp, {r4-r10, fp, sp, pc}
200 .ltorg
201
202 .comm _n, 4, 4
203 .comm _p, 4, 4
204 @ End
205 ]]*)