module MoreTrees exposing (..)

type Tree a = Empty | Node a (Tree a) (Tree a)

height t =
  case t of
    Empty ->
      0
    Node _ left right ->
      1 + max (height left) (height right)

------------------------------------------------------------------------------

{-
isFull tree =
  let
    h =
      height tree

    foo depth subtree =
      if depth == h {- && subtree == Empty -} then
        True
      else
        case subtree of
          Empty ->
            False
          Node _ left right ->
            foo (depth + 1) left && foo (depth + 1) right
  in
  foo 0 tree
-}

------------------------------------------------------------------------------

isFull : Tree a -> Bool
isFull t =
  case maybeFullTreeHeight t of
    Just _  -> True
    Nothing -> False
    
maybeFullTreeHeight : Tree a -> Maybe Int
maybeFullTreeHeight t =
  case t of
    Empty ->
      Just 0

    Node _ left right ->
      maybeFullTreeHeight left  |> maybeAndThen (\h1 ->
      maybeFullTreeHeight right |> maybeAndThen (\h2 ->
      maybeGuard (h1 == h2)     |> maybeAndThen (\() ->
        Just (1 + h1)
      )))

{-
      case maybeFullTreeHeight left of
        Nothing -> Nothing
        Just h1 ->
          case maybeFullTreeHeight right of
            Nothing -> Nothing
            Just h2 ->
              if h1 == h2
                then Just (1 + h1)
                else Nothing
-}


------------------------------------------------------------------------------

maybeAndThen : (a -> Maybe b) -> Maybe a -> Maybe b
maybeAndThen f mx =
  case mx of
    Nothing -> Nothing
    Just x  -> f x

maybePure : a -> Maybe a
maybePure x =
  Just x

maybeGuard : Bool -> Maybe ()
maybeGuard b =
  if b
    then Just ()
    else Nothing