Repository: tmcclintock/donjuan

Issue:
Refactor Room
The `Space` class is the parent of `Room` and `Hallway`. It has a 2D array of `Cell`s, but this is not ideal because we would like spaces to be non-rectangular. After discussion with @jammcc we are going to do  the following refactors:

- [ ] create a single `Room` class
- [ ] a `Room` has a dictionary of cells with keys being the cell coordinates
- [ ] a `Cell` has an optional (i.e. it can be `None`) attribute that is the `Room` it is a part of

These upgrades will make things a lot easier going forward, especially wall finding. It also means that the proposed `Edge` class in #34 is only ever seen in the `Grid` class, which makes sense since that is the only class that should have to be a rectangle.

Discussion:

Patch:
diff --git a/donjuan/cell.py b/donjuan/cell.py
index 276c7b1..18c83a3 100644
--- a/donjuan/cell.py
+++ b/donjuan/cell.py
@@ -1,5 +1,5 @@
 from abc import ABC
-from typing import Any, List, Optional, Tuple
+from typing import Any, List, Optional, Tuple, Type
 
 from donjuan.door_space import DoorSpace
 from donjuan.face import Faces, HexFaces, SquareFaces
@@ -19,6 +19,7 @@ class Cell(ABC):
         door_space: Optional[DoorSpace] = None,
         contents: Optional[List[Any]] = None,
         coordinates: Optional[Tuple[int, int]] = None,
+        space: Optional["Space"] = None,
     ):
         self.faces = faces
         self.filled = filled
@@ -28,10 +29,14 @@ class Cell(ABC):
             self._coordinates = [0, 0]
         else:
             self._coordinates = list(coordinates)
+        self._space = space
 
     def set_coordinates(self, y: int, x: int) -> None:
         self._coordinates = [int(y), int(x)]
 
+    def set_space(self, space: Type["Space"]) -> None:
+        self._space = space
+
     def set_x(self, x: int) -> None:
         self._coordinates[1] = int(x)
 
@@ -42,6 +47,11 @@ class Cell(ABC):
     def coordinates(self) -> Tuple[int, int]:
         return tuple(self._coordinates)
 
+    @property
+    def space(self) -> Optional[Type["Space"]]:
+        """``Space`` this cell is a part of."""
+        return self._space
+
     @property
     def x(self) -> int:
         return self._coordinates[1]
diff --git a/donjuan/dungeon.py b/donjuan/dungeon.py
index 2145bc1..65e0136 100644
--- a/donjuan/dungeon.py
+++ b/donjuan/dungeon.py
@@ -66,8 +66,6 @@ class Dungeon:
         Args:
             room (Room): room to emplace in the :attr:`grid`
         """
-        for i in range(room.n_rows):
-            for j in range(room.n_cols):
-                cell = room.cells[i][j]
-                self.grid.cells[cell.y][cell.x] = cell
+        for cell in room.cells:
+            self.grid.cells[cell.y][cell.x] = cell
         return
diff --git a/donjuan/room.py b/donjuan/room.py
index 175c5ab..c754dc8 100644
--- a/donjuan/room.py
+++ b/donjuan/room.py
@@ -1,4 +1,4 @@
-from typing import List, Optional, Union
+from typing import Optional, Set, Union
 
 from donjuan.cell import Cell
 from donjuan.space import Space
@@ -6,14 +6,13 @@ from donjuan.space import Space
 
 class Room(Space):
     """
-    A room in a dungeon. Rooms can have names. In future versions, rooms
-    will have additional features.
+    A room in a dungeon. A room has is a named ``Space``.
     """
 
     def __init__(
-        self, cells: Optional[List[List[Cell]]] = None, name: Union[int, str] = ""
+        self, cells: Optional[Set[Cell]] = None, name: Union[int, str] = "",
     ):
-        super().__init__(cells=cells or [[]])
+        super().__init__(cells=cells)
         assert isinstance(name, (int, str))
         self._name = name
 
@@ -24,13 +23,3 @@ class Room(Space):
     def set_name(self, name: Union[int, str]) -> None:
         self._name = name
         return
-
-    @property
-    def n_rows(self) -> int:
-        if self.cells == [[]]:
-            return 0  # special case
-        return len(self.cells)
-
-    @property
-    def n_cols(self) -> int:
-        return len(self.cells[0])
diff --git a/donjuan/room_randomizer.py b/donjuan/room_randomizer.py
index 4e240dd..cf3bc97 100644
--- a/donjuan/room_randomizer.py
+++ b/donjuan/room_randomizer.py
@@ -36,10 +36,11 @@ class RoomSizeRandomizer(Randomizer):
 
         # Create empty cells and set them in the room
         cells = [
-            [self.cell_type(filled=False, coordinates=(i, j)) for j in range(height)]
+            self.cell_type(filled=False, coordinates=(i, j))
+            for j in range(height)
             for i in range(width)
         ]
-        room.set_cells(cells)
+        room.insert_cell_list(cells)
         return
 
 
@@ -72,14 +73,22 @@ class AlphaNumRoomName(Randomizer):
 
 class RoomPositionRandomizer(Randomizer):
     """
-    Randomly shift a room, assuming it has :attr:`n_cols`
-    and :attr:`n_rows` attributes.
+    Randomly shift a room, assuming its left edge is at column 0 and it's top
+    edge is at row 0.
     """
 
     def randomize_room_position(self, room: Room, dungeon: Dungeon) -> None:
+        """
+        Args:
+            room (Room): room to move around
+            dungeon (Dungeon): dungeon to move the room around in
+        """
+        # Determing the right-most and bottom-most cells of the room
+        bottom = max(room.cell_coordinates, key=lambda x: x[0])[0]
+        right = max(room.cell_coordinates, key=lambda x: x[1])[1]
         # Draw random positions and shift
-        room.shift_horizontal(random.randint(0, dungeon.n_cols - room.n_cols))
-        room.shift_vertical(random.randint(0, dungeon.n_rows - room.n_rows))
+        room.shift_horizontal(random.randint(0, dungeon.n_cols - right - 1))
+        room.shift_vertical(random.randint(0, dungeon.n_rows - bottom - 1))
         return
 
 
diff --git a/donjuan/space.py b/donjuan/space.py
index b283d9d..d8f98a6 100644
--- a/donjuan/space.py
+++ b/donjuan/space.py
@@ -1,48 +1,71 @@
 from abc import ABC
-from itertools import chain
-from typing import List
+from typing import List, Optional, Set, Tuple
 
 from donjuan.cell import Cell
 
 
 class Space(ABC):
     """
-    A space is a section of a dungeon composed of cells.
+    A space is a section of a dungeon composed of `Cell`s. This object
+    contains these cells in a ``set`` under the property :attr:`cells`.
+
+    Args:
+        cells (Optional[Set[Cell]]): cells that make up this space
     """
 
-    def __init__(self, cells: List[List[Cell]]):
-        self._cells = cells
+    def __init__(self, cells: Optional[Set[Cell]] = None):
+        self._cells = cells or set()
+        self.assign_space_to_cells()
+        self.reset_cell_coordinates()
+
+    def assign_space_to_cells(self) -> None:
+        """Set the :attr:`space` attribute for each `Cell` to ``self``."""
+        for cell in self.cells:
+            cell.set_space(self)
+
+    def reset_cell_coordinates(self) -> None:
+        self._cell_coordinates = set(cell.coordinates for cell in self.cells)
 
     @property
-    def cells(self) -> List[List[Cell]]:
+    def cells(self) -> Set[Cell]:
         return self._cells
 
-    def set_cells(self, cells: List[List[Cell]]) -> None:
-        assert isinstance(cells, list)
+    @property
+    def cell_coordinates(self) -> Set[Tuple[int, int]]:
+        return self._cell_coordinates
+
+    def insert_cell_list(self, cells: List[Cell]) -> None:
+        """
+        Insert a list of cells into the :attr:`cells` set, with
+        keys being the coordinates of the cells.
+
+        Args:
+            cells (List[Cell]): list of cells to insert
+        """
         if len(cells) > 0:
-            assert isinstance(cells[0], list)
-            if len(cells[0]) > 0:
-                assert isinstance(cells[0][0], Cell)
-        self._cells = cells
+            assert isinstance(cells[0], Cell)
+        for cell in cells:
+            self.cells.add(cell)
+            self.cell_coordinates.add(cell.coordinates)
 
     def overlaps(self, other: "Space") -> bool:
         """
-        Compare the cells of this room to the other room to determine
-        whether they overlap or not. Note, this algorithm is ``O(N*M)``
-        where ``N`` is the number of cells in this room and ``M`` is
-        the number of cells in the other room.
+        Compare the cells of this space to the other space to determine
+        whether they overlap or not. Note, this algorithm is ``O(N)``
+        where ``N`` is the number of cells in this space, since set
+        lookup is ``O(1)``.
 
         Args:
-            other (Room): other room to check against
+            other (Space): other space to check against
 
         Returns:
             ``True`` if they overlap, ``False`` if not
         """
         # Loop over all of this space's cells
-        for c1 in chain.from_iterable(self._cells):
-            for c2 in chain.from_iterable(other._cells):
-                if c1.coordinates == c2.coordinates:
-                    return True
+        for cell in self.cells:
+            if cell.coordinates in other.cell_coordinates:
+                return True
+
         # No overlap
         return False
 
@@ -53,8 +76,9 @@ class Space(ABC):
         Args:
             n (int): number to increment vertical position of cells
         """
-        for c in chain.from_iterable(self.cells):
-            c.set_y(c.y + int(n))
+        for cell in self.cells:
+            cell.set_y(cell.y + int(n))
+        self.reset_cell_coordinates()
         return
 
     def shift_horizontal(self, n: int) -> None:
@@ -64,6 +88,7 @@ class Space(ABC):
         Args:
             n (int): number to increment horizontal position of cells
         """
-        for c in chain.from_iterable(self.cells):
-            c.set_x(c.x + int(n))
+        for cell in self.cells:
+            cell.set_x(cell.x + int(n))
+        self.reset_cell_coordinates()
         return
diff --git a/examples/render_a_randomized_dungeon.py b/examples/render_a_randomized_dungeon.py
index aa2c5f3..240c264 100644
--- a/examples/render_a_randomized_dungeon.py
+++ b/examples/render_a_randomized_dungeon.py
@@ -1,12 +1,15 @@
 import os
 
 import matplotlib as mpl
+import numpy as np
 
-from donjuan import Dungeon, DungeonRoomRandomizer, Renderer, RoomRandomizer
+from donjuan import Dungeon, DungeonRandomizer, Renderer, RoomSizeRandomizer
+
+np.random.seed(123)
 
 # Create and randomize the dungeon
-room_randomizer = RoomRandomizer(max_size=4)
-randomizer = DungeonRoomRandomizer(max_num_rooms=10, room_randomizers=[room_randomizer])
+room_randomizer = RoomSizeRandomizer(max_size=8, min_size=6)
+randomizer = DungeonRandomizer(max_num_rooms=10, room_size_randomizer=room_randomizer)
 randomizer.seed(54321)
 dungeon = Dungeon(30, 30, randomizers=[randomizer])
 


Test patch:
diff --git a/tests/cell_test.py b/tests/cell_test.py
index 0f0e732..1f94794 100644
--- a/tests/cell_test.py
+++ b/tests/cell_test.py
@@ -8,6 +8,10 @@ class SquareCellTest(TestCase):
         c = SquareCell()
         assert c is not None
 
+    def test_space(self):
+        c = SquareCell()
+        assert c.space is None
+
     def test_filled(self):
         c = SquareCell()
         assert not c.filled
diff --git a/tests/dungeon_test.py b/tests/dungeon_test.py
index ff67da8..2f41802 100644
--- a/tests/dungeon_test.py
+++ b/tests/dungeon_test.py
@@ -55,7 +55,7 @@ class DungeonTest(TestCase):
     def test_emplace_room(self):
         grid = SquareGrid(3, 4)
         d = Dungeon(grid=grid)
-        cs = [[SquareCell(filled=False, coordinates=(1, 2))]]
+        cs = set([SquareCell(filled=False, coordinates=(1, 2))])
         room = Room(cells=cs)
         d.emplace_room(room)
         for i in range(d.n_rows):
@@ -67,7 +67,7 @@ class DungeonTest(TestCase):
 
     def test_emplace_rooms(self):
         grid = SquareGrid(3, 4)
-        cs = [[SquareCell(filled=False, coordinates=(1, 2))]]
+        cs = set([SquareCell(filled=False, coordinates=(1, 2))])
         room = Room(cells=cs)
         d = Dungeon(grid=grid, rooms={"0": room})
         d.emplace_rooms()
diff --git a/tests/room_randomizer_test.py b/tests/room_randomizer_test.py
index 58aa1ee..e5a6190 100644
--- a/tests/room_randomizer_test.py
+++ b/tests/room_randomizer_test.py
@@ -19,12 +19,13 @@ class RandomizerTestCase(TestCase):
         self.grid = SquareGrid(n_rows=4, n_cols=5)
         self.hexgrid = HexGrid(n_rows=4, n_cols=5)
         self.dungeon = Dungeon(grid=self.grid)
+        self.room = Room(cells=set([SquareCell()]))
 
 
 class AlphaNumRoomNameTest(RandomizerTestCase):
     def test_names(self):
         rr = AlphaNumRoomName()
-        room = Room()
+        room = self.room
         rr.randomize_room_name(room)
         assert room.name == "A0"
         rr.randomize_room_name(room)
@@ -47,13 +48,12 @@ class RoomPositionRandomizerTest(RandomizerTestCase):
         # Make a 1x1 room. try moving it around.
         rr = RoomPositionRandomizer()
         rr.seed(123)
-        cells = [[SquareCell()]]
-        room = Room(cells=cells)
-        assert room.cells[0][0].coordinates == (0, 0)
+        room = self.room
+        assert (0, 0) in room.cell_coordinates
         # Try moving it. 5% chance this fails if the seed is not set
         # Works with seed 123
         rr.randomize_room_position(room, self.dungeon)
-        assert room.cells[0][0].coordinates != (0, 0)
+        assert (0, 0) not in room.cell_coordinates
 
 
 class RoomSizeRandomizerTest(RandomizerTestCase):
@@ -64,17 +64,15 @@ class RoomSizeRandomizerTest(RandomizerTestCase):
         assert rng.max_size == 4
         assert issubclass(rng.cell_type, Cell)
 
-    def test_randomize_room(self):
+    def test_randomize_room_size(self):
         room = Room()
-        assert room.cells == [[]]
+        assert room.cells == set()
         rng = RoomSizeRandomizer()
         rng.randomize_room_size(room)
-        assert len(room.cells) >= rng.min_size
-        assert len(room.cells) <= rng.max_size
-        assert len(room.cells[0]) >= rng.min_size
-        assert len(room.cells[0]) <= rng.max_size
-        assert isinstance(room.cells[0][0], Cell)
-        assert not room.cells[0][0].filled
+        assert len(room.cells) >= rng.min_size ** 2
+        assert len(room.cells) <= rng.max_size ** 2
+        for cell in room.cells:
+            assert not cell.filled
 
 
 class DungeonRandomizerTest(RandomizerTestCase):
diff --git a/tests/room_test.py b/tests/room_test.py
index 2d3ef2e..b6e30cd 100644
--- a/tests/room_test.py
+++ b/tests/room_test.py
@@ -5,13 +5,18 @@ from donjuan import Room, SquareCell
 
 
 class RoomTest(TestCase):
+    def setUp(self):
+        super().setUp()
+        self.cells = set(
+            SquareCell(coordinates=(i, j)) for j in range(5) for i in range(4)
+        )
+
     def test_smoke(self):
         r = Room()
         assert r is not None
-        assert r.cells == [[]]
+        assert r.cells == set()
+        assert r.cell_coordinates == set()
         assert r.name == ""
-        assert r.n_rows == 0
-        assert r.n_cols == 0
 
     def test_name(self):
         r = Room(name="testroom")
@@ -24,44 +29,59 @@ class RoomTest(TestCase):
         r.set_name("catdog")
         assert r.name == "catdog"
 
-    def test_set_cells(self):
-        cs = [[SquareCell()]]
-        r = Room(cells=cs)
-        assert r.n_rows == 1
-        assert r.n_cols == 1
-        cs = [[SquareCell(coordinates=(i, j)) for j in range(3)] for i in range(2)]
-        r.set_cells(cs)
-        assert r.n_rows == 2
-        assert r.n_cols == 3
+    def test_insert_cell_list(self):
+        r = Room()
+        assert len(r.cells) == 0
+        r.insert_cell_list([SquareCell()])
+        assert len(r.cells) == 1
+        assert len(r.cell_coordinates) == 1
+        assert r.cell_coordinates == set(((0, 0),))
+
+    def test_set_space_to_cells(self):
+        r = Room(self.cells)
+        for cell in r.cells:
+            assert cell.space is r
 
     def test_shift_vertical(self):
-        cs = [[SquareCell(coordinates=(i, j)) for j in range(5)] for i in range(4)]
-        r = Room(cs)
+        r = Room(self.cells)
         r.shift_vertical(100)
-        for i in range(len(cs)):
-            for j in range(len(cs[0])):
-                assert r.cells[i][j].coordinates == (i + 100, j)
+        for cell in r.cells:
+            assert cell.coordinates[0] >= 100, cell.coordinates
+        for i in range(4):
+            for j in range(5):
+                assert (i + 100, j) in r.cell_coordinates
+
+    def test_shift_vertical_one_row(self):
+        r = Room(self.cells)
+        r.shift_vertical(1)
+        for i in range(4):
+            for j in range(5):
+                assert (i + 1, j) in r.cell_coordinates
 
     def test_shift_horizontal(self):
-        cs = [[SquareCell(coordinates=(i, j)) for j in range(5)] for i in range(4)]
-        r = Room(cs)
+        r = Room(self.cells)
         r.shift_horizontal(100)
-        for i in range(len(cs)):
-            for j in range(len(cs[0])):
-                assert r.cells[i][j].coordinates == (i, j + 100)
+        for cell in r.cells:
+            assert cell.coordinates[1] >= 100, cell.coordinates
+        for i in range(4):
+            for j in range(5):
+                assert (i, j + 100) in r.cell_coordinates
+
+    def test_shift_horizontal_one_col(self):
+        r = Room(self.cells)
+        r.shift_horizontal(1)
+        for i in range(4):
+            for j in range(5):
+                assert (i, j + 1) in r.cell_coordinates
 
     def test_overlaps(self):
-        cs = [[SquareCell(coordinates=(i, j)) for j in range(5)] for i in range(4)]
-        r1 = Room(cs)
-        r2 = Room(deepcopy(cs))
+        r1 = Room(self.cells)
+        r2 = Room(deepcopy(self.cells))
         assert r1.overlaps(r2)
 
     def test_no_overlap(self):
-        cs = [[SquareCell(coordinates=(i, j)) for j in range(5)] for i in range(4)]
-        r1 = Room(cs)
-        cs2 = deepcopy(cs)
-        for i in range(len(cs)):
-            for j in range(len(cs[0])):
-                cs2[i][j].set_coordinates(100 + i, j)
+        r1 = Room(self.cells)
+        cs2 = deepcopy(self.cells)
         r2 = Room(cs2)
+        r2.shift_vertical(100)
         assert not r1.overlaps(r2)