10 text \<open>This theory implements the set operations \<open>insert\<close>, \<open>delete\<close>, |
10 text \<open>This theory implements the set operations \<open>insert\<close>, \<open>delete\<close>, |
11 \<open>union\<close>, \<open>inter\<close>section and \<open>diff\<close>erence. The implementation is based on binary search trees. |
11 \<open>union\<close>, \<open>inter\<close>section and \<open>diff\<close>erence. The implementation is based on binary search trees. |
12 All operations are reduced to a single operation \<open>join l x r\<close> that joins two BSTs \<open>l\<close> and \<open>r\<close> |
12 All operations are reduced to a single operation \<open>join l x r\<close> that joins two BSTs \<open>l\<close> and \<open>r\<close> |
13 and an element \<open>x\<close> such that \<open>l < x < r\<close>. |
13 and an element \<open>x\<close> such that \<open>l < x < r\<close>. |
14 |
14 |
15 The theory is based on theory @{theory "HOL-Data_Structures.Tree2"} where nodes have an additional field. |
15 The theory is based on theory \<^theory>\<open>HOL-Data_Structures.Tree2\<close> where nodes have an additional field. |
16 This field is ignored here but it means that this theory can be instantiated |
16 This field is ignored here but it means that this theory can be instantiated |
17 with red-black trees (see theory @{file "Set2_Join_RBT.thy"}) and other balanced trees. |
17 with red-black trees (see theory \<^file>\<open>Set2_Join_RBT.thy\<close>) and other balanced trees. |
18 This approach is very concrete and fixes the type of trees. |
18 This approach is very concrete and fixes the type of trees. |
19 Alternatively, one could assume some abstract type @{typ 't} of trees with suitable decomposition |
19 Alternatively, one could assume some abstract type \<^typ>\<open>'t\<close> of trees with suitable decomposition |
20 and recursion operators on it.\<close> |
20 and recursion operators on it.\<close> |
21 |
21 |
22 locale Set2_Join = |
22 locale Set2_Join = |
23 fixes join :: "('a::linorder,'b) tree \<Rightarrow> 'a \<Rightarrow> ('a,'b) tree \<Rightarrow> ('a,'b) tree" |
23 fixes join :: "('a::linorder,'b) tree \<Rightarrow> 'a \<Rightarrow> ('a,'b) tree \<Rightarrow> ('a,'b) tree" |
24 fixes inv :: "('a,'b) tree \<Rightarrow> bool" |
24 fixes inv :: "('a,'b) tree \<Rightarrow> bool" |
302 thus ?case |
302 thus ?case |
303 by(auto simp: diff.simps[of t1 t2] inv_join inv_join2 split_inv Let_def |
303 by(auto simp: diff.simps[of t1 t2] inv_join inv_join2 split_inv Let_def |
304 split!: tree.split prod.split dest: inv_Node) |
304 split!: tree.split prod.split dest: inv_Node) |
305 qed |
305 qed |
306 |
306 |
307 text \<open>Locale @{locale Set2_Join} implements locale @{locale Set2}:\<close> |
307 text \<open>Locale \<^locale>\<open>Set2_Join\<close> implements locale \<^locale>\<open>Set2\<close>:\<close> |
308 |
308 |
309 sublocale Set2 |
309 sublocale Set2 |
310 where empty = Leaf and insert = insert and delete = delete and isin = isin |
310 where empty = Leaf and insert = insert and delete = delete and isin = isin |
311 and union = union and inter = inter and diff = diff |
311 and union = union and inter = inter and diff = diff |
312 and set = set_tree and invar = "\<lambda>t. inv t \<and> bst t" |
312 and set = set_tree and invar = "\<lambda>t. inv t \<and> bst t" |