blob: 3225bddda7725448e7467daa43245e8b98c9416b [file]
/-
Copyright (c) 2025 Robin Arnez. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Robin Arnez, Markus Himmel, Paul Reichert
-/
module
prelude
public import Std.Data.ExtTreeMap.Basic
@[expose] public section
/-!
# Extensional tree sets
This file develops the type `Std.ExtTreeSet` of tree sets.
Lemmas about the operations on `Std.Data.ExtTreeSet` will be available in the
module `Std.Data.ExtTreeSet.Lemmas`.
See the module `Std.Data.TreeSet.Raw.Basic` for a variant of this type which is safe to use in
nested inductive types.
-/
set_option autoImplicit false
set_option linter.missingDocs true
universe u v w w₂
variable {α : Type u} {cmp : α → α → Ordering}
namespace Std
/--
Extensional tree sets.
A tree set stores elements of a certain type in a certain order. It depends on a comparator function
that defines an ordering on the keys and provides efficient order-dependent queries, such as
retrieval of the minimum or maximum.
To ensure that the operations behave as expected, the comparator function `cmp` should satisfy
certain laws that ensure a consistent ordering:
* If `a` is less than (or equal) to `b`, then `b` is greater than (or equal) to `a`
and vice versa (see the `OrientedCmp` typeclass).
* If `a` is less than or equal to `b` and `b` is, in turn, less than or equal to `c`, then `a`
is less than or equal to `c` (see the `TransCmp` typeclass).
Keys for which `cmp a b = Ordering.eq` are considered the same, i.e., there can be only one of them
be contained in a single tree set at the same time.
To avoid expensive copies, users should make sure that the tree set is used linearly.
Internally, the tree sets are represented as size-bounded trees, a type of self-balancing binary
search tree with efficient order statistic lookups.
In contrast to regular dependent tree maps, `Std.ExtTreeSet` offers several extensionality lemmas
and therefore has more lemmas about equality of tree sets. This doesn't affect the amount of
supported functions though: `Std.ExtTreeSet` supports all operations from `Std.TreeMap`.
In order to use most functions, a `TransCmp` instance is required. This is necessary to make sure
that the functions are congruent, i.e. equivalent tree sets as parameters produce equivalent return
values.
These tree sets contain a bundled well-formedness invariant, which means that they cannot
be used in nested inductive types. For these use cases, `Std.TreeSet.Raw` and
`Std.TreeSet.Raw.WF` unbundle the invariant from the tree set. When in doubt, prefer
`ExtTreeSet` over `TreeSet.Raw`.
-/
structure ExtTreeSet (α : Type u) (cmp : α → α → Ordering := by exact compare) where
/-- Internal implementation detail of the tree map. -/
inner : ExtTreeMap α Unit cmp
namespace ExtTreeSet
/--
Creates a new empty tree set. It is also possible and recommended to
use the empty collection notations `∅` and `{}` to create an empty tree set. `simp` replaces
`empty` with `∅`.
-/
@[inline]
def empty : ExtTreeSet α cmp :=
⟨ExtTreeMap.empty⟩
instance : EmptyCollection (ExtTreeSet α cmp) where
emptyCollection := empty
instance : Inhabited (ExtTreeSet α cmp) where
default := ∅
@[simp, grind =]
theorem empty_eq_emptyc : (empty : ExtTreeSet α cmp) = ∅ :=
rfl
/--
Inserts the given element into the set. If the tree set already contains an element that is
equal (with regard to `cmp`) to the given element, then the tree set is returned unchanged.
Note: this non-replacement behavior is true for `ExtTreeSet` and `ExtTreeSet.Raw`.
The `insert` function on `ExtTreeMap`, `ExtDTreeMap`, `ExtTreeMap.Raw` and `ExtDTreeMap.Raw` behaves
differently: it will overwrite an existing mapping.
-/
@[inline]
def insert [TransCmp cmp] (l : ExtTreeSet α cmp) (a : α) : ExtTreeSet α cmp :=
⟨l.inner.insertIfNew a ()⟩
instance [TransCmp cmp] : Singleton α (ExtTreeSet α cmp) where
singleton e := (∅ : ExtTreeSet α cmp).insert e
instance [TransCmp cmp] : Insert α (ExtTreeSet α cmp) where
insert e s := s.insert e
instance [TransCmp cmp] : LawfulSingleton α (ExtTreeSet α cmp) where
insert_empty_eq _ := rfl
/--
Checks whether an element is present in a set and inserts the element if it was not found.
If the tree set already contains an element that is equal (with regard to `cmp` to the given
element, then the tree set is returned unchanged.
Equivalent to (but potentially faster than) calling `contains` followed by `insert`.
-/
@[inline]
def containsThenInsert [TransCmp cmp] (t : ExtTreeSet α cmp) (a : α) : Bool × ExtTreeSet α cmp :=
let p := t.inner.containsThenInsertIfNew a ()
(p.1, ⟨p.2⟩)
/--
Returns `true` if `a`, or an element equal to `a` according to the comparator `cmp`, is contained
in the set. There is also a `Prop`-valued version of this: `a ∈ t` is equivalent to
`t.contains a = true`.
Observe that this is different behavior than for lists: for lists, `∈` uses `=` and `contains` uses
`==` for equality checks, while for tree sets, both use the given comparator `cmp`.
-/
@[inline]
def contains [TransCmp cmp] (l : ExtTreeSet α cmp) (a : α) : Bool :=
l.inner.contains a
instance [TransCmp cmp] : Membership α (ExtTreeSet α cmp) where
mem m a := m.contains a
instance [TransCmp cmp] {m : ExtTreeSet α cmp} {a : α} : Decidable (a ∈ m) :=
inferInstanceAs <| Decidable (m.contains a)
/-- Returns the number of mappings present in the map. -/
@[inline]
def size (t : ExtTreeSet α cmp) : Nat :=
t.inner.size
/-- Returns `true` if the tree set contains no mappings. -/
@[inline]
def isEmpty (t : ExtTreeSet α cmp) : Bool :=
t.inner.isEmpty
/-- Removes the given key if it exists. -/
@[inline]
def erase [TransCmp cmp] (t : ExtTreeSet α cmp) (a : α) : ExtTreeSet α cmp :=
⟨t.inner.erase a⟩
/--
Checks if given key is contained and returns the key if it is, otherwise `none`.
The result in the `some` case is guaranteed to be pointer equal to the key in the map.
-/
@[inline]
def get? [TransCmp cmp] (t : ExtTreeSet α cmp) (a : α) : Option α :=
t.inner.getKey? a
/--
Retrieves the key from the set that matches `a`. Ensures that such a key exists by requiring a proof
of `a ∈ m`. The result is guaranteed to be pointer equal to the key in the set.
-/
@[inline]
def get [TransCmp cmp] (t : ExtTreeSet α cmp) (a : α) (h : a ∈ t) : α :=
t.inner.getKey a h
/--
Checks if given key is contained and returns the key if it is, otherwise panics.
If no panic occurs the result is guaranteed to be pointer equal to the key in the set.
-/
@[inline]
def get! [TransCmp cmp] [Inhabited α] (t : ExtTreeSet α cmp) (a : α) : α :=
t.inner.getKey! a
/--
Checks if given key is contained and returns the key if it is, otherwise `fallback`.
If they key is contained the result is guaranteed to be pointer equal to the key in the set.
-/
@[inline]
def getD [TransCmp cmp] (t : ExtTreeSet α cmp) (a : α) (fallback : α) : α :=
t.inner.getKeyD a fallback
/--
Tries to retrieve the smallest element of the tree set, returning `none` if the set is empty.
-/
@[inline]
def min? [TransCmp cmp] (t : ExtTreeSet α cmp) : Option α :=
ExtTreeMap.minKey? t.inner
/--
Given a proof that the tree set is not empty, retrieves the smallest element.
-/
@[inline]
def min [TransCmp cmp] (t : ExtTreeSet α cmp) (h : t ≠ ∅) : α :=
ExtTreeMap.minKey t.inner (fun _ => nomatch t)
/--
Tries to retrieve the smallest element of the tree set, panicking if the set is empty.
-/
@[inline]
def min! [TransCmp cmp] [Inhabited α] (t : ExtTreeSet α cmp) : α :=
ExtTreeMap.minKey! t.inner
/--
Tries to retrieve the smallest element of the tree set, returning `fallback` if the tree set is empty.
-/
@[inline]
def minD [TransCmp cmp] (t : ExtTreeSet α cmp) (fallback : α) : α :=
ExtTreeMap.minKeyD t.inner fallback
/--
Tries to retrieve the largest element of the tree set, returning `none` if the set is empty.
-/
@[inline]
def max? [TransCmp cmp] (t : ExtTreeSet α cmp) : Option α :=
ExtTreeMap.maxKey? t.inner
/--
Given a proof that the tree set is not empty, retrieves the largest element.
-/
@[inline]
def max [TransCmp cmp] (t : ExtTreeSet α cmp) (h : t ≠ ∅) : α :=
ExtTreeMap.maxKey t.inner (fun _ => nomatch t)
/--
Tries to retrieve the largest element of the tree set, panicking if the set is empty.
-/
@[inline]
def max! [TransCmp cmp] [Inhabited α] (t : ExtTreeSet α cmp) : α :=
ExtTreeMap.maxKey! t.inner
/--
Tries to retrieve the largest element of the tree set, returning `fallback` if the tree set is empty.
-/
@[inline]
def maxD [TransCmp cmp] (t : ExtTreeSet α cmp) (fallback : α) : α :=
ExtTreeMap.maxKeyD t.inner fallback
/-- Returns the `n`-th smallest element, or `none` if `n` is at least `t.size`. -/
@[inline]
def atIdx? [TransCmp cmp] (t : ExtTreeSet α cmp) (n : Nat) : Option α :=
ExtTreeMap.keyAtIdx? t.inner n
/-- Returns the `n`-th smallest element. -/
@[inline]
def atIdx [TransCmp cmp] (t : ExtTreeSet α cmp) (n : Nat) (h : n < t.size) : α :=
ExtTreeMap.keyAtIdx t.inner n h
/-- Returns the `n`-th smallest element, or panics if `n` is at least `t.size`. -/
@[inline]
def atIdx! [TransCmp cmp] [Inhabited α] (t : ExtTreeSet α cmp) (n : Nat) : α :=
ExtTreeMap.keyAtIdx! t.inner n
/-- Returns the `n`-th smallest element, or `fallback` if `n` is at least `t.size`. -/
@[inline]
def atIdxD [TransCmp cmp] (t : ExtTreeSet α cmp) (n : Nat) (fallback : α) : α :=
ExtTreeMap.keyAtIdxD t.inner n fallback
/--
Tries to retrieve the smallest element that is greater than or equal to the
given element, returning `none` if no such element exists.
-/
@[inline]
def getGE? [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) : Option α :=
ExtTreeMap.getKeyGE? t.inner k
/--
Tries to retrieve the smallest element that is greater than the given element,
returning `none` if no such element exists.
-/
@[inline]
def getGT? [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) : Option α :=
ExtTreeMap.getKeyGT? t.inner k
/--
Tries to retrieve the largest element that is less than or equal to the
given element, returning `none` if no such element exists.
-/
@[inline]
def getLE? [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) : Option α :=
ExtTreeMap.getKeyLE? t.inner k
/--
Tries to retrieve the smallest element that is less than the given element,
returning `none` if no such element exists.
-/
@[inline]
def getLT? [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) : Option α :=
ExtTreeMap.getKeyLT? t.inner k
/--
Given a proof that such an element exists, retrieves the smallest element that is
greater than or equal to the given element.
-/
@[inline]
def getGE [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) (h : ∃ a ∈ t, (cmp a k).isGE) : α :=
ExtTreeMap.getKeyGE t.inner k h
/--
Given a proof that such an element exists, retrieves the smallest element that is
greater than the given element.
-/
@[inline]
def getGT [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) (h : ∃ a ∈ t, cmp a k = .gt) : α :=
ExtTreeMap.getKeyGT t.inner k h
/--
Given a proof that such an element exists, retrieves the largest element that is
less than or equal to the given element.
-/
@[inline]
def getLE [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) (h : ∃ a ∈ t, (cmp a k).isLE) : α :=
ExtTreeMap.getKeyLE t.inner k h
/--
Given a proof that such an element exists, retrieves the smallest element that is
less than the given element.
-/
@[inline]
def getLT [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) (h : ∃ a ∈ t, cmp a k = .lt) : α :=
ExtTreeMap.getKeyLT t.inner k h
/--
Tries to retrieve the smallest element that is greater than or equal to the
given element, panicking if no such element exists.
-/
@[inline]
def getGE! [TransCmp cmp] [Inhabited α] (t : ExtTreeSet α cmp) (k : α) : α :=
ExtTreeMap.getKeyGE! t.inner k
/--
Tries to retrieve the smallest element that is greater than the given element,
panicking if no such element exists.
-/
@[inline]
def getGT! [TransCmp cmp] [Inhabited α] (t : ExtTreeSet α cmp) (k : α) : α :=
ExtTreeMap.getKeyGT! t.inner k
/--
Tries to retrieve the largest element that is less than or equal to the
given element, panicking if no such element exists.
-/
@[inline]
def getLE! [TransCmp cmp] [Inhabited α] (t : ExtTreeSet α cmp) (k : α) : α :=
ExtTreeMap.getKeyLE! t.inner k
/--
Tries to retrieve the smallest element that is less than the given element,
panicking if no such element exists.
-/
@[inline]
def getLT! [TransCmp cmp] [Inhabited α] (t : ExtTreeSet α cmp) (k : α) : α :=
ExtTreeMap.getKeyLT! t.inner k
/--
Tries to retrieve the smallest element that is greater than or equal to the
given element, returning `fallback` if no such element exists.
-/
@[inline]
def getGED [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) (fallback : α) : α :=
ExtTreeMap.getKeyGED t.inner k fallback
/--
Tries to retrieve the smallest element that is greater than the given element,
returning `fallback` if no such element exists.
-/
@[inline]
def getGTD [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) (fallback : α) : α :=
ExtTreeMap.getKeyGTD t.inner k fallback
/--
Tries to retrieve the largest element that is less than or equal to the
given element, returning `fallback` if no such element exists.
-/
@[inline]
def getLED [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) (fallback : α) : α :=
ExtTreeMap.getKeyLED t.inner k fallback
/--
Tries to retrieve the smallest element that is less than the given element,
returning `fallback` if no such element exists.
-/
@[inline]
def getLTD [TransCmp cmp] (t : ExtTreeSet α cmp) (k : α) (fallback : α) : α :=
ExtTreeMap.getKeyLTD t.inner k fallback
variable {γ δ : Type w} {m : Type w → Type w₂} [Monad m] [LawfulMonad m]
/-- Removes all elements from the tree set for which the given function returns `false`. -/
@[inline]
def filter (f : α → Bool) (m : ExtTreeSet α cmp) : ExtTreeSet α cmp :=
⟨m.inner.filter fun a _ => f a⟩
/--
Monadically computes a value by folding the given function over the elements in the tree set in
ascending order.
-/
@[inline]
def foldlM [TransCmp cmp] (f : δ → (a : α) → m δ) (init : δ) (t : ExtTreeSet α cmp) : m δ :=
t.inner.foldlM (fun c a _ => f c a) init
/-- Folds the given function over the elements of the tree set in ascending order. -/
@[inline]
def foldl [TransCmp cmp] (f : δ → (a : α) → δ) (init : δ) (t : ExtTreeSet α cmp) : δ :=
t.inner.foldl (fun c a _ => f c a) init
/--
Monadically computes a value by folding the given function over the elements in the tree set in
descending order.
-/
@[inline]
def foldrM [TransCmp cmp] (f : (a : α) → δ → m δ) (init : δ) (t : ExtTreeSet α cmp) : m δ :=
t.inner.foldrM (fun a _ acc => f a acc) init
/-- Folds the given function over the elements of the tree set in descending order. -/
@[inline]
def foldr [TransCmp cmp] (f : (a : α) → δ → δ) (init : δ) (t : ExtTreeSet α cmp) : δ :=
t.inner.foldr (fun a _ acc => f a acc) init
/-- Partitions a tree set into two tree sets based on a predicate. -/
@[inline]
def partition [TransCmp cmp] (f : (a : α) → Bool) (t : ExtTreeSet α cmp) :
ExtTreeSet α cmp × ExtTreeSet α cmp :=
let p := t.inner.partition fun a _ => f a; (⟨p.1⟩, ⟨p.2⟩)
/-- Carries out a monadic action on each element in the tree set in ascending order. -/
@[inline]
def forM [TransCmp cmp] (f : α → m PUnit) (t : ExtTreeSet α cmp) : m PUnit :=
t.inner.forM (fun a _ => f a)
/--
Support for the `for` loop construct in `do` blocks. The iteration happens in ascending
order.
-/
@[inline]
def forIn [TransCmp cmp] (f : α → δ → m (ForInStep δ)) (init : δ) (t : ExtTreeSet α cmp) : m δ :=
t.inner.forIn (fun a _ c => f a c) init
instance [TransCmp cmp] [Monad m] [LawfulMonad m] : ForM m (ExtTreeSet α cmp) α where
forM t f := forM f t
instance [TransCmp cmp] [Monad m] [LawfulMonad m] : ForIn m (ExtTreeSet α cmp) α where
forIn m init f := forIn f init m
/-- Check if all elements satisfy the predicate, short-circuiting if a predicate fails. -/
@[inline]
def any [TransCmp cmp] (t : ExtTreeSet α cmp) (p : α → Bool) : Bool :=
t.inner.any (fun a _ => p a)
/-- Check if any element satisfies the predicate, short-circuiting if a predicate succeeds. -/
@[inline]
def all [TransCmp cmp] (t : ExtTreeSet α cmp) (p : α → Bool) : Bool :=
t.inner.all (fun a _ => p a)
/-- Transforms the tree set into a list of elements in ascending order. -/
@[inline]
def toList [TransCmp cmp] (t : ExtTreeSet α cmp) : List α :=
t.inner.keys
/-- Transforms a list into a tree set. -/
def ofList (l : List α) (cmp : α → α → Ordering := by exact compare) : ExtTreeSet α cmp :=
⟨ExtTreeMap.unitOfList l cmp⟩
/-- Transforms the tree set into an array of elements in ascending order. -/
@[inline]
def toArray [TransCmp cmp] (t : ExtTreeSet α cmp) : Array α :=
t.inner.keysArray
/-- Transforms an array into a tree set. -/
def ofArray (a : Array α) (cmp : α → α → Ordering := by exact compare) : ExtTreeSet α cmp :=
⟨ExtTreeMap.unitOfArray a cmp⟩
/--
Returns a set that contains all mappings of `t₁` and `t₂.
This function ensures that `t₁` is used linearly.
Hence, as long as `t₁` is unshared, the performance characteristics follow the following imperative
description: Iterate over all mappings in `t₂`, inserting them into `t₁`.
Hence, the runtime of this method scales logarithmically in the size of `t₁` and linearly in the
size of `t₂` as long as `t₁` is unshared.
-/
@[inline]
def merge [TransCmp cmp] (t₁ t₂ : ExtTreeSet α cmp) : ExtTreeSet α cmp :=
⟨ExtTreeMap.mergeWith (fun _ _ _ => ()) t₁.inner t₂.inner⟩
/--
Inserts multiple elements into the tree set by iterating over the given collection and calling
`insert`. If the same element (with respect to `cmp`) appears multiple times, the first occurrence
takes precedence.
Note: this precedence behavior is true for `ExtTreeSet` and `ExtTreeSet.Raw`. The `insertMany` function on
`ExtTreeMap`, `ExtDTreeMap`, `ExtTreeMap.Raw` and `ExtDTreeMap.Raw` behaves differently: it will prefer the last
appearance.
-/
@[inline]
def insertMany [TransCmp cmp] {ρ} [ForIn Id ρ α] (t : ExtTreeSet α cmp) (l : ρ) : ExtTreeSet α cmp :=
⟨ExtTreeMap.insertManyIfNewUnit t.inner l⟩
/--
Computes the union of the given tree sets. If both maps contain elements that are equal according
to the comparison function, the element contained in the second argument will appear in the result.
This function always merges the smaller set into the larger set.
-/
@[inline]
def union [TransCmp cmp] (t₁ t₂ : ExtTreeSet α cmp) : ExtTreeSet α cmp := ⟨ExtTreeMap.union t₁.inner t₂.inner⟩
instance [TransCmp cmp] : Union (ExtTreeSet α cmp) := ⟨union⟩
/--
Computes the intersection of the given tree sets.
This function always iterates through the smaller set.
-/
@[inline]
def inter [TransCmp cmp] (t₁ t₂ : ExtTreeSet α cmp) : ExtTreeSet α cmp := ⟨ExtTreeMap.inter t₁.inner t₂.inner⟩
instance [TransCmp cmp] : Inter (ExtTreeSet α cmp) := ⟨inter⟩
instance [TransCmp cmp] : BEq (ExtTreeSet α cmp) where
beq m₁ m₂ := ExtDTreeMap.Const.beq m₁.inner.inner m₂.inner.inner
instance [TransCmp cmp] : ReflBEq (ExtTreeSet α cmp) where
rfl := ExtDTreeMap.Const.beq_of_eq _ _ rfl
instance [TransCmp cmp] [LawfulEqCmp cmp] : LawfulBEq (ExtTreeSet α cmp) where
eq_of_beq {a} {b} hyp := by
have ⟨⟨_⟩⟩ := a
have ⟨⟨_⟩⟩ := b
simp only [mk.injEq, ExtTreeMap.mk.injEq] at |- hyp
exact ExtDTreeMap.Const.eq_of_beq _ _ hyp
/--
Computes the difference of the given tree sets.
This function always iterates through the smaller set.
-/
@[inline]
def diff [TransCmp cmp] (t₁ t₂ : ExtTreeSet α cmp) : ExtTreeSet α cmp := ⟨ExtTreeMap.diff t₁.inner t₂.inner⟩
instance [TransCmp cmp] : SDiff (ExtTreeSet α cmp) := ⟨diff⟩
instance {α : Type u} {cmp : α → α → Ordering} [LawfulEqCmp cmp] [TransCmp cmp] : DecidableEq (ExtTreeSet α cmp) :=
fun _ _ => decidable_of_iff _ beq_iff_eq
/--
Erases multiple items from the tree set by iterating over the given collection and calling erase.
-/
@[inline]
def eraseMany [TransCmp cmp] {ρ} [ForIn Id ρ α] (t : ExtTreeSet α cmp) (l : ρ) : ExtTreeSet α cmp :=
⟨t.inner.eraseMany l⟩
instance [TransCmp cmp] [Repr α] : Repr (ExtTreeSet α cmp) where
reprPrec m prec := Repr.addAppParen ("Std.ExtTreeSet.ofList " ++ repr m.toList) prec
end ExtTreeSet
end Std