dequeu

Queue

It is a basis data structure to store data. In a queue, the first input element is the first element to exit. Its operations are:

push to insert at new value
pop to remove a value from the queue
top to see the last value that was inserted

Es una estructura básica de datos. En una cola, el primero elemento en entrar es el primer elemento en salir. Sus operaciones son:

push para insertar un valor nuevo
pop para remover un valor
top para ver el último valor que fue insertado

deque

A deque is a double queue. It is possible to push and pop at both ends of the queue. Its operations are:

push_back and push_front
pop_back and pop_front
back and front

Una deque es una cola doble. Es posible insertar y sacar valores en ambos extremos de la cola. Sus operaciones son:

push_back y push_front
pop_back y pop_front
back y front

Tip

deque support iterating through its elements. On the other hand, it is not possible to iterate the elements of a queue.

deque suporta iterar a través de sus elementos. Por otro lado, no es posible iterar los elementos de una queue.

Undo-redo

Most programs allow going back to a previous state. These actions are known as undo and redo.There are three main operations that must be implemented to provide Undo and Redo:

When the state of the program is modified
When the undo button is pressed (Ctrl-Z)
When the redo button is pressed (Ctrl-Shift-Z)

La mayoría de los programas permiten regresar a un estado anterior o posterior. Estas acciones se conocen comúnmente como rehacer y deshacer. Existen tres operaciones que se deben implementar para proporcionar Rehacer y Deshacer:

Cuando se edita o modifica el estado del programa
Cuando se presiona el botón de deshacer (Ctrl-Z)
Cuando se presiona el botón de rehacer (Ctrl-Shift-Z)

Tip

The Undo-redo technology works by storing several copies of the state of the program (several copies of the document or several copies of the variables of a program). If the state of the program requires a lot of memory, then it is possible only to have few levels to Undo and Redo. De-queues allow implemented easily the Undo and Redo technology.

La tecnología de rehacer y deshacer funciona a través de almacenar varias copias del estado del programa (varias copias del documento o varias copias de la memoria del programa). Si el estado de estado del programa requiere mucha memoria para ser guardado, entonces solo es posible tener pocos niveles de rehacer y deshacer. Las colas dobles permites implementar fácilmente la tecnología de Rehacer y Deshacer.

Edit (modify the state of the program)

The figure shows how the Undo-redo technology works during a change in the state of the program (document). Before performing any change, the current state is stored at the front of the undo-deque. After that, we must check if the undo-deque is fulled and if it is full, then one element must be removed from the back. Finally, the changed in the program (document) state is performed. In the figure, the original document has an orange letter b. First we store the orange letter b in the deque. Second we remove the red letter c from the deque, and we update the program to has a blue letter a.

La figura de abajo muestra como la tecnología de Deshacer y rehacer opera durante un cambio en el estado del programa (o documento). Antes de cualquier cambio, se guarda el estado actual en el front de la deque de deshacer. Después se debe checar si la deque de deshacer está llena y si está llena entonces se debe remover un elemento del back. Finalmente, se realiza la edición o modificación del programa (o documento). En la figura, el documento original tiene una letra B naranja. Primero almacenamos la letra B naranja en la cola. Segundo nosotros removemos la letra roja C de la cola, y actualizamos el programa para que tenga una letra A azul.

Undo

The operation of Undo is described in the figure. The current state of the program (or document) is stored in the front of the undo-queue. After that, we check if the undo-deque is full, if it is full one element is removed from the back. Finally, one element is removed from the front of the undo-queue, this element is used to set the state of the program (or document).

La operación de deshacer se describe en la figura de abajo. El estado actual del programa (o documento) se guarda en el front de la cola de rehacer. Después se comprueba que la cola de rehacer se encuentra llena, si se encuentra llena se remueve un elemento del back. Finalmente, se saca un elemento del front de la cola de deshacer y se usa para fijar el estado actual del programa (o documento).

Redo

The figure shows how to perform a Redo. The current state is stored in the front of the undo-deque. After that, we check if the undo-queue is full, and if it is, the one element is removed from the back. Finally, one element form the redo-deque is removed and used to set the state of the program (or document).

La figura de abajo ilustra cómo realizar un Rehacer. El estado actual se guarda en el front de la cola de deshacer. Después se comprueba que la cola de deshacer se encuentra llena, si se encuentra llena se remueve un elemento del back. Finalmente, se saca un elemento del front de la cola de rehacer y se usa para fijar el estado del programa (o documento).

Problem 1

Create a Wintempla dialog application called MyEditor to test the Undo-Redo technology using the deque from the STL. Set the "Change" event in the textbox.

Cree una aplicación de diálogo de Wintempla llamada MyEditor para probar la tecnología de Deshacer-Rehacer usando la cola doble de la STL. Fije el evento de "Change" en la caja de texto.

MyEditor.h

#pragma once //______________________________________ MyEditor.h
#include "Resource.h"

#define MAX_UNDO 20

class MyEditor: public Win::Dialog
{
public:
     MyEditor()
     {
     }
     ~MyEditor()
     {
     }
     deque<wstring> undo;
     deque<wstring> redo;
...
};

MyEditor.cpp

...
void MyEditor::Window_Open(Win::Event& e)
{
     btUndo.Enabled = false;
     btRedo.Enabled = false;
}

void MyEditor::btUndo_Click(Win::Event& e)
{
     if (undo.empty() == true) return;
     //_____________________________ Step 1: Store current state
     redo.push_front(tbxInput.Text);
     //_____________________________ Step 2. Remove if full
     if (redo.size()>=MAX_UNDO) redo.pop_back();
     //_____________________________ Step 3. Perform the change
     tbxInput.Text = undo.front();
     undo.pop_front();
     //_____________________________ Update buttons
     btRedo.Enabled = (redo.empty() == false);
     btUndo.Enabled = (undo.empty() == false);
}

void MyEditor::btRedo_Click(Win::Event& e)
{
     if (redo.empty() == true) return;
     //_____________________________ Step 1: Store current state
     undo.push_front(tbxInput.Text);
     //_____________________________ Step 2. Remove if full
     if (undo.size()>=MAX_UNDO) undo.pop_back();
     //_____________________________ Step 3. Perform the change
     tbxInput.Text = redo.front();
     redo.pop_front();
     //_____________________________ Update buttons
     btRedo.Enabled = (redo.empty() == false);
     btUndo.Enabled = (undo.empty() == false);
}

void MyEditor::tbxInput_Change(Win::Event& e)
{
     undo.push_front(tbxInput.Text);
     btUndo.Enabled = true;
     if (undo.size()>=MAX_UNDO) undo.pop_back();
     redo.clear();
     btRedo.Enabled = false;
}