From 5262bb2da6fee480e1ee6f402ae3daa55bc6a808 Mon Sep 17 00:00:00 2001 From: Axy Date: Sat, 21 Mar 2026 02:43:14 +0100 Subject: [PATCH] Fixed dumb issue with quadtree, only need a few more touch-ups and it should be done --- __main__.py | 2 +- amazeing/maze_display/TTYdisplay.py | 14 ++++----- amazeing/utils/__init__.py | 6 ++-- amazeing/utils/avl.py | 22 ++++++++++++-- amazeing/utils/bi_map.py | 46 +++++++++++++++++++---------- amazeing/utils/quadtree.py | 5 +++- 6 files changed, 62 insertions(+), 33 deletions(-) diff --git a/__main__.py b/__main__.py index 836e648..81d3e84 100644 --- a/__main__.py +++ b/__main__.py @@ -16,7 +16,7 @@ from amazeing.maze_class.maze_dirty_tracker import MazeDirtyTracker from amazeing.maze_class.maze_pacman_tracker import MazePacmanTracker from amazeing.maze_display.TTYdisplay import TileCycle, TileMaps, extract_pairs from amazeing.maze_display.backend import CloseRequested, IVec2 -from amazeing.utils import quadtree +from amazeing.utils import QuadTree config = Config.parse(open("./example.conf").read()) diff --git a/amazeing/maze_display/TTYdisplay.py b/amazeing/maze_display/TTYdisplay.py index 162e746..df580e5 100644 --- a/amazeing/maze_display/TTYdisplay.py +++ b/amazeing/maze_display/TTYdisplay.py @@ -1,7 +1,6 @@ from abc import ABC, abstractmethod from collections.abc import Callable, Generator, Iterable -import time -from amazeing.utils import BiMap +from amazeing.utils import BiMap, AVLTree from amazeing.config.config_parser import Color, Config, ColoredLine, ColorPair from amazeing.maze_display.layout import ( BInt, @@ -470,7 +469,6 @@ class TTYBackend: self.__filler: None | int = None self.__style_bimap: BiMap[int, IVec2] = BiMap() - self.__style_rename_bimap: BiMap[int, int] = BiMap() self.__bg_init: Callable[[IVec2], int] | None = None def __del__(self) -> None: @@ -492,8 +490,6 @@ class TTYBackend: for tile in redrawn.tiles(): if self.__style_bimap.revcontains(tile): style = self.__style_bimap.revget(tile) - if self.__style_rename_bimap.revcontains(style): - style = self.__style_rename_bimap.revget(style) self.set_style(style) self.draw_tile(tile) elif self.__bg_init is not None: @@ -511,8 +507,8 @@ class TTYBackend: def set_bg_init(self, bg_init: Callable[[IVec2], int]) -> None: self.__bg_init = bg_init - def get_styled(self, style: int) -> set[IVec2]: - return self.__style_bimap.get(style) + def get_style_height(self, style: int) -> int: + return self.__style_bimap.get(style).height() def map_style_cb(self) -> Callable[[int], None]: curr: int | None = None @@ -523,9 +519,9 @@ class TTYBackend: curr = new if curr == new: return - if len(self.get_styled(curr)) != 0: + if self.get_style_height(curr) != 0: self.__drawn = QuadTree() - self.__style_rename_bimap.add(new, curr) + self.__style_bimap.key_map(curr, new) curr = new return inner diff --git a/amazeing/utils/__init__.py b/amazeing/utils/__init__.py index 30fd547..5db6856 100644 --- a/amazeing/utils/__init__.py +++ b/amazeing/utils/__init__.py @@ -1,7 +1,5 @@ from .bi_map import BiMap -from .avl import Tree as AVLTree -from .avl import Leaf as AVLLeaf -from .quadtree import Tree as QuadTree -from .quadtree import Rect +from .avl import Tree as AVLTree, Leaf as AVLLeaf +from .quadtree import Tree as QuadTree, Rect __all__ = ["BiMap", "AVLTree", "AVLLeaf", "QuadTree", "Rect"] diff --git a/amazeing/utils/avl.py b/amazeing/utils/avl.py index b77a430..08b82ba 100644 --- a/amazeing/utils/avl.py +++ b/amazeing/utils/avl.py @@ -1,4 +1,5 @@ -from collections.abc import Callable +from abc import ABC, abstractmethod +from collections.abc import Callable, Iterator from typing import cast import textwrap @@ -14,6 +15,11 @@ class Tree[T]: if self.root is not None: self.root.validate() + def __iter__(self) -> Iterator[T]: + if self.root is None: + return () + return iter(self.root) + def append(self, value: T) -> "Leaf[T]": if self.root is None: leaf = Leaf(self, value) @@ -118,11 +124,14 @@ class Tree[T]: parent.balance_one_propagate() -class Node[T]: +class Node[T](ABC): def __init__(self, parent: "Branch[T] | Tree[T]") -> None: self.parent: Branch[T] | Tree[T] = parent self.height: int = 1 + @abstractmethod + def __iter__(self) -> Iterator[T]: ... + def validate(self) -> None: visited = set() border: list[Node[T]] = [self] @@ -179,6 +188,12 @@ class Branch[T](Node[T]): self.rhs: Node[T] = rhs(self) self.update_height() + def __iter__(self) -> Iterator[T]: + for e in self.lhs: + yield e + for e in self.rhs: + yield e + def __repr__(self) -> str: return ( f"lhs ({self.lhs.height}):\n" @@ -365,6 +380,9 @@ class Leaf[T](Node[T]): super().__init__(parent) self.value: T = value + def __iter__(self) -> Iterator[T]: + yield self.value + def __repr__(self) -> str: return f"leaf: {self.value}" diff --git a/amazeing/utils/bi_map.py b/amazeing/utils/bi_map.py index 25ca372..ea331b2 100644 --- a/amazeing/utils/bi_map.py +++ b/amazeing/utils/bi_map.py @@ -1,38 +1,52 @@ -from collections.abc import Iterable +from .avl import Tree as AVLTree, Leaf as AVLLeaf class BiMap[K, R]: def __init__(self) -> None: - self.__map: dict[K, set[R]] = {} - self.__revmap: dict[R, K] = {} + self.__map: dict[K, AVLTree[R]] = {} + self.__revmap: dict[AVLTree[R], K] = {} + self.__leafmap: dict[R, AVLLeaf[R]] = {} def add(self, key: K, revkey: R) -> None: if self.revcontains(revkey): self.revremove(revkey) if not self.contains(key): - self.__map[key] = set() - self.__revmap[revkey] = key - self.__map[key].add(revkey) + tree = AVLTree() + self.__map[key] = tree + self.__revmap[tree] = key + self.__leafmap[revkey] = self.__map[key].append(revkey) def remove(self, key: K) -> None: for revkey in self.__map[key]: - self.__revmap.pop(revkey) - self.__map.pop(key) + self.__leafmap.pop(revkey) + self.__revmap.pop(self.__map.pop(key)) def revremove(self, revkey: R) -> None: - key = self.__revmap.pop(revkey) - self.__map[key].remove(revkey) - if len(self.__map[key]) == 0: - self.__map.pop(key) + leaf = self.__leafmap.pop(revkey) + root = leaf.root() + leaf.remove() + if root.height() == 0: + self.__map.pop(self.__revmap.pop(root)) - def get(self, key: K) -> set[R]: - return self.__map[key] if self.contains(key) else set() + def get(self, key: K) -> AVLTree[R]: + return self.__map[key] if self.contains(key) else AVLTree() def revget(self, revkey: R) -> K: - return self.__revmap[revkey] + return self.__revmap[self.__leafmap[revkey].root()] + + def key_map(self, src: K, dst: K) -> None: + if src == dst: + return + if src not in self.__map: + return + if dst not in self.__map: + tree = AVLTree() + self.__map[dst] = tree + self.__revmap[tree] = dst + self.__map[dst].rjoin(self.__map.pop(src)) def contains(self, key: K) -> bool: return key in self.__map def revcontains(self, revkey: R) -> bool: - return revkey in self.__revmap + return revkey in self.__leafmap diff --git a/amazeing/utils/quadtree.py b/amazeing/utils/quadtree.py index 222e11b..a3a7152 100644 --- a/amazeing/utils/quadtree.py +++ b/amazeing/utils/quadtree.py @@ -76,6 +76,9 @@ class Tree: case (e, False, False, False): res.__height -= 1 res.__root = e + case False: + res.__height = 0 + return res case _: return res @@ -91,7 +94,7 @@ class Tree: a = descend(a, depth + 1) return Tree.node_normalize((a, b, c, d)) - res.__root = descend(self.__root) + res.__root = descend(res.__root) return res.normalized() def __or__(self, other: "Tree") -> "Tree": -- 2.53.0