type Tree<'a> =
| Lf
| Br of 'a * Tree<'a> * Tree<'a>;;

let A = Br( (1005,"budi"), Br((1002, "anto"), Br((1001, "tato"),Lf, Lf), Br((1003, "anca"),Lf, Lf)) , Br((1008, "andi"), Br((1006, "ani"),Lf, Lf), Br((1007, "didi"),Lf, Lf)) );;

let F = [(1001, 1002); (1001, 1006); (1005, 1007); (1006, 1008)];;
let fsn = (A,F);;

(*=========================1.isMember(fsn,id)====================================================*)

let rec isMemberHelp = function
| (Lf,F),idN -> false
| ((Br((id,name),anakKiri,anakKanan),F),idN) -> if idN = id then true
                                                elif idN < id then isMemberHelp((anakKiri,F),idN)
                                                else isMemberHelp((anakKanan,F),idN);;

let isMember (fsn,id) = isMemberHelp(fsn,id);;

isMember (fsn,1005);;


(*=========================2.whoIs(fsn,id)====================================================*)

let rec whoIsHelp = function
| (Lf,F),idWanted -> raise(System.ArgumentException("Tidak Ada!!"))
| ((Br((id,name),anakKiri,anakKanan),F),idWanted) -> if idWanted = id then name
                                                     elif idWanted < id then whoIsHelp((anakKiri,F),idWanted)
                                                     else whoIsHelp((anakKanan,F),idWanted);;

let whoIs (fsn, id) = whoIsHelp(fsn,id);;
whoIs (fsn, 1005);;
(*=========================3.updateName(fsn,id,newName)====================================================*)

let rec updateNameHelp = function
| (Lf,F),id, newName -> raise(System.ArgumentException("Tidak Ada!!"))
| ((Br((id,name),anakKiri,anakKanan),F),idChanged, newName) -> if idChanged < id then Br((id,name), updateNameHelp((anakKiri,F),idChanged, newName),anakKanan)
                                                               elif id < idChanged then Br((id,name), anakKiri, updateNameHelp((anakKanan, F), idChanged, newName))
                                                               else Br((id,newName),anakKiri,anakKanan);;

let updateName (fsn, id, newName) = updateNameHelp(fsn,id,newName);;
updateName(fsn, 1005, "banu");;

(*=========================4.join(fsn,newId,newName)====================================================*)

let rec joinHelp = function
| ((Lf, F),newId,newName) -> Br ((newId, newName),Lf,Lf)
| ((Br((id,name),anakKiri,anakKanan),F),newId, newName) -> if newId < id then Br((id,name), joinHelp((anakKiri, F), newId, newName),anakKanan)
                                                           elif (newId > id) then Br ((id,name), anakKiri, joinHelp ((anakKanan,F), newId, newName))
                                                           else raise(System.ArgumentException("Sudah Ada!!"));;
let join (fsn,newId,newName) = joinHelp(fsn,newId,newName);;

join (fsn, 1011, "yati");;
(*=========================5.removeAccount(fsn, id)====================================================*)

let rec delMin = function
 | Br ((id,name), Lf, anakKanan) -> ((id,name), anakKanan)
 | Br ((id,name), anakKiri, anakKanan) -> let (minEl, new_anakKiri) = delMin anakKiri
                                          (minEl, Br((id,name), new_anakKiri, anakKanan));;

let rec removeA = function
 | (Lf, idDel) -> Lf
 | (Br ((id,name), anakKiri, anakKanan), idDel) ->
 if (idDel < id) then Br ((id,name), removeA (anakKiri, idDel), anakKanan)
 elif (idDel > id) then Br ((id,name), anakKiri, removeA (anakKanan, idDel))
 else match anakKanan with
 | Lf -> anakKiri
 | _ -> let (minEl, new_anakKanan) = delMin anakKanan (*e = v*)
        Br (minEl, anakKiri, new_anakKanan);;

let rec removeF = function
| [],delId -> []
| ((idFollower,idFollowee)::xs),delId -> if delId = idFollower || delId = idFollowee then removeF (xs,delId)
                                         else ((idFollower, idFollowee)) :: removeF (xs,delId);;

let rec removeAccount ((A,F),id) = (removeA(A,id),removeF(F, id));;

removeAccount (fsn, 1005);;

(*=========================6.listOfAccounts(fsn)====================================================*)
let rec listOfAccountsHelper = function
|Lf -> []
|Br((id,name),anakKiri,anakKanan) -> listOfAccountsHelper anakKiri @ [id,name] @ listOfAccountsHelper anakKanan;;

let rec listOfAccounts((A,F)) = listOfAccountsHelper(A);;

listOfAccounts(fsn);;
A;;
(*=========================7.mergeAccount(fsn1, fsn2)====================================================*)

let rec joinHelp = function
|(Lf, newId, newName) -> Br((newId,newName), Lf, Lf)
|(Br ((id,name), anakKiri, anakKanan), newId, newName) ->
  if (newId<id) then Br ((id,name), joinHelp(anakKiri, newId, newName), anakKanan)
  elif (newId>id) then Br ((id,name), anakKiri, joinHelp(anakKanan, newId, newName))
  else Br((id,name),anakKiri,anakKanan);;

let rec listOfAccountsHelp = function
|(Lf,vs) -> vs
|(Br(v,anakKiri,anakKanan),vs) -> listOfAccountsHelp (anakKiri,v::listOfAccountsHelp(anakKanan,vs));;

let listOfAccount(A) = listOfAccountsHelp(A,[]);;

let joinAccount(fsn2) = listOfAccount(fsn2);;

let rec joinTree = function
|([],tree)-> tree
|((newId,newName)::sisaList,tree) -> (joinTree(sisaList,joinHelp(tree,newId,newName)));;

let rec isExists = function
|((idFollower,idFollowee),[]) -> true
|((idFollower,idFollowee),((idFollower2,idFollowee2)::xs)) ->
  if(idFollower=idFollower2 && idFollowee=idFollowee2) then true
  else isExists((idFollower,idFollowee),xs);;

let rec joinList = function
|([],y) -> y
|((idFollower,idFollowee)::xs,y) ->
  if(isExists((idFollower,idFollowee),y)) then joinList(xs,y)
  else (idFollower,idFollowee)::y;;

let rec mergeAccount((A,F),(A2,F2)) = ((joinTree(joinAccount(A2),A)),(joinList(F2,F)));;

let fsn1 = (A,F);

let A2 = Br((5,"budi"), Br((2, "anto"), Br((1, "tato"), Lf, Lf), Br((3, "anca"), Lf, Lf)),
                          Br((8, "andi"), Br((6, "ani"), Lf, Lf), Br((7, "didi"), Lf, Lf)));;
let F2 = [(1,2);(1,6);(5,7);(6,8)];;
let fsn2 = (A2,F2);

mergeAccount(fsn1,fsn2);;
(*=============================================================================================================*)

let rec map f = function
|[] -> []
|x::xs -> (f x) :: map f xs;;

let rec foldl f = function
|(e,[]) -> e
|(e,x::xs) -> foldl f (f(e,x),xs);;

let rec foldr f = function
|([],e) -> e
|(x::xs,e) -> f(x, foldr f (xs,e));;

let rec maptree f = function
|Lf -> Lf
|(Br (v,t1,t2)) ->
     Br (f v, maptree f t1, maptree f t2);;

let rec fold f e = function
|Lf -> e
|(Br (v,t1,t2)) ->
      f (v, fold f e t1, fold f e t2);;

(*=========================1.reverseRelation(fsn)====================================================*)
let getF(A,F)=F;;

let reverseRelation x = foldr (fun ((x,y),e) -> (y,x)::e) (getF(x),[]);;

reverseRelation fsn;;
(*=========================2.checkFollowerId(fsn)====================================================*)
let getF(A,F)=F;;

let checkFollowerId x = foldr (fun ((x,y),e) -> if x<y then 1::e else 0::e) (getF(x),[]);;

checkFollowerId fsn;;
(*=========================3.getTotalFollowers(fsn, id)====================================================*)
let getF(A,F)=F;;

let getTotalFollowers (x,y) = foldr (fun ((a,b),e) -> if y = b then e+1 else e) (getF(x),0);;

getTotalFollowers (fsn,1002);;
(*=========================4.getTotalFollowees(fsn, id)====================================================*)
let getF(A,F)=F;;

let getTotalFollowees (x,y) = foldr (fun ((a,b),e) -> if y = a then e+1 else e) (getF(x),0);;

getTotalFollowees (fsn,1001);;
(*=========================5.listOfFollowers(fsn, id) ====================================================*)
let fsn= (A,F);;
let getF(A,F)=F;;

let rec whoIs = function
|((Lf,F),idWanted) -> raise(System.ArgumentException("Id tidak ada"))
|((Br((id,name),t1,t2),F),idWanted) ->
    if (idWanted<id) then whoIs ((t1,F), idWanted)
    elif (idWanted>id) then whoIs ((t2,F),idWanted)
    else name;;

let listOfFollowers (x,y) = foldr (fun ((a,b),e) -> if y = b then whoIs(x,a)::e else e) (getF(x),[]);;

listOfFollowers (fsn,1005);;
(*=========================6.listOfFollowees(fsn, id)====================================================*)
let getF(A,F)=F;;

let rec whoIs = function
|((Lf,F),idWanted) -> raise(System.ArgumentException("Id tidak ada"))
|((Br((id,name),anakKiri,anakKanan),F),idWanted) ->
    if (idWanted<id) then whoIs ((anakKiri,F), idWanted)
    elif (idWanted>id) then whoIs ((anakKanan,F),idWanted)
    else name;;

let listOfFollowees (x,y) = foldr (fun ((a,b),e) -> if y = a then whoIs(x,b)::e else e) (getF(x),[]);;
whoIs(fsn,1005);;
listOfFollowees (fsn,1005);;
(*=========================7.checkMutualRelation(fsn, id1, id2)====================================================*)
let getF(A,F)=F;;

let checkMutualRelation1(x,y,z) = foldr (fun ((a,b),e) -> if a=y && b=z then true else e) (getF(x),false);
let checkMutualRelation2(x,y,z) = foldr (fun ((a,b),e) -> if a=z && b=y then true else e) (getF(x),false);

let checkMutualRelation(fsn,id1,id2)=checkMutualRelation1(fsn,id1,id2) && checkMutualRelation2(fsn,id1,id2);;

checkMutualRelation(fsn,1001,1002);;
(*=========================8.listOfIds(fsn)====================================================*)
let rec maptree f = function
|Lf -> Lf
|(Br (v,t1,t2)) ->
     Br (f v, maptree f t1, maptree f t2);;

let getA(A,F)=A;;

let listOfIds x = maptree (fun (id,nama) -> id) (getA(x));;

listOfIds fsn;;