"""Corre los ejemplos de la semana y comprueba lo que se puede contar: nunca tiempos.""" import math import pathlib import re import subprocess import unittest HERE = pathlib.Path(__file__).parent SAN = ["g++", "-Wall", "-Wextra", "-std=c++20", "-g", "-fsanitize=address,undefined"] 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 bound(n): return 2 * math.log2(n + 1) - 1 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/rb_trace", "1", "2", "3"], ["build/tree_234_trace", "1", "2", "3", "4"], ["build/height_bound"], ["build/btree_levels"]]: with self.subTest(program=command[0]): done = run(*command) self.assertEqual(done.returncode, 0, done.stdout) def test_review_question(self): """La pregunta 4 de la guía: 10, 20, 30, 15 y 25.""" lines = run("build/rb_trace", "10", "20", "30", "15", "25").stdout.splitlines() self.assertIn("insertar 30: 20(10r,30r)", lines) self.assertIn(" en 10: tio negro, en linea: una rotacion", lines) self.assertIn("insertar 15: 20(10(_,15r),30)", lines) self.assertIn(" en 20: tio rojo: recolorear", lines) self.assertIn(" en 20: raiz roja: pintar de negro", lines) self.assertEqual(lines[-3:-1], ["insertar 25: 20(10(_,15r),30(25r,_))", " 2-3-4: [20]([10 15],[25 30])"]) self.assertEqual(lines[-1], "altura 2, negros 2, rotaciones 1, recoloreos 1") def test_every_order_rotates_at_most_twice(self): rows = run("build/all_orders").stdout.splitlines()[1:] self.assertEqual(len(rows), 9) for row in rows: fields = row.split() n, max_height, rotations = int(fields[0]), int(fields[3]), int(fields[5]) self.assertLessEqual(rotations, 2) if n >= 3: self.assertEqual(rotations, 2) self.assertLessEqual(max_height, bound(n)) self.assertEqual(fields[7], "si") def test_collapse_matches_only_with_the_same_split_policy(self): lines = run("build/collapse_check").stdout.splitlines() rows = [line.split() for line in lines[1:10]] self.assertEqual([int(row[0]) for row in rows], list(range(1, 10))) for row in rows: self.assertEqual(row[2], "0") self.assertGreater(int(rows[3][3]), 0) self.assertEqual(rows[7][4], "0") self.assertGreater(int(rows[8][4]), 0) self.assertIn(" al hacer overflow, sube la del medio de las 3: ninguno", lines) self.assertIn(" al hacer overflow, sube siempre la segunda de las 4: 1 3 4 2", lines) self.assertIn(" al bajar, se divide todo nodo lleno: 1 2 3 4 5 6 7 8 9", lines) for seed in [12, 13, 14]: self.assertIn(f" semilla {seed}: calza", lines) def test_each_234_tree_has_two_to_the_t_shapes(self): done = run("build/all_shapes") self.assertEqual(done.returncode, 0, done.stdout) for row in done.stdout.splitlines()[1:]: n, trees, groups, total, reachable, height, inserted, _ = row.split() self.assertEqual(trees, total) self.assertLessEqual(int(groups), int(trees)) self.assertLessEqual(int(reachable), int(trees)) self.assertLessEqual(int(inserted), int(height)) self.assertLessEqual(int(height), bound(int(n))) def test_tallest_tree_agrees_with_generating_them_all(self): fewest = {} for row in run("build/height_bound").stdout.splitlines()[1:]: h, nodes, _, printed, _ = row.split() fewest[int(h)] = int(nodes) self.assertLessEqual(int(h), bound(int(nodes))) self.assertLess(bound(int(nodes)) - int(h), 2.2) self.assertAlmostEqual(float(printed), bound(int(nodes)), places=2) for row in run("build/all_shapes").stdout.splitlines()[1:]: fields = row.split() n, tallest = int(fields[0]), int(fields[5]) self.assertLessEqual(fewest[tallest], n) if tallest + 1 in fewest: self.assertGreater(fewest[tallest + 1], n) def test_counts_table(self): rows = run("build/count_table").stdout.splitlines()[1:] self.assertEqual(len(rows), 9) for row in rows: name, n, avl, rb, recolors, max_rotations, max_recolors = row.split() self.assertLessEqual(int(max_rotations), 2) if name == "azar": self.assertLess(float(rb), 0.86 * float(avl)) else: self.assertEqual(int(max_rotations), 1) self.assertLessEqual(abs(float(rb) - float(avl)), 0.01) 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, rb = int(fields[0]), int(fields[3]), int(fields[4]) self.assertEqual(avl, math.floor(math.log2(n))) self.assertLess(rb, bound(n)) self.assertGreater(rb, 1.6 * avl) for row in lines[split + 2:]: fields = row.split() n = int(fields[0]) avl = [int(field) for field in fields[3:6]] rb = [int(field) for field in fields[6:9]] self.assertLessEqual(max(rb), max(avl) + 1) self.assertLessEqual(max(avl), max(rb)) self.assertLess(max(rb), bound(n)) self.assertLess(float(fields[10]) / float(fields[9]), 1.02) def test_btree_levels(self): rows = [line.split() for line in run("build/btree_levels").stdout.splitlines()[1:]] self.assertEqual(dict((int(a), int(b)) for a, b in rows), {1: 30, 3: 15, 15: 8, 100: 5, 500: 4, 1000: 3}) class SameRotations(unittest.TestCase): """Las rotaciones del rojinegro son las de la semana 11, sin cambiar nada.""" def body(self, path, name): text = (HERE / path).read_text(encoding="utf-8") match = re.search(r"Node\* %s\(Node\* x\) \{.*?\n \}\n" % name, text, re.S) self.assertIsNotNone(match, f"falta {name} en {path}") return match.group(0) @unittest.skipUnless((HERE / "solution").is_dir(), "no está la solución") def test_rotations_are_copied_verbatim(self): for name in ["rotate_left", "rotate_right"]: self.assertEqual(self.body("solution/red_black_map.h", name), self.body("lab/avl_map.h", name)) def test_no_erase_is_offered(self): for path in ["lab/red_black_map.h", "rb_set.h"]: self.assertNotIn("erase", (HERE / path).read_text(encoding="utf-8")) 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_root_paint(self): done = run(self.build("no_root_paint")) self.assertNotEqual(done.returncode, 0) self.assertIn("encuentra el 40: si", done.stdout) self.assertIn("Assertion `!is_red(root_)'", done.stdout) def test_new_node_black(self): done = run(self.build("new_node_black")) self.assertNotEqual(done.returncode, 0) self.assertIn("Assertion `left == right'", 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(_,30r(20r,_))", done.stdout) def test_no_repaint_after_rotation(self): done = run(self.build("no_repaint_after_rotation")) self.assertNotEqual(done.returncode, 0) self.assertIn("insertar 30: 20(10,30r)", done.stdout) if __name__ == "__main__": unittest.main()