#!/usr/bin/env python3
"""One interpreter start for every measurement 99-python3-sortedcontainers makes.

WHY ONE PROCESS. A python3 start on wasm32-hwjs is tens of seconds before the
first line of a program runs, and this suite has ~200 things to say about
sortedcontainers. Run as separate `python3 -c` invocations that would be hours
of interpreter starts and nothing else; run here it is ONE start, and the work
inside is a few thousand comparisons over containers of at most a few dozen
small ints and strings.

THE OUTPUT CONTRACT. One `key=value` line per measurement, keys emitted in file
order, `probe_done=yes` last and `emitted_count=N` beside it. The suite asserts
both, so a probe that died two thirds of the way through is distinguishable
from a library that returned the wrong answers -- without them the early cases
stay green and the later ones read got:'', which looks like a partial library.

WHY THE WHOLE CONTAINER IS EMITTED AFTER EVERY OPERATION, NOT THE RETURN VALUE.
This package's subject is an INVARIANT -- the elements are in order -- and the
invariant is maintained across a mutation rather than computed by it. `add`
returns None. `remove` returns None. `discard` returns None. A suite that
asserted only what each call returned would assert nothing at all about the
three methods a caller uses most, and a container that silently stopped sorting
would pass every one of them.

So each mutation sequence emits the container's whole `repr` after every step,
and the repr names the class: `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. That is also why the set-algebra cases below
compare a repr and not a value -- the question there is precisely whether
`union` gave back a `SortedSet` still in order or a builtin `set` in whatever
order it hashed to.

NOTHING HERE DEPENDS ON HASH ORDER, THE CLOCK, THE LOCALE OR THE HOST. Every
fixture is a literal, every comparison is against a literal, and every container
whose repr is asserted is a SORTED one -- so the order in the expected string is
the library's answer and not an artifact of this run. The one builtin `set` that
appears is immediately fed to a SortedSet constructor, whose output is ordered.

WHAT THIS PROBE DELIBERATELY DOES NOT MEASURE: performance. sortedcontainers'
own selling point is that it is "fast as C-extensions", and its load-factor
machinery exists for that. A timing assertion on this arm would measure the
wasm32 runtime and the host's load, not the library, and would red at random.
`DEFAULT_LOAD_FACTOR` and the `_load` a container is actually built with are
asserted as VALUES instead -- which is the part of that machinery that is a fact
about the package rather than about the machine it ran on.
"""
import sys
import traceback

COUNT = 0


def emit(key, value):
    global COUNT
    COUNT += 1
    sys.stdout.write("%s=%s\n" % (key, value))


def val(key, fn):
    """Emit fn()'s repr, or `raised:<Class>` -- never a traceback.

    A case that expects a value and gets an exception name still reds, and the
    class name is what says which. The traceback goes to stderr, which
    bst_probe keeps at <out>.err, so nothing is lost by not putting it on a
    key line the runner would parse as N stray results.
    """
    try:
        emit(key, repr(fn()))
    except Exception:
        traceback.print_exc()
        emit(key, "raised:%s" % sys.exc_info()[0].__name__)


def sval(key, fn):
    """Emit fn()'s value as plain text -- for ints, bools and names.

    `repr` of an int is the int, so this exists only to keep the quoting of the
    handful of cases whose answer is a NAME (`type(x).__name__`) out of the
    expected strings in the suite, where a stray pair of quotes is the sort of
    difference a reader cannot see.
    """
    try:
        emit(key, "%s" % (fn(),))
    except Exception:
        traceback.print_exc()
        emit(key, "raised:%s" % sys.exc_info()[0].__name__)


class _quiet(object):
    """Run a call with its STDOUT diverted to stderr.

    `SortedList._check` PRINTS its internal dump -- lengths, index, maxes,
    lists -- to stdout before re-raising. On this transcript those lines are
    not `key=value` and the suite's `pv` would not read them, but they would
    still sit in the middle of the output a person opens after a red, so they
    go to stderr with the traceback they belong to.
    """

    def __enter__(self):
        self._saved = sys.stdout
        sys.stdout = sys.stderr
        return self

    def __exit__(self, *exc):
        sys.stdout = self._saved
        return False


def raises(key, exc, fn):
    """Emit `yes` iff fn() raises exc -- the failure paths, stated positively.

    `no` when it returned, and the class name when it raised something else:
    three outcomes, one key, and the red says which of the two wrong ones
    happened.
    """
    try:
        fn()
    except exc:
        emit(key, "yes")
        return
    except Exception:
        emit(key, "raised:%s" % sys.exc_info()[0].__name__)
        return
    emit(key, "no")


# PRE_MODULES is taken BEFORE the import below, and is what `no_third_party_import`
# is computed from. It has to be here -- once sortedcontainers is imported there
# is no way left to tell what it brought with it.
PRE_MODULES = set(sys.modules)


# =========================================================== the import ======
# Before anything else, and separately from the module's contents: an import
# failure here would otherwise show up as ~200 identical `raised:NameError`
# lines with nothing saying which one was the cause.
try:
    import sortedcontainers
    from sortedcontainers import (SortedDict, SortedKeyList, SortedList,
                                  SortedListWithKey, SortedSet)
except Exception:
    traceback.print_exc()
    sys.stdout.write("import_failed=%s\n" % sys.exc_info()[0].__name__)
    sys.stdout.write("emitted_count=1\n")
    sys.stdout.write("probe_done=yes\n")
    raise SystemExit(0)

emit("import_ok", "yes")

# ================================================== the module's identity ====
# Where it came from, what it is, and what it says its version is. `module_file`
# is asserted against the packaging's own path in the suite, which is what ties
# these measurements to the .deb that was installed rather than to some other
# copy that happened to be on sys.path.
emit("module_file", sortedcontainers.__file__)
sval("is_package", lambda: "yes" if hasattr(sortedcontainers, "__path__") else "no")

# THE VERSION HAS TWO INDEPENDENT READINGS AND THEY MUST AGREE. `__version__` is
# a literal in the package's own `__init__.py`; the dist-info METADATA the suite
# greps separately is written by the build. A recipe that packaged one version's
# source under another version's metadata passes each reading on its own and
# fails this pair.
emit("dunder_version", sortedcontainers.__version__)
emit("dunder_title", sortedcontainers.__title__)
emit("dunder_author", sortedcontainers.__author__)
emit("dunder_license", sortedcontainers.__license__)

# `__build__` is a packed hex form of the same version -- 0x020400 for 2.4.0 --
# so it is a THIRD reading, and the one that would survive a search-and-replace
# over the string. Emitted as hex, since that is how it is written upstream.
sval("dunder_build", lambda: hex(sortedcontainers.__build__))

# The public surface, sorted so the assertion does not depend on the order the
# names were written in `__all__`.
sval("all_count", lambda: len(sortedcontainers.__all__))
sval("all_sorted", lambda: ",".join(sorted(sortedcontainers.__all__)))

# FOUR MODULES, NO MORE. The sdist ships `__init__`, `sortedlist`, `sortedset`
# and `sorteddict` and nothing else -- no `_sortedlist` C accelerator, no
# compiled fallback, no test package. That is the whole reason this port is
# possible on an image whose python3 is one static binary with an empty
# lib-dynload (BRINTOS-1476), so it is asserted here as a fact about what was
# imported and not only as a fact about what was packaged.
sval("submodule_count",
     lambda: len([m for m in sys.modules if m.startswith("sortedcontainers")]))
sval("submodules",
     lambda: ",".join(sorted(m for m in sys.modules
                             if m.startswith("sortedcontainers."))))

# NO EXTENSION MODULE REACHED THIS PROCESS. Every sortedcontainers module in
# sys.modules must have come from a `.py` (or its cached `.pyc`) -- a module with
# no `__file__`, or one ending in `.so`, would be a builtin or an extension, and
# on this image the second could not have loaded at all.
sval("submodules_all_py",
     lambda: "yes" if all(
         getattr(sys.modules[m], "__file__", "").endswith((".py", ".pyc"))
         for m in sys.modules if m.startswith("sortedcontainers")) else "no")

# NO THIRD-PARTY IMPORT, MEASURED RATHER THAN ASSERTED. The recipe declares no
# RDEPENDS beyond python3-core, and this is the runtime half of that statement:
# `PRE_MODULES` was taken before the import at the top of this file, so the
# difference is exactly what `import sortedcontainers` pulled in, and every one
# of those must be either the package itself or a name python3 itself ships
# (`sys.stdlib_module_names`). A release that started importing, say,
# `typing_extensions` would red HERE, on the image, rather than at the next
# person's `import` in production -- and it names the offender rather than only
# saying `no`.
_pulled = sorted(set(sys.modules) - PRE_MODULES)
_foreign = [m for m in _pulled
            if not m.startswith("sortedcontainers")
            and m.split(".")[0] not in sys.stdlib_module_names]
sval("no_third_party_import", lambda: "yes" if not _foreign else ",".join(_foreign))

# ===================================================== SortedList: build =====
# The constructor is the first thing that has to sort, and the input is
# deliberately given out of order with a duplicate in it: a `SortedList` that
# merely stored what it was handed would pass an assertion made on a
# pre-sorted fixture.
BASE = [5, 1, 4, 1, 3, 2]
val("sl_ctor", lambda: SortedList(BASE))
val("sl_ctor_empty", lambda: SortedList())
val("sl_ctor_str", lambda: SortedList("banana"))

# THE INPUT IS NOT MUTATED. A constructor that sorted its argument in place
# would pass every ordering case above and quietly corrupt the caller's list.
_src = [3, 1, 2]
SortedList(_src)
val("sl_ctor_input_untouched", lambda: _src)

sval("sl_len", lambda: len(SortedList(BASE)))
sval("sl_default_load_factor", lambda: SortedList.DEFAULT_LOAD_FACTOR)
sval("sl_key_is_none", lambda: "yes" if SortedList(BASE).key is None else "no")
sval("sl_type_name", lambda: type(SortedList(BASE)).__name__)

# ============================================ SortedList: add and update =====
# The sequence a caller actually writes, with the whole container emitted after
# EVERY step. `add` and `update` both return None, so the container is the only
# thing there is to assert.
_sl = SortedList([5, 1, 4])
val("sl_add_0", lambda: _sl)
_sl.add(3)
val("sl_add_1", lambda: _sl)          # into the middle
_sl.add(0)
val("sl_add_2", lambda: _sl)          # before everything
_sl.add(9)
val("sl_add_3", lambda: _sl)          # after everything
_sl.add(3)
val("sl_add_dup", lambda: _sl)        # a duplicate: kept, not collapsed
_sl.update([7, 2, 7])
val("sl_update", lambda: _sl)

# `append` and `insert` are inherited names that a sorted list CANNOT honour --
# both would put an element where the caller said rather than where it belongs.
# The package refuses them rather than silently sorting, which is the right
# choice and the one a caller migrating from `list` trips over first.
raises("sl_append_refused", NotImplementedError, lambda: SortedList([1, 2]).append(0))
raises("sl_insert_refused", NotImplementedError, lambda: SortedList([1, 2]).insert(0, 0))
raises("sl_reverse_refused", NotImplementedError, lambda: SortedList([1, 2]).reverse())

# ================================== SortedList: remove, discard and pop ======
_sl = SortedList([1, 1, 2, 3, 4, 5, 7, 7, 9])
val("sl_rm_0", lambda: _sl)
_sl.remove(3)
val("sl_rm_1", lambda: _sl)
_sl.discard(4)
val("sl_rm_2", lambda: _sl)

# DISCARD OF AN ABSENT VALUE IS A NO-OP AND REMOVE OF ONE RAISES. That is the
# entire difference between the two methods, and it is asserted as a pair --
# the container after the no-op, and the exception from the other.
_sl.discard(1000)
val("sl_discard_absent_noop", lambda: _sl)
raises("sl_remove_absent_raises", ValueError, lambda: _sl.remove(1000))

# REMOVE TAKES ONE OF THE DUPLICATES, NOT BOTH. `[1, 1]` becomes `[1]`.
_sl.remove(1)
val("sl_rm_one_dup", lambda: _sl)

# `pop` at both ends and at an index. Each emits the value popped AND the
# container after it, because a pop that returned the right element from the
# wrong position would pass the first half alone.
_sl = SortedList([1, 2, 3, 4, 5])
val("sl_pop_default_val", lambda: _sl.pop())        # the default is -1, the LAST
val("sl_pop_default_after", lambda: _sl)
val("sl_pop_first_val", lambda: _sl.pop(0))
val("sl_pop_first_after", lambda: _sl)
val("sl_pop_index_val", lambda: _sl.pop(1))
val("sl_pop_index_after", lambda: _sl)
val("sl_pop_neg_val", lambda: _sl.pop(-1))
val("sl_pop_neg_after", lambda: _sl)
raises("sl_pop_oob_raises", IndexError, lambda: SortedList([1]).pop(5))
raises("sl_pop_empty_raises", IndexError, lambda: SortedList().pop())

# `clear` empties it and leaves a usable container, not a broken one.
_sl = SortedList([1, 2, 3])
_sl.clear()
val("sl_clear", lambda: _sl)
_sl.add(1)
val("sl_clear_reusable", lambda: _sl)

# ================================ SortedList: __getitem__ and __delitem__ ====
_sl = SortedList([10, 20, 30, 40, 50])
val("sl_get_0", lambda: _sl[0])
val("sl_get_2", lambda: _sl[2])
val("sl_get_neg1", lambda: _sl[-1])
val("sl_get_neg5", lambda: _sl[-5])
raises("sl_get_oob_raises", IndexError, lambda: _sl[5])

# A SLICE RETURNS A PLAIN LIST, NOT A SortedList. That is a real asymmetry with
# `list`, where a slice gives back the same type, and it is asserted through the
# repr precisely because the two print differently.
val("sl_slice_all", lambda: _sl[:])
val("sl_slice_head", lambda: _sl[:2])
val("sl_slice_tail", lambda: _sl[3:])
val("sl_slice_mid", lambda: _sl[1:4])
val("sl_slice_step", lambda: _sl[::2])
val("sl_slice_neg_step", lambda: _sl[::-1])
sval("sl_slice_type", lambda: type(_sl[1:3]).__name__)

_sl = SortedList([10, 20, 30, 40, 50])
del _sl[0]
val("sl_del_first", lambda: _sl)
del _sl[-1]
val("sl_del_last", lambda: _sl)
del _sl[0:2]
val("sl_del_slice", lambda: _sl)

# ================================== SortedList: bisect, index and count ======
# The duplicate is the whole point: `bisect_left` and `bisect_right` differ ONLY
# where the value is present, and by exactly the number of copies of it.
_sl = SortedList([1, 2, 2, 2, 3, 5])
sval("sl_bisect_left_dup", lambda: _sl.bisect_left(2))
sval("sl_bisect_right_dup", lambda: _sl.bisect_right(2))
sval("sl_bisect_alias", lambda: _sl.bisect(2))       # `bisect` is bisect_right
sval("sl_bisect_left_absent", lambda: _sl.bisect_left(4))
sval("sl_bisect_right_absent", lambda: _sl.bisect_right(4))
sval("sl_bisect_before_all", lambda: _sl.bisect_left(0))
sval("sl_bisect_after_all", lambda: _sl.bisect_right(99))

# `index` answers the FIRST occurrence, and takes the same start/stop window
# `list.index` does.
sval("sl_index_dup", lambda: _sl.index(2))
sval("sl_index_last", lambda: _sl.index(5))
sval("sl_index_window", lambda: _sl.index(2, 2, 5))
raises("sl_index_absent_raises", ValueError, lambda: _sl.index(4))
raises("sl_index_outside_window_raises", ValueError, lambda: _sl.index(1, 2, 5))

sval("sl_count_dup", lambda: _sl.count(2))
sval("sl_count_one", lambda: _sl.count(3))
sval("sl_count_absent", lambda: _sl.count(4))

sval("sl_contains_yes", lambda: 2 in _sl)
sval("sl_contains_no", lambda: 4 in _sl)

# ================================================= SortedList: irange ========
# A bounded range with EVERY combination of inclusive endpoints, which is the
# argument a caller gets wrong. `inclusive` is a pair of bools, `(lower, upper)`.
_sl = SortedList([1, 2, 3, 4, 5, 6, 7])
val("sl_irange_both", lambda: list(_sl.irange(2, 5)))
val("sl_irange_tt", lambda: list(_sl.irange(2, 5, (True, True))))
val("sl_irange_tf", lambda: list(_sl.irange(2, 5, (True, False))))
val("sl_irange_ft", lambda: list(_sl.irange(2, 5, (False, True))))
val("sl_irange_ff", lambda: list(_sl.irange(2, 5, (False, False))))
val("sl_irange_open_lo", lambda: list(_sl.irange(None, 3)))
val("sl_irange_open_hi", lambda: list(_sl.irange(5, None)))
val("sl_irange_open_both", lambda: list(_sl.irange()))
val("sl_irange_reverse", lambda: list(_sl.irange(2, 5, reverse=True)))
val("sl_irange_empty", lambda: list(_sl.irange(10, 20)))

# The endpoints need not be PRESENT: irange is a range over the order, not a
# lookup, so bounds between elements are the ordinary case.
val("sl_irange_absent_bounds", lambda: list(_sl.irange(2.5, 5.5)))

# `islice` is the positional sibling of irange, and the pair is worth stating
# together: one takes VALUES and the other takes INDEXES.
val("sl_islice", lambda: list(_sl.islice(1, 4)))
val("sl_islice_reverse", lambda: list(_sl.islice(1, 4, reverse=True)))

# ============================== SortedList: the arithmetic and comparison ====
val("sl_add_op", lambda: SortedList([1, 3]) + SortedList([2, 4]))
val("sl_mul_op", lambda: SortedList([1, 2]) * 2)
sval("sl_eq", lambda: SortedList([1, 2]) == SortedList([1, 2]))
sval("sl_eq_list", lambda: SortedList([1, 2]) == [1, 2])
sval("sl_lt", lambda: SortedList([1, 2]) < SortedList([1, 3]))
val("sl_copy", lambda: SortedList([1, 2, 3]).copy())

# A COPY IS INDEPENDENT. The whole family shares internal sublists between a
# container and things derived from it, so this is not a formality.
_orig = SortedList([1, 2, 3])
_cp = _orig.copy()
_cp.add(4)
val("sl_copy_independent", lambda: _orig)

# ========================================== SortedList: the load factor ======
# The internal `_load` is what the container's B-tree-ish layout is built on,
# and it is a FACT ABOUT THE PACKAGE (a constant, 1000) rather than about the
# machine. Asserted because a release that changed it would change the
# performance characteristics this package exists for, silently.
sval("sl_load", lambda: SortedList([1, 2, 3])._load)

# A container big enough to need more than one internal sublist. 3000 elements
# against a load of 1000 is the case where the index machinery actually runs --
# everything above it fits in a single sublist and never exercises it.
_big = SortedList(range(3000))
sval("sl_big_len", lambda: len(_big))
sval("sl_big_maxes_len", lambda: len(_big._maxes))
sval("sl_big_get_mid", lambda: _big[1500])
sval("sl_big_index", lambda: _big.index(2999))
sval("sl_big_bisect", lambda: _big.bisect_left(2500))
_big.remove(1500)
sval("sl_big_after_remove", lambda: _big[1500])
sval("sl_big_len_after", lambda: len(_big))

# ======================================================= SortedKeyList =======
# The key function REVERSES the natural order, 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
# you can read -- rather than as an exception or as nothing at all.
def negate(x):
    return -x


_kl = SortedKeyList([5, 1, 4, 1, 3, 2], key=negate)
val("kl_ctor", lambda: list(_kl))
sval("kl_type_name", lambda: type(_kl).__name__)
sval("kl_key_is_negate", lambda: "yes" if _kl.key is negate else "no")

# `SortedList(key=...)` does not return a SortedList: the constructor dispatches
# on the key and hands back a SortedKeyList. A caller who wrote an `isinstance`
# check against SortedList is fine (it is a subclass) and one who wrote
# `type(x) is SortedList` is not.
sval("kl_from_sortedlist", lambda: type(SortedList([1, 2], key=negate)).__name__)
sval("kl_is_sortedlist_subclass",
     lambda: "yes" if isinstance(SortedList([1, 2], key=negate), SortedList) else "no")

# `SortedListWithKey` is the 1.x name, kept as an ALIAS -- the same object, not
# a subclass, so old code keeps working and `type()` still says SortedKeyList.
sval("kl_alias_is_same", lambda: "yes" if SortedListWithKey is SortedKeyList else "no")

_kl.add(0)
val("kl_add_last", lambda: list(_kl))     # 0 has the LARGEST key, so it goes last
_kl.add(9)
val("kl_add_first", lambda: list(_kl))    # 9 has the smallest key, so it goes first
val("kl_getitem", lambda: _kl[0])
val("kl_pop", lambda: _kl.pop())
val("kl_after_pop", lambda: list(_kl))

# The bisects come in two families on a keyed list, and they take different
# arguments: `bisect_left` takes a VALUE and computes its key, `bisect_key_left`
# takes a KEY. Confusing the two is the mistake this pair exists to catch.
_kl = SortedKeyList([5, 1, 4, 3, 2], key=negate)
sval("kl_bisect_left_value", lambda: _kl.bisect_left(3))
sval("kl_bisect_right_value", lambda: _kl.bisect_right(3))
sval("kl_bisect_key_left", lambda: _kl.bisect_key_left(-3))
sval("kl_bisect_key_right", lambda: _kl.bisect_key_right(-3))
val("kl_irange_key", lambda: list(_kl.irange_key(-4, -2)))
val("kl_irange_key_ff", lambda: list(_kl.irange_key(-4, -2, (False, False))))
val("kl_irange_value", lambda: list(_kl.irange(4, 2)))
sval("kl_index", lambda: _kl.index(4))
sval("kl_count", lambda: _kl.count(4))
raises("kl_remove_absent_raises", ValueError, lambda: _kl.remove(99))

# A KEY THAT COLLIDES. Two distinct values with the SAME key must both be kept
# -- the key orders, it does not identify -- and `remove` must take the one
# asked for rather than whichever came first.
_kc = SortedKeyList(["bb", "aa", "c"], key=len)
val("kl_collide_ctor", lambda: list(_kc))
_kc.remove("aa")
val("kl_collide_remove", lambda: list(_kc))
raises("kl_collide_remove_absent", ValueError, lambda: _kc.remove("zz"))

# ==================================================== SortedSet: build =======
# Same fixture as SortedList, so the two are directly comparable: the duplicate
# 1 is COLLAPSED here and kept there, which is the whole difference.
_ss = SortedSet(BASE)
val("ss_ctor", lambda: _ss)
sval("ss_len", lambda: len(_ss))
sval("ss_type_name", lambda: type(_ss).__name__)
val("ss_ctor_empty", lambda: SortedSet())
val("ss_ctor_str", lambda: SortedSet("abracadabra"))
val("ss_ctor_from_set", lambda: SortedSet({3, 1, 2}))

_ss = SortedSet([5, 1, 4])
_ss.add(3)
val("ss_add", lambda: _ss)
_ss.add(3)
val("ss_add_dup_noop", lambda: _ss)      # already present: the set is unchanged
_ss.update([9, 0, 5])
val("ss_update", lambda: _ss)
_ss.discard(0)
val("ss_discard", lambda: _ss)
_ss.discard(1000)
val("ss_discard_absent_noop", lambda: _ss)
_ss.remove(9)
val("ss_remove", lambda: _ss)
raises("ss_remove_absent_raises", KeyError, lambda: _ss.remove(1000))
val("ss_pop_val", lambda: _ss.pop())
val("ss_pop_after", lambda: _ss)
val("ss_pop_first_val", lambda: _ss.pop(0))
val("ss_pop_first_after", lambda: _ss)

# =============================================== SortedSet: the algebra ======
# EACH RESULT IS ASSERTED TO BE A SortedSet AND TO BE IN ORDER. That is the
# question: a `union` implemented by falling through to `set.__or__` would give
# back a builtin set whose iteration order is the hash order, and a suite
# comparing values with `==` would not notice, because `SortedSet([1,2]) ==
# {1,2}` is True. The repr is what separates them.
A = SortedSet([1, 3, 5, 7])
B = SortedSet([5, 6, 7, 8])
val("ss_union", lambda: A.union(B))
val("ss_union_op", lambda: A | B)
val("ss_intersection", lambda: A.intersection(B))
val("ss_intersection_op", lambda: A & B)
val("ss_difference", lambda: A.difference(B))
val("ss_difference_op", lambda: A - B)
val("ss_symmetric_difference", lambda: A.symmetric_difference(B))
val("ss_symmetric_difference_op", lambda: A ^ B)
sval("ss_union_type", lambda: type(A.union(B)).__name__)
sval("ss_intersection_type", lambda: type(A.intersection(B)).__name__)
sval("ss_difference_type", lambda: type(A.difference(B)).__name__)
sval("ss_symmetric_difference_type", lambda: type(A.symmetric_difference(B)).__name__)

# THE OPERANDS ARE UNCHANGED. The non-`_update` forms must not mutate, and this
# is emitted AFTER all eight of them above have run.
val("ss_a_untouched", lambda: A)
val("ss_b_untouched", lambda: B)

# The algebra also takes a plain iterable, not only another SortedSet -- and the
# answer is still ordered.
val("ss_union_list", lambda: A.union([0, 9]))
val("ss_intersection_list", lambda: A.intersection([1, 2, 3]))

# The in-place forms, each with the container emitted after.
_u = SortedSet([1, 3, 5])
_u.difference_update([3])
val("ss_difference_update", lambda: _u)
_u.intersection_update([1, 5, 9])
val("ss_intersection_update", lambda: _u)
_u.symmetric_difference_update([5, 7])
val("ss_symmetric_difference_update", lambda: _u)

sval("ss_issubset", lambda: SortedSet([1, 3]).issubset(A))
sval("ss_issuperset", lambda: A.issuperset(SortedSet([1, 3])))
sval("ss_isdisjoint_no", lambda: A.isdisjoint(B))
sval("ss_isdisjoint_yes", lambda: A.isdisjoint(SortedSet([2, 4])))
sval("ss_eq_set", lambda: SortedSet([1, 2]) == {1, 2})
sval("ss_contains", lambda: 3 in A)

# ================================== SortedSet: the ordering it adds to set ===
# These are what a SortedSet has that a `set` does not: an index, a bisect and a
# range. A caller reaching for sortedcontainers is reaching for exactly this.
val("ss_getitem", lambda: A[0])
val("ss_getitem_neg", lambda: A[-1])
val("ss_slice", lambda: A[1:3])
sval("ss_index", lambda: A.index(5))
raises("ss_index_absent_raises", ValueError, lambda: A.index(4))
sval("ss_bisect_left", lambda: A.bisect_left(5))
sval("ss_bisect_right", lambda: A.bisect_right(5))
sval("ss_count_present", lambda: A.count(5))
sval("ss_count_absent", lambda: A.count(4))
val("ss_irange", lambda: list(A.irange(3, 7)))
val("ss_irange_ff", lambda: list(A.irange(3, 7, (False, False))))
val("ss_irange_reverse", lambda: list(A.irange(3, 7, reverse=True)))
val("ss_islice", lambda: list(A.islice(1, 3)))
val("ss_iter", lambda: list(A))
val("ss_reversed", lambda: list(reversed(A)))
val("ss_copy", lambda: A.copy())

# A KEYED SortedSet orders by the key while still deduplicating by VALUE.
#
# THE KEYS HERE ARE ALL DISTINCT, DELIBERATELY. SortedSet builds its ordered
# half by iterating its own builtin `set`, so the order EQUAL keys reach the
# comparator in is the hash order -- and for str that is randomised per process
# by PYTHONHASHSEED. Measured on the x86-64 control: `SortedSet(["bb", "a",
# "ccc", "dd"], key=len)` gives `['a', 'bb', 'dd', 'ccc']` on some runs and
# `['a', 'dd', 'bb', 'ccc']` on others, from the same input in the same
# interpreter. A case asserting a tie order would therefore red at random, on
# an image where nothing had changed. So the fixture has four distinct lengths,
# and the tie question is asked separately below in the only form that has an
# answer.
_sk = SortedSet(["bb", "a", "cccc", "ddd"], key=len)
val("ss_keyed", lambda: list(_sk))
sval("ss_keyed_type", lambda: type(_sk).__name__)

# WITH TIES, ONLY THE KEY SEQUENCE IS DEFINED -- not which of two equal-keyed
# values comes first. That is the whole of what can be asserted, and it is worth
# asserting: it still catches a keyed set that ignored the key entirely, while
# the stronger-looking assertion above it would have been a coin flip.
_skt = SortedSet(["bb", "a", "ccc", "dd"], key=len)
sval("ss_keyed_tie_keys", lambda: ",".join(str(len(v)) for v in _skt))
sval("ss_keyed_tie_values", lambda: ",".join(sorted(_skt)))

# ================================================== SortedDict: build ========
_sd = SortedDict({"c": 3, "a": 1, "b": 2})
val("sd_ctor", lambda: _sd)
sval("sd_type_name", lambda: type(_sd).__name__)
sval("sd_is_dict", lambda: "yes" if isinstance(_sd, dict) else "no")
val("sd_ctor_pairs", lambda: SortedDict([("z", 26), ("a", 1)]))
val("sd_ctor_kwargs", lambda: SortedDict(b=2, a=1))
val("sd_ctor_empty", lambda: SortedDict())
val("sd_fromkeys", lambda: SortedDict.fromkeys(["c", "a", "b"], 0))

# ============================ SortedDict: insertion and deletion, in order ===
# The key order emitted after EVERY step, which is the invariant. A plain dict
# would answer insertion order here and pass nothing below the first line.
_sd = SortedDict()
val("sd_ins_0", lambda: list(_sd))
_sd["m"] = 1
val("sd_ins_1", lambda: list(_sd))
_sd["a"] = 2
val("sd_ins_2", lambda: list(_sd))       # before
_sd["z"] = 3
val("sd_ins_3", lambda: list(_sd))       # after
_sd["n"] = 4
val("sd_ins_4", lambda: list(_sd))       # between
_sd["m"] = 99
val("sd_ins_overwrite", lambda: list(_sd))   # an EXISTING key: no reordering
val("sd_ins_overwrite_val", lambda: _sd["m"])
del _sd["m"]
val("sd_del_1", lambda: list(_sd))
del _sd["a"]
val("sd_del_2", lambda: list(_sd))
raises("sd_del_absent_raises", KeyError, lambda: _sd.__delitem__("q"))
_sd.update({"b": 5, "y": 6})
val("sd_update", lambda: list(_sd))
val("sd_setdefault_new", lambda: _sd.setdefault("c", 7))
val("sd_setdefault_existing", lambda: _sd.setdefault("c", 100))
val("sd_after_setdefault", lambda: list(_sd))
val("sd_get_present", lambda: _sd.get("b"))
val("sd_get_absent", lambda: _sd.get("q"))
val("sd_get_default", lambda: _sd.get("q", -1))
val("sd_pop", lambda: _sd.pop("b"))
val("sd_after_pop", lambda: list(_sd))
val("sd_pop_default", lambda: _sd.pop("q", -1))
raises("sd_pop_absent_raises", KeyError, lambda: _sd.pop("q"))
_sd.clear()
val("sd_clear", lambda: list(_sd))

# ============================== SortedDict: peekitem, popitem and the index ==
_sd = SortedDict({"b": 2, "d": 4, "a": 1, "c": 3})
val("sd_peekitem_last", lambda: _sd.peekitem())      # the default is -1
val("sd_peekitem_first", lambda: _sd.peekitem(0))
val("sd_peekitem_index", lambda: _sd.peekitem(2))
val("sd_peekitem_neg", lambda: _sd.peekitem(-2))
raises("sd_peekitem_oob_raises", IndexError, lambda: _sd.peekitem(99))
val("sd_unchanged_by_peek", lambda: list(_sd))       # peekitem does NOT remove

# `popitem` DOES remove, and it takes an index -- unlike `dict.popitem`, which
# takes none and gives the last inserted.
val("sd_popitem_last", lambda: _sd.popitem())
val("sd_popitem_first", lambda: _sd.popitem(0))
val("sd_after_popitem", lambda: list(_sd))
raises("sd_popitem_empty_raises", KeyError, lambda: SortedDict().popitem())

_sd = SortedDict({"b": 2, "d": 4, "a": 1, "c": 3})
sval("sd_index", lambda: _sd.index("c"))
raises("sd_index_absent_raises", ValueError, lambda: _sd.index("q"))
sval("sd_bisect_left", lambda: _sd.bisect_left("c"))
sval("sd_bisect_right", lambda: _sd.bisect_right("c"))
sval("sd_bisect_alias", lambda: _sd.bisect("c"))
sval("sd_bisect_absent", lambda: _sd.bisect_left("bb"))

val("sd_irange", lambda: list(_sd.irange("b", "d")))
val("sd_irange_ff", lambda: list(_sd.irange("b", "d", (False, False))))
val("sd_irange_tf", lambda: list(_sd.irange("b", "d", (True, False))))
val("sd_irange_ft", lambda: list(_sd.irange("b", "d", (False, True))))
val("sd_irange_open", lambda: list(_sd.irange()))
val("sd_irange_reverse", lambda: list(_sd.irange("b", "d", reverse=True)))
val("sd_islice", lambda: list(_sd.islice(1, 3)))

# ============================================ SortedDict: the ordered views ==
# THIS IS THE TYPE'S OWN EXTENSION OVER dict, and the reason it is worth having.
# `dict.keys()` is a view you can iterate and test membership on and NOTHING
# else -- `d.keys()[0]` is a TypeError. Here the three views are INDEXABLE, and
# sliceable, and the index agrees with the container's own order.
_sd = SortedDict({"b": 2, "d": 4, "a": 1, "c": 3})
_k, _v, _i = _sd.keys(), _sd.values(), _sd.items()
sval("sd_keys_type", lambda: type(_k).__name__)
sval("sd_values_type", lambda: type(_v).__name__)
sval("sd_items_type", lambda: type(_i).__name__)
val("sd_keys_list", lambda: list(_k))
val("sd_values_list", lambda: list(_v))
val("sd_items_list", lambda: list(_i))
val("sd_keys_index", lambda: _k[0])
val("sd_values_index", lambda: _v[0])
val("sd_items_index", lambda: _i[0])
val("sd_keys_neg", lambda: _k[-1])
val("sd_values_neg", lambda: _v[-1])
val("sd_items_neg", lambda: _i[-1])
val("sd_keys_slice", lambda: _k[1:3])
val("sd_values_slice", lambda: _v[1:3])
val("sd_items_slice", lambda: _i[1:3])
sval("sd_keys_len", lambda: len(_k))
sval("sd_keys_contains", lambda: "b" in _k)
sval("sd_items_contains", lambda: ("b", 2) in _i)
val("sd_keys_reversed", lambda: list(reversed(_k)))

# A VIEW IS LIVE. It reflects a mutation made after it was taken -- which is
# what makes it a view rather than a snapshot, and what a caller who cached one
# is relying on without knowing it.
_sd["aa"] = 11
val("sd_view_live", lambda: list(_k))
val("sd_view_live_index", lambda: _k[1])

# The builtin's own view is NOT indexable, asserted directly so the extension
# above is stated against something rather than in the abstract.
raises("sd_builtin_view_not_indexable", TypeError,
       lambda: {"a": 1}.keys()[0])

# `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.
val("sd_iloc", lambda: list(_sd.iloc))
val("sd_iloc_index", lambda: _sd.iloc[0])

# ================================================== SortedDict: with a key ===
# The keys are ordered by the key function, and `bisect_key_left` and
# `irange_key` -- which a keyless SortedDict does not even HAVE -- appear.
_sdk = SortedDict(negate, {1: "a", 5: "b", 3: "c"})
val("sdk_keys", lambda: list(_sdk))
sval("sdk_key_is_negate", lambda: "yes" if _sdk.key is negate else "no")
sval("sdk_has_bisect_key_left",
     lambda: "yes" if hasattr(_sdk, "bisect_key_left") else "no")
sval("sd_plain_has_bisect_key_left",
     lambda: "yes" if hasattr(SortedDict(), "bisect_key_left") else "no")
sval("sdk_bisect_key_left", lambda: _sdk.bisect_key_left(-3))
sval("sdk_bisect_key_right", lambda: _sdk.bisect_key_right(-3))
val("sdk_irange_key", lambda: list(_sdk.irange_key(-5, -1)))
val("sdk_irange_key_ff", lambda: list(_sdk.irange_key(-5, -1, (False, False))))
_sdk[4] = "d"
val("sdk_after_insert", lambda: list(_sdk))
val("sdk_peekitem_first", lambda: _sdk.peekitem(0))

# ============================ the documented programmer error: mutation ======
# sortedcontainers' documentation is explicit that a value must not be mutated
# in a way that changes its order while it is IN a container -- the container
# cannot observe the change, so its index goes stale and its answers become
# wrong.
#
# THIS IS THE CASE THAT MUST NOT BE WRITTEN AS "IT RAISES", because it does not.
# What is asserted is the DOCUMENTED BEHAVIOUR -- undefined answers, not an
# exception -- and each answer is pinned as measured. A release that started
# detecting the mutation and raising would red here and say so, which is the
# right outcome: a behaviour change a caller must know about.
_mut = SortedList([[1], [2], [3]])
val("mut_before", lambda: _mut)
_mut[0].append(99)                       # [1] becomes [1, 99]: still in order
val("mut_harmless", lambda: _mut)
sval("mut_harmless_index", lambda: _mut.index([1, 99]))

_mut = SortedList([[1], [2], [3]])
_mut[0].append(99)
_mut[0][0] = 9                           # [1, 99] becomes [9, 99]: OUT of order
val("mut_broken_repr", lambda: _mut)     # the container still PRINTS it in place
# The index is now stale, and this is exactly the shape the docs warn about:
# a lookup by bisection walks past the element it is looking for.
raises("mut_broken_index_raises", ValueError, lambda: _mut.index([9, 99]))
sval("mut_broken_contains", lambda: [9, 99] in _mut)
sval("mut_broken_len", lambda: len(_mut))
# `_check` is the package's own internal consistency audit, and it is what says
# the container is genuinely broken rather than merely printing oddly.
def _check_broken():
    with _quiet():
        return _mut._check()


raises("mut_broken_check_fails", Exception, _check_broken)
# A container that was NOT mutated passes the same audit -- without this the
# case above would pass on a `_check` that raised unconditionally.
def _check_intact():
    with _quiet():
        return "yes" if SortedList([1, 2, 3])._check() is None else "no"


sval("mut_intact_check_passes", _check_intact)

# A KEYED list is worse, and worth stating separately: the key was computed at
# insert time and is CACHED, so mutating the value leaves the container ordered
# by a key nothing has any more.
_kmut = SortedKeyList([[1], [2], [3]], key=lambda v: v[0])
_kmut[0][0] = 9
val("kmut_broken_repr", lambda: list(_kmut))
raises("kmut_broken_index_raises", ValueError, lambda: _kmut.index([9]))

# ============================================= the cross-type invariants =====
# One fixture through all three types, so the three answers can be read against
# each other: the LIST keeps duplicates, the SET collapses them, and the DICT
# keeps one entry per key with the LAST value that was written for it.
FIX = [("b", 2), ("a", 1), ("c", 3), ("a", 9)]
val("x_list", lambda: SortedList(k for k, _ in FIX))
val("x_set", lambda: SortedSet(k for k, _ in FIX))
val("x_dict", lambda: SortedDict(FIX))
val("x_dict_keys", lambda: list(SortedDict(FIX)))

# EVERY TYPE ITERATES IN ORDER, and `sorted()` of it is itself. That is the
# invariant the whole package is, stated once per type over an input chosen so
# that insertion order, hash order and sorted order are three different things.
SHUF = [7, 2, 9, 1, 8, 3]
sval("inv_list_sorted",
     lambda: "yes" if list(SortedList(SHUF)) == sorted(SHUF) else "no")
sval("inv_set_sorted",
     lambda: "yes" if list(SortedSet(SHUF)) == sorted(set(SHUF)) else "no")
sval("inv_dict_sorted",
     lambda: "yes" if list(SortedDict.fromkeys(SHUF, 0)) == sorted(SHUF) else "no")

# AND THE INVARIANT SURVIVES A LONG RANDOMISED SEQUENCE, which is the one thing
# the hand-written cases above cannot do: they each exercise one call, and the
# failure mode of a B-tree-ish structure is a rebalance that only goes wrong at
# a size or a sequence nobody wrote down. `random` is seeded with a LITERAL, so
# the sequence is the same on every image and on the x86-64 control -- a case
# that reds here reds reproducibly, which an unseeded one would not.
import random


def stress():
    rnd = random.Random(20120901)
    sl, ref = SortedList(), []
    for _ in range(4000):
        op = rnd.randrange(3)
        v = rnd.randrange(500)
        if op == 0 or not ref:
            sl.add(v)
            ref.append(v)
        elif op == 1:
            v = ref.pop(rnd.randrange(len(ref)))
            sl.remove(v)
        else:
            i = rnd.randrange(len(ref))
            if sl[i] != sorted(ref)[i]:
                return "index-mismatch-at-%d" % i
    with _quiet():
        sl._check()
    return "yes" if list(sl) == sorted(ref) else "order-mismatch"


sval("stress_list", stress)


def stress_dict():
    rnd = random.Random(20120902)
    sd, ref = SortedDict(), {}
    for _ in range(3000):
        k = "k%03d" % rnd.randrange(400)
        if rnd.randrange(3) == 0 and ref:
            k = rnd.choice(sorted(ref))
            del sd[k]
            del ref[k]
        else:
            sd[k] = len(ref)
            ref[k] = len(ref) - (1 if k in ref else 0)
    return "yes" if list(sd) == sorted(ref) else "order-mismatch"


sval("stress_dict", stress_dict)


def stress_set():
    rnd = random.Random(20120903)
    ss, ref = SortedSet(), set()
    for _ in range(3000):
        v = rnd.randrange(300)
        if rnd.randrange(3) == 0 and ref:
            v = rnd.choice(sorted(ref))
            ss.discard(v)
            ref.discard(v)
        else:
            ss.add(v)
            ref.add(v)
    return "yes" if list(ss) == sorted(ref) else "order-mismatch"


sval("stress_set", stress_set)

# ------------------------------------------------------------- the trailer ---
# Emitted last, and the suite asserts both: `probe_done` says the probe reached
# the end, `emitted_count` says nothing between the first key and this line was
# skipped. Together they make every got:'' above readable as a missing KEY
# rather than as a missing RUN.
emit("emitted_count", COUNT + 1)
sys.stdout.write("probe_done=yes\n")