data.rbtree.main | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

4d416710

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

4d416710

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -146,7 +146,7 @@ theorem Std.RBSet.not_mem_of_find?_none [IsStrictWeakOrder α lt] {a : α} {t :
     by
     intro h
     cases' h with _ h; cases' h with h₁ h₂
-    rw [h] at h₁ ; contradiction
+    rw [h] at h₁; contradiction
 #align rbtree.not_mem_of_find_none Std.RBSet.not_mem_of_find?_none
 
 theorem Std.RBSet.eqv_of_find?_some [IsStrictWeakOrder α lt] {a b : α} {t : Std.RBSet α lt} :
@@ -177,7 +177,7 @@ theorem Std.RBSet.contains_correct [IsStrictWeakOrder α lt] (a : α) (t : Std.R
   simp [h, contains]; apply Iff.intro
   · intro h'; cases' h' with _ h'; cases h'; simp [*]; simp [Option.isSome]
   · intro h'
-    cases' heq : find t a with v; simp [HEq, Option.isSome] at h' ; contradiction
+    cases' heq : find t a with v; simp [HEq, Option.isSome] at h'; contradiction
     exists v; simp; apply eqv_of_find_some HEq
 #align rbtree.contains_correct Std.RBSet.contains_correct
 
@@ -212,7 +212,7 @@ theorem Std.RBSet.incomp_or_mem_of_mem_ins {a b : α} {t : Std.RBSet α lt} :
 
 theorem Std.RBSet.eq_or_mem_of_mem_ins [IsStrictTotalOrder α lt] {a b : α} {t : Std.RBSet α lt} :
     a ∈ t.insert b → a = b ∨ a ∈ t := fun h =>
-  suffices a ≈[lt]b ∨ a ∈ t by simp [eqv_lt_iff_eq] at this  <;> assumption
+  suffices a ≈[lt]b ∨ a ∈ t by simp [eqv_lt_iff_eq] at this <;> assumption
   Std.RBSet.incomp_or_mem_of_mem_ins h
 #align rbtree.eq_or_mem_of_mem_ins Std.RBSet.eq_or_mem_of_mem_ins

4d416710

bump to nightly-2024-02-01-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

5433bded

Diff

@@ -237,7 +237,12 @@ theorem Std.RBSet.eq_leaf_of_max_eq_none {t : Std.RBSet α lt} :
 #align rbtree.eq_leaf_of_max_eq_none Std.RBSet.eq_leaf_of_max_eq_none
 
 theorem Std.RBSet.min_is_minimal [IsStrictWeakOrder α lt] {a : α} {t : Std.RBSet α lt} :
-    t.min = some a → ∀ {b}, b ∈ t → a ≈[lt]b ∨ lt a b := by classical
+    t.min = some a → ∀ {b}, b ∈ t → a ≈[lt]b ∨ lt a b := by
+  classical
+  cases t
+  apply Std.RBNode.min_is_minimal
+  apply Std.RBNode.isSearchableOfWellFormed
+  assumption
 #align rbtree.min_is_minimal Std.RBSet.min_is_minimal
 
 theorem Std.RBSet.max_is_maximal [IsStrictWeakOrder α lt] {a : α} {t : Std.RBSet α lt} :

4d416710

bump to nightly-2024-01-31-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

61100fe9

Diff

@@ -237,12 +237,7 @@ theorem Std.RBSet.eq_leaf_of_max_eq_none {t : Std.RBSet α lt} :
 #align rbtree.eq_leaf_of_max_eq_none Std.RBSet.eq_leaf_of_max_eq_none
 
 theorem Std.RBSet.min_is_minimal [IsStrictWeakOrder α lt] {a : α} {t : Std.RBSet α lt} :
-    t.min = some a → ∀ {b}, b ∈ t → a ≈[lt]b ∨ lt a b := by
-  classical
-  cases t
-  apply Std.RBNode.min_is_minimal
-  apply Std.RBNode.isSearchableOfWellFormed
-  assumption
+    t.min = some a → ∀ {b}, b ∈ t → a ≈[lt]b ∨ lt a b := by classical
 #align rbtree.min_is_minimal Std.RBSet.min_is_minimal
 
 theorem Std.RBSet.max_is_maximal [IsStrictWeakOrder α lt] {a : α} {t : Std.RBSet α lt} :

4d416710

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,10 +3,10 @@ Copyright (c) 2017 Microsoft Corporation. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura
 -/
-import Mathbin.Data.Rbtree.Find
-import Mathbin.Data.Rbtree.Insert
-import Mathbin.Data.Rbtree.MinMax
-import Mathbin.Order.RelClasses
+import Data.Rbtree.Find
+import Data.Rbtree.Insert
+import Data.Rbtree.MinMax
+import Order.RelClasses
 
 #align_import data.rbtree.main from "leanprover-community/mathlib"@"4d4167104581a21259f7f448e1972a63a4546be7"

4d416710

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2017 Microsoft Corporation. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura
-
-! This file was ported from Lean 3 source module data.rbtree.main
-! leanprover-community/mathlib commit 4d4167104581a21259f7f448e1972a63a4546be7
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Rbtree.Find
 import Mathbin.Data.Rbtree.Insert
 import Mathbin.Data.Rbtree.MinMax
 import Mathbin.Order.RelClasses
 
+#align_import data.rbtree.main from "leanprover-community/mathlib"@"4d4167104581a21259f7f448e1972a63a4546be7"
+
 universe u
 
 namespace Std.RBNode

4d416710

bump to nightly-2023-06-27-05

mathlib commit https://github.com/leanprover-community/mathlib/commit/8b981918a93bc45a8600de608cde7944a80d92b9

9377c86a

Diff

@@ -15,157 +15,166 @@ import Mathbin.Order.RelClasses
 
 universe u
 
-namespace Rbnode
+namespace Std.RBNode
 
 variable {α : Type u} {lt : α → α → Prop}
 
-theorem isSearchable_of_wellFormed {t : Rbnode α} [IsStrictWeakOrder α lt] :
-    t.WellFormed lt → IsSearchable lt t none none :=
+theorem Std.RBNode.isSearchableOfWellFormed {t : Std.RBNode α} [IsStrictWeakOrder α lt] :
+    t.WF lt → Std.RBNode.IsSearchable lt t none none :=
   by
   intro h; induction h
   · constructor; simp [lift]
   · subst h_n'; apply is_searchable_insert; assumption
-#align rbnode.is_searchable_of_well_formed Rbnode.isSearchable_of_wellFormed
+#align rbnode.is_searchable_of_well_formed Std.RBNode.isSearchableOfWellFormed
 
 open Color
 
-theorem isRedBlack_of_wellFormed {t : Rbnode α} : t.WellFormed lt → ∃ c n, IsRedBlack t c n :=
+theorem Std.RBNode.isRedBlack_of_wF {t : Std.RBNode α} :
+    t.WF lt → ∃ c n, Std.RBNode.IsRedBlack t c n :=
   by
   intro h; induction h
   · exists black; exists 0; constructor
   · cases' h_ih with c ih; cases' ih with n ih; subst h_n'; apply insert_is_red_black; assumption
-#align rbnode.is_red_black_of_well_formed Rbnode.isRedBlack_of_wellFormed
+#align rbnode.is_red_black_of_well_formed Std.RBNode.isRedBlack_of_wF
 
-end Rbnode
+end Std.RBNode
 
-namespace Rbtree
+namespace Std.RBSet
 
 variable {α : Type u} {lt : α → α → Prop}
 
-theorem balanced (t : Rbtree α lt) : t.depth max ≤ 2 * t.depth min + 1 :=
+theorem Std.RBSet.balanced (t : Std.RBSet α lt) : t.depth max ≤ 2 * t.depth min + 1 :=
   by
   cases' t with n p; simp only [depth]
-  have := Rbnode.isRedBlack_of_wellFormed p
+  have := Std.RBNode.isRedBlack_of_wF p
   cases' this with _ this; cases' this with _ this
-  apply Rbnode.balanced; assumption
-#align rbtree.balanced Rbtree.balanced
+  apply Std.RBNode.balanced; assumption
+#align rbtree.balanced Std.RBSet.balanced
 
-theorem not_mem_mkRbtree : ∀ a : α, a ∉ mkRbtree α lt := by
-  simp [Membership.Mem, Rbtree.Mem, Rbnode.Mem, mkRbtree]
-#align rbtree.not_mem_mk_rbtree Rbtree.not_mem_mkRbtree
+theorem Std.RBSet.not_mem_mkRBSet : ∀ a : α, a ∉ Std.mkRBSet α lt := by
+  simp [Membership.Mem, Std.RBSet.Mem, Std.RBNode.Mem, Std.mkRBSet]
+#align rbtree.not_mem_mk_rbtree Std.RBSet.not_mem_mkRBSet
 
-theorem not_mem_of_empty {t : Rbtree α lt} (a : α) : t.Empty = true → a ∉ t := by
+theorem Std.RBSet.not_mem_of_empty {t : Std.RBSet α lt} (a : α) : t.Empty = true → a ∉ t := by
   cases' t with n p <;> cases n <;>
-    simp [Empty, Membership.Mem, Rbtree.Mem, Rbnode.Mem, false_imp_iff]
-#align rbtree.not_mem_of_empty Rbtree.not_mem_of_empty
+    simp [Empty, Membership.Mem, Std.RBSet.Mem, Std.RBNode.Mem, false_imp_iff]
+#align rbtree.not_mem_of_empty Std.RBSet.not_mem_of_empty
 
-theorem mem_of_mem_of_eqv [IsStrictWeakOrder α lt] {t : Rbtree α lt} {a b : α} :
+theorem Std.RBSet.mem_of_mem_of_eqv [IsStrictWeakOrder α lt] {t : Std.RBSet α lt} {a b : α} :
     a ∈ t → a ≈[lt]b → b ∈ t :=
   by
-  cases' t with n p <;> simp [Membership.Mem, Rbtree.Mem] <;> clear p <;> induction n <;>
-        simp only [Rbnode.Mem, StrictWeakOrder.Equiv, false_imp_iff] <;>
+  cases' t with n p <;> simp [Membership.Mem, Std.RBSet.Mem] <;> clear p <;> induction n <;>
+        simp only [Std.RBNode.Mem, StrictWeakOrder.Equiv, false_imp_iff] <;>
       intro h₁ h₂ <;>
     cases_type* or.1
   iterate 2 
-    · have : Rbnode.Mem lt b n_lchild := n_ih_lchild h₁ h₂; simp [this]
+    · have : Std.RBNode.Mem lt b n_lchild := n_ih_lchild h₁ h₂; simp [this]
     · simp [incomp_trans_of lt h₂.swap h₁]
-    · have : Rbnode.Mem lt b n_rchild := n_ih_rchild h₁ h₂; simp [this]
-#align rbtree.mem_of_mem_of_eqv Rbtree.mem_of_mem_of_eqv
+    · have : Std.RBNode.Mem lt b n_rchild := n_ih_rchild h₁ h₂; simp [this]
+#align rbtree.mem_of_mem_of_eqv Std.RBSet.mem_of_mem_of_eqv
 
 section Dec
 
 variable [DecidableRel lt]
 
-theorem insert_ne_mkRbtree (t : Rbtree α lt) (a : α) : t.insert a ≠ mkRbtree α lt :=
+theorem Std.RBSet.insert_ne_mkRBSet (t : Std.RBSet α lt) (a : α) : t.insert a ≠ Std.mkRBSet α lt :=
   by
   cases' t with n p
-  simpa [insert, mkRbtree] using Rbnode.insert_ne_leaf lt n a
-#align rbtree.insert_ne_mk_rbtree Rbtree.insert_ne_mkRbtree
+  simpa [insert, Std.mkRBSet] using Std.RBNode.insert_ne_nil lt n a
+#align rbtree.insert_ne_mk_rbtree Std.RBSet.insert_ne_mkRBSet
 
-theorem find_correct [IsStrictWeakOrder α lt] (a : α) (t : Rbtree α lt) :
-    a ∈ t ↔ ∃ b, t.find a = some b ∧ a ≈[lt]b := by cases t; apply Rbnode.find_correct;
-  apply Rbnode.isSearchable_of_wellFormed; assumption
-#align rbtree.find_correct Rbtree.find_correct
+theorem Std.RBSet.find?_correct [IsStrictWeakOrder α lt] (a : α) (t : Std.RBSet α lt) :
+    a ∈ t ↔ ∃ b, t.find a = some b ∧ a ≈[lt]b := by cases t; apply Std.RBNode.find?_correct;
+  apply Std.RBNode.isSearchableOfWellFormed; assumption
+#align rbtree.find_correct Std.RBSet.find?_correct
 
-theorem find_correct_of_total [IsStrictTotalOrder α lt] (a : α) (t : Rbtree α lt) :
+theorem Std.RBSet.find?_correct_of_total [IsStrictTotalOrder α lt] (a : α) (t : Std.RBSet α lt) :
     a ∈ t ↔ t.find a = some a :=
   Iff.intro
     (fun h =>
-      match Iff.mp (find_correct a t) h with
+      match Iff.mp (Std.RBSet.find?_correct a t) h with
       | ⟨b, HEq, heqv⟩ => by simp [HEq, (eq_of_eqv_lt heqv).symm])
-    fun h => Iff.mpr (find_correct a t) ⟨a, ⟨h, refl a⟩⟩
-#align rbtree.find_correct_of_total Rbtree.find_correct_of_total
+    fun h => Iff.mpr (Std.RBSet.find?_correct a t) ⟨a, ⟨h, refl a⟩⟩
+#align rbtree.find_correct_of_total Std.RBSet.find?_correct_of_total
 
-theorem find_correct_exact [IsStrictTotalOrder α lt] (a : α) (t : Rbtree α lt) :
-    MemExact a t ↔ t.find a = some a := by cases t; apply Rbnode.find_correct_exact;
-  apply Rbnode.isSearchable_of_wellFormed; assumption
-#align rbtree.find_correct_exact Rbtree.find_correct_exact
+theorem Std.RBSet.find?_correct_exact [IsStrictTotalOrder α lt] (a : α) (t : Std.RBSet α lt) :
+    Std.RBSet.MemExact a t ↔ t.find a = some a := by cases t; apply Std.RBNode.find?_correct_exact;
+  apply Std.RBNode.isSearchableOfWellFormed; assumption
+#align rbtree.find_correct_exact Std.RBSet.find?_correct_exact
 
-theorem find_insert_of_eqv [IsStrictWeakOrder α lt] (t : Rbtree α lt) {x y} :
+theorem Std.RBSet.find?_insert_of_eqv [IsStrictWeakOrder α lt] (t : Std.RBSet α lt) {x y} :
     x ≈[lt]y → (t.insert x).find y = some x :=
   by
-  cases t; intro h; apply Rbnode.find_insert_of_eqv lt h; apply Rbnode.isSearchable_of_wellFormed
+  cases t; intro h; apply Std.RBNode.find?_insert_of_eqv lt h;
+  apply Std.RBNode.isSearchableOfWellFormed
   assumption
-#align rbtree.find_insert_of_eqv Rbtree.find_insert_of_eqv
+#align rbtree.find_insert_of_eqv Std.RBSet.find?_insert_of_eqv
 
-theorem find_insert [IsStrictWeakOrder α lt] (t : Rbtree α lt) (x) : (t.insert x).find x = some x :=
-  find_insert_of_eqv t (refl x)
-#align rbtree.find_insert Rbtree.find_insert
+#print Std.RBSet.find?_insert /-
+theorem Std.RBSet.find?_insert [IsStrictWeakOrder α lt] (t : Std.RBSet α lt) (x) :
+    (t.insert x).find x = some x :=
+  Std.RBSet.find?_insert_of_eqv t (refl x)
+#align rbtree.find_insert Std.RBSet.find?_insert
+-/
 
-theorem find_insert_of_disj [IsStrictWeakOrder α lt] {x y : α} (t : Rbtree α lt) :
+theorem Std.RBSet.find?_insert_of_disj [IsStrictWeakOrder α lt] {x y : α} (t : Std.RBSet α lt) :
     lt x y ∨ lt y x → (t.insert x).find y = t.find y :=
   by
-  cases t; intro h; apply Rbnode.find_insert_of_disj lt h
-  apply Rbnode.isSearchable_of_wellFormed
+  cases t; intro h; apply Std.RBNode.find?_insert_of_disj lt h
+  apply Std.RBNode.isSearchableOfWellFormed
   assumption
-#align rbtree.find_insert_of_disj Rbtree.find_insert_of_disj
+#align rbtree.find_insert_of_disj Std.RBSet.find?_insert_of_disj
 
-theorem find_insert_of_not_eqv [IsStrictWeakOrder α lt] {x y : α} (t : Rbtree α lt) :
+theorem Std.RBSet.find?_insert_of_not_eqv [IsStrictWeakOrder α lt] {x y : α} (t : Std.RBSet α lt) :
     ¬x ≈[lt]y → (t.insert x).find y = t.find y :=
   by
-  cases t; intro h; apply Rbnode.find_insert_of_not_eqv lt h
-  apply Rbnode.isSearchable_of_wellFormed; assumption
-#align rbtree.find_insert_of_not_eqv Rbtree.find_insert_of_not_eqv
+  cases t; intro h; apply Std.RBNode.find?_insert_of_not_eqv lt h
+  apply Std.RBNode.isSearchableOfWellFormed; assumption
+#align rbtree.find_insert_of_not_eqv Std.RBSet.find?_insert_of_not_eqv
 
-theorem find_insert_of_ne [IsStrictTotalOrder α lt] {x y : α} (t : Rbtree α lt) :
+#print Std.RBSet.find?_insert_of_ne /-
+theorem Std.RBSet.find?_insert_of_ne [IsStrictTotalOrder α lt] {x y : α} (t : Std.RBSet α lt) :
     x ≠ y → (t.insert x).find y = t.find y :=
   by
   cases t; intro h
   have : ¬x ≈[lt]y := fun h' => h (eq_of_eqv_lt h')
-  apply Rbnode.find_insert_of_not_eqv lt this
-  apply Rbnode.isSearchable_of_wellFormed; assumption
-#align rbtree.find_insert_of_ne Rbtree.find_insert_of_ne
+  apply Std.RBNode.find?_insert_of_not_eqv lt this
+  apply Std.RBNode.isSearchableOfWellFormed; assumption
+#align rbtree.find_insert_of_ne Std.RBSet.find?_insert_of_ne
+-/
 
-theorem not_mem_of_find_none [IsStrictWeakOrder α lt] {a : α} {t : Rbtree α lt} :
+theorem Std.RBSet.not_mem_of_find?_none [IsStrictWeakOrder α lt] {a : α} {t : Std.RBSet α lt} :
     t.find a = none → a ∉ t := fun h =>
-  Iff.mpr (not_congr (find_correct a t)) <| by
+  Iff.mpr (not_congr (Std.RBSet.find?_correct a t)) <|
+    by
     intro h
     cases' h with _ h; cases' h with h₁ h₂
     rw [h] at h₁ ; contradiction
-#align rbtree.not_mem_of_find_none Rbtree.not_mem_of_find_none
+#align rbtree.not_mem_of_find_none Std.RBSet.not_mem_of_find?_none
 
-theorem eqv_of_find_some [IsStrictWeakOrder α lt] {a b : α} {t : Rbtree α lt} :
-    t.find a = some b → a ≈[lt]b := by cases t; apply Rbnode.eqv_of_find_some;
-  apply Rbnode.isSearchable_of_wellFormed; assumption
-#align rbtree.eqv_of_find_some Rbtree.eqv_of_find_some
+theorem Std.RBSet.eqv_of_find?_some [IsStrictWeakOrder α lt] {a b : α} {t : Std.RBSet α lt} :
+    t.find a = some b → a ≈[lt]b := by cases t; apply Std.RBNode.eqv_of_find?_some;
+  apply Std.RBNode.isSearchableOfWellFormed; assumption
+#align rbtree.eqv_of_find_some Std.RBSet.eqv_of_find?_some
 
-theorem eq_of_find_some [IsStrictTotalOrder α lt] {a b : α} {t : Rbtree α lt} :
+theorem Std.RBSet.eq_of_find?_some [IsStrictTotalOrder α lt] {a b : α} {t : Std.RBSet α lt} :
     t.find a = some b → a = b := fun h =>
   suffices a ≈[lt]b from eq_of_eqv_lt this
-  eqv_of_find_some h
-#align rbtree.eq_of_find_some Rbtree.eq_of_find_some
+  Std.RBSet.eqv_of_find?_some h
+#align rbtree.eq_of_find_some Std.RBSet.eq_of_find?_some
 
-theorem mem_of_find_some [IsStrictWeakOrder α lt] {a b : α} {t : Rbtree α lt} :
-    t.find a = some b → a ∈ t := fun h => Iff.mpr (find_correct a t) ⟨b, ⟨h, eqv_of_find_some h⟩⟩
-#align rbtree.mem_of_find_some Rbtree.mem_of_find_some
+theorem Std.RBSet.mem_of_find?_some [IsStrictWeakOrder α lt] {a b : α} {t : Std.RBSet α lt} :
+    t.find a = some b → a ∈ t := fun h =>
+  Iff.mpr (Std.RBSet.find?_correct a t) ⟨b, ⟨h, Std.RBSet.eqv_of_find?_some h⟩⟩
+#align rbtree.mem_of_find_some Std.RBSet.mem_of_find?_some
 
-theorem find_eq_find_of_eqv [IsStrictWeakOrder α lt] {a b : α} (t : Rbtree α lt) :
+theorem Std.RBSet.find?_eq_find?_of_eqv [IsStrictWeakOrder α lt] {a b : α} (t : Std.RBSet α lt) :
     a ≈[lt]b → t.find a = t.find b := by
-  cases t; apply Rbnode.find_eq_find_of_eqv
-  apply Rbnode.isSearchable_of_wellFormed; assumption
-#align rbtree.find_eq_find_of_eqv Rbtree.find_eq_find_of_eqv
+  cases t; apply Std.RBNode.find?_eq_find?_of_eqv
+  apply Std.RBNode.isSearchableOfWellFormed; assumption
+#align rbtree.find_eq_find_of_eqv Std.RBSet.find?_eq_find?_of_eqv
 
-theorem contains_correct [IsStrictWeakOrder α lt] (a : α) (t : Rbtree α lt) :
+theorem Std.RBSet.contains_correct [IsStrictWeakOrder α lt] (a : α) (t : Std.RBSet α lt) :
     a ∈ t ↔ t.contains a = true := by
   have h := find_correct a t
   simp [h, contains]; apply Iff.intro
@@ -173,70 +182,76 @@ theorem contains_correct [IsStrictWeakOrder α lt] (a : α) (t : Rbtree α lt) :
   · intro h'
     cases' heq : find t a with v; simp [HEq, Option.isSome] at h' ; contradiction
     exists v; simp; apply eqv_of_find_some HEq
-#align rbtree.contains_correct Rbtree.contains_correct
+#align rbtree.contains_correct Std.RBSet.contains_correct
 
-theorem mem_insert_of_incomp {a b : α} (t : Rbtree α lt) : ¬lt a b ∧ ¬lt b a → a ∈ t.insert b := by
-  cases t; apply Rbnode.mem_insert_of_incomp
-#align rbtree.mem_insert_of_incomp Rbtree.mem_insert_of_incomp
+theorem Std.RBSet.mem_insert_of_incomp {a b : α} (t : Std.RBSet α lt) :
+    ¬lt a b ∧ ¬lt b a → a ∈ t.insert b := by cases t; apply Std.RBNode.mem_insert_of_incomp
+#align rbtree.mem_insert_of_incomp Std.RBSet.mem_insert_of_incomp
 
-theorem mem_insert [IsIrrefl α lt] : ∀ (a : α) (t : Rbtree α lt), a ∈ t.insert a := by intros;
-  apply mem_insert_of_incomp; constructor <;> apply irrefl_of lt
-#align rbtree.mem_insert Rbtree.mem_insert
+#print Std.RBSet.mem_insert /-
+theorem Std.RBSet.mem_insert [IsIrrefl α lt] : ∀ (a : α) (t : Std.RBSet α lt), a ∈ t.insert a := by
+  intros; apply mem_insert_of_incomp; constructor <;> apply irrefl_of lt
+#align rbtree.mem_insert Std.RBSet.mem_insert
+-/
 
-theorem mem_insert_of_equiv {a b : α} (t : Rbtree α lt) : a ≈[lt]b → a ∈ t.insert b := by cases t;
-  apply Rbnode.mem_insert_of_incomp
-#align rbtree.mem_insert_of_equiv Rbtree.mem_insert_of_equiv
+theorem Std.RBSet.mem_insert_of_equiv {a b : α} (t : Std.RBSet α lt) : a ≈[lt]b → a ∈ t.insert b :=
+  by cases t; apply Std.RBNode.mem_insert_of_incomp
+#align rbtree.mem_insert_of_equiv Std.RBSet.mem_insert_of_equiv
 
-theorem mem_insert_of_mem [IsStrictWeakOrder α lt] {a : α} {t : Rbtree α lt} (b : α) :
-    a ∈ t → a ∈ t.insert b := by cases t; apply Rbnode.mem_insert_of_mem
-#align rbtree.mem_insert_of_mem Rbtree.mem_insert_of_mem
+#print Std.RBSet.mem_insert_of_mem /-
+theorem Std.RBSet.mem_insert_of_mem [IsStrictWeakOrder α lt] {a : α} {t : Std.RBSet α lt} (b : α) :
+    a ∈ t → a ∈ t.insert b := by cases t; apply Std.RBNode.mem_insert_of_mem
+#align rbtree.mem_insert_of_mem Std.RBSet.mem_insert_of_mem
+-/
 
-theorem equiv_or_mem_of_mem_insert {a b : α} {t : Rbtree α lt} :
-    a ∈ t.insert b → a ≈[lt]b ∨ a ∈ t := by cases t; apply Rbnode.equiv_or_mem_of_mem_insert
-#align rbtree.equiv_or_mem_of_mem_insert Rbtree.equiv_or_mem_of_mem_insert
+theorem Std.RBSet.equiv_or_mem_of_mem_insert {a b : α} {t : Std.RBSet α lt} :
+    a ∈ t.insert b → a ≈[lt]b ∨ a ∈ t := by cases t; apply Std.RBNode.equiv_or_mem_of_mem_insert
+#align rbtree.equiv_or_mem_of_mem_insert Std.RBSet.equiv_or_mem_of_mem_insert
 
-theorem incomp_or_mem_of_mem_ins {a b : α} {t : Rbtree α lt} :
+theorem Std.RBSet.incomp_or_mem_of_mem_ins {a b : α} {t : Std.RBSet α lt} :
     a ∈ t.insert b → ¬lt a b ∧ ¬lt b a ∨ a ∈ t :=
-  equiv_or_mem_of_mem_insert
-#align rbtree.incomp_or_mem_of_mem_ins Rbtree.incomp_or_mem_of_mem_ins
+  Std.RBSet.equiv_or_mem_of_mem_insert
+#align rbtree.incomp_or_mem_of_mem_ins Std.RBSet.incomp_or_mem_of_mem_ins
 
-theorem eq_or_mem_of_mem_ins [IsStrictTotalOrder α lt] {a b : α} {t : Rbtree α lt} :
+theorem Std.RBSet.eq_or_mem_of_mem_ins [IsStrictTotalOrder α lt] {a b : α} {t : Std.RBSet α lt} :
     a ∈ t.insert b → a = b ∨ a ∈ t := fun h =>
   suffices a ≈[lt]b ∨ a ∈ t by simp [eqv_lt_iff_eq] at this  <;> assumption
-  incomp_or_mem_of_mem_ins h
-#align rbtree.eq_or_mem_of_mem_ins Rbtree.eq_or_mem_of_mem_ins
+  Std.RBSet.incomp_or_mem_of_mem_ins h
+#align rbtree.eq_or_mem_of_mem_ins Std.RBSet.eq_or_mem_of_mem_ins
 
 end Dec
 
-theorem mem_of_min_eq [IsIrrefl α lt] {a : α} {t : Rbtree α lt} : t.min = some a → a ∈ t := by
-  cases t; apply Rbnode.mem_of_min_eq
-#align rbtree.mem_of_min_eq Rbtree.mem_of_min_eq
+theorem Std.RBSet.mem_of_min_eq [IsIrrefl α lt] {a : α} {t : Std.RBSet α lt} :
+    t.min = some a → a ∈ t := by cases t; apply Std.RBNode.mem_of_min_eq
+#align rbtree.mem_of_min_eq Std.RBSet.mem_of_min_eq
 
-theorem mem_of_max_eq [IsIrrefl α lt] {a : α} {t : Rbtree α lt} : t.max = some a → a ∈ t := by
-  cases t; apply Rbnode.mem_of_max_eq
-#align rbtree.mem_of_max_eq Rbtree.mem_of_max_eq
+theorem Std.RBSet.mem_of_max_eq [IsIrrefl α lt] {a : α} {t : Std.RBSet α lt} :
+    t.max = some a → a ∈ t := by cases t; apply Std.RBNode.mem_of_max_eq
+#align rbtree.mem_of_max_eq Std.RBSet.mem_of_max_eq
 
-theorem eq_leaf_of_min_eq_none {t : Rbtree α lt} : t.min = none → t = mkRbtree α lt := by cases t;
-  intro h; congr; apply Rbnode.eq_leaf_of_min_eq_none h
-#align rbtree.eq_leaf_of_min_eq_none Rbtree.eq_leaf_of_min_eq_none
+theorem Std.RBSet.eq_leaf_of_min_eq_none {t : Std.RBSet α lt} :
+    t.min = none → t = Std.mkRBSet α lt := by cases t; intro h; congr;
+  apply Std.RBNode.eq_nil_of_min_eq_none h
+#align rbtree.eq_leaf_of_min_eq_none Std.RBSet.eq_leaf_of_min_eq_none
 
-theorem eq_leaf_of_max_eq_none {t : Rbtree α lt} : t.max = none → t = mkRbtree α lt := by cases t;
-  intro h; congr; apply Rbnode.eq_leaf_of_max_eq_none h
-#align rbtree.eq_leaf_of_max_eq_none Rbtree.eq_leaf_of_max_eq_none
+theorem Std.RBSet.eq_leaf_of_max_eq_none {t : Std.RBSet α lt} :
+    t.max = none → t = Std.mkRBSet α lt := by cases t; intro h; congr;
+  apply Std.RBNode.eq_nil_of_max_eq_none h
+#align rbtree.eq_leaf_of_max_eq_none Std.RBSet.eq_leaf_of_max_eq_none
 
-theorem min_is_minimal [IsStrictWeakOrder α lt] {a : α} {t : Rbtree α lt} :
+theorem Std.RBSet.min_is_minimal [IsStrictWeakOrder α lt] {a : α} {t : Std.RBSet α lt} :
     t.min = some a → ∀ {b}, b ∈ t → a ≈[lt]b ∨ lt a b := by
   classical
   cases t
-  apply Rbnode.min_is_minimal
-  apply Rbnode.isSearchable_of_wellFormed
+  apply Std.RBNode.min_is_minimal
+  apply Std.RBNode.isSearchableOfWellFormed
   assumption
-#align rbtree.min_is_minimal Rbtree.min_is_minimal
+#align rbtree.min_is_minimal Std.RBSet.min_is_minimal
 
-theorem max_is_maximal [IsStrictWeakOrder α lt] {a : α} {t : Rbtree α lt} :
-    t.max = some a → ∀ {b}, b ∈ t → a ≈[lt]b ∨ lt b a := by cases t; apply Rbnode.max_is_maximal;
-  apply Rbnode.isSearchable_of_wellFormed; assumption
-#align rbtree.max_is_maximal Rbtree.max_is_maximal
+theorem Std.RBSet.max_is_maximal [IsStrictWeakOrder α lt] {a : α} {t : Std.RBSet α lt} :
+    t.max = some a → ∀ {b}, b ∈ t → a ≈[lt]b ∨ lt b a := by cases t;
+  apply Std.RBNode.max_is_maximal; apply Std.RBNode.isSearchableOfWellFormed; assumption
+#align rbtree.max_is_maximal Std.RBSet.max_is_maximal
 
-end Rbtree
+end Std.RBSet

4d416710

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -65,7 +65,7 @@ theorem mem_of_mem_of_eqv [IsStrictWeakOrder α lt] {t : Rbtree α lt} {a b : α
   cases' t with n p <;> simp [Membership.Mem, Rbtree.Mem] <;> clear p <;> induction n <;>
         simp only [Rbnode.Mem, StrictWeakOrder.Equiv, false_imp_iff] <;>
       intro h₁ h₂ <;>
-    cases_type*or.1
+    cases_type* or.1
   iterate 2 
     · have : Rbnode.Mem lt b n_lchild := n_ih_lchild h₁ h₂; simp [this]
     · simp [incomp_trans_of lt h₂.swap h₁]
@@ -227,10 +227,10 @@ theorem eq_leaf_of_max_eq_none {t : Rbtree α lt} : t.max = none → t = mkRbtre
 theorem min_is_minimal [IsStrictWeakOrder α lt] {a : α} {t : Rbtree α lt} :
     t.min = some a → ∀ {b}, b ∈ t → a ≈[lt]b ∨ lt a b := by
   classical
-    cases t
-    apply Rbnode.min_is_minimal
-    apply Rbnode.isSearchable_of_wellFormed
-    assumption
+  cases t
+  apply Rbnode.min_is_minimal
+  apply Rbnode.isSearchable_of_wellFormed
+  assumption
 #align rbtree.min_is_minimal Rbtree.min_is_minimal
 
 theorem max_is_maximal [IsStrictWeakOrder α lt] {a : α} {t : Rbtree α lt} :

4d416710

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -141,7 +141,7 @@ theorem not_mem_of_find_none [IsStrictWeakOrder α lt] {a : α} {t : Rbtree α l
   Iff.mpr (not_congr (find_correct a t)) <| by
     intro h
     cases' h with _ h; cases' h with h₁ h₂
-    rw [h] at h₁; contradiction
+    rw [h] at h₁ ; contradiction
 #align rbtree.not_mem_of_find_none Rbtree.not_mem_of_find_none
 
 theorem eqv_of_find_some [IsStrictWeakOrder α lt] {a b : α} {t : Rbtree α lt} :
@@ -171,7 +171,7 @@ theorem contains_correct [IsStrictWeakOrder α lt] (a : α) (t : Rbtree α lt) :
   simp [h, contains]; apply Iff.intro
   · intro h'; cases' h' with _ h'; cases h'; simp [*]; simp [Option.isSome]
   · intro h'
-    cases' heq : find t a with v; simp [HEq, Option.isSome] at h'; contradiction
+    cases' heq : find t a with v; simp [HEq, Option.isSome] at h' ; contradiction
     exists v; simp; apply eqv_of_find_some HEq
 #align rbtree.contains_correct Rbtree.contains_correct
 
@@ -179,7 +179,7 @@ theorem mem_insert_of_incomp {a b : α} (t : Rbtree α lt) : ¬lt a b ∧ ¬lt b
   cases t; apply Rbnode.mem_insert_of_incomp
 #align rbtree.mem_insert_of_incomp Rbtree.mem_insert_of_incomp
 
-theorem mem_insert [IsIrrefl α lt] : ∀ (a : α) (t : Rbtree α lt), a ∈ t.insert a := by intros ;
+theorem mem_insert [IsIrrefl α lt] : ∀ (a : α) (t : Rbtree α lt), a ∈ t.insert a := by intros;
   apply mem_insert_of_incomp; constructor <;> apply irrefl_of lt
 #align rbtree.mem_insert Rbtree.mem_insert
 
@@ -202,7 +202,7 @@ theorem incomp_or_mem_of_mem_ins {a b : α} {t : Rbtree α lt} :
 
 theorem eq_or_mem_of_mem_ins [IsStrictTotalOrder α lt] {a b : α} {t : Rbtree α lt} :
     a ∈ t.insert b → a = b ∨ a ∈ t := fun h =>
-  suffices a ≈[lt]b ∨ a ∈ t by simp [eqv_lt_iff_eq] at this <;> assumption
+  suffices a ≈[lt]b ∨ a ∈ t by simp [eqv_lt_iff_eq] at this  <;> assumption
   incomp_or_mem_of_mem_ins h
 #align rbtree.eq_or_mem_of_mem_ins Rbtree.eq_or_mem_of_mem_ins
 
@@ -217,11 +217,11 @@ theorem mem_of_max_eq [IsIrrefl α lt] {a : α} {t : Rbtree α lt} : t.max = som
 #align rbtree.mem_of_max_eq Rbtree.mem_of_max_eq
 
 theorem eq_leaf_of_min_eq_none {t : Rbtree α lt} : t.min = none → t = mkRbtree α lt := by cases t;
-  intro h; congr ; apply Rbnode.eq_leaf_of_min_eq_none h
+  intro h; congr; apply Rbnode.eq_leaf_of_min_eq_none h
 #align rbtree.eq_leaf_of_min_eq_none Rbtree.eq_leaf_of_min_eq_none
 
 theorem eq_leaf_of_max_eq_none {t : Rbtree α lt} : t.max = none → t = mkRbtree α lt := by cases t;
-  intro h; congr ; apply Rbnode.eq_leaf_of_max_eq_none h
+  intro h; congr; apply Rbnode.eq_leaf_of_max_eq_none h
 #align rbtree.eq_leaf_of_max_eq_none Rbtree.eq_leaf_of_max_eq_none
 
 theorem min_is_minimal [IsStrictWeakOrder α lt] {a : α} {t : Rbtree α lt} :

4d416710

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -23,11 +23,8 @@ theorem isSearchable_of_wellFormed {t : Rbnode α} [IsStrictWeakOrder α lt] :
     t.WellFormed lt → IsSearchable lt t none none :=
   by
   intro h; induction h
-  · constructor
-    simp [lift]
-  · subst h_n'
-    apply is_searchable_insert
-    assumption
+  · constructor; simp [lift]
+  · subst h_n'; apply is_searchable_insert; assumption
 #align rbnode.is_searchable_of_well_formed Rbnode.isSearchable_of_wellFormed
 
 open Color
@@ -35,14 +32,8 @@ open Color
 theorem isRedBlack_of_wellFormed {t : Rbnode α} : t.WellFormed lt → ∃ c n, IsRedBlack t c n :=
   by
   intro h; induction h
-  · exists black
-    exists 0
-    constructor
-  · cases' h_ih with c ih
-    cases' ih with n ih
-    subst h_n'
-    apply insert_is_red_black
-    assumption
+  · exists black; exists 0; constructor
+  · cases' h_ih with c ih; cases' ih with n ih; subst h_n'; apply insert_is_red_black; assumption
 #align rbnode.is_red_black_of_well_formed Rbnode.isRedBlack_of_wellFormed
 
 end Rbnode
@@ -75,13 +66,10 @@ theorem mem_of_mem_of_eqv [IsStrictWeakOrder α lt] {t : Rbtree α lt} {a b : α
         simp only [Rbnode.Mem, StrictWeakOrder.Equiv, false_imp_iff] <;>
       intro h₁ h₂ <;>
     cases_type*or.1
-  iterate 2
-    
-    · have : Rbnode.Mem lt b n_lchild := n_ih_lchild h₁ h₂
-      simp [this]
+  iterate 2 
+    · have : Rbnode.Mem lt b n_lchild := n_ih_lchild h₁ h₂; simp [this]
     · simp [incomp_trans_of lt h₂.swap h₁]
-    · have : Rbnode.Mem lt b n_rchild := n_ih_rchild h₁ h₂
-      simp [this]
+    · have : Rbnode.Mem lt b n_rchild := n_ih_rchild h₁ h₂; simp [this]
 #align rbtree.mem_of_mem_of_eqv Rbtree.mem_of_mem_of_eqv
 
 section Dec
@@ -181,18 +169,10 @@ theorem contains_correct [IsStrictWeakOrder α lt] (a : α) (t : Rbtree α lt) :
     a ∈ t ↔ t.contains a = true := by
   have h := find_correct a t
   simp [h, contains]; apply Iff.intro
+  · intro h'; cases' h' with _ h'; cases h'; simp [*]; simp [Option.isSome]
   · intro h'
-    cases' h' with _ h'
-    cases h'
-    simp [*]
-    simp [Option.isSome]
-  · intro h'
-    cases' heq : find t a with v
-    simp [HEq, Option.isSome] at h'
-    contradiction
-    exists v
-    simp
-    apply eqv_of_find_some HEq
+    cases' heq : find t a with v; simp [HEq, Option.isSome] at h'; contradiction
+    exists v; simp; apply eqv_of_find_some HEq
 #align rbtree.contains_correct Rbtree.contains_correct
 
 theorem mem_insert_of_incomp {a b : α} (t : Rbtree α lt) : ¬lt a b ∧ ¬lt b a → a ∈ t.insert b := by
@@ -254,12 +234,8 @@ theorem min_is_minimal [IsStrictWeakOrder α lt] {a : α} {t : Rbtree α lt} :
 #align rbtree.min_is_minimal Rbtree.min_is_minimal
 
 theorem max_is_maximal [IsStrictWeakOrder α lt] {a : α} {t : Rbtree α lt} :
-    t.max = some a → ∀ {b}, b ∈ t → a ≈[lt]b ∨ lt b a :=
-  by
-  cases t
-  apply Rbnode.max_is_maximal
-  apply Rbnode.isSearchable_of_wellFormed
-  assumption
+    t.max = some a → ∀ {b}, b ∈ t → a ≈[lt]b ∨ lt b a := by cases t; apply Rbnode.max_is_maximal;
+  apply Rbnode.isSearchable_of_wellFormed; assumption
 #align rbtree.max_is_maximal Rbtree.max_is_maximal
 
 end Rbtree

4d416710

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

4d416710

chore: move #align_import out of comment (#6165)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

1919f537

Diff

@@ -3,12 +3,13 @@ Copyright (c) 2017 Microsoft Corporation. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura
 -/
+import Mathlib.Mathport.Rename
+
+#align_import data.rbtree.main from "leanprover-community/mathlib"@"4d4167104581a21259f7f448e1972a63a4546be7"
 
 /-!
 # Porting note: essentially already ported to std4
 
-#align_import data.rbtree.main from "leanprover-community/mathlib"@"4d4167104581a21259f7f448e1972a63a4546be7"
-
 https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Mathlib4.20porting.20meeting.20series/near/369848971
 
 -/

4d416710

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,16 +2,13 @@
 Copyright (c) 2017 Microsoft Corporation. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura
-
-! This file was ported from Lean 3 source module data.rbtree.main
-! leanprover-community/mathlib commit 4d4167104581a21259f7f448e1972a63a4546be7
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 
 /-!
 # Porting note: essentially already ported to std4
 
+#align_import data.rbtree.main from "leanprover-community/mathlib"@"4d4167104581a21259f7f448e1972a63a4546be7"
+
 https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Mathlib4.20porting.20meeting.20series/near/369848971
 
 -/

4d416710

feat: "port" Rbmap and Rbtree files (#5504)

Cf. here. Incorporates #5479.

Co-authored-by: Johan Commelin <johan@commelin.net>

0171e873

`data.rbtree.main` ⟷ `Mathlib.Data.Rbtree.Main`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 14

data.rbtree.main ⟷ Mathlib.Data.Rbtree.Main

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 14

`data.rbtree.main` ⟷ `Mathlib.Data.Rbtree.Main`