Skip to content

Appendix A. Writing a new structure

[Source: include/ADS/stack/MinStack.h, stack/impl/MinStack.tpp, ADT.h, Contract.h, docs/STYLE.md, docs/theory/stack.dox, test/ods_lists.cpp, test/tests.txt, bench/queues.cpp, cmake/ads_sets.txt, src/ADSBase.cppm]

We are concerned in this appendix with the steps by which a structure enters ADS, from its header to the pages of this manual, in the order in which a contributor takes them. Each step is described as the repository does it at the time of writing. Our running example is MinStack, the STACK with its least item of Morin 2013, exercise 3.14. It is small enough to be read in full (a header of 167 lines and a .tpp of 66), and yet it goes through almost all the steps: a concept that it models, contracts of three kinds, two operations with pseudocode, a lemma on its theory page, a test in the registry, a line of the module and one of the changelog. It has no benchmark, and hence §A.7 takes as its example the stacks that have one. A structure written for speed (the engineered level of §1.9) goes through the same steps, with the differences noted where they arise; the method of the benchmarks is the subject of Appendix B.

A.1 The folder and the files

A structure goes in the folder of the abstract data type that it realizes, which is also the area of its chapter. Thus, MinStack is a STACK and lives in include/ADS/stack, next to ArrayStack and MultiStack, while the queues and the deques with the minimum of exercises 3.15 and 3.16 live in include/ADS/queue. A structure that realizes no abstract data type of the book goes in the folder of the problem it solves (e.g., succinct or external). A new folder needs a new theory page (§A.5) and a row in the map of the areas of manual/build/structmap.py.

Each structure is one header, here MinStack.h, which declares the class with its contracts. At its end, the header includes the definitions of its templates from the folder impl/ next to it, here impl/MinStack.tpp. Small members (the observers, clear()) are defined in the class, while the operations that carry pseudocode and contracts are defined in the .tpp. Both files have the frame of all the sources of ADS, which opens with a box of 78 columns holding the name of the file:

/*--------------------------------------------------------------------------*/
/*---------------------------- File MinStack.h -----------------------------*/
/*--------------------------------------------------------------------------*/

After it come the comment /** @file, which Doxygen shows as the description of the header, and then the boxes DEFINITIONS, INCLUDES, NAMESPACE and CLASS MinStack. We include the headers of ADS by their path from include/ (e.g., "ADS/Contract.h"), before those of the standard library in alphabetical order. Its guard is #ifndef __ADS_MinStack, followed by the comment /* self-identification: #endif constant */. A box IMPLEMENTATION precedes the line #include "ADS/stack/impl/MinStack.tpp", and the box End File MinStack.h closes the file. As for the .tpp, it has no guard and only three boxes, that of its name, IMPLEMENTATION before the definitions and End File MinStack.tpp, and its @file comment is one sentence ("The operations of MinStack [see MinStack.h], with their contracts.").

Inside the class, the members are named f_ followed by the name of the text (f_A the items, f_M the minima, f_less the order). Furthermore, the type of the items is the alias Item, which the concepts require, and the order is a parameter C with std::less<> as its default, stored as [[no_unique_address]], whereby an empty comparator takes no room. We format the code by the rules of the repository code-style, which the continuous integration applies to each pull request (§A.10).

In the @file comment a reader learns what the structure is before reading any code, and it follows a fixed order: (i) what the header realizes and from which source, with the section or the exercise ("The STACK with the minimum of exercise 3.14 of Morin's book, beyond the book [see ADT.h]"); (ii) the representation, its invariant and the costs, each with its reason when that is not obvious (e.g., the minima are one item per record low from the bottom, hence \(n\) at most); (iii) the order of the items and the contracts, with the cost of the invariant; (iv) the \see lines of the sources; (v) the author and the copyright. In it, the words "beyond the book" mark a structure that the main textbook of the library, Montresor 2025, does not describe. Hence the tests of such a structure go in the programs of the source it comes from (§A.6), not in those of the chapters of that book (ch01 to ch19).

A structure at the textbook level follows its pseudocode line by line, and its comment states it. An engineered one, instead, cites the paper it follows, and its comment states what it changes with respect to the code of the textbook and why that change should be faster. Where the code of the textbook is available, the comment compares with it explicitly. For instance, the headers of the skip list, of the scapegoat tree, of the treap and of the left-leaning Red-Black tree each have a paragraph "Where it is meant to be faster than the ... of Morin, for the benchmarks to check", whose claims are tested by the campaign of §B.6.

A.2 The concept

A structure models the concept of its abstract data type, i.e., the names and the types of its operations (the syntactic part of the specification, in the terms of §1.2). We give the concepts of the book in ADS/ADT.h (Sequence, Set, Dictionary, Stack and Queue). Those of the interfaces of Morin's book are in ADS/set/SetInterfaces.h (USet and SSet, with the KeyedDictionary and OrderedDictionary on which DictionarySet builds them) and in ADS/sequence/IndexedList.h (IndexedList and IndexedDeque). The concept of the STACK is

template< class S >
concept Stack = requires( S s , const S cs , const typename S::Item & v )
{
 typename S::Item;
 { cs.empty() } -> std::same_as< bool >;
 s.push( v );
 { s.pop() } -> std::convertible_to< typename S::Item >;
 { cs.top() } -> std::convertible_to< typename S::Item >;
 };

and MinStack models it, since it has the type Item, empty(), push(), top() and a pop() that returns the item removed. Its min() is an addition that the concept neither requires nor forbids; hence the algorithms written on Stack (e.g., those of §3.7) run on a MinStack unchanged. A concept is checked where this is cheapest, by a static_assert in the program of the tests that includes the header:

static_assert( Stack< MinStack< int > > );

This line of test/ods_lists.cpp stands next to those of MinQueue and RealTimeMinQueue on Queue and to those of the lists of Morin on IndexedList and IndexedDeque. A wrong name or type makes the static_assert fail at compile time. However, it does not check the meaning of the operations: the axioms in the comment of each concept (for the STACK, \(\mathrm{top}( \mathrm{push}( S , v ) ) = v\) and \(\mathrm{pop}( \mathrm{push}( S , v ) ) = S\)) are checked by the tests (§A.6), and the constructive part of the specification by the contracts.

A.3 The contracts

In ADS, the contracts of an operation are its precondition, its postcondition and the invariant of the structure, in the sense of Meyer 1992. ADS checks them at run time by the four macros of ADS/Contract.h, which mirror the contracts of C++26 (Berne et al. 2025), so that the compilers that support those can replace them. All four expand to the macro ADS_CONTRACT_CHECK( level , kind , cond ), each with its level and its kind, which tests the condition under if constexpr( ADS_CONTRACTS >= level ) and, when the condition is false, calls a function of ADS::detail with the kind, the text of the condition, the function, the file and the line. ADS_PRE is checked from the level 1 and ADS_POST from the level 2, while ADS_INVARIANT and ADS_AUDIT (a precondition or a postcondition that costs more than the operation, e.g., that a vector is sorted before a binary search) are checked from the level 3. This level is the macro ADS_CONTRACTS, which is 1 by default and 0 when NDEBUG is defined (as for assert); we compile the programs of the tests at 3 and the benchmarks at 0. A violated contract throws ADS::contract_violation, a std::logic_error whose message names the kind, the condition, the function and the place. Since a condition is compiled at every level but evaluated only from its level up, it must remain correct C++ and have no side effect.

MinStack has contracts of three kinds (it needs no audit). The precondition ! f_A.empty() opens top(), min() and pop(), the three partial operations of the STACK with the minimum. Also, the postconditions of push() and pop() check that the size grows or shrinks by one, at a cost of \(O( 1 )\), as befits a postcondition. Finally, the invariant is the private member ordered(), which checks in \(O( n )\) time that the minima do not increase from the bottom and that their top is equivalent, under the order, to the least item of the vector. Indeed, the tests rely on it, since at the level 3 each push() and pop() of the test of §A.6 checks it; it is also the statement of Lemma A.1. Note that the copy of the size that the postconditions compare, [[maybe_unused]] const std::size_t n = f_A.size();, carries its attribute because the compiler would otherwise warn at the levels where no contract reads it.

A.4 The pseudocode, the code and the references

Each operation that is an algorithm (i.e., not an accessor, nor a constructor that only copies) carries its pseudocode in its comment, after the description and before \pre and \post. Its conventions are those of section 2 of docs/STYLE.md: one display \f[ \class{pseudocode}{ ... } \f], an array with the numbers of the lines in its first column and its rows ended by \cr, the keywords in \textbf{}, the calls in \mathrm{} and the assignment as \gets. Also, the comment lines stay within 79 columns, and none of them may end with a backslash. The paragraph before the display names the source ("In pseudocode (Morin, exercise 3.14), \(A\) the items and \(M\) the minima:"), and for a paper already cited by a \see line it reads "(Kahn's algorithm, beyond the book)" or the like. We write all the pseudocode in our own words, from the description of the algorithm and from the code of ADS, whatever the license of the source (the book of Montresor, under CC BY-NC 4.0, the books of Knuth, the notes of Ferragina, the papers), and cite the source in place of copying it. For MinStack the two displays read as in Algorithm A.1.

Algorithm A.1. The operations of MinStack that change it (Morin 2013, exercise 3.14); \(A\) is the vector of the items and \(M\) that of the minima.

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{push}( x ) \cr 2 & \quad \mathrm{push}( A , x ) \cr 3 & \quad \textbf{if}\ M = \emptyset\ \textbf{or not}\ \mathrm{top}( M ) < x\ \textbf{then}\ \mathrm{push}( M , x ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{pop}() \cr 2 & \quad x \gets \mathrm{pop}( A ) \cr 3 & \quad \textbf{if not}\ \mathrm{top}( M ) < x\ \textbf{then} \ \mathrm{pop}( M ) \cr 4 & \quad \textbf{return}\ x \end{array} \]

Both procedures test \(\mathbf{not}\ \mathrm{top}( M ) < x\), rather than \(x \le \mathrm{top}( M )\), since the class has only less, which is a strict weak order. This test sends to \(M\) also an item equivalent to the minimum, and this is why pop() is correct when two equal minima are on the stack:

Lemma A.1. After any sequence of operations of Algorithm A.1 on an empty MinStack, \(M\) does not increase from its bottom, and if the stack is not empty then \(\mathrm{top}( M )\) is a least item of \(A\). Moreover, \(M\) holds one item for each item of \(A\) that is not larger than all those below it, hence at most \(n\) items.

Proof. By induction on the operations, the claim being true of the empty stack. A push() of \(x\) with \(\mathrm{top}( M ) < x\) leaves both the least item and \(M\) as they were. Otherwise \(x\) is not larger than the least item of \(A\), and it goes on top of \(M\), which remains not increasing. A pop() of \(x\) finds \(\mathrm{top}( M ) \le x\) by the inductive hypothesis. If \(\mathrm{top}( M ) < x\), then \(x\) never entered \(M\) (an item enters \(M\) only when it is not larger than its top), and \(M\) stays as it is. If instead \(x\) is equivalent to \(\mathrm{top}( M )\), then \(x\) is the item that put it there or an equivalent one pushed later, which entered \(M\) too; hence popping \(M\) leaves on its top the least of the items below \(x\). Finally, the last claim follows, since an item enters \(M\) exactly when it is a record low from the bottom of \(A\). \(\square\)

Hence min() costs \(O( 1 )\) in the worst case, and push() and pop() cost \(O( 1 )\) but for the doublings of the two vectors (the header states "\(O( 1 )\) amortized time"). On a decreasing input \(M\) has \(n\) items, while on a random permutation (cf. the theory page) it has \(H_n = O( \log n )\) expected, the number of its records. Figure A.1 shows the two branches of push() and a pop() that removes a minimum.

Figure A.1. A MinStack with the items 5, 3, 7, 3 after push(9), push(2) and pop(); what each operation adds is in orange, what it reads or removes in violet, the rest in the faint tint. The 9 does not enter \(M\), while the 2 does, and leaves it with pop().

The code of the two operations is the pseudocode with the names of the class. We show it here, as the example of how a structure is written, without the contracts, which the text states (the chapters of the areas, instead, give only the pseudocode, the signatures and short examples of use, see §A.11):

f_A.push_back( x );
if( f_M.empty() || ! f_less( f_M.back() , f_A.back() ) )
 f_M.push_back( f_A.back() );
T x = std::move( f_A.back() );
f_A.pop_back();
if( ! f_less( f_M.back() , x ) )  // x is the least: it leaves
 f_M.pop_back();

These listings come from the .tpp, where two comments that change no code, the markers //! [push] and //! [pop], delimit them. Such markers are those of the command \snippet of Doxygen, and §A.11 shows how the manual extracts them.

Finally, each source of a header has its \see line, with the section, the exercise or the pages, and with the DOI whenever the work has one (e.g., doi:10.1109/2.161279 for the paper of Meyer in Contract.h). A DOI is checked on doi.org, never guessed. Morin's book is cited by the URL of its C++ edition, https://opendatastructures.org/ods-cpp.pdf, which the code of ADS follows. Indeed, the DOI of the book belongs to its edition in pseudocode (Morin 2013), whose numbering of the exercises may differ.

A.5 The theory page

An area collects its definitions, its notation, its invariants and the arguments behind its costs in a theory page, docs/theory/<folder>.dox. Section 1 of docs/STYLE.md fixes its form: one Doxygen group theory_<folder>, titled "Theory of" followed by the title of the area and placed in the group area_<folder>, with sections theory_<folder>_<name> for the definitions, the realizations and their costs, each family of algorithms, and the references. A new structure adds two things to it: (i) its row in the table of the realizations and their costs, with the reason of each cost that is not obvious; (ii) the statement on which its correctness rests, as a numbered paragraph in italics followed by its argument.

For MinStack, docs/theory/stack.dox has the row of the table in its section theory_stack_repr (two vectors, the items and the record lows). Its statement is in the section theory_stack_ods, "The stacks of Morin's book", as Lemma 3 (the minimum of a stack, exercise 3.14), with the argument of Lemma A.1; also, the theory page of the queues refers to it for the queue with the minimum, which is made of two such stacks. A header refers to its theory page by \ref, and the build of the two sites finds and links a new page with no change of docs/apiref.py. This manual supersedes the page without replacing it, since the page remains the documentation that the API reference shows next to the headers.

A.6 The tests

The tests are programs of test/, grouped by their source: ch01.cpp to ch19.cpp for the chapters of Montresor's book, ods_ints.cpp, ods_lists.cpp and ods_trees.cpp for Morin's, taocp.cpp for Knuth's, pearls_*.cpp for Ferragina's and exam_*.cpp for the exams of the course (and conclusion.cpp for the conclusion of Montresor's book). Furthermore, beyond.cpp tests what no book covers, lib_*.cpp the problems that the library adds in an area (e.g., lib_graphs.cpp), contract_<area>.cpp the contracts and the axioms of an area, interop.cpp the standard interface of the containers, and engineered*.cpp (with a few programs by family, e.g., heaps.cpp, hashing.cpp, join_trees.cpp, ordered.cpp and sorting.cpp) the engineered structures. A test is a function registered with a name by the macro ADS_TEST of test/ADSTest.h. This header also gives CHECK( c ), whose failure names its file and line, CHECK_THROWS( e , E ), which checks that a precondition throws, and scaled( n , small ), the size of a case that is there for its scale only (the build of the coverage makes it small through ADS_TEST_SMALL).

A test is named after its source, and that of MinStack is ods-ex3.14.min-stack, in test/ods_lists.cpp. It runs 4000 random operations, about 60% of which are pushes (all of them on an empty stack) of keys in \([ 0 , 50 )\), where equal minima occur often. A std::vector holds the same items, and the test compares with it the item that each pop() returns and, after each operation, the size, the top and min() (the latter against std::min_element). Then it pushes 0 to 99 in increasing order and checks by minima(), the size of \(M\), that a single minimum is kept, i.e., the bound of Lemma A.1 at its best. Since the program is compiled with ADS_CONTRACTS=3, each operation also checks the invariant of §A.3.

In test/tests.txt, the registry of the tests, there is one line per test with its program, its name and its source, e.g.,

ods_lists  ods-ex3.14.min-stack         MinStack

Both builds read it. On one side, test/CMakeLists.txt makes a program for each name of the first column and a ctest <program>.<name> for each line; on the other, the makefile builds the same programs (make) and runs the same tests (make test). Hence a new test, or a new program, takes one line of the registry and no change of either build. Note that the two build files are kept specular by hand only for what the registry cannot express, i.e., the programs of MPI (engineered_mpi, run on 1 to 4 processes), the test of the order of the includes of FastFlow and the test of the module, which both files list. Then the ctest <program>.registry (in the makefile, the target test-<program>) checks that the tests of a program, as <program> -l lists them, are those of the registry; thus, no test can be written and never run.

One runs the test of MinStack by itself with ctest --test-dir build -R ods_lists.ods-ex3.14.min-stack, or by build-make/ods_lists ods-ex3.14.min-stack after make. An exercise of a chapter of this manual names a ctest of this form, which must exist.

A.7 The benchmark

An engineered structure enters a benchmark of bench/, and so does a textbook one that has a counterpart in the standard library or in a well-known library. It goes in the program of its family, as one more structure measured on the same cases as the others. MinStack has no benchmark, since no library that ADS is compared with has a stack with the minimum; however, the other stacks of the library show the pattern. For instance, the program bench/queues.cpp has a function stack( who , n , r , make , push , pop ), which measures \(n\) pushes followed by \(n\) pops (the case push-pop) on the structure that make builds. Its main() calls it once per structure: std::stack on a std::vector twice, under the labels std::vector and std::vector A/A, then std::stack on a std::deque, boost::container::devector (if Boost is found), ADS::ArrayStack, ADS::MultiStack and ADS::RingDeque. A new stack would be one more call, with its label (e.g., "ADS::MinStack"), its constructor and its two operations as lambdas.

Three functions of bench/Bench.h do the rest. First, skip( who ) leaves out the cells of any structure other than the one that ADS_BENCH_WHO names, and under ADS_BENCH_LIST it prints the labels instead; this allows bench/run.sh to run each structure in a separate process. Then, median( prepare , work , r , ops ) times work \(r\) times, on what the untimed prepare returns, and gives the median in nanoseconds per operation. Finally, print() writes the line of a cell, separated by tabs, as ( benchmark , case , n , structure , ns/op ). A competitor that may be missing goes under a macro of the form ADS_HAS_<LIBRARY> (which the makefile sets from a variable naming its prefix or its sources) or under __has_include; hence the program builds wherever ADS does. All the benchmarks are compiled with the contracts off.

A new program bench/<name>.cpp takes four more lines. It goes in the list BENCHES of the makefile and in the foreach of the benchmarks of CMakeLists.txt, which are kept specular by hand. It also needs a line run in bench/run.sh, without which no campaign measures it, and a row in the list PAIRS of bench/summary.py for each structure of ADS that the summary of the README compares with a library. Appendix B gives the method by which these programs are run.

A.8 The module

The C++20 module ads exports all the names that the headers declare in the namespace ADS and in those nested in it, but for the namespaces detail, through the modules of the three sets of §1.9, ads.core, ads.base and ads.advanced. Their interfaces (src/ADSCore.cppm, src/ADSBase.cppm, src/ADSAdvanced.cppm and src/ADS.cppm) are not written by hand. Instead, the script cmake/ads_module_exports.py reads the AST of all the headers, as clang dumps it, and writes in the module of the set of each header a block of using-declarations, e.g.,

// stack/MinStack.h
using ADS::MinStack;

The blocks of the core are also written in ads.base and ads.advanced, which do not import ads.core, since Clang 18 does not compile a module whose global fragment includes the headers of Highway and which imports another module that included them too (the functions of Highway are static, i.e., local to each translation unit).

A new header is first given its set by a line of cmake/ads_sets.txt (e.g., stack/MinStack.h base), with a line uses if it is a base header that includes an advanced one. A header that would hold a part of each set is written as two, the base one including the advanced one at its end (e.g., graph/MaxFlow.h and graph/PushRelabel.h); a header of ADS/interop/, which includes the headers of another library, is given the set interop, which no entry point includes and no module exports, so that the script reads none of its names. Otherwise cmake/ads_sets.py stops the configuration and the make, and the job sets of the continuous integration fails. Then a new header, or one that gains or loses a public name, needs the module script to be run again (python3 cmake/ads_module_exports.py, with the flags of the optional executors when their names are to be exported). We build the modules by -DADS_BUILD_MODULE=ON with CMake, or by make test ADSMOD=1, and the tests module, module.core, module.base and module.advanced import them in place of the headers; a name that the script missed shows as a program that does not compile.

A.9 The changelog

CHANGELOG.md follows Keep a Changelog, with the changes since the last release under ## [Unreleased] and its subsections ### Added, ### Changed, ### Removed and ### Fixed; the versions follow semantic versioning. Each entry of a new structure names the header and the classes, the source (the exercise or the paper), and the tests and the benchmark that come with it. MinStack entered with the other structures of Morin's exercises, in the item that lists "MinStack, MinQueue and MinDeque (exercises 3.14 to 3.16)". An entry describes the library as it is after the change, not the steps by which the change was made.

A.10 The checks before pushing

The workflow .github/workflows/ci.yml builds all the programs and runs all the tests with g++ and clang++ on Linux, macOS and Windows (and with MSVC by CMake only), by CMake and by the makefile, with and without the backends of GMP and of a CBLAS. Its job sanitizers runs all the tests under AddressSanitizer and UndefinedBehaviorSanitizer (make test with -fsanitize=address,undefined and ADS_TEST_SMALL). Other jobs run the concurrent structures under ThreadSanitizer (threads), measure the coverage, build the module by CMake and by the makefile, run the programs of MPI on 1 to 4 processes, and build the executors and the backends that are optional (executors, backends); on a pull request, the action of code-style also checks the formatting of the lines changed.

A push is expected to leave the workflow green, and usually the cheapest way to ensure this is to run its steps first. These are make -j4 test with g++ and with clang++ (the two compilers often diagnose somewhat different errors in the templates), and the same with CXXFLAGS="-std=c++20 -O1 -g -fsanitize=address,undefined -fno-omit-frame-pointer -Wall -Wextra -DADS_TEST_SMALL", as the job does; a concurrent structure adds a run under ThreadSanitizer. CMake and the makefile define ADS_SANITIZE_ADDRESS and ADS_SANITIZE_THREAD when the options of the compiler turn a sanitizer on (the headers ask the build, never the compiler, whether one runs), and the tests of CMake are then built with ADS_TEST_SMALL; under ThreadSanitizer, ctest passes the suppressions of test/tsan.supp, for the reports whose stacks pass through OpenMP, oneTBB, Kokkos, FastFlow or Taskflow, which the sanitizer does not instrument and whose synchronization it therefore cannot see (OpenMPLock adds to the lock of OpenMP a release and an acquire that the sanitizer sees); under AddressSanitizer, those of test/lsan.supp, for the memory that Open MPI, hwloc under it and FastFlow keep until the process ends, and the programs of MPI run there without the search of leaks, since Open MPI unloads its components first and leaves their leaks with no frame that a suppression could name. Also, the files must keep their frame: no line may exceed 79 columns, and the boxes must be aligned, which a checker of the boxes, where one has it, verifies on the files changed (section 3 of docs/STYLE.md). Then the documentation must build with no warning by bash docs/build.sh, which also fails on a comment line that ends with a backslash. Section 3 of docs/STYLE.md adds the screenshots of the pseudocode on both sites, in the light and in the dark theme.

A.11 The pages of this manual

A structure enters the chapter of its area (for MinStack, Chapter 3) with the parts that manual/MAINTENANCE.md and the model chapter fix. These are the abstract data type and its axioms, the the representation and its invariant, a figure of the state before and after the operation that matters, the pseudocode, the lemmas and the theorems with their proofs, the signatures of the operations that a user calls with short examples of use, the engineered variants, and the exercises, each naming its ctest. A chapter shows no extract of an implementation, which the pseudocode replaces, and it copies neither pseudocode nor code: instead, the script manual/build/snarf.py (run by make snippets in manual/build) writes into manual/generated two kinds of files: (i) a file <File>-<name>.cpp for each pair of markers //! [name] of a .h or a .tpp, dedented and without the contracts and the copies that only they read; (ii) a file <File>-<name>.pseudo.md for each pseudocode of the comments, named after its first procedure or function. A member of a class not named as the file takes the class in front of its name, and a name that occurs twice in a header takes -2, -3, and so on.

The chapter includes these files with a line --8<-- "generated/<file>", in a separate paragraph for the pseudocode and as the only line of a fenced cpp block for the code. On the site the line is expanded by pymdownx.snippets, and in the PDF by build/snippets.lua. For instance, §A.4 includes in this way MinStack-push.pseudo.md and MinStack-pop.pseudo.md, and, as the example of this appendix only, MinStack-push.cpp and MinStack-pop.cpp. A function whose comment has no pseudocode gets one in its header (a change of the comments only) before a chapter describes it.

A figure is a standalone TikZ file, manual/figures/<area>-<name>.tex (here stack-min.tex), that loads lmodern, amsmath and amssymb, tikz and lamalunga, and then inputs tikz-ads.tex. It draws with the styles of that file only: touched (with its variants for nodes, vertices and edges) for what the operation reads or follows, added for what it adds, and cell, node, vertex, edge and free for the rest, with no outline and no colour outside the palette that lamalunga computes from the primary. Then make figures writes its .pdf and its .svg, and the chapter shows it in a separate paragraph, ![Figure N.M. caption](../figures/<name>.svg){#fig-N-M}.

A work that the chapter cites goes in manual/chapters/Z-bibliography.md, in alphabetical order, with the anchor ref-<surname><year> and its DOI. Two checks follow by make check: build/bibcheck.py verifies that the bibliography holds all the works of the \see lines of the headers, of the theory pages and of the README, and build/structmap.py that each header and each public class appears in the map of the structures of §1.12, whose tables it also writes. Then we build the chapter with the others by make pdf, which must give no overfull box and no undefined reference after a second run of LaTeX, and by make html; we check its prose on the PDF against the conventions of the front matter.

A.12 Checklist

Table A.1 collects the files that a new structure touches, with the check by which one verifies each step; its last column gives what MinStack has for each of them.

Table A.1. The files of a new structure, in the order of this appendix, with the check of each step and the corresponding file or entry of MinStack.

Step File Check MinStack
header include/ADS/<area>/<Name>.h boxes, 79 columns stack/MinStack.h
operations include/ADS/<area>/impl/<Name>.tpp contracts at level 3 stack/impl/MinStack.tpp
concept a test program static_assert Stack< MinStack< int > >
pseudocode the comments of the header docs/build.sh push(), pop()
theory docs/theory/<area>.dox docs/build.sh Lemma 3 of stack.dox
test test/<source>.cpp, test/tests.txt <program>.registry ods_lists.ods-ex3.14.min-stack
benchmark bench/<family>.cpp, bench/run.sh, bench/summary.py a campaign (Appendix B) none
set and module cmake/ads_sets.txt, src/ADSBase.cppm the tests sets.* and module.* stack/MinStack.h base, using ADS::MinStack;
changelog CHANGELOG.md under [Unreleased] exercises 3.14 to 3.16
manual manual/chapters/NN-<area>.md, manual/figures make check, make pdf stack-min.tex, two pseudocodes