{-# LANGUAGE BangPatterns #-}
module Task10 (
      SortedSet
    , emptySet
    , insertSet
    , setElem
    , splitMin
    , getMin
    ) where

import Control.DeepSeq

data SortedSet a = Node !a !(SortedSet a) !(SortedSet a)
                 | Empty
                 deriving (Eq, Show, Read)

instance NFData a => NFData (SortedSet a) where
    rnf !_ = ()

-- create empty set
emptySet :: SortedSet a
emptySet = Empty

-- | insert (or replace) element in set
insertSet :: (NFData a, Ord a) => a -> SortedSet a -> SortedSet a
insertSet !x Empty = Node (force x) Empty Empty
insertSet !x (Node v l r)
    | x == v = Node x l r
    | x <  v = Node x (insertSet x l) r
    | True   = Node x l (insertSet x r)

-- | check if value is in set (should be lazy in value if set is empty)
setElem :: Ord a => a -> SortedSet a -> Bool
setElem x Empty = False
setElem !x (Node v l r) = x == v || (x < v && setElem v l) || (x > v && setElem v r)

-- | Obtain minimal value from set
getMin :: Ord a => SortedSet a -> Maybe a
getMin Empty = Nothing
getMin (Node v Empty _) = Just v
getMin (Node v l _)     = let !min = getMin l in min

-- | Separate minimum form set and return both minimum and set witout minimum
splitMin :: Ord a => SortedSet a -> Maybe (a, SortedSet a)
splitMin Empty = Nothing
splitMin node  = Just $! split node
  where
    split (Node v Empty r) = (v, r)
    split (Node v l r)     = let !(!min, !l') = split l in (min, Node v l' r)