"""Corre los ejemplos de la semana y comprueba lo que se puede contar: nunca tiempos.""" import math import os import pathlib import subprocess import unittest HERE = pathlib.Path(__file__).parent DATA = os.environ.get("DATA", "../../data") WORDS = f"{DATA}/palabras.txt" SAN = ["g++", "-Wall", "-Wextra", "-std=c++20", "-g", "-fsanitize=address,undefined"] PHI = (1 + math.sqrt(5)) / 2 def run(*command): return subprocess.run( list(command), cwd=HERE, text=True, encoding="utf-8", errors="replace", stdin=subprocess.DEVNULL, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=300, ) def min_nodes(limit): """N(h) para h = 0..limit, con enteros de Python: no hay overflow.""" values = [1, 2] while len(values) <= limit: values.append(values[-1] + values[-2] + 1) return values class Examples(unittest.TestCase): def test_structure_tests_pass(self): done = run("build/test_structures") self.assertEqual(done.returncode, 0, done.stdout) self.assertIn("ok", done.stdout) def test_programs_exit_cleanly(self): for command in [["build/avl_trace", "1", "2", "3", "-1"], ["build/rotation_demo"], ["build/min_nodes"], ["build/all_orders"]]: with self.subTest(program=command[0]): done = run(*command) self.assertEqual(done.returncode, 0, done.stdout) def test_every_order_needs_at_most_one_repair(self): rows = run("build/all_orders").stdout.splitlines()[1:] self.assertEqual(len(rows), 9) for row in rows: n, _, _, _, repairs, rotations = (int(field) for field in row.split()) self.assertLessEqual(repairs, 1) self.assertLessEqual(rotations, 2) if n >= 3: self.assertEqual((repairs, rotations), (1, 2)) def test_repairs_and_heights_table(self): lines = run("build/repair_counts").stdout.splitlines() self.assertNotIn("se paso de h / 2", lines) split = lines.index("Borrar la clave mayor de un arbol de Fibonacci") for row in lines[1:split]: fields = row.rsplit(None, 4) maximum, bound = int(fields[3]), int(fields[4]) if row.lstrip().startswith("insertar"): self.assertEqual(maximum, 1) else: self.assertLessEqual(maximum, bound) for row in lines[split + 2:]: h, _, repairs, rotations, half, after = (int(field) for field in row.split()) self.assertEqual(repairs, h // 2) self.assertEqual(half, h // 2) self.assertEqual(rotations, repairs) self.assertEqual(after, h - 1) def test_height_table(self): lines = run("build/height_table").stdout.splitlines() split = lines.index("Claves al azar, tres semillas") for row in lines[2:split]: fields = row.split() n, avl = int(fields[0]), int(fields[3]) self.assertEqual(avl, math.floor(math.log2(n))) if fields[4] != "-": self.assertEqual(int(fields[4]), n - 1) for row in lines[split + 2:]: fields = row.split() limit = float(fields[2]) for avl in fields[3:6]: self.assertLess(int(avl), limit) for plain in fields[7:10]: self.assertGreater(int(plain), limit) def test_dictionary_shape_is_counted(self): lines = run("build/dictionary_avl", WORDS).stdout.splitlines() self.assertEqual(lines[0], "orden de bytes: si") self.assertIn("1045757 palabras, altura 19, rotaciones 1045737,", lines[1]) self.assertIn("1045757 palabras, altura 23,", lines[3]) self.assertIn("1045757 palabras, altura 49,", lines[5]) class HeightBound(unittest.TestCase): """Con enteros exactos, la cota que dicen los apuntes para los AVL más flacos.""" def test_min_nodes_is_fibonacci_minus_one(self): nodes = min_nodes(400) fib = [0, 1] while len(fib) < 410: fib.append(fib[-1] + fib[-2]) for h, n in enumerate(nodes): self.assertEqual(n, fib[h + 3] - 1) self.assertEqual(nodes[4], 12) def test_exact_bound_holds_and_is_tight(self): constant = 1 / math.log2(PHI) shift = math.log(math.sqrt(5), PHI) - 3 self.assertAlmostEqual(constant, 1.4404, places=4) self.assertAlmostEqual(shift, -1.3277, places=4) for h, n in enumerate(min_nodes(1400)): bound = constant * math.log2(n + 2) + shift self.assertLess(h, bound + 1e-9) if h >= 20: self.assertLess(bound - h, 0.01) def test_printed_constants_are_a_true_bound(self): """Los números tal como salen en los apuntes. Con 1.4404, redondeado hacia abajo, ya no vale.""" nodes = min_nodes(1400) for h, n in enumerate(nodes): self.assertLess(h, 1.4405 * math.log2(n + 2) - 1.3277) self.assertGreater(18, 1.4404 * math.log2(nodes[18] + 2) - 1.3277) def test_simple_bound_with_two(self): for h, n in enumerate(min_nodes(1400)): self.assertLess(h, 2 * math.log2(n + 1)) def test_rounded_constant_fails_only_for_huge_n(self): """1.44 es menor que la constante de verdad: h <= 1.44 log2 n termina fallando, muy lejos.""" nodes = min_nodes(5000) failures = [h for h, n in enumerate(nodes) if h > 1.44 * math.log2(n)] self.assertTrue(failures) first = failures[0] self.assertGreater(first, 4000) digits = len(str(nodes[first])) self.assertGreater(digits, 900) # Desde ahí ya no vuelve a valer. self.assertEqual(failures, list(range(first, len(nodes)))) class DeliberateErrors(unittest.TestCase): def build(self, name): binary = f"build/{name}" done = run(*SAN, f"errors/{name}.cpp", "-o", binary) self.assertEqual(done.returncode, 0, done.stdout) return binary def test_no_height_update(self): done = run(self.build("no_height_update")) self.assertNotEqual(done.returncode, 0) self.assertIn("Assertion", done.stdout) self.assertNotIn("no vio nada", done.stdout) def test_parent_before_child(self): done = run(self.build("parent_before_child")) self.assertNotEqual(done.returncode, 0) self.assertIn("altura real 1, altura guardada 3", done.stdout) def test_single_on_zigzag(self): done = run(self.build("single_on_zigzag")) self.assertNotEqual(done.returncode, 0) self.assertIn("insertar 20: 10(_,30(20,_))", done.stdout) def test_stop_after_first_repair(self): done = run(self.build("stop_after_first_repair")) self.assertNotEqual(done.returncode, 0) self.assertIn("todas pasan check_invariants", done.stdout) self.assertIn("Assertion", done.stdout) if __name__ == "__main__": unittest.main()