Documentation

Lean.Data.RBTree

def Lean.RBTree (α : Type u) (cmp : α → α → Ordering) :

Equations

Lean.RBTree α cmp = Lean.RBMap α Unit cmp

instance Lean.instInhabitedRBTree {α : Type u_1} {p : α → α → Ordering} :

Inhabited (Lean.RBTree α p)

Equations

Lean.instInhabitedRBTree = { default := Lean.RBMap.empty }

@[inline]

def Lean.mkRBTree (α : Type u) (cmp : α → α → Ordering) :

Lean.RBTree α cmp

Equations

Lean.mkRBTree α cmp = Lean.mkRBMap α Unit cmp

instance Lean.instEmptyCollectionRBTree (α : Type u) (cmp : α → α → Ordering) :

EmptyCollection (Lean.RBTree α cmp)

Equations

Lean.instEmptyCollectionRBTree α cmp = { emptyCollection := Lean.mkRBTree α cmp }

@[inline]

def Lean.RBTree.empty {α : Type u} {cmp : α → α → Ordering} :

Lean.RBTree α cmp

Equations

Lean.RBTree.empty = Lean.RBMap.empty

@[inline]

def Lean.RBTree.depth {α : Type u} {cmp : α → α → Ordering} (f : Nat → Nat → Nat) (t : Lean.RBTree α cmp) :

Equations

Lean.RBTree.depth f t = Lean.RBMap.depth f t

@[inline]

def Lean.RBTree.fold {α : Type u} {β : Type v} {cmp : α → α → Ordering} (f : β → α → β) (init : β) (t : Lean.RBTree α cmp) :

β

Equations

Lean.RBTree.fold f init t = Lean.RBMap.fold (fun r a x => f r a) init t

@[inline]

def Lean.RBTree.revFold {α : Type u} {β : Type v} {cmp : α → α → Ordering} (f : β → α → β) (init : β) (t : Lean.RBTree α cmp) :

β

Equations

Lean.RBTree.revFold f init t = Lean.RBMap.revFold (fun r a x => f r a) init t

@[inline]

def Lean.RBTree.foldM {α : Type u} {β : Type v} {cmp : α → α → Ordering} {m : Type v → Type w} [inst : Monad m] (f : β → α → m β) (init : β) (t : Lean.RBTree α cmp) :

m β

Equations

Lean.RBTree.foldM f init t = Lean.RBMap.foldM (fun r a x => f r a) init t

@[inline]

def Lean.RBTree.forM {α : Type u} {cmp : α → α → Ordering} {m : Type v → Type w} [inst : Monad m] (f : α → m PUnit) (t : Lean.RBTree α cmp) :

Equations

Lean.RBTree.forM f t = Lean.RBTree.foldM (fun x a => f a) PUnit.unit t

@[inline]

def Lean.RBTree.forIn {α : Type u} {cmp : α → α → Ordering} {m : Type u_1 → Type u_2} {σ : Type u_1} [inst : Monad m] (t : Lean.RBTree α cmp) (init : σ) (f : α → σ → m (ForInStep σ)) :

m σ

Equations

Lean.RBTree.forIn t init f = Lean.RBNode.forIn t.val init fun a x acc => f a acc

instance Lean.RBTree.instForInRBTree {α : Type u} {cmp : α → α → Ordering} {m : Type u_1 → Type u_2} :

ForIn m (Lean.RBTree α cmp) α

Equations

Lean.RBTree.instForInRBTree = { forIn := fun {β} [Monad m] => Lean.RBTree.forIn }

@[inline]

def Lean.RBTree.isEmpty {α : Type u} {cmp : α → α → Ordering} (t : Lean.RBTree α cmp) :

Equations

Lean.RBTree.isEmpty t = Lean.RBMap.isEmpty t

@[specialize #[]]

def Lean.RBTree.toList {α : Type u} {cmp : α → α → Ordering} (t : Lean.RBTree α cmp) :

Equations

Lean.RBTree.toList t = Lean.RBTree.revFold (fun as a => a :: as) [] t

@[specialize #[]]

def Lean.RBTree.toArray {α : Type u} {cmp : α → α → Ordering} (t : Lean.RBTree α cmp) :

Equations

Lean.RBTree.toArray t = Lean.RBTree.fold (fun as a => Array.push as a) #[] t

@[inline]

def Lean.RBTree.min {α : Type u} {cmp : α → α → Ordering} (t : Lean.RBTree α cmp) :

Equations

Lean.RBTree.min t = match Lean.RBMap.min t with | some (a, snd) => some a | none => none

@[inline]

def Lean.RBTree.max {α : Type u} {cmp : α → α → Ordering} (t : Lean.RBTree α cmp) :

Equations

Lean.RBTree.max t = match Lean.RBMap.max t with | some (a, snd) => some a | none => none

instance Lean.RBTree.instReprRBTree {α : Type u} {cmp : α → α → Ordering} [inst : Repr α] :

Repr (Lean.RBTree α cmp)

Equations

Lean.RBTree.instReprRBTree = { reprPrec := fun t prec => Repr.addAppParen (Std.Format.text "Lean.rbtreeOf " ++ repr (Lean.RBTree.toList t)) prec }

@[inline]

def Lean.RBTree.insert {α : Type u} {cmp : α → α → Ordering} (t : Lean.RBTree α cmp) (a : α) :

Lean.RBTree α cmp

Equations

Lean.RBTree.insert t a = Lean.RBMap.insert t a ()

@[inline]

def Lean.RBTree.erase {α : Type u} {cmp : α → α → Ordering} (t : Lean.RBTree α cmp) (a : α) :

Lean.RBTree α cmp

Equations

Lean.RBTree.erase t a = Lean.RBMap.erase t a

@[specialize #[]]

def Lean.RBTree.ofList {α : Type u} {cmp : α → α → Ordering} :

List α → Lean.RBTree α cmp

Equations

Lean.RBTree.ofList [] = Lean.mkRBTree α cmp
Lean.RBTree.ofList (x_1 :: xs) = Lean.RBTree.insert (Lean.RBTree.ofList xs) x_1

@[inline]

def Lean.RBTree.find? {α : Type u} {cmp : α → α → Ordering} (t : Lean.RBTree α cmp) (a : α) :

Equations

Lean.RBTree.find? t a = match Lean.RBMap.findCore? t a with | some { fst := a, snd := snd } => some a | none => none

@[inline]

def Lean.RBTree.contains {α : Type u} {cmp : α → α → Ordering} (t : Lean.RBTree α cmp) (a : α) :

Equations

Lean.RBTree.contains t a = Option.isSome (Lean.RBTree.find? t a)

def Lean.RBTree.fromList {α : Type u} (l : List α) (cmp : α → α → Ordering) :

Lean.RBTree α cmp

Equations

Lean.RBTree.fromList l cmp = List.foldl Lean.RBTree.insert (Lean.mkRBTree α cmp) l

def Lean.RBTree.fromArray {α : Type u} (l : Array α) (cmp : α → α → Ordering) :

Lean.RBTree α cmp

Equations

Lean.RBTree.fromArray l cmp = Array.foldl Lean.RBTree.insert (Lean.mkRBTree α cmp) l 0 (Array.size l)

@[inline]

def Lean.RBTree.all {α : Type u} {cmp : α → α → Ordering} (t : Lean.RBTree α cmp) (p : α → Bool) :

Equations

Lean.RBTree.all t p = Lean.RBMap.all t fun a x => p a

@[inline]

def Lean.RBTree.any {α : Type u} {cmp : α → α → Ordering} (t : Lean.RBTree α cmp) (p : α → Bool) :

Equations

Lean.RBTree.any t p = Lean.RBMap.any t fun a x => p a

def Lean.RBTree.subset {α : Type u} {cmp : α → α → Ordering} (t₁ : Lean.RBTree α cmp) (t₂ : Lean.RBTree α cmp) :

Equations

Lean.RBTree.subset t₁ t₂ = Lean.RBTree.all t₁ fun a => Option.toBool (Lean.RBTree.find? t₂ a)

def Lean.RBTree.seteq {α : Type u} {cmp : α → α → Ordering} (t₁ : Lean.RBTree α cmp) (t₂ : Lean.RBTree α cmp) :

Equations

Lean.RBTree.seteq t₁ t₂ = (Lean.RBTree.subset t₁ t₂ && Lean.RBTree.subset t₂ t₁)

def Lean.RBTree.union {α : Type u} {cmp : α → α → Ordering} (t₁ : Lean.RBTree α cmp) (t₂ : Lean.RBTree α cmp) :

Lean.RBTree α cmp

Equations

Lean.RBTree.union t₁ t₂ = if Lean.RBTree.isEmpty t₁ = true then t₂ else Lean.RBTree.fold Lean.RBTree.insert t₁ t₂

def Lean.RBTree.diff {α : Type u} {cmp : α → α → Ordering} (t₁ : Lean.RBTree α cmp) (t₂ : Lean.RBTree α cmp) :

Lean.RBTree α cmp

Equations

Lean.RBTree.diff t₁ t₂ = Lean.RBTree.fold Lean.RBTree.erase t₁ t₂

def Lean.rbtreeOf {α : Type u} (l : List α) (cmp : α → α → Ordering) :

Lean.RBTree α cmp

Equations

Lean.rbtreeOf l cmp = Lean.RBTree.fromList l cmp