%%% DOCUMENTCLASS 
%%%-------------------------------------------------------------------------------

\documentclass[
a4paper, % Stock and paper size.
11pt, % Type size.
% article,
% oneside, 
onecolumn, % Only one column of text on a page.
% openright, % Each chapter will start on a recto page.
% openleft, % Each chapter will start on a verso page.
openany, % A chapter may start on either a recto or verso page.
]{memoir}

%%% PACKAGES 
%%%------------------------------------------------------------------------------

\usepackage[utf8]{inputenc} % If utf8 encoding
% \usepackage[lantin1]{inputenc} % If not utf8 encoding, then this is probably the way to go
\usepackage[T1]{fontenc}    %
\usepackage[english]{babel} % English please
\usepackage[final]{microtype} % Less badboxes

% \usepackage{kpfonts} %Font

\usepackage{amsmath,amssymb,mathtools} % Math

% \usepackage{tikz} % Figures
\usepackage{graphicx} % Include figures

%%% PAGE LAYOUT 
%%%------------------------------------------------------------------------------

\setlrmarginsandblock{0.15\paperwidth}{*}{1} % Left and right margin
\setulmarginsandblock{0.2\paperwidth}{*}{1}  % Upper and lower margin
\checkandfixthelayout

%%% SECTIONAL DIVISIONS
%%%------------------------------------------------------------------------------

\maxsecnumdepth{subsection} % Subsections (and higher) are numbered
\setsecnumdepth{subsection}

\makeatletter %
\makechapterstyle{standard}{
  \setlength{\beforechapskip}{0\baselineskip}
  \setlength{\midchapskip}{1\baselineskip}
  \setlength{\afterchapskip}{8\baselineskip}
  \renewcommand{\chapterheadstart}{\vspace*{\beforechapskip}}
  \renewcommand{\chapnamefont}{\centering\normalfont\Large}
  \renewcommand{\printchaptername}{\chapnamefont \@chapapp}
  \renewcommand{\chapternamenum}{\space}
  \renewcommand{\chapnumfont}{\normalfont\Large}
  \renewcommand{\printchapternum}{\chapnumfont \thechapter}
  \renewcommand{\afterchapternum}{\par\nobreak\vskip \midchapskip}
  \renewcommand{\printchapternonum}{\vspace*{\midchapskip}\vspace*{5mm}}
  \renewcommand{\chaptitlefont}{\centering\bfseries\LARGE}
  \renewcommand{\printchaptertitle}[1]{\chaptitlefont ##1}
  \renewcommand{\afterchaptertitle}{\par\nobreak\vskip \afterchapskip}
}
\makeatother

\chapterstyle{standard}

\setsecheadstyle{\normalfont\large\bfseries}
\setsubsecheadstyle{\normalfont\normalsize\bfseries}
\setparaheadstyle{\normalfont\normalsize\bfseries}
\setparaindent{0pt}\setafterparaskip{0pt}

%%% FLOATS AND CAPTIONS
%%%------------------------------------------------------------------------------

\makeatletter                  % You do not need to write [htpb] all the time
\renewcommand\fps@figure{htbp} %
\renewcommand\fps@table{htbp}  %
\makeatother                   %

\captiondelim{\space } % A space between caption name and text
\captionnamefont{\small\bfseries} % Font of the caption name
\captiontitlefont{\small\normalfont} % Font of the caption text

\changecaptionwidth          % Change the width of the caption
\captionwidth{1\textwidth} %

%%% ABSTRACT
%%%------------------------------------------------------------------------------

\renewcommand{\abstractnamefont}{\normalfont\small\bfseries} % Font of abstract title
\setlength{\absleftindent}{0.1\textwidth} % Width of abstract
\setlength{\absrightindent}{\absleftindent}

%%% HEADER AND FOOTER 
%%%------------------------------------------------------------------------------

\makepagestyle{standard} % Make standard pagestyle

\makeatletter                 % Define standard pagestyle
\makeevenfoot{standard}{}{}{} %
\makeoddfoot{standard}{}{}{}  %
\makeevenhead{standard}{\bfseries\thepage\normalfont\qquad\small\leftmark}{}{}
\makeoddhead{standard}{}{}{\small\rightmark\qquad\bfseries\thepage}
% \makeheadrule{standard}{\textwidth}{\normalrulethickness}
\makeatother                  %

\makeatletter
\makepsmarks{standard}{
\createmark{chapter}{both}{shownumber}{\@chapapp\ }{ \quad }
\createmark{section}{right}{shownumber}{}{ \quad }
\createplainmark{toc}{both}{\contentsname}
\createplainmark{lof}{both}{\listfigurename}
\createplainmark{lot}{both}{\listtablename}
\createplainmark{bib}{both}{\bibname}
\createplainmark{index}{both}{\indexname}
\createplainmark{glossary}{both}{\glossaryname}
}
\makeatother                               %

\makepagestyle{chap} % Make new chapter pagestyle

\makeatletter
\makeevenfoot{chap}{}{\small\bfseries\thepage}{} % Define new chapter pagestyle
\makeoddfoot{chap}{}{\small\bfseries\thepage}{}  %
\makeevenhead{chap}{}{}{}   %
\makeoddhead{chap}{}{}{}    %
% \makeheadrule{chap}{\textwidth}{\normalrulethickness}
\makeatother

\nouppercaseheads
\pagestyle{standard}               % Choosing pagestyle and chapter pagestyle
\aliaspagestyle{chapter}{chap} %

%%% NEW COMMANDS
%%%------------------------------------------------------------------------------

\newcommand{\p}{\partial} %Partial
% Or what ever you want

%%% TABLE OF CONTENTS
%%%------------------------------------------------------------------------------

\maxtocdepth{subsection} % Only parts, chapters and sections in the table of contents
\settocdepth{subsection}

\AtEndDocument{\addtocontents{toc}{\par}} % Add a \par to the end of the TOC

%%% INTERNAL HYPERLINKS
%%%-------------------------------------------------------------------------------

\usepackage{hyperref}   % Internal hyperlinks
\hypersetup{
pdfborder={0 0 0},      % No borders around internal hyperlinks
pdfauthor={I am the Author} % author
}
\usepackage{memhfixc}   %

%%% THE DOCUMENT
%%% Where all the important stuff is included!
%%%-------------------------------------------------------------------------------

\author{J. Travnicek}
\title{The algorithms library toolkit}

\usepackage{lipsum} % Just to put in some text

\begin{document}

\frontmatter

\maketitle

\begin{abstract}
\lipsum[1-2]
\end{abstract}
\clearpage

\tableofcontents*
\clearpage

\chapter{Introduction}

The Algorithms Library Toolkit is a opensource project aiming to provide an implementation of algorithms from areas including automata theory, stringology, arbology and others. The project started with bachelor theses of students of Faculty of Information Technology of Czech Technical University in Prague. The original idea behind the library, formely called Automata Library, is to provided another source material for students -- show implemetation of algorithms that manipulate automata. Soon it got extended with algorithms that use automata -- mainly from the area of stringology and arbology. Later, the library was used to base implementation of some state-of-the-art algorthms including efficient determinisation of subclass pushdown automata and some tree searching and indexing algorithms.

The library is desinged to be mostly about algorithms which manipulate data and are as such stateles. Data manipulated by algorithms can vary from automata through regexps to string and others. The design allows simple extension of functionality. If a new algorithm manipulates already existing datatype, it immediately fits into the ecosystem. Of course new datatype can be introduced as well. Datatypes and algorithms are designed to be maximaly independent on each other, which allows easier maitanence.

Besides using algorithms to manipulate data, the datatypes allow casting when appropriate, i.e. DFA to NFA and similar.

The user interaction with the library is through binaries using pipes and filters philosophy, through builtin interactive command line interface, or through graphical interface.

The binaries are oldest approach of user interface suported by the library and as they are designed as filters, they use some common communication format -- xml. The binaries and command line interface providing binary are compatible, meaning the command line interface providing binary can itself be used as one of the filters. Also following the pipes and filters philosophy, each binary is accumulating some related operations and combining more binaries together allows to implement more complicated algorithms.

The command line interface binary is newer in design and it allows interaction with all algorithms through interactove command line interface. The syntax of the language similar to shell known from unix. Internally it does not use any common communication format. Such approach allows speeding up the interpretation of the algorithm description. Even though the command line interface tries to hide some implementation details, user can feel the fact that the imlementation language of the library is c++ in some cases. For example, the command line interface is aware of datatypes and it is also unable to handle templates (used to design datatypes and algorithms) othervise than statically. This however does not influence the overall functionality.

The command line interface binary can at start react to changes of algorithms provided by the library -- it detects newly registered algorithms automatically. The command line interface is planed to be extended to support procedural like language which may cause drop of backward compatibility.

A limited graphical interface allowing to desing complex algorithm is also provided. The limitation is in the number of available algorithms, which is a static subset of all algorithms. The graphical interface is planed to be extended to support all registered algorithm similarly to the command line interface.

\mainmatter

\chapter{Structure of the code}

The library consists of modules compiled to libraries and some accessors represented by binaries. Modules provide the functionality - either some core code, datatypes, or algorithms. Accessors are usually programmed as a single file with main function. The accessor binary allows interaction with implemented algorithms from bash, or other shell like environment. One more complex accessor binary \emph{aql} exists. This aql accessor itself provides  command line interface to all algorithms.

\section{Structure and overall description of modules}

Each module can be compiled separately. It shares a common makefile, which is parametrized with a configuration. Source files of the module are placed into \emph{src} directory. Modules are tested with appended unit tests. Unit tests are placed in a separate directory \emph{test-src}.

When compiled the modules object files are, depending on the target type, placed into \emph{obj-debug} or \emph{obj-release} directory. Resulting shared library is placed into \emph{lib-debug} or \emph{lib-release}. Similarly object files of unit tests are placed into \emph{obj-test-debug} or \emph{obj-test-release}. An executable binary representing unit tests can be located in \emph{tet-bin-debug} or \emph{test-bin-release} directory.

Compilation of each module requires its dependencies to be compiled as well. One can deside whether to compile only the module itself, only unit tests, or both. When both the code and tests are compiled, the tests are also executed. The respective targets are \emph{build-code-debug} (\emph{build-code-releae}), \emph{build-test-debug} (\emph{build-test-release}), or simply \emph{debug} (\emph{release}).

Compilation may be tuned with some parameters in configuration file. Library name can be specified with LIBRARY parameter, the name of the test binary with TESTBIN. Dependencies split into those of the module and some additional ones required by unit tests. Of those the compilation environment also distinguish other linked modules (LINK\_LIBRARIES) and system libraries which require to be linked to the shared library of the module (SYSTEM\_LIBRARIES). Include paths can be also specified for system libraries with SYSTEM\_INCLUDE\_PATHS. Prefix TEST\_ is used for both types of linked libraries and specification of includes for dependencies of unit tests.

\section{Existing modules}

The algorithm library toolkit consists of these modules: alib2std, alib2measure, alib2abstraction, alib2common, alib2xml, alib2data, alib2aux, alib2str, alib2raw, alib2algo, and alib2cli. Additionaly there are some more modules available mainly for testing purposes: alib2data\_experimental, alib2algo\_experimental, alib2elgo, alib2graph\_data, alib2graph\_algo, and alib2dummy.

\subsection{Standard library extensiton}
The module alib2std provides extensions to the c++ standard library. The extensition are placed in namespace \emph{ext}, not to colide with the same classes, functions ... in namespace \emph{std} and also because the standard disallowes placing anything new into the std namespace exept specilisations of templated types.

This module exists to simplify some common operations with standard library containers, to serve as a place for backported code from newer standards then used currently. To name a few exaples now consider three-way comparison of standard library containers, print of containers to standard stream with overloaded operator, implementation of copy on write shared pointer, and some standard library containers modified to store array of pointers instead of array of values, while providing almost the same interface.

To use these extended features use prepared includes. For example to use extensitions of standard vector include \emph{alib2/vector}.

\subsection{alib2measure}
The measure module contains datastructures needed for measurements. Execution of code can be measured usign this module when include \emph{measure} is used. Mmasurements are represented by frames where each frame can contain subframes. Each frame rememberes an ammount of time spend within the frame (not including the subframes), difference in memory usage caused by dynamic allocations and deallocations, and value general purpose counters.

\subsection{alib2abstraction}
Abstraction is one of the most fundamental concepts of the library. Implementation of it is generalized to a separate module to allow reuse if needed. This module greatly co-operates with alib2cli module.

Every algorithm, cast operation, and datatype implemented in the algorithm library toolkit is so called registered to the internal structures of the abstraction module. The registration allows later execution of each algorithm from the command line iterface.

The registration is achieved through construction of global variables placed to unnamed namespaces or via a function call.

\subsection{alib2common}

\subsection{alib2xml}

\subsection{alib2data}

\subsection{alib2aux}

\subsection{alib2str}

\subsection{alib2raw}

\subsection{alib2algo}

\subsection{alib2cli}

\chapter{Concepts used in the implementation}

\section{Abstraction}

As mentioned the alib2abstraction module provides a facility to register algorithms, casts, datatypes, etc... to its internal structures for later execution on demand from command line interface. Here in this section more detailed description of use and internal behavior of the abstraction concept is provided.

First the documentation focuses on the registration of algorithms, later casts and variables printing and other posibilities.

\subsection{Registration of algorithms via constructors}
Variables, when constructed, carry on information about the registered algorithm to inside of the abstraction module. Such an approach was chosen to easily hook some code before the execution of main function, so that all registrations are done beforehand at a load time of shared library.

The registration of algorithms is performed via \emph{registration::AbstractRegister} class. The class is templated with types Algorithm, ReturnType, and by means of variadic template also ParameterTypes. The Algorithm type will serve as a source of identifier naming the algorithm. ReturnType and ParameterTypes are exact types of returned value and parameters including const qualifications, reference specifiers, etc. Constructor of the class accepts a function pointer, optionaly algorithm category (unused yet), and optionaly strings representing parameter names (up to the number of parameters specified by templates). Parameter names default to arg0 to argn.

The function pointer must exactly match the requirements set up by ReturnType and ParameterTypes.

auto RegExpEmptyFormalRegExp = registration::AbstractRegister < regexp::properties::RegExpEmpty, bool, const regexp::FormalRegExp < > \& > ( regexp::properties::RegExpEmpty::languageIsEmpty );

Already registered algorithm, cast, printer of datatype can be re-registered as an algorithm. Such a registration is available via \emph{registration::WrapperRegister} class. The class is templated with types Algorithm and ParameterTypes with the same meaning as in case of AbstractRegister. The class constructor accepts a function pointer to a delegate function capable of looking up the actual registered algorthm, cast, ... Also paramter names can be specified as well.

auto xmlParse = registration::WrapperRegister < xml::Parse, ext::deque < sax::Token > \&\& > ( xml::Parse::abstractionFromTokens, "arg0" );

Last option is register a method. The class allowing this kind of registration is \emph{registration::MethodRegister}. It is parametrized again with types Algorithm, ReturnType, additionally ObjectType, and again ParameterTypes. The ObjectType is a decayed type of object on which to call the registered method. Constructor of the method registration class accepts pointer to method, string representing the method name, and optionaly names of parameters.

auto fooBar = registration::MethodRegister < Foo, int, Foo, int > ( \& Foo::bar, "bar" );

The registration::AbstractRegister and registration::MethodRegister also register the exact return type for a normalization automatically.

\subsection{Registration of algorithms via function call}
The constructors from previous section are merely a tool to call a registrator functions. If the existence of global registration object can be avoided, the respective function can be called directly. Hence any algorithm can be registered at any time before or during the execution of main function. Registration functions do not register for normalization.

The basic registration is of a callback to the algorithm. That is equivalent to use of registration::AbstractRegister class (except for the normalization). The call is to \emph{abstraction::AlgorithmRegistry::registerAlgorithm} which is parametrized with following types: Algorithm, ReturnType and ParameterTypes. As parameters the registration accepts the callback of the algorithm, the category and parameter names. The same requirements for the callback as specified for the registration via constructor apply. The parameter names are accepted in a form of standard c++ array of strings of size equal to the number of parameters.

abstraction::AlgorithmRegistry::registerAlgorithm < Divide > ( Divide::divide, abstraction::AlgorithmCategories::AlgorithmCategory::DEFAULT, std::array < std::string, 2 > ( "numerator", "denominator" ) );

The wrapper of alredy registered abstraction can be registered as algorithm via function call too. The function is \emph{abstraction::AlgorithmRegistry::registerWrapper} and it is templated by Algorithm and ParameterTypes. The call accepts a callback to the same delegate function as in the case of registration via constructor. Parameter names must be specified by a string array of size equal to the number of parameters (ParameterTypes template).

abstraction::AlgorithmRegistry::registerWrapper < xml::Compose, const Type \& > ( xml::Compose::abstractionFromType, std::array < std::string, 1 > { { "arg0" } } );

The method registration, as last of options, is done via \emph{abstraction::AlgorithmRegistry::registerMethod} function. The template parameters are Algorithm, ObjectType, ReturnType, and ParameterTypes. The call parameters are a method pointer, a method name, and parameter names.

abstraction::AlgorithmRegistry::registerMethod < ComponentName > ( getMethod, "get", emptyNames );

\section{Normalization}

\chapter{The query language}

This chapter will mostly focus on describing current status of the command line interface so called aql.

\lipsum[1-13]

\chapter{Builtin commands}

\lipsum[1-14]

\chapter{Summary on registered commands}

\lipsum[1-14]

\chapter{Introspection}

introspect algorithms
introspect algorithms automaton::
introspect overloads automaton::determinize::Determinize
introspect datatypes
introspect casts
introspect casts :from int
introspect casts :to int

\appendix

\chapter{Examples}

\section{Interactive}

execute cli::builtin::ReadFile ../examples2/automaton/DFA.txt | string::Parse @ automaton::Automaton \^{} -

\section{Command line execution}

./aql2 -p input=../examples2/automaton/DFA.txt -q 'execute cli::builtin::ReadFile \#input > \$in' -q 'execute string::Parse @ automaton::Automaton \^{} \$in'

\noindent
./aql2 -q 'execute automaton::simplify::efficient::EpsilonRemoverIncoming <\#stdin | automaton::determinize::Determinize - | automaton::simplify::Trim - | automaton::simplify::Minimize - | automaton::simplify::Normalize - >\#stdout'

\noindent
echo 'a + a' | ./aql2 -q 'execute cli::builtin::ReadFile \#stdin | string::Parse @ regexp::RegExp \^{} - | regexp::convert::ToAutomatonGlushkov (UnboundedRegExp) -'

\backmatter

%%% BIBLIOGRAPHY
%%% -------------------------------------------------------------

% \bibliographystyle{utphysics}
% \bibliography{ref}

\end{document}
