# Experiment 1: Editorial C++17 Code

This source set contains corrected implementations and correctness tests.
It does not reproduce the historical timing plots or claim a new online-judge acceptance.

## Files

- experiment1-algorithms.hpp: header-only algorithms in namespace experiment1.
- experiment1-closest-pair.cpp: complete standard-input driver.
- experiment1-tests.cpp: self-contained correctness tests; no external test framework.

## Compile

```sh
g++ -std=c++17 -O2 -Wall -Wextra -Wpedantic -Werror experiment1-tests.cpp -o experiment1-tests
./experiment1-tests
g++ -std=c++17 -O2 experiment1-closest-pair.cpp -o experiment1-closest-pair
```

Windows executables use the .exe suffix and may need the compiler runtime DLL directory on PATH.
The commands are for a working directory where all three source files are present.

On a GCC/Linux installation with sanitizer runtimes:

```sh
g++ -std=c++17 -O1 -g -D_GLIBCXX_ASSERTIONS -fno-omit-frame-pointer -fsanitize=address,undefined -fno-sanitize-recover=all experiment1-tests.cpp -o experiment1-tests-sanitized
ASAN_OPTIONS=detect_leaks=1:halt_on_error=1 UBSAN_OPTIONS=halt_on_error=1 ./experiment1-tests-sanitized
```

## Public Entry Points

- closest_squared: at most 400000 points, coordinates in [-10000000,10000000]; returns nullopt for fewer than two valid points, zero for duplicates, otherwise the minimum squared distance. Invalid ranges throw invalid_argument. The input is copied, not modified.
- Insertion, Selection, Shell_1, Shell_2, Shell_3, Mergesort: sort the entire vector<int> in ascending order. Empty vectors are valid.
- Quicksort(vector<int>&, uint32_t seed=20260911): sorts the vector and returns logical partition-tree depth (empty=0, nonempty root=1). Only the smaller side recurses, so actual stack depth is different. Duplicate keys can still cause quadratic work.
- MatchNutsBolts: equal-length arrays with one item of each distinct size on both sides. Only compare(nut,bolt) is used. Negative/zero/positive signs express size order. The comparator must be deterministic and consistent with one total size order. Objects must be copyable and swappable. Missing matches, duplicates and inconsistent partitions throw invalid_argument; arrays may be reordered before rejection. Arbitrary inconsistent comparators are outside the contract.
- Internal range and arithmetic helpers assume entry-point validation and valid half-open intervals; do not call them with arbitrary endpoints or coordinates.
- Shell increments preserve 2h, 2h+1 and 3h+1, starting at 1. Generation checks representable size_t limits before multiplication/addition.
- The driver requires 2 <= n <= 400000 and valid integer coordinates, prints D^2 and rejects malformed/missing input with exit status 1. Duplicate coordinates are an explicit extension beyond P7883's distinct-point input guarantee.

The fixed seed permits replay on the same standard-library implementation; uniform_int_distribution mappings need not match between libraries.

## Validation (2026-09-11)

Windows GCC 14.2 and Linux GCC 13.3: 202982 assertions, 4296 sorting inputs, 2018 closest-pair inputs, 16841 matching inputs including 770 rejections. The closest-pair driver has 11 additional CLI cases. Linux ASan/UBSan and library assertions passed. Windows MinGW did not include libasan/libubsan, so sanitizer claims refer only to the Linux run.

No execution timings in these checks are used as benchmark results. The historical input-size mapping, original benchmark driver, random seeds, environment, raw timings and threshold variants are still unavailable.