| 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.Balance
Description
Implementation of the balancing algorithm over ITree trees for externalist AlmostAVL trees.
Synopsis
- class Balanceable (t :: Tree) where
- class Balanceable' (t :: Tree) (us :: US) where
- class Rotateable (t :: Tree) (us :: US) (bs :: BS) where
Documentation
class Balanceable (t :: Tree) where Source #
This type class provides the functionality to balance
a tree t without checking any structural invariant (key ordering or height balance).
The insertion is defined at the value level and the type level;
the verification of the BST/AVL restrictions is performed after the insertion.
Instances
| Balanceable 'EmptyTree Source # | |
| (us ~ UnbalancedState (Height l) (Height r), Balanceable' ('ForkTree l (Node n a) r) us) => Balanceable ('ForkTree l (Node n a) r) Source # | |
class Balanceable' (t :: Tree) (us :: US) where Source #
This type class provides the functionality to balance
a tree t without checking any structural invariant (key ordering or height balance).
It's only used by the Balanceable class and it has one extra parameter us,
which is the UnbalancedState of the two sub trees of t.
Instances
| (bs ~ BalancedState (Height rl) (Height rr), Rotateable ('ForkTree l (Node n a) ('ForkTree rl (Node rn ra) rr)) 'RightUnbalanced bs) => Balanceable' ('ForkTree l (Node n a) ('ForkTree rl (Node rn ra) rr)) 'RightUnbalanced Source # | |
Defined in Data.Tree.AVL.Extern.Balance | |
| Balanceable' ('ForkTree l (Node n a) r) 'NotUnbalanced Source # | |
| (bs ~ BalancedState (Height ll) (Height lr), Rotateable ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a) r) 'LeftUnbalanced bs) => Balanceable' ('ForkTree ('ForkTree ll (Node ln la) lr) (Node n a) r) 'LeftUnbalanced Source # | |
Defined in Data.Tree.AVL.Extern.Balance | |
class Rotateable (t :: Tree) (us :: US) (bs :: BS) where Source #
This type class provides the functionality to apply a rotation to
a tree t without checking any structural invariant (key ordering or height balance).
The rotation is defined at the value level and the type level;
the verification of the BST/AVL restrictions is performed after the insertion.