-- |
-- Module      : Data.RedBlackTree.TreeFamily
-- Copyright   : (c) 2017 Gabriel Aumala
--
-- License     : BSD3
-- Maintainer  : gabriel@criptext.com
-- Stability   : experimental
-- Portability : GHC
--
-- @TreeFamily@ is a structure that is used to describe the hierarchy of a tree
-- in which a new branch has been isenrted at the bottom. With this we can quickly answer
-- questions like is the new branch the root? Does it only have parent? Does have
-- a grandparent or more ancestors?. This is used internally by
-- "Data.RedBlackTree.InsertionAlgorithm" to identify insertion cases and handle
-- the appropriately.
module Data.RedBlackTree.TreeFamily (
  getTreeFamily,
  TreeFamily (IsRoot, HasParent, HasGrandparent)
) where

import Data.RedBlackTree.BinaryTree
-- | Describes the hierarchy 3 kinds of non empty trees:
--
-- 1. A tree with only 1 item. (@IsRoot@).
-- 2. A tree with a 2 level herarchy: parent and child. ()@HasParent@).
-- 3. A tree with a hierarchy of at least 3 levels: grandparent, parent and
-- child. (@HasGrandparent@)
data TreeFamily a =
  IsRoot (TreeBranch a) |
  HasParent (TreeDirection a) (TreeBranch a) |
  HasGrandparent (TreeDirections a) (TreeDirection a) (TreeDirection a)
    (TreeBranch a)

getTreeFamily' :: (BinaryTreeNode a) => BranchZipper a -> TreeDirection a ->
  TreeBranch a -> TreeFamily a
getTreeFamily' :: forall a.
BinaryTreeNode a =>
BranchZipper a -> TreeDirection a -> TreeBranch a -> TreeFamily a
getTreeFamily' (TreeBranch a
parentBranch, []) TreeDirection a
direction TreeBranch a
branch =
  TreeDirection a -> TreeBranch a -> TreeFamily a
forall a. TreeDirection a -> TreeBranch a -> TreeFamily a
HasParent TreeDirection a
direction TreeBranch a
branch
getTreeFamily' (TreeBranch a
_, TreeDirection a
grandparentDirection:TreeDirections a
xs) TreeDirection a
parentDirection TreeBranch a
branch =
  TreeDirections a
-> TreeDirection a
-> TreeDirection a
-> TreeBranch a
-> TreeFamily a
forall a.
TreeDirections a
-> TreeDirection a
-> TreeDirection a
-> TreeBranch a
-> TreeFamily a
HasGrandparent TreeDirections a
xs TreeDirection a
grandparentDirection TreeDirection a
parentDirection TreeBranch a
branch

-- | Takes a zipper focusing on a branch and returns a @TreeFamily@ structure
-- relative to that branch.
getTreeFamily :: (BinaryTreeNode a) => BranchZipper a -> TreeFamily a
getTreeFamily :: forall a. BinaryTreeNode a => BranchZipper a -> TreeFamily a
getTreeFamily (TreeBranch a
branch, []) = TreeBranch a -> TreeFamily a
forall a. TreeBranch a -> TreeFamily a
IsRoot TreeBranch a
branch
getTreeFamily (TreeBranch a
branch, TreeDirection a
direction:TreeDirections a
xs) =
  (TreeBranch a, TreeDirections a)
-> TreeDirection a -> TreeBranch a -> TreeFamily a
forall a.
BinaryTreeNode a =>
BranchZipper a -> TreeDirection a -> TreeBranch a -> TreeFamily a
getTreeFamily' (TreeBranch a, TreeDirections a)
parentZipper TreeDirection a
direction TreeBranch a
branch
  where parentBranch :: TreeBranch a
parentBranch = TreeBranch a -> TreeDirection a -> TreeBranch a
forall a.
BinaryTreeNode a =>
TreeBranch a -> TreeDirection a -> TreeBranch a
reconstructAncestor TreeBranch a
branch TreeDirection a
direction
        parentZipper :: (TreeBranch a, TreeDirections a)
parentZipper = (TreeBranch a
parentBranch, TreeDirections a
xs)