| """ 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() |
