Discussion :

[Tony310]

Bonjour

Je n'arrive pas � surcharger proprement une fonction r�cursive, qui peut prendre en argument un Array ou un Typed Array, et une fonction de comparaison.

Typiquement il s'agit de l'algorithme Floyd-Rivest (les d�tails d'impl�mentation importent peu, l'algo fonctionne tr�s bien avec un typage faible, je voulais juste d�finir des signatures propres).

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
function swap(
  array: any[] | Int8Array | Uint8Array | Uint8ClampedArray | Int16Array |
         Uint16Array | Int32Array | Uint32Array | Float32Array | Float64Array,
  idx1: number,
  idx2: number,
): void {
  const tmp = array[idx1];
  array[idx1] = array[idx2];
  array[idx2] = tmp;
}
 
function select(
  array: Int8Array | Uint8Array | Uint8ClampedArray | Int16Array |
         Uint16Array | Int32Array | Uint32Array | Float32Array | Float64Array,
  first: number,
  nth: number,
  last: number,
  comp: (a: number, b: number) => boolean,
): void;
function select<T>(
  array: T[],
  first: number,
  nth: number,
  last: number,
  comp: (a: T, b: T) => boolean,
): void;
function select<T>(
  array: Int8Array | Uint8Array | Uint8ClampedArray | Int16Array |
         Uint16Array | Int32Array | Uint32Array | Float32Array | Float64Array |
         T[],
  first: number,
  nth: number,
  last: number,
  comp: (a: number | T, b: number | T) => boolean,
): void {
  --last;
  while (first < last) {
    if (last - first > 600) {
      const n = last - first + 1;
      const m = nth - first + 1;
      const z = Math.log(n);
      const s = 0.5 * Math.exp(2 * z / 3);
      const sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);
      const newFirst = Math.max(first, Math.floor(nth - m * s / n + sd));
      const newLast = Math.min(last, Math.floor(nth + (n - m) * s / n + sd));
      select(array, newFirst, nth, newLast, comp);
    }
 
    const t = array[nth];
    let i = first;
    let j = last;
 
    swap(array, first, nth);
    if (comp(t, array[last])) swap(array, first, last);
 
    while (i < j) {
      swap(array, i++, j--);
      while (comp(array[i], t)) ++i;
      while (comp(t, array[j])) --j;
    }
 
    if (!comp(array[first], t)) {
      swap(array, first, j);
    } else {
      swap(array, ++j, last);
    }
 
    if (j <= nth) first = j + 1;
    if (nth <= j) last = j - 1;
  }
}

Il me sort l'erreur suivante pour l'argument array lors de l'appel r�cursif dans l'impl�mentation de la fonction (ligne 46) :

[ts]
L'argument de type 'Int8Array | Uint8Array | Uint8ClampedArray | Int16Array | Uint16Array | Int32Array | Uint32Array | Float32Array | Float64Array | T[]' n'est pas attribuable au param�tre de type '(number | T)[]'.
Impossible d'assigner le type 'Int8Array' au type '(number | T)[]'.
La propri�t� 'pop' est manquante dans le type 'Int8Array'. [2345]

Je comprends le message, mais je ne vois pas trop bien comment contourner le pb.

Auriez vous une id�e de la mani�re de d�finir proprement les signatures de la fonction, tout en gardant un typage fort?

Des quelques modifs que j'ai pu tenter, il n'appr�cie pas trop le fait d'avoir une surcharge sans <> juste apr�s le nom de la fonction (� la ligne 12). Pourtant, avec des fonctions non r�cursives cela ne pose aucun probl�me.

[Tony310]

Mmmhh, en fait un point m'avait �chapp�, la signature de l'impl�mentation peut �tre la plus g�n�rale possible puisqu'elle n'est pas reconnue dans le cas de surcharges.

Du coup ceci fonctionne :

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function select(
  array: Int8Array | Uint8Array | Uint8ClampedArray | Int16Array |
         Uint16Array | Int32Array | Uint32Array | Float32Array | Float64Array,
  first: number,
  nth: number,
  last: number,
  comp: (a: number, b: number) => boolean,
): void;
function select<T>(
  array: T[],
  first: number,
  nth: number,
  last: number,
  comp: (a: T, b: T) => boolean,
): void;
function select(
  array: any,
  first: number,
  nth: number,
  last: number,
  comp: (a: any, b: any) => boolean,
): void {
  // Implementation
}

Par contre, on ne b�n�ficie plus de typage dans l'impl�mentation (si on appelle la fonction par contre c'est bon), il y a peut �tre plus propre?