. "$BST_LIB"
# BST-TIMEOUT: 900  # THREE python3 starts, and they are the whole cost.
#                   # Everything else reads the filesystem or dpkg with shell
#                   # builtins, or greps one probe transcript.
#                   #
#                   # The three: a bare `import sortedcontainers', a second
#                   # import whose STDERR is the assertion, and the probe --
#                   # which takes ONE start for 303 measurements. This package
#                   # ships NO executable and NO test package, so unlike
#                   # 99-python3-docopt there is no shipped program to run as a
#                   # real process and no exit status to assert, and unlike
#                   # 99-python3-isodate there is no upstream unittest suite to
#                   # run: nothing here needs a fourth start.
#                   #
#                   # The work inside a start is a few thousand comparisons over
#                   # containers of at most a few dozen small ints and strings,
#                   # plus three seeded randomised sequences of 4000, 3000 and
#                   # 3000 operations. All of it measures 0.09s on the x86-64
#                   # control -- microseconds beside an interpreter start on this
#                   # arm, which is tens of seconds before the first line of the
#                   # program runs.
#                   #
#                   # 900 is 300s per start, against the ~60s a python3 start has
#                   # measured at here. The start dominates; the stress loops are
#                   # linear in their operation counts and nothing in this file
#                   # is quadratic in anything.
#                   #
#                   # NOT MEASURED ON TARGET YET: this port's first on-target run
#                   # is the batch verify. The measured elapsed goes in the test
#                   # plan rather than in this comment, which would cost an image
#                   # build to keep the shipped suite byte-identical.
#
# python3-sortedcontainers 2.4.0 (poky/meta
# recipes-devtools/python/python3-sortedcontainers_2.4.0.bb, `inherit pypi
# setuptools3', PyPI sdist) on the wasm32-hwjs glibc image.
#
# ============================================================================
# WHAT THE PACKAGE IS, AND WHY THE CONTAINER IS ASSERTED AND NOT THE RETURN.
# ============================================================================
#
# sortedcontainers is three container types -- SortedList, SortedSet,
# SortedDict -- that keep their elements in order across insertion and deletion,
# and add to that order the three things a `list`, a `set` and a `dict` do not
# have: an INDEX, a BISECTION and a RANGE.
#
# Its subject is therefore an INVARIANT, not a return value. The invariant is
# maintained across a mutation rather than computed by one, and the three
# methods a caller uses most all return None: `add`, `remove`, `discard`. A
# suite that asserted only what each call gave back would assert nothing at all
# about them, and a container that silently stopped sorting would pass every
# case.
#
# So every mutation sequence in the probe emits the WHOLE CONTAINER after EVERY
# step, and the cases below compare those. The repr names the class, which is
# the second half of the same point: `SortedList([1, 2, 3])` and `[1, 2, 3]` are
# different strings, so a method that returned a plain list instead of keeping
# the type cannot pass by looking equal.
#
# ============================================================================
# THE FIXTURES ARE OUT OF ORDER AND CARRY DUPLICATES, DELIBERATELY.
# ============================================================================
#
# `[5, 1, 4, 1, 3, 2]` is the constructor fixture for both SortedList and
# SortedSet. Out of order, so a container that merely stored what it was handed
# fails; with a duplicate, so the two types' answers DIFFER -- the list keeps
# both 1s and the set collapses them -- and the pair of cases says which type
# was actually built.
#
# The same reasoning runs through the whole file. `bisect_left` and
# `bisect_right` are asserted around a value that appears three times, because
# they differ ONLY where the value is present and by exactly the number of
# copies of it; on a fixture without duplicates the two are the same number and
# a suite could not tell one from the other. `irange` is asserted with all four
# combinations of inclusive endpoints, because that argument is the one a caller
# gets wrong. And `SortedKeyList` is exercised with a key that REVERSES the
# natural order, so a comparator that ignored the key surfaces as a wrong ORDER
# -- something a reader can act on -- rather than as a still-sorted container
# that passes.
#
# ============================================================================
# THE ONE THING THAT COULD NOT BE ASSERTED, AND WHY IT IS SAID HERE.
# ============================================================================
#
# A KEYED SortedSet's order among EQUAL keys is not defined and not stable.
# SortedSet holds a builtin `set` beside its ordered list and builds the ordered
# half by iterating that set, so equal-keyed values reach the comparator in HASH
# order -- which for str is randomised per process by PYTHONHASHSEED. Measured
# on the x86-64 control: `SortedSet(["bb", "a", "ccc", "dd"], key=len)` answers
# `['a', 'bb', 'dd', 'ccc']` on some runs and `['a', 'dd', 'bb', 'ccc']` on
# others, from the same input in the same interpreter.
#
# A case pinning a tie order would therefore have red at random on an image
# where nothing had changed -- the worst kind of red, because it is
# indistinguishable from a real one until someone re-runs it. `ss-keyed` uses
# four DISTINCT key lengths instead, and `ss-keyed-tie-keys` asks the tie
# question in the only form that has an answer: the sequence of KEYS is defined,
# the order of values within a key is not.
#
# ============================================================================
# THE DOCUMENTED PROGRAMMER ERROR IS A CASE, AND IT IS NOT AN EXCEPTION.
# ============================================================================
#
# The package documents that a value must not be mutated, while it is in a
# container, in a way that changes its order: the container cannot observe the
# change, so its index goes stale. It does NOT detect this and does NOT raise --
# and that is the point of the `mut-*` cases, which pin what the package DOES.
#
# The container still prints the moved element in its old position
# (`mut-broken-repr`), `index` of it raises ValueError while `in` answers False
# and `len` is unchanged, and the package's own internal audit `_check()` is
# what finally says the structure is broken. That last one is asserted in a
# pair: the audit fails on the mutated container AND passes on an intact one,
# because without the second half the first would pass on a `_check` that raised
# unconditionally.
#
# A release that started detecting the mutation and raising would red here, and
# should: that is a behaviour change a caller must know about.
#
# ============================================================================
# WHY IT PORTS AT ALL: PURE PYTHON, AND NOT ONE DEPENDENCY.
# ============================================================================
#
# This image's python3 is ONE STATIC BINARY with an EMPTY lib-dynload and no
# dynamic loader (BRINTOS-1476; 99-python3 asserts both directly), so a module
# carrying a compiled extension could not be imported here -- not "would be
# slow", could not be imported. sortedcontainers ships four .py files and no C:
# the built wheel says `Root-Is-Purelib: true` and `pkg-only-python` below says
# the same thing about what actually landed on the image.
#
# That is unusual for a container library, and it is the package's own stated
# selling point -- "fast as C-extensions" WITHOUT a C extension -- which is why
# this port needed no bbappend, no patch and no site answer.
#
# Its dependency list is empty: `install_requires=[]` upstream, and `Depends:
# python3-core` and nothing else in the built .deb. `pkg-depends-exactly-core`
# asserts that as an equality rather than as a substring, so a release that
# ACQUIRED a dependency reds here -- on this image, where an unsatisfied import
# is the failure it would become.
#
# `no-third-party-import` is the runtime half of the same statement, and it is
# measured rather than declared: the probe snapshots sys.modules before the
# import and reports any module that appeared afterwards which is neither
# sortedcontainers itself nor a name in `sys.stdlib_module_names`. It names the
# offender rather than only failing.
#
# ============================================================================
# WHAT THIS SUITE DELIBERATELY DOES NOT MEASURE.
# ============================================================================
#
# Performance. The package exists to be fast and its load-factor machinery is
# there for that, but a timing assertion on this arm would measure the wasm32
# runtime and whatever else the host is doing, not the library, and would red at
# random. `sl-default-load-factor` and `sl-load` assert that machinery as VALUES
# instead -- 1000, a constant of the package -- and `sl-big-*` exercises the
# multi-sublist path a 3000-element container actually takes, which is where a
# rebalance bug would live. That is the part of the subject that is a fact about
# the package rather than about the machine it ran on.


P=python3-sortedcontainers

# The suite canary: emitted before anything can fail, so a runner that saw this
# file at all is distinguishable from one that did not. Every case below it is
# then a statement about the package rather than about whether the suite ran.
bst_ok $P/suite-canary

require python3 $P/python3-present

SITE=/usr/lib/python3.12/site-packages
PKGDIR=$SITE/sortedcontainers
DI=$SITE/sortedcontainers-2.4.0.dist-info
PKGLIST=/var/lib/dpkg/info/python3-sortedcontainers.list
PROBE=$BST_DATA/python3-sortedcontainers-probe.py
tmp=${TMPDIR:-/tmp}
W=$tmp/bst-sortedcontainers.$$
mkdir -p "$W" || { bst_notok $P/workdir "cannot create $W"; exit 0; }

# ============================================================================
# WHERE IT LANDED. The packaging's own claim, checked against the filesystem.
# ============================================================================
check $P/site-packages-dir test -d "$SITE"

# A PACKAGE, NOT A FLAT MODULE. sortedcontainers is a directory with an
# `__init__.py`, and `no-flat-module` is the other half of that: a build that
# had installed a single `sortedcontainers.py` beside it would shadow one with
# the other depending on sys.path order, which is a fault nobody can see.
check $P/package-dir  test -d "$PKGDIR"
check $P/package-init test -s "$PKGDIR/__init__.py"
check $P/no-flat-module test ! -f "$SITE/sortedcontainers.py"

# FOUR MODULES AND NO MORE. Named one at a time rather than counted, so a red
# says WHICH one did not ship.
for _m in sorteddict sortedlist sortedset; do
  check $P/module-$_m test -s "$PKGDIR/$_m.py"
done

# The byte-compiled forms ship too -- python3 cannot write them on this image's
# read-only /usr, so a package that omitted them would re-parse ~118 KB of
# source at every interpreter start.
check $P/pycache test -s "$PKGDIR/__pycache__/__init__.cpython-312.pyc"
for _m in sorteddict sortedlist sortedset; do
  check $P/pycache-$_m test -s "$PKGDIR/__pycache__/$_m.cpython-312.pyc"
done

# NO TEST PACKAGE. Upstream's `setup.py` names only `packages=['sortedcontainers']`
# and its tests live outside the sdist entirely, so unlike python3-isodate there
# is nothing shipped here for a probe to run. Asserted rather than left to be
# inferred from an absent case -- and it is what says the ~300 cases in this file
# are the whole of the evidence for this port.
check $P/no-tests-dir test ! -d "$PKGDIR/tests"

# ============================================================================
# WHAT THE PACKAGE SHIPS, read from dpkg's own file list rather than from the
# filesystem -- so this says what THIS package installed, not what happens to
# be present.
# ============================================================================
cat "$PKGLIST" > "$W/pkgf" 2>/dev/null || : > "$W/pkgf"
check $P/pkg-list-present test -s "$W/pkgf"

# NO SHARED OBJECT. The image's python3 has an empty lib-dynload and no dynamic
# loader, so an extension module here would not be slow, it would be
# unimportable. This is the packaging-side statement of that; `submodules-all-py`
# in the probe is the runtime-side one.
check_eq $P/pkg-no-so "" \
  "$(grep -E '\.so($|\.)' "$W/pkgf" 2>/dev/null)"

# AND NO EXECUTABLE. `setup.py` declares neither `scripts` nor
# `console_scripts`, so nothing lands in ${bindir} and there is no shebang to
# patch -- the same shape as python3-isodate and the opposite of
# python3-docopt.
check_eq $P/pkg-no-bin "" \
  "$(grep -E '^/usr/s?bin/' "$W/pkgf" 2>/dev/null)"

# EVERYTHING IT SHIPS IS PYTHON. Anything that is not a .py, a .pyc or a
# dist-info file is named in the failure, so a red says what the stray file was.
_bad=""
while IFS= read -r _f; do
  [ -f "$_f" ] || continue
  case "$_f" in
    *.py|*.pyc)      continue ;;
    */__pycache__/*) continue ;;
    */*.dist-info/*) continue ;;
  esac
  _bad="$_bad $_f"
done < "$W/pkgf"
check_eq $P/pkg-only-python "" "$_bad"

# ============================================================================
# THE DIST-INFO. The build's statement about what it installed, which is a
# different source from the package's own `__version__` -- the two are
# cross-checked, and a recipe that packaged one version's source under another
# version's metadata fails the pair while passing each half alone.
# ============================================================================
check $P/dist-info-dir      test -d "$DI"
check $P/dist-info-metadata test -f "$DI/METADATA"
check_out $P/dist-info-version "Version: 2.4.0" cat "$DI/METADATA"
check_out $P/dist-info-name "Name: sortedcontainers" cat "$DI/METADATA"
check_out $P/dist-info-top-level "sortedcontainers" cat "$DI/top_level.txt"

# PURE PYTHON, IN THE BUILD'S OWN WORDS. `Root-Is-Purelib: true` and a
# `py3-none-any` tag are what a wheel says when it carries no compiled code and
# is valid on any platform -- which is the whole reason this package ports to
# wasm32 unchanged.
check_out $P/dist-info-purelib "Root-Is-Purelib: true" cat "$DI/WHEEL"
check_out $P/dist-info-tag "Tag: py3-none-any" cat "$DI/WHEEL"

# THE LICENCE SHIPS. `MANIFEST.in` includes it and bdist_wheel puts it in the
# dist-info, so it is on the image -- the opposite of python3-isodate, whose
# dist-info carries none. Stated as a fact about this package rather than
# assumed from the sibling.
check $P/dist-info-license test -s "$DI/LICENSE"
check $P/dist-info-record  test -s "$DI/RECORD"

# ============================================================================
# WHAT DPKG THINKS. Installed, and depending on exactly one thing.
# ============================================================================
sed -n '/^Package: python3-sortedcontainers$/,/^$/p' /var/lib/dpkg/status > "$W/st" 2>/dev/null
check $P/pkg-known test -s "$W/st"
check_out $P/pkg-installed "Status: install ok installed" cat "$W/st"

# AN EQUALITY, NOT A SUBSTRING. `install_requires` is empty upstream and the
# built .deb depends on python3-core alone. Asserting the exact line is what
# makes a release that ACQUIRED a dependency red here -- on the image, where an
# unsatisfied import is what it would become -- rather than passing a
# `contains python3-core` check unchanged.
grep '^Depends:' "$W/st" > "$W/dep" 2>/dev/null || : > "$W/dep"
check $P/pkg-depends-line test -s "$W/dep"
check_eq $P/pkg-depends-exactly-core "Depends: python3-core" "$(cat "$W/dep")"

# ============================================================================
# THE IMPORT, TWICE AND SEPARATELY.
# ============================================================================
# The first says it imports at all. The second says it does so QUIETLY: a
# DeprecationWarning or a stray print on import would be invisible to the first
# and would land in the middle of the output of every program that used the
# package.
check $P/import python3 -c 'import sortedcontainers'
check_eq $P/import-quiet "" \
  "$(python3 -c 'import sortedcontainers' 2>&1)"

# ============================================================================
# THE PROBE. One interpreter start for everything below.
# ============================================================================
if [ ! -f "$PROBE" ]; then
  bst_notok $P/probe-present "$PROBE did not ship"
  rm -rf "$W"
  exit 0
fi
bst_ok $P/probe-present

bst_probe $P/probe-run "$W/probe" 600 python3 "$PROBE"

OUT="$W/probe"

# One transcript line per measurement, `key=value`. `head -n 1` is not
# defensive dressing: a probe that somehow emitted a key twice would otherwise
# feed check_eq a two-line string and red with an unreadable detail.
pv() { grep "^$1=" "$OUT" 2>/dev/null | head -n 1 | cut -d= -f2-; }

# NOTHING BELOW IS SCORABLE IF THE PROBE PRINTED NOTHING, and this is the case
# that says so. Without it, ~300 cases red with got:'' and a reader has to work
# out from the pattern that python3 never started.
if [ -s "$OUT" ]; then
  bst_ok $P/probe-output
else
  bst_notok $P/probe-output "the probe emitted nothing -- python3 did not start, or died before its first line; every CASE below is unscorable"
fi

# THE TWO TRAILER CASES, asserted before anything they guard. `probe-complete`
# says the probe reached its last line; `emitted-count` says nothing between
# the first key and that line was skipped. Together they make every got:'' below
# readable as a missing KEY rather than as a missing RUN.
check_eq $P/probe-complete "yes" "$(pv probe_done)"
check_eq $P/emitted-count "303" "$(pv emitted_count)"

# The import inside the probe is its own case: an import failure there would
# otherwise be ~300 identical reds with nothing saying which was the cause.
check_eq $P/probe-import "yes" "$(pv import_ok)"

# THE MODULE THE PROBE ACTUALLY IMPORTED IS THE ONE THE PACKAGE INSTALLED.
# This is what ties every measurement below to the .deb rather than to some
# other copy that happened to be earlier on sys.path.
check_eq $P/module-answered "$PKGDIR/__init__.py" "$(pv module_file)"

# ============================================================================
# THE MODULE'S IDENTITY, AND THE VERSION READ THREE WAYS.
# ============================================================================
# `dunder-version` is a literal in the package's own `__init__.py`;
# `dist-info-version` above was written by the build; and `dunder-build` is the
# same version packed as hex, 0x20400 for 2.4.0 -- the reading that would
# survive a search-and-replace over the string. Three sources that must agree,
# and a recipe that packaged one version's source under another version's
# metadata disagrees on the first pair while passing each of them alone.
check_eq $P/is-package "yes" "$(pv is_package)"
check_eq $P/dunder-version "2.4.0" "$(pv dunder_version)"
check_eq $P/dunder-title "sortedcontainers" "$(pv dunder_title)"
check_eq $P/dunder-author "Grant Jenks" "$(pv dunder_author)"
check_eq $P/dunder-license "Apache 2.0" "$(pv dunder_license)"
check_eq $P/dunder-build "0x20400" "$(pv dunder_build)"

# THE PUBLIC SURFACE. Sorted, so the assertion does not depend on the order the
# names were written in `__all__`. Eight names: the three container types, the
# keyed list and its 1.x alias, and the three view types SortedDict returns.
check_eq $P/all-count "8" "$(pv all_count)"
check_eq $P/all-sorted "SortedDict,SortedItemsView,SortedKeyList,SortedKeysView,SortedList,SortedListWithKey,SortedSet,SortedValuesView" "$(pv all_sorted)"

# FOUR MODULES IN THE PROCESS, ALL OF THEM PYTHON. `submodules-all-py` is the
# runtime half of `pkg-no-so` above: every sortedcontainers module that reached
# this interpreter came from a .py or its .pyc, so none of them was a builtin or
# an extension -- which on this image could not have loaded at all.
check_eq $P/submodule-count "4" "$(pv submodule_count)"
check_eq $P/submodules "sortedcontainers.sorteddict,sortedcontainers.sortedlist,sortedcontainers.sortedset" "$(pv submodules)"
check_eq $P/submodules-all-py "yes" "$(pv submodules_all_py)"
check_eq $P/no-third-party-import "yes" "$(pv no_third_party_import)"

# ============================================================================
# SortedList: THE CONSTRUCTOR.
# ============================================================================
# The fixture is out of order and carries a duplicate, so a container that
# merely stored what it was handed fails here rather than three sections later.
# `sl-ctor-input-untouched` is the other half: a constructor that sorted its
# argument in place would pass every ordering case in this file and quietly
# corrupt the caller's list.
check_eq $P/sl-ctor "SortedList([1, 1, 2, 3, 4, 5])" "$(pv sl_ctor)"
check_eq $P/sl-ctor-empty "SortedList([])" "$(pv sl_ctor_empty)"
check_eq $P/sl-ctor-str "SortedList(['a', 'a', 'a', 'b', 'n', 'n'])" "$(pv sl_ctor_str)"
check_eq $P/sl-ctor-input-untouched "[3, 1, 2]" "$(pv sl_ctor_input_untouched)"
check_eq $P/sl-len "6" "$(pv sl_len)"
check_eq $P/sl-default-load-factor "1000" "$(pv sl_default_load_factor)"
check_eq $P/sl-key-is-none "yes" "$(pv sl_key_is_none)"
check_eq $P/sl-type-name "SortedList" "$(pv sl_type_name)"

# ============================================================================
# SortedList: add, update -- AND THE THREE list METHODS IT REFUSES.
# ============================================================================
# The container is emitted after EVERY step, because `add` and `update` both
# return None and there is nothing else to assert. Four insertions chosen for
# four positions: into the middle, before everything, after everything, and a
# duplicate -- which is KEPT, not collapsed, and that is what separates this
# type from SortedSet.
#
# `append`, `insert` and `reverse` are inherited names a sorted list CANNOT
# honour: each would put an element somewhere other than where it belongs. The
# package raises NotImplementedError rather than silently sorting, which is the
# right choice and the first thing a caller migrating from `list` trips over.
check_eq $P/sl-add-0 "SortedList([1, 4, 5])" "$(pv sl_add_0)"
check_eq $P/sl-add-1 "SortedList([1, 3, 4, 5])" "$(pv sl_add_1)"
check_eq $P/sl-add-2 "SortedList([0, 1, 3, 4, 5])" "$(pv sl_add_2)"
check_eq $P/sl-add-3 "SortedList([0, 1, 3, 4, 5, 9])" "$(pv sl_add_3)"
check_eq $P/sl-add-dup "SortedList([0, 1, 3, 3, 4, 5, 9])" "$(pv sl_add_dup)"
check_eq $P/sl-update "SortedList([0, 1, 2, 3, 3, 4, 5, 7, 7, 9])" "$(pv sl_update)"
check_eq $P/sl-append-refused "yes" "$(pv sl_append_refused)"
check_eq $P/sl-insert-refused "yes" "$(pv sl_insert_refused)"
check_eq $P/sl-reverse-refused "yes" "$(pv sl_reverse_refused)"

# ============================================================================
# SortedList: remove, discard, pop, clear.
# ============================================================================
# THE WHOLE DIFFERENCE BETWEEN remove AND discard is what they do with an absent
# value, and it is asserted as a pair: the container after discard's no-op, and
# the ValueError from remove. `sl-rm-one-dup` is the other question a caller
# has: remove takes ONE of the duplicates, not all of them.
#
# Every pop emits the value AND the container after it. A pop that returned the
# right element from the wrong position would pass the first half alone.
check_eq $P/sl-rm-0 "SortedList([1, 1, 2, 3, 4, 5, 7, 7, 9])" "$(pv sl_rm_0)"
check_eq $P/sl-rm-1 "SortedList([1, 1, 2, 4, 5, 7, 7, 9])" "$(pv sl_rm_1)"
check_eq $P/sl-rm-2 "SortedList([1, 1, 2, 5, 7, 7, 9])" "$(pv sl_rm_2)"
check_eq $P/sl-discard-absent-noop "SortedList([1, 1, 2, 5, 7, 7, 9])" "$(pv sl_discard_absent_noop)"
check_eq $P/sl-remove-absent-raises "yes" "$(pv sl_remove_absent_raises)"
check_eq $P/sl-rm-one-dup "SortedList([1, 2, 5, 7, 7, 9])" "$(pv sl_rm_one_dup)"
check_eq $P/sl-pop-default-val "5" "$(pv sl_pop_default_val)"
check_eq $P/sl-pop-default-after "SortedList([1, 2, 3, 4])" "$(pv sl_pop_default_after)"
check_eq $P/sl-pop-first-val "1" "$(pv sl_pop_first_val)"
check_eq $P/sl-pop-first-after "SortedList([2, 3, 4])" "$(pv sl_pop_first_after)"
check_eq $P/sl-pop-index-val "3" "$(pv sl_pop_index_val)"
check_eq $P/sl-pop-index-after "SortedList([2, 4])" "$(pv sl_pop_index_after)"
check_eq $P/sl-pop-neg-val "4" "$(pv sl_pop_neg_val)"
check_eq $P/sl-pop-neg-after "SortedList([2])" "$(pv sl_pop_neg_after)"
check_eq $P/sl-pop-oob-raises "yes" "$(pv sl_pop_oob_raises)"
check_eq $P/sl-pop-empty-raises "yes" "$(pv sl_pop_empty_raises)"
check_eq $P/sl-clear "SortedList([])" "$(pv sl_clear)"
check_eq $P/sl-clear-reusable "SortedList([1])" "$(pv sl_clear_reusable)"

# ============================================================================
# SortedList: __getitem__, slices, __delitem__.
# ============================================================================
# A SLICE RETURNS A PLAIN list, NOT A SortedList -- a real asymmetry with
# `list`, where a slice gives back the same type. It is asserted through the
# repr, which is what makes the two distinguishable, and `sl-slice-type` says it
# outright so a reader does not have to notice the missing wrapper.
check_eq $P/sl-get-0 "10" "$(pv sl_get_0)"
check_eq $P/sl-get-2 "30" "$(pv sl_get_2)"
check_eq $P/sl-get-neg1 "50" "$(pv sl_get_neg1)"
check_eq $P/sl-get-neg5 "10" "$(pv sl_get_neg5)"
check_eq $P/sl-get-oob-raises "yes" "$(pv sl_get_oob_raises)"
check_eq $P/sl-slice-all "[10, 20, 30, 40, 50]" "$(pv sl_slice_all)"
check_eq $P/sl-slice-head "[10, 20]" "$(pv sl_slice_head)"
check_eq $P/sl-slice-tail "[40, 50]" "$(pv sl_slice_tail)"
check_eq $P/sl-slice-mid "[20, 30, 40]" "$(pv sl_slice_mid)"
check_eq $P/sl-slice-step "[10, 30, 50]" "$(pv sl_slice_step)"
check_eq $P/sl-slice-neg-step "[50, 40, 30, 20, 10]" "$(pv sl_slice_neg_step)"
check_eq $P/sl-slice-type "list" "$(pv sl_slice_type)"
check_eq $P/sl-del-first "SortedList([20, 30, 40, 50])" "$(pv sl_del_first)"
check_eq $P/sl-del-last "SortedList([20, 30, 40])" "$(pv sl_del_last)"
check_eq $P/sl-del-slice "SortedList([40])" "$(pv sl_del_slice)"

# ============================================================================
# SortedList: bisect, index, count -- AROUND A VALUE THAT APPEARS THREE TIMES.
# ============================================================================
# `bisect_left` and `bisect_right` differ ONLY where the value is present, and
# by exactly the number of copies of it: 1 and 4 here, across the three 2s. On a
# fixture without duplicates the two are the same number and no suite could tell
# one from the other -- which is why the fixture has them.
#
# `bisect` is an alias for bisect_RIGHT, which is the one a caller assumes
# wrongly. `index` answers the FIRST occurrence and takes the same start/stop
# window `list.index` does, including raising when the value is present but
# outside it.
check_eq $P/sl-bisect-left-dup "1" "$(pv sl_bisect_left_dup)"
check_eq $P/sl-bisect-right-dup "4" "$(pv sl_bisect_right_dup)"
check_eq $P/sl-bisect-alias "4" "$(pv sl_bisect_alias)"
check_eq $P/sl-bisect-left-absent "5" "$(pv sl_bisect_left_absent)"
check_eq $P/sl-bisect-right-absent "5" "$(pv sl_bisect_right_absent)"
check_eq $P/sl-bisect-before-all "0" "$(pv sl_bisect_before_all)"
check_eq $P/sl-bisect-after-all "6" "$(pv sl_bisect_after_all)"
check_eq $P/sl-index-dup "1" "$(pv sl_index_dup)"
check_eq $P/sl-index-last "5" "$(pv sl_index_last)"
check_eq $P/sl-index-window "2" "$(pv sl_index_window)"
check_eq $P/sl-index-absent-raises "yes" "$(pv sl_index_absent_raises)"
check_eq $P/sl-index-outside-window-raises "yes" "$(pv sl_index_outside_window_raises)"
check_eq $P/sl-count-dup "3" "$(pv sl_count_dup)"
check_eq $P/sl-count-one "1" "$(pv sl_count_one)"
check_eq $P/sl-count-absent "0" "$(pv sl_count_absent)"
check_eq $P/sl-contains-yes "True" "$(pv sl_contains_yes)"
check_eq $P/sl-contains-no "False" "$(pv sl_contains_no)"

# ============================================================================
# SortedList: irange, WITH ALL FOUR ENDPOINT COMBINATIONS.
# ============================================================================
# `inclusive` is a pair of bools, `(lower, upper)`, and it defaults to
# `(True, True)` -- the argument a caller gets wrong. All four are asserted over
# one fixture so the four answers can be read against each other: 2..5 gives
# four elements, three, three and two.
#
# The endpoints need not be PRESENT (`sl-irange-absent-bounds`): irange is a
# range over the ORDER, not a lookup, so bounds falling between elements are the
# ordinary case rather than an error. `islice` is its positional sibling and is
# asserted beside it -- one takes VALUES, the other takes INDEXES, and that is
# the pair worth stating together.
check_eq $P/sl-irange-both "[2, 3, 4, 5]" "$(pv sl_irange_both)"
check_eq $P/sl-irange-tt "[2, 3, 4, 5]" "$(pv sl_irange_tt)"
check_eq $P/sl-irange-tf "[2, 3, 4]" "$(pv sl_irange_tf)"
check_eq $P/sl-irange-ft "[3, 4, 5]" "$(pv sl_irange_ft)"
check_eq $P/sl-irange-ff "[3, 4]" "$(pv sl_irange_ff)"
check_eq $P/sl-irange-open-lo "[1, 2, 3]" "$(pv sl_irange_open_lo)"
check_eq $P/sl-irange-open-hi "[5, 6, 7]" "$(pv sl_irange_open_hi)"
check_eq $P/sl-irange-open-both "[1, 2, 3, 4, 5, 6, 7]" "$(pv sl_irange_open_both)"
check_eq $P/sl-irange-reverse "[5, 4, 3, 2]" "$(pv sl_irange_reverse)"
check_eq $P/sl-irange-empty "[]" "$(pv sl_irange_empty)"
check_eq $P/sl-irange-absent-bounds "[3, 4, 5]" "$(pv sl_irange_absent_bounds)"
check_eq $P/sl-islice "[2, 3, 4]" "$(pv sl_islice)"
check_eq $P/sl-islice-reverse "[4, 3, 2]" "$(pv sl_islice_reverse)"

# ============================================================================
# SortedList: the operators, and an independent copy.
# ============================================================================
# `sl-eq-list` is the case that says why every assertion in this file compares
# a repr: `SortedList([1, 2]) == [1, 2]` is TRUE, so a method that returned a
# plain list where a SortedList was meant would pass any `==` comparison.
#
# `sl-copy-independent` is not a formality. This family shares internal sublists
# between a container and things derived from it, so a copy that aliased them
# would be invisible until the first mutation of either.
check_eq $P/sl-add-op "SortedList([1, 2, 3, 4])" "$(pv sl_add_op)"
check_eq $P/sl-mul-op "SortedList([1, 1, 2, 2])" "$(pv sl_mul_op)"
check_eq $P/sl-eq "True" "$(pv sl_eq)"
check_eq $P/sl-eq-list "True" "$(pv sl_eq_list)"
check_eq $P/sl-lt "True" "$(pv sl_lt)"
check_eq $P/sl-copy "SortedList([1, 2, 3])" "$(pv sl_copy)"
check_eq $P/sl-copy-independent "SortedList([1, 2, 3])" "$(pv sl_copy_independent)"

# ============================================================================
# SortedList: the load factor, and the multi-sublist path.
# ============================================================================
# `_load` is 1000 -- a constant of the package, not of the machine -- and it is
# the size at which the container stops being one flat list. Everything above
# fits in a single sublist and never exercises the index machinery at all, so
# `sl-big-*` builds 3000 elements: three sublists, and `_maxes` with three
# entries is the direct statement of that.
#
# This is where a rebalance bug would live, and it is the closest this suite
# comes to the performance question -- asserted as VALUES rather than as timings,
# which on this arm would measure the wasm32 runtime and the host's load.
check_eq $P/sl-load "1000" "$(pv sl_load)"
check_eq $P/sl-big-len "3000" "$(pv sl_big_len)"
check_eq $P/sl-big-maxes-len "3" "$(pv sl_big_maxes_len)"
check_eq $P/sl-big-get-mid "1500" "$(pv sl_big_get_mid)"
check_eq $P/sl-big-index "2999" "$(pv sl_big_index)"
check_eq $P/sl-big-bisect "2500" "$(pv sl_big_bisect)"
check_eq $P/sl-big-after-remove "1501" "$(pv sl_big_after_remove)"
check_eq $P/sl-big-len-after "2999" "$(pv sl_big_len_after)"

# ============================================================================
# SortedKeyList: A KEY THAT REVERSES THE NATURAL ORDER.
# ============================================================================
# The key is `-x`, deliberately. A container that IGNORED the key would still be
# sorted, so a wrong comparator would surface as a passing test; reversed, it
# surfaces as a wrong ORDER, which is a failure a reader can act on.
#
# `SortedList(key=...)` does not give back a SortedList: the constructor
# dispatches on the key and returns a SortedKeyList. A caller who wrote
# `isinstance(x, SortedList)` is fine -- it is a subclass -- and one who wrote
# `type(x) is SortedList` is not. `SortedListWithKey` is the 1.x name kept as an
# ALIAS: the same object, not a subclass, so `type()` still says SortedKeyList.
#
# THE TWO BISECT FAMILIES TAKE DIFFERENT ARGUMENTS and that is the mistake this
# pair exists to catch: `bisect_left` takes a VALUE and computes its key,
# `bisect_key_left` takes a KEY. Both are asserted over the same container.
#
# `kl-collide-*` is the other half of what a key is: it ORDERS, it does not
# IDENTIFY. Two distinct values with the same key are both kept, and `remove`
# must take the one asked for rather than whichever came first.
check_eq $P/kl-ctor "[5, 4, 3, 2, 1, 1]" "$(pv kl_ctor)"
check_eq $P/kl-type-name "SortedKeyList" "$(pv kl_type_name)"
check_eq $P/kl-key-is-negate "yes" "$(pv kl_key_is_negate)"
check_eq $P/kl-from-sortedlist "SortedKeyList" "$(pv kl_from_sortedlist)"
check_eq $P/kl-is-sortedlist-subclass "yes" "$(pv kl_is_sortedlist_subclass)"
check_eq $P/kl-alias-is-same "yes" "$(pv kl_alias_is_same)"
check_eq $P/kl-add-last "[5, 4, 3, 2, 1, 1, 0]" "$(pv kl_add_last)"
check_eq $P/kl-add-first "[9, 5, 4, 3, 2, 1, 1, 0]" "$(pv kl_add_first)"
check_eq $P/kl-getitem "9" "$(pv kl_getitem)"
check_eq $P/kl-pop "0" "$(pv kl_pop)"
check_eq $P/kl-after-pop "[9, 5, 4, 3, 2, 1, 1]" "$(pv kl_after_pop)"
check_eq $P/kl-bisect-left-value "2" "$(pv kl_bisect_left_value)"
check_eq $P/kl-bisect-right-value "3" "$(pv kl_bisect_right_value)"
check_eq $P/kl-bisect-key-left "2" "$(pv kl_bisect_key_left)"
check_eq $P/kl-bisect-key-right "3" "$(pv kl_bisect_key_right)"
check_eq $P/kl-irange-key "[4, 3, 2]" "$(pv kl_irange_key)"
check_eq $P/kl-irange-key-ff "[3]" "$(pv kl_irange_key_ff)"
check_eq $P/kl-irange-value "[4, 3, 2]" "$(pv kl_irange_value)"
check_eq $P/kl-index "1" "$(pv kl_index)"
check_eq $P/kl-count "1" "$(pv kl_count)"
check_eq $P/kl-remove-absent-raises "yes" "$(pv kl_remove_absent_raises)"
check_eq $P/kl-collide-ctor "['c', 'bb', 'aa']" "$(pv kl_collide_ctor)"
check_eq $P/kl-collide-remove "['c', 'bb']" "$(pv kl_collide_remove)"
check_eq $P/kl-collide-remove-absent "yes" "$(pv kl_collide_remove_absent)"

# ============================================================================
# SortedSet: THE SAME FIXTURE AS SortedList, SO THE TWO CAN BE COMPARED.
# ============================================================================
# `[5, 1, 4, 1, 3, 2]` gives `SortedList([1, 1, 2, 3, 4, 5])` above and
# `SortedSet([1, 2, 3, 4, 5])` here. The duplicate is the whole difference
# between the types, and the pair of cases is what says which one was built.
#
# `remove` of an absent value raises KeyError here and ValueError on the list --
# each type keeps its own builtin's exception, which is right and is the sort of
# thing a caller only discovers in production.
check_eq $P/ss-ctor "SortedSet([1, 2, 3, 4, 5])" "$(pv ss_ctor)"
check_eq $P/ss-len "5" "$(pv ss_len)"
check_eq $P/ss-type-name "SortedSet" "$(pv ss_type_name)"
check_eq $P/ss-ctor-empty "SortedSet([])" "$(pv ss_ctor_empty)"
check_eq $P/ss-ctor-str "SortedSet(['a', 'b', 'c', 'd', 'r'])" "$(pv ss_ctor_str)"
check_eq $P/ss-ctor-from-set "SortedSet([1, 2, 3])" "$(pv ss_ctor_from_set)"
check_eq $P/ss-add "SortedSet([1, 3, 4, 5])" "$(pv ss_add)"
check_eq $P/ss-add-dup-noop "SortedSet([1, 3, 4, 5])" "$(pv ss_add_dup_noop)"
check_eq $P/ss-update "SortedSet([0, 1, 3, 4, 5, 9])" "$(pv ss_update)"
check_eq $P/ss-discard "SortedSet([1, 3, 4, 5, 9])" "$(pv ss_discard)"
check_eq $P/ss-discard-absent-noop "SortedSet([1, 3, 4, 5, 9])" "$(pv ss_discard_absent_noop)"
check_eq $P/ss-remove "SortedSet([1, 3, 4, 5])" "$(pv ss_remove)"
check_eq $P/ss-remove-absent-raises "yes" "$(pv ss_remove_absent_raises)"
check_eq $P/ss-pop-val "5" "$(pv ss_pop_val)"
check_eq $P/ss-pop-after "SortedSet([1, 3, 4])" "$(pv ss_pop_after)"
check_eq $P/ss-pop-first-val "1" "$(pv ss_pop_first_val)"
check_eq $P/ss-pop-first-after "SortedSet([3, 4])" "$(pv ss_pop_first_after)"

# ============================================================================
# SortedSet: THE ALGEBRA, AND WHY EACH RESULT'S TYPE IS ASSERTED.
# ============================================================================
# `SortedSet([1, 2]) == {1, 2}` is TRUE. So a `union` that fell through to
# `set.__or__` and gave back a builtin set -- in whatever order it hashed to --
# would pass any assertion made with `==`, and the caller would find out when
# they indexed the result. The repr is what separates them, and the four
# `*-type` cases say it outright.
#
# Both spellings of each operation are asserted, the method and the operator,
# because they are separate code paths: `A.union(B)` accepts any iterable and
# `A | B` requires a set. `ss-union-list` is that difference, stated.
#
# `ss-a-untouched` and `ss-b-untouched` are emitted AFTER all eight operations
# above have run: the non-`_update` forms must not mutate their operands.
check_eq $P/ss-union "SortedSet([1, 3, 5, 6, 7, 8])" "$(pv ss_union)"
check_eq $P/ss-union-op "SortedSet([1, 3, 5, 6, 7, 8])" "$(pv ss_union_op)"
check_eq $P/ss-intersection "SortedSet([5, 7])" "$(pv ss_intersection)"
check_eq $P/ss-intersection-op "SortedSet([5, 7])" "$(pv ss_intersection_op)"
check_eq $P/ss-difference "SortedSet([1, 3])" "$(pv ss_difference)"
check_eq $P/ss-difference-op "SortedSet([1, 3])" "$(pv ss_difference_op)"
check_eq $P/ss-symmetric-difference "SortedSet([1, 3, 6, 8])" "$(pv ss_symmetric_difference)"
check_eq $P/ss-symmetric-difference-op "SortedSet([1, 3, 6, 8])" "$(pv ss_symmetric_difference_op)"
check_eq $P/ss-union-type "SortedSet" "$(pv ss_union_type)"
check_eq $P/ss-intersection-type "SortedSet" "$(pv ss_intersection_type)"
check_eq $P/ss-difference-type "SortedSet" "$(pv ss_difference_type)"
check_eq $P/ss-symmetric-difference-type "SortedSet" "$(pv ss_symmetric_difference_type)"
check_eq $P/ss-a-untouched "SortedSet([1, 3, 5, 7])" "$(pv ss_a_untouched)"
check_eq $P/ss-b-untouched "SortedSet([5, 6, 7, 8])" "$(pv ss_b_untouched)"
check_eq $P/ss-union-list "SortedSet([0, 1, 3, 5, 7, 9])" "$(pv ss_union_list)"
check_eq $P/ss-intersection-list "SortedSet([1, 3])" "$(pv ss_intersection_list)"
check_eq $P/ss-difference-update "SortedSet([1, 5])" "$(pv ss_difference_update)"
check_eq $P/ss-intersection-update "SortedSet([1, 5])" "$(pv ss_intersection_update)"
check_eq $P/ss-symmetric-difference-update "SortedSet([1, 7])" "$(pv ss_symmetric_difference_update)"
check_eq $P/ss-issubset "True" "$(pv ss_issubset)"
check_eq $P/ss-issuperset "True" "$(pv ss_issuperset)"
check_eq $P/ss-isdisjoint-no "False" "$(pv ss_isdisjoint_no)"
check_eq $P/ss-isdisjoint-yes "True" "$(pv ss_isdisjoint_yes)"
check_eq $P/ss-eq-set "True" "$(pv ss_eq_set)"
check_eq $P/ss-contains "True" "$(pv ss_contains)"

# ============================================================================
# SortedSet: WHAT IT HAS THAT A set DOES NOT.
# ============================================================================
# An index, a bisection, a range and a reverse iteration. A caller reaching for
# this package instead of `set` is reaching for exactly these, and none of them
# exists on the builtin.
check_eq $P/ss-getitem "1" "$(pv ss_getitem)"
check_eq $P/ss-getitem-neg "7" "$(pv ss_getitem_neg)"
check_eq $P/ss-slice "[3, 5]" "$(pv ss_slice)"
check_eq $P/ss-index "2" "$(pv ss_index)"
check_eq $P/ss-index-absent-raises "yes" "$(pv ss_index_absent_raises)"
check_eq $P/ss-bisect-left "2" "$(pv ss_bisect_left)"
check_eq $P/ss-bisect-right "3" "$(pv ss_bisect_right)"
check_eq $P/ss-count-present "1" "$(pv ss_count_present)"
check_eq $P/ss-count-absent "0" "$(pv ss_count_absent)"
check_eq $P/ss-irange "[3, 5, 7]" "$(pv ss_irange)"
check_eq $P/ss-irange-ff "[5]" "$(pv ss_irange_ff)"
check_eq $P/ss-irange-reverse "[7, 5, 3]" "$(pv ss_irange_reverse)"
check_eq $P/ss-islice "[3, 5]" "$(pv ss_islice)"
check_eq $P/ss-iter "[1, 3, 5, 7]" "$(pv ss_iter)"
check_eq $P/ss-reversed "[7, 5, 3, 1]" "$(pv ss_reversed)"
check_eq $P/ss-copy "SortedSet([1, 3, 5, 7])" "$(pv ss_copy)"
check_eq $P/ss-keyed "['a', 'bb', 'ddd', 'cccc']" "$(pv ss_keyed)"
check_eq $P/ss-keyed-type "SortedSet" "$(pv ss_keyed_type)"
check_eq $P/ss-keyed-tie-keys "1,2,2,3" "$(pv ss_keyed_tie_keys)"
check_eq $P/ss-keyed-tie-values "a,bb,ccc,dd" "$(pv ss_keyed_tie_values)"

# ============================================================================
# SortedDict: THE CONSTRUCTOR, IN ALL FOUR SPELLINGS.
# ============================================================================
# A mapping, a pair sequence, keyword arguments and `fromkeys` -- each a
# separate path into the same invariant, and `sd-is-dict` says the result really
# is a `dict` subclass, which is what lets it be passed to anything that expects
# one.
check_eq $P/sd-ctor "SortedDict({'a': 1, 'b': 2, 'c': 3})" "$(pv sd_ctor)"
check_eq $P/sd-type-name "SortedDict" "$(pv sd_type_name)"
check_eq $P/sd-is-dict "yes" "$(pv sd_is_dict)"
check_eq $P/sd-ctor-pairs "SortedDict({'a': 1, 'z': 26})" "$(pv sd_ctor_pairs)"
check_eq $P/sd-ctor-kwargs "SortedDict({'a': 1, 'b': 2})" "$(pv sd_ctor_kwargs)"
check_eq $P/sd-ctor-empty "SortedDict({})" "$(pv sd_ctor_empty)"
check_eq $P/sd-fromkeys "SortedDict({'a': 0, 'b': 0, 'c': 0})" "$(pv sd_fromkeys)"

# ============================================================================
# SortedDict: INSERTION AND DELETION, WITH THE KEY ORDER AFTER EVERY STEP.
# ============================================================================
# A plain dict answers INSERTION order, so it would pass `sd-ins-1` and fail
# everything after it. The four insertions are chosen for four positions --
# first, before, after, between -- and `sd-ins-overwrite` is the fifth case a
# dict has that a list does not: writing an EXISTING key must not reorder
# anything.
check_eq $P/sd-ins-0 "[]" "$(pv sd_ins_0)"
check_eq $P/sd-ins-1 "['m']" "$(pv sd_ins_1)"
check_eq $P/sd-ins-2 "['a', 'm']" "$(pv sd_ins_2)"
check_eq $P/sd-ins-3 "['a', 'm', 'z']" "$(pv sd_ins_3)"
check_eq $P/sd-ins-4 "['a', 'm', 'n', 'z']" "$(pv sd_ins_4)"
check_eq $P/sd-ins-overwrite "['a', 'm', 'n', 'z']" "$(pv sd_ins_overwrite)"
check_eq $P/sd-ins-overwrite-val "99" "$(pv sd_ins_overwrite_val)"
check_eq $P/sd-del-1 "['a', 'n', 'z']" "$(pv sd_del_1)"
check_eq $P/sd-del-2 "['n', 'z']" "$(pv sd_del_2)"
check_eq $P/sd-del-absent-raises "yes" "$(pv sd_del_absent_raises)"
check_eq $P/sd-update "['b', 'n', 'y', 'z']" "$(pv sd_update)"
check_eq $P/sd-setdefault-new "7" "$(pv sd_setdefault_new)"
check_eq $P/sd-setdefault-existing "7" "$(pv sd_setdefault_existing)"
check_eq $P/sd-after-setdefault "['b', 'c', 'n', 'y', 'z']" "$(pv sd_after_setdefault)"
check_eq $P/sd-get-present "5" "$(pv sd_get_present)"
check_eq $P/sd-get-absent "None" "$(pv sd_get_absent)"
check_eq $P/sd-get-default "-1" "$(pv sd_get_default)"
check_eq $P/sd-pop "5" "$(pv sd_pop)"
check_eq $P/sd-after-pop "['c', 'n', 'y', 'z']" "$(pv sd_after_pop)"
check_eq $P/sd-pop-default "-1" "$(pv sd_pop_default)"
check_eq $P/sd-pop-absent-raises "yes" "$(pv sd_pop_absent_raises)"
check_eq $P/sd-clear "[]" "$(pv sd_clear)"

# ============================================================================
# SortedDict: peekitem, popitem, AND THE INDEX INTO THE KEYS.
# ============================================================================
# `peekitem` reads at a position and does NOT remove -- asserted directly by
# `sd-unchanged-by-peek`, since a "peek" that mutated would otherwise be caught
# only by whatever ran next. `popitem` DOES remove and takes an INDEX, unlike
# `dict.popitem`, which takes none and gives back the last inserted.
#
# `bisect` here is again an alias for bisect_RIGHT, and `sd-bisect-absent` uses
# a key that is not present ("bb", between "b" and "c") because that is where
# the left and right forms agree and the answer is the insertion point.
check_eq $P/sd-peekitem-last "('d', 4)" "$(pv sd_peekitem_last)"
check_eq $P/sd-peekitem-first "('a', 1)" "$(pv sd_peekitem_first)"
check_eq $P/sd-peekitem-index "('c', 3)" "$(pv sd_peekitem_index)"
check_eq $P/sd-peekitem-neg "('c', 3)" "$(pv sd_peekitem_neg)"
check_eq $P/sd-peekitem-oob-raises "yes" "$(pv sd_peekitem_oob_raises)"
check_eq $P/sd-unchanged-by-peek "['a', 'b', 'c', 'd']" "$(pv sd_unchanged_by_peek)"
check_eq $P/sd-popitem-last "('d', 4)" "$(pv sd_popitem_last)"
check_eq $P/sd-popitem-first "('a', 1)" "$(pv sd_popitem_first)"
check_eq $P/sd-after-popitem "['b', 'c']" "$(pv sd_after_popitem)"
check_eq $P/sd-popitem-empty-raises "yes" "$(pv sd_popitem_empty_raises)"
check_eq $P/sd-index "2" "$(pv sd_index)"
check_eq $P/sd-index-absent-raises "yes" "$(pv sd_index_absent_raises)"
check_eq $P/sd-bisect-left "2" "$(pv sd_bisect_left)"
check_eq $P/sd-bisect-right "3" "$(pv sd_bisect_right)"
check_eq $P/sd-bisect-alias "3" "$(pv sd_bisect_alias)"
check_eq $P/sd-bisect-absent "2" "$(pv sd_bisect_absent)"
check_eq $P/sd-irange "['b', 'c', 'd']" "$(pv sd_irange)"
check_eq $P/sd-irange-ff "['c']" "$(pv sd_irange_ff)"
check_eq $P/sd-irange-tf "['b', 'c']" "$(pv sd_irange_tf)"
check_eq $P/sd-irange-ft "['c', 'd']" "$(pv sd_irange_ft)"
check_eq $P/sd-irange-open "['a', 'b', 'c', 'd']" "$(pv sd_irange_open)"
check_eq $P/sd-irange-reverse "['d', 'c', 'b']" "$(pv sd_irange_reverse)"
check_eq $P/sd-islice "['b', 'c']" "$(pv sd_islice)"

# ============================================================================
# SortedDict: THE ORDERED VIEWS -- THIS TYPE'S OWN EXTENSION OVER dict.
# ============================================================================
# `dict.keys()` is a view you can iterate and test membership on and NOTHING
# else: `d.keys()[0]` is a TypeError, asserted directly in
# `sd-builtin-view-not-indexable` so this section is stated against something
# rather than in the abstract.
#
# Here all three views are INDEXABLE and SLICEABLE, with negative indexes, and
# the index agrees with the container's own order. That is the reason to reach
# for SortedDict over an OrderedDict you re-sort.
#
# A VIEW IS LIVE. `sd-view-live` inserts a key AFTER the views were taken and
# the keys view reflects it -- which is what makes it a view rather than a
# snapshot, and what a caller who cached one is relying on without knowing it.
#
# `iloc` is the deprecated 1.x spelling of the keys view, kept and asserted so a
# release that dropped it reds here rather than in somebody's old script.
check_eq $P/sd-keys-type "SortedKeysView" "$(pv sd_keys_type)"
check_eq $P/sd-values-type "SortedValuesView" "$(pv sd_values_type)"
check_eq $P/sd-items-type "SortedItemsView" "$(pv sd_items_type)"
check_eq $P/sd-keys-list "['a', 'b', 'c', 'd']" "$(pv sd_keys_list)"
check_eq $P/sd-values-list "[1, 2, 3, 4]" "$(pv sd_values_list)"
check_eq $P/sd-items-list "[('a', 1), ('b', 2), ('c', 3), ('d', 4)]" "$(pv sd_items_list)"
check_eq $P/sd-keys-index "'a'" "$(pv sd_keys_index)"
check_eq $P/sd-values-index "1" "$(pv sd_values_index)"
check_eq $P/sd-items-index "('a', 1)" "$(pv sd_items_index)"
check_eq $P/sd-keys-neg "'d'" "$(pv sd_keys_neg)"
check_eq $P/sd-values-neg "4" "$(pv sd_values_neg)"
check_eq $P/sd-items-neg "('d', 4)" "$(pv sd_items_neg)"
check_eq $P/sd-keys-slice "['b', 'c']" "$(pv sd_keys_slice)"
check_eq $P/sd-values-slice "[2, 3]" "$(pv sd_values_slice)"
check_eq $P/sd-items-slice "[('b', 2), ('c', 3)]" "$(pv sd_items_slice)"
check_eq $P/sd-keys-len "4" "$(pv sd_keys_len)"
check_eq $P/sd-keys-contains "True" "$(pv sd_keys_contains)"
check_eq $P/sd-items-contains "True" "$(pv sd_items_contains)"
check_eq $P/sd-keys-reversed "['d', 'c', 'b', 'a']" "$(pv sd_keys_reversed)"
check_eq $P/sd-view-live "['a', 'aa', 'b', 'c', 'd']" "$(pv sd_view_live)"
check_eq $P/sd-view-live-index "'aa'" "$(pv sd_view_live_index)"
check_eq $P/sd-builtin-view-not-indexable "yes" "$(pv sd_builtin_view_not_indexable)"
check_eq $P/sd-iloc "['a', 'aa', 'b', 'c', 'd']" "$(pv sd_iloc)"
check_eq $P/sd-iloc-index "'a'" "$(pv sd_iloc_index)"

# ============================================================================
# SortedDict WITH A KEY: METHODS THAT DO NOT EXIST WITHOUT ONE.
# ============================================================================
# `bisect_key_left`, `bisect_key_right` and `irange_key` are bound onto the
# instance only when a key function was given -- `sd-plain-has-bisect-key-left`
# answers `no` for a keyless SortedDict, which is the pair that makes the point.
# The key is the same reversing `-x`, so the key order is visibly not the
# natural one.
check_eq $P/sdk-keys "[5, 3, 1]" "$(pv sdk_keys)"
check_eq $P/sdk-key-is-negate "yes" "$(pv sdk_key_is_negate)"
check_eq $P/sdk-has-bisect-key-left "yes" "$(pv sdk_has_bisect_key_left)"
check_eq $P/sd-plain-has-bisect-key-left "no" "$(pv sd_plain_has_bisect_key_left)"
check_eq $P/sdk-bisect-key-left "1" "$(pv sdk_bisect_key_left)"
check_eq $P/sdk-bisect-key-right "2" "$(pv sdk_bisect_key_right)"
check_eq $P/sdk-irange-key "[5, 3, 1]" "$(pv sdk_irange_key)"
check_eq $P/sdk-irange-key-ff "[3]" "$(pv sdk_irange_key_ff)"
check_eq $P/sdk-after-insert "[5, 4, 3, 1]" "$(pv sdk_after_insert)"
check_eq $P/sdk-peekitem-first "(5, 'b')" "$(pv sdk_peekitem_first)"

# ============================================================================
# THE DOCUMENTED PROGRAMMER ERROR -- AND IT IS NOT AN EXCEPTION.
# ============================================================================
# The package documents that a value must not be mutated, while it is IN a
# container, in a way that changes its order. It does not detect this and does
# not raise, so these cases pin what it DOES.
#
# `mut-harmless` is the control: mutating `[1]` to `[1, 99]` keeps it in order,
# and everything still works. `mut-broken-*` then moves the same element out of
# order -- and the container still PRINTS it in place, `index` of it raises
# ValueError, `in` answers False, and `len` is unchanged. Nothing anywhere says
# the structure is wrong.
#
# `_check()` is the package's own internal audit and is what finally does say
# so. It is asserted as a PAIR: it fails on the mutated container AND passes on
# an intact one. Without the second half the first would pass on a `_check` that
# raised unconditionally.
#
# A KEYED list is worse and is stated separately: the key was computed at insert
# time and CACHED, so a mutated value leaves the container ordered by a key
# nothing has any more.
#
# A release that started detecting the mutation and raising would red here, and
# should -- that is a behaviour change a caller must know about, not a
# regression to suppress.
check_eq $P/mut-before "SortedList([[1], [2], [3]])" "$(pv mut_before)"
check_eq $P/mut-harmless "SortedList([[1, 99], [2], [3]])" "$(pv mut_harmless)"
check_eq $P/mut-harmless-index "0" "$(pv mut_harmless_index)"
check_eq $P/mut-broken-repr "SortedList([[9, 99], [2], [3]])" "$(pv mut_broken_repr)"
check_eq $P/mut-broken-index-raises "yes" "$(pv mut_broken_index_raises)"
check_eq $P/mut-broken-contains "False" "$(pv mut_broken_contains)"
check_eq $P/mut-broken-len "3" "$(pv mut_broken_len)"
check_eq $P/mut-broken-check-fails "yes" "$(pv mut_broken_check_fails)"
check_eq $P/mut-intact-check-passes "yes" "$(pv mut_intact_check_passes)"
check_eq $P/kmut-broken-repr "[[9], [2], [3]]" "$(pv kmut_broken_repr)"
check_eq $P/kmut-broken-index-raises "yes" "$(pv kmut_broken_index_raises)"

# ============================================================================
# ONE FIXTURE THROUGH ALL THREE TYPES, SO THE ANSWERS CAN BE READ TOGETHER.
# ============================================================================
# The list keeps the duplicate key, the set collapses it, and the dict keeps one
# entry per key with the LAST value written for it. Three cases, one input, and
# the differences between the types stated in one place instead of inferred from
# three sections.
check_eq $P/x-list "SortedList(['a', 'a', 'b', 'c'])" "$(pv x_list)"
check_eq $P/x-set "SortedSet(['a', 'b', 'c'])" "$(pv x_set)"
check_eq $P/x-dict "SortedDict({'a': 9, 'b': 2, 'c': 3})" "$(pv x_dict)"
check_eq $P/x-dict-keys "['a', 'b', 'c']" "$(pv x_dict_keys)"

# THE INVARIANT ITSELF, ONCE PER TYPE. The input is chosen so that insertion
# order, hash order and sorted order are three different things, and the
# assertion is that iterating the container gives `sorted()` of the input. This
# is the one statement the whole package is.
check_eq $P/inv-list-sorted "yes" "$(pv inv_list_sorted)"
check_eq $P/inv-set-sorted "yes" "$(pv inv_set_sorted)"
check_eq $P/inv-dict-sorted "yes" "$(pv inv_dict_sorted)"

# ============================================================================
# AND THE INVARIANT UNDER A LONG RANDOMISED SEQUENCE.
# ============================================================================
# Every case above exercises ONE call. The failure mode of a B-tree-ish
# structure is a rebalance that only goes wrong at a size or an interleaving
# nobody thought to write down, and no table of hand-written cases reaches it.
#
# So: 4000 add/remove/index operations against a plain-list reference, 3000
# insert/delete against a dict, and 3000 add/discard against a set, each
# compared to `sorted()` of the reference at the end, and the list run also put
# through the package's own `_check()`.
#
# `random` is seeded with a LITERAL, so the sequence is identical on every image
# and on the x86-64 control. A case that reds here reds reproducibly and can be
# replayed -- which an unseeded stress test could not be, and which is the
# difference between a finding and a rumour.
check_eq $P/stress-list "yes" "$(pv stress_list)"
check_eq $P/stress-dict "yes" "$(pv stress_dict)"
check_eq $P/stress-set "yes" "$(pv stress_set)"

rm -rf "$W"