{-# LANGUAGE FlexibleInstances, TypeSynonymInstances #-}
module JoinList where
import Data.Monoid
import Sized
data JoinList m a = Empty
                  | Single m a
                  | Append m (JoinList m a) (JoinList m a)
                  deriving (Eq, Show)


tag :: Monoid m => JoinList m a -> m
tag (Single m _) = m
tag (Append m _ _) = m

(+++) :: Monoid m => JoinList m a -> JoinList m a -> JoinList m a
(+++) Empty a = a
(+++) a Empty = a
-- (+++) elem1@(Single m1 _) elem2@(Single m2 _) =  Append (mappend (tag elem1) (tag elem2)) elem1 elem2
(+++) elem1 elem2 =  Append (mappend (tag elem1) (tag elem2)) elem1 elem2


indexJ :: (Sized b, Monoid b) => Int -> JoinList b a -> Maybe a
indexJ _ Empty = Nothing
indexJ n (Single m a) = Just a
indexJ n root@(Append m left right)
  | n > size_root = Nothing
  | n > size_left = indexJ (n - size_left) right
  | otherwise = indexJ n left
  where size_left = getSize(size (tag left))
        size_root = getSize(size (tag root))

dropJ :: (Sized b, Monoid b) => Int -> JoinList b a -> JoinList b a
dropJ n Empty = Empty
dropJ 1 (Single m a) = Empty
dropJ n root@(Append m left right)
  | n > size_root = Empty
  | n > size_left =  dropJ (n - size_left) right
  | otherwise = new_left +++ right
  where
    size_left = getSize(size (tag left))
    size_root = getSize(size (tag root))
    new_left = dropJ n left

takeJ :: (Sized b, Monoid b) => Int -> JoinList b a -> JoinList b a
takeJ n Empty = Empty
takeJ 1 (Single m a) = Empty
takeJ n root@(Append m left right)
  | n > size_root = root
  | n > size_left = left +++ new_right
  | otherwise = Append m (dropJ n left) right
  where size_left = getSize(size (tag left))
        size_root = getSize(size (tag root))
        new_right = takeJ (n - size_left) right