module Data.RedBlackTree.BinaryTreeSpec (spec) where

import Test.Hspec
import Data.RedBlackTree.BinaryTree


instance BinaryTreeNode Int where
  mergeNodes leftInt rightInt = leftInt

spec :: Spec
spec = do
  let leftChildContent = 2 :: Int
  let rightChildContent = 3
  let treeContent = 1
  let emptyBranchContent = 4 :: Int
  let emptyTreeBranch = TreeBranch Leaf emptyBranchContent Leaf
  let leftChild = Branch Leaf leftChildContent Leaf
  let rightChild = Branch Leaf rightChildContent Leaf
  let tree = Branch leftChild treeContent rightChild
  let emptyBranch = Branch Leaf emptyBranchContent Leaf
  let leaf = Leaf :: BinaryTree Int

  describe "goLeft" $ do
    let branch = TreeBranch leftChild treeContent rightChild
    it "returns a new zipper focusing on the left child of current tree" $ do
      let (newTree, _) = goLeft (branch, [])

      newTree `shouldBe` leftChild

    it "returns a new zipper with a LeftTree direction, with node's data on top of its direction list" $ do
      let (_, [direction]) = goLeft (branch, [])

      direction `shouldBe` TreeDirection LeftBranch 1 rightChild

  describe "goRight" $ do
    let branch = TreeBranch leftChild treeContent rightChild
    it "returns a new zipper focusing on the right child of current tree" $ do
      let (newTree, _) = goRight (branch, [])

      newTree `shouldBe` rightChild

    it "returns a new zipper with a RightTree direction with node's data on top of its direction list" $ do
      let (_, [direction]) = goRight (branch, [])

      direction `shouldBe` TreeDirection RightBranch 1 leftChild

  describe "goUp" $ do
    let treeContent = 2
    let treeBranch = TreeBranch Leaf treeContent Leaf
    let parentContent = 1
    let expectedLeftChild = Branch Leaf treeContent Leaf

    it "returns a new zipper focusing on the current tree's parent" $ do
      let directionsToParent = [ TreeDirection LeftBranch parentContent
                               rightChild ]
      let Just (parentBranch, _) = goUp(treeBranch, directionsToParent)

      parentBranch `shouldBe` TreeBranch expectedLeftChild parentContent rightChild

    it "returns a new zipper with the direction list's head removed" $ do
      let directionsToParent = [ TreeDirection LeftBranch parentContent
                               rightChild ]
      let Just (_, directions) = goUp(treeBranch, directionsToParent)

      directions `shouldBe` []

    it "returns Nothing if the directions list is empty" $ do
      let maybeZipper = goUp(treeBranch, [])

      maybeZipper `shouldBe` Nothing

  describe "getTreeRoot" $
    it "returns the root branch of the tree" $ do
      let latestNode = 5
      let grandChild = Branch Leaf latestNode Leaf
      let grandChildBranch = TreeBranch Leaf latestNode Leaf
      let grandChildDirections = [ TreeDirection LeftBranch rightChildContent Leaf
                                 , TreeDirection RightBranch treeContent leftChild ]

      let modifiedRightChild = Branch grandChild rightChildContent Leaf
      let expectedRootBranch = TreeBranch leftChild treeContent modifiedRightChild

      let grandChildZipper = (grandChildBranch, grandChildDirections)
      let rootZipper = getTreeRoot grandChildZipper

      rootZipper `shouldBe` (expectedRootBranch, [])

  describe "appendLeftChild" $ do
    it "returns InsertOk with a BranchZipper focusing on the child inserted left" $ do
      let nodeToAppend = 0

      let expectedBranch = TreeBranch Leaf nodeToAppend Leaf
      let expectedDirection = TreeDirection LeftBranch emptyBranchContent Leaf

      let insertResult = appendLeftChild emptyTreeBranch nodeToAppend

      insertResult `shouldBe` InsertOk expectedBranch expectedDirection

    it "returns InsertNotYet if the tree already has a left child" $ do
      let nodeToInsert = 0

      let treeBranch = TreeBranch leftChild treeContent rightChild
      let expectedDirectionToObstuction = TreeDirection LeftBranch treeContent rightChild
      let expectedFailiure = InsertNotYet leftChild expectedDirectionToObstuction nodeToInsert

      let insertResult = appendLeftChild treeBranch nodeToInsert

      insertResult `shouldBe` expectedFailiure

  describe "appendRightChild" $ do
    it "returns InsertOk with a BranchZipper focusing on the child inserted right" $ do
      let nodeToAppend = 1

      let expectedBranch = TreeBranch Leaf nodeToAppend Leaf
      let expectedDirection = TreeDirection RightBranch emptyBranchContent Leaf

      let insertResult = appendRightChild emptyTreeBranch nodeToAppend

      insertResult `shouldBe` InsertOk expectedBranch expectedDirection

    it "returns InsertNotYet if the tree already has a left child" $ do
      let nodeToInsert = 6

      let treeBranch = TreeBranch leftChild treeContent rightChild
      let expectedDirectionToObstuction = TreeDirection RightBranch treeContent leftChild
      let expectedFailiure = InsertNotYet rightChild expectedDirectionToObstuction nodeToInsert

      let insertResult = appendRightChild treeBranch nodeToInsert

      insertResult `shouldBe` expectedFailiure


  describe "binaryTreeInsert" $ do
    let node1 = 10 :: Int
    let node2 = 8
    let node3 = 12
    let node4 = 7
    let node5 = 9
    let node6 = 11
    let node7 = 13

    it "inserts at the correct position" $ do
      let newContent = 8
      let expectedDirections = [ TreeDirection RightBranch emptyBranchContent Leaf ]
      let newZipper = binaryTreeInsert emptyBranch newContent

      newZipper `shouldBe` (TreeBranch Leaf newContent Leaf, expectedDirections)

    it "should be able to create a full tree of size 3 from scratch only wth insertions" $ do
      let zipper1 = (Leaf, [])
      let zipper2 = binaryTreeInsert Leaf node1
      zipper2 `shouldBe` (TreeBranch Leaf node1 Leaf, [])

      let treeBranchNode2 = TreeBranch Leaf node2 Leaf
      let treeNode2 = Branch Leaf node2 Leaf
      let zipper3 = branchZipperInsert zipper2 node2
      zipper3 `shouldBe` (treeBranchNode2, [ TreeDirection LeftBranch node1 Leaf ])

      let zipper4 = getTreeRoot zipper3

      let expectedFullDirections = [ TreeDirection RightBranch node1 treeNode2 ]
      let fullZipper = branchZipperInsert zipper4 node3
      fullZipper `shouldBe` (TreeBranch Leaf node3 Leaf, expectedFullDirections)

    it "should be able to create a full tree of size 5 wth insertions" $ do
      let initialLeftChild = Branch Leaf node2 Leaf
      let initialRightChild = Branch Leaf node3 Leaf
      let tree1 = Branch initialLeftChild node1 initialRightChild

      let zipper2Branch = TreeBranch Leaf node4 Leaf
      let zipper2Tree = Branch Leaf node4 Leaf
      let zipper2Directions = [ TreeDirection LeftBranch node2 Leaf
                              , TreeDirection LeftBranch node1 initialRightChild ]
      let zipper2 = binaryTreeInsert tree1 node4

      zipper2 `shouldBe` (zipper2Branch, zipper2Directions)

      let zipper3Branch = TreeBranch Leaf node5 Leaf
      let zipper3Directions = [ TreeDirection RightBranch node2 zipper2Tree
                              , TreeDirection LeftBranch node1 initialRightChild ]
      let zipper3 = branchZipperInsert (getTreeRoot zipper2) node5

      zipper3 `shouldBe` (zipper3Branch, zipper3Directions)

    it "should be able to create a full tree of size 7 wth insertions" $ do
      let initialLeftLeftChild = Branch Leaf node4 Leaf
      let initialLeftRightChild = Branch Leaf node5 Leaf
      let initialLeftChild = Branch initialLeftLeftChild node2 initialLeftRightChild
      let initialRightChild = Branch Leaf node3 Leaf
      let tree1 = Branch initialLeftChild node1 initialRightChild

      let zipper2Branch = TreeBranch Leaf node6 Leaf
      let zipper2Tree = Branch Leaf node6 Leaf
      let zipper2Directions = [ TreeDirection LeftBranch node3 Leaf
                              , TreeDirection RightBranch node1 initialLeftChild ]
      let zipper2 = binaryTreeInsert tree1 node6

      zipper2 `shouldBe` (zipper2Branch, zipper2Directions)

      let zipper3Branch = TreeBranch Leaf node7 Leaf
      let zipper3Directions = [ TreeDirection RightBranch node3 zipper2Tree
                              , TreeDirection RightBranch node1 initialLeftChild ]
      let zipper3 = branchZipperInsert (getTreeRoot zipper2) node7

      zipper3 `shouldBe` (zipper3Branch, zipper3Directions)