(* PS2 solutions (c) Cornell University CS312 Fall 2002 *)

signature PART1 = sig

   val insert: string -> string -> (string*string) list -> (string*string) list
   val lookup: string -> (string * string) list -> string
   val polymorphicLookup: 'a -> ('a * 'a -> bool) -> ('a * 'b) list -> 'b
   val lookupCUID: int -> (int * string) list -> string

end

structure Part1Sol :> PART1 = struct
   (* YOU MAY NOT CHANGE ANYTHING BEFORE THIS LINE *)

   (****************** PART 1 ******************)

   (* 1 *)
   fun insert (key: string) (value: string) (lst: (string*string) list) =
          (key, value) :: lst

   (* 2 *)
   fun lookup (key:string) (lst: (string*string) list) : string =
     case (List.find (fn (k,_)=>k=key) lst) of
       SOME (_,v) => v
     | _ => raise Fail "Not Found!"

   (* 2 - Alternative solution *)
   fun lookup2 (key: string) (lst: (string * string) list)  =
     case lst of
       [] => raise Fail "Not found!"
     | (key2, val2)::tl => if key = key2
                           then val2
                           else lookup key tl

   (* 3 *)
   fun polymorphicLookup (key: 'a) (equal: 'a*'a->bool) (lst: ('a*'b) list) =
     case (List.find (fn (k,_)=>equal(k,key)) lst) of
       SOME (_,v) => v
     | _ => raise Fail "Not Found!"

   (* 3 - Alternative solution *)
   fun polymorphicLookup2 (key: 'a) (equal: 'a*'a->bool) (lst: ('a*'b) list) =
     case lst of
       [] => raise Fail "Not found!"
     | (key2, val2)::tl => if equal(key, key2)
                           then val2
                           else polymorphicLookup key equal tl

   (* 4 *)
   fun lookupCUID (id: int) (lst: (int * string) list): string =
     (polymorphicLookup id (op =)  lst)

end

signature PART2 = sig

   datatype 'a llist = LList of 'a llist list | Elem of 'a

   val flatten: 'a llist -> 'a list
   val depth: 'a llist -> int
   val cutOff: int * 'a llist -> 'a llist

end

structure Part2Sol :> PART2 = struct
   (* YOU MAY NOT CHANGE ANYTHING BEFORE THIS LINE *)

   (****************** PART 2 ******************)

   datatype 'a llist = LList of 'a llist list | Elem of 'a

   (* 5 *)
   fun flatten(l:'a llist) : 'a list =
     case l of
       Elem(x) => [x]
     | LList(lst) => List.concat (List.map flatten lst)

   (* 6 *)
   fun depth(l:'a llist) : int =
     case l of
       Elem(_) => 0
     | LList(lst) => 1 + (foldl Int.max 0 (List.map depth lst))

   (* 7 *)
   fun cutOff (n:int, l:'a llist) : 'a llist =
     case (n, l) of
       (_, Elem(x)) => Elem(x)
     | (0, LList(_)) => raise Fail "This cutoff operation is not meaningful!"
     | (_, LList([])) => LList([])
     | (1, LList(xs)) => LList(List.filter
                             (fn x=>case x of Elem _ => true | _ => false) xs)
     | (_, LList(xs)) => LList(map (fn x=>cutOff(n-1,x)) xs)

end

signature PART3 = sig

   val match: string * string -> bool

end

structure Part3Sol :> PART3 = struct
   (* YOU MAY NOT CHANGE ANYTHING BEFORE THIS LINE *)

   (****************** PART 3 ******************)

   (* 8 *)
   fun match (regexp: string, tested: string): bool  =
   let
     fun helper (exp: char list, cnd: char list): bool =
       case (exp, cnd) of
         ([], []) => true
       | (rc::(#"*")::rt, []) => helper(rt,[])
       | (#"?"::rt, cc::ct) => helper(rt, ct)
       | (rc::(#"+")::rt, cc::ct)
           => (rc = cc) andalso helper(rc::(#"*")::rt, ct)
       | (rc::(#"*")::rt, cc::ct)
           => helper(rt, cnd) orelse (rc = cc andalso helper(exp, ct))
       | (rc::rt, cc::ct) => (rc = cc) andalso helper(rt, ct)
       | _ => false
   in
     helper(String.explode(regexp), String.explode(tested))
   end

end