wgaffa/ffxwt - Change WILCC2NZDLTXRZADOLY2I4O2UP4BC7ZA7G7PFWXZAXUNRSBUS4AQC

Now removes a node on Delete case 4

Created by wgaffa on February 27, 2023

WILCC2NZDLTXRZADOLY2I4O2UP4BC7ZA7G7PFWXZAXUNRSBUS4AQC

Dependencies

[2] GNENKYVZNZHP7ZH624LVZ7HJUHFNEG5CHPJNY3IUBTWDSXQ3YFIAC

In channels

main

Change contents

Insertion in src/AlBhed/Tree.hs at line 3 [2.32]
[2.107]
[2.107]
```
{-# LANGUAGE LambdaCase #-}
```
Insertion in src/AlBhed/Tree.hs at line 27 [2.32]
[2.444]
[2.444]
```
import Data.Bifunctor
```

Insertion in src/AlBhed/Tree.hs at line 93 [2.32]

[2.2616]

modify :: (RedBlackTree a -> RedBlackTree a) -> TreeZipper a -> TreeZipper a
modify = second

Replacement in src/AlBhed/Tree.hs at line 116 [2.32]

B:BD[2.3261] → [2.3261:3368]

remove' :: (Ord a) => TreeZipper a -> RedBlackTree a
remove' (path, node) = go $ identifyCase (path, node)

[2.3261]

[2.3368]

remove' :: forall a. (Ord a) => TreeZipper a -> RedBlackTree a
remove' zipper = go $ identifyCase zipper

Replacement in src/AlBhed/Tree.hs at line 119 [2.32]
B:BD[2.3378] → [2.3378:3417]
```
        go :: Case a -> RedBlackTree a
```
[2.3378]
[2.3417]
```
        go :: Case -> RedBlackTree a
```

Replacement in src/AlBhed/Tree.hs at line 121 [2.32]

B:BD[2.3443] → [2.3443:3525]

        go (D4 (Node pc pl pv pr) (Node sc cl cv cr)) = error "To be implemented"

[2.3443]

[2.3525]

        go D4 =
            let actions = [modify (const Leaf), modify switchColor . sibling, modify switchColor . parent]
                zipper' = foldl (\acc f -> f acc) zipper actions
                in fromZipper zipper'

Insertion in src/AlBhed/Tree.hs at line 126 [2.32]

[2.3551]

        switchColor (Node Black l v r) = Node Red l v r
        switchColor (Node Red l v r) = Node Black l v r
        switchColor n = n
nodeDirection :: TreeZipper a -> Direction
nodeDirection = fst . last . fst
parent :: TreeZipper a -> TreeZipper a
parent = up
sibling :: TreeZipper a -> TreeZipper a
sibling node = case nodeDirection node of
    L -> right . parent $ node
    R -> left . parent $ node

Replacement in src/AlBhed/Tree.hs at line 141 [2.32]

B:BD[2.3552] → [2.3552:3604]

-- Maybe this is a candidate for GADTS?
data Case a

[2.3552]

[2.3604]

distantNephew :: TreeZipper a -> TreeZipper a
distantNephew z = case nodeDirection z of
    L -> right . sibling $ z
    R -> left . sibling $ z
closeNephew :: TreeZipper a -> TreeZipper a
closeNephew z = case nodeDirection z of
    L -> left . sibling $ z
    R -> right . sibling $ z
colorOf :: RedBlackTree a -> Color
colorOf Leaf = Black
colorOf (Node c _ _ _) = c
data Case

Replacement in src/AlBhed/Tree.hs at line 159 [2.32]
B:BD[2.3631] → [2.3631:3674]
```
    | D4 (RedBlackTree a) (RedBlackTree a)
```
[2.3631]
[2.3674]
```
    | D4
```
Replacement in src/AlBhed/Tree.hs at line 164 [2.32]
B:BD[2.3713] → [2.3713:3752]
```
identifyCase :: TreeZipper a -> Case a
```
[2.3713]
[2.3752]
```
identifyCase :: TreeZipper a -> Case
```

Replacement in src/AlBhed/Tree.hs at line 166 [2.32]

B:BD[2.3774] → [2.3774:3872]

    let colors = map (colorOf . snd . ($ zipper)) [parent, sibling, distant_nephew, close_nephew]

[2.3774]

[2.3872]

    let colors = map (colorOf . snd . ($ zipper)) [parent, sibling, distantNephew, closeNephew]

Replacement in src/AlBhed/Tree.hs at line 168 [2.32]

B:BD[2.3898] → [2.3898:4496]

            [Red, Black, Black, Black] -> D4 (snd $ parent zipper) (snd $ sibling zipper)
            
    where
        colorOf Leaf = Black
        colorOf (Node c _ _ _) = c
        ourDirection = fst . last . fst $ zipper
        sibling z = case ourDirection of
            L -> right . parent $ z
            R -> left . parent $ z
        parent = up
        distant_nephew z = case ourDirection of
            L -> right . sibling $ z
            R -> left . sibling $ z
        close_nephew z = case ourDirection of
            L -> left . sibling $ z
            R -> right . sibling $ z

[2.3898]

            [Red, Black, Black, Black] -> D4

Now removes a node on Delete case 4

Dependencies

In channels

Change contents

Insertion in src/AlBhed/Tree.hs at line 3 [2.32]

Insertion in src/AlBhed/Tree.hs at line 27 [2.32]