src/HOL/Data_Structures/Set2_Join.thy
changeset 69597 ff784d5a5bfb
parent 68969 7a9118e63cad
child 70572 b63e5e4598d7
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
    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"