import Prelude hiding (lookup)
import qualified Data.List as List

class Collection c where
    empty :: c key value
    singleton :: key -> value -> c key value
    insert:: Ord key => key -> value -> c key value -> c key value
    lookup:: Ord key => key -> c key value -> Maybe value
    delete :: Ord key => key -> c key value -> c key value
    keys :: c key value -> [key]
    keys collection = [fst x | x<- toList collection]
    values :: c key value -> [value]
    values collection = [snd x | x<- toList collection] 
    toList :: c key value -> [(key, value)]
    fromList :: Ord key => [(key, value)] -> c key value
    fromList = foldr (Prelude.uncurry insert) empty
    -- fromList list = insertInto empty list
    --     where
          insertInto : :  key = > c ke value - > [ ( key , value ) ] - > c key value 
          insertInto acc [ ] = acc 
          insertInto acc ( x : xs ) = insertInto ( insert ( fst x ) ( snd x ) acc ) xs 

newtype PairList  k v
    = PairList {getPairList ::[(k,v)]}

exercitiul 1 
instance Collection PairList where
  empty = PairList []
  singleton a b = PairList ([(a,b)])
  insert a b c = PairList ( getPairList c ++ [(a,b)])
  lookup k c = lookup' k (getPairList c)
    where 
      lookup' _ [] = Nothing
      lookup' a (x:xs) | fst x == a = Just (snd x)
                       | otherwise = lookup' a xs
  delete k c = PairList (delete' k (getPairList c))
    where
      delete' k (x:xs) | fst x == k = delete' k xs
                       | otherwise = x : delete' k xs
  toList c = getPairList c

exercitiul 2 
data SearchTree key value
  = Empty
  | Node
      (SearchTree key value) -- elemente cu cheia mai mica 
      key                    -- cheia elementului
  valoarea elementului 
      (SearchTree key value) -- elemente cu cheia mai mare

instance Collection SearchTree where
  empty = Empty
  singleton a b = Node Empty a (Just b) Empty
  insert a b (Node l key value r ) | a<key = Node (insert a b l) key value r
                                   | a>key = Node l key value (insert a b r) 
                                   | a==key = Node l key (Just b) r
  insert a b Empty = singleton a b
  lookup _ Empty = Nothing
  lookup k (Node l key o r ) | k == key = o
                             | k < key = lookup k l
                             | k > key = lookup k r
  delete k (Node l key value r) | k == key = Node l key Nothing r
                                | k < key = Node (delete k l) key value r 
                                | k > key = Node l key value (delete k r)
  toList Empty = []
  toList (Node l key (Just value) r ) = toList l ++ [(key,value)] ++ toList r
  toList (Node l _ Nothing r ) = toList l++ toList r  

data Element k v
    = Element k (Maybe v)
    | OverLimit
  
3 a 
instance Eq k => Eq (Element k v) where
    (Element k1 v1) == (Element k2 v2) = k2 == k1
    --(Element k1 v1) /= (Element k2 v2) = k2 /= k1
    (Element k v) == OverLimit = False
    OverLimit == (Element k v) = False
    OverLimit == OverLimit = True

3 b 
instance Ord k => Ord (Element k v) where
    (Element k1 v1) <= (Element k2 v2) = k1 <= k1
    OverLimit <= (Element k v) = False
    (Element k v) <= OverLimit = True

3 c 
instance (Show k, Show v) => Show (Element k v) where
    show (Element k (Just v)) = "("++ show k ++ ","++ show v++")"
    show (Element k (Nothing)) = show k
    show OverLimit = "[]"


4 

order :: Int
order = 1

data BTree key value
  = BEmpty
  | BNode [(BTree key value, Element key value)]

instance Collection BTree where
  empty = BEmpty
  singleton a b = BNode [(BEmpty, Element a (Just b)), (BEmpty, OverLimit)]

  lookup _ BEmpty = Nothing
  lookup k (BNode list) = go list
    where
      go ((less_than_key, OverLimit): list') = lookup k less_than_key
      go ((less_than_key, Element key o): list')
        | k == key = o
        | k < key = lookup k less_than_key
        | k > key = go list'

  delete _ BEmpty = BEmpty
  delete k (BNode list) = BNode (go list)
    where
      go ((less_than_key, OverLimit): list') = (delete k less_than_key, OverLimit): list'
      go ((less_than_key, Element key o): list')
        | k == key = (less_than_key, Element key Nothing): list'
        | k < key = ((delete k less_than_key, Element key o): list')
        | k > key = (less_than_key, Element key o): go list'

  toList BEmpty = []
  toList (BNode list) = go list
    where
      go ((less_than_key, OverLimit):_) = toList less_than_key
      go ((less_than_key, e): list') = toList less_than_key ++ elemToList e ++ go list'
      elemToList (Element key Nothing) = []
      elemToList (Element key (Just v)) = [(key, v)]

  insert k v tree = fst (insert' k v tree)
    where
      insert' k v BEmpty = (singleton k v, True)
      insert' k v (BNode list) = echilibreaza (go list)
      go ((less_than_key, OverLimit): list') =
        let (less_than_key', e) = insert' k v less_than_key
        in if e then let (BNode [(less_than_key'', element'),(greater_than_key'', OverLimit)]) = less_than_key' in [(less_than_key'', element'), (greater_than_key'',OverLimit)]
            else (less_than_key', OverLimit): list'
      go ((less_than_key, Element key o): list')
        | k == key = (less_than_key, Element key (Just v)): list'
        | k < key = 
          let (less_than_key', e) = insert' k v less_than_key
          in if e then let (BNode [(less_than_key'', element'),(greater_than_key'', OverLimit)]) = less_than_key' in (less_than_key'', element'): (greater_than_key'',Element key o): list'
             else (less_than_key', Element key o): list'
        | k > key = (less_than_key, Element key o): go list'
      echilibreaza noduri
        | lnod <= 2 * order + 1 = (BNode noduri, False)
        | otherwise = (BNode [( BNode (mici ++ [(mijlocii, OverLimit)]), emijloc), (BNode mari, OverLimit)], True)
        where
          lnod = length noduri
          mici = take order noduri
          ((mijlocii, emijloc):mari) = drop order noduri


 In    vom incerca sa implementam o 
      in Haskell . 
 Pentru a reprezenta un nod , am putea sa separam elementele de 
 subarbori ,         . O      imperechem fiecare subarbore cu elementul imediat in 
   . 
 Dar ce vom face cu ultimul subarbore ? O     creem   
 element artificial care sa fie mai “ mare ” decat orice alt element . 
  ar arata cam asa : 
         ( k1,v1 )    ( k2 , v2 ) ... ( kn , vn )   OverLimit 
     /            /              /            / 
 mai mici             mai mari decat kn 
 decat k1     si k2          si kn 


 BEmpty 

   Element 3 ( Just " a " )     Element 5 ( Just " b " )   OverLimit 
    /                          /                      / 
 BEmpty                   BEmpty                   BEmpty 

In continuarea acestui laborator vom incerca sa implementam o
versiune de B-arbori in Haskell.
Pentru a reprezenta un nod, am putea sa separam elementele de
subarbori, dar este mult mai convenabil sa le imperechem. O idee
simpla e sa imperechem fiecare subarbore cu elementul imediat in
dreapta lui.
Dar ce vom face cu ultimul subarbore? O idee ar fi sa creem un nou
element artificial care sa fie mai “mare” decat orice alt element.
Atunci ar arata cam asa:
        (k1,v1)   (k2, v2) ... (kn,vn)  OverLimit
    /           /             /           /
mai mici    intre k1      intre kn-1   mai mari decat kn
decat k1    si k2         si kn 


BEmpty

  Element 3 (Just "a")    Element 5 (Just "b")  OverLimit
   /                         /                     /
BEmpty                  BEmpty                  BEmpty
-}
 fromList list = insertInto empty list
     where
 elemente cu cheia mai mica 
 cheia elementului
 elemente cu cheia mai mare
(Element k1 v1) /= (Element k2 v2) = k2 /= k1

import Prelude hiding (lookup)
import qualified Data.List as List

class Collection c where
    empty :: c key value
    singleton :: key -> value -> c key value
    insert:: Ord key => key -> value -> c key value -> c key value
    lookup:: Ord key => key -> c key value -> Maybe value
    delete :: Ord key => key -> c key value -> c key value
    keys :: c key value -> [key]
    keys collection = [fst x | x<- toList collection]
    values :: c key value -> [value]
    values collection = [snd x | x<- toList collection] 
    toList :: c key value -> [(key, value)]
    fromList :: Ord key => [(key, value)] -> c key value
    fromList = foldr (Prelude.uncurry insert) empty
          insertInto : :  key = > c ke value - > [ ( key , value ) ] - > c key value 
          insertInto acc [ ] = acc 
          insertInto acc ( x : xs ) = insertInto ( insert ( fst x ) ( snd x ) acc ) xs 

newtype PairList  k v
    = PairList {getPairList ::[(k,v)]}

exercitiul 1 
instance Collection PairList where
  empty = PairList []
  singleton a b = PairList ([(a,b)])
  insert a b c = PairList ( getPairList c ++ [(a,b)])
  lookup k c = lookup' k (getPairList c)
    where 
      lookup' _ [] = Nothing
      lookup' a (x:xs) | fst x == a = Just (snd x)
                       | otherwise = lookup' a xs
  delete k c = PairList (delete' k (getPairList c))
    where
      delete' k (x:xs) | fst x == k = delete' k xs
                       | otherwise = x : delete' k xs
  toList c = getPairList c

exercitiul 2 
data SearchTree key value
  = Empty
  | Node
  valoarea elementului 

instance Collection SearchTree where
  empty = Empty
  singleton a b = Node Empty a (Just b) Empty
  insert a b (Node l key value r ) | a<key = Node (insert a b l) key value r
                                   | a>key = Node l key value (insert a b r) 
                                   | a==key = Node l key (Just b) r
  insert a b Empty = singleton a b
  lookup _ Empty = Nothing
  lookup k (Node l key o r ) | k == key = o
                             | k < key = lookup k l
                             | k > key = lookup k r
  delete k (Node l key value r) | k == key = Node l key Nothing r
                                | k < key = Node (delete k l) key value r 
                                | k > key = Node l key value (delete k r)
  toList Empty = []
  toList (Node l key (Just value) r ) = toList l ++ [(key,value)] ++ toList r
  toList (Node l _ Nothing r ) = toList l++ toList r  

data Element k v
    = Element k (Maybe v)
    | OverLimit
  
3 a 
instance Eq k => Eq (Element k v) where
    (Element k1 v1) == (Element k2 v2) = k2 == k1
    (Element k v) == OverLimit = False
    OverLimit == (Element k v) = False
    OverLimit == OverLimit = True

3 b 
instance Ord k => Ord (Element k v) where
    (Element k1 v1) <= (Element k2 v2) = k1 <= k1
    OverLimit <= (Element k v) = False
    (Element k v) <= OverLimit = True

3 c 
instance (Show k, Show v) => Show (Element k v) where
    show (Element k (Just v)) = "("++ show k ++ ","++ show v++")"
    show (Element k (Nothing)) = show k
    show OverLimit = "[]"


4 

order :: Int
order = 1

data BTree key value
  = BEmpty
  | BNode [(BTree key value, Element key value)]

instance Collection BTree where
  empty = BEmpty
  singleton a b = BNode [(BEmpty, Element a (Just b)), (BEmpty, OverLimit)]

  lookup _ BEmpty = Nothing
  lookup k (BNode list) = go list
    where
      go ((less_than_key, OverLimit): list') = lookup k less_than_key
      go ((less_than_key, Element key o): list')
        | k == key = o
        | k < key = lookup k less_than_key
        | k > key = go list'

  delete _ BEmpty = BEmpty
  delete k (BNode list) = BNode (go list)
    where
      go ((less_than_key, OverLimit): list') = (delete k less_than_key, OverLimit): list'
      go ((less_than_key, Element key o): list')
        | k == key = (less_than_key, Element key Nothing): list'
        | k < key = ((delete k less_than_key, Element key o): list')
        | k > key = (less_than_key, Element key o): go list'

  toList BEmpty = []
  toList (BNode list) = go list
    where
      go ((less_than_key, OverLimit):_) = toList less_than_key
      go ((less_than_key, e): list') = toList less_than_key ++ elemToList e ++ go list'
      elemToList (Element key Nothing) = []
      elemToList (Element key (Just v)) = [(key, v)]

  insert k v tree = fst (insert' k v tree)
    where
      insert' k v BEmpty = (singleton k v, True)
      insert' k v (BNode list) = echilibreaza (go list)
      go ((less_than_key, OverLimit): list') =
        let (less_than_key', e) = insert' k v less_than_key
        in if e then let (BNode [(less_than_key'', element'),(greater_than_key'', OverLimit)]) = less_than_key' in [(less_than_key'', element'), (greater_than_key'',OverLimit)]
            else (less_than_key', OverLimit): list'
      go ((less_than_key, Element key o): list')
        | k == key = (less_than_key, Element key (Just v)): list'
        | k < key = 
          let (less_than_key', e) = insert' k v less_than_key
          in if e then let (BNode [(less_than_key'', element'),(greater_than_key'', OverLimit)]) = less_than_key' in (less_than_key'', element'): (greater_than_key'',Element key o): list'
             else (less_than_key', Element key o): list'
        | k > key = (less_than_key, Element key o): go list'
      echilibreaza noduri
        | lnod <= 2 * order + 1 = (BNode noduri, False)
        | otherwise = (BNode [( BNode (mici ++ [(mijlocii, OverLimit)]), emijloc), (BNode mari, OverLimit)], True)
        where
          lnod = length noduri
          mici = take order noduri
          ((mijlocii, emijloc):mari) = drop order noduri


 In    vom incerca sa implementam o 
      in Haskell . 
 Pentru a reprezenta un nod , am putea sa separam elementele de 
 subarbori ,         . O      imperechem fiecare subarbore cu elementul imediat in 
   . 
 Dar ce vom face cu ultimul subarbore ? O     creem   
 element artificial care sa fie mai “ mare ” decat orice alt element . 
  ar arata cam asa : 
         ( k1,v1 )    ( k2 , v2 ) ... ( kn , vn )   OverLimit 
     /            /              /            / 
 mai mici             mai mari decat kn 
 decat k1     si k2          si kn 


 BEmpty 

   Element 3 ( Just " a " )     Element 5 ( Just " b " )   OverLimit 
    /                          /                      / 
 BEmpty                   BEmpty                   BEmpty 

In continuarea acestui laborator vom incerca sa implementam o
versiune de B-arbori in Haskell.
Pentru a reprezenta un nod, am putea sa separam elementele de
subarbori, dar este mult mai convenabil sa le imperechem. O idee
simpla e sa imperechem fiecare subarbore cu elementul imediat in
dreapta lui.
Dar ce vom face cu ultimul subarbore? O idee ar fi sa creem un nou
element artificial care sa fie mai “mare” decat orice alt element.
Atunci ar arata cam asa:
        (k1,v1)   (k2, v2) ... (kn,vn)  OverLimit
    /           /             /           /
mai mici    intre k1      intre kn-1   mai mari decat kn
decat k1    si k2         si kn 


BEmpty

  Element 3 (Just "a")    Element 5 (Just "b")  OverLimit
   /                         /                     /
BEmpty                  BEmpty                  BEmpty
-}