the_memento_pattern.tex

\documentclass[11pt, a4paper, twoside]{article}

%% Die folgende Anleitung gilt für Linux:
%%
%%  Die Übersetzung dieses Dokuments erfolgt mit (ggf. öfter aufrufen):
%%  pdflatex seminar.tex
%%
%%  Falls die Bibliographie geändert wurde, dann zusätzlich:
%%  bibtex seminar
%%
%%  Bitte darauf achten, dass pdflatex und bibtex keine Warnungen und
%%  keine Fehler melden.
%%
%%  Das Ergebnis kann man ansehen:
%%  acroread seminar.pdf
%%
%%  Die Quelldatei einer deutschen Rechtschreibprüfung unterziehen:
%%  ispell -d deutsch -T latin1 seminar.tex

%% Kodierung des Dokuments
\usepackage[utf8]{inputenc}

%% Titel und Autor der Ausarbeitung (BITTE ANPASSEN!)
\title{The Memento Design Pattern}
\author{Daniel Geier}
\date{} %% leer lassen

%% Grafiken einbetten
\usepackage{graphicx}

%% Verweise in der PDF
\usepackage{hyperref} % important: load after float
\hypersetup{
	pdfproducer={pdfeTex 3.14159-1.30.6-2.2},
	colorlinks=false,
	pdfborder=0 0 0	% keine Box um die Links!
}
\usepackage{url}
\urlstyle{rm}

%% Programmcode Listings
\usepackage{listings}
\lstset{basicstyle=\ttfamily}

\lstset{language=C++,
	basicstyle=\ttfamily,
	keywordstyle=\color{blue}\ttfamily,
	stringstyle=\color{red}\ttfamily,
	commentstyle=\color{green}\ttfamily,
	morecomment=[l][\color{magenta}]{\#},
	frame=single,
	numbers=left
}

\usepackage{color}
\usepackage{cite}

%% Seitenlayout (BITTE NICHT VERÄNDERN!)
\oddsidemargin0mm
\evensidemargin0mm
\textwidth159.2mm
\topmargin0mm
\headheight0mm
\textheight43\baselineskip

%% Header und Footer (BITTE NICHT VERÄNDERN!)
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancypagestyle{plain}{\fancyhf{}\fancyfoot[RO,LE]{\thepage}\renewcommand\headrulewidth{0pt}}
\fancyhf{}
\fancyhead[LE]{\myauthor}
\fancyhead[RO]{\mytitle}
\fancyfoot[RO,LE]{\thepage}
\setlength{\headheight}{14pt}
\makeatletter
\let\mytitle\@title
\let\myauthor\@author
\makeatother

\def\cpp{C{}\texttt{++}}

% Der eigentliche Inhalt startet hier
\begin{document}
	\maketitle

	\begin{abstract} \noindent
 		Managing state restoration is a commonly occurring task in software development. Memento is a design pattern used for saving and restoring the (partial) state of objects. After examining reasons for using Memento, a comprehensive overview covering the static and dynamic structure is given. Examples from a \cpp{} source are presented. Benefits, drawbacks and implementation details in \cpp{} and \verb|Java| are discussed.
	\end{abstract}
	
	\section{Introduction}
	\label{sec:intro}
	The average project size in software development is constantly growing and so is code complexity. On the technical side, design patterns, made popular by Gamma \textit{et al.} \cite{gamma1993design}, are an attempt to tame this complexity with a structured object-oriented approach. The impact of design patterns were critically examined in a number of empirical investigations (e.g., \cite{jeanmart2009impact}, \cite{khomh2008design}, \cite{di2008empirical}, \cite{prechelt2001controlled}, \cite{vokac2004defect}, \cite{vokavc2004controlled}), which led to mixed conclusions on the benefits patterns may bring. Nonetheless patterns, when carefully used, can bring key advantages to the design and implementation process.
	
	The analysis in this paper concentrates on the Memento design pattern as it is presented in \cite{gamma1994design}.
	
	\section{Motivation}
	\label{sec:motivation}
	 Why invent a pattern to manage state changes in the first place? Why not use a simpler approach?
	 
	 When preserving the state of an object, the first technique that comes to mind is copying the variables that represent the state and copy them back to the object at a later time. Though seductive in its simplicity, this technique breaks encapsulation. Another possible solution, letting the stateful object manage its previous states by itself, violates separation of concern.
	 
	 Memento works by splitting the burden of managing state restoration between multiple classes, thus preserving good development practices.
	 	
	\section{Structure}
	The structure of a pattern can broken down into a \emph{static structure} and a \emph{dynamic structure}. The \emph{static structure} is composed of the object-oriented classes, their member variables, and their functions while the interactions between these static elements constitute the \emph{dynamic structure}. 
	
	\subsection{Static Structure}
	Three classes make up Memento: \verb|Originator|, \verb|Caretaker| and \verb|Memento|.
	
	\verb|Originator| is the class whose state will be encapsulated by our memento.
	
	\verb|Memento| encapsulates this state. It provides set and get mechanisms for this state which are accessible only to the originator. This is achieved by defining a \emph{narrow} interface for the caretaker and a \emph{wide} one for the originator.
	
	\verb|Caretaker| is the user of the originator. It is responsible for storing the mementos returned by the originator and returning them back to it. The caretaker never accesses the memento directly.
	
	\begin{figure}[htb]
		\begin{center}
			\includegraphics[width=\textwidth]{class_diagram.pdf}
			\caption{Class diagram showing the static structure with classes, their methods and class variables used}
			\label{fig:class}
		\end{center}
	\end{figure}
	
	As one can see in figure \ref{fig:class}, \verb|Originator| implements the method \verb|createMemento| for creating a memento, while \verb|setMemento| is used to load a previous state. \verb|Memento| implements accessors for its state, which should only be accessible to the \verb|Originator|. \verb|Caretaker| doesn't implement any methods specific to the pattern.
	
	\subsubsection{A \emph{Wide} and a \emph{Narrow} Interface}
	
	The key to Memento lies in implementing two different interfaces for \verb|Originator| and \verb|Caretaker|. The details of \verb|Memento| should be opaque to all but \verb|Originator| which accesses \verb|Memento| through a \emph{wide} interface. This way, \verb|Originator| can access the state  of \verb|Memento| while all other participants interact with \verb|Memento| through an \emph{narrow} interface, which leaves it opaque to them, i.e., they cannot access \verb|Memento|'s state or call its methods.
	
	This poses difficulties in programming languages who lack mechanism to define such constructs. Section~\ref{sec:impl} discusses mechanisms in \cpp{} and \verb|Java| for defining those interfaces.
	
	\subsection{Dynamic Structure}
	
	\begin{figure}[htb]
		\begin{center}
			\includegraphics[width=0.8\textwidth]{sequence_diagram.pdf}
			\caption{Sequence diagram showing the dynamic structure through method calls being made}
			\label{fig:sequence}
		\end{center}
	\end{figure}
	
	Figure \ref{fig:sequence} shows how the pattern is used in practice. \verb|aCaretaker| receives \verb|aMemento| from \verb|anOriginator| and saves it through the subsequent program execution. As soon as \verb|aCaretaker| wants to restore \verb|anOriginator| to a previous state, it returns \verb|aMemento| back to \verb|anOriginator| through the \verb|setMemento| method.
	
	
	\section{Sample Code}
	
	\begin{figure}[htb]
		\begin{center}
			\includegraphics[width=\textwidth]{mandelbrot.png}
			\caption{Part of the Mandelbrot figure as rendered by our program.}
			\label{fig:mandelbrot}
		\end{center}
	\end{figure}
	
	The sample application is a Mandelbrot  fractal explorer written in \cpp. We use a $c$-value of 1 to obtain the most famous of the Mandelbrot fractals. The fractal drawing and rendering is managed in the \verb|Mandelbrot| class. It is responsible for calculating the values of the Mandelbrot set and saving them in an array of pixels.
	
	\subsection{About Fractals}
	A fractal is a phenomenon that displays repeating patterns at every level of scale. The Mandelbrot fractal in specific is the set of complex numbers $c$ for which the sequence $c_{n+1} = c_n + c$ does not converge to infinity for $n \to \infty$. Observations about the intrinsics involved in the calculation of the Mandelbrot and related fractals are made by Mandelbrot himself~\cite{mandelbrot1980fractal}.
	
	\subsection{Code}
	\label{subsec:code}
	The Memento pattern is used for saving the state of the calculation and the calculated image in Listings \ref{Mandelbrot.h} and \ref{Mandelbrot.cpp}.
	
	\begin{lstlisting}[language=c++, caption={Mandelbrot.h}, label={Mandelbrot.h}]
class Mandelbrot
{
public:
	Memento* createMemento();
	void setMemento(Memento* memento);
	
	/* ... */
	
private:
	// Wide interface for the memento
	friend class Memento;
	
	// Variables saved within the memento
	Dimensions bounds;
	uint32_t* pixels;
	
	// Independent state variables
	int iterations;
	int width, height;
	bool doCalc;
	
	/* ... */
	};
	\end{lstlisting}
	
	\begin{lstlisting}[language=c++, caption={Mandelbrot.cpp}, label={Mandelbrot.cpp}]
Memento* Mandelbrot::createMemento()
{
	Memento* m = new Memento();
	m->setPixels(pixels, width * height);
	m->setBounds(bounds);
	return m;
}

void Mandelbrot::setMemento(Memento* memento)
{
	// Copy pixels from memento
	memcpy(pixels,memento->getPixels(),
		width * height * sizeof(uint32_t));
	bounds = memento->getBounds();
	doCalc = false;
}
	\end{lstlisting}
	
	In Listings \ref{Memento.h} and \ref{Memento.cpp}, the \verb|Memento| class saves the state which consists of the image data, \verb|pixels|, and the logical position of the Mandelbrot section, \verb|bounds|. A wide interface to \verb|Mandelbrot| is achieved by declaring it as a \verb|friend|.
	
	\begin{lstlisting}[language=c++, caption={Memento.h}, label={Memento.h}]
class Memento
{
public:
	~Memento();
	
private:
	friend class Mandelbrot;
	
	uint32_t* pixels;
	Dimensions bounds;
	
	Memento();
	void setPixels(uint32_t* oldPixels, int size);
	void setBounds(Dimensions bounds);
	
	uint32_t* getPixels();
	Dimensions getBounds();
};
	\end{lstlisting}
	
	\begin{lstlisting}[language=c++, caption={Memento.cpp}, label={Memento.cpp}]
void Memento::setPixels(uint32_t* oldPixels, int size)
{
	pixels = new uint32_t[size];
	// Copy pixels from mandelbrot
	memcpy(pixels, oldPixels,
		size * sizeof(uint32_t));
}

void Memento::setBounds(Dimensions oldBounds)
{
	bounds = oldBounds;
}

Memento::~Memento()
{
	delete[] pixels;
}

uint32_t* Memento::getPixels()
{
	return pixels;
}

Dimensions Memento::getBounds()
{
	return bounds;
}
	\end{lstlisting}
	
	We want to allow the user to zoom into the fractal. For this, she has to select a portion of the image by drawing a rectangle. Subsequently \verb|zoomIn()| is called.
	
	Listing \ref{Main.cpp} show how a Memento is created and put aside in dynamic storage before zooming in. The memento will restored at a later point to zoom out of the image.
	
	\begin{lstlisting}[language=c++, caption={Main.cpp}, label={Main.cpp}]
void zoomIn() {
	// mementos is a list of previous mementos
	mementos.push_back(mandelbrot.createMemento());
	mandelbrot.zoomIn(zoomRect);
	mandelbrot.render(renderer, screenTexture);
}
	\end{lstlisting}
	
	The user may want to zoom out of the image to explore another part of the fractal. She can do so by clicking a button whereupon \verb|zoomOut()| is called. In Listing \ref{Main.cpp2} a previously stored memento is retrieved from storage. The state of the \verb|Mandelbrot| object is restored.
	
	\begin{lstlisting}[language=c++, caption={Main.cpp}, label={Main.cpp2}]
void zoomOut() {
	if (mementos.size() > 0) {
		// Retrieve last memento
		Memento* m = mementos.back();
		mementos.pop_back();
		
		mandelbrot.setMemento(m);
		mandelbrot.render(renderer,
			screenTexture);
		
		delete m;
	}
}
	\end{lstlisting}
	
	\subsection{Implementation Details}
	\label{sec:impl}
	Not every programming language has features to facilitate the creation of wide and narrow interfaces. We examine two languages, Java and \cpp, that provide such features and show how they are used.
	
	In Java, \emph{static nested classes} can access private members of its surrounding class and vice versa. In such a way the memento can be implemented as a static nested class of the originator class. Listing \ref{Memento.java} shows this concept in practice.
	
		% language=c++ works fine here - its pretty much C++, syntactically
		\begin{lstlisting}[language=c++, caption={Memento.java}, label={Memento.java}]
class Originator {
	
	private String data;
	
	public Memento getMemento() {
		return new Memento(data);
	}
	
	public void setMemento(Memento m) {
		this.data = m.data;
	}
	
	// This is a static nested class -  its private members
	// can only be accessed by its outer class.
	// In this context, 'static' means that a Memento object
	// can be instantiated independently from an Originator
	// object.
	static class Memento {
		private String data;
	
		private Memento(String data) {
			this.data = data;
		}
	}
}
		\end{lstlisting}
	
	In C++ a class that is marked with the \verb|friend| keyword may access private members of the class. Hence the memento has to declare the originator as a \verb|friend|, as does the originator with the memento. How to do so in practice is shown in Section~\ref{subsec:code}.
	
	\section{Discussion}
	Now that we have examined Memento in theory and practice we can discuss when its suitable to use, when we can fit it to a problem and when something else can be used to a greater effect.
	
	
	\subsection{Benefits}
	\label{sec:benefits}
	\emph{Encapsulation}. Encapsulation has been shown to provide key benefits in the understandability and changeability of a computer program \cite{snyder1986}. As already explored in Section~\ref{sec:motivation}, simply copying member variables is unsuitable for maintaining good development practices; exposing state variables involves confiding implementation-specific details of the class. The memento object encapsulates the state of the originator. Inaccessible for all but the originator, the state is safe from unsound modifications from outside objects. \\
	
	\noindent\emph{Separation of concerns}. Before using Memento, the originator had to manage all state-restoring functionality by itself to maintain proper encapsulation. With this functionality moved into Memento, the originator is simplified. An in-depth treatment on separation of concerns is \cite{Huersch95}.
	
	\subsection{Drawbacks}
	\emph{Memory overhead}. Depending on how easily the state can be refactored out of the originator, there may be a substantial memory overhead in creating a memento. \\
	
	\noindent\emph{Defining different interfaces}. Some programming languages may lack facilities for declaring both a narrow and wide interface. \\
	
	\noindent\emph{Hidden costs}. As the implementation of the memento is hidden from the caretaker, it doesn't know how much state the memento is managing. It will therefore be hard to assess the memory consumption of a possibly otherwise lightweight caretaker.
	
	\subsection{Comparison with Other Patterns}
	A similar pattern, is \emph{Memoization}. \emph{Memoization} is most often used for program-speed optimization. It is the simple storing of function values to avoid repetitively calculating the same values over and over again. This is feasible if a time-consuming function has a manageable number of possible inputs and outputs; The most common outputs can be saved in an appropriate data structure like a hash table.
	
	\section{Conclusions}
	We have seen that Memento can be useful for managing state restoration.
	
	Though a number of drawbacks limit the usefulness of Memento, wisely used it can be an asset for suitable applications. Just as much as any other design strategy, the use of a pattern has to be weighed carefully against the added complexity it adds to the project. Only when a right fit of pattern to problem is determined, the pattern unfolds its potential.
	
	\bibliographystyle{unsrt}
	\bibliography{the_memento_pattern}
\end{document}