| Copyright | (c) Nicolás Rodríguez 2021 |
|---|---|
| License | GPL-3 |
| Maintainer | Nicolás Rodríguez |
| Stability | experimental |
| Portability | POSIX |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Data.Tree.AVL.Extern.Delete
Description
Implementation of the deletion algorithm over ITree trees for externalist AVL trees.
Synopsis
- class MaxKeyDeletable (t :: Tree) where
- type MaxKeyDelete (t :: Tree) :: Tree
- maxKeyDelete :: t ~ 'ForkTree l (Node n a1) r => ITree t -> ITree (MaxKeyDelete t)
- class Deletable (x :: Nat) (t :: Tree) where
- class Deletable' (x :: Nat) (t :: Tree) (o :: Ordering) where
Documentation
class MaxKeyDeletable (t :: Tree) where Source #
This type class provides the functionality to delete the node with maximum key value
in a tree t without checking any structural invariant (key ordering or height balance).
The deletion is defined at the value level and the type level, and is performed
as if the tree is an AVL; the verification of the AVL restrictions is performed after the deletion.
Associated Types
type MaxKeyDelete (t :: Tree) :: Tree Source #
Methods
maxKeyDelete :: t ~ 'ForkTree l (Node n a1) r => ITree t -> ITree (MaxKeyDelete t) Source #
Instances
| MaxKeyDeletable 'EmptyTree Source # | |
Defined in Data.Tree.AVL.Extern.Delete Associated Types type MaxKeyDelete 'EmptyTree :: Tree Source # | |
| (r ~ 'ForkTree rl (Node rn ra) rr, MaxKeyDeletable r, Balanceable ('ForkTree l (Node n a1) (MaxKeyDelete r))) => MaxKeyDeletable ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) Source # | |
Defined in Data.Tree.AVL.Extern.Delete Associated Types type MaxKeyDelete ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) :: Tree Source # Methods maxKeyDelete :: forall (l0 :: Tree) (n0 :: Nat) a10 (r :: Tree). 'ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr) ~ 'ForkTree l0 (Node n0 a10) r => ITree ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) -> ITree (MaxKeyDelete ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr))) Source # | |
| MaxKeyDeletable ('ForkTree l (Node n a1) 'EmptyTree) Source # | |
Defined in Data.Tree.AVL.Extern.Delete | |
class Deletable (x :: Nat) (t :: Tree) where Source #
This type class provides the functionality to delete the node with key x
in a tree t without checking any structural invariant (key ordering or height balance).
The deletion is defined at the value level and the type level, and is performed
as if the tree is a AVL; the verification of the AVL restrictions is performed after the deletion.
Methods
delete :: Proxy x -> ITree t -> ITree (Delete x t) Source #
Delete the node with the given key. If the key is not in the tree, return the same tree.
class Deletable' (x :: Nat) (t :: Tree) (o :: Ordering) Source #
This type class provides the functionality to delete a node with key x
in a non empty tree t without checking any structural invariant (key ordering or height balance).
It's only used by the Deletable type class and it has one extra parameter o,
which is the type level comparison of x with the key value of the root node.
The o parameter guides the deletion.
Minimal complete definition
delete'