127 by (Asm_simp_tac 1); |
127 by (Asm_simp_tac 1); |
128 by (case_tac "x<nat" 1); |
128 by (case_tac "x<nat" 1); |
129 by (case_tac "height (insert x tree1) = Suc (Suc (height tree2))" 1); |
129 by (case_tac "height (insert x tree1) = Suc (Suc (height tree2))" 1); |
130 by (forw_inst_tac [("n","nat")] height_l_bal 1); |
130 by (forw_inst_tac [("n","nat")] height_l_bal 1); |
131 by (asm_full_simp_tac (simpset() addsimps [max_def]) 1); |
131 by (asm_full_simp_tac (simpset() addsimps [max_def]) 1); |
132 by(fast_tac (claset() addss simpset()) 1); |
132 by (fast_tac (claset() addss simpset()) 1); |
133 by (asm_full_simp_tac (simpset() addsimps [max_def]) 1); |
133 by (asm_full_simp_tac (simpset() addsimps [max_def]) 1); |
134 by(fast_tac (claset() addss simpset()) 1); |
134 by (fast_tac (claset() addss simpset()) 1); |
135 by (case_tac "height (insert x tree2) = Suc (Suc (height tree1))" 1); |
135 by (case_tac "height (insert x tree2) = Suc (Suc (height tree1))" 1); |
136 by (forw_inst_tac [("n","nat")] height_r_bal 1); |
136 by (forw_inst_tac [("n","nat")] height_r_bal 1); |
137 by (asm_full_simp_tac (simpset() addsimps [max_def]) 1); |
137 by (asm_full_simp_tac (simpset() addsimps [max_def]) 1); |
138 by(fast_tac (claset() addss simpset()) 1); |
138 by (fast_tac (claset() addss simpset()) 1); |
139 by (asm_full_simp_tac (simpset() addsimps [max_def]) 1); |
139 by (asm_full_simp_tac (simpset() addsimps [max_def]) 1); |
140 by(fast_tac (claset() addss simpset()) 1); |
140 by (fast_tac (claset() addss simpset()) 1); |
141 qed_spec_mp "height_insert"; |
141 qed_spec_mp "height_insert"; |
142 |
142 |
143 |
143 |
144 Goal |
144 Goal |
145 "!!x. [| height (insert x l) ~= Suc(Suc(height r)); isbal (insert x l); isbal (MKT n l r) |] \ |
145 "!!x. [| height (insert x l) ~= Suc(Suc(height r)); isbal (insert x l); isbal (MKT n l r) |] \ |
172 by (fast_tac (claset() addIs [isbal_lr_rot] addss (simpset() |
172 by (fast_tac (claset() addIs [isbal_lr_rot] addss (simpset() |
173 addsimps [l_bal_def])) 1); |
173 addsimps [l_bal_def])) 1); |
174 by (fast_tac (claset() addIs [isbal_r_rot] addss (simpset() |
174 by (fast_tac (claset() addIs [isbal_r_rot] addss (simpset() |
175 addsimps [l_bal_def])) 1); |
175 addsimps [l_bal_def])) 1); |
176 by (Clarify_tac 1); |
176 by (Clarify_tac 1); |
177 by (forward_tac [isbal_insert_left] 1); |
177 by (ftac isbal_insert_left 1); |
178 by (Asm_full_simp_tac 1); |
178 by (Asm_full_simp_tac 1); |
179 ba 1; |
179 by (assume_tac 1); |
180 by (Asm_full_simp_tac 1); |
180 by (Asm_full_simp_tac 1); |
181 by (case_tac "height (insert x tree2) = Suc (Suc (height tree1))" 1); |
181 by (case_tac "height (insert x tree2) = Suc (Suc (height tree1))" 1); |
182 by (case_tac "bal (insert x tree2) = Left" 1); |
182 by (case_tac "bal (insert x tree2) = Left" 1); |
183 by (fast_tac (claset() addIs [isbal_rl_rot] addss (simpset() |
183 by (fast_tac (claset() addIs [isbal_rl_rot] addss (simpset() |
184 addsimps [r_bal_def])) 1); |
184 addsimps [r_bal_def])) 1); |
185 by (fast_tac (claset() addIs [isbal_l_rot] addss (simpset() |
185 by (fast_tac (claset() addIs [isbal_l_rot] addss (simpset() |
186 addsimps [r_bal_def])) 1); |
186 addsimps [r_bal_def])) 1); |
187 by (Clarify_tac 1); |
187 by (Clarify_tac 1); |
188 by (forward_tac [isbal_insert_right] 1); |
188 by (ftac isbal_insert_right 1); |
189 by (Asm_full_simp_tac 1); |
189 by (Asm_full_simp_tac 1); |
190 ba 1; |
190 by (assume_tac 1); |
191 by (Asm_full_simp_tac 1); |
191 by (Asm_full_simp_tac 1); |
192 qed_spec_mp "isbal_insert"; |
192 qed_spec_mp "isbal_insert"; |
193 |
193 |
194 |
194 |
195 (****************************** isin **********************************) |
195 (****************************** isin **********************************) |
241 |
241 |
242 Goal |
242 Goal |
243 "isin y (insert x t) = (y=x | isin y t)"; |
243 "isin y (insert x t) = (y=x | isin y t)"; |
244 by (induct_tac "t" 1); |
244 by (induct_tac "t" 1); |
245 by (Asm_simp_tac 1); |
245 by (Asm_simp_tac 1); |
246 by(asm_simp_tac (simpset() addsimps [l_bal_def,isin_lr_rot,isin_r_rot, |
246 by (asm_simp_tac (simpset() addsimps [l_bal_def,isin_lr_rot,isin_r_rot, |
247 r_bal_def,isin_rl_rot,isin_l_rot]) 1); |
247 r_bal_def,isin_rl_rot,isin_l_rot]) 1); |
248 by(Blast_tac 1); |
248 by (Blast_tac 1); |
249 qed "isin_insert"; |
249 qed "isin_insert"; |
250 |
250 |
251 |
251 |
252 (****************************** isord **********************************) |
252 (****************************** isord **********************************) |
253 |
253 |
280 by (case_tac "r" 1); |
280 by (case_tac "r" 1); |
281 by (Asm_simp_tac 1); |
281 by (Asm_simp_tac 1); |
282 by (case_tac "tree1" 1); |
282 by (case_tac "tree1" 1); |
283 by (asm_simp_tac (simpset() addsimps [le_def]) 1); |
283 by (asm_simp_tac (simpset() addsimps [le_def]) 1); |
284 by (Asm_simp_tac 1); |
284 by (Asm_simp_tac 1); |
285 by(blast_tac (claset() addIs [less_trans])1); |
285 by (blast_tac (claset() addIs [less_trans])1); |
286 qed_spec_mp "isord_rl_rot"; |
286 qed_spec_mp "isord_rl_rot"; |
287 |
287 |
288 |
288 |
289 Goalw [bal_def] |
289 Goalw [bal_def] |
290 "height r = Suc(Suc(height l)) --> bal r ~= Left --> isord (MKT n l r) \ |
290 "height r = Suc(Suc(height l)) --> bal r ~= Left --> isord (MKT n l r) \ |
291 \ --> isord (l_rot (n, l, r))"; |
291 \ --> isord (l_rot (n, l, r))"; |
292 by (case_tac "r" 1); |
292 by (case_tac "r" 1); |
293 by (Asm_simp_tac 1); |
293 by (Asm_simp_tac 1); |
294 by (Asm_simp_tac 1); |
294 by (Asm_simp_tac 1); |
295 by(blast_tac (claset() addIs [less_trans])1); |
295 by (blast_tac (claset() addIs [less_trans])1); |
296 qed_spec_mp "isord_l_rot"; |
296 qed_spec_mp "isord_l_rot"; |
297 |
297 |
298 (* insert operation presreves isord property *) |
298 (* insert operation presreves isord property *) |
299 |
299 |
300 Goal |
300 Goal |