tuned order of arguments
authornipkow
Mon Jun 11 16:29:27 2018 +0200 (11 months ago)
changeset 68413b56ed5010e69
parent 68411 d8363de26567
child 68414 b001bef9aa39
tuned order of arguments
src/HOL/Data_Structures/AA_Map.thy
src/HOL/Data_Structures/AA_Set.thy
src/HOL/Data_Structures/AVL_Map.thy
src/HOL/Data_Structures/AVL_Set.thy
src/HOL/Data_Structures/Isin2.thy
src/HOL/Data_Structures/Leftist_Heap.thy
src/HOL/Data_Structures/Lookup2.thy
src/HOL/Data_Structures/RBT.thy
src/HOL/Data_Structures/RBT_Map.thy
src/HOL/Data_Structures/RBT_Set.thy
src/HOL/Data_Structures/Set2_Join.thy
src/HOL/Data_Structures/Tree2.thy
     1.1 --- a/src/HOL/Data_Structures/AA_Map.thy	Mon Jun 11 08:15:43 2018 +0200
     1.2 +++ b/src/HOL/Data_Structures/AA_Map.thy	Mon Jun 11 16:29:27 2018 +0200
     1.3 @@ -9,21 +9,21 @@
     1.4  begin
     1.5  
     1.6  fun update :: "'a::linorder \<Rightarrow> 'b \<Rightarrow> ('a*'b) aa_tree \<Rightarrow> ('a*'b) aa_tree" where
     1.7 -"update x y Leaf = Node 1 Leaf (x,y) Leaf" |
     1.8 -"update x y (Node lv t1 (a,b) t2) =
     1.9 +"update x y Leaf = Node Leaf (x,y) 1 Leaf" |
    1.10 +"update x y (Node t1 (a,b) lv t2) =
    1.11    (case cmp x a of
    1.12 -     LT \<Rightarrow> split (skew (Node lv (update x y t1) (a,b) t2)) |
    1.13 -     GT \<Rightarrow> split (skew (Node lv t1 (a,b) (update x y t2))) |
    1.14 -     EQ \<Rightarrow> Node lv t1 (x,y) t2)"
    1.15 +     LT \<Rightarrow> split (skew (Node (update x y t1) (a,b) lv t2)) |
    1.16 +     GT \<Rightarrow> split (skew (Node t1 (a,b) lv (update x y t2))) |
    1.17 +     EQ \<Rightarrow> Node t1 (x,y) lv t2)"
    1.18  
    1.19  fun delete :: "'a::linorder \<Rightarrow> ('a*'b) aa_tree \<Rightarrow> ('a*'b) aa_tree" where
    1.20  "delete _ Leaf = Leaf" |
    1.21 -"delete x (Node lv l (a,b) r) =
    1.22 +"delete x (Node l (a,b) lv r) =
    1.23    (case cmp x a of
    1.24 -     LT \<Rightarrow> adjust (Node lv (delete x l) (a,b) r) |
    1.25 -     GT \<Rightarrow> adjust (Node lv l (a,b) (delete x r)) |
    1.26 +     LT \<Rightarrow> adjust (Node (delete x l) (a,b) lv r) |
    1.27 +     GT \<Rightarrow> adjust (Node l (a,b) lv (delete x r)) |
    1.28       EQ \<Rightarrow> (if l = Leaf then r
    1.29 -            else let (l',ab') = split_max l in adjust (Node lv l' ab' r)))"
    1.30 +            else let (l',ab') = split_max l in adjust (Node l' ab' lv r)))"
    1.31  
    1.32  
    1.33  subsection "Invariance"
    1.34 @@ -46,7 +46,7 @@
    1.35  
    1.36  lemma lvl_update_sngl: "invar t \<Longrightarrow> sngl t \<Longrightarrow> lvl(update x y t) = lvl t"
    1.37  proof (induction t rule: update.induct)
    1.38 -  case (2 x y lv t1 a b t2)
    1.39 +  case (2 x y t1 a b lv t2)
    1.40    consider (LT) "x < a" | (GT) "x > a" | (EQ) "x = a" 
    1.41      using less_linear by blast 
    1.42    thus ?case proof cases
    1.43 @@ -64,7 +64,7 @@
    1.44  qed simp
    1.45  
    1.46  lemma lvl_update_incr_iff: "(lvl(update a b t) = lvl t + 1) \<longleftrightarrow>
    1.47 -  (\<exists>l x r. update a b t = Node (lvl t + 1) l x r \<and> lvl l = lvl r)"
    1.48 +  (\<exists>l x r. update a b t = Node l x (lvl t + 1) r \<and> lvl l = lvl r)"
    1.49  apply(cases t)
    1.50  apply(auto simp add: skew_case split_case split: if_splits)
    1.51  apply(auto split: tree.splits if_splits)
    1.52 @@ -72,12 +72,12 @@
    1.53  
    1.54  lemma invar_update: "invar t \<Longrightarrow> invar(update a b t)"
    1.55  proof(induction t)
    1.56 -  case N: (Node n l xy r)
    1.57 +  case N: (Node l xy n r)
    1.58    hence il: "invar l" and ir: "invar r" by auto
    1.59    note iil = N.IH(1)[OF il]
    1.60    note iir = N.IH(2)[OF ir]
    1.61    obtain x y where [simp]: "xy = (x,y)" by fastforce
    1.62 -  let ?t = "Node n l xy r"
    1.63 +  let ?t = "Node l xy n r"
    1.64    have "a < x \<or> a = x \<or> x < a" by auto
    1.65    moreover
    1.66    have ?case if "a < x"
    1.67 @@ -87,13 +87,13 @@
    1.68        by (simp add: skew_invar split_invar del: invar.simps)
    1.69    next
    1.70      case (Incr)
    1.71 -    then obtain t1 w t2 where ial[simp]: "update a b l = Node n t1 w t2"
    1.72 +    then obtain t1 w t2 where ial[simp]: "update a b l = Node t1 w n t2"
    1.73        using N.prems by (auto simp: lvl_Suc_iff)
    1.74      have l12: "lvl t1 = lvl t2"
    1.75        by (metis Incr(1) ial lvl_update_incr_iff tree.inject)
    1.76 -    have "update a b ?t = split(skew(Node n (update a b l) xy r))"
    1.77 +    have "update a b ?t = split(skew(Node (update a b l) xy n r))"
    1.78        by(simp add: \<open>a<x\<close>)
    1.79 -    also have "skew(Node n (update a b l) xy r) = Node n t1 w (Node n t2 xy r)"
    1.80 +    also have "skew(Node (update a b l) xy n r) = Node t1 w n (Node t2 xy n r)"
    1.81        by(simp)
    1.82      also have "invar(split \<dots>)"
    1.83      proof (cases r)
    1.84 @@ -101,7 +101,7 @@
    1.85        hence "l = Leaf" using N.prems by(auto simp: lvl_0_iff)
    1.86        thus ?thesis using Leaf ial by simp
    1.87      next
    1.88 -      case [simp]: (Node m t3 y t4)
    1.89 +      case [simp]: (Node t3 y m t4)
    1.90        show ?thesis (*using N(3) iil l12 by(auto)*)
    1.91        proof cases
    1.92          assume "m = n" thus ?thesis using N(3) iil by(auto)
    1.93 @@ -118,14 +118,14 @@
    1.94      thus ?case
    1.95      proof
    1.96        assume 0: "n = lvl r"
    1.97 -      have "update a b ?t = split(skew(Node n l xy (update a b r)))"
    1.98 +      have "update a b ?t = split(skew(Node l xy n (update a b r)))"
    1.99          using \<open>a>x\<close> by(auto)
   1.100 -      also have "skew(Node n l xy (update a b r)) = Node n l xy (update a b r)"
   1.101 +      also have "skew(Node l xy n (update a b r)) = Node l xy n (update a b r)"
   1.102          using N.prems by(simp add: skew_case split: tree.split)
   1.103        also have "invar(split \<dots>)"
   1.104        proof -
   1.105          from lvl_update_sngl[OF ir sngl_if_invar[OF \<open>invar ?t\<close> 0], of a b]
   1.106 -        obtain t1 p t2 where iar: "update a b r = Node n t1 p t2"
   1.107 +        obtain t1 p t2 where iar: "update a b r = Node t1 p n t2"
   1.108            using N.prems 0 by (auto simp: lvl_Suc_iff)
   1.109          from N.prems iar 0 iir
   1.110          show ?thesis by (auto simp: split_case split: tree.splits)
   1.111 @@ -157,12 +157,12 @@
   1.112  
   1.113  theorem post_delete: "invar t \<Longrightarrow> post_del t (delete x t)"
   1.114  proof (induction t)
   1.115 -  case (Node lv l ab r)
   1.116 +  case (Node l ab lv r)
   1.117  
   1.118    obtain a b where [simp]: "ab = (a,b)" by fastforce
   1.119  
   1.120    let ?l' = "delete x l" and ?r' = "delete x r"
   1.121 -  let ?t = "Node lv l ab r" let ?t' = "delete x ?t"
   1.122 +  let ?t = "Node l ab lv r" let ?t' = "delete x ?t"
   1.123  
   1.124    from Node.prems have inv_l: "invar l" and inv_r: "invar r" by (auto)
   1.125  
     2.1 --- a/src/HOL/Data_Structures/AA_Set.thy	Mon Jun 11 08:15:43 2018 +0200
     2.2 +++ b/src/HOL/Data_Structures/AA_Set.thy	Mon Jun 11 16:29:27 2018 +0200
     2.3 @@ -14,60 +14,60 @@
     2.4  
     2.5  fun lvl :: "'a aa_tree \<Rightarrow> nat" where
     2.6  "lvl Leaf = 0" |
     2.7 -"lvl (Node lv _ _ _) = lv"
     2.8 +"lvl (Node _ _ lv _) = lv"
     2.9  
    2.10  fun invar :: "'a aa_tree \<Rightarrow> bool" where
    2.11  "invar Leaf = True" |
    2.12 -"invar (Node h l a r) =
    2.13 +"invar (Node l a h r) =
    2.14   (invar l \<and> invar r \<and>
    2.15 -  h = lvl l + 1 \<and> (h = lvl r + 1 \<or> (\<exists>lr b rr. r = Node h lr b rr \<and> h = lvl rr + 1)))"
    2.16 +  h = lvl l + 1 \<and> (h = lvl r + 1 \<or> (\<exists>lr b rr. r = Node lr b h rr \<and> h = lvl rr + 1)))"
    2.17  
    2.18  fun skew :: "'a aa_tree \<Rightarrow> 'a aa_tree" where
    2.19 -"skew (Node lva (Node lvb t1 b t2) a t3) =
    2.20 -  (if lva = lvb then Node lva t1 b (Node lva t2 a t3) else Node lva (Node lvb t1 b t2) a t3)" |
    2.21 +"skew (Node (Node t1 b lvb t2) a lva t3) =
    2.22 +  (if lva = lvb then Node t1 b lvb (Node t2 a lva t3) else Node (Node t1 b lvb t2) a lva t3)" |
    2.23  "skew t = t"
    2.24  
    2.25  fun split :: "'a aa_tree \<Rightarrow> 'a aa_tree" where
    2.26 -"split (Node lva t1 a (Node lvb t2 b (Node lvc t3 c t4))) =
    2.27 +"split (Node t1 a lva (Node t2 b lvb (Node t3 c lvc t4))) =
    2.28     (if lva = lvb \<and> lvb = lvc \<comment> \<open>\<open>lva = lvc\<close> suffices\<close>
    2.29 -    then Node (lva+1) (Node lva t1 a t2) b (Node lva t3 c t4)
    2.30 -    else Node lva t1 a (Node lvb t2 b (Node lvc t3 c t4)))" |
    2.31 +    then Node (Node t1 a lva t2) b (lva+1) (Node t3 c lva t4)
    2.32 +    else Node t1 a lva (Node t2 b lvb (Node t3 c lvc t4)))" |
    2.33  "split t = t"
    2.34  
    2.35  hide_const (open) insert
    2.36  
    2.37  fun insert :: "'a::linorder \<Rightarrow> 'a aa_tree \<Rightarrow> 'a aa_tree" where
    2.38 -"insert x Leaf = Node 1 Leaf x Leaf" |
    2.39 -"insert x (Node lv t1 a t2) =
    2.40 +"insert x Leaf = Node Leaf x 1 Leaf" |
    2.41 +"insert x (Node t1 a lv t2) =
    2.42    (case cmp x a of
    2.43 -     LT \<Rightarrow> split (skew (Node lv (insert x t1) a t2)) |
    2.44 -     GT \<Rightarrow> split (skew (Node lv t1 a (insert x t2))) |
    2.45 -     EQ \<Rightarrow> Node lv t1 x t2)"
    2.46 +     LT \<Rightarrow> split (skew (Node (insert x t1) a lv t2)) |
    2.47 +     GT \<Rightarrow> split (skew (Node t1 a lv (insert x t2))) |
    2.48 +     EQ \<Rightarrow> Node t1 x lv t2)"
    2.49  
    2.50  fun sngl :: "'a aa_tree \<Rightarrow> bool" where
    2.51  "sngl Leaf = False" |
    2.52  "sngl (Node _ _ _ Leaf) = True" |
    2.53 -"sngl (Node lva _ _ (Node lvb _ _ _)) = (lva > lvb)"
    2.54 +"sngl (Node _ _ lva (Node _ _ lvb _)) = (lva > lvb)"
    2.55  
    2.56  definition adjust :: "'a aa_tree \<Rightarrow> 'a aa_tree" where
    2.57  "adjust t =
    2.58   (case t of
    2.59 -  Node lv l x r \<Rightarrow>
    2.60 +  Node l x lv r \<Rightarrow>
    2.61     (if lvl l >= lv-1 \<and> lvl r >= lv-1 then t else
    2.62 -    if lvl r < lv-1 \<and> sngl l then skew (Node (lv-1) l x r) else
    2.63 +    if lvl r < lv-1 \<and> sngl l then skew (Node l x (lv-1) r) else
    2.64      if lvl r < lv-1
    2.65      then case l of
    2.66 -           Node lva t1 a (Node lvb t2 b t3)
    2.67 -             \<Rightarrow> Node (lvb+1) (Node lva t1 a t2) b (Node (lv-1) t3 x r) 
    2.68 +           Node t1 a lva (Node t2 b lvb t3)
    2.69 +             \<Rightarrow> Node (Node t1 a lva t2) b (lvb+1) (Node t3 x (lv-1) r) 
    2.70      else
    2.71 -    if lvl r < lv then split (Node (lv-1) l x r)
    2.72 +    if lvl r < lv then split (Node l x (lv-1) r)
    2.73      else
    2.74        case r of
    2.75 -        Node lvb t1 b t4 \<Rightarrow>
    2.76 +        Node t1 b lvb t4 \<Rightarrow>
    2.77            (case t1 of
    2.78 -             Node lva t2 a t3
    2.79 -               \<Rightarrow> Node (lva+1) (Node (lv-1) l x t2) a
    2.80 -                    (split (Node (if sngl t1 then lva else lva+1) t3 b t4)))))"
    2.81 +             Node t2 a lva t3
    2.82 +               \<Rightarrow> Node (Node l x (lv-1) t2) a (lva+1)
    2.83 +                    (split (Node t3 b (if sngl t1 then lva else lva+1) t4)))))"
    2.84  
    2.85  text\<open>In the paper, the last case of @{const adjust} is expressed with the help of an
    2.86  incorrect auxiliary function \texttt{nlvl}.
    2.87 @@ -78,20 +78,20 @@
    2.88  is not restored.\<close>
    2.89  
    2.90  fun split_max :: "'a aa_tree \<Rightarrow> 'a aa_tree * 'a" where
    2.91 -"split_max (Node lv l a Leaf) = (l,a)" |
    2.92 -"split_max (Node lv l a r) = (let (r',b) = split_max r in (adjust(Node lv l a r'), b))"
    2.93 +"split_max (Node l a lv Leaf) = (l,a)" |
    2.94 +"split_max (Node l a lv r) = (let (r',b) = split_max r in (adjust(Node l a lv r'), b))"
    2.95  
    2.96  fun delete :: "'a::linorder \<Rightarrow> 'a aa_tree \<Rightarrow> 'a aa_tree" where
    2.97  "delete _ Leaf = Leaf" |
    2.98 -"delete x (Node lv l a r) =
    2.99 +"delete x (Node l a lv r) =
   2.100    (case cmp x a of
   2.101 -     LT \<Rightarrow> adjust (Node lv (delete x l) a r) |
   2.102 -     GT \<Rightarrow> adjust (Node lv l a (delete x r)) |
   2.103 +     LT \<Rightarrow> adjust (Node (delete x l) a lv r) |
   2.104 +     GT \<Rightarrow> adjust (Node l a lv (delete x r)) |
   2.105       EQ \<Rightarrow> (if l = Leaf then r
   2.106 -            else let (l',b) = split_max l in adjust (Node lv l' b r)))"
   2.107 +            else let (l',b) = split_max l in adjust (Node l' b lv r)))"
   2.108  
   2.109  fun pre_adjust where
   2.110 -"pre_adjust (Node lv l a r) = (invar l \<and> invar r \<and>
   2.111 +"pre_adjust (Node l a lv r) = (invar l \<and> invar r \<and>
   2.112      ((lv = lvl l + 1 \<and> (lv = lvl r + 1 \<or> lv = lvl r + 2 \<or> lv = lvl r \<and> sngl r)) \<or>
   2.113       (lv = lvl l + 2 \<and> (lv = lvl r + 1 \<or> lv = lvl r \<and> sngl r))))"
   2.114  
   2.115 @@ -100,23 +100,23 @@
   2.116  subsection "Auxiliary Proofs"
   2.117  
   2.118  lemma split_case: "split t = (case t of
   2.119 -  Node lvx a x (Node lvy b y (Node lvz c z d)) \<Rightarrow>
   2.120 +  Node t1 x lvx (Node t2 y lvy (Node t3 z lvz t4)) \<Rightarrow>
   2.121     (if lvx = lvy \<and> lvy = lvz
   2.122 -    then Node (lvx+1) (Node lvx a x b) y (Node lvx c z d)
   2.123 +    then Node (Node t1 x lvx t2) y (lvx+1) (Node t3 z lvx t4)
   2.124      else t)
   2.125    | t \<Rightarrow> t)"
   2.126  by(auto split: tree.split)
   2.127  
   2.128  lemma skew_case: "skew t = (case t of
   2.129 -  Node lvx (Node lvy a y b) x c \<Rightarrow>
   2.130 -  (if lvx = lvy then Node lvx a y (Node lvx b x c) else t)
   2.131 +  Node (Node t1 y lvy t2) x lvx t3 \<Rightarrow>
   2.132 +  (if lvx = lvy then Node t1 y lvx (Node t2 x lvx t3) else t)
   2.133   | t \<Rightarrow> t)"
   2.134  by(auto split: tree.split)
   2.135  
   2.136  lemma lvl_0_iff: "invar t \<Longrightarrow> lvl t = 0 \<longleftrightarrow> t = Leaf"
   2.137  by(cases t) auto
   2.138  
   2.139 -lemma lvl_Suc_iff: "lvl t = Suc n \<longleftrightarrow> (\<exists> l a r. t = Node (Suc n) l a r)"
   2.140 +lemma lvl_Suc_iff: "lvl t = Suc n \<longleftrightarrow> (\<exists> l a r. t = Node l a (Suc n) r)"
   2.141  by(cases t) auto
   2.142  
   2.143  lemma lvl_skew: "lvl (skew t) = lvl t"
   2.144 @@ -125,16 +125,16 @@
   2.145  lemma lvl_split: "lvl (split t) = lvl t \<or> lvl (split t) = lvl t + 1 \<and> sngl (split t)"
   2.146  by(cases t rule: split.cases) auto
   2.147  
   2.148 -lemma invar_2Nodes:"invar (Node lv l x (Node rlv rl rx rr)) =
   2.149 -     (invar l \<and> invar \<langle>rlv, rl, rx, rr\<rangle> \<and> lv = Suc (lvl l) \<and>
   2.150 +lemma invar_2Nodes:"invar (Node l x lv (Node rl rx rlv rr)) =
   2.151 +     (invar l \<and> invar \<langle>rl, rx, rlv, rr\<rangle> \<and> lv = Suc (lvl l) \<and>
   2.152       (lv = Suc rlv \<or> rlv = lv \<and> lv = Suc (lvl rr)))"
   2.153  by simp
   2.154  
   2.155  lemma invar_NodeLeaf[simp]:
   2.156 -  "invar (Node lv l x Leaf) = (invar l \<and> lv = Suc (lvl l) \<and> lv = Suc 0)"
   2.157 +  "invar (Node l x lv Leaf) = (invar l \<and> lv = Suc (lvl l) \<and> lv = Suc 0)"
   2.158  by simp
   2.159  
   2.160 -lemma sngl_if_invar: "invar (Node n l a r) \<Longrightarrow> n = lvl r \<Longrightarrow> sngl r"
   2.161 +lemma sngl_if_invar: "invar (Node l a n r) \<Longrightarrow> n = lvl r \<Longrightarrow> sngl r"
   2.162  by(cases r rule: sngl.cases) clarsimp+
   2.163  
   2.164  
   2.165 @@ -156,7 +156,7 @@
   2.166  
   2.167  lemma lvl_insert_sngl: "invar t \<Longrightarrow> sngl t \<Longrightarrow> lvl(insert x t) = lvl t"
   2.168  proof (induction t rule: insert.induct)
   2.169 -  case (2 x lv t1 a t2)
   2.170 +  case (2 x t1 a lv t2)
   2.171    consider (LT) "x < a" | (GT) "x > a" | (EQ) "x = a" 
   2.172      using less_linear by blast 
   2.173    thus ?case proof cases
   2.174 @@ -180,20 +180,20 @@
   2.175  by(cases t rule: split.cases) clarsimp+
   2.176  
   2.177  lemma invar_NodeL:
   2.178 -  "\<lbrakk> invar(Node n l x r); invar l'; lvl l' = lvl l \<rbrakk> \<Longrightarrow> invar(Node n l' x r)"
   2.179 +  "\<lbrakk> invar(Node l x n r); invar l'; lvl l' = lvl l \<rbrakk> \<Longrightarrow> invar(Node l' x n r)"
   2.180  by(auto)
   2.181  
   2.182  lemma invar_NodeR:
   2.183 -  "\<lbrakk> invar(Node n l x r); n = lvl r + 1; invar r'; lvl r' = lvl r \<rbrakk> \<Longrightarrow> invar(Node n l x r')"
   2.184 +  "\<lbrakk> invar(Node l x n r); n = lvl r + 1; invar r'; lvl r' = lvl r \<rbrakk> \<Longrightarrow> invar(Node l x n r')"
   2.185  by(auto)
   2.186  
   2.187  lemma invar_NodeR2:
   2.188 -  "\<lbrakk> invar(Node n l x r); sngl r'; n = lvl r + 1; invar r'; lvl r' = n \<rbrakk> \<Longrightarrow> invar(Node n l x r')"
   2.189 +  "\<lbrakk> invar(Node l x n r); sngl r'; n = lvl r + 1; invar r'; lvl r' = n \<rbrakk> \<Longrightarrow> invar(Node l x n r')"
   2.190  by(cases r' rule: sngl.cases) clarsimp+
   2.191  
   2.192  
   2.193  lemma lvl_insert_incr_iff: "(lvl(insert a t) = lvl t + 1) \<longleftrightarrow>
   2.194 -  (\<exists>l x r. insert a t = Node (lvl t + 1) l x r \<and> lvl l = lvl r)"
   2.195 +  (\<exists>l x r. insert a t = Node l x (lvl t + 1) r \<and> lvl l = lvl r)"
   2.196  apply(cases t)
   2.197  apply(auto simp add: skew_case split_case split: if_splits)
   2.198  apply(auto split: tree.splits if_splits)
   2.199 @@ -201,11 +201,11 @@
   2.200  
   2.201  lemma invar_insert: "invar t \<Longrightarrow> invar(insert a t)"
   2.202  proof(induction t)
   2.203 -  case N: (Node n l x r)
   2.204 +  case N: (Node l x n r)
   2.205    hence il: "invar l" and ir: "invar r" by auto
   2.206    note iil = N.IH(1)[OF il]
   2.207    note iir = N.IH(2)[OF ir]
   2.208 -  let ?t = "Node n l x r"
   2.209 +  let ?t = "Node l x n r"
   2.210    have "a < x \<or> a = x \<or> x < a" by auto
   2.211    moreover
   2.212    have ?case if "a < x"
   2.213 @@ -215,13 +215,13 @@
   2.214        by (simp add: skew_invar split_invar del: invar.simps)
   2.215    next
   2.216      case (Incr)
   2.217 -    then obtain t1 w t2 where ial[simp]: "insert a l = Node n t1 w t2"
   2.218 +    then obtain t1 w t2 where ial[simp]: "insert a l = Node t1 w n t2"
   2.219        using N.prems by (auto simp: lvl_Suc_iff)
   2.220      have l12: "lvl t1 = lvl t2"
   2.221        by (metis Incr(1) ial lvl_insert_incr_iff tree.inject)
   2.222 -    have "insert a ?t = split(skew(Node n (insert a l) x r))"
   2.223 +    have "insert a ?t = split(skew(Node (insert a l) x n r))"
   2.224        by(simp add: \<open>a<x\<close>)
   2.225 -    also have "skew(Node n (insert a l) x r) = Node n t1 w (Node n t2 x r)"
   2.226 +    also have "skew(Node (insert a l) x n r) = Node t1 w n (Node t2 x n r)"
   2.227        by(simp)
   2.228      also have "invar(split \<dots>)"
   2.229      proof (cases r)
   2.230 @@ -229,7 +229,7 @@
   2.231        hence "l = Leaf" using N.prems by(auto simp: lvl_0_iff)
   2.232        thus ?thesis using Leaf ial by simp
   2.233      next
   2.234 -      case [simp]: (Node m t3 y t4)
   2.235 +      case [simp]: (Node t3 y m t4)
   2.236        show ?thesis (*using N(3) iil l12 by(auto)*)
   2.237        proof cases
   2.238          assume "m = n" thus ?thesis using N(3) iil by(auto)
   2.239 @@ -246,14 +246,14 @@
   2.240      thus ?case
   2.241      proof
   2.242        assume 0: "n = lvl r"
   2.243 -      have "insert a ?t = split(skew(Node n l x (insert a r)))"
   2.244 +      have "insert a ?t = split(skew(Node l x n (insert a r)))"
   2.245          using \<open>a>x\<close> by(auto)
   2.246 -      also have "skew(Node n l x (insert a r)) = Node n l x (insert a r)"
   2.247 +      also have "skew(Node l x n (insert a r)) = Node l x n (insert a r)"
   2.248          using N.prems by(simp add: skew_case split: tree.split)
   2.249        also have "invar(split \<dots>)"
   2.250        proof -
   2.251          from lvl_insert_sngl[OF ir sngl_if_invar[OF \<open>invar ?t\<close> 0], of a]
   2.252 -        obtain t1 y t2 where iar: "insert a r = Node n t1 y t2"
   2.253 +        obtain t1 y t2 where iar: "insert a r = Node t1 y n t2"
   2.254            using N.prems 0 by (auto simp: lvl_Suc_iff)
   2.255          from N.prems iar 0 iir
   2.256          show ?thesis by (auto simp: split_case split: tree.splits)
   2.257 @@ -282,21 +282,21 @@
   2.258  
   2.259  subsubsection "Proofs for delete"
   2.260  
   2.261 -lemma invarL: "ASSUMPTION(invar \<langle>lv, l, a, r\<rangle>) \<Longrightarrow> invar l"
   2.262 +lemma invarL: "ASSUMPTION(invar \<langle>l, a, lv, r\<rangle>) \<Longrightarrow> invar l"
   2.263  by(simp add: ASSUMPTION_def)
   2.264  
   2.265  lemma invarR: "ASSUMPTION(invar \<langle>lv, l, a, r\<rangle>) \<Longrightarrow> invar r"
   2.266  by(simp add: ASSUMPTION_def)
   2.267  
   2.268  lemma sngl_NodeI:
   2.269 -  "sngl (Node lv l a r) \<Longrightarrow> sngl (Node lv l' a' r)"
   2.270 +  "sngl (Node l a lv r) \<Longrightarrow> sngl (Node l' a' lv r)"
   2.271  by(cases r) (simp_all)
   2.272  
   2.273  
   2.274  declare invarL[simp] invarR[simp]
   2.275  
   2.276  lemma pre_cases:
   2.277 -assumes "pre_adjust (Node lv l x r)"
   2.278 +assumes "pre_adjust (Node l x lv r)"
   2.279  obtains
   2.280   (tSngl) "invar l \<and> invar r \<and>
   2.281      lv = Suc (lvl r) \<and> lvl l = lvl r" |
   2.282 @@ -314,38 +314,38 @@
   2.283  declare invar.simps(2)[simp del] invar_2Nodes[simp add]
   2.284  
   2.285  lemma invar_adjust:
   2.286 -  assumes pre: "pre_adjust (Node lv l a r)"
   2.287 -  shows  "invar(adjust (Node lv l a r))"
   2.288 +  assumes pre: "pre_adjust (Node l a lv r)"
   2.289 +  shows  "invar(adjust (Node l a lv r))"
   2.290  using pre proof (cases rule: pre_cases)
   2.291    case (tDouble) thus ?thesis unfolding adjust_def by (cases r) (auto simp: invar.simps(2)) 
   2.292  next 
   2.293    case (rDown)
   2.294 -  from rDown obtain llv ll la lr where l: "l = Node llv ll la lr" by (cases l) auto
   2.295 +  from rDown obtain llv ll la lr where l: "l = Node ll la llv lr" by (cases l) auto
   2.296    from rDown show ?thesis unfolding adjust_def by (auto simp: l invar.simps(2) split: tree.splits)
   2.297  next
   2.298    case (lDown_tDouble)
   2.299 -  from lDown_tDouble obtain rlv rr ra rl where r: "r = Node rlv rl ra rr" by (cases r) auto
   2.300 +  from lDown_tDouble obtain rlv rr ra rl where r: "r = Node rl ra rlv rr" by (cases r) auto
   2.301    from lDown_tDouble and r obtain rrlv rrr rra rrl where
   2.302 -    rr :"rr = Node rrlv rrr rra rrl" by (cases rr) auto
   2.303 +    rr :"rr = Node rrr rra rrlv rrl" by (cases rr) auto
   2.304    from  lDown_tDouble show ?thesis unfolding adjust_def r rr
   2.305      apply (cases rl) apply (auto simp add: invar.simps(2) split!: if_split)
   2.306      using lDown_tDouble by (auto simp: split_case lvl_0_iff  elim:lvl.elims split: tree.split)
   2.307  qed (auto simp: split_case invar.simps(2) adjust_def split: tree.splits)
   2.308  
   2.309  lemma lvl_adjust:
   2.310 -  assumes "pre_adjust (Node lv l a r)"
   2.311 -  shows "lv = lvl (adjust(Node lv l a r)) \<or> lv = lvl (adjust(Node lv l a r)) + 1"
   2.312 +  assumes "pre_adjust (Node l a lv r)"
   2.313 +  shows "lv = lvl (adjust(Node l a lv r)) \<or> lv = lvl (adjust(Node l a lv r)) + 1"
   2.314  using assms(1) proof(cases rule: pre_cases)
   2.315    case lDown_tSngl thus ?thesis
   2.316 -    using lvl_split[of "\<langle>lvl r, l, a, r\<rangle>"] by (auto simp: adjust_def)
   2.317 +    using lvl_split[of "\<langle>l, a, lvl r, r\<rangle>"] by (auto simp: adjust_def)
   2.318  next
   2.319    case lDown_tDouble thus ?thesis
   2.320      by (auto simp: adjust_def invar.simps(2) split: tree.split)
   2.321  qed (auto simp: adjust_def split: tree.splits)
   2.322  
   2.323 -lemma sngl_adjust: assumes "pre_adjust (Node lv l a r)"
   2.324 -  "sngl \<langle>lv, l, a, r\<rangle>" "lv = lvl (adjust \<langle>lv, l, a, r\<rangle>)"
   2.325 -  shows "sngl (adjust \<langle>lv, l, a, r\<rangle>)" 
   2.326 +lemma sngl_adjust: assumes "pre_adjust (Node l a lv r)"
   2.327 +  "sngl \<langle>l, a, lv, r\<rangle>" "lv = lvl (adjust \<langle>l, a, lv, r\<rangle>)"
   2.328 +  shows "sngl (adjust \<langle>l, a, lv, r\<rangle>)" 
   2.329  using assms proof (cases rule: pre_cases)
   2.330    case rDown
   2.331    thus ?thesis using assms(2,3) unfolding adjust_def
   2.332 @@ -363,13 +363,13 @@
   2.333    (auto simp: pre_adjust.simps post_del_def invar.simps(2) elim: sngl.elims)
   2.334  
   2.335  lemma pre_adj_if_postL:
   2.336 -  "invar\<langle>lv, l, a, r\<rangle> \<Longrightarrow> post_del l l' \<Longrightarrow> pre_adjust \<langle>lv, l', b, r\<rangle>"
   2.337 +  "invar\<langle>l, a, lv, r\<rangle> \<Longrightarrow> post_del l l' \<Longrightarrow> pre_adjust \<langle>l', b, lv, r\<rangle>"
   2.338  by(cases "sngl r")
   2.339    (auto simp: pre_adjust.simps post_del_def invar.simps(2) elim: sngl.elims)
   2.340  
   2.341  lemma post_del_adjL:
   2.342 -  "\<lbrakk> invar\<langle>lv, l, a, r\<rangle>; pre_adjust \<langle>lv, l', b, r\<rangle> \<rbrakk>
   2.343 -  \<Longrightarrow> post_del \<langle>lv, l, a, r\<rangle> (adjust \<langle>lv, l', b, r\<rangle>)"
   2.344 +  "\<lbrakk> invar\<langle>l, a, lv, r\<rangle>; pre_adjust \<langle>l', b, lv, r\<rangle> \<rbrakk>
   2.345 +  \<Longrightarrow> post_del \<langle>l, a, lv, r\<rangle> (adjust \<langle>l', b, lv, r\<rangle>)"
   2.346  unfolding post_del_def
   2.347  by (metis invar_adjust lvl_adjust sngl_NodeI sngl_adjust lvl.simps(2))
   2.348  
   2.349 @@ -412,10 +412,10 @@
   2.350  
   2.351  theorem post_delete: "invar t \<Longrightarrow> post_del t (delete x t)"
   2.352  proof (induction t)
   2.353 -  case (Node lv l a r)
   2.354 +  case (Node l a lv r)
   2.355  
   2.356    let ?l' = "delete x l" and ?r' = "delete x r"
   2.357 -  let ?t = "Node lv l a r" let ?t' = "delete x ?t"
   2.358 +  let ?t = "Node l a lv r" let ?t' = "delete x ?t"
   2.359  
   2.360    from Node.prems have inv_l: "invar l" and inv_r: "invar r" by (auto)
   2.361  
     3.1 --- a/src/HOL/Data_Structures/AVL_Map.thy	Mon Jun 11 08:15:43 2018 +0200
     3.2 +++ b/src/HOL/Data_Structures/AVL_Map.thy	Mon Jun 11 16:29:27 2018 +0200
     3.3 @@ -9,16 +9,16 @@
     3.4  begin
     3.5  
     3.6  fun update :: "'a::linorder \<Rightarrow> 'b \<Rightarrow> ('a*'b) avl_tree \<Rightarrow> ('a*'b) avl_tree" where
     3.7 -"update x y Leaf = Node 1 Leaf (x,y) Leaf" |
     3.8 -"update x y (Node h l (a,b) r) = (case cmp x a of
     3.9 -   EQ \<Rightarrow> Node h l (x,y) r |
    3.10 +"update x y Leaf = Node Leaf (x,y) 1 Leaf" |
    3.11 +"update x y (Node l (a,b) h r) = (case cmp x a of
    3.12 +   EQ \<Rightarrow> Node l (x,y) h r |
    3.13     LT \<Rightarrow> balL (update x y l) (a,b) r |
    3.14     GT \<Rightarrow> balR l (a,b) (update x y r))"
    3.15  
    3.16  fun delete :: "'a::linorder \<Rightarrow> ('a*'b) avl_tree \<Rightarrow> ('a*'b) avl_tree" where
    3.17  "delete _ Leaf = Leaf" |
    3.18 -"delete x (Node h l (a,b) r) = (case cmp x a of
    3.19 -   EQ \<Rightarrow> del_root (Node h l (a,b) r) |
    3.20 +"delete x (Node l (a,b) h r) = (case cmp x a of
    3.21 +   EQ \<Rightarrow> del_root (Node l (a,b) h r) |
    3.22     LT \<Rightarrow> balR (delete x l) (a,b) r |
    3.23     GT \<Rightarrow> balL l (a,b) (delete x r))"
    3.24  
     4.1 --- a/src/HOL/Data_Structures/AVL_Set.thy	Mon Jun 11 08:15:43 2018 +0200
     4.2 +++ b/src/HOL/Data_Structures/AVL_Set.thy	Mon Jun 11 16:29:27 2018 +0200
     4.3 @@ -18,25 +18,25 @@
     4.4  
     4.5  fun avl :: "'a avl_tree \<Rightarrow> bool" where
     4.6  "avl Leaf = True" |
     4.7 -"avl (Node h l a r) =
     4.8 +"avl (Node l a h r) =
     4.9   ((height l = height r \<or> height l = height r + 1 \<or> height r = height l + 1) \<and> 
    4.10    h = max (height l) (height r) + 1 \<and> avl l \<and> avl r)"
    4.11  
    4.12  fun ht :: "'a avl_tree \<Rightarrow> nat" where
    4.13  "ht Leaf = 0" |
    4.14 -"ht (Node h l a r) = h"
    4.15 +"ht (Node l a h r) = h"
    4.16  
    4.17  definition node :: "'a avl_tree \<Rightarrow> 'a \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
    4.18 -"node l a r = Node (max (ht l) (ht r) + 1) l a r"
    4.19 +"node l a r = Node l a (max (ht l) (ht r) + 1) r"
    4.20  
    4.21  definition balL :: "'a avl_tree \<Rightarrow> 'a \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
    4.22  "balL l a r =
    4.23    (if ht l = ht r + 2 then
    4.24       case l of 
    4.25 -       Node _ bl b br \<Rightarrow>
    4.26 +       Node bl b _ br \<Rightarrow>
    4.27           if ht bl < ht br then
    4.28             case br of
    4.29 -             Node _ cl c cr \<Rightarrow> node (node bl b cl) c (node cr a r)
    4.30 +             Node cl c _ cr \<Rightarrow> node (node bl b cl) c (node cr a r)
    4.31           else node bl b (node br a r)
    4.32     else node l a r)"
    4.33  
    4.34 @@ -44,38 +44,38 @@
    4.35  "balR l a r =
    4.36     (if ht r = ht l + 2 then
    4.37        case r of
    4.38 -        Node _ bl b br \<Rightarrow>
    4.39 +        Node bl b _ br \<Rightarrow>
    4.40            if ht bl > ht br then
    4.41              case bl of
    4.42 -              Node _ cl c cr \<Rightarrow> node (node l a cl) c (node cr b br)
    4.43 +              Node cl c _ cr \<Rightarrow> node (node l a cl) c (node cr b br)
    4.44            else node (node l a bl) b br
    4.45    else node l a r)"
    4.46  
    4.47  fun insert :: "'a::linorder \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
    4.48 -"insert x Leaf = Node 1 Leaf x Leaf" |
    4.49 -"insert x (Node h l a r) = (case cmp x a of
    4.50 -   EQ \<Rightarrow> Node h l a r |
    4.51 +"insert x Leaf = Node Leaf x 1 Leaf" |
    4.52 +"insert x (Node l a h r) = (case cmp x a of
    4.53 +   EQ \<Rightarrow> Node l a h r |
    4.54     LT \<Rightarrow> balL (insert x l) a r |
    4.55     GT \<Rightarrow> balR l a (insert x r))"
    4.56  
    4.57  fun split_max :: "'a avl_tree \<Rightarrow> 'a avl_tree * 'a" where
    4.58 -"split_max (Node _ l a r) =
    4.59 +"split_max (Node l a _ r) =
    4.60    (if r = Leaf then (l,a) else let (r',a') = split_max r in (balL l a r', a'))"
    4.61  
    4.62  lemmas split_max_induct = split_max.induct[case_names Node Leaf]
    4.63  
    4.64  fun del_root :: "'a avl_tree \<Rightarrow> 'a avl_tree" where
    4.65 -"del_root (Node h Leaf a r) = r" |
    4.66 -"del_root (Node h l a Leaf) = l" |
    4.67 -"del_root (Node h l a r) = (let (l', a') = split_max l in balR l' a' r)"
    4.68 +"del_root (Node Leaf a h r) = r" |
    4.69 +"del_root (Node l a h Leaf) = l" |
    4.70 +"del_root (Node l a h r) = (let (l', a') = split_max l in balR l' a' r)"
    4.71  
    4.72  lemmas del_root_cases = del_root.cases[case_names Leaf_t Node_Leaf Node_Node]
    4.73  
    4.74  fun delete :: "'a::linorder \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
    4.75  "delete _ Leaf = Leaf" |
    4.76 -"delete x (Node h l a r) =
    4.77 +"delete x (Node l a h r) =
    4.78    (case cmp x a of
    4.79 -     EQ \<Rightarrow> del_root (Node h l a r) |
    4.80 +     EQ \<Rightarrow> del_root (Node l a h r) |
    4.81       LT \<Rightarrow> balR (delete x l) a r |
    4.82       GT \<Rightarrow> balL l a (delete x r))"
    4.83  
    4.84 @@ -110,8 +110,8 @@
    4.85    (auto simp: inorder_balL split: if_splits prod.splits tree.split)
    4.86  
    4.87  lemma inorder_del_root:
    4.88 -  "inorder (del_root (Node h l a r)) = inorder l @ inorder r"
    4.89 -by(cases "Node h l a r" rule: del_root.cases)
    4.90 +  "inorder (del_root (Node l a h r)) = inorder l @ inorder r"
    4.91 +by(cases "Node l a h r" rule: del_root.cases)
    4.92    (auto simp: inorder_balL inorder_balR inorder_split_maxD split: if_splits prod.splits)
    4.93  
    4.94  theorem inorder_delete:
    4.95 @@ -188,7 +188,7 @@
    4.96    case Leaf
    4.97    with assms show ?thesis by (simp add: node_def balL_def)
    4.98  next
    4.99 -  case (Node ln ll lr lh)
   4.100 +  case Node
   4.101    with assms show ?thesis
   4.102    proof(cases "height l = height r + 2")
   4.103      case True
   4.104 @@ -208,7 +208,7 @@
   4.105    case Leaf
   4.106    with assms show ?thesis by (simp add: node_def balR_def)
   4.107  next
   4.108 -  case (Node rn rl rr rh)
   4.109 +  case Node
   4.110    with assms show ?thesis
   4.111    proof(cases "height r = height l + 2")
   4.112      case True
   4.113 @@ -230,7 +230,7 @@
   4.114          "(height (insert x t) = height t \<or> height (insert x t) = height t + 1)"
   4.115  using assms
   4.116  proof (induction t)
   4.117 -  case (Node h l a r)
   4.118 +  case (Node l a h r)
   4.119    case 1
   4.120    with Node show ?case
   4.121    proof(cases "x = a")
   4.122 @@ -307,14 +307,14 @@
   4.123           height x = height(fst (split_max x)) + 1"
   4.124  using assms
   4.125  proof (induct x rule: split_max_induct)
   4.126 -  case (Node h l a r)
   4.127 +  case (Node l a h r)
   4.128    case 1
   4.129    thus ?case using Node
   4.130      by (auto simp: height_balL height_balL2 avl_balL
   4.131        linorder_class.max.absorb1 linorder_class.max.absorb2
   4.132        split:prod.split)
   4.133  next
   4.134 -  case (Node h l a r)
   4.135 +  case (Node l a h r)
   4.136    case 2
   4.137    let ?r' = "fst (split_max r)"
   4.138    from \<open>avl x\<close> Node 2 have "avl l" and "avl r" by simp_all
   4.139 @@ -327,9 +327,9 @@
   4.140    shows "avl(del_root t)" 
   4.141  using assms
   4.142  proof (cases t rule:del_root_cases)
   4.143 -  case (Node_Node h lh ll ln lr n rh rl rn rr)
   4.144 -  let ?l = "Node lh ll ln lr"
   4.145 -  let ?r = "Node rh rl rn rr"
   4.146 +  case (Node_Node ll ln lh lr n h rl rn rh rr)
   4.147 +  let ?l = "Node ll ln lh lr"
   4.148 +  let ?r = "Node rl rn rh rr"
   4.149    let ?l' = "fst (split_max ?l)"
   4.150    from \<open>avl t\<close> and Node_Node have "avl ?r" by simp
   4.151    from \<open>avl t\<close> and Node_Node have "avl ?l" by simp
   4.152 @@ -347,9 +347,9 @@
   4.153    shows "height t = height(del_root t) \<or> height t = height(del_root t) + 1"
   4.154  using assms
   4.155  proof (cases t rule: del_root_cases)
   4.156 -  case (Node_Node h lh ll ln lr n rh rl rn rr)
   4.157 -  let ?l = "Node lh ll ln lr"
   4.158 -  let ?r = "Node rh rl rn rr"
   4.159 +  case (Node_Node ll ln lh lr n h rl rn rh rr)
   4.160 +  let ?l = "Node ll ln lh lr"
   4.161 +  let ?r = "Node rl rn rh rr"
   4.162    let ?l' = "fst (split_max ?l)"
   4.163    let ?t' = "balR ?l' (snd(split_max ?l)) ?r"
   4.164    from \<open>avl t\<close> and Node_Node have "avl ?r" by simp
   4.165 @@ -382,7 +382,7 @@
   4.166    shows "avl(delete x t)" and "height t = (height (delete x t)) \<or> height t = height (delete x t) + 1"
   4.167  using assms
   4.168  proof (induct t)
   4.169 -  case (Node h l n r)
   4.170 +  case (Node l n h r)
   4.171    case 1
   4.172    with Node show ?case
   4.173    proof(cases "x = n")
   4.174 @@ -403,8 +403,8 @@
   4.175    with Node show ?case
   4.176    proof(cases "x = n")
   4.177      case True
   4.178 -    with 1 have "height (Node h l n r) = height(del_root (Node h l n r))
   4.179 -      \<or> height (Node h l n r) = height(del_root (Node h l n r)) + 1"
   4.180 +    with 1 have "height (Node l n h r) = height(del_root (Node l n h r))
   4.181 +      \<or> height (Node l n h r) = height(del_root (Node l n h r)) + 1"
   4.182        by (subst height_del_root,simp_all)
   4.183      with True show ?thesis by simp
   4.184    next
   4.185 @@ -459,7 +459,7 @@
   4.186  
   4.187  lemma height_invers: 
   4.188    "(height t = 0) = (t = Leaf)"
   4.189 -  "avl t \<Longrightarrow> (height t = Suc h) = (\<exists> l a r . t = Node (Suc h) l a r)"
   4.190 +  "avl t \<Longrightarrow> (height t = Suc h) = (\<exists> l a r . t = Node l a (Suc h) r)"
   4.191  by (induction t) auto
   4.192  
   4.193  text \<open>Any AVL tree of height \<open>h\<close> has at least \<open>fib (h+2)\<close> leaves:\<close>
   4.194 @@ -472,7 +472,7 @@
   4.195  next
   4.196    case (3 h)
   4.197    from "3.prems" obtain l a r where
   4.198 -    [simp]: "t = Node (Suc(Suc h)) l a r" "avl l" "avl r"
   4.199 +    [simp]: "t = Node l a (Suc(Suc h)) r" "avl l" "avl r"
   4.200      and C: "
   4.201        height r = Suc h \<and> height l = Suc h
   4.202      \<or> height r = Suc h \<and> height l = h
     5.1 --- a/src/HOL/Data_Structures/Isin2.thy	Mon Jun 11 08:15:43 2018 +0200
     5.2 +++ b/src/HOL/Data_Structures/Isin2.thy	Mon Jun 11 16:29:27 2018 +0200
     5.3 @@ -11,7 +11,7 @@
     5.4  
     5.5  fun isin :: "('a::linorder,'b) tree \<Rightarrow> 'a \<Rightarrow> bool" where
     5.6  "isin Leaf x = False" |
     5.7 -"isin (Node _ l a r) x =
     5.8 +"isin (Node l a _ r) x =
     5.9    (case cmp x a of
    5.10       LT \<Rightarrow> isin l x |
    5.11       EQ \<Rightarrow> True |
     6.1 --- a/src/HOL/Data_Structures/Leftist_Heap.thy	Mon Jun 11 08:15:43 2018 +0200
     6.2 +++ b/src/HOL/Data_Structures/Leftist_Heap.thy	Mon Jun 11 16:29:27 2018 +0200
     6.3 @@ -12,7 +12,7 @@
     6.4  
     6.5  fun mset_tree :: "('a,'b) tree \<Rightarrow> 'a multiset" where
     6.6  "mset_tree Leaf = {#}" |
     6.7 -"mset_tree (Node _ l a r) = {#a#} + mset_tree l + mset_tree r"
     6.8 +"mset_tree (Node l a _ r) = {#a#} + mset_tree l + mset_tree r"
     6.9  
    6.10  type_synonym 'a lheap = "('a,nat)tree"
    6.11  
    6.12 @@ -22,27 +22,27 @@
    6.13  
    6.14  fun rk :: "'a lheap \<Rightarrow> nat" where
    6.15  "rk Leaf = 0" |
    6.16 -"rk (Node n _ _ _) = n"
    6.17 +"rk (Node _ _ n _) = n"
    6.18  
    6.19  text\<open>The invariants:\<close>
    6.20  
    6.21  fun (in linorder) heap :: "('a,'b) tree \<Rightarrow> bool" where
    6.22  "heap Leaf = True" |
    6.23 -"heap (Node _ l m r) =
    6.24 +"heap (Node l m _ r) =
    6.25    (heap l \<and> heap r \<and> (\<forall>x \<in> set_mset(mset_tree l + mset_tree r). m \<le> x))"
    6.26  
    6.27  fun ltree :: "'a lheap \<Rightarrow> bool" where
    6.28  "ltree Leaf = True" |
    6.29 -"ltree (Node n l a r) =
    6.30 +"ltree (Node l a n r) =
    6.31   (n = rank r + 1 \<and> rank l \<ge> rank r \<and> ltree l & ltree r)"
    6.32  
    6.33  definition node :: "'a lheap \<Rightarrow> 'a \<Rightarrow> 'a lheap \<Rightarrow> 'a lheap" where
    6.34  "node l a r =
    6.35   (let rl = rk l; rr = rk r
    6.36 -  in if rl \<ge> rr then Node (rr+1) l a r else Node (rl+1) r a l)"
    6.37 +  in if rl \<ge> rr then Node l a (rr+1) r else Node r a (rl+1) l)"
    6.38  
    6.39  fun get_min :: "'a lheap \<Rightarrow> 'a" where
    6.40 -"get_min(Node n l a r) = a"
    6.41 +"get_min(Node l a n r) = a"
    6.42  
    6.43  text \<open>For function \<open>merge\<close>:\<close>
    6.44  unbundle pattern_aliases
    6.45 @@ -51,25 +51,25 @@
    6.46  fun merge :: "'a::ord lheap \<Rightarrow> 'a lheap \<Rightarrow> 'a lheap" where
    6.47  "merge Leaf t2 = t2" |
    6.48  "merge t1 Leaf = t1" |
    6.49 -"merge (Node n1 l1 a1 r1 =: t1) (Node n2 l2 a2 r2 =: t2) =
    6.50 +"merge (Node l1 a1 n1 r1 =: t1) (Node l2 a2 n2 r2 =: t2) =
    6.51     (if a1 \<le> a2 then node l1 a1 (merge r1 t2)
    6.52      else node l2 a2 (merge r2 t1))"
    6.53  
    6.54  lemma merge_code: "merge t1 t2 = (case (t1,t2) of
    6.55    (Leaf, _) \<Rightarrow> t2 |
    6.56    (_, Leaf) \<Rightarrow> t1 |
    6.57 -  (Node n1 l1 a1 r1, Node n2 l2 a2 r2) \<Rightarrow>
    6.58 +  (Node l1 a1 n1 r1, Node l2 a2 n2 r2) \<Rightarrow>
    6.59      if a1 \<le> a2 then node l1 a1 (merge r1 t2) else node l2 a2 (merge r2 t1))"
    6.60  by(induction t1 t2 rule: merge.induct) (simp_all split: tree.split)
    6.61  
    6.62  hide_const (open) insert
    6.63  
    6.64  definition insert :: "'a::ord \<Rightarrow> 'a lheap \<Rightarrow> 'a lheap" where
    6.65 -"insert x t = merge (Node 1 Leaf x Leaf) t"
    6.66 +"insert x t = merge (Node Leaf x 1 Leaf) t"
    6.67  
    6.68  fun del_min :: "'a::ord lheap \<Rightarrow> 'a lheap" where
    6.69  "del_min Leaf = Leaf" |
    6.70 -"del_min (Node n l x r) = merge l r"
    6.71 +"del_min (Node l x n r) = merge l r"
    6.72  
    6.73  
    6.74  subsection "Lemmas"
    6.75 @@ -104,7 +104,7 @@
    6.76  
    6.77  lemma ltree_merge: "\<lbrakk> ltree l; ltree r \<rbrakk> \<Longrightarrow> ltree (merge l r)"
    6.78  proof(induction l r rule: merge.induct)
    6.79 -  case (3 n1 l1 a1 r1 n2 l2 a2 r2)
    6.80 +  case (3 l1 a1 n1 r1 l2 a2 n2 r2)
    6.81    show ?case (is "ltree(merge ?t1 ?t2)")
    6.82    proof cases
    6.83      assume "a1 \<le> a2"
    6.84 @@ -173,14 +173,14 @@
    6.85  proof(induction t)
    6.86    case Leaf show ?case by simp
    6.87  next
    6.88 -  case (Node n l a r)
    6.89 +  case (Node l a n r)
    6.90    hence "rank r \<le> rank l" by simp
    6.91    hence *: "(2::nat) ^ rank r \<le> 2 ^ rank l" by simp
    6.92 -  have "(2::nat) ^ rank \<langle>n, l, a, r\<rangle> = 2 ^ rank r + 2 ^ rank r"
    6.93 +  have "(2::nat) ^ rank \<langle>l, a, n, r\<rangle> = 2 ^ rank r + 2 ^ rank r"
    6.94      by(simp add: mult_2)
    6.95    also have "\<dots> \<le> size1 l + size1 r"
    6.96      using Node * by (simp del: power_increasing_iff)
    6.97 -  also have "\<dots> = size1 \<langle>n, l, a, r\<rangle>" by simp
    6.98 +  also have "\<dots> = size1 \<langle>l, a, n, r\<rangle>" by simp
    6.99    finally show ?case .
   6.100  qed
   6.101  
   6.102 @@ -189,16 +189,16 @@
   6.103  fun t_merge :: "'a::ord lheap \<Rightarrow> 'a lheap \<Rightarrow> nat" where
   6.104  "t_merge Leaf t2 = 1" |
   6.105  "t_merge t2 Leaf = 1" |
   6.106 -"t_merge (Node n1 l1 a1 r1 =: t1) (Node n2 l2 a2 r2 =: t2) =
   6.107 +"t_merge (Node l1 a1 n1 r1 =: t1) (Node l2 a2 n2 r2 =: t2) =
   6.108    (if a1 \<le> a2 then 1 + t_merge r1 t2
   6.109     else 1 + t_merge r2 t1)"
   6.110  
   6.111  definition t_insert :: "'a::ord \<Rightarrow> 'a lheap \<Rightarrow> nat" where
   6.112 -"t_insert x t = t_merge (Node 1 Leaf x Leaf) t"
   6.113 +"t_insert x t = t_merge (Node Leaf x 1 Leaf) t"
   6.114  
   6.115  fun t_del_min :: "'a::ord lheap \<Rightarrow> nat" where
   6.116  "t_del_min Leaf = 1" |
   6.117 -"t_del_min (Node n l a r) = t_merge l r"
   6.118 +"t_del_min (Node l a n r) = t_merge l r"
   6.119  
   6.120  lemma t_merge_rank: "t_merge l r \<le> rank l + rank r + 1"
   6.121  proof(induction l r rule: merge.induct)
   6.122 @@ -213,7 +213,7 @@
   6.123  by linarith
   6.124  
   6.125  corollary t_insert_log: "ltree t \<Longrightarrow> t_insert x t \<le> log 2 (size1 t) + 2"
   6.126 -using t_merge_log[of "Node 1 Leaf x Leaf" t]
   6.127 +using t_merge_log[of "Node Leaf x 1 Leaf" t]
   6.128  by(simp add: t_insert_def split: tree.split)
   6.129  
   6.130  (* FIXME mv ? *)
   6.131 @@ -234,7 +234,7 @@
   6.132  proof(cases t)
   6.133    case Leaf thus ?thesis using assms by simp
   6.134  next
   6.135 -  case [simp]: (Node _ t1 _ t2)
   6.136 +  case [simp]: (Node t1 _ _ t2)
   6.137    have "t_del_min t = t_merge t1 t2" by simp
   6.138    also have "\<dots> \<le> log 2 (size1 t1) + log 2 (size1 t2) + 1"
   6.139      using \<open>ltree t\<close> by (auto simp: t_merge_log simp del: t_merge.simps)
     7.1 --- a/src/HOL/Data_Structures/Lookup2.thy	Mon Jun 11 08:15:43 2018 +0200
     7.2 +++ b/src/HOL/Data_Structures/Lookup2.thy	Mon Jun 11 16:29:27 2018 +0200
     7.3 @@ -11,7 +11,7 @@
     7.4  
     7.5  fun lookup :: "('a::linorder * 'b, 'c) tree \<Rightarrow> 'a \<Rightarrow> 'b option" where
     7.6  "lookup Leaf x = None" |
     7.7 -"lookup (Node _ l (a,b) r) x =
     7.8 +"lookup (Node l (a,b) _ r) x =
     7.9    (case cmp x a of LT \<Rightarrow> lookup l x | GT \<Rightarrow> lookup r x | EQ \<Rightarrow> Some b)"
    7.10  
    7.11  lemma lookup_map_of:
     8.1 --- a/src/HOL/Data_Structures/RBT.thy	Mon Jun 11 08:15:43 2018 +0200
     8.2 +++ b/src/HOL/Data_Structures/RBT.thy	Mon Jun 11 16:29:27 2018 +0200
     8.3 @@ -10,8 +10,8 @@
     8.4  
     8.5  type_synonym 'a rbt = "('a,color)tree"
     8.6  
     8.7 -abbreviation R where "R l a r \<equiv> Node Red l a r"
     8.8 -abbreviation B where "B l a r \<equiv> Node Black l a r"
     8.9 +abbreviation R where "R l a r \<equiv> Node l a Red r"
    8.10 +abbreviation B where "B l a r \<equiv> Node l a Black r"
    8.11  
    8.12  fun baliL :: "'a rbt \<Rightarrow> 'a \<Rightarrow> 'a rbt \<Rightarrow> 'a rbt" where
    8.13  "baliL (R (R t1 a1 t2) a2 t3) a3 t4 = R (B t1 a1 t2) a2 (B t3 a3 t4)" |
    8.14 @@ -25,7 +25,7 @@
    8.15  
    8.16  fun paint :: "color \<Rightarrow> 'a rbt \<Rightarrow> 'a rbt" where
    8.17  "paint c Leaf = Leaf" |
    8.18 -"paint c (Node _ l a r) = Node c l a r"
    8.19 +"paint c (Node l a _ r) = Node l a c r"
    8.20  
    8.21  fun baldL :: "'a rbt \<Rightarrow> 'a \<Rightarrow> 'a rbt \<Rightarrow> 'a rbt" where
    8.22  "baldL (R t1 x t2) y t3 = R (B t1 x t2) y t3" |
     9.1 --- a/src/HOL/Data_Structures/RBT_Map.thy	Mon Jun 11 08:15:43 2018 +0200
     9.2 +++ b/src/HOL/Data_Structures/RBT_Map.thy	Mon Jun 11 16:29:27 2018 +0200
     9.3 @@ -27,7 +27,7 @@
     9.4  and delR :: "'a::linorder \<Rightarrow> ('a*'b)rbt \<Rightarrow> 'a*'b \<Rightarrow> ('a*'b)rbt \<Rightarrow> ('a*'b)rbt"
     9.5  where
     9.6  "del x Leaf = Leaf" |
     9.7 -"del x (Node c t1 (a,b) t2) = (case cmp x a of
     9.8 +"del x (Node t1 (a,b) c t2) = (case cmp x a of
     9.9    LT \<Rightarrow> delL x t1 (a,b) t2 |
    9.10    GT \<Rightarrow> delR x t1 (a,b) t2 |
    9.11    EQ \<Rightarrow> combine t1 t2)" |
    10.1 --- a/src/HOL/Data_Structures/RBT_Set.thy	Mon Jun 11 08:15:43 2018 +0200
    10.2 +++ b/src/HOL/Data_Structures/RBT_Set.thy	Mon Jun 11 16:29:27 2018 +0200
    10.3 @@ -28,11 +28,11 @@
    10.4  
    10.5  fun color :: "'a rbt \<Rightarrow> color" where
    10.6  "color Leaf = Black" |
    10.7 -"color (Node c _ _ _) = c"
    10.8 +"color (Node _ _ c _) = c"
    10.9  
   10.10  fun del :: "'a::linorder \<Rightarrow> 'a rbt \<Rightarrow> 'a rbt" where
   10.11  "del x Leaf = Leaf" |
   10.12 -"del x (Node _ l a r) =
   10.13 +"del x (Node l a _ r) =
   10.14    (case cmp x a of
   10.15       LT \<Rightarrow> if l \<noteq> Leaf \<and> color l = Black
   10.16             then baldL (del x l) a r else R (del x l) a r |
   10.17 @@ -97,20 +97,20 @@
   10.18  
   10.19  fun bheight :: "'a rbt \<Rightarrow> nat" where
   10.20  "bheight Leaf = 0" |
   10.21 -"bheight (Node c l x r) = (if c = Black then bheight l + 1 else bheight l)"
   10.22 +"bheight (Node l x c r) = (if c = Black then bheight l + 1 else bheight l)"
   10.23  
   10.24  fun invc :: "'a rbt \<Rightarrow> bool" where
   10.25  "invc Leaf = True" |
   10.26 -"invc (Node c l a r) =
   10.27 +"invc (Node l a c r) =
   10.28    (invc l \<and> invc r \<and> (c = Red \<longrightarrow> color l = Black \<and> color r = Black))"
   10.29  
   10.30  fun invc2 :: "'a rbt \<Rightarrow> bool" \<comment> \<open>Weaker version\<close> where
   10.31  "invc2 Leaf = True" |
   10.32 -"invc2 (Node c l a r) = (invc l \<and> invc r)"
   10.33 +"invc2 (Node l a c r) = (invc l \<and> invc r)"
   10.34  
   10.35  fun invh :: "'a rbt \<Rightarrow> bool" where
   10.36  "invh Leaf = True" |
   10.37 -"invh (Node c l x r) = (invh l \<and> invh r \<and> bheight l = bheight r)"
   10.38 +"invh (Node l x c r) = (invh l \<and> invh r \<and> bheight l = bheight r)"
   10.39  
   10.40  lemma invc2I: "invc t \<Longrightarrow> invc2 t"
   10.41  by (cases t) simp+
   10.42 @@ -232,7 +232,7 @@
   10.43     (color t = Red \<and> bheight (del x t) = bheight t \<and> invc (del x t) \<or>
   10.44      color t = Black \<and> bheight (del x t) = bheight t - 1 \<and> invc2 (del x t))"
   10.45  proof (induct x t rule: del.induct)
   10.46 -case (2 x c _ y)
   10.47 +case (2 x _ y c)
   10.48    have "x = y \<or> x < y \<or> x > y" by auto
   10.49    thus ?case proof (elim disjE)
   10.50      assume "x = y"
    11.1 --- a/src/HOL/Data_Structures/Set2_Join.thy	Mon Jun 11 08:15:43 2018 +0200
    11.2 +++ b/src/HOL/Data_Structures/Set2_Join.thy	Mon Jun 11 16:29:27 2018 +0200
    11.3 @@ -28,7 +28,7 @@
    11.4    \<Longrightarrow> bst (join l a r)"
    11.5  assumes inv_Leaf: "inv \<langle>\<rangle>"
    11.6  assumes inv_join: "\<lbrakk> inv l; inv r \<rbrakk> \<Longrightarrow> inv (join l k r)"
    11.7 -assumes inv_Node: "\<lbrakk> inv (Node h l x r) \<rbrakk> \<Longrightarrow> inv l \<and> inv r"
    11.8 +assumes inv_Node: "\<lbrakk> inv (Node l x h r) \<rbrakk> \<Longrightarrow> inv l \<and> inv r"
    11.9  begin
   11.10  
   11.11  declare set_join [simp]
   11.12 @@ -36,7 +36,7 @@
   11.13  subsection "\<open>split_min\<close>"
   11.14  
   11.15  fun split_min :: "('a,'b) tree \<Rightarrow> 'a \<times> ('a,'b) tree" where
   11.16 -"split_min (Node _ l x r) =
   11.17 +"split_min (Node l x _ r) =
   11.18    (if l = Leaf then (x,r) else let (m,l') = split_min l in (m, join l' x r))"
   11.19  
   11.20  lemma split_min_set:
   11.21 @@ -84,7 +84,7 @@
   11.22  
   11.23  fun split :: "('a,'b)tree \<Rightarrow> 'a \<Rightarrow> ('a,'b)tree \<times> bool \<times> ('a,'b)tree" where
   11.24  "split Leaf k = (Leaf, False, Leaf)" |
   11.25 -"split (Node _ l a r) k =
   11.26 +"split (Node l a _ r) k =
   11.27    (if k < a then let (l1,b,l2) = split l k in (l1, b, join l2 a r) else
   11.28     if a < k then let (r1,b,r2) = split r k in (join l a r1, b, r2)
   11.29     else (l, True, r))"
   11.30 @@ -145,7 +145,7 @@
   11.31  "union t1 t2 =
   11.32    (if t1 = Leaf then t2 else
   11.33     if t2 = Leaf then t1 else
   11.34 -   case t1 of Node _ l1 k r1 \<Rightarrow>
   11.35 +   case t1 of Node l1 k _ r1 \<Rightarrow>
   11.36     let (l2,_ ,r2) = split t2 k;
   11.37         l' = union l1 l2; r' = union r1 r2
   11.38     in join l' k r')"
   11.39 @@ -181,7 +181,7 @@
   11.40  "inter t1 t2 =
   11.41    (if t1 = Leaf then Leaf else
   11.42     if t2 = Leaf then Leaf else
   11.43 -   case t1 of Node _ l1 k r1 \<Rightarrow>
   11.44 +   case t1 of Node l1 k _ r1 \<Rightarrow>
   11.45     let (l2,kin,r2) = split t2 k;
   11.46         l' = inter l1 l2; r' = inter r1 r2
   11.47     in if kin then join l' k r' else join2 l' r')"
   11.48 @@ -196,7 +196,7 @@
   11.49    proof (cases t1)
   11.50      case Leaf thus ?thesis by (simp add: inter.simps)
   11.51    next
   11.52 -    case [simp]: (Node _ l1 k r1)
   11.53 +    case [simp]: (Node l1 k _ r1)
   11.54      show ?thesis
   11.55      proof (cases "t2 = Leaf")
   11.56        case True thus ?thesis by (simp add: inter.simps)
   11.57 @@ -246,7 +246,7 @@
   11.58  "diff t1 t2 =
   11.59    (if t1 = Leaf then Leaf else
   11.60     if t2 = Leaf then t1 else
   11.61 -   case t2 of Node _ l2 k r2 \<Rightarrow>
   11.62 +   case t2 of Node l2 k _ r2 \<Rightarrow>
   11.63     let (l1,_,r1) = split t1 k;
   11.64         l' = diff l1 l2; r' = diff r1 r2
   11.65     in join2 l' r')"
   11.66 @@ -261,7 +261,7 @@
   11.67    proof (cases t2)
   11.68      case Leaf thus ?thesis by (simp add: diff.simps)
   11.69    next
   11.70 -    case [simp]: (Node _ l2 k r2)
   11.71 +    case [simp]: (Node l2 k _ r2)
   11.72      show ?thesis
   11.73      proof (cases "t1 = Leaf")
   11.74        case True thus ?thesis by (simp add: diff.simps)
   11.75 @@ -341,7 +341,7 @@
   11.76  end
   11.77  
   11.78  interpretation unbal: Set2_Join
   11.79 -where join = "\<lambda>l x r. Node () l x r" and inv = "\<lambda>t. True"
   11.80 +where join = "\<lambda>l x r. Node l x () r" and inv = "\<lambda>t. True"
   11.81  proof (standard, goal_cases)
   11.82    case 1 show ?case by simp
   11.83  next
    12.1 --- a/src/HOL/Data_Structures/Tree2.thy	Mon Jun 11 08:15:43 2018 +0200
    12.2 +++ b/src/HOL/Data_Structures/Tree2.thy	Mon Jun 11 16:29:27 2018 +0200
    12.3 @@ -4,30 +4,30 @@
    12.4  
    12.5  datatype ('a,'b) tree =
    12.6    Leaf ("\<langle>\<rangle>") |
    12.7 -  Node 'b "('a,'b)tree" 'a "('a,'b) tree" ("(1\<langle>_,/ _,/ _,/ _\<rangle>)")
    12.8 +  Node "('a,'b)tree" 'a 'b "('a,'b) tree" ("(1\<langle>_,/ _,/ _,/ _\<rangle>)")
    12.9  
   12.10  fun inorder :: "('a,'b)tree \<Rightarrow> 'a list" where
   12.11  "inorder Leaf = []" |
   12.12 -"inorder (Node _ l a r) = inorder l @ a # inorder r"
   12.13 +"inorder (Node l a _ r) = inorder l @ a # inorder r"
   12.14  
   12.15  fun height :: "('a,'b) tree \<Rightarrow> nat" where
   12.16  "height Leaf = 0" |
   12.17 -"height (Node _ l a r) = max (height l) (height r) + 1"
   12.18 +"height (Node l a _ r) = max (height l) (height r) + 1"
   12.19  
   12.20  fun set_tree :: "('a,'b) tree \<Rightarrow> 'a set" where
   12.21  "set_tree Leaf = {}" |
   12.22 -"set_tree (Node _ l x r) = Set.insert x (set_tree l \<union> set_tree r)"
   12.23 +"set_tree (Node l a _ r) = Set.insert a (set_tree l \<union> set_tree r)"
   12.24  
   12.25  fun bst :: "('a::linorder,'b) tree \<Rightarrow> bool" where
   12.26  "bst Leaf = True" |
   12.27 -"bst (Node _ l a r) = (bst l \<and> bst r \<and> (\<forall>x \<in> set_tree l. x < a) \<and> (\<forall>x \<in> set_tree r. a < x))"
   12.28 +"bst (Node l a _ r) = (bst l \<and> bst r \<and> (\<forall>x \<in> set_tree l. x < a) \<and> (\<forall>x \<in> set_tree r. a < x))"
   12.29  
   12.30  definition size1 :: "('a,'b) tree \<Rightarrow> nat" where
   12.31  "size1 t = size t + 1"
   12.32  
   12.33  lemma size1_simps[simp]:
   12.34    "size1 \<langle>\<rangle> = 1"
   12.35 -  "size1 \<langle>u, l, x, r\<rangle> = size1 l + size1 r"
   12.36 +  "size1 \<langle>l, x, u, r\<rangle> = size1 l + size1 r"
   12.37  by (simp_all add: size1_def)
   12.38  
   12.39  lemma size1_ge0[simp]: "0 < size1 t"