откат (undo)

В этой статье я хочу предложить класс CStackDoUndo, предназначенный для выполнения отката (а точнее - отката и возврата т.е. операций Undo и Do).
Сохраняемые объекты могут быть любыми - от простых переменных и массивов до описаний действий, произведённых над данными. Следовательно, если непосредственно перед изменениями сохранить данные или сохранить описание действий, то откат станет возможен - просто надо "проиграть" всё в обратном порядке или заменить содержимое переменных.
Стеки UNDO и DO можно представить как две трубы, линии осей которых совпадают, а между торцами этимх труб имеется некоторое расстояние. Труба слева - Это стек UNDO, справа - DO, а просвет - это текущее состояние (ТС).

Код:
UNDO-ТС-DO
Сначала трубы пусты. Когда ТС требуется изменить, оно вдвигается в стек UNDO, а затем изменяется. Если UNDO становится полностью заполнен, то элемент, вдвинутый в UNDO первым (он расположен самым левым в UNDO) "выпадает" и теряется при помещении в UNDO нового элемента. Заметьте, что при этом стек DO нужно очистить, так как его содержимое практически теряет смысл.
При команде "undo" если стек UNDO не пуст, то ТС помещается в стек DO, а из UNDO извлекается последний помещённый элемент и помещается на место ТС. Если стек UNDO пуст, ничего не произойдёт.
Команда "do" выполняются наоборот: DO->TC->UNDO.
Так как для правильной работы класса необходимо сначала описать сохраняемые данные , например в виде структуры, то для каждого типа такой структуры класс нужно будет немного подогнать под. Собственно, сохраняемые даные описываются в структуре item класса и только его надо будет менять. Вернее: описание указателей, содержимое функции extract() и содержимое конструктора и деструктора item() и ~item().
Вот заголовочный файл класса:

Код:
// файл StackDoUndo.h
class CStackDoUndo
{
public:
/////////////////// интерфейс класса///////////////////////////
//эта процедура вызывается перед изменениями
void SaveBeforeChange(item *ITEM);
void OperationDo(item *ITEM); //выполнить действие "Do"
void OperationUndo(item *ITEM); //выполнить действие "UnDo"
void ClearDoUndoStacks();//Очистить оба стека
int GetDoLen();//получить длину стека Do
int GetUndoLen();//получить длину стека Undo
//////////////////////////////////////////////////////////////////////////
CStackDoUndo(int UndoStackSize=5,int DoStackSize=5);//конструктор
~CStackDoUndo(); //деструктор
struct item; //структура "элемент" для DO/UNDO
private:
int SP_Undo; //счётчик элементов стека UNDO
int SP_Do; //счётчик элементов стека DO
int StackSize_Undo; //размер стека UNDO.
item **Stack_Undo; //счётчик элементов стека UNDO
int StackSize_Do; //размер стека DO.
item **Stack_Do; //счётчик элементов стека DO

void PushToDo(item *ITEM); //добавить в стек Do
bool PopFromDo(item *ITEM); //извлечь из стека Do
void PushToUndo(item *ITEM); //добавить в стек UnDo
bool PopFromUndo(item *ITEM); //извлечь из стека UnDo
void ClearDoStack();//очистка стека DO
void ClearUndoStack();//очистка стека UNDO
public:
//структура "элемент" для DO/UNDO
//(описывает сохраняемые данные)
struct item
{
bool m_bMadeEmpty;//Способ заполнения элемента
bool m_being;//флаг существования "элемента"

//Далее - всё зависит от типов сохраняемых данных

//Объявление УКАЗАТЕЛЕЙ для переменных и массивов
int *m_pH, *m_pW;//размер матрицы(height, width)
BYTE *m_pMatrix;//для массива, куда скопируется матрица.

//конструктор. Сюда передаются УКАЗАТЕЛИ для
//переменных и массивов внешних данных
item(BYTE *Matrix, int *H, int *W, bool bToMakeEmpty=true);

//извлечь данные из "элемента"
void extract(item *ITEM);

//деструктор. Здесь удаляются динамически созданные
//переменные и массивы
~item();
};
};

Переопределить item для других типов данных несложно, далее будет рассказано, как это сделать. Для примера в данном коде item настроен на сохранение матрицы типа BYTE размером H*W , где H - высота, W-ширина.
В структуре item определены члены int m_H, m_W для хранения ширины и высоты и BYTE *m_Matrix для хранения указателя на массив, который будет создан для копирования сохраняемого массива (либо уже существует - об это далее).


Описание файла реализации класса CStackDoUndo

(текст кода в некоторых местах разорван комментариями :) )

Код:
// файл StackDoUndo.cpp

//#include "stdafx.h" //для windows - приложения
#include "StackDoUndo.h"

//конструктор структуры item
CStackDoUndo::item::item(BYTE *Matrix, int *H, int *W,bool bToMakeEmpty)
{
m_being=false; //существование элемента item
//сохраняем способ заполнения и проверяем
if(m_bMadeEmpty=bToMakeEmpty)
{
////способ - настройка указателей на уже существующие данные

// Matrix - внешний массив
if(Matrix)
{
m_pMatrix=Matrix; //матрица
m_pW=W; m_pH=H; //ширина и высота
m_being=true; //существование
}
else{m_pH=m_pW=NULL;}
}
else
{
////способ - выделение памяти под данные

//создаётся массив для хранения матрицы
m_pMatrix=new BYTE[(*H)*(*W)];
//переменные для ширины и высоты
m_pW=new int(0); m_pH=new int(0);
//проверяем правильность создания
if(m_pMatrix && m_pH && m_pW)
{
//копируем данные извне в "элемент"
for(int i=0;i<(*H)*(*W);i++) m_pMatrix[i]=Matrix[i];
*(m_pW)= *W; //копируем ширину
*(m_pH)= *H; //копируем высоту

m_being=true;//существование
}
else{m_pMatrix=NULL;m_pH=m_pW=NULL;}
}
}

Данные передаются элементу item при его создании через конструктор. Количество и типы аргументов конструктора идентичны переменным-указателям структуры. Только добавлен флаг bToMakeEmpty:
Код:
item(BYTE *Matrix, int *H, int *W, bool bToMakeEmpty=true)

Флаг bToMakeEmpty задаёт способ создания экземпляра структуры. Если bToMakeEmpty==true (по умолчанию), то настройка указатели-члены настраиваются уже существующие внешние данные. Если bToMakeEmpty==false, то создаются динамические переменные, их адреса присваиваются указателям членам и в эти переменные копируются данные из внешних переменных.

Код:
//деструктор структуры item
CStackDoUndo::item::~item()
{
//удаляем всё созданное new (при методе
//созданияя не-empty
if(!m_bMadeEmpty)
{
if(m_pMatrix)delete [] m_pMatrix;
if(m_pH)delete m_pH;
if(m_pW)delete m_pW;
}
}

В деструкторе удаляем динамически созданные переменные, если был способ создания - Empty.

Код:
//скопировать данные из "элемента" во внешние переменные
void CStackDoUndo::item::extract(item *ITEM)
{
for(int i=0;i<(*m_pH)*(*m_pW);i++)
{
(ITEM->m_pMatrix)[i]=m_pMatrix[i];
}
*(ITEM->m_pH)=(*m_pH);
*(ITEM->m_pW)=(*m_pW);
}

Процедурой extract() данные "извлекаются" из элемента - копируются из экземпляра item во внешние переменные.
Весь дальнейший код класса - не зависит от типа сохраняемых данных

Код:
//конструктор класса CStackDoUndo
CStackDoUndo::CStackDoUndo(int UndoStackSize,int DoStackSize)
{
//массивы ещё не созданы
Stack_Undo=Stack_Do=NULL;
//задание размеров стеков UNDO и DO
StackSize_Undo=(UndoStackSize>0 ? UndoStackSize:5);
StackSize_Do=(DoStackSize>0 ? DoStackSize:5);
//обнуление счётчиков стеков UNDO и DO
SP_Undo=SP_Do=0;
//создаётся стек UNDO
Stack_Undo=new item* [StackSize_Undo];
//создаётся стек DO
Stack_Do=new item* [StackSize_Do];
}

//деструктор
CStackDoUndo::~CStackDoUndo()
{
//очищаем стеки
ClearDoUndoStacks();
//удаляем стеки
if(Stack_Undo)delete [] Stack_Undo;
if(Stack_Do)delete [] Stack_Do;
}

Далее в файле реализации расположен код privat-процедур класса CStackDoUndo

Код:
//добавление элемента в UNDO_Stack
void CStackDoUndo::PushToUndo(item *ITEM)
{
//если стек заполнен до упора, то сдвигаем
//содержимое стека на единицу,
//убивая самый ранний элемент
if(SP_Undo==StackSize_Undo)
{
//удаляем первый элемент (он заведомо
//существует, т.к. SP_Undo==StackSize_Undo )
delete Stack_Undo[0];
//сдвигаем остальные элементы стека
//и уменьшаем указатель
for(int i=1;i<StackSize_Undo;i++)
{Stack_Undo[i-1]=Stack_Undo[i];}
SP_Undo--;
}
//добавляем элемент и увеличиваем указатель
Stack_Undo[SP_Undo++]=
new item(ITEM->m_pMatrix,
ITEM->m_pH, ITEM->m_pW, false);
}

// добавление элемента в DO_Stack
void CStackDoUndo::PushToDo(item *ITEM)
{
//если стек заполнен до упора, то сдвигаем
//стек на единицу по принципу FIFO,
//убивая самый ранний элемент
if(SP_Do==StackSize_Do)
{
//удаляем первый элемент (он заведомо
//существует, т.к. SP_Do==StackSize_Do)
delete Stack_Do[0];
//сдвигаем остальные элементы стека
//и уменьшаем указатель
for(int i=1;i<StackSize_Do;i++)
{Stack_Do[i-1]=Stack_Do[i];}
SP_Do--;
}
//добавляем элемент и увеличиваем указатель
Stack_Do[SP_Do++]=
new item(ITEM->m_pMatrix,
ITEM->m_pH, ITEM->m_pW, false);
}

//функция извлечения из Undo стека
bool CStackDoUndo::PopFromUndo(item *ITEM)
{
//если элементов нет, то выходим
if(SP_Undo==0)return false;
//уменьшаем указатель и извлекаем элемент
Stack_Undo[--SP_Undo]->extract(ITEM);
//удаляем элемент из стека
delete Stack_Undo[SP_Undo];
return true;
}

//функция извлечения из Do стека
bool CStackDoUndo::PopFromDo(item *ITEM)
{
//если элементов нет, то выходим
if(SP_Do==0)return false;
//уменьшаем указатель и извлекаем элемент
Stack_Do[--SP_Do]->extract(ITEM);
//удаляем элемент из стека
delete Stack_Do[SP_Do];
return true;
}

//очищаем стек DO
void CStackDoUndo::ClearDoStack()
{
//очищаем стек DO
if(Stack_Do)
{
while(SP_Do>0)
{
//уменьшаем указатель и коцаем элемент
delete Stack_Do[--SP_Do];
}
}
}

//очищаем стек UNDO
void CStackDoUndo::ClearUndoStack()
{
//очищаем стек UNDO
if(Stack_Undo)
{
while(SP_Undo>0)
{
//уменьшаем указатель и коцаем элемент
delete Stack_Undo[--SP_Undo];
}
}
}

Далее в файле реализации расположен код интерфейсных процедур класса CStackDoUndo

Код:
/////////////////////////////////
////////// интерфейс ///////////
/////////////////////////////////

//дейтсвие "DO"
void CStackDoUndo::OperationDo(item *ITEM)
{
//если стек Do пуст - вылазим
if(!SP_Do)return;
//сохраняем текущие данные в стек UNDO
//и заменяем их данными из стека DO
PushToUndo(ITEM);
PopFromDo(ITEM);
}

//действие "UNDO"
void CStackDoUndo::OperationUndo(item *ITEM)
{
//если стек Undo пуст - вылазим
if(!SP_Undo)return;
//сохраняем текущие данные в стек DO
//и заменяем их данными из стека UNDO
PushToDo(ITEM);
PopFromUndo(ITEM);
}

//функция очистки DO/UNDO стеков
void CStackDoUndo::ClearDoUndoStacks()
{
ClearDoStack(); ClearUndoStack();
}

//получить длину стека Do
int CStackDoUndo::GetDoLen(){return SP_Do;}

//получить длину стека Undo
int CStackDoUndo::GetUndoLen(){return SP_Undo;}

//эту процедуру нужно вызывать перед очередным
//изменением данных - тогда данные будут помещены
//в стек UNDO. При этом стек DO очищается.
void CStackDoUndo::SaveBeforeChange(item *ITEM)
{
//сохраняем в стек UNDO и очищаем стек DO
PushToUndo(ITEM);
ClearDoStack();
}


Пример использования (на VC++).


Создайте MFC проект (dialog-based) и назовите его, к примеру, doundo.
Добавьте класс CStackDoUndo в проект: скопируйте файлы CStackDoUndo.h и CStackDoUndo.cpp в папку пректа, затем в окне проекта во вкладке Classiew - правой кнопкой по корню списка классов, затем -> New Class. Class Type выберите Generic Class. Обратите внимание, чтобы вначале файла CStackDoUndo.cpp была строка
Код:
#include "stdafx.h"

Разместите на форме диалога три кнопки с надписями "Undo","Do","Change" и ID соответственно IDC_bnUNDO, IDC_bnDO и IDC_bnCHANGE. Также разместите окно ввода (CEdit) с ID == IDC_edTEXT. Окно ввода сделайте поквадратнее и побольше (на пол экрана сойдёт ;) ).
В заголовочный файл диалога CDoundoDlg.h добавьте заголовок класса CStackDoUndo и переменные-члены для данных диалога:
Код:
// doundoDlg.h
#include "StackDoUndo.h"

class CDoundoDlg : public CDialog
{
// Construction
public:
BYTE *Matrix;
int H;
int W;
CStackDoUndo stk;
...
...
};
...
...

В конце конструктора диалога (файл doundoDlg.cpp) добавьте инициализацию

Код:
// doundoDlg.cpp
CDoundoDlg::CDoundoDlg(CWnd* pParent /*=NULL*/)
: CDialog(CDoundoDlg::IDD, pParent)
{
...
...
...

H=10;
W=5;
Matrix=new BYTE[H*W];
for(int i=0;i<H*W;i++)
{
Matrix[i]=i;
}
}

В процедуре CDoundoDlg::OnPaint(), после строки
Код:
CDialog::OnPaint()
добавьте:

Код:
// doundoDlg.cpp

void CDoundoDlg::OnPaint()
{
if (IsIconic())
{
...
...
}
else
{
CDialog::OnPaint();

CString txt="",txt1;
for(int h=0;h<H;h++)
{
for(int w=0;w<W;w++)
{
txt1.Format("%02x",Matrix[h*W+w]);
txt+=txt1+"\t";
}
txt+="\r\n";
}

((CEdit*)GetDlgItem(IDC_edTEXT))->SetWindowText(txt);

if(stk.GetDoLen()==0)
GetDlgItem(IDC_bnDO)->EnableWindow(FALSE);
else
GetDlgItem(IDC_bnDO)->EnableWindow(TRUE);

if(stk.GetUndoLen()==0)
GetDlgItem(IDC_bnUNDO)->EnableWindow(FALSE);
else
GetDlgItem(IDC_bnUNDO)->EnableWindow(TRUE);
}
}

Также добавьте обработчики кнопок

Код:
// doundoDlg.cpp
void CDoundoDlg::OnbnCHANGE()
{
//создаём элемент
CStackDoUndo::item ITEM(Matrix,&H,&W);
//сохраняем
stk.SaveBeforeChange(&ITEM);
//изменяем данные
Matrix[0]++;
Matrix[H*W-1]++;
//перерисовываем
OnPaint();
}

void CDoundoDlg::OnbnDO()
{
//создаём элемент
CStackDoUndo::item ITEM(Matrix,&H,&W);
//сохраняем
stk.OperationDo(&ITEM);
//перерисовываем
OnPaint();
}

void CDoundoDlg::OnbnUNDO()
{
//создаём элемент
CStackDoUndo::item ITEM(Matrix,&H,&W);
//сохраняем
stk.OperationUndo(&ITEM);
//перерисовываем
OnPaint();
}

Скомпилируйте и запустите проект. По нажатию кнопка Change содержимое массива будет меняться. Кнопками DO/UNDO - можно делать откат.


Если переписать структуру item для некого абстрактного типа A, то получится:

рабочая структура будет выглядеть так:
Код:
struct item
{
bool m_bMadeEmpty;
bool m_being;
A *m_pA
item(A *pA, bool bToMakeEmpty=true);
void extract(item *ITEM);
~item();
};

конструктор структуры item:
Код:
//конструктор структуры item
CStackDoUndo::item::item(A *pA, bool bToMakeEmpty)
{
m_being=false;
if(m_bMadeEmpty=bToMakeEmpty)
{
if(pA)
{
m_pA=pA;
m_being=true;
}
else{m_pA=0;}
}
else
{
m_pA=new A();
if(m_pA)
{
*(m_pA)= *A;
m_being=true;
}
else{m_pA=0;}
}
}

деструктор структуры item:
Код:
//деструктор структуры item
CStackDoUndo::item::~item()
{
if(!m_bMadeEmpty)
{
if(m_pA)delete m_pA;
}
}

процедура для извлечения :
Код:
//скопировать данные из "элемента" во внешние переменные
void CStackDoUndo::item::extract(item *ITEM)
{
*(ITEM->m_pA)=(*m_pA);
}


пример использования:

Код:
CStackDoUndo stk;
A a;

//создаём элемент
CStackDoUndo::item ITEM(&a);

//ПРИМЕРЫ ВЫЗОВОВ

//сохраняем текущее состояние в стек
stk.SaveBeforeChange(&ITEM);

//вносим некие изменения
...
...

//выполняем "откат"
stk.OperationUndo(&ITEM);

//выполняем возврат
stk.OperationDo(&ITEM);

Вот и всё :)


C Уважением, Алексей Журавлёв
Автор: Алексей1153