data.rbmap.default | 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

70fd9563

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

70fd9563

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -148,7 +148,7 @@ theorem findEntry_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt
     have h := to_rbtree_mem h; cases' h with v h₁
     have hex := Iff.mp (Std.RBSet.find?_correct _ _) h₁; cases' hex with e h₂
     exists e; cases t <;> simp [find_entry] at h₂ ⊢
-    · simp [Std.RBSet.find?, Std.RBNode.find?] at h₂ ; cases h₂
+    · simp [Std.RBSet.find?, Std.RBNode.find?] at h₂; cases h₂
     · cases' h₂ with h₂₁ h₂₂; constructor
       · have :=
           Std.RBSet.find?_eq_find?_of_eqv ⟨Std.RBNode.node t_lchild t_val t_rchild, p⟩
@@ -162,7 +162,7 @@ theorem findEntry_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt
         rw [← this]; exact h₂₁
       · cases e; apply eqv_keys_of_eqv_entries h₂₂
   · intro h; cases' h with e h
-    cases' h with h₁ h₂; cases t <;> simp [find_entry] at h₁ 
+    cases' h with h₁ h₂; cases t <;> simp [find_entry] at h₁
     · contradiction
     all_goals exact to_rbmap_mem (Std.RBSet.mem_of_find?_some h₁)
 #align rbmap.find_entry_correct Rbmap.findEntry_correct
@@ -189,7 +189,7 @@ theorem find_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt) :
     exists e.2; simp [find, h₁, to_value]
   · intro h
     cases' h with v h
-    simp [find] at h 
+    simp [find] at h
     have h := eq_some_of_to_value_eq_some h
     cases' h with k' h
     have heqv := eqv_of_find_entry_some h
@@ -207,7 +207,7 @@ theorem constains_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt
     intro h
     generalize he : find_entry m k = e
     cases e
-    · simp [he, Option.isSome] at h ; contradiction
+    · simp [he, Option.isSome] at h; contradiction
     · exact mem_of_find_entry_some he
 #align rbmap.constains_correct Rbmap.constains_correct
 
@@ -243,7 +243,7 @@ theorem incomp_or_mem_of_mem_ins [IsStrictWeakOrder α lt] {k₁ k₂ : α} {v :
 
 theorem eq_or_mem_of_mem_ins [IsStrictTotalOrder α lt] {k₁ k₂ : α} {v : β} {m : Rbmap α β lt} :
     k₁ ∈ m.insert k₂ v → k₁ = k₂ ∨ k₁ ∈ m := fun h =>
-  suffices k₁ ≈[lt]k₂ ∨ k₁ ∈ m by simp [eqv_lt_iff_eq] at this  <;> assumption
+  suffices k₁ ≈[lt]k₂ ∨ k₁ ∈ m by simp [eqv_lt_iff_eq] at this <;> assumption
   incomp_or_mem_of_mem_ins h
 #align rbmap.eq_or_mem_of_mem_ins Rbmap.eq_or_mem_of_mem_ins
 
@@ -253,7 +253,7 @@ theorem findEntry_insert_of_eqv [IsStrictWeakOrder α lt] (m : Rbmap α β lt) {
   intro h
   generalize h₁ : m.insert k₁ v = m'
   cases' m' with t p; cases t
-  · have := mem_insert k₁ m v; rw [h₁] at this ; apply absurd this; apply not_mem_mk_rbmap
+  · have := mem_insert k₁ m v; rw [h₁] at this; apply absurd this; apply not_mem_mk_rbmap
   all_goals
     simp [find_entry]; rw [← h₁, insert]; apply Std.RBSet.find?_insert_of_eqv
     apply eqv_entries_of_eqv_keys _ _ h
@@ -296,7 +296,7 @@ theorem findEntry_insert_of_disj [IsStrictWeakOrder α lt] {k₁ k₂ : α} (m :
     rw [← h₂, insert, Std.RBSet.find?_insert_of_disj _ h', h₁]
     rfl
   any_goals
-    simp [insert] at h₂ 
+    simp [insert] at h₂
     exact absurd h₂ (Std.RBSet.insert_ne_mkRBSet m (k₁, v))
   any_goals
     rw [h₂, h₁]; simp [find_entry]; rw [← h₂, ← h₁, insert, Std.RBSet.find?_insert_of_disj _ h']
@@ -309,7 +309,7 @@ theorem findEntry_insert_of_not_eqv [IsStrictWeakOrder α lt] {k₁ k₂ : α} (
   intro hn
   have he : lt k₁ k₂ ∨ lt k₂ k₁ :=
     by
-    simp [StrictWeakOrder.Equiv, Decidable.not_and_iff_or_not, Decidable.not_not_iff] at hn 
+    simp [StrictWeakOrder.Equiv, Decidable.not_and_iff_or_not, Decidable.not_not_iff] at hn
     assumption
   apply find_entry_insert_of_disj _ _ he
 #align rbmap.find_entry_insert_of_not_eqv Rbmap.findEntry_insert_of_not_eqv

70fd9563

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,8 +3,8 @@ 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.Rbmap.Basic
-import Mathbin.Data.Rbtree.Main
+import Data.Rbmap.Basic
+import Data.Rbtree.Main
 
 #align_import data.rbmap.default from "leanprover-community/mathlib"@"70fd9563a21e7b963887c9360bd29b2393e6225a"

70fd9563

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,15 +2,12 @@
 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.rbmap.default
-! leanprover-community/mathlib commit 70fd9563a21e7b963887c9360bd29b2393e6225a
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Rbmap.Basic
 import Mathbin.Data.Rbtree.Main
 
+#align_import data.rbmap.default from "leanprover-community/mathlib"@"70fd9563a21e7b963887c9360bd29b2393e6225a"
+
 universe u v
 
 namespace Rbmap

70fd9563

bump to nightly-2023-06-27-05

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

9377c86a

Diff

@@ -31,7 +31,8 @@ private def rbmapLtDec {α : Type u} {β : Type v} {lt : α → α → Prop} [h
 attribute [local instance] rbmap_lt_is_swo rbmap_lt_dec
 
 -- Helper lemmas for reusing rbtree results.
-private theorem to_rbtree_mem {k : α} {m : Rbmap α β lt} : k ∈ m → ∃ v : β, Rbtree.Mem (k, v) m :=
+private theorem to_rbtree_mem {k : α} {m : Rbmap α β lt} :
+    k ∈ m → ∃ v : β, Std.RBSet.Mem (k, v) m :=
   by
   cases' m with n p <;> cases n <;> intro h
   · exact False.elim h
@@ -49,24 +50,24 @@ private theorem eqv_entries [IsIrrefl α lt] (k : α) (v₁ v₂ : β) : (k, v
   And.intro (irrefl_of lt k) (irrefl_of lt k)
 
 private theorem to_rbmap_mem [IsStrictWeakOrder α lt] {k : α} {v : β} {m : Rbmap α β lt} :
-    Rbtree.Mem (k, v) m → k ∈ m :=
+    Std.RBSet.Mem (k, v) m → k ∈ m :=
   by
   cases' m with n p <;> cases n <;> intro h
   · exact False.elim h
   · simp [Membership.Mem, Rbmap.Mem]
     exact
-      @Rbtree.mem_of_mem_of_eqv _ _ _ ⟨Rbnode.red_node n_lchild n_val n_rchild, p⟩ _ _ h
+      @Std.RBSet.mem_of_mem_of_eqv _ _ _ ⟨Std.RBNode.node n_lchild n_val n_rchild, p⟩ _ _ h
         (eqv_entries _ _ _)
   · simp [Membership.Mem, Rbmap.Mem]
     exact
-      @Rbtree.mem_of_mem_of_eqv _ _ _ ⟨Rbnode.black_node n_lchild n_val n_rchild, p⟩ _ _ h
+      @Std.RBSet.mem_of_mem_of_eqv _ _ _ ⟨rbnode.black_node n_lchild n_val n_rchild, p⟩ _ _ h
         (eqv_entries _ _ _)
 
 private theorem to_rbtree_mem' [IsStrictWeakOrder α lt] {k : α} {m : Rbmap α β lt} (v : β) :
-    k ∈ m → Rbtree.Mem (k, v) m := by
+    k ∈ m → Std.RBSet.Mem (k, v) m := by
   intro h
   cases' to_rbtree_mem h with v' hm
-  apply Rbtree.mem_of_mem_of_eqv hm
+  apply Std.RBSet.mem_of_mem_of_eqv hm
   apply eqv_entries
 
 theorem eq_some_of_toValue_eq_some {e : Option (α × β)} {v : β} :
@@ -82,19 +83,20 @@ theorem eq_none_of_toValue_eq_none {e : Option (α × β)} : toValue e = none 
 
 -- Lemmas
 theorem not_mem_mkRbmap : ∀ k : α, k ∉ mkRbmap α β lt := by
-  simp [Membership.Mem, mkRbmap, mkRbtree, Rbmap.Mem]
+  simp [Membership.Mem, mkRbmap, Std.mkRBSet, Rbmap.Mem]
 #align rbmap.not_mem_mk_rbmap Rbmap.not_mem_mkRbmap
 
 theorem not_mem_of_empty {m : Rbmap α β lt} (k : α) : m.Empty = true → k ∉ m := by
   cases' m with n p <;> cases n <;>
-    simp [Membership.Mem, mkRbmap, mkRbtree, Rbmap.Mem, Rbmap.empty, Rbtree.empty, false_imp_iff]
+    simp [Membership.Mem, mkRbmap, Std.mkRBSet, Rbmap.Mem, Rbmap.empty, Std.RBSet.empty,
+      false_imp_iff]
 #align rbmap.not_mem_of_empty Rbmap.not_mem_of_empty
 
 theorem mem_of_mem_of_eqv [IsStrictWeakOrder α lt] {m : Rbmap α β lt} {k₁ k₂ : α} :
     k₁ ∈ m → k₁ ≈[lt]k₂ → k₂ ∈ m := by
   intro h₁ h₂
   have h₁ := to_rbtree_mem h₁; cases' h₁ with v h₁
-  exact to_rbmap_mem (Rbtree.mem_of_mem_of_eqv h₁ (eqv_entries_of_eqv_keys v v h₂))
+  exact to_rbmap_mem (Std.RBSet.mem_of_mem_of_eqv h₁ (eqv_entries_of_eqv_keys v v h₂))
 #align rbmap.mem_of_mem_of_eqv Rbmap.mem_of_mem_of_eqv
 
 section Decidable
@@ -105,7 +107,7 @@ theorem not_mem_of_findEntry_none [IsStrictWeakOrder α lt] {k : α} {m : Rbmap
     m.findEntry k = none → k ∉ m := by
   cases' m with t p; cases t <;> simp [find_entry]
   · intros; simp [Membership.Mem, Rbmap.Mem]
-  all_goals intro h; exact Rbtree.not_mem_of_find_none h
+  all_goals intro h; exact Std.RBSet.not_mem_of_find?_none h
 #align rbmap.not_mem_of_find_entry_none Rbmap.not_mem_of_findEntry_none
 
 theorem not_mem_of_find_none [IsStrictWeakOrder α lt] {k : α} {m : Rbmap α β lt} :
@@ -118,7 +120,7 @@ theorem not_mem_of_find_none [IsStrictWeakOrder α lt] {k : α} {m : Rbmap α β
 theorem mem_of_findEntry_some [IsStrictWeakOrder α lt] {k₁ : α} {e : α × β} {m : Rbmap α β lt} :
     m.findEntry k₁ = some e → k₁ ∈ m := by
   cases' m with t p; cases t <;> simp [find_entry, false_imp_iff]
-  all_goals intro h; exact Rbtree.mem_of_find_some h
+  all_goals intro h; exact Std.RBSet.mem_of_find?_some h
 #align rbmap.mem_of_find_entry_some Rbmap.mem_of_findEntry_some
 
 theorem mem_of_find_some [IsStrictWeakOrder α lt] {k : α} {v : β} {m : Rbmap α β lt} :
@@ -133,7 +135,7 @@ theorem findEntry_eq_findEntry_of_eqv [IsStrictWeakOrder α lt] {m : Rbmap α β
     k₁ ≈[lt]k₂ → m.findEntry k₁ = m.findEntry k₂ :=
   by
   intro h; cases' m with t p; cases t <;> simp [find_entry]
-  all_goals apply Rbtree.find_eq_find_of_eqv; apply eqv_entries_of_eqv_keys; assumption
+  all_goals apply Std.RBSet.find?_eq_find?_of_eqv; apply eqv_entries_of_eqv_keys; assumption
 #align rbmap.find_entry_eq_find_entry_of_eqv Rbmap.findEntry_eq_findEntry_of_eqv
 
 theorem find_eq_find_of_eqv [IsStrictWeakOrder α lt] {k₁ k₂ : α} (m : Rbmap α β lt) :
@@ -147,32 +149,32 @@ theorem findEntry_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt
   apply Iff.intro <;> cases' m with t p
   · intro h
     have h := to_rbtree_mem h; cases' h with v h₁
-    have hex := Iff.mp (Rbtree.find_correct _ _) h₁; cases' hex with e h₂
+    have hex := Iff.mp (Std.RBSet.find?_correct _ _) h₁; cases' hex with e h₂
     exists e; cases t <;> simp [find_entry] at h₂ ⊢
-    · simp [Rbtree.find, Rbnode.find] at h₂ ; cases h₂
+    · simp [Std.RBSet.find?, Std.RBNode.find?] at h₂ ; cases h₂
     · cases' h₂ with h₂₁ h₂₂; constructor
       · have :=
-          Rbtree.find_eq_find_of_eqv ⟨Rbnode.red_node t_lchild t_val t_rchild, p⟩
+          Std.RBSet.find?_eq_find?_of_eqv ⟨Std.RBNode.node t_lchild t_val t_rchild, p⟩
             (eqv_entries k v t_val.2)
         rw [← this]; exact h₂₁
       · cases e; apply eqv_keys_of_eqv_entries h₂₂
     · cases' h₂ with h₂₁ h₂₂; constructor
       · have :=
-          Rbtree.find_eq_find_of_eqv ⟨Rbnode.black_node t_lchild t_val t_rchild, p⟩
+          Std.RBSet.find?_eq_find?_of_eqv ⟨rbnode.black_node t_lchild t_val t_rchild, p⟩
             (eqv_entries k v t_val.2)
         rw [← this]; exact h₂₁
       · cases e; apply eqv_keys_of_eqv_entries h₂₂
   · intro h; cases' h with e h
     cases' h with h₁ h₂; cases t <;> simp [find_entry] at h₁ 
     · contradiction
-    all_goals exact to_rbmap_mem (Rbtree.mem_of_find_some h₁)
+    all_goals exact to_rbmap_mem (Std.RBSet.mem_of_find?_some h₁)
 #align rbmap.find_entry_correct Rbmap.findEntry_correct
 
 theorem eqv_of_findEntry_some [IsStrictWeakOrder α lt] {k₁ k₂ : α} {v : β} {m : Rbmap α β lt} :
     m.findEntry k₁ = some (k₂, v) → k₁ ≈[lt]k₂ :=
   by
   cases' m with t p; cases t <;> simp [find_entry, false_imp_iff]
-  all_goals intro h; exact eqv_keys_of_eqv_entries (Rbtree.eqv_of_find_some h)
+  all_goals intro h; exact eqv_keys_of_eqv_entries (Std.RBSet.eqv_of_find?_some h)
 #align rbmap.eqv_of_find_entry_some Rbmap.eqv_of_findEntry_some
 
 theorem eq_of_findEntry_some [IsStrictTotalOrder α lt] {k₁ k₂ : α} {v : β} {m : Rbmap α β lt} :
@@ -214,11 +216,11 @@ theorem constains_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt
 
 theorem mem_insert_of_incomp [IsStrictWeakOrder α lt] {k₁ k₂ : α} (m : Rbmap α β lt) (v : β) :
     ¬lt k₁ k₂ ∧ ¬lt k₂ k₁ → k₁ ∈ m.insert k₂ v := fun h =>
-  to_rbmap_mem (Rbtree.mem_insert_of_incomp m (eqv_entries_of_eqv_keys v v h))
+  to_rbmap_mem (Std.RBSet.mem_insert_of_incomp m (eqv_entries_of_eqv_keys v v h))
 #align rbmap.mem_insert_of_incomp Rbmap.mem_insert_of_incomp
 
 theorem mem_insert [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt) (v : β) : k ∈ m.insert k v :=
-  to_rbmap_mem (Rbtree.mem_insert (k, v) m)
+  to_rbmap_mem (Std.RBSet.mem_insert (k, v) m)
 #align rbmap.mem_insert Rbmap.mem_insert
 
 theorem mem_insert_of_equiv [IsStrictWeakOrder α lt] {k₁ k₂ : α} (m : Rbmap α β lt) (v : β) :
@@ -228,12 +230,12 @@ theorem mem_insert_of_equiv [IsStrictWeakOrder α lt] {k₁ k₂ : α} (m : Rbma
 
 theorem mem_insert_of_mem [IsStrictWeakOrder α lt] {k₁ : α} {m : Rbmap α β lt} (k₂ : α) (v : β) :
     k₁ ∈ m → k₁ ∈ m.insert k₂ v := fun h =>
-  to_rbmap_mem (Rbtree.mem_insert_of_mem (k₂, v) (to_rbtree_mem' v h))
+  to_rbmap_mem (Std.RBSet.mem_insert_of_mem (k₂, v) (to_rbtree_mem' v h))
 #align rbmap.mem_insert_of_mem Rbmap.mem_insert_of_mem
 
 theorem equiv_or_mem_of_mem_insert [IsStrictWeakOrder α lt] {k₁ k₂ : α} {v : β} {m : Rbmap α β lt} :
     k₁ ∈ m.insert k₂ v → k₁ ≈[lt]k₂ ∨ k₁ ∈ m := fun h =>
-  Or.elim (Rbtree.equiv_or_mem_of_mem_insert (to_rbtree_mem' v h))
+  Or.elim (Std.RBSet.equiv_or_mem_of_mem_insert (to_rbtree_mem' v h))
     (fun h => Or.inl (eqv_keys_of_eqv_entries h)) fun h => Or.inr (to_rbmap_mem h)
 #align rbmap.equiv_or_mem_of_mem_insert Rbmap.equiv_or_mem_of_mem_insert
 
@@ -256,7 +258,7 @@ theorem findEntry_insert_of_eqv [IsStrictWeakOrder α lt] (m : Rbmap α β lt) {
   cases' m' with t p; cases t
   · have := mem_insert k₁ m v; rw [h₁] at this ; apply absurd this; apply not_mem_mk_rbmap
   all_goals
-    simp [find_entry]; rw [← h₁, insert]; apply Rbtree.find_insert_of_eqv
+    simp [find_entry]; rw [← h₁, insert]; apply Std.RBSet.find?_insert_of_eqv
     apply eqv_entries_of_eqv_keys _ _ h
 #align rbmap.find_entry_insert_of_eqv Rbmap.findEntry_insert_of_eqv
 
@@ -294,14 +296,14 @@ theorem findEntry_insert_of_disj [IsStrictWeakOrder α lt] {k₁ k₂ : α} (m :
     conv =>
       lhs
       simp [find_entry]
-    rw [← h₂, insert, Rbtree.find_insert_of_disj _ h', h₁]
+    rw [← h₂, insert, Std.RBSet.find?_insert_of_disj _ h', h₁]
     rfl
   any_goals
     simp [insert] at h₂ 
-    exact absurd h₂ (Rbtree.insert_ne_mkRbtree m (k₁, v))
+    exact absurd h₂ (Std.RBSet.insert_ne_mkRBSet m (k₁, v))
   any_goals
-    rw [h₂, h₁]; simp [find_entry]; rw [← h₂, ← h₁, insert, Rbtree.find_insert_of_disj _ h']
-    apply Rbtree.find_eq_find_of_eqv; apply eqv_entries
+    rw [h₂, h₁]; simp [find_entry]; rw [← h₂, ← h₁, insert, Std.RBSet.find?_insert_of_disj _ h']
+    apply Std.RBSet.find?_eq_find?_of_eqv; apply eqv_entries
 #align rbmap.find_entry_insert_of_disj Rbmap.findEntry_insert_of_disj
 
 theorem findEntry_insert_of_not_eqv [IsStrictWeakOrder α lt] {k₁ k₂ : α} (m : Rbmap α β lt)
@@ -341,30 +343,30 @@ theorem find_insert_of_ne [IsStrictTotalOrder α lt] {k₁ k₂ : α} (m : Rbmap
 end Decidable
 
 theorem mem_of_min_eq [IsStrictTotalOrder α lt] {k : α} {v : β} {m : Rbmap α β lt} :
-    m.min = some (k, v) → k ∈ m := fun h => to_rbmap_mem (Rbtree.mem_of_min_eq h)
+    m.min = some (k, v) → k ∈ m := fun h => to_rbmap_mem (Std.RBSet.mem_of_min_eq h)
 #align rbmap.mem_of_min_eq Rbmap.mem_of_min_eq
 
 theorem mem_of_max_eq [IsStrictTotalOrder α lt] {k : α} {v : β} {m : Rbmap α β lt} :
-    m.max = some (k, v) → k ∈ m := fun h => to_rbmap_mem (Rbtree.mem_of_max_eq h)
+    m.max = some (k, v) → k ∈ m := fun h => to_rbmap_mem (Std.RBSet.mem_of_max_eq h)
 #align rbmap.mem_of_max_eq Rbmap.mem_of_max_eq
 
 theorem eq_leaf_of_min_eq_none {m : Rbmap α β lt} : m.min = none → m = mkRbmap α β lt :=
-  Rbtree.eq_leaf_of_min_eq_none
+  Std.RBSet.eq_leaf_of_min_eq_none
 #align rbmap.eq_leaf_of_min_eq_none Rbmap.eq_leaf_of_min_eq_none
 
 theorem eq_leaf_of_max_eq_none {m : Rbmap α β lt} : m.max = none → m = mkRbmap α β lt :=
-  Rbtree.eq_leaf_of_max_eq_none
+  Std.RBSet.eq_leaf_of_max_eq_none
 #align rbmap.eq_leaf_of_max_eq_none Rbmap.eq_leaf_of_max_eq_none
 
 theorem min_is_minimal [IsStrictWeakOrder α lt] {k : α} {v : β} {m : Rbmap α β lt} :
     m.min = some (k, v) → ∀ {k'}, k' ∈ m → k ≈[lt]k' ∨ lt k k' := fun h k' hm =>
-  Or.elim (Rbtree.min_is_minimal h (to_rbtree_mem' v hm))
+  Or.elim (Std.RBSet.min_is_minimal h (to_rbtree_mem' v hm))
     (fun h => Or.inl (eqv_keys_of_eqv_entries h)) fun h => Or.inr h
 #align rbmap.min_is_minimal Rbmap.min_is_minimal
 
 theorem max_is_maximal [IsStrictWeakOrder α lt] {k : α} {v : β} {m : Rbmap α β lt} :
     m.max = some (k, v) → ∀ {k'}, k' ∈ m → k ≈[lt]k' ∨ lt k' k := fun h k' hm =>
-  Or.elim (Rbtree.max_is_maximal h (to_rbtree_mem' v hm))
+  Or.elim (Std.RBSet.max_is_maximal h (to_rbtree_mem' v hm))
     (fun h => Or.inl (eqv_keys_of_eqv_entries h)) fun h => Or.inr h
 #align rbmap.max_is_maximal Rbmap.max_is_maximal

70fd9563

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -104,7 +104,7 @@ variable [DecidableRel lt]
 theorem not_mem_of_findEntry_none [IsStrictWeakOrder α lt] {k : α} {m : Rbmap α β lt} :
     m.findEntry k = none → k ∉ m := by
   cases' m with t p; cases t <;> simp [find_entry]
-  · intros ; simp [Membership.Mem, Rbmap.Mem]
+  · intros; simp [Membership.Mem, Rbmap.Mem]
   all_goals intro h; exact Rbtree.not_mem_of_find_none h
 #align rbmap.not_mem_of_find_entry_none Rbmap.not_mem_of_findEntry_none
 
@@ -148,8 +148,8 @@ theorem findEntry_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt
   · intro h
     have h := to_rbtree_mem h; cases' h with v h₁
     have hex := Iff.mp (Rbtree.find_correct _ _) h₁; cases' hex with e h₂
-    exists e; cases t <;> simp [find_entry] at h₂⊢
-    · simp [Rbtree.find, Rbnode.find] at h₂; cases h₂
+    exists e; cases t <;> simp [find_entry] at h₂ ⊢
+    · simp [Rbtree.find, Rbnode.find] at h₂ ; cases h₂
     · cases' h₂ with h₂₁ h₂₂; constructor
       · have :=
           Rbtree.find_eq_find_of_eqv ⟨Rbnode.red_node t_lchild t_val t_rchild, p⟩
@@ -163,7 +163,7 @@ theorem findEntry_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt
         rw [← this]; exact h₂₁
       · cases e; apply eqv_keys_of_eqv_entries h₂₂
   · intro h; cases' h with e h
-    cases' h with h₁ h₂; cases t <;> simp [find_entry] at h₁
+    cases' h with h₁ h₂; cases t <;> simp [find_entry] at h₁ 
     · contradiction
     all_goals exact to_rbmap_mem (Rbtree.mem_of_find_some h₁)
 #align rbmap.find_entry_correct Rbmap.findEntry_correct
@@ -190,7 +190,7 @@ theorem find_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt) :
     exists e.2; simp [find, h₁, to_value]
   · intro h
     cases' h with v h
-    simp [find] at h
+    simp [find] at h 
     have h := eq_some_of_to_value_eq_some h
     cases' h with k' h
     have heqv := eqv_of_find_entry_some h
@@ -208,7 +208,7 @@ theorem constains_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt
     intro h
     generalize he : find_entry m k = e
     cases e
-    · simp [he, Option.isSome] at h; contradiction
+    · simp [he, Option.isSome] at h ; contradiction
     · exact mem_of_find_entry_some he
 #align rbmap.constains_correct Rbmap.constains_correct
 
@@ -244,7 +244,7 @@ theorem incomp_or_mem_of_mem_ins [IsStrictWeakOrder α lt] {k₁ k₂ : α} {v :
 
 theorem eq_or_mem_of_mem_ins [IsStrictTotalOrder α lt] {k₁ k₂ : α} {v : β} {m : Rbmap α β lt} :
     k₁ ∈ m.insert k₂ v → k₁ = k₂ ∨ k₁ ∈ m := fun h =>
-  suffices k₁ ≈[lt]k₂ ∨ k₁ ∈ m by simp [eqv_lt_iff_eq] at this <;> assumption
+  suffices k₁ ≈[lt]k₂ ∨ k₁ ∈ m by simp [eqv_lt_iff_eq] at this  <;> assumption
   incomp_or_mem_of_mem_ins h
 #align rbmap.eq_or_mem_of_mem_ins Rbmap.eq_or_mem_of_mem_ins
 
@@ -254,7 +254,7 @@ theorem findEntry_insert_of_eqv [IsStrictWeakOrder α lt] (m : Rbmap α β lt) {
   intro h
   generalize h₁ : m.insert k₁ v = m'
   cases' m' with t p; cases t
-  · have := mem_insert k₁ m v; rw [h₁] at this; apply absurd this; apply not_mem_mk_rbmap
+  · have := mem_insert k₁ m v; rw [h₁] at this ; apply absurd this; apply not_mem_mk_rbmap
   all_goals
     simp [find_entry]; rw [← h₁, insert]; apply Rbtree.find_insert_of_eqv
     apply eqv_entries_of_eqv_keys _ _ h
@@ -286,7 +286,7 @@ theorem findEntry_insert_of_disj [IsStrictWeakOrder α lt] {k₁ k₂ : α} (m :
     fun _ _ => h
   generalize h₁ : m = m₁
   generalize h₂ : insert m₁ k₁ v = m₂
-  rw [← h₁] at h₂⊢; rw [← h₂]
+  rw [← h₁] at h₂ ⊢; rw [← h₂]
   cases' m₁ with t₁ p₁ <;> cases t₁ <;> cases' m₂ with t₂ p₂ <;> cases t₂
   · rw [h₂, h₁]
   iterate 2 
@@ -297,7 +297,7 @@ theorem findEntry_insert_of_disj [IsStrictWeakOrder α lt] {k₁ k₂ : α} (m :
     rw [← h₂, insert, Rbtree.find_insert_of_disj _ h', h₁]
     rfl
   any_goals
-    simp [insert] at h₂
+    simp [insert] at h₂ 
     exact absurd h₂ (Rbtree.insert_ne_mkRbtree m (k₁, v))
   any_goals
     rw [h₂, h₁]; simp [find_entry]; rw [← h₂, ← h₁, insert, Rbtree.find_insert_of_disj _ h']
@@ -310,7 +310,7 @@ theorem findEntry_insert_of_not_eqv [IsStrictWeakOrder α lt] {k₁ k₂ : α} (
   intro hn
   have he : lt k₁ k₂ ∨ lt k₂ k₁ :=
     by
-    simp [StrictWeakOrder.Equiv, Decidable.not_and_iff_or_not, Decidable.not_not_iff] at hn
+    simp [StrictWeakOrder.Equiv, Decidable.not_and_iff_or_not, Decidable.not_not_iff] at hn 
     assumption
   apply find_entry_insert_of_disj _ _ he
 #align rbmap.find_entry_insert_of_not_eqv Rbmap.findEntry_insert_of_not_eqv

70fd9563

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -73,8 +73,7 @@ theorem eq_some_of_toValue_eq_some {e : Option (α × β)} {v : β} :
     toValue e = some v → ∃ k, e = some (k, v) :=
   by
   cases' e with val <;> simp [to_value, false_imp_iff]
-  · cases val
-    simp
+  · cases val; simp
 #align rbmap.eq_some_of_to_value_eq_some Rbmap.eq_some_of_toValue_eq_some
 
 theorem eq_none_of_toValue_eq_none {e : Option (α × β)} : toValue e = none → e = none := by
@@ -105,8 +104,7 @@ variable [DecidableRel lt]
 theorem not_mem_of_findEntry_none [IsStrictWeakOrder α lt] {k : α} {m : Rbmap α β lt} :
     m.findEntry k = none → k ∉ m := by
   cases' m with t p; cases t <;> simp [find_entry]
-  · intros
-    simp [Membership.Mem, Rbmap.Mem]
+  · intros ; simp [Membership.Mem, Rbmap.Mem]
   all_goals intro h; exact Rbtree.not_mem_of_find_none h
 #align rbmap.not_mem_of_find_entry_none Rbmap.not_mem_of_findEntry_none
 
@@ -148,36 +146,24 @@ theorem findEntry_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt
   by
   apply Iff.intro <;> cases' m with t p
   · intro h
-    have h := to_rbtree_mem h
-    cases' h with v h₁
-    have hex := Iff.mp (Rbtree.find_correct _ _) h₁
-    cases' hex with e h₂
-    exists e
-    cases t <;> simp [find_entry] at h₂⊢
-    · simp [Rbtree.find, Rbnode.find] at h₂
-      cases h₂
-    · cases' h₂ with h₂₁ h₂₂
-      constructor
+    have h := to_rbtree_mem h; cases' h with v h₁
+    have hex := Iff.mp (Rbtree.find_correct _ _) h₁; cases' hex with e h₂
+    exists e; cases t <;> simp [find_entry] at h₂⊢
+    · simp [Rbtree.find, Rbnode.find] at h₂; cases h₂
+    · cases' h₂ with h₂₁ h₂₂; constructor
       · have :=
           Rbtree.find_eq_find_of_eqv ⟨Rbnode.red_node t_lchild t_val t_rchild, p⟩
             (eqv_entries k v t_val.2)
-        rw [← this]
-        exact h₂₁
-      · cases e
-        apply eqv_keys_of_eqv_entries h₂₂
-    · cases' h₂ with h₂₁ h₂₂
-      constructor
+        rw [← this]; exact h₂₁
+      · cases e; apply eqv_keys_of_eqv_entries h₂₂
+    · cases' h₂ with h₂₁ h₂₂; constructor
       · have :=
           Rbtree.find_eq_find_of_eqv ⟨Rbnode.black_node t_lchild t_val t_rchild, p⟩
             (eqv_entries k v t_val.2)
-        rw [← this]
-        exact h₂₁
-      · cases e
-        apply eqv_keys_of_eqv_entries h₂₂
-  · intro h
-    cases' h with e h
-    cases' h with h₁ h₂
-    cases t <;> simp [find_entry] at h₁
+        rw [← this]; exact h₂₁
+      · cases e; apply eqv_keys_of_eqv_entries h₂₂
+  · intro h; cases' h with e h
+    cases' h with h₁ h₂; cases t <;> simp [find_entry] at h₁
     · contradiction
     all_goals exact to_rbmap_mem (Rbtree.mem_of_find_some h₁)
 #align rbmap.find_entry_correct Rbmap.findEntry_correct
@@ -200,10 +186,8 @@ theorem find_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt) :
   apply Iff.intro
   · intro h
     have := Iff.mp (find_entry_correct k m) h
-    cases' this with e h
-    cases' h with h₁ h₂
-    exists e.2
-    simp [find, h₁, to_value]
+    cases' this with e h; cases' h with h₁ h₂
+    exists e.2; simp [find, h₁, to_value]
   · intro h
     cases' h with v h
     simp [find] at h
@@ -218,15 +202,13 @@ theorem constains_correct [IsStrictWeakOrder α lt] (k : α) (m : Rbmap α β lt
   apply Iff.intro
   · intro h
     have h := Iff.mp (find_entry_correct k m) h
-    cases' h with e h
-    cases' h with h₁ h₂
+    cases' h with e h; cases' h with h₁ h₂
     simp [contains, h₁, Option.isSome]
   · simp [contains]
     intro h
     generalize he : find_entry m k = e
     cases e
-    · simp [he, Option.isSome] at h
-      contradiction
+    · simp [he, Option.isSome] at h; contradiction
     · exact mem_of_find_entry_some he
 #align rbmap.constains_correct Rbmap.constains_correct
 
@@ -272,10 +254,7 @@ theorem findEntry_insert_of_eqv [IsStrictWeakOrder α lt] (m : Rbmap α β lt) {
   intro h
   generalize h₁ : m.insert k₁ v = m'
   cases' m' with t p; cases t
-  · have := mem_insert k₁ m v
-    rw [h₁] at this
-    apply absurd this
-    apply not_mem_mk_rbmap
+  · have := mem_insert k₁ m v; rw [h₁] at this; apply absurd this; apply not_mem_mk_rbmap
   all_goals
     simp [find_entry]; rw [← h₁, insert]; apply Rbtree.find_insert_of_eqv
     apply eqv_entries_of_eqv_keys _ _ h

70fd9563

bump to nightly-2023-05-28-03

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

6c6011cf

Diff

@@ -24,11 +24,9 @@ private def rbmap_lt_is_swo {α : Type u} {β : Type v} {lt : α → α → Prop
   irrefl _ := irrefl_of lt _
   trans _ _ _ h₁ h₂ := trans_of lt h₁ h₂
   incomp_trans _ _ _ h₁ h₂ := incomp_trans_of lt h₁ h₂
-#align rbmap.rbmap_lt_is_swo rbmap.rbmap_lt_is_swo
 
 private def rbmapLtDec {α : Type u} {β : Type v} {lt : α → α → Prop} [h : DecidableRel lt] :
     DecidableRel (@RbmapLt α β lt) := fun a b => h a.1 b.1
-#align rbmap.rbmap_lt_dec Rbmap.rbmapLtDec
 
 attribute [local instance] rbmap_lt_is_swo rbmap_lt_dec
 
@@ -38,21 +36,17 @@ private theorem to_rbtree_mem {k : α} {m : Rbmap α β lt} : k ∈ m → ∃ v
   cases' m with n p <;> cases n <;> intro h
   · exact False.elim h
   all_goals exists n_val.2; exact h
-#align rbmap.to_rbtree_mem rbmap.to_rbtree_mem
 
 private theorem eqv_entries_of_eqv_keys {k₁ k₂ : α} (v₁ v₂ : β) :
     k₁ ≈[lt]k₂ → (k₁, v₁) ≈[RbmapLt lt](k₂, v₂) :=
   id
-#align rbmap.eqv_entries_of_eqv_keys rbmap.eqv_entries_of_eqv_keys
 
 private theorem eqv_keys_of_eqv_entries {k₁ k₂ : α} {v₁ v₂ : β} :
     (k₁, v₁) ≈[RbmapLt lt](k₂, v₂) → k₁ ≈[lt]k₂ :=
   id
-#align rbmap.eqv_keys_of_eqv_entries rbmap.eqv_keys_of_eqv_entries
 
 private theorem eqv_entries [IsIrrefl α lt] (k : α) (v₁ v₂ : β) : (k, v₁) ≈[RbmapLt lt](k, v₂) :=
   And.intro (irrefl_of lt k) (irrefl_of lt k)
-#align rbmap.eqv_entries rbmap.eqv_entries
 
 private theorem to_rbmap_mem [IsStrictWeakOrder α lt] {k : α} {v : β} {m : Rbmap α β lt} :
     Rbtree.Mem (k, v) m → k ∈ m :=
@@ -67,7 +61,6 @@ private theorem to_rbmap_mem [IsStrictWeakOrder α lt] {k : α} {v : β} {m : Rb
     exact
       @Rbtree.mem_of_mem_of_eqv _ _ _ ⟨Rbnode.black_node n_lchild n_val n_rchild, p⟩ _ _ h
         (eqv_entries _ _ _)
-#align rbmap.to_rbmap_mem rbmap.to_rbmap_mem
 
 private theorem to_rbtree_mem' [IsStrictWeakOrder α lt] {k : α} {m : Rbmap α β lt} (v : β) :
     k ∈ m → Rbtree.Mem (k, v) m := by
@@ -75,7 +68,6 @@ private theorem to_rbtree_mem' [IsStrictWeakOrder α lt] {k : α} {m : Rbmap α
   cases' to_rbtree_mem h with v' hm
   apply Rbtree.mem_of_mem_of_eqv hm
   apply eqv_entries
-#align rbmap.to_rbtree_mem' rbmap.to_rbtree_mem'
 
 theorem eq_some_of_toValue_eq_some {e : Option (α × β)} {v : β} :
     toValue e = some v → ∃ k, e = some (k, v) :=

70fd9563

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

70fd9563

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.rbmap.default from "leanprover-community/mathlib"@"70fd9563a21e7b963887c9360bd29b2393e6225a"
 
 /-!
 # Porting note: essentially already ported to std4
 
-#align_import data.rbmap.default from "leanprover-community/mathlib"@"70fd9563a21e7b963887c9360bd29b2393e6225a"
-
 https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Mathlib4.20porting.20meeting.20series/near/369848971
 
 -/

70fd9563

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.rbmap.default
-! leanprover-community/mathlib commit 70fd9563a21e7b963887c9360bd29b2393e6225a
-! 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.rbmap.default from "leanprover-community/mathlib"@"70fd9563a21e7b963887c9360bd29b2393e6225a"
+
 https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Mathlib4.20porting.20meeting.20series/near/369848971
 
 -/

70fd9563

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

Cf. here. Incorporates #5479.

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

0171e873

`data.rbmap.default` ⟷ `Mathlib.Data.Rbmap.Default`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 15

data.rbmap.default ⟷ Mathlib.Data.Rbmap.Default

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 15

`data.rbmap.default` ⟷ `Mathlib.Data.Rbmap.Default`