# HG changeset patch
# User nipkow
# Date 1445788333 -3600
# Node ID c0126c001b3d8606d8c961ef3890145b2158d8b5
# Parent  9334634404494bec07a21f9816aa9260cdd5e667
tuned

diff -r 933463440449 -r c0126c001b3d src/HOL/Data_Structures/Tree23_Map.thy
--- a/src/HOL/Data_Structures/Tree23_Map.thy	Sat Oct 24 13:42:31 2015 +0200
+++ b/src/HOL/Data_Structures/Tree23_Map.thy	Sun Oct 25 16:52:13 2015 +0100
@@ -1,6 +1,6 @@
 (* Author: Tobias Nipkow *)
 
-section \<open>2-3 Tree Implementation of Maps\<close>
+section \<open>A 2-3 Tree Implementation of Maps\<close>
 
 theory Tree23_Map
 imports
@@ -70,49 +70,39 @@
 "delete k t = tree\<^sub>d(del k t)"
 
 
-subsection "Proofs for Lookup"
+subsection \<open>Functional Correctness\<close>
 
 lemma lookup: "sorted1(inorder t) \<Longrightarrow> lookup t x = map_of (inorder t) x"
 by (induction t) (auto simp: map_of_simps split: option.split)
 
 
-subsection "Proofs for Update"
-
-text {* Balanced trees *}
-
-text{* First a standard proof that @{const upd} preserves @{const bal}. *}
-
-lemma bal_upd: "bal t \<Longrightarrow> bal (tree\<^sub>i(upd a b t)) \<and> height(upd a b t) = height t"
-by (induct t) (auto split: up\<^sub>i.split)
-
-text{* Now an alternative proof (by Brian Huffman) that runs faster because
-two properties (balance and height) are combined in one predicate. *}
-
-lemma full\<^sub>i_ins: "full n t \<Longrightarrow> full\<^sub>i n (upd a b t)"
-by (induct rule: full.induct, auto split: up\<^sub>i.split)
-
-text {* The @{const update} operation preserves balance. *}
-
-lemma bal_update: "bal t \<Longrightarrow> bal (update a b t)"
-unfolding bal_iff_full update_def
-apply (erule exE)
-apply (drule full\<^sub>i_ins [of _ _ a b])
-apply (cases "upd a b t")
-apply (auto intro: full.intros)
-done
-
-text {* Functional correctness of @{const "update"}. *}
-
 lemma inorder_upd:
   "sorted1(inorder t) \<Longrightarrow> inorder(tree\<^sub>i(upd a b t)) = upd_list a b (inorder t)"
 by(induction t) (auto simp: upd_list_simps split: up\<^sub>i.splits)
 
-lemma inorder_update:
+corollary inorder_update:
   "sorted1(inorder t) \<Longrightarrow> inorder(update a b t) = upd_list a b (inorder t)"
 by(simp add: update_def inorder_upd)
 
 
-subsection "Proofs for Deletion"
+lemma inorder_del: "\<lbrakk> bal t ; sorted1(inorder t) \<rbrakk> \<Longrightarrow>
+  inorder(tree\<^sub>d (del x t)) = del_list x (inorder t)"
+by(induction t rule: del.induct)
+  (auto simp: del_list_simps inorder_nodes del_minD split: prod.splits)
+
+corollary inorder_delete: "\<lbrakk> bal t ; sorted1(inorder t) \<rbrakk> \<Longrightarrow>
+  inorder(delete x t) = del_list x (inorder t)"
+by(simp add: delete_def inorder_del)
+
+
+subsection \<open>Balancedness\<close>
+
+lemma bal_upd: "bal t \<Longrightarrow> bal (tree\<^sub>i(upd a b t)) \<and> height(upd a b t) = height t"
+by (induct t) (auto split: up\<^sub>i.split)(* 30 secs in 2015 *)
+
+corollary bal_update: "bal t \<Longrightarrow> bal (update a b t)"
+by (simp add: update_def bal_upd)
+
 
 lemma height_del: "bal t \<Longrightarrow> height(del x t) = height t"
 by(induction x t rule: del.induct)
@@ -125,15 +115,6 @@
 corollary bal_delete: "bal t \<Longrightarrow> bal(delete x t)"
 by(simp add: delete_def bal_tree\<^sub>d_del)
 
-lemma inorder_del: "\<lbrakk> bal t ; sorted1(inorder t) \<rbrakk> \<Longrightarrow>
-  inorder(tree\<^sub>d (del x t)) = del_list x (inorder t)"
-by(induction t rule: del.induct)
-  (auto simp: del_list_simps inorder_nodes del_minD split: prod.splits)
-
-lemma inorder_delete: "\<lbrakk> bal t ; sorted1(inorder t) \<rbrakk> \<Longrightarrow>
-  inorder(delete x t) = del_list x (inorder t)"
-by(simp add: delete_def inorder_del)
-
 
 subsection \<open>Overall Correctness\<close>
 
diff -r 933463440449 -r c0126c001b3d src/HOL/Data_Structures/Tree23_Set.thy
--- a/src/HOL/Data_Structures/Tree23_Set.thy	Sat Oct 24 13:42:31 2015 +0200
+++ b/src/HOL/Data_Structures/Tree23_Set.thy	Sun Oct 25 16:52:13 2015 +0100
@@ -1,6 +1,6 @@
 (* Author: Tobias Nipkow *)
 
-section \<open>2-3 Tree Implementation of Sets\<close>
+section \<open>A 2-3 Tree Implementation of Sets\<close>
 
 theory Tree23_Set
 imports
@@ -111,8 +111,6 @@
 "delete k t = tree\<^sub>d(del k t)"
 
 
-declare prod.splits [split]
-
 subsection "Functional Correctness"
 
 
@@ -165,12 +163,12 @@
   "del_min t = (x,t') \<Longrightarrow> bal t \<Longrightarrow> height t > 0 \<Longrightarrow>
   x # inorder(tree\<^sub>d t') = inorder t"
 by(induction t arbitrary: t' rule: del_min.induct)
-  (auto simp: inorder_nodes)
+  (auto simp: inorder_nodes split: prod.splits)
 
 lemma inorder_del: "\<lbrakk> bal t ; sorted(inorder t) \<rbrakk> \<Longrightarrow>
   inorder(tree\<^sub>d (del x t)) = del_list x (inorder t)"
 by(induction t rule: del.induct)
-  (auto simp: del_list_simps inorder_nodes del_minD)
+  (auto simp: del_list_simps inorder_nodes del_minD split: prod.splits)
 
 lemma inorder_delete: "\<lbrakk> bal t ; sorted(inorder t) \<rbrakk> \<Longrightarrow>
   inorder(delete x t) = del_list x (inorder t)"
@@ -196,7 +194,7 @@
 end
 
 lemma bal_ins: "bal t \<Longrightarrow> bal (tree\<^sub>i(ins a t)) \<and> height(ins a t) = height t"
-by (induct t) (auto split: up\<^sub>i.split)
+by (induct t) (auto split: up\<^sub>i.split) (* 25 secs in 2015 *)
 
 text{* Now an alternative proof (by Brian Huffman) that runs faster because
 two properties (balance and height) are combined in one predicate. *}
@@ -336,16 +334,17 @@
 
 lemma height_del: "bal t \<Longrightarrow> height(del x t) = height t"
 by(induction x t rule: del.induct)
-  (auto simp add: heights max_def height_del_min)
+  (auto simp: heights max_def height_del_min split: prod.splits)
 
 lemma bal_del_min:
   "\<lbrakk> del_min t = (x, t'); bal t; height t > 0 \<rbrakk> \<Longrightarrow> bal (tree\<^sub>d t')"
 by(induct t arbitrary: x t' rule: del_min.induct)
-  (auto simp: heights height_del_min bals)
+  (auto simp: heights height_del_min bals split: prod.splits)
 
 lemma bal_tree\<^sub>d_del: "bal t \<Longrightarrow> bal(tree\<^sub>d(del x t))"
 by(induction x t rule: del.induct)
-  (auto simp: bals bal_del_min height_del height_del_min)
+  (auto simp: bals bal_del_min height_del height_del_min split: prod.splits)
+
 corollary bal_delete: "bal t \<Longrightarrow> bal(delete x t)"
 by(simp add: delete_def bal_tree\<^sub>d_del)