(*

 * ExtLib Testing Suite

 * Copyright (C) 2004 Janne Hellsten

 * Copyright (C) 2008 Red Hat, Inc.

 * Copyright (C) 2010 ygrek

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version,

 * with the special exception on linking described in file LICENSE.

 *

 * This library is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with this library; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 *)

(* Standard library list *)

module StdList = List

open ExtList

exception Test_Exception

let check_empty_list_exn f = 

  try f (); false with List.Empty_list -> true

(** Random length list with [0;1;2;..n] contents. *)

let rnd_list () = 

  let len = Random.int 3 in 

  List.init len Std.identity

let test_iteri () = 

  for i = 0 to 15 do

    List.iteri (fun i e -> assert (i = e)) (rnd_list ());

  done

let test_mapi () =

  for i = 0 to 15 do

    let rnd_list = rnd_list () in

    let lst = List.mapi (fun n e -> (e,"foo")) rnd_list in

    let lst' = 

      List.mapi (fun n (e,s) -> assert (s = "foo"); assert (n = e); n) lst in

    List.iteri (fun i e -> assert (i = e)) lst'

  done

let test_exceptions () = 

  assert (check_empty_list_exn (fun () -> List.hd []));

  assert (check_empty_list_exn (fun () -> List.first []));

  assert (check_empty_list_exn (fun () -> List.last []))

let test_find_exc () =

  let check_exn f = try f (); false with Test_Exception -> true | _ -> false in

  assert (check_exn (fun () -> (List.find_exc (fun _ -> true) Test_Exception [])));

  try 

    for i = 0 to 15 do

      let rnd_lst = rnd_list () in

      begin 

        match rnd_lst with

          [] -> ()

        | lst -> 

            let rnd_elem = Random.int (List.length lst) in

            assert (check_exn 

                      (fun () -> 

                         List.find_exc (fun e -> e = List.length lst) Test_Exception lst));

            assert (not (check_exn 

                           (fun () -> 

                              List.find_exc (fun e -> e = rnd_elem) Test_Exception lst)))

      end

    done

  with _ -> assert false

let test_findi () =

  let check_fn f = try (let e,i = f () in e<>i) with Not_found -> true in

  try 

    for i = 0 to 15 do

      let rnd_lst = rnd_list () in

      begin 

        match rnd_lst with

          [] -> ()

        | lst -> 

            let rnd_elem = Random.int (List.length lst) in

            assert (check_fn 

                      (fun () -> 

                         List.findi (fun i e -> e = List.length lst) lst));

            assert (not (check_fn 

                           (fun () -> 

                              List.findi (fun i e -> e = rnd_elem) lst)))

      end

    done

  with _ -> assert false

let test_fold_right () = 

  let maxlen = 2000 in

  (* NOTE assuming we will not blow the stack with 2000 elements *)

  let lst = List.init maxlen Std.identity in

  let a = StdList.fold_right (fun e a -> e::a) lst [] in

  let b = List.fold_right (fun e a -> e::a) lst [] in

  assert (a = b)

let test_fold_right2 () = 

  let len = 2000 in

  let cnt = ref 0 in

  let lst = List.init len Std.identity in

  ignore (StdList.fold_right (fun e a -> incr cnt; e::a) lst []);

  let cnt_std = !cnt in

  cnt := 0;

  ignore (List.fold_right (fun e a -> incr cnt; e::a) lst []);

  assert (cnt_std = len);

  assert (!cnt = cnt_std)

let test_map () = 

  for i = 0 to 10 do

    let f = ( * ) 2 in

    let lst = rnd_list () in

    let a = StdList.map f lst in

    let b = List.map f lst in

    assert (a = b)

  done

let test_find_map () =

  let f = function "this", v -> Some v | _ -> None in

  (try

     let r = List.find_map f [ "a", 1; "b", 2; "this", 3; "d", 4 ] in

     assert (3 = r);

     let r = List.find_map f [ "this", 1; "b", 2; "c", 3; "d", 4 ] in

     assert (1 = r);

     let r = List.find_map f [ "a", 1; "b", 2; "c", 3; "this", 4 ] in

     assert (4 = r);

     let r = List.find_map f [ "this", 1; "b", 2; "c", 3; "this", 4 ] in

     assert (1 = r);

     let r = List.find_map f [ "a", 1; "b", 2; "this", 3; "this", 4 ] in

     assert (3 = r);

     let r = List.find_map f [ "this", 5 ] in

     assert (5 = r)

   with

     Not_found -> assert false

  );

  (try

     ignore (List.find_map f []); assert false

   with

     Not_found -> ()

  );

  (try

     ignore (List.find_map f [ "a", 1 ]); assert false

   with

     Not_found -> ()

  );

  (try

     ignore (List.find_map f [ "a", 1; "b", 2 ]); assert false

   with

     Not_found -> ()

  )

(* Issue 12: List.make not tail-recursive *)

let test_make () =

  let l = List.make 10_000_000 1 in

  assert (List.length l = 10_000_000)

let () =

  Util.register "ExtList" [

    "iteri", test_iteri;

    "mapi", test_mapi;

    "exceptions", test_exceptions;

    "find_exc", test_find_exc;

    "findi", test_findi;

    "fold_right", test_fold_right;

    "fold_right2", test_fold_right2;

    "map", test_map;

    "find_map", test_find_map;

    "make", test_make;

  ]