Repository navigation
Releases
Releases · dmeoli/ADS
ADS 0.1.0
Added
Organization of the library
- a header-only C++20 library of 445 public headers in
include/ADS, one
directory per area, each in one of the sets ofcmake/ads_sets.txt:
base(245 headers, the structures and the algorithms that follow a
textbook or an academic source),advanced(153, those written for speed
beyond these sources, the concurrent and parallel structures, the
executors, the distributed layer, the typed modifications and the
observers),core(19, the infrastructure of both) andinterop(28,
the adapters to other libraries); the entry pointsADS/core.h,
ADS/base.h,ADS/advanced.handADS/ADS.h
Structures and algorithms of the textbooks
- the abstract data types of A. Montresor, Algoritmi e Strutture Dati
(2025), each a concept ofADT.h, realized after the pseudocode and the
names of the book (sequence/,stack/,queue/,tree/,
dictionary/,set/,priority/,mfset/,graph/), with the
algorithms of its chapters (algorithm/,search/,sort/,
optimization/,backtrack/,complexity/,intractable/) and its
exercises as tests - the structures of P. Morin, Open Data Structures, e.g.,
RootishArrayStack,DualArrayDeque,SEList,ScapegoatTree,
MeldableHeap,XFastTrieandYFastTrie - from The Art of Computer Programming: the multiple-precision arithmetic
(BigInteger,Rational), the sorts and the searches of volume 3
(sort/KnuthSorts.h,search/KnuthSearches.h,LoserTree), the
broadword operations and the combinatorial generation (combinatorial/),
the dancing links (ExactCover) and the satisfiability solvers
(backtrack/SatSolvers.h) - from the notes of P. Ferragina on algorithm engineering: the two-level
memory and its algorithms (external/), the integer codes,PGMIndex,
rank and select, Elias-Fano and the suffix arrays
Engineered structures
- sequences and dictionaries:
SmallVector,TieredVector,RingDeque,
Fenwick;FlatHashTableandPointerTable(open addressing on groups
of tags compared by vector instructions),DenseHashMap,
BucketCuckooTable,FastHash, the minimal perfect hash functions
RecSplitandMinimalPerfectHash,AdaptiveRadixTree,
SuccinctPatriciaTrieandBTreeMap - trees: the balanced trees whose only balancing is join
(tree/JoinTree.h), with split, union, intersection and difference in
the optimal work, batches and augmented maps;SplayTree,LinkCutTree,
IntervalTreeandRangeTree - sets and priority queues:
BlockedBloomFilter,CuckooFilter,
RibbonFilter,BinaryFuseFilter,PrefixFilter, the range filter
GrafiteFilter,RoaringBitmap;DaryHeap,IndexedDaryHeap,
PairingHeap,RadixHeap,BucketQueue,MinMaxHeap,SequenceHeap;
UnionFind,RemUnionFindandRollbackUnionFind - sorting and searching:
sort()andstableSort()(sort/Sort.h), which
choose among a pdqsort partitioned by blocks, the radix sorts of integers
and floating-point numbers and the sorts of strings; the sample sort, the
learned sort and the vector quicksort;DynamicPGMIndex,
CompressedPGMIndex,search/StaticSearch.hand
search/RangeMinimum.h - strings, compression and succinct structures:
AhoCorasick,
SuffixAutomaton,string/SuffixSorting.h; rANS and tANS
(ransCompress(),tansCompress()),streamVByteEncode(), the r-index
(RIndex,MoveRIndex);RRRBitVector,PartitionedEliasFano,
WaveletMatrix,LAVector,K2Tree,BVGraphandPackedArray - graphs and numerics:
StaticGraph(compressed rows),GridGraph,
GraphBuilder, the maximum flow ofFlowNetworkby push-relabel,
Assignment, the matchings of Edmonds;DenseMatrix,CsrMatrix,
SellMatrix,DynamicCsrandgemm() - memory:
Arena,ObjectPool,ConcurrentPoolResource,PageHeap,
PoolAllocator,SizeClassAllocator,HugePageAllocator, and the files
of records ofRecordFilefor the external memory
Parallelism, concurrency and distribution
- the executors of one concept (
parallel/Executor.h):Sequential,
ThreadPool(work stealing onstd::thread) and, as options,
OpenMPExecutor,TBBExecutorandFastFlowExecutor, so that a program
that already has one of these runtimes does not start a second one; the
loops, the reductions (whose blocks do not depend on the number of
threads) and the prefix sums on them - on any executor: the parallel sorts and merges, the products of sparse
and dense matrices, the visit in breadth that optimizes its direction,
the components by Afforest, the shortest paths by Delta-stepping and
rho-stepping, the LCP array, the greedy algorithms,
speculativeFor(), the builds of the succinct structures, the
long-lived workers ofrun(), the channels ofparallel/Channels.h,
feedbackFarm()and theMailboxthat detects the termination - the concurrent structures of
concurrent/, among themSPSCQueue,
MPMCQueue,WorkStealingDeque,EventCount,MultiQueue,
StealablePriorityQueue,LockFreePriorityQueue,ConcurrentFlatTable,
ConcurrentCuckooTableandConcurrentUnionFind - with
ADS_WITH_MPI, the processes of MPI as workers (MPIExecutor,
MPIMailbox, with the termination by the four counters of Mattern,
DistributedMin) and the sort by regular sampling of
distributed/DistributedSort.h, also on a communicator of Boost.MPI
Typed modifications and reoptimization
- the typed modifications of
Modification.h: the events ofADS::mod
(Inserted,Erased,Changed,BulkInserted,Rebuilt, and so on),
declared by each structure as a type list, the subject policies
NoObservers,Static,DynamicandBoth, the groups ofbatch()
coalesced into their net effect,quiet()andUndoLog; with
NoObserversa structure compiles to the code of the plain one ObservableandObservedGraph, and the observers of
graph/Reoptimization.h(ShortestPathsObserver,
SpanningForestObserver,MaxFlowObserver,AssignmentObserver), which
keep a solution with a certificate of its optimality across the changes
of a graph and tell byoutcome()whether the last solve was certified,
warm or from scratch, asRatioPolicydecides- the warm starts of LEMON (
interop/lemon/Warm.h,ADS_LEMON_SHIM):
runWarm()onNetworkSimplex,CostScaling,CycleCanceling,
CapacityScalingandPreflow, the changes of one arc or node in
constant time (warmCost(),warmUpper(),warmSupply()), and
PreflowEngine,NetworkSimplexAssignmentandMinCostFlowObserver
on them
Contracts, capabilities and persistence
- design by contract on the whole library (
Contract.h):ADS_PRE,
ADS_POST,ADS_INVARIANTandADS_AUDIT, evaluated up to the level
ADS_CONTRACTSchosen at compile time (1 by default, 0 withNDEBUG),
a violation throwingADS::contract_violation - the capabilities of
Capabilities.h, which the algorithms query at
compile time: the conceptssplittable,addressableandundoable,
the opt-inenable_stable_references,query(),decrease_key_of()
and the customization pointsreserve,prefetchandinsert_bulk - the interface of the standard containers, with iterators of the
strongest category that each structure allows (Iterators.h), so that
the algorithms ofstd::rangesand of Boost run on them store(),restore()andrestoreMapped()of the static structures
that modelPersistent(external/Persistence.h), in a versioned
format with a checksum;restoreMapped()maps the file (MappedFile)
and opens a structure of any size in constant time, with no copy- the primitives that the compilers spell each in their own way in one
form (Portable.h,Wide.h), with no test on the platform, the
compiler or the architecture in any header; the vector kernels (the
hash tables, the filters, the edit distance, the search of many
patterns, the suffix sorting, the integer codes) on Google Highway with
scalar fallbacks (Simd.h,SimdInline.h), and the layouts of the hash
tables under an inline namespace (Abi.h), so that units built with
different options link into one program
Interoperation
- GMP for
BigIntegerandRational, a CBLAS forgemm(), the headers
of Boost, Highway and hwloc, eachAUTOby default (ADS_WITH_GMP,
ADS_WITH_BLAS,ADS_WITH_BOOST,ADS_WITH_HIGHWAY,
ADS_WITH_HWLOC), the code of ADS running without them - Boost.Graph, Boost.Heap and Boost.Unordered (
interop/boost/): the
algorithms of Boost.Graph on the graphs of ADS and vice versa, the heaps
of ADS in its Dijkstra, those of Boost.Heap as frontiers of ADS, and
FastHashas a hasher; LEMON (interop/lemon/,ADS_WITH_LEMON, the
targetADS::LEMON): the heaps and the maps of ADS in its algorithms,
the graphs both ways, its notifiers told to the observers of ADS - the executors on the runtimes of a program (
interop/parallel/): the
parallel algorithms of the standard library, stdexec, Taskflow and Kokkos
(ADS_WITH_STDPAR,ADS_WITH_STDEXEC,ADS_WITH_TASKFLOW,
ADS_WITH_KOKKOS) - Eigen, METIS, KaHIP, SuiteSparse:GraphBLAS, NetworKit, CRoaring,
sdsl-lite 3 and cereal (ADS_WITH_EIGEN,ADS_WITH_METIS,
ADS_WITH_KAHIP,ADS_WITH_GRAPHBLAS,ADS_WITH_NETWORKIT,
ADS_WITH_CROARING,ADS_WITH_SDSL,ADS_WITH_CEREAL), the C Data
Interface of Apache Arrow,std::flat_mapandstd::pmr
(interop/std/); each targetADS::<name>is linked only by a program
that asks for it - the C++20 modules
ads,ads.core,ads.baseandads.advanced
(ADS_BUILD_MODULE, with CMake 3.28, Ninja and Clang 16 or GCC 15, or
make ADSMOD=1), as the targetsADS::ADS_moduleand those of the sets - the Python package
ads-python(python/) on nanobind, with the
arrays of the structures as read-only views of NumPy, `re...