Layout

Headers are grouped by abstract data type, one header per realization, and include/ADS/ADT.h has the concepts of the book. The folders of the types (sequence/, stack/, queue/, tree/, dictionary/, set/, priority/, mfset/ and graph/) also hold the algorithms on them, e.g., the operations on sets or the visits of a graph. The other folders group the algorithms by technique or by problem:

  • search/ and sort/, the searches and the sorts;

  • numeric/, the products of integers, polynomials and matrices;

  • string/, the algorithms on strings;

  • optimization/, the problems of optimization (knapsack, intervals);

  • geometry/, the convex hull;

  • backtrack/, the enumerations by backtrack;

  • complexity/, the problems of NP and their reductions;

  • intractable/, the techniques for the intractable problems;

  • memory/ and concurrent/, the allocators, the arena, the queues between threads and the concurrent hash table;

  • external/, the two-level memory and the algorithms on it;

  • compression/ and succinct/, the codes, the compressors and the compressed data structures;

  • combinatorial/, the broadword tricks and the combinatorial generation;

  • algorithm/, the rest.

A header is included by its path (e.g., #include "ADS/graph/ListGraph.h") and includes what it needs. It declares its classes and functions, with their contracts, and the definitions of its templates are in the folder impl/ next to it (e.g., ADS/graph/impl/ListGraph.tpp), included at the end of the header, as in Boost; hence, include/ is the whole library.