La classe Deque

(PECL ds >= 1.0.0)

Introduction

Un Deque (prononcé “deck”) est une séquence de valeurs dans un tampon contigu qui grandit et rétrécit automatiquement. Le nom est une abréviation courante de “double-ended queue” et est utilisé en interne par Ds\Queue.

Deux pointeurs sont utilisés pour garder une trace d'une tête et d'une queue. Les pointeurs peuvent “enrouler” la fin du tampon, ce qui évite de déplacer d'autres valeurs pour faire de la place. Cela rend shift et unshift très rapides — quelque chose qu'un Ds\Vector ne peut pas concurrencer.

Accéder à une valeur par index nécessite une traduction entre l'index et sa position correspondante dans le tampon : ((head + position) % capacity).

Forces

Support de la syntaxe de tableau (crochets).
Utilise moins de mémoire globale qu'un tableau pour le même nombre de valeurs.
Libère automatiquement la mémoire allouée lorsque sa taille devient suffisamment faible.
get(), set(), push(), pop(), shift(), et unshift() sont tous de complexité O(1).

Faiblesses

La capacité doit être une puissance de 2.
insert() et remove() sont de complexité O(n).

Synopsis de la classe

class Ds\Deque implements Ds\Sequence, ArrayAccess {

/* Constantes */

const int MIN_CAPACITY = 8;

/* Méthodes */

public allocate(int $capacity): void

public apply(callable $callback): void

public capacity(): int

public clear(): void

public contains(mixed ...$values): bool

public copy(): Ds\Deque

public filter(callable $callback = ?): Ds\Deque

public find(mixed $value): mixed

public first(): mixed

public get(int $index): mixed

public insert(int $index, mixed ...$values): void

public isEmpty(): bool

public join(string $glue = ?): string

public last(): mixed

public map(callable $callback): Ds\Deque

public merge(mixed $values): Ds\Deque

public pop(): mixed

public push(mixed ...$values): void

public reduce(callable $callback, mixed $initial = ?): mixed

public remove(int $index): mixed

public reverse(): void

public reversed(): Ds\Deque

public rotate(int $rotations): void

public set(int $index, mixed $value): void

public shift(): mixed

public slice(int $index, int $length = ?): Ds\Deque

public sort(callable $comparator = ?): void

public sorted(callable $comparator = ?): Ds\Deque

public sum(): int|float

public toArray(): array

public unshift(mixed $values = ?): void

}

Constantes pré-définies

Ds\Deque::MIN_CAPACITY

Historique

Version Description

PECL ds 1.3.0 La classe implémente maintenant ArrayAccess.

Version	Description
PECL ds 1.3.0	La classe implémente maintenant ArrayAccess.

Sommaire

Ds\Deque::allocate — Alloue suffisamment de mémoire pour une capacité requise
Ds\Deque::apply — Met à jour toutes les valeurs en appliquant une fonction de rappel à chaque valeur
Ds\Deque::capacity — Renvoie la capacité actuelle
Ds\Deque::clear — Supprime toutes les valeurs du deque
Ds\Deque::__construct — Crée une nouvelle instance
Ds\Deque::contains — Détermine si le deque contient des valeurs données
Ds\Deque::copy — Renvoie une copie superficielle de la deque
Ds\Deque::count — Renvoie le nombre de valeurs dans la collection
Ds\Deque::filter — Créer un nouveau deque en utilisant un callable pour déterminer quelles valeurs inclure
Ds\Deque::find — Essaye de trouver l'index d'une valeur
Ds\Deque::first — Renvoie la première valeur de la deque
Ds\Deque::get — Renvoie la valeur à un index donné
Ds\Deque::insert — Insère des valeurs à un index donné
Ds\Deque::isEmpty — Renvoie si la deque est vide
Ds\Deque::join — Rassemble toutes les valeurs en une chaîne
Ds\Deque::jsonSerialize — Renvoie une représentation qui peut être convertie en JSON
Ds\Deque::last — Renvoie la dernière valeur
Ds\Deque::map — Renvoie le résultat de l'application d'une fonction de rappel à chaque valeur
Ds\Deque::merge — Renvoie le résultat de l'ajout de toutes les valeurs données au deque
Ds\Deque::pop — Enlève et renvoie la dernière valeur
Ds\Deque::push — Ajoute des valeurs à la fin du deque
Ds\Deque::reduce — Réduit le deque à une seule valeur en utilisant une fonction de rappel
Ds\Deque::remove — Enlève et renvoie une valeur par index
Ds\Deque::reverse — Renverse le deque en place
Ds\Deque::reversed — Renvoie une copie renversée
Ds\Deque::rotate — Tourne le deque d'un certain nombre de rotations
Ds\Deque::set — Met à jour une valeur à un index donné
Ds\Deque::shift — Enlève et renvoie la première valeur
Ds\Deque::slice — Renvoie un sous-deque d'une plage donnée
Ds\Deque::sort — Trie le deque en place
Ds\Deque::sorted — Renvoie une copie triée
Ds\Deque::sum — Renvoie la somme de toutes les valeurs du deque
Ds\Deque::toArray — Convertit le deque en un tableau
Ds\Deque::unshift — Ajoute des valeurs au début du deque