type 'a ind = int

type ('a, 'b) t = {
    mutable data : 'b array ;
    mutable length : int;
    step : int;
  } ;;

let create ?(step=256) () = { data = [| |] ; length = 0 ; step = step};;

let check_bound t i =
  if i >= t.length then raise (Invalid_argument "index out of bounds");;



(** Add a new element to the array and return its id. *)


let add a v =
  let len = Array.length a.data in
  if a.length < len then
    (
     a.data.(a.length) <- v ;
     a.length <- a.length + 1
    )
  else
    (
     (* we must increase the array's size *)
     let t = Array.create a.step v in
     a.data <- Array.append a.data t;
     a.length <- a.length + 1;
    );
  a.length - 1
;;


let get a i = check_bound a i; a.data.(i);;
let set a i v = check_bound a i; a.data.(i) <- v;;

let find a pred =
  let rec iter i =
    if i >= a.length then
      raise Not_found
    else
      if pred a.data.(i) = 0 then
        i
      else
        iter (i + 1)
  in
  iter 0
;;

let copy ?(copy=(fun x -> x)) a =
  { data = Array.map copy a.data; length = a.length; step = a.step } ;;

let length a = a.length;;
let iteri f a = for i = 0 to a.length - 1 do f i a.data.(i) done ;;
let iter f a = for i = 0 to a.length - 1 do f a.data.(i) done;;
let fold_left f a b = Array.fold_left f a (Array.sub b.data 0 b.length);;
let fold_right f a b = Array.fold_right f (Array.sub a.data 0 a.length) b;;
let fold_lefti f a b =
  let len = length b in
  let rec iter acc i =
    if i < len then
      iter (f acc i (get b i)) (i+1)
    else
      acc
  in
  iter a 0
;;

let fold_righti f a b =
  let len = length a in
  let rec iter acc i =
    if i >= 0 then
      iter (f i (get a i) acc) (i-1)
    else
      acc
  in
  iter b (len - 1)
;;


let to_array a = Array.copy (Array.sub a.data 0 a.length);;
let mapi f a =
  { data = Array.mapi f (Array.sub a.data 0 a.length);
    length = a.length ;
    step = a.step ;
  };;
let mapi_as_list f a = Array.to_list (Array.mapi f (Array.sub a.data 0 a.length));;
let insert a pos v =
  let len = a.length in
  if pos > len then raise (Invalid_argument "Index too big to insert in this ext_array");
  if pos = len then
    ignore(add a v)
  else
    (
     let a1 = Array.sub a.data 0 pos in
     let a2 = Array.sub a.data pos (len - pos) in
     a.data <- Array.concat [ a1 ; [| v |]; a2]
    )
;;

let int ind = ind;;
let (~~) = int;;
let (@@) = get;;
let (@>) t n = n;;
let (@~) t n = get t (t @> n);;