\documentclass{article}
\usepackage{amssymb, amsmath, geometry, multicol, stmaryrd}
\usepackage{listings, xcolor}

\definecolor{red}{rgb}{0.8, 0.0, 0.0}
\definecolor{green}{rgb}{0.0, 0.8, 0.0}
\definecolor{blue}{rgb}{0.0, 0.0, 0.8}
\definecolor{orange}{rgb}{0.8, 0.5, 0.0}
\definecolor{lightgreen}{rgb}{0.6, 0.9, 0.6}

\lstloadlanguages{[Objective]Caml}
\lstdefinestyle{mystyle}{
    backgroundcolor=\color{white},
    commentstyle=\color{orange},
    keywordstyle=\color{blue},
    numberstyle=\tiny\color{blue},
    basicstyle=\footnotesize\ttfamily,             
    captionpos=b,
    numbers=none,
    numbersep=5pt,
    showspaces=false,
    showstringspaces=false,
    showtabs=false,
    tabsize=4
}
\lstset{style=mystyle,
        frameround=fttt,
        frame=trBL, 
        linewidth=15cm,
        aboveskip=5pt,
        belowskip=15pt,
        language=caml
}

\geometry{tmargin=.7in, bmargin=.75in, lmargin=.75in, rmargin = .75in}

\begin{document}
\setlength{\parindent}{0mm}

\title{OCaml - Tableaux}
\author{Aubin SIONVILLE}
\date{MPI Clemenceau - 2021-2023}
\maketitle

\section{Bases}

    \subsection{Premier zéro}

    Fonction calculant l'indice du premier zéro d'un tableau d'entiers avec une boucle \textbf{while}.

    \begin{lstlisting}
        let premier_zero (t: int array): int =
            let n = Array.length t in
            let i = ref 0 in
            while !i < n && t.(!i) <> 0 do
                incr i
            done;
            if !i = n then -1 else !i;;
    \end{lstlisting}

    Fonction calculant l'indice du premier zéro d'un tableau d'entiers avec une boucle \textbf{for} arrêtée par une exception.

    \begin{lstlisting}
        exception Zero of int;;
        let premier_zero (t: int array): int =
            let n = Array.length t in
            try
                for i = 0 to n - 1 do
                    if t.(i) = 0 then raise (Zero i)
                done; -1
            with Zero i -> i;;
    \end{lstlisting}

    \subsection*{Dernier zéro}

    Fonction calculant l'indice du dernier zéro d'un tableau d'entiers avec une boucle \textbf{while}.

    \begin{lstlisting}
        let dernier_zero (t: int array): int =
            let n = Array.length t in
            let i = ref (n - 1) in
            while !i >= 0 && t.(!i) <> 0 do
                decr i
            done;
            if !i = -1 then -1 else !i;;
    \end{lstlisting}

    \subsection*{Existence d'un zéro}

    Fonction testant l'existence d'un zéro dans un tableau d'entiers avec une boucle \textbf{while}, arrêtée dès que possible sans utiliser d'exception.

    \begin{lstlisting}
        let existe_zero (t: int array): bool =
            let res = ref false in
            let n = Array.length t in
            let i = ref 0 in
            while !i < n && not !res do
                if t.(!i) = 0 then res := true;
                incr i
            done;
            !res;;
    \end{lstlisting}

    Fonction testant l'existence d'un zéro dans un tableau d'entiers avec \textbf{Array.iter}, arrêtée par une exception.

    \begin{lstlisting}
        exception Zero

        let existe_zero (t: int array): bool =
            try 
                Array.iter (fun x -> if x = 0 then raise Zero) t;
                false
            with Zero -> true;;
    \end{lstlisting}

    \subsection*{Somme des éléments d'un tableau}

    Fonction calculant la somme des éléments d'un tableau d'entiers avec une boucle \textbf{for}.

    \begin{lstlisting}
        let somme (t: int array): int =
            let n = Array.length t in
            let s = ref 0 in
            for i = 0 to n - 1 do
                s := !s + t.(i)
            done;
            !s;;
    \end{lstlisting}

    Fonction calculant la somme des éléments d'un tableau d'entiers avec \textbf{Array.fold\_left}.

    \begin{lstlisting}
        let somme (t: int array): int =
            Array.fold_left (fun s x -> s + x) 0 t;;
    \end{lstlisting}

    \subsection*{Minimum et maximum}

    Fonction calculant l'indice du minimum d'un tableau d'entiers avec une boucle \textbf{for}. On lève une exception si le tableau est vide.

    \begin{lstlisting}
        let indice_min (t: int array): int =
            let n = Array.length t in
            if n = 0 then raise (Invalid_argument "indice_min");
            else
                let i_min = ref 0 in
                let v_min = ref t.(0) in
                for i = 1 to n - 1 do
                    if t.(i) < !v_min then
                    begin
                        i_min := i;
                        v_min := t.(i)
                    end
                done;
                !i_min;;
    \end{lstlisting}

    Fonction calculant l'indice du maximum d'un tableau d'entiers avec \textbf{Array.fold\_left}. On lève une exception si le tableau est vide.

    \begin{lstlisting}
        let indice_min (t: int array): int =
            let aux = (fun (i_max, v_max,i) ->
                if t.(i) > v_max then (i, t.(i), i + 1)
                else (i_max, v_max, i + 1))
            in let (i_max, _, _) = Array.fold_left aux (-1, -1, 0) t
            in i_max;;
    \end{lstlisting}

\newpage

    \subsection*{Sommes cumulées}

    Fonction prenant en argument un tableau d'entier $t$ et renvoyant le tableau des sommes cumulées de $t$.

    \begin{lstlisting}
        let cumul (t: int array): int array =
            let n = Array.length t in
            if n = 0 then [||]
            else begin
                let cumul = Array.make n t.(0) in
                for i = 1 to n - 1 do
                    cumul.(i) <- cumul.(i - 1) + t.(i)
                done;
                cumul
            end;;
    \end{lstlisting}

    \subsection*{Tableau de listes}

    Fonction prenant en argument un tableau de listes d'entiers $t$ et le modifiant en ajoutant à chaque liste l'indice de la liste dans le tableau.

    \begin{lstlisting}
        let ajoute_indice (t: int list array): unit =
            let n = Array.length t in
            for i = 0 to n - 1 do
                t.(i) <- i :: t.(i)
            done;;
    \end{lstlisting}

    Fonction prenant en argument un tableau de listes d'entiers $t$ et un entier $x$ et renvoyant un tableau de listes d'entiers obtenu en ajoutant $x$ en tête de chaque liste de $t$.\\
    On utilise \textbf{Array.map}.

    \begin{lstlisting}
        let ajoute_x (t: int list array) (x: int): int list array =
            Array.map (fun l -> x :: l) t;;
    \end{lstlisting}

    \subsection*{Element majoritaire}

    Fonction prenant en argument un entier $m$ et un tableau $t$ d'entiers entre $0$ et $m-1$ et renvoyant l'élément majoritaire de $t$.\\
    On n'utilise pas de boucle \textbf{for} ou \textbf{while} et on a une complexité en $O(n + m)$.

    \begin{lstlisting}
        let element_majoritaire (m: int) (t: int array): int =
            let tab_occurences = Array.make m 0 in
            Array.iter (fun x -> tab_occurences.(x) <- tab_occurences.(x) + 1) t;
            let aux = (fun (i_max, v_max, i) ->
                if x > v_max then (i, x, i + 1)
                else (i_max, v_max, i + 1))
            in let (i_max, _, _) = Array.fold_left aux (-1, -1, 0) tab_occurences
            in i_max;;
    \end{lstlisting}

\end{document}