{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4729fb96",
   "metadata": {},
   "source": [
    "# Algorithmes sur les tableaux\n",
    "\n",
    "Le module `utils`, founi avec les notebooks, définit le type `IntArray`, ainsi que des fonctions de manipulation des tableaux."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "85e0de92",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b76f952",
   "metadata": {},
   "source": [
    "## Recherche du maximum\n",
    "\n",
    "Recherche la plus grande valeur du tableau d'entiers `t`\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers\n",
    "- **POSTCOND:** retourne `None` si `t` est vide, sinon `x` tel que `x` est la plus grande valeur qui appartient à `t`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "61e1b734",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findMax(t: IntArray) -> int | None:\n",
    "    if t.size == 0:\n",
    "        return None\n",
    "    max: int = t[0]\n",
    "    for i in range(1, t.size):\n",
    "        if t[i] > max:\n",
    "            max = t[i]\n",
    "    return max"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c4d8e08",
   "metadata": {},
   "source": [
    "## Somme des valeurs d'un tableau\n",
    "\n",
    "Somme des éléments d'un tableau d'entiers\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers\n",
    "- **POSTCOND:** `sumArray` retourne la somme des entiers dans `t`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "3f977ca4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sumArray(t: IntArray) -> int:\n",
    "    s = 0\n",
    "    for i in range(t.size):\n",
    "        s = s + t[i]\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb631f35",
   "metadata": {},
   "source": [
    "## Produit scalaire\n",
    "\n",
    "Produit scalaire de deux tableaux d'entiers\n",
    "\n",
    "- **PRECOND:** `t1` et `t2` sont deux tableaux d'entiers de même taille\n",
    "- **POSTCOND:** `scalarProduct` retourne le produit scalaire de `t1` et `t2`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "7bfc4fac",
   "metadata": {},
   "outputs": [],
   "source": [
    "def scalarProduct(t1: IntArray, t2: IntArray) -> int:\n",
    "    assert t1.size == t2.size\n",
    "    p = 0\n",
    "    for i in range(t1.size):\n",
    "        p = p + t1[i] * t2[i]\n",
    "    return p"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7e81f2f",
   "metadata": {},
   "source": [
    "## Nombre d'occurrences d'une valeur\n",
    "\n",
    "Compte les occurrences de `x` dans `t`\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers, et `x` est un entier\n",
    "- **POSTCOND:** `countArray` retourne le nombre d'occurrences de `x` dans `t`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "c2b543f1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def countArray(t: IntArray, x: int) -> int:\n",
    "    count = 0\n",
    "    for i in range(t):\n",
    "        if t[i] == x:\n",
    "            count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "953c7893",
   "metadata": {},
   "source": [
    "## Fréquences\n",
    "\n",
    "Calcule la fonction de fréquence des valeurs d'un tableau `t`\n",
    "\n",
    "- **PRECOND:** `t` est un tableau d'entiers **positifs ou nuls**\n",
    "- **POSTCOND:** `freqArray` retourne un tableau d'entiers tel que `t[i]` est la fréquence de `i` dans `t`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "2d448e86",
   "metadata": {},
   "outputs": [],
   "source": [
    "def freqArray(t: IntArray) -> IntArray:\n",
    "    freq = newIntArray(max(t) + 1)\n",
    "    for i in range(t.size):\n",
    "        freq[t[i]] += 1\n",
    "    return freq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ca4a7004",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction freqArray\n",
    "\n",
    "t = newRandomIntArray(20, 0, 20)\n",
    "freq = freqArray(t)\n",
    "print(t)\n",
    "print(freq)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ddbbf58d",
   "metadata": {},
   "source": [
    "## Égalité de tableaux\n",
    "\n",
    "Décider si deux tableaux `t1` et `t2` contiennent les mêmes valeurs, aux mêmes indices\n",
    "\n",
    "- **PRECOND:** `t1` et `t2` sont deux tableaux d'entiers\n",
    "- **POSTCOND:** `equalArray` retourne la première position où `t1` et `t2` diffèrent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "191528f1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def equalArray(t1: IntArray, t2: IntArray) -> bool:\n",
    "    \"\"\" Returns True if t1 and t2 have same size and elements, False otherwise \"\"\"\n",
    "    if t1.size != t2.size:\n",
    "        return False\n",
    "    for i in range(t1.size):\n",
    "        if t1[i] != t2[i]:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "31904ff2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction eqArray\n",
    "\n",
    "t1 = newExplicitIntArray([1, 2, 3, 4, 5])\n",
    "t2 = newExplicitIntArray([1, 2, 3])\n",
    "t3 = newExplicitIntArray([1, 2, 3])\n",
    "\n",
    "assert equalArray(t1, t1)\n",
    "assert equalArray(t2, t2)\n",
    "assert not equalArray(t1, t2)\n",
    "assert equalArray(t2, t3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0f59711",
   "metadata": {},
   "source": [
    "## Égalité de tableaux à rotation près\n",
    "\n",
    "Décider si deux tableaux `t1` et `t2` sont égaux à rotation `d` près, plus précisément, si `t2` est égal `t1` auquel on aurait appliqué une roation `d`\n",
    "\n",
    "- **PRECOND:** `t1` et `t2` sont deux tableaux d'entiers, et `d` est un entier\n",
    "- **POSTCOND:** `equalRotArray` retourne `True` si `t1` et `t2` sont égaux à rotation `d` près, `False` sinon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "ccd37946",
   "metadata": {},
   "outputs": [],
   "source": [
    "def equalRotArray(t1: IntArray, t2: IntArray, d: int) -> bool:\n",
    "    if t1.size != t2.size:\n",
    "        return False\n",
    "    for i in range(t1.size):\n",
    "        if t1[i] != t2[(i+d) % t2.size]:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "01d1d4e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction eqRotArray\n",
    "\n",
    "t1 = newExplicitIntArray([1, 2, 3, 4, 5])\n",
    "t2 = newExplicitIntArray([4, 5, 1, 2, 3])\n",
    "\n",
    "assert equalRotArray(t1, t1, 0)\n",
    "assert not equalRotArray(t1, t1, 2)\n",
    "assert not equalRotArray(t1, t2, 1)\n",
    "assert equalRotArray(t1, t2, 2)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "defaultInterpreterPath: 3.14.7.final.0",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.14.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}