<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html> <head> <meta http-equiv="content-type" content="text/html; charset=UTF-8"> <title>The Deque class</title> </head> <body><div class="manualnavbar" style="text-align: center;"> <div class="prev" style="text-align: left; float: left;"><a href="ds-vector.unshift.html">Ds\Vector::unshift</a></div> <div class="next" style="text-align: right; float: right;"><a href="ds-deque.allocate.html">Ds\Deque::allocate</a></div> <div class="up"><a href="book.ds.html">Data Structures</a></div> <div class="home"><a href="index.html">PHP Manual</a></div> </div><hr /><div id="class.ds-deque" class="reference"> <h1 class="title">The Deque class</h1> <div class="partintro"><p class="verinfo">(No version information available, might only be in Git)</p> <div class="section" id="ds-deque.intro"> <h2 class="title">Introduction</h2> <p class="para"> 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 <strong class="classname">Ds\Queue</strong>. </p> <p class="para"> 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 <strong class="classname">Ds\Vector</strong> can’t compete with. </p> <p class="para"> Accessing a value by index requires a translation between the index and its corresponding position in the buffer: <code class="code">((head + position) % capacity)</code>. </p> </div> <div class="section" id="ds-deque.strengths"> <h2 class="title">Strengths</h2> <p class="para"> <ul class="simplelist"> <li class="member">Supports array syntax (square brackets).</li> <li class="member">Uses less overall memory than an <span class="type"><a href="language.types.array.html" class="type array">array</a></span> for the same number of values.</li> <li class="member">Automatically frees allocated memory when its size drops low enough.</li> <li class="member"> <span class="function"><strong>get()</strong></span>, <span class="function"><strong>set()</strong></span>, <span class="function"><strong>push()</strong></span>, <span class="function"><strong>pop()</strong></span>, <span class="function"><strong>shift()</strong></span>, and <span class="function"><strong>unshift()</strong></span> are all O(1). </li> </ul> </p> </div> <div class="section" id="ds-deque.weaknesses"> <h2 class="title">Weaknesses</h2> <p class="para"> <ul class="simplelist"> <li class="member">Capacity must be a power of 2.</li> <li class="member"> <span class="function"><strong>insert()</strong></span> and <span class="function"><strong>remove()</strong></span> are O(n). </li> </ul> </p> </div> <div class="section" id="ds-deque.synopsis"> <h2 class="title">Class synopsis</h2> <div class="classsynopsis"> <div class="ooclass"></div> <div class="classsynopsisinfo"> <span class="ooclass"> <strong class="classname">Ds\Deque</strong> </span> <span class="oointerface">implements <span class="interfacename"><strong class="interfacename">Ds\Sequence</strong></span> </span> {</div> <div class="classsynopsisinfo classsynopsisinfo_comment">/* Constants */</div> <div class="fieldsynopsis"> <span class="modifier">const</span> <span class="type">int</span> <var class="fieldsynopsis_varname"><a href="class.ds-deque.html#ds-deque.constants.min-capacity"><var class="varname">MIN_CAPACITY</var></a></var> <span class="initializer"> = 8</span> ;</div> <div class="classsynopsisinfo classsynopsisinfo_comment">/* Methods */</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">void</span> <span class="methodname"><a href="ds-deque.allocate.html" class="methodname">allocate</a></span> ( <span class="methodparam"><span class="type">int</span> <code class="parameter">$capacity</code></span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">void</span> <span class="methodname"><a href="ds-deque.apply.html" class="methodname">apply</a></span> ( <span class="methodparam"><span class="type"><a href="language.types.callable.html" class="type callable">callable</a></span> <code class="parameter">$callback</code></span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">int</span> <span class="methodname"><a href="ds-deque.capacity.html" class="methodname">capacity</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">void</span> <span class="methodname"><a href="ds-deque.clear.html" class="methodname">clear</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">bool</span> <span class="methodname"><a href="ds-deque.contains.html" class="methodname">contains</a></span> ([ <span class="methodparam"><span class="type"><a href="language.pseudo-types.html#language.types.mixed" class="type mixed">mixed</a></span> <code class="parameter">$...values</code></span> ] )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">Ds\Deque</span> <span class="methodname"><a href="ds-deque.copy.html" class="methodname">copy</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">Ds\Deque</span> <span class="methodname"><a href="ds-deque.filter.html" class="methodname">filter</a></span> ([ <span class="methodparam"><span class="type"><a href="language.types.callable.html" class="type callable">callable</a></span> <code class="parameter">$callback</code></span> ] )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">mixed</span> <span class="methodname"><a href="ds-deque.find.html" class="methodname">find</a></span> ( <span class="methodparam"><span class="type"><a href="language.pseudo-types.html#language.types.mixed" class="type mixed">mixed</a></span> <code class="parameter">$value</code></span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">mixed</span> <span class="methodname"><a href="ds-deque.first.html" class="methodname">first</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">mixed</span> <span class="methodname"><a href="ds-deque.get.html" class="methodname">get</a></span> ( <span class="methodparam"><span class="type">int</span> <code class="parameter">$index</code></span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">void</span> <span class="methodname"><a href="ds-deque.insert.html" class="methodname">insert</a></span> ( <span class="methodparam"><span class="type">int</span> <code class="parameter">$index</code></span> [, <span class="methodparam"><span class="type"><a href="language.pseudo-types.html#language.types.mixed" class="type mixed">mixed</a></span> <code class="parameter">$...values</code></span> ] )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">bool</span> <span class="methodname"><a href="ds-deque.isempty.html" class="methodname">isEmpty</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">string</span> <span class="methodname"><a href="ds-deque.join.html" class="methodname">join</a></span> ([ <span class="methodparam"><span class="type">string</span> <code class="parameter">$glue</code></span> ] )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">mixed</span> <span class="methodname"><a href="ds-deque.last.html" class="methodname">last</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">Ds\Deque</span> <span class="methodname"><a href="ds-deque.map.html" class="methodname">map</a></span> ( <span class="methodparam"><span class="type"><a href="language.types.callable.html" class="type callable">callable</a></span> <code class="parameter">$callback</code></span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">Ds\Deque</span> <span class="methodname"><a href="ds-deque.merge.html" class="methodname">merge</a></span> ( <span class="methodparam"><span class="type"><a href="language.pseudo-types.html#language.types.mixed" class="type mixed">mixed</a></span> <code class="parameter">$values</code></span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">mixed</span> <span class="methodname"><a href="ds-deque.pop.html" class="methodname">pop</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">void</span> <span class="methodname"><a href="ds-deque.push.html" class="methodname">push</a></span> ([ <span class="methodparam"><span class="type"><a href="language.pseudo-types.html#language.types.mixed" class="type mixed">mixed</a></span> <code class="parameter">$...values</code></span> ] )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">mixed</span> <span class="methodname"><a href="ds-deque.reduce.html" class="methodname">reduce</a></span> ( <span class="methodparam"><span class="type"><a href="language.types.callable.html" class="type callable">callable</a></span> <code class="parameter">$callback</code></span> [, <span class="methodparam"><span class="type"><a href="language.pseudo-types.html#language.types.mixed" class="type mixed">mixed</a></span> <code class="parameter">$initial</code></span> ] )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">mixed</span> <span class="methodname"><a href="ds-deque.remove.html" class="methodname">remove</a></span> ( <span class="methodparam"><span class="type">int</span> <code class="parameter">$index</code></span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">void</span> <span class="methodname"><a href="ds-deque.reverse.html" class="methodname">reverse</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">Ds\Deque</span> <span class="methodname"><a href="ds-deque.reversed.html" class="methodname">reversed</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">void</span> <span class="methodname"><a href="ds-deque.rotate.html" class="methodname">rotate</a></span> ( <span class="methodparam"><span class="type">int</span> <code class="parameter">$rotations</code></span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">void</span> <span class="methodname"><a href="ds-deque.set.html" class="methodname">set</a></span> ( <span class="methodparam"><span class="type">int</span> <code class="parameter">$index</code></span> , <span class="methodparam"><span class="type"><a href="language.pseudo-types.html#language.types.mixed" class="type mixed">mixed</a></span> <code class="parameter">$value</code></span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">mixed</span> <span class="methodname"><a href="ds-deque.shift.html" class="methodname">shift</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">Ds\Deque</span> <span class="methodname"><a href="ds-deque.slice.html" class="methodname">slice</a></span> ( <span class="methodparam"><span class="type">int</span> <code class="parameter">$index</code></span> [, <span class="methodparam"><span class="type">int</span> <code class="parameter">$length</code></span> ] )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">void</span> <span class="methodname"><a href="ds-deque.sort.html" class="methodname">sort</a></span> ([ <span class="methodparam"><span class="type"><a href="language.types.callable.html" class="type callable">callable</a></span> <code class="parameter">$comparator</code></span> ] )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">Ds\Deque</span> <span class="methodname"><a href="ds-deque.sorted.html" class="methodname">sorted</a></span> ([ <span class="methodparam"><span class="type"><a href="language.types.callable.html" class="type callable">callable</a></span> <code class="parameter">$comparator</code></span> ] )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">number</span> <span class="methodname"><a href="ds-deque.sum.html" class="methodname">sum</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">array</span> <span class="methodname"><a href="ds-deque.toarray.html" class="methodname">toArray</a></span> ( <span class="methodparam">void</span> )</div> <div class="methodsynopsis dc-description"> <span class="modifier">public</span> <span class="type">void</span> <span class="methodname"><a href="ds-deque.unshift.html" class="methodname">unshift</a></span> ([ <span class="methodparam"><span class="type"><a href="language.pseudo-types.html#language.types.mixed" class="type mixed">mixed</a></span> <code class="parameter">$values</code></span> ] )</div> }</div> </div> <div class="section" id="ds-deque.constants"> <h2 class="title">Predefined Constants</h2> <dl> <dt id="ds-deque.constants.min-capacity"><strong><code>Ds\Deque::MIN_CAPACITY</code></strong></dt> <dd> <p class="para"/> </dd> </dl> </div> </div> <h2>Table of Contents</h2><ul class="chunklist chunklist_reference"><li><a href="ds-deque.allocate.html">Ds\Deque::allocate</a> — Allocates enough memory for a required capacity</li><li><a href="ds-deque.apply.html">Ds\Deque::apply</a> — Updates all values by applying a callback function to each value</li><li><a href="ds-deque.capacity.html">Ds\Deque::capacity</a> — Returns the current capacity</li><li><a href="ds-deque.clear.html">Ds\Deque::clear</a> — Removes all values from the deque</li><li><a href="ds-deque.construct.html">Ds\Deque::__construct</a> — Creates a new instance</li><li><a href="ds-deque.contains.html">Ds\Deque::contains</a> — Determines if the deque contains given values</li><li><a href="ds-deque.copy.html">Ds\Deque::copy</a> — Returns a shallow copy of the deque</li><li><a href="ds-deque.count.html">Ds\Deque::count</a> — Returns the number of values in the collection</li><li><a href="ds-deque.filter.html">Ds\Deque::filter</a> — Creates a new deque using a callable to determine which values to include</li><li><a href="ds-deque.find.html">Ds\Deque::find</a> — Attempts to find a value's index</li><li><a href="ds-deque.first.html">Ds\Deque::first</a> — Returns the first value in the deque</li><li><a href="ds-deque.get.html">Ds\Deque::get</a> — Returns the value at a given index</li><li><a href="ds-deque.insert.html">Ds\Deque::insert</a> — Inserts values at a given index</li><li><a href="ds-deque.isempty.html">Ds\Deque::isEmpty</a> — Returns whether the deque is empty</li><li><a href="ds-deque.join.html">Ds\Deque::join</a> — Joins all values together as a string</li><li><a href="ds-deque.jsonserialize.html">Ds\Deque::jsonSerialize</a> — Returns a representation that can be converted to JSON</li><li><a href="ds-deque.last.html">Ds\Deque::last</a> — Returns the last value</li><li><a href="ds-deque.map.html">Ds\Deque::map</a> — Returns the result of applying a callback to each value</li><li><a href="ds-deque.merge.html">Ds\Deque::merge</a> — Returns the result of adding all given values to the deque</li><li><a href="ds-deque.pop.html">Ds\Deque::pop</a> — Removes and returns the last value</li><li><a href="ds-deque.push.html">Ds\Deque::push</a> — Adds values to the end of the deque</li><li><a href="ds-deque.reduce.html">Ds\Deque::reduce</a> — Reduces the deque to a single value using a callback function</li><li><a href="ds-deque.remove.html">Ds\Deque::remove</a> — Removes and returns a value by index</li><li><a href="ds-deque.reverse.html">Ds\Deque::reverse</a> — Reverses the deque in-place</li><li><a href="ds-deque.reversed.html">Ds\Deque::reversed</a> — Returns a reversed copy</li><li><a href="ds-deque.rotate.html">Ds\Deque::rotate</a> — Rotates the deque by a given number of rotations</li><li><a href="ds-deque.set.html">Ds\Deque::set</a> — Updates a value at a given index</li><li><a href="ds-deque.shift.html">Ds\Deque::shift</a> — Removes and returns the first value</li><li><a href="ds-deque.slice.html">Ds\Deque::slice</a> — Returns a sub-deque of a given range</li><li><a href="ds-deque.sort.html">Ds\Deque::sort</a> — Sorts the deque in-place</li><li><a href="ds-deque.sorted.html">Ds\Deque::sorted</a> — Returns a sorted copy</li><li><a href="ds-deque.sum.html">Ds\Deque::sum</a> — Returns the sum of all values in the deque</li><li><a href="ds-deque.toarray.html">Ds\Deque::toArray</a> — Converts the deque to an array</li><li><a href="ds-deque.unshift.html">Ds\Deque::unshift</a> — Adds values to the front of the deque</li></ul> </div> <hr /><div class="manualnavbar" style="text-align: center;"> <div class="prev" style="text-align: left; float: left;"><a href="ds-vector.unshift.html">Ds\Vector::unshift</a></div> <div class="next" style="text-align: right; float: right;"><a href="ds-deque.allocate.html">Ds\Deque::allocate</a></div> <div class="up"><a href="book.ds.html">Data Structures</a></div> <div class="home"><a href="index.html">PHP Manual</a></div> </div></body></html>