blob: 83d1b22e4f645fdd7ce67f42440d5325120b0d1d [file]
/-
Copyright (c) 2025 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/
prelude
import Init.Data.Array.Lemmas
import Init.Data.List.Nat.InsertIdx
/-!
# insertIdx
Proves various lemmas about `Array.insertIdx`.
-/
set_option linter.listVariables true -- Enforce naming conventions for `List`/`Array`/`Vector` variables.
set_option linter.indexVariables true -- Enforce naming conventions for index variables.
open Function
open Nat
namespace Array
universe u
variable {α : Type u}
section InsertIdx
variable {a : α}
@[simp] theorem toList_insertIdx (xs : Array α) (i x) (h) :
(xs.insertIdx i x h).toList = xs.toList.insertIdx i x := by
rcases xs with ⟨xs⟩
simp
@[simp]
theorem insertIdx_zero (xs : Array α) (x : α) : xs.insertIdx 0 x = #[x] ++ xs := by
rcases xs with ⟨xs⟩
simp
@[simp] theorem size_insertIdx {xs : Array α} (h : i ≤ xs.size) : (xs.insertIdx i a).size = xs.size + 1 := by
rcases xs with ⟨xs⟩
simp [List.length_insertIdx, h]
theorem eraseIdx_insertIdx (i : Nat) (xs : Array α) (h : i ≤ xs.size) :
(xs.insertIdx i a).eraseIdx i (by simp; omega) = xs := by
rcases xs with ⟨xs⟩
simp_all
theorem insertIdx_eraseIdx_of_ge {as : Array α}
(w₁ : i < as.size) (w₂ : j ≤ (as.eraseIdx i).size) (h : i ≤ j) :
(as.eraseIdx i).insertIdx j a =
(as.insertIdx (j + 1) a (by simp at w₂; omega)).eraseIdx i (by simp_all; omega) := by
cases as
simpa using List.insertIdx_eraseIdx_of_ge _ _ _ (by simpa) (by simpa)
theorem insertIdx_eraseIdx_of_le {as : Array α}
(w₁ : i < as.size) (w₂ : j ≤ (as.eraseIdx i).size) (h : j ≤ i) :
(as.eraseIdx i).insertIdx j a =
(as.insertIdx j a (by simp at w₂; omega)).eraseIdx (i + 1) (by simp_all) := by
cases as
simpa using List.insertIdx_eraseIdx_of_le _ _ _ (by simpa) (by simpa)
theorem insertIdx_comm (a b : α) (i j : Nat) (xs : Array α) (_ : i ≤ j) (_ : j ≤ xs.size) :
(xs.insertIdx i a).insertIdx (j + 1) b (by simpa) =
(xs.insertIdx j b).insertIdx i a (by simp; omega) := by
rcases xs with ⟨xs⟩
simpa using List.insertIdx_comm a b i j _ (by simpa) (by simpa)
theorem mem_insertIdx {xs : Array α} {h : i ≤ xs.size} : a ∈ xs.insertIdx i b h ↔ a = b ∨ a ∈ xs := by
rcases xs with ⟨xs⟩
simpa using List.mem_insertIdx (by simpa)
@[simp]
theorem insertIdx_size_self (xs : Array α) (x : α) : xs.insertIdx xs.size x = xs.push x := by
rcases xs with ⟨xs⟩
simp
theorem getElem_insertIdx {xs : Array α} {x : α} {i k : Nat} (w : i ≤ xs.size) (h : k < (xs.insertIdx i x).size) :
(xs.insertIdx i x)[k] =
if h₁ : k < i then
xs[k]'(by simp [size_insertIdx] at h; omega)
else
if h₂ : k = i then
x
else
xs[k-1]'(by simp [size_insertIdx] at h; omega) := by
cases xs
simp [List.getElem_insertIdx, w]
theorem getElem_insertIdx_of_lt {xs : Array α} {x : α} {i k : Nat} (w : i ≤ xs.size) (h : k < i) :
(xs.insertIdx i x)[k]'(by simp; omega) = xs[k] := by
simp [getElem_insertIdx, w, h]
theorem getElem_insertIdx_self {xs : Array α} {x : α} {i : Nat} (w : i ≤ xs.size) :
(xs.insertIdx i x)[i]'(by simp; omega) = x := by
simp [getElem_insertIdx, w]
theorem getElem_insertIdx_of_gt {xs : Array α} {x : α} {i k : Nat} (w : k ≤ xs.size) (h : k > i) :
(xs.insertIdx i x)[k]'(by simp; omega) = xs[k - 1]'(by omega) := by
simp [getElem_insertIdx, w, h]
rw [dif_neg (by omega), dif_neg (by omega)]
theorem getElem?_insertIdx {xs : Array α} {x : α} {i k : Nat} (h : i ≤ xs.size) :
(xs.insertIdx i x)[k]? =
if k < i then
xs[k]?
else
if k = i then
if k ≤ xs.size then some x else none
else
xs[k-1]? := by
cases xs
simp [List.getElem?_insertIdx, h]
theorem getElem?_insertIdx_of_lt {xs : Array α} {x : α} {i k : Nat} (w : i ≤ xs.size) (h : k < i) :
(xs.insertIdx i x)[k]? = xs[k]? := by
rw [getElem?_insertIdx, if_pos h]
theorem getElem?_insertIdx_self {xs : Array α} {x : α} {i : Nat} (w : i ≤ xs.size) :
(xs.insertIdx i x)[i]? = some x := by
rw [getElem?_insertIdx, if_neg (by omega), if_pos rfl, if_pos w]
theorem getElem?_insertIdx_of_ge {xs : Array α} {x : α} {i k : Nat} (w : i < k) (h : k ≤ xs.size) :
(xs.insertIdx i x)[k]? = xs[k - 1]? := by
rw [getElem?_insertIdx, if_neg (by omega), if_neg (by omega)]
end InsertIdx
end Array