"""Stdlib-only tests (no pytest): plain asserts in functions called from a __main__ block. Run: `python3 test_inverted_index.py`. The headline test pins the exact step counts the commentary quotes, so the numbers on that page cannot rot silently. The rest check the pieces: postings come out sorted and deduplicated, `gallop_index` agrees with `bisect_left` on every input, and the two intersection strategies always return the same hits however much their costs differ. """ import random from bisect import bisect_left from functools import partial from demo import make_corpus from inverted_index import ( Steps, build_index, document_frequency, gallop_index, intersect_gallop, intersect_linear, query, tokenize, ) GALLOP_FROM_LONGEST = partial(intersect_gallop, drive_shortest=False) # Built once: the corpus is a pure function of SEED, so every test below sees # the identical index the demo printed. INDEX = build_index(make_corpus()) def test_document_frequencies_are_pinned(): """The seeded corpus produces exactly these postings list lengths.""" assert document_frequency(INDEX, "the") == 8526 assert document_frequency(INDEX, "of") == 6064 assert document_frequency(INDEX, "search") == 1246 assert document_frequency(INDEX, "ranking") == 2001 assert document_frequency(INDEX, "obelisk") == 5 assert document_frequency(INDEX, "quantum") == 2 assert document_frequency(INDEX, "nonexistent") == 0 def test_headline_intersection_order(): """`the AND obelisk`: same 5 hits three ways, costs 113x apart.""" hits_short, steps_short = query(INDEX, ("the", "obelisk"), intersect_gallop) hits_lin, steps_lin = query(INDEX, ("the", "obelisk"), intersect_linear) hits_long, steps_long = query(INDEX, ("the", "obelisk"), GALLOP_FROM_LONGEST) assert hits_short == hits_lin == hits_long == [4872, 5669, 6222, 6499, 7267] assert (steps_short, steps_lin, steps_long) == (110, 6204, 12409) assert steps_long // steps_short == 112 # 12409 / 110 = 112.8 -> "113x" def test_adding_a_selective_term_makes_the_query_cheaper(): """The opener: `the` costs 8526 steps, `the AND quantum` costs 52.""" solo, solo_steps = query(INDEX, ("the",), intersect_gallop) pair, pair_steps = query(INDEX, ("the", "quantum"), intersect_gallop) assert len(solo) == 8526 and solo_steps == 8526 assert pair == [6659] and pair_steps == 52 # ...and the opposite when the added term is not selective: `search` # covers 12% of the corpus, so the AND costs *more* than `the` alone. _, wide_steps = query(INDEX, ("the", "search"), intersect_gallop) assert wide_steps == 8570 > solo_steps def test_galloping_loses_when_the_lists_are_the_same_size(): """The boundary condition: no selectivity skew, no win.""" _, gallop_steps = query(INDEX, ("of", "the"), intersect_gallop) _, linear_steps = query(INDEX, ("of", "the"), intersect_linear) assert (gallop_steps, linear_steps) == (17632, 9438) assert gallop_steps > linear_steps # The crossover sits between 4:1 and 7:1 skew against `the`. _, g4 = query(INDEX, ("the", "ranking"), intersect_gallop) # 8526/2001 = 4:1 _, l4 = query(INDEX, ("the", "ranking"), intersect_linear) _, g7 = query(INDEX, ("the", "search"), intersect_gallop) # 8526/1246 = 7:1 _, l7 = query(INDEX, ("the", "search"), intersect_linear) assert g4 > l4, "at 4:1 skew, linear still wins" assert g7 < l7, "at 7:1 skew, galloping has taken over" def test_both_strategies_always_agree(): """Cost differs wildly; results never do.""" terms = ["the", "of", "and", "search", "index", "obelisk", "quantum"] for i, left in enumerate(terms): for right in terms[i + 1:]: a, _ = query(INDEX, (left, right), intersect_gallop) b, _ = query(INDEX, (left, right), intersect_linear) c, _ = query(INDEX, (left, right), GALLOP_FROM_LONGEST) assert a == b == c, (left, right, a, b, c) def test_postings_are_sorted_and_deduplicated(): """Doc ids are assigned in corpus order, so no sort is ever needed.""" for term, postings in INDEX.items(): assert postings == sorted(postings), term assert len(postings) == len(set(postings)), term # A term repeated inside one document contributes exactly one posting. index = build_index(["the cat the cat the", "a dog", "THE end"]) assert index["the"] == [0, 2] assert index["cat"] == [0] assert index["dog"] == [1] def test_tokenize_lowercases_and_splits_on_whitespace(): assert tokenize("The QUICK\tbrown\nfox") == ["the", "quick", "brown", "fox"] assert tokenize(" ") == [] def test_gallop_index_matches_bisect_left(): """Galloping is an optimisation, not a different answer.""" rng = random.Random(7) for _ in range(200): postings = sorted(rng.sample(range(500), rng.randint(1, 60))) for target in range(-2, 502, 7): for start in (0, len(postings) // 2, len(postings)): expected = max(start, bisect_left(postings, target)) got = gallop_index(postings, start, target, Steps()) assert got == expected, (postings, start, target, got, expected) def test_empty_and_missing_terms(): """A term nobody indexed makes the AND free, not expensive.""" hits, steps = query(INDEX, ("the", "nonexistent"), intersect_gallop) assert hits == [] assert steps == 0 TESTS = [ test_document_frequencies_are_pinned, test_headline_intersection_order, test_adding_a_selective_term_makes_the_query_cheaper, test_galloping_loses_when_the_lists_are_the_same_size, test_both_strategies_always_agree, test_postings_are_sorted_and_deduplicated, test_tokenize_lowercases_and_splits_on_whitespace, test_gallop_index_matches_bisect_left, test_empty_and_missing_terms, ] if __name__ == "__main__": failed = 0 for test in TESTS: try: test() except AssertionError as exc: failed += 1 print(f"FAIL {test.__name__}: {exc}") else: print(f"PASS {test.__name__}") if failed: print(f"\n{failed} of {len(TESTS)} tests FAILED") raise SystemExit(1) print(f"\nAll {len(TESTS)} tests PASSED")