DEQueue
An object-based double-ended queue
|
Description
|
|
•
|
The DEQueue appliable object provides an efficient means to construct, manipulate, and query double-ended queues.
|
•
|
Unlike a Maple list, adding or replacing an element in a DEQueue does not allocate a new container. As such, it can be efficiently used in loops to build up a sequence an element at a time, adding new elements at either end.
|
|
Construction
|
|
•
|
The DEQueue function returns a new DEQueue object.
|
–
|
If called with a single argument that is either a Maple list or a DEQueue object, the returned object contains the elements in the argument.
|
–
|
Otherwise, the returned object contains each distinct argument as an element.
|
|
|
Modification
|
|
•
|
The following functions modify the contents of a DEQueue object. The dq argument denotes a DEQueue object. The expr argument denotes any Maple expression or sequence thereof.
|
–
|
pop_front(dq) : Deletes and returns one element from the front of dq.
|
–
|
pop_back(dq) : Deletes and returns one element from the back of dq.
|
–
|
push_front(dq,expr) : Pushes expr onto the front of dq.
|
–
|
push_back(dq,expr) : Pushes expr onto the back of dq.
|
–
|
dq ,= expr : Equivalent to push_back(dq,expr).
|
•
|
Because elements can be pushed onto and popped from either end of a DEQueue, it can be used as both a first-in-first-out (FIFO) queue (by using push_back and pop_front), or as a stack (by using push_front and pop_front).
|
|
|
Inspection
|
|
•
|
The following functions inspect the content of a DEQueue object. The dq arguments denote DEQueue objects.
|
–
|
dq = other or `=`(dq,other) : When evaluated in a boolean context, returns true if dq and other are both DEQueue objects with identical content, false otherwise.
|
–
|
expr in dq or `in`(expr,dq) : Returns true if expr is an element of dq, false otherwise.
|
–
|
empty(dq) : Returns true if dq is empty, false otherwise.
|
–
|
entries(dq) : Returns an expression sequence of all the entries in dq, with each entry enclosed in a list by default.
|
–
|
front(dq) or back(dq) : Returns the element at the front or back of dq, without removing it.
|
–
|
has(dq,expr) : Returns true if any element of dq contains expr, false otherwise.
|
–
|
hastype(dq,typ) : Returns true if any element of dq contains an expression of the specified type, false otherwise.
|
–
|
indets(dq,typ) : Returns a Maple set of all indeterminates in dq. If the optional typ parameter is specified, then returns the expressions of type typ.
|
–
|
indices(dq) : Returns an expression sequence of all the indices of dq, with each index enclosed in a list by default.
|
–
|
lowerbound(dq) : Returns the lower index bound (always 1)
|
–
|
max(dq) : Returns the maximum element of dq. Behaves like max on lists.
|
–
|
member(expr,dq) : Returns true if expr is an element of dq, false otherwise. The three argument form of member is not supported.
|
–
|
min(dq) : returns the minimum element of dq. Behaves like min on lists.
|
–
|
numboccur(dq,expr) : Count the number of occurrences of expr in dq, either as an element or within elements.
|
–
|
numelems(dq) : Returns the number of elements in dq.
|
–
|
upperbound(dq) : Returns the upper index (same as the output of numelems).
|
•
|
Each of the above functions is already available in Maple for built-in Maple structures such as lists and Arrays. Please refer to the help page for each function for details on usage.
|
|
|
Mapping, Selection, Removal, and Substitution
|
|
•
|
The map, select, remove, selectremove, and subs functions operate on a DEQueue object. Refer to their help pages for the calling sequences. By default they create a new DEQueue object, but if called with the inplace index option, they update the existing DEQueue object. The dq argument denotes a DEQueue object.
|
–
|
map(fcn,dq) : Apply a procedure, fcn, to each element of dq.
|
–
|
select(fcn,dq) : Select elements of dq for which fcn returns true.
|
–
|
remove(fcn,dq) : Remove elements of dq for which fcn returns true.
|
–
|
selectremove(fcn,dq) : Produce two DEQueues, one containing selected elements and the other removed elements.
|
–
|
subs(eqns,dq) : Substitute subexpressions in the content of dq.
|
|
|
Conversion
|
|
•
|
The convert functions can be used to convert a DEQueue object to and from other Maple structures.
|
–
|
convert(dq,typ) : Convert a DEQueue to the specified type.
|
–
|
convert(expr,DEQueue) : Convert expr to a DEQueue object. expr must be a list, set, or rtable.
|
|
|
Indexing
|
|
•
|
Integer indices can be used to extract or reassign a single element of a DEQueue.
|
|
|
Iteration
|
|
•
|
The DEQueue object exports a ModuleIterator function, allowing the DEQueue object to be used in loops and iterations (seq, add, etc.).
|
|
|
|
Examples
|
|
|
Construction
|
|
•
|
Create a DEQueue with three elements.
|
>
|
|
| (1) |
| (2) |
•
|
Create a DEQueue from a Maple list.
|
>
|
|
| (3) |
|
|
Modification
|
|
•
|
Remove c from the back of Q1 and insert z at the front.
|
| (5) |
•
|
Add c to each element in Q2, doing so inplace.
|
>
|
|
| (6) |
•
|
Replace all occurrences of c inside Q2 with d, doing so inplace.
|
>
|
|
| (7) |
|
|
Inspection
|
|
•
|
Use member to determine whether a given element is a member of Q1.
|
>
|
|
| (8) |
•
|
Use has to test for the occurrence of a subexpression in any of the members of the set.
|
>
|
|
|
|
Conversion
|
|
•
|
Create a DEQueue object by converting a Vector.
|
>
|
|
| (12) |
| (13) |
|
|
Indexing
|
|
•
|
Use indexing to extract each element of a DEQueue.
|
>
|
|
| (14) |
>
|
|
•
|
Reassign the value at the second index.
|
>
|
|
|
|
Iteration
|
|
•
|
Iterate through each element in Q1.
|
| (17) |
•
|
Add the elements of Q2.
|
>
|
|
|
|
Usage
|
|
•
|
The DEQueue object provides an efficient way to construct a list an element at a time, in a loop. Doing so with standard Maple lists is inefficient in that each addition creates a new list; as such the operation is in time and memory, where is the number of elements. The following compares the memory and time required to create a list of twenty thousand elements using lists and a DEQueue object.
|
>
|
MapleLists := proc(n :: posint)
local i, s;
s := [];
for i to n do
s := [op(s), i];
end do:
numelems(s);
end proc:
DEQueues := proc(n :: posint)
local i, s;
s := DEQueue();
for i to n do
push_back(s,-i);
end do;
numelems(s);
end proc:
|
>
|
|
memory used=1.49GiB, alloc change=25.48MiB, cpu time=3.84s, real time=2.64s, gc time=2.50s
| |
>
|
|
memory used=13.78MiB, alloc change=8.00MiB, cpu time=161.00ms, real time=134.00ms, gc time=56.58ms
| |
|
|
|
Compatibility
|
|
•
|
The DEQueue object was introduced in Maple 2021.
|
|
|
|
|
|
|