imperatywne

open Array;;
(*Zadanie 2*)
let cykl tab =
  let n = length tab in
  let odw = make n 0
  and akt = ref 0
  and best = ref 0 in begin
  for i = 0 to (n - 1) do
    akt := 0;
    let j = ref i in
    while odw.(!j) = 0 do
      odw.(!j) <- 1;
      akt := !akt + 1;
      if !akt > !best then best := !akt;
      j := tab.(!j)
    done
  done; !best end
;;

(*Zadanie 4*)
let nawiasy tab =
  let n = length tab
  and p = ref 0
  and k = ref 0
  and cnt = ref 0
  and best = ref 0 in
  begin
    while !k < n do
      if tab.(!k) = '(' then
        begin
          cnt := !cnt + 1;
          k := !k + 1;
        end
      else
        begin
          cnt := !cnt - 1;
          k := !k + 1;
          if !cnt < 0 then
            begin
              cnt := 0;
              p := !k;
            end
          else
            begin
              if !k - !p - !cnt > !best then
                begin
                  best := !k - !p - !cnt
                end
            end
        end
    done;
    !best
  end
;;

let test1 = [|'(';'(';'(';')'|];;
let test2 = [|')';')';')'|];;
let test3 = [|'(';'(';')';')'|];;
let test4 = [|'(';'(';'(';')';')';')';')';'(';'(';'(';')'|];;

type 'a tree =
  Node of 'a * 'a * 'a tree * 'a tree ref |
  Null
;;

(*Zadanie 6*)
let diag a b = Float.sqrt (a *. a +. b *. b);;

(*czas: log(n)*)
let diagonal a b =
  let n = length a in
  let l = ref 0
  and r = ref n
  and m = ref 0
  and w = ref 0. in
  begin
    while !l < !r do
      m := (!l + !r)/2;
      if (a.(!m) -. b.(!m)) < 0. then begin l := !m + 1 end
      else begin r := !m end
    done;
    if !l > 0 then begin
      w := (min (diag a.(!l) b.(!l)) (diag a.(!l - 1) b.(!l - 1)));
    end
    else begin w := (diag a.(!l) b.(!l)) end;
    !w
  end
;;

let test1a = [|1.;2.;4.;5.;20.;25.;50.;|];;
let test1b = [|100.;50.;25.;20.;5.;4.;2.;|];;

(*Zadanie 10*)
(*złożoność czasowa O(n), złożoność pamięciowa O(1)*)
let rotacja tab k =
  let temp = ref '1'
  and n = length tab in
  let k = k mod (n - 1)
  and reverse a b =
    begin
      for i = 0 to (b - a)/2 do
        temp := tab.(a + i);
        tab.(a + i) <- tab.(b - i);
        tab.(b - i) <- !temp
      done
    end in
  begin
    reverse 0 (n - k - 1);
    reverse (n - k) (n - 1);
    reverse 0 (n - 1)
  end
;;

let testchar = [|'a'; 'l'; 'a'; 'm'; 'a'; 'k'; 'o'; 't';  'a'|];;

(*Zadanie 13*)
let blisko_zera tab =
  let n = length tab
  and l = ref 0
  and r = ref 0
  and m = ref 0
  and w = ref 0 in
  begin
    if (tab.(0) < tab.(n - 1)) then begin
      l := 0;
      r := n;
      while !l < !r do
        m := (!l + !r)/2;
        if tab.(!m) < 0 then begin
          l := !m + 1
        end else begin
          r := !m
        end
      done;
      if !l > 0 then begin
        w := min (abs tab.(!l)) (abs tab.(!l - 1))
      end else begin
        w := abs tab.(!l)
      end
    end else begin
      l := 0;
      r := n;
      while !l < !r do
        m := (!l + !r)/2;
        if tab.(!m) <= 0 then begin
          r := !m
        end else begin
          l := !m + 1
        end
      done;
      if !r = 0 then begin
        w := abs tab.(!r)
      end else begin
        w := min (abs tab.(!r - 1)) (abs tab.(!r))
      end
    end;
    !w
  end
;;