text: #!/usr/bin/python
  ########################################################################################################################
  #
  # Copyright (c) 2014, Regents of the University of California
  # All rights reserved.
  #
  # Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
  # following conditions are met:
  #
  # 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following
  #   disclaimer.
  # 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
  #    following disclaimer in the documentation and/or other materials provided with the distribution.
  #
  # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  # INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  # DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  # SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  # WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  #
  ########################################################################################################################
  
  """
  The GridObject module and class implements a object that contains grid information for placement and route. It also
  provides useful functions for coordinate conversion between physical and abstract grids.
  """
  
  __author__ = "Jaeduk Han"
  __maintainer__ = "Jaeduk Han"
  __email__ = "jdhan@eecs.berkeley.edu"
  __status__ = "Prototype"
  
  import numpy as np
  
  class GridObject():
      """Layout abstract grid class"""
      type="native"
      """str: type of grid. can be 'native', 'route', 'placement'"""
      name=None
      """str: name of grid"""
      libname=None
      """str: library name of grid"""
      xy = np.array([0, 0]) # Coordinate
      """np.array([float, float]): size of grid"""
      xgrid=np.array([])
      """np.array([float, float, ...]): x coordinates of grid"""
      ygrid=np.array([])
      """np.array([float, float, ...]): y coordinates of grid"""
      max_resolution=10
      """int: maximum resolution to handle floating point numbers"""
  
      @property
      def height(self):
          """float: height of grid"""
          return abs(self.xy[0][1]-self.xy[1][1])
  
      @property
      def width(self):
          """float: width of grid"""
          return abs(self.xy[0][0]-self.xy[1][0])
  
      def __init__(self, name, libname, xy, _xgrid=np.array([0]), _ygrid=np.array([0])):
          """
          Constructor
          """
          self.name = name
          self.libname=libname
          self.xy=xy
          self.xgrid=_xgrid
          self.ygrid=_ygrid
  
      def display(self):
          """
          Display grid information
          """
          print("  " + self.name + " width:" + str(np.around(self.width, decimals=self.max_resolution))
                                 + " height:" + str(np.around(self.height, decimals=self.max_resolution)))
  
      def export_dict(self):
          """
          Export object information in dict format
  
          Returns
          -------
          dict
              grid information in dict format
          """
          export_dict={'type':self.type,
                       'xy0':np.around(self.xy[0,:], decimals=self.max_resolution).tolist(),
                       'xy1':np.around(self.xy[1,:], decimals=self.max_resolution).tolist()}
          if not self.xgrid.tolist()==[]:
              export_dict['xgrid']=np.around(self.xgrid, decimals=self.max_resolution).tolist()
          if not self.ygrid.tolist()==[]:
              export_dict['ygrid']=np.around(self.ygrid, decimals=self.max_resolution).tolist()
          return export_dict
  
      def _add_grid(self, grid, v):
          """
          add a grid coordinate
  
          Parameters
          ----------
          grid : np.array
              grid array
          v : float
              value
  
          Returns
          -------
          np.array
              updated grid array
          """
          grid.append(v)
          grid.sort()
          return grid
  
      def add_xgrid(self, x):
          """
          add a coordinate value to grid in x direction
  
          Parameters
          ----------
          x : float
              value to be added
          """
          self.xgrid=self._add_grid(self.xgrid, x)
  
      def add_ygrid(self, y):
          """
          add a coordinate value to grid in y direction
  
          Parameters
          ----------
          y : float
              value to be added
          """
          self.ygrid=self._add_grid(self.ygrid, y)
  
      def get_xgrid(self):
          """use laygo.GridObject.GridObject.xgrid instead"""
          return self.xgrid
  
      def get_ygrid(self):
          """use laygo.GridObject.GridObject.ygrid instead"""
          return self.ygrid
  
      #abstract to physical conversion functions
      def _get_absgrid_coord(self, v, grid, size, method='ceil'):
          """
          Convert physical value to abstract value on grid. Since physical values are continuous and grid values are
          discrete, boundary conditions are need to be defined for the conversion.
          Default (and only supported in the current version) converting method is ceil, which is described as follows:
          #   physical grid: 0----grid0----grid1----grid2----...----gridN---size
          # abstracted grid: 0  0   0    1   1    2   2           N   N   N+1
          The ceiling method works well with stacked grids. For example, in the example, phyical values ranging from
          (larger than) GridN to (equal to) gridN+1 (grid0 of the second stack) will be converted to N+1.
  
          Parameters
          ----------
          v : float
              grid value
          grid : np.array
              grid array
          size : float
              grid size
          method : str, optional
              converting method
  
          Returns
          -------
          int
              abstract grid value
          """
          quo=np.floor(np.divide(v, size))
          mod=v-quo*size #mod=np.mod(v, size) not working well
          mod_ongrid=np.searchsorted(grid+1e-10, mod) #add 1e-10 to handle floating point precision errors
          #print('physical:' + str(v.tolist()) + ' size:'+ str(size) +
          #      ' quo:' + str(quo.tolist()) + ' mod:' + str(mod) +
          #      ' abs:' + str(np.add(np.multiply(quo,grid.shape[0]), mod_ongrid).tolist()))
          return np.add(np.multiply(quo,grid.shape[0]), mod_ongrid)
  
      def get_absgrid_coord_x(self, x): return self.get_absgrid_x(x)
      def get_absgrid_x(self, x):
          """
          Convert a physical x coordinate to a corresponding value in abstract grid
  
          Parameters
          ----------
          x : float
              value
  
          Returns
          -------
          int
              converted value
          """
          return self._get_absgrid_coord(x, self.xgrid, self.width).astype(int)
  
      def get_absgrid_coord_y(self, y): return self.get_absgrid_y(y)
      def get_absgrid_y(self, y):
          """
          Convert a physical y coordinate to a corresponding value in abstract grid
  
          Parameters
          ----------
          y : float
              value
  
          Returns
          -------
          int
              converted value
          """
          return self._get_absgrid_coord(y, self.ygrid, self.height).astype(int)
  
      def get_absgrid_coord_xy(self, xy): return self.get_absgrid_xy(xy)
      def get_absgrid_xy(self, xy):
          """
          Convert a physical xy coordinate to a corresponding vector in abstract grid
  
          Parameters
          ----------
          xy : np.array([float, float])
  
          Returns
          -------
          np.array([int, int])
          """
          _xy=np.vstack((self.get_absgrid_x(xy.T[0]), self.get_absgrid_y(xy.T[1]))).T
          if _xy.shape[0]==1: return _xy[0]
          else: return _xy
  
      def get_absgrid_coord_region(self, xy0, xy1): return self.get_absgrid_region(xy0, xy1)
      def get_absgrid_region(self, xy0, xy1):
          """
          Convert a physical regin to a corresponding region in abstract grid
  
          Parameters
          ----------
          xy0 : np.array([float, float])
              first coordinate
          xy1 : np.array([float, float])
              second coordinate
  
          Returns
          -------
          np.array([[int, int], [int, int]])
              converted coordinate
          """
          _xy0 = np.vstack((self.get_absgrid_coord_x(xy0.T[0]), self.get_absgrid_coord_y(xy0.T[1]))).T
          _xy1 = np.vstack((self.get_absgrid_coord_x(xy1.T[0]), self.get_absgrid_coord_y(xy1.T[1]))).T
          if _xy0.shape[0] == 1: _xy0 = _xy0[0]
          if _xy1.shape[0] == 1: _xy1 = _xy1[0]
          #upper right boundary adjust
          #check by re-converting to physical grid and see if the points are within original [xy0, xy1]
          #xy0_check = self.get_phygrid_coord_xy(_xy0)[0]
          #xy1_check = self.get_phygrid_coord_xy(_xy1)[0]
          xy0_check = self.get_phygrid_xy(_xy0)
          xy1_check = self.get_phygrid_xy(_xy1)
          xy0_check = np.around(xy0_check, decimals=self.max_resolution)
          xy1_check = np.around(xy1_check, decimals=self.max_resolution)
          xy0 = np.around(xy0, decimals=self.max_resolution)
          xy1 = np.around(xy1, decimals=self.max_resolution)
          #print("phy:" + str(xy0) + " " + str(xy1) + " abs:" + str(_xy0) + " " + str(_xy1) + " chk:" + str(xy0_check) + " " + str(xy1_check))
          if xy0_check[0] > xy0[0] and xy0_check[0] > xy1[0]: _xy0[0] -= 1
          if xy1_check[0] > xy0[0] and xy1_check[0] > xy1[0]: _xy1[0] -= 1
          if xy0_check[1] > xy0[1] and xy0_check[1] > xy1[1]: _xy0[1] -= 1
          if xy1_check[1] > xy0[1] and xy1_check[1] > xy1[1]: _xy1[1] -= 1
          #if _xy1[1]==7:
          #    print("phy:"+str(xy0)+" "+str(xy1)+" abs:"+str(_xy0)+" "+str(_xy1)+" chk:"+str(xy0_check)+" "+str(xy1_check))
          #print(xy1)
  
          return(np.vstack((_xy0, _xy1)))
  
      # physical to abstract conversion functions
      def _get_phygrid_coord(self, v, grid, size):
          """
          Internal function for abstract to physical coordinate conversions
  
          Parameters
          ----------
          v : int
              value in abstract coordinate
          grid : np.array
              grid array
          size : float
              grid size
  
          Returns
          -------
          float
              value in physical coordinate
          """
          quo = np.floor(np.divide(v, grid.shape[0]))
          mod = np.mod(v, grid.shape[0])  # mod = v - quo * grid.shape[0]
          return np.add(np.multiply(quo, size), np.take(grid, mod))
  
      def get_phygrid_coord_x(self, x): return self.get_phygrid_x(x)
      def get_phygrid_x(self, x):
          """
          Get the physical value of a abstract x coordinate
  
          Parameters
          ----------
          x : int
              abstract coordinate value
  
          Returns
          -------
          float
              physical coordinate value
          """
          return self._get_phygrid_coord(x, self.xgrid, self.width)
  
      def get_phygrid_coord_y(self, y): return self.get_phygrid_y(y)
      def get_phygrid_y(self, y):
          """
          Get the physical value of a abstract y coordinate
  
          Parameters
          ----------
          y : int
              abstract coordinate value
  
          Returns
          -------
          float
              physical coordinate value
          """
          return self._get_phygrid_coord(y, self.ygrid, self.height)
  
      def get_phygrid_coord_xy(self, xy): return self.get_phygrid_xy(xy)
      def get_phygrid_xy(self, xy):
          """
          Get the physical value of a abstract vector
  
          Parameters
          ----------
          xy : np.array([int, int])
              abstract coordinate vector
  
          Returns
          -------
          np.array([float, float])
              physical coordinate vector
          """
          if xy.ndim==1: #single coordinate
              return np.vstack((self.get_phygrid_coord_x(xy.T[0]), self.get_phygrid_coord_y(xy.T[1]))).T[0]
          else:
              return np.vstack((self.get_phygrid_coord_x(xy.T[0]), self.get_phygrid_coord_y(xy.T[1]))).T
  
  
  class PlacementGrid(GridObject):
      """
      Placement grid class
      """
      type = 'placement'
  
  
  class RouteGrid(GridObject):
      """
      Routing grid class
      """
      type = 'route'
      """str: type of grid. can be 'native', 'route', 'placement'"""
      xwidth = np.array([])
      """np.array: width of xgrid"""
      ywidth = np.array([])
      """np.array: width of ygrid"""
      viamap = dict()
      """dict: via map information"""
      xlayer = None
      """list: layer of xgrid"""
      ylayer = None
      """list: layer of ygrid"""
  
      def __init__(self, name, libname, xy, xgrid, ygrid, xwidth, ywidth, xlayer=None, ylayer=None, viamap=None):
          """
          Constructor
          """
          self.name = name
          self.libname = libname
          self.xy = xy
          self.xgrid = xgrid
          self.ygrid = ygrid
          self.xwidth = xwidth
          self.ywidth = ywidth
          self.xlayer = xlayer
          self.ylayer = ylayer
          self.viamap = viamap
  
      def _get_route_width(self, v, _width):
          """
          Get metal width
  
          Parameters
          ----------
          v : int
              value
          _width : np.array
              width vector
  
          Returns
          -------
          float
              route width
          """
          #quo=np.floor(np.divide(v, self._width.shape[0]))
          mod=np.mod(v, _width.shape[0])
          #if not isinstance(mod, int):
          #    print(v, _width, mod)
          return _width[int(np.round(mod))]
  
      def _get_route_layer(self, v, _layer):
          """
          Get metal layer
  
          Parameters
          ----------
          v : int
              index value
          _layer : list
              layer list
  
          Returns
          -------
          [str, str]
              route layer
          """
          mod=np.mod(v, len(_layer))
          return _layer[mod]
  
      #def get_xwidth(self): return self.xwidth
      #def get_ywidth(self): return self.ywidth
      #def get_viamap(self): return self.viamap
  
      def get_route_width_xy(self, xy):
          """
          Get metal width vector
  
          Parameters
          ----------
          xy : np.array([int, int])
              coordinate
  
          Returns
          -------
          np.array([float, float])
              route width vector ([xgrid, ygrid])
          """
          return np.array([self._get_route_width(xy[0], self.xwidth),
                           self._get_route_width(xy[1], self.ywidth)])
  
      def get_route_xlayer_xy(self, xy):
          """
          Get route layer in xgrid direction (vertical)
  
          Parameters
          ----------
          xy : np.array([int, int])
              coordinate
  
          Returns
          -------
          [str, str]
              route layer information
          """
          return self._get_route_layer(xy[0], self.xlayer)
  
      def get_route_ylayer_xy(self, xy):
          """
          Get route layer in ygrid direction (horizontal)
  
          Parameters
          ----------
          xy : np.array([int, int])
              coordinate
  
          Returns
          -------
          [str, str]
              route layer information
          """
          return self._get_route_layer(xy[1], self.ylayer)
  
      def get_vianame(self, xy):
          """
          Get the name of via on xy
  
          Parameters
          ----------
          xy : np.array([int, int])
              coordinate
  
          Returns
          -------
          str
              cellname of via
          """
          mod = np.array([np.mod(xy[0], self.xgrid.shape[0]), np.mod(xy[1], self.ygrid.shape[0])])
          for vianame, viacoord in self.viamap.items():
              if viacoord.ndim==1:
                  if np.array_equal(mod, viacoord): return vianame
              else:
                  for v in viacoord:
                      if np.array_equal(mod,v):
                          return vianame
  
      def display(self):
          """
          Display RouteGrid information
          """
          display_str="  " + self.name + " width:" + str(np.around(self.width, decimals=self.max_resolution))\
                      + " height:" + str(np.around(self.height, decimals=self.max_resolution))\
                      + " xgrid:" + str(np.around(self.xgrid, decimals=self.max_resolution))\
                      + " ygrid:" + str(np.around(self.ygrid, decimals=self.max_resolution))\
                      + " xwidth:" + str(np.around(self.xwidth, decimals=self.max_resolution))\
                      + " ywidth:" + str(np.around(self.ywidth, decimals=self.max_resolution))\
                      + " xlayer:" + str(self.xlayer)\
                      + " ylayer:" + str(self.ylayer)\
                      + " viamap:{"
          for vm_name, vm in self.viamap.items():
              display_str+=vm_name + ": " + str(vm.tolist()) + " "
          display_str+="}"
          print(display_str)
  
      def export_dict(self):
          """
          Export grid information in dict format
  
          Returns
          -------
          dict
              Grid information
          """
          export_dict=GridObject.export_dict(self)
          export_dict['xwidth'] = np.around(self.xwidth, decimals=self.max_resolution).tolist()
          export_dict['ywidth'] = np.around(self.ywidth, decimals=self.max_resolution).tolist()
          export_dict['xlayer'] = self.xlayer
          export_dict['ylayer'] = self.ylayer
          export_dict['viamap'] = dict()
          for vn, v in self.viamap.items():
              export_dict['viamap'][vn]=[]
              for _v in v:
                  export_dict['viamap'][vn].append(_v.tolist())
          return export_dict
  
      def update_viamap(self, viamap):
          """use laygo.GridObject.RouteGrid.viamap instead"""
          self.viamap=viamap
  
  if __name__ == '__main__':
      lgrid=GridObject()
      print('LayoutGrid test')
      lgrid.xgrid = np.array([0.2, 0.4, 0.6])
      lgrid.ygrid = np.array([0, 0.4, 0.9, 1.2, 2, 3])
      lgrid.width = 1.2
      lgrid.height = 3.2
      phycoord = np.array([[-0.2, -0.2], [0, 2], [4,2.2], [0.5, 1.5], [1.3, 3.6], [8,2.3]])
      print("  xgrid:" + str(lgrid.xgrid) + " width:" + str(lgrid.width))
      print("  ygrid:" + str(lgrid.ygrid) + " height:" + str(lgrid.height))
      print('physical grid to abstract grid')
      print("  input:"+str(phycoord.tolist()))
      abscoord=lgrid.get_absgrid_coord_xy(phycoord)
      print("  output:"+str(abscoord.tolist()))
      print('abstract grid to physical grid')
      phycoord=lgrid.get_phygrid_xy(abscoord).tolist()
      print("  output:"+str(phycoord))
  