{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies, Safe #-}

{-
  This module is part of Chatty.
  Copyleft (c) 2014 Marvin Cohrs

  All wrongs reversed. Sharing is an act of love, not crime.
  Please share Chatty with everyone you like.

  Chatty is free software: you can redistribute it and/or modify
  it under the terms of the GNU Affero General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  Chatty is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  GNU Affero General Public License for more details.

  You should have received a copy of the GNU Affero General Public License
  along with Chatty. If not, see <http://www.gnu.org/licenses/>.
-}

-- | Provides an unbalanced BST with a focus on the root.
module Data.Chatty.Focus (Focus, focusSelect) where

import Data.Chatty.BST
import Data.Chatty.None

-- | An unbalanced BST with a focus on the root.
newtype Focus a = Focus { Focus a -> BST a
runFocus :: BST a }

instance None (Focus a) where
  none :: Focus a
none = BST a -> Focus a
forall a. BST a -> Focus a
Focus BST a
forall n. None n => n
none

instance Indexable i o v => AnyBST Focus i o v where
  anyBstInsert :: i -> Focus i -> Focus i
anyBstInsert i
i Focus i
t = BST i -> Focus i
forall a. BST a -> Focus a
Focus (BST i -> Focus i) -> BST i -> Focus i
forall a b. (a -> b) -> a -> b
$ i -> BST i -> BST i
forall i o v. Indexable i o v => i -> BST i -> BST i
bstInsert i
i (BST i -> BST i) -> BST i -> BST i
forall a b. (a -> b) -> a -> b
$ Focus i -> BST i
forall a. Focus a -> BST a
runFocus Focus i
t
  anyBstRemove :: o -> Focus i -> Focus i
anyBstRemove o
o Focus i
t = BST i -> Focus i
forall a. BST a -> Focus a
Focus (BST i -> Focus i) -> BST i -> Focus i
forall a b. (a -> b) -> a -> b
$ o -> BST i -> BST i
forall i o v. Indexable i o v => o -> BST i -> BST i
bstRemove o
o (BST i -> BST i) -> BST i -> BST i
forall a b. (a -> b) -> a -> b
$ Focus i -> BST i
forall a. Focus a -> BST a
runFocus Focus i
t
  anyBstMax :: Focus i -> Maybe i
anyBstMax Focus i
t = BST i -> Maybe i
forall i. BST i -> Maybe i
bstMax (BST i -> Maybe i) -> BST i -> Maybe i
forall a b. (a -> b) -> a -> b
$ Focus i -> BST i
forall a. Focus a -> BST a
runFocus Focus i
t
  anyBstMin :: Focus i -> Maybe i
anyBstMin Focus i
t = BST i -> Maybe i
forall i. BST i -> Maybe i
bstMin (BST i -> Maybe i) -> BST i -> Maybe i
forall a b. (a -> b) -> a -> b
$ Focus i -> BST i
forall a. Focus a -> BST a
runFocus Focus i
t
  anyBstLookup :: o -> Focus i -> Maybe v
anyBstLookup o
o Focus i
t = o -> BST i -> Maybe v
forall i o v. Indexable i o v => o -> BST i -> Maybe v
bstLookup o
o (BST i -> Maybe v) -> BST i -> Maybe v
forall a b. (a -> b) -> a -> b
$ Focus i -> BST i
forall a. Focus a -> BST a
runFocus Focus i
t
  anyBstHead :: Focus i -> Maybe i
anyBstHead Focus i
t = BST i -> Maybe i
forall i o v. Indexable i o v => BST i -> Maybe i
bstHead (BST i -> Maybe i) -> BST i -> Maybe i
forall a b. (a -> b) -> a -> b
$ Focus i -> BST i
forall a. Focus a -> BST a
runFocus Focus i
t
  anyBstEmpty :: Focus i
anyBstEmpty = BST i -> Focus i
forall a. BST a -> Focus a
Focus BST i
forall n. None n => n
none
  anyBstInorder :: Focus i -> [i]
anyBstInorder Focus i
t = BST i -> [i]
forall i o v. Indexable i o v => BST i -> [i]
bstInorder (BST i -> [i]) -> BST i -> [i]
forall a b. (a -> b) -> a -> b
$ Focus i -> BST i
forall a. Focus a -> BST a
runFocus Focus i
t

focusSelect' :: Indexable i o v => o -> BST i -> Maybe (BST i)
focusSelect' :: o -> BST i -> Maybe (BST i)
focusSelect' o
_ BST i
EmptyBST = Maybe (BST i)
forall a. Maybe a
Nothing
focusSelect' o
o t :: BST i
t@(BST i
a BST i
l BST i
r)
  | o
o o -> o -> Bool
forall a. Eq a => a -> a -> Bool
== i -> o
forall i o v. Indexable i o v => i -> o
indexOf i
a = BST i -> Maybe (BST i)
forall a. a -> Maybe a
Just BST i
t
  | o
o o -> o -> Bool
forall a. Ord a => a -> a -> Bool
< i -> o
forall i o v. Indexable i o v => i -> o
indexOf i
a = case o -> BST i -> Maybe (BST i)
forall i o v. Indexable i o v => o -> BST i -> Maybe (BST i)
focusSelect' o
o BST i
l of
      Just (BST i
a' BST i
l' BST i
r') -> BST i -> Maybe (BST i)
forall a. a -> Maybe a
Just (BST i -> Maybe (BST i)) -> BST i -> Maybe (BST i)
forall a b. (a -> b) -> a -> b
$ i -> BST i -> BST i -> BST i
forall a. a -> BST a -> BST a -> BST a
BST i
a' BST i
l' (i -> BST i -> BST i -> BST i
forall a. a -> BST a -> BST a -> BST a
BST i
a BST i
r' BST i
r)
      Maybe (BST i)
Nothing -> Maybe (BST i)
forall a. Maybe a
Nothing
  | Bool
otherwise = case o -> BST i -> Maybe (BST i)
forall i o v. Indexable i o v => o -> BST i -> Maybe (BST i)
focusSelect' o
o BST i
r of
      Maybe (BST i)
Nothing -> Maybe (BST i)
forall a. Maybe a
Nothing
      Just (BST i
a' BST i
l' BST i
r') -> BST i -> Maybe (BST i)
forall a. a -> Maybe a
Just (BST i -> Maybe (BST i)) -> BST i -> Maybe (BST i)
forall a b. (a -> b) -> a -> b
$ i -> BST i -> BST i -> BST i
forall a. a -> BST a -> BST a -> BST a
BST i
a' (i -> BST i -> BST i -> BST i
forall a. a -> BST a -> BST a -> BST a
BST i
a BST i
l BST i
l') BST i
r'

focusInsert' :: Indexable i o v => i -> BST i -> BST i
focusInsert' :: i -> BST i -> BST i
focusInsert' i
i = Maybe (BST i) -> BST i
forall a. Maybe a -> a
unjust (Maybe (BST i) -> BST i)
-> (BST i -> Maybe (BST i)) -> BST i -> BST i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. o -> BST i -> Maybe (BST i)
forall i o v. Indexable i o v => o -> BST i -> Maybe (BST i)
focusSelect' (i -> o
forall i o v. Indexable i o v => i -> o
indexOf i
i) (BST i -> Maybe (BST i))
-> (BST i -> BST i) -> BST i -> Maybe (BST i)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. i -> BST i -> BST i
forall i o v. Indexable i o v => i -> BST i -> BST i
bstInsert i
i
  where unjust :: Maybe a -> a
unjust (Just a
j) = a
j

-- | Rotate the tree such that the given element becomes the root node.
focusSelect :: o -> Focus a -> Maybe (Focus a)
focusSelect o
o Focus a
t = (BST a -> Focus a) -> Maybe (BST a) -> Maybe (Focus a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap BST a -> Focus a
forall a. BST a -> Focus a
Focus (Maybe (BST a) -> Maybe (Focus a))
-> Maybe (BST a) -> Maybe (Focus a)
forall a b. (a -> b) -> a -> b
$ o -> BST a -> Maybe (BST a)
forall i o v. Indexable i o v => o -> BST i -> Maybe (BST i)
focusSelect' o
o (BST a -> Maybe (BST a)) -> BST a -> Maybe (BST a)
forall a b. (a -> b) -> a -> b
$ Focus a -> BST a
forall a. Focus a -> BST a
runFocus Focus a
t