| """ Grid splitting model with connection database back references. | |
| The Grid object provides methods to manipulate a 2D grid of Tile objects, that | |
| contain zero or more Site objects. Site objects are considered immutable. | |
| To construct the Grid object, the initial grid and an empty_tile_type_pkey must | |
| be provided. The initial grid should be provided as a map of 2 element int | |
| tuples to Tile objects. Tile objects should already contain their initial | |
| sites prior to construction of the Grid object. | |
| """ | |
| from enum import Enum | |
| from collections import namedtuple | |
| class Direction(Enum): | |
| """ Grid directions. """ | |
| NORTH = 1 | |
| SOUTH = 2 | |
| EAST = 3 | |
| WEST = 4 | |
| NORTH = Direction.NORTH | |
| SOUTH = Direction.SOUTH | |
| EAST = Direction.EAST | |
| WEST = Direction.WEST | |
| OPPOSITE_DIRECTIONS = { | |
| NORTH: SOUTH, | |
| SOUTH: NORTH, | |
| EAST: WEST, | |
| WEST: EAST, | |
| } | |
| # Zipper direction when splitting in a direction | |
| SPLIT_NEXT_DIRECTIONS = { | |
| NORTH: EAST, | |
| SOUTH: EAST, | |
| EAST: SOUTH, | |
| WEST: SOUTH, | |
| } | |
| def opposite_direction(direction): | |
| """ Return opposite direction of given direction. | |
| >>> opposite_direction(NORTH) | |
| <Direction.SOUTH: 2> | |
| >>> opposite_direction(SOUTH) | |
| <Direction.NORTH: 1> | |
| >>> opposite_direction(EAST) | |
| <Direction.WEST: 4> | |
| >>> opposite_direction(WEST) | |
| <Direction.EAST: 3> | |
| """ | |
| return OPPOSITE_DIRECTIONS[direction] | |
| # Right handed coordinate system, N/S in y, E/W in x, E is x-positive, | |
| # S is y-positive. | |
| DIRECTION_OFFSET = { | |
| NORTH: [0, -1], | |
| SOUTH: [0, 1], | |
| EAST: [1, 0], | |
| WEST: [-1, 0], | |
| } | |
| def coordinate_in_direction(coord, direction): | |
| """ Given a coordinate, returns a new coordinate 1 step in direction. | |
| Coordinate system is right handed, N/S in y, E/W in x. E is x-positive. | |
| S is y-positive. | |
| Parameters | |
| ---------- | |
| coord : Tuple of 2 ints | |
| Starting coordinate | |
| direction : Direction | |
| Direction to add unit vector. | |
| Returns | |
| ------- | |
| Tuple of 2 ints | |
| Coordinate 1 unit step in specified direction. Will return none if | |
| x or y coordinate is negative. | |
| Examples | |
| -------- | |
| >>> coordinate_in_direction((0, 0), SOUTH) | |
| (0, 1) | |
| >>> coordinate_in_direction((0, 0), EAST) | |
| (1, 0) | |
| >>> coordinate_in_direction((1, 1), SOUTH) | |
| (1, 2) | |
| >>> coordinate_in_direction((1, 1), NORTH) | |
| (1, 0) | |
| >>> coordinate_in_direction((1, 1), EAST) | |
| (2, 1) | |
| >>> coordinate_in_direction((1, 1), WEST) | |
| (0, 1) | |
| # Returns None for negative coordinates. | |
| >>> coordinate_in_direction((0, 0), NORTH) | |
| >>> coordinate_in_direction((1, 0), NORTH) | |
| >>> coordinate_in_direction((0, 0), WEST) | |
| >>> coordinate_in_direction((0, 1), WEST) | |
| """ | |
| x, y = coord | |
| dx, dy = DIRECTION_OFFSET[direction] | |
| x += dx | |
| y += dy | |
| if x < 0 or y < 0: | |
| return None | |
| else: | |
| return x, y | |
| class Site(namedtuple('Site', ('name', 'phy_tile_pkey', 'tile_type_pkey', | |
| 'site_type_pkey', 'site_pkey', 'x', 'y'))): | |
| """ Object to hold back reference information for a site. """ | |
| pass | |
| class Tile(object): | |
| """ Tile instance within the grid. | |
| Attributes | |
| ---------- | |
| root_phy_tile_pkeys : list of ints | |
| The list of root_phy_tile_pkey's. | |
| By default a tile typically has one root phy_tile_pkey, which is the | |
| phy_tile this initial represents. | |
| If two Tile objects are merged, the root_phy_tile_pkeys are also merged. | |
| If a Tile object is split, only one of the split tiles will take all | |
| of the root_phy_tile_pkeys, and the other tiles will have no | |
| root_phy_tile_pkeys. | |
| Invariant: Each phy_tile_pkey will appear in 1 and only 1 Tile | |
| object's root_phy_tile_pkeys list. | |
| Because of the invariant, the root_phy_tile_pkeys list can be used as | |
| a default assignment of children of the relevant phy_tile_pkey items | |
| (e.g. wires, pips, sites, etc). | |
| phy_tile_pkeys : list of ints | |
| The list of phy_tile_pkey's. This is the list of all phy_tile_pkey's | |
| that are involved in this tile via either a tile merge or split. | |
| By default a tile typically has one phy_tile_pkey, which is the | |
| phy_tile this initial represents. | |
| If two Tile objects are split, all output tiles will get a copy of the | |
| original phy_tile_pkeys list. This attribute can be used to determine | |
| what phy_tile_pkeys were used to make this tile. | |
| sites : list of Site objects | |
| This is the list of Site's contained within this tile. This should | |
| be initial set to the Site objects contained within the original | |
| phy_tile. | |
| Invariant: Each Site object will be contained within exactly one Tile | |
| object. | |
| split_sites : boolean | |
| True if this tile was split. | |
| Invariant: Each split tile will contain exactly one Site object. | |
| Invariant: Two tiles that were split cannot be merged, otherwise the | |
| resulting Tile will have two Sites, potentially from different | |
| phy_tile_pkey, which cannot be presented using FASm prefixes. | |
| neighboors : Map of Direction to Tile object | |
| Linked list pointers to neighboors tiles. | |
| Invariant: Underlying linked link should be rectangular after an | |
| operation on the grid. An single operation on the Tile will typically | |
| invalidate the overall grid, it is up to the Grid object to enforce | |
| the rectangular constraint. | |
| Invariant: Underlying linked link must not be circular. | |
| """ | |
| def __init__( | |
| self, root_phy_tile_pkeys, phy_tile_pkeys, tile_type_pkey, sites | |
| ): | |
| self.root_phy_tile_pkeys = root_phy_tile_pkeys | |
| self.phy_tile_pkeys = phy_tile_pkeys | |
| self.tile_type_pkey = tile_type_pkey | |
| self.sites = sites | |
| self.split_sites = False | |
| self.neighboors = {} | |
| def link_neighboor_in_direction(self, other_tile, direction_to_other_tile): | |
| """ Connect this tile to another tile in a specific direction. | |
| It is legal to call this method on an existing connection, but it is | |
| not legal to call this method to replace an existing connection. | |
| Parameters | |
| ---------- | |
| other_tile : Tile object | |
| Other Tile object to connect in specified direction. | |
| direction_to_other_tile : Direction | |
| Direction to connect other tile. | |
| """ | |
| if direction_to_other_tile in self.neighboors: | |
| assert id( | |
| self.neighboors[direction_to_other_tile] | |
| ) == id(other_tile), (self.neighboors, direction_to_other_tile) | |
| self.neighboors[direction_to_other_tile] = other_tile | |
| direction_to_this_tile = opposite_direction(direction_to_other_tile) | |
| if direction_to_this_tile in other_tile.neighboors: | |
| assert id(other_tile.neighboors[direction_to_this_tile] | |
| ) == id(self) | |
| other_tile.neighboors[direction_to_this_tile] = self | |
| def insert_in_direction(self, other_tile, direction_to_other_tile): | |
| """ Insert a tile in a specified direction. | |
| Parameters | |
| ---------- | |
| other_tile : Tile object | |
| Other Tile object to insert in specified direction. | |
| direction_to_other_tile : Direction | |
| Direction to insert other tile. | |
| """ | |
| old_neighboor = self.neighboors.get(direction_to_other_tile, None) | |
| direction_to_this_tile = opposite_direction(direction_to_other_tile) | |
| self.neighboors[direction_to_other_tile] = other_tile | |
| other_tile.neighboors[direction_to_this_tile] = self | |
| if old_neighboor is not None: | |
| other_tile.neighboors[direction_to_other_tile] = old_neighboor | |
| old_neighboor.neighboors[direction_to_this_tile] = other_tile | |
| def walk_in_direction(self, direction): | |
| """ Walk in specified direction from this Tile node. | |
| Parameters | |
| ---------- | |
| direction : Direction | |
| Direction to walk in. | |
| Yields | |
| ------ | |
| tile : Tile | |
| Tile in specified direction. First Tile object will always be the | |
| tile whose walk_in_direction was invoked. When the end of the grid | |
| is encounted, no more tiles will be yielded. | |
| """ | |
| node = self | |
| while True: | |
| yield node | |
| if direction in node.neighboors: | |
| node = node.neighboors[direction] | |
| else: | |
| break | |
| def check_grid_loc(grid_loc_map): | |
| """ Verifies input grid makes sense. | |
| Internal grid consistency is defined as: | |
| - Has an origin location @ (0, 0) | |
| - Is rectangular | |
| - Has no gaps. | |
| Parameters | |
| ---------- | |
| grid_loc_map : Dict of 2 int tuple to Tile objects | |
| Grid being checked. | |
| Raises | |
| ------ | |
| AssertionError | |
| If provided grid does not conform to assumptions about grid. | |
| """ | |
| xs, ys = zip(*grid_loc_map.keys()) | |
| max_x = max(xs) | |
| max_y = max(ys) | |
| for x in range(max_x + 1): | |
| for y in range(max_y + 1): | |
| assert (x, y) in grid_loc_map, (x, y) | |
| def build_mesh(current, visited, loc, grid_loc_map): | |
| """ Stitch grid_loc_map into a double-linked list 2D mesh. | |
| Modifies Tile object neighboors attributes to form a doubly linked list | |
| 2D mesh. | |
| It is strongly recommended that grid_loc_map be passed to check_grid_loc | |
| prior to calling build_mesh to verify grid invariants. | |
| Parameters | |
| ---------- | |
| current : Tile object | |
| visited : set of python object id's | |
| Should be empty on root invocation. | |
| loc : Location of current Tile object argument | |
| grid_loc_map : Dict of 2 int tuple to Tile objects | |
| Grid being converted to linked list form. | |
| """ | |
| for direction in (SOUTH, EAST): | |
| new_loc = coordinate_in_direction(loc, direction) | |
| if new_loc in grid_loc_map: | |
| current.link_neighboor_in_direction( | |
| grid_loc_map[new_loc], direction | |
| ) | |
| if id(grid_loc_map[new_loc]) not in visited: | |
| visited.add(id(grid_loc_map[new_loc])) | |
| build_mesh( | |
| grid_loc_map[new_loc], visited, new_loc, grid_loc_map | |
| ) | |
| class Grid(object): | |
| """ Object for manipulating a 2D grid of Tile objects. | |
| Parameters | |
| ---------- | |
| grid_loc_map : Dict of 2 int tuple to Tile objects | |
| Initial grid of Tile objects. | |
| empty_tile_type_pkey : int | |
| tile_type_pkey to use when creating new empty tiles during tile splits. | |
| """ | |
| def __init__(self, grid_loc_map, empty_tile_type_pkey): | |
| # Make sure initial grid is sane | |
| check_grid_loc(grid_loc_map) | |
| # Keep root object of grid. | |
| self.origin = grid_loc_map[(0, 0)] | |
| # Convert grid to doubly-linked list. | |
| build_mesh(self.origin, set(), (0, 0), grid_loc_map) | |
| # Keep list of all Tile objects for convience. | |
| self.items = grid_loc_map.values() | |
| self.empty_tile_type_pkey = empty_tile_type_pkey | |
| def column(self, x): | |
| """ Return Tile object at top of column. | |
| Parameters | |
| ---------- | |
| x : int | |
| 0 based column to retrive. | |
| Returns | |
| ------- | |
| top_of_column : Tile | |
| Tile object at top of column | |
| """ | |
| top_of_column = self.origin | |
| for _ in range(x): | |
| top_of_column = top_of_column.neighboors[EAST] | |
| return top_of_column | |
| def row(self, y): | |
| """ Return Tile object at right of row. | |
| Parameters | |
| ---------- | |
| y : int | |
| 0 based row to retrive. | |
| Returns | |
| ------- | |
| right_of_row : Tile | |
| Tile object at right of row | |
| """ | |
| right_of_row = self.origin | |
| for _ in range(y): | |
| right_of_row = right_of_row.neighboors[SOUTH] | |
| def split_tile(self, tile, tile_type_pkeys, split_direction, split_map): | |
| """ Split tile in specified direction. | |
| This method requires that the tiles required to perform the split (e.g. | |
| len(tile_type_pkeys)-1 tiles in split_direction from tile) have | |
| tile_type_pkey == empty_tile_type_pkey, e.g. they are empty tiles. | |
| If empty tiles must be inserted into the grid to accomidate the split, | |
| this must be done prior to calling this method. | |
| Parameters | |
| ---------- | |
| tile : Tile object | |
| Tile being split | |
| tile_type_pkeys : List of int | |
| List of new tile_type_pkeys to be used after the tile split. | |
| The tile being split will become tile_type_pkeys[0], the next tile | |
| in split_direction will become tile_type_pkeys[1], etc. | |
| split_direction : Direction | |
| Which direction from tile should the split occur. | |
| split_map : Dict of (int, int) to int | |
| Mapping of site location (x, y) to tile_type_pkey indicies. | |
| This enables control over which sites go to which tiles based on | |
| their coordinate. | |
| min(split_map.values()) >= 0 | |
| max(split_map.values()) < len(tile_type_pkeys) | |
| """ | |
| sites = tile.sites | |
| tile.tile_type_pkey = self.empty_tile_type_pkey | |
| phy_tile_pkeys = set(tile.phy_tile_pkeys) | |
| new_tiles = [] | |
| for idx, tile in enumerate(tile.walk_in_direction(split_direction)): | |
| assert tile.tile_type_pkey == self.empty_tile_type_pkey, ( | |
| tile.tile_type_pkey | |
| ) | |
| tile.phy_tile_pkeys = [] | |
| new_tiles.append(tile) | |
| if idx + 1 >= len(tile_type_pkeys): | |
| break | |
| for tile, new_tile_type_pkey in zip(new_tiles, tile_type_pkeys): | |
| assert tile.tile_type_pkey == self.empty_tile_type_pkey | |
| tile.tile_type_pkey = new_tile_type_pkey | |
| tile.phy_tile_pkeys = list( | |
| set(tile.phy_tile_pkeys) | phy_tile_pkeys | |
| ) | |
| tile.sites = [] | |
| tile.split_sites = True | |
| for site in sites: | |
| site_idx = split_map[site.x, site.y] | |
| assert site_idx < len(tile_type_pkeys), ( | |
| site, site_idx, tile_type_pkeys | |
| ) | |
| new_tiles[site_idx].sites.append(site) | |
| def insert_empty(self, top, insert_in_direction): | |
| """ Insert empty row/colum. | |
| Insert a row/column of empty tiles from the tiles in the row/column specified | |
| by top_of_row/column tile. The new empty tiles will have tile_type_pkey | |
| set to empty_tile_type_pkey, and have phy_tile_pkeys of the tile they | |
| were inserted from. | |
| Parameters | |
| ---------- | |
| top_of_row/column : Tile object | |
| Tile at top of row/column adjcent to where new row/column should be | |
| inserted. | |
| insert_in_direction : Direction | |
| Direction to insert empty tiles, from perspective of the row/column | |
| specified by top_of_row/column. | |
| """ | |
| # Verify that insert direction is not the same as zipper direction. | |
| next_dir = SPLIT_NEXT_DIRECTIONS[insert_in_direction] | |
| # Verify that top is in fact the top of the zipper | |
| assert OPPOSITE_DIRECTIONS[next_dir] not in top.neighboors | |
| empty_tiles = [] | |
| for tile in top.walk_in_direction(next_dir): | |
| empty_tile = Tile( | |
| root_phy_tile_pkeys=[], | |
| phy_tile_pkeys=list(tile.phy_tile_pkeys), | |
| tile_type_pkey=self.empty_tile_type_pkey, | |
| sites=[] | |
| ) | |
| empty_tiles.append(empty_tile) | |
| tile.insert_in_direction(empty_tile, insert_in_direction) | |
| for a, b in zip(empty_tiles, empty_tiles[1:]): | |
| a.link_neighboor_in_direction(b, next_dir) | |
| self.check_grid() | |
| def split_in_dir( | |
| self, | |
| top, | |
| tile_type_pkey, | |
| tile_type_pkeys, | |
| split_direction, | |
| split_map, | |
| ): | |
| """ Split row/column of tiles. | |
| Splits specified tile types into new row/column by first inserting any | |
| required empty row/column in the split direction, and then performing | |
| the split. | |
| Parameters | |
| ---------- | |
| top_of_row/column : Tile object | |
| Tile at top of row/column where split should be performed. | |
| tile_type_pkey : Tile type to split. | |
| tile_type_pkeys : Refer to split_tile documentation. | |
| split_direction : Direction | |
| Direction to insert perform split. New row/column will be inserted | |
| in that direction to accomidate the tile split. | |
| split_map : Dict of (int, int) to int | |
| Mapping of site location (x, y) to tile_type_pkey indicies. | |
| This enables control over which sites go to which tiles based on | |
| their coordinate. | |
| """ | |
| next_dir = SPLIT_NEXT_DIRECTIONS[split_direction] | |
| # Find how many empty tiles are required to support the split | |
| num_to_insert = 0 | |
| for tile in top.walk_in_direction(next_dir): | |
| if tile.tile_type_pkey != tile_type_pkey: | |
| continue | |
| for idx, tile_in_split in enumerate( | |
| tile.walk_in_direction(split_direction)): | |
| if idx == 0: | |
| continue | |
| else: | |
| if tile_in_split.tile_type_pkey != self.empty_tile_type_pkey: | |
| num_to_insert = max(num_to_insert, idx) | |
| if idx + 1 >= len(tile_type_pkeys): | |
| break | |
| for _ in range(num_to_insert): | |
| self.insert_empty(top, split_direction) | |
| for tile in top.walk_in_direction(next_dir): | |
| if tile.tile_type_pkey != tile_type_pkey: | |
| continue | |
| self.split_tile(tile, tile_type_pkeys, split_direction, split_map) | |
| def split_tile_type( | |
| self, tile_type_pkey, tile_type_pkeys, split_direction, split_map | |
| ): | |
| """ Split a specified tile type within grid. | |
| Splits specified tile types by finding each column that contains the | |
| relevant tile type, and spliting each column. | |
| Parameters | |
| ---------- | |
| tile_type_pkey : Tile type to split. | |
| tile_type_pkeys : Refer to split_tile documentation. | |
| split_direction : Direction | |
| Direction to insert perform split. | |
| split_map : Dict of (int, int) to int | |
| Mapping of site location (x, y) to tile_type_pkey indicies. | |
| This enables control over which sites go to which tiles based on | |
| their coordinate. | |
| """ | |
| tiles_seen = set() | |
| tiles = [] | |
| tops_to_split = [] | |
| next_dir = SPLIT_NEXT_DIRECTIONS[split_direction] | |
| for tile in self.items: | |
| if id(tile) in tiles_seen: | |
| continue | |
| if tile.tile_type_pkey == tile_type_pkey: | |
| # Found a row/column that needs to be split, walk to the bottom of | |
| # the row/column, then back to the top. | |
| for tile in tile.walk_in_direction(next_dir): | |
| pass | |
| for tile in tile.walk_in_direction( | |
| OPPOSITE_DIRECTIONS[next_dir]): | |
| if id(tile) not in tiles_seen: | |
| tiles_seen.add(id(tile)) | |
| if tile.tile_type_pkey == tile_type_pkey: | |
| tiles.append(tile) | |
| tops_to_split.append(tile) | |
| for top in tops_to_split: | |
| self.split_in_dir( | |
| top, tile_type_pkey, tile_type_pkeys, split_direction, | |
| split_map | |
| ) | |
| def merge_in_dir(self, tile, merge_direction): | |
| """ Merge tile in specified direction. | |
| Merging a tile causes the connects of that tile to be merged into | |
| the tile in the merge direction. The tile that was merged will become | |
| empty. | |
| The original tile root_phy_tile_pkeys and phy_tile_pkeys will appear | |
| first. | |
| Parameters | |
| ---------- | |
| tile : Tile | |
| Tile to merge | |
| merge_direction : Direction | |
| Direction to merge tiles. | |
| """ | |
| assert merge_direction in tile.neighboors, (tile, merge_direction) | |
| merge_into = tile.neighboors[merge_direction] | |
| merge_into.root_phy_tile_pkeys.extend(tile.root_phy_tile_pkeys) | |
| merge_into.phy_tile_pkeys.extend(tile.phy_tile_pkeys) | |
| merge_into.sites.extend(tile.sites) | |
| tile.sites = list() | |
| tile.tile_type_pkey = self.empty_tile_type_pkey | |
| tile.root_phy_tile_pkeys = list() | |
| tile.phy_tile_pkeys = list() | |
| def merge_tile_type(self, tile_type_pkey, merge_direction): | |
| """ Merge tile types in specified direction. | |
| Parameters | |
| ---------- | |
| tile_type_pkey : Tile type to split. | |
| merge_direction : Direction | |
| Direction to merge tiles. | |
| """ | |
| for tile in self.items: | |
| if tile.tile_type_pkey == tile_type_pkey: | |
| self.merge_in_dir(tile, merge_direction) | |
| def output_grid(self): | |
| """ Convert grid back to coordinate lookup form. | |
| Returns | |
| ------- | |
| grid_loc_map : Dict of 2 int tuple to Tile objects | |
| Output grid of Tile objects. | |
| """ | |
| grid_loc_map = {} | |
| for x, tile in enumerate(self.origin.walk_in_direction(EAST)): | |
| for y, tile in enumerate(tile.walk_in_direction(SOUTH)): | |
| grid_loc_map[(x, y)] = tile | |
| check_grid_loc(grid_loc_map) | |
| return grid_loc_map | |
| def check_grid(self): | |
| """ Verifies that grid linked list model still represents valid grid. | |
| """ | |
| self.output_grid() |