type-safe-avl-1.0.0.1: Type safe BST and AVL trees
Copyright(c) Nicolás Rodríguez 2021
LicenseGPL-3
MaintainerNicolás Rodríguez
Stabilityexperimental
PortabilityPOSIX
Safe HaskellSafe
LanguageHaskell2010

Data.Tree.BST.Extern.Delete

Description

Implementation of the deletion algorithm over ITree trees for externalist BST trees.

Synopsis

Documentation

class Maxable (t :: Tree) where Source #

This type class provides the functionality to get the key, type and value of the node with maximum key value in a tree t without checking any structural invariant (key ordering). The lookup is defined at the value level and the type level, and is performed as if the tree is a BST. Since the keys are only kept at the type level, there's no value level getter of the maximum key.

Associated Types

type MaxKey (t :: Tree) :: Nat Source #

type MaxValue (t :: Tree) :: Type Source #

Methods

maxValue :: t ~ 'ForkTree l (Node n a1) r => ITree t -> MaxValue t Source #

Instances

Instances details
Maxable ('ForkTree rl (Node rn ra) rr) => Maxable ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type MaxKey ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) :: Nat Source #

type MaxValue ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) Source #

Methods

maxValue :: 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)) -> MaxValue ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) Source #

Maxable ('ForkTree l (Node n a1) 'EmptyTree) Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type MaxKey ('ForkTree l (Node n a1) 'EmptyTree) :: Nat Source #

type MaxValue ('ForkTree l (Node n a1) 'EmptyTree) Source #

Methods

maxValue :: forall (l0 :: Tree) (n0 :: Nat) a10 (r :: Tree). 'ForkTree l (Node n a1) 'EmptyTree ~ 'ForkTree l0 (Node n0 a10) r => ITree ('ForkTree l (Node n a1) 'EmptyTree) -> MaxValue ('ForkTree l (Node n a1) 'EmptyTree) Source #

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). The deletion is defined at the value level and the type level, and is performed as if the tree is a BST; the verification of the BST 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

Instances details
MaxKeyDeletable 'EmptyTree Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type MaxKeyDelete 'EmptyTree :: Tree Source #

Methods

maxKeyDelete :: forall (l :: Tree) (n :: Nat) a1 (r :: Tree). 'EmptyTree ~ 'ForkTree l (Node n a1) r => ITree 'EmptyTree -> ITree (MaxKeyDelete 'EmptyTree) Source #

MaxKeyDeletable ('ForkTree rl (Node rn ra) rr) => MaxKeyDeletable ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) Source # 
Instance details

Defined in Data.Tree.BST.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 # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type MaxKeyDelete ('ForkTree l (Node n a1) 'EmptyTree) :: Tree Source #

Methods

maxKeyDelete :: forall (l0 :: Tree) (n0 :: Nat) a10 (r :: Tree). 'ForkTree l (Node n a1) 'EmptyTree ~ 'ForkTree l0 (Node n0 a10) r => ITree ('ForkTree l (Node n a1) 'EmptyTree) -> ITree (MaxKeyDelete ('ForkTree l (Node n a1) 'EmptyTree)) Source #

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). The deletion is defined at the value level and the type level, and is performed as if the tree is a BST; the key ordering is verified after the deletion.

Associated Types

type Delete (x :: Nat) (t :: Tree) :: Tree Source #

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.

Instances

Instances details
Deletable x 'EmptyTree Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type Delete x 'EmptyTree :: Tree Source #

(o ~ CmpNat x n, Deletable' x ('ForkTree l (Node n a1) r) o) => Deletable x ('ForkTree l (Node n a1) r) Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type Delete x ('ForkTree l (Node n a1) r) :: Tree Source #

Methods

delete :: Proxy x -> ITree ('ForkTree l (Node n a1) r) -> ITree (Delete x ('ForkTree l (Node n a1) r)) Source #

class Deletable' (x :: Nat) (t :: Tree) (o :: Ordering) where 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). 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.

Associated Types

type Delete' (x :: Nat) (t :: Tree) (o :: Ordering) :: Tree Source #

Methods

delete' :: Proxy x -> ITree t -> Proxy o -> ITree (Delete' x t o) Source #

Instances

Instances details
(o ~ CmpNat x rn, Deletable' x ('ForkTree rl (Node rn ra) rr) o) => Deletable' x ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) 'GT Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type Delete' x ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) 'GT :: Tree Source #

Methods

delete' :: Proxy x -> ITree ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) -> Proxy 'GT -> ITree (Delete' x ('ForkTree l (Node n a1) ('ForkTree rl (Node rn ra) rr)) 'GT) Source #

Deletable' x ('ForkTree l (Node n a1) 'EmptyTree) 'GT Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type Delete' x ('ForkTree l (Node n a1) 'EmptyTree) 'GT :: Tree Source #

Methods

delete' :: Proxy x -> ITree ('ForkTree l (Node n a1) 'EmptyTree) -> Proxy 'GT -> ITree (Delete' x ('ForkTree l (Node n a1) 'EmptyTree) 'GT) Source #

(o ~ CmpNat x ln, Deletable' x ('ForkTree ll (Node ln la) lr) o) => Deletable' x ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) r) 'LT Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type Delete' x ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) r) 'LT :: Tree Source #

Methods

delete' :: Proxy x -> ITree ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) r) -> Proxy 'LT -> ITree (Delete' x ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) r) 'LT) Source #

Deletable' x ('ForkTree 'EmptyTree (Node n a1) r) 'LT Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type Delete' x ('ForkTree 'EmptyTree (Node n a1) r) 'LT :: Tree Source #

Methods

delete' :: Proxy x -> ITree ('ForkTree 'EmptyTree (Node n a1) r) -> Proxy 'LT -> ITree (Delete' x ('ForkTree 'EmptyTree (Node n a1) r) 'LT) Source #

(l ~ 'ForkTree ll (Node ln la) lr, Show (MaxValue l), MaxKeyDeletable l, Maxable l) => Deletable' x ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) ('ForkTree rl (Node rn ra) rr)) 'EQ Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type Delete' x ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) ('ForkTree rl (Node rn ra) rr)) 'EQ :: Tree Source #

Methods

delete' :: Proxy x -> ITree ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) ('ForkTree rl (Node rn ra) rr)) -> Proxy 'EQ -> ITree (Delete' x ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) ('ForkTree rl (Node rn ra) rr)) 'EQ) Source #

Deletable' x ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) 'EmptyTree) 'EQ Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type Delete' x ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) 'EmptyTree) 'EQ :: Tree Source #

Methods

delete' :: Proxy x -> ITree ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) 'EmptyTree) -> Proxy 'EQ -> ITree (Delete' x ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a1) 'EmptyTree) 'EQ) Source #

Deletable' x ('ForkTree 'EmptyTree (Node n a1) ('ForkTree rl (Node rn ra) rr)) 'EQ Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type Delete' x ('ForkTree 'EmptyTree (Node n a1) ('ForkTree rl (Node rn ra) rr)) 'EQ :: Tree Source #

Methods

delete' :: Proxy x -> ITree ('ForkTree 'EmptyTree (Node n a1) ('ForkTree rl (Node rn ra) rr)) -> Proxy 'EQ -> ITree (Delete' x ('ForkTree 'EmptyTree (Node n a1) ('ForkTree rl (Node rn ra) rr)) 'EQ) Source #

Deletable' x ('ForkTree 'EmptyTree (Node n a1) 'EmptyTree) 'EQ Source # 
Instance details

Defined in Data.Tree.BST.Extern.Delete

Associated Types

type Delete' x ('ForkTree 'EmptyTree (Node n a1) 'EmptyTree) 'EQ :: Tree Source #