The Deque class

(No version information available, might only be in Git)

Introduction

A Deque (pronounced “deck”) is a sequence of values in a contiguous buffer that grows and shrinks automatically. The name is a common abbreviation of “double-ended queue” and is used internally by Ds\Queue.

Two pointers are used to keep track of a head and a tail. The pointers can “wrap around” the end of the buffer, which avoids the need to move other values around to make room. This makes shift and unshift very fast — something a Ds\Vector can’t compete with.

Accessing a value by index requires a translation between the index and its corresponding position in the buffer: ((head + position) % capacity).

Retour à la première page de Manuel PHP Table des matières Haut

Strengths

Supports array syntax (square brackets).
Uses less overall memory than an tableau for the same number of values.
Automatically frees allocated memory when its size drops low enough.
get(), set(), push(), pop(), shift(), and unshift() are all O(1).

Retour à la première page de Manuel PHP Table des matières Haut

Weaknesses

Capacity must be a power of 2.
insert() and remove() are O(n).

Retour à la première page de Manuel PHP Table des matières Haut

Synopsis de la classe

Ds\Deque implements Ds\Sequence {

/* Constants */

const int MIN_CAPACITY = 8 ;

/* Méthodes */

public allocate ( int $capacity ) : void

public apply ( callable $callback ) : void

public capacity ( void ) : int

public clear ( void ) : void

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

public copy ( void ) : Ds\Deque

public filter ([ callable $callback ] ) : Ds\Deque

public find ( mixed $value ) : mixed

public first ( void ) : mixed

public get ( int $index ) : mixed

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

public isEmpty ( void ) : bool

public join ([ string $glue ] ) : string

public last ( void ) : mixed

public map ( callable $callback ) : Ds\Deque

public merge ( mixed $values ) : Ds\Deque

public pop ( void ) : mixed

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

public reduce ( callable $callback [, mixed $initial ] ) : mixed

public remove ( int $index ) : mixed

public reverse ( void ) : void

public reversed ( void ) : Ds\Deque

public rotate ( int $rotations ) : void

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

public shift ( void ) : mixed

public slice ( int $index [, int $length ] ) : Ds\Deque

public sort ([ callable $comparator ] ) : void

public sorted ([ callable $comparator ] ) : Ds\Deque

public sum ( void ) : number

public toArray ( void ) : array

public unshift ([ mixed $values ] ) : void

}

Retour à la première page de Manuel PHP Table des matières Haut

Constantes pré-définies

Ds\Deque::MIN_CAPACITY

Retour à la première page de Manuel PHP Table des matières Haut

Sommaire

Ds\Deque::allocate — Allocates enough memory for a required capacity
Ds\Deque::apply — Updates all values by applying a callback function to each value
Ds\Deque::capacity — Returns the current capacity
Ds\Deque::clear — Removes all values from the deque
Ds\Deque::__construct — Creates a new instance
Ds\Deque::contains — Determines if the deque contains given values
Ds\Deque::copy — Returns a shallow copy of the deque
Ds\Deque::count — Returns the number of values in the collection
Ds\Deque::filter — Creates a new deque using a callable to determine which values to include
Ds\Deque::find — Attempts to find a value's index
Ds\Deque::first — Returns the first value in the deque
Ds\Deque::get — Returns the value at a given index
Ds\Deque::insert — Inserts values at a given index
Ds\Deque::isEmpty — Returns whether the deque is empty
Ds\Deque::join — Joins all values together as a string
Ds\Deque::jsonSerialize — Returns a representation that can be converted to JSON
Ds\Deque::last — Returns the last value
Ds\Deque::map — Returns the result of applying a callback to each value
Ds\Deque::merge — Returns the result of adding all given values to the deque
Ds\Deque::pop — Removes and returns the last value
Ds\Deque::push — Adds values to the end of the deque
Ds\Deque::reduce — Reduces the deque to a single value using a callback function
Ds\Deque::remove — Removes and returns a value by index
Ds\Deque::reverse — Reverses the deque in-place
Ds\Deque::reversed — Returns a reversed copy
Ds\Deque::rotate — Rotates the deque by a given number of rotations
Ds\Deque::set — Updates a value at a given index
Ds\Deque::shift — Removes and returns the first value
Ds\Deque::slice — Returns a sub-deque of a given range
Ds\Deque::sort — Sorts the deque in-place
Ds\Deque::sorted — Returns a sorted copy
Ds\Deque::sum — Returns the sum of all values in the deque
Ds\Deque::toArray — Converts the deque to an tableau
Ds\Deque::unshift — Adds values to the front of the deque

Rechercher une fonction PHP

Version en cache

22/12/2024 23:20:00 Cette version de la page est en cache (à la date du 22/12/2024 23:20:00) afin d'accélérer le traitement. Vous pouvez activer le mode utilisateur dans le menu en haut pour afficher la dernère version de la page.

Document créé le 30/01/2003, dernière modification le 26/10/2018
Source du document imprimé : https://www.gaudry.be/php-rf-class.ds-deque.html

L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.

Références

Manuel PHP : http://php.net

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

Table des matières Haut