'''
### ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ###
                   308-304 - Object-Oriented Software Design
                                 ASSIGNMENT  1

   SSheetLIST.py ---
      class SpreadsheetData implementation, based on Python lists.

   last modified: 01/24/02
                       ===============================
                             Copyright (c)  2002
                            Jean-Sébastien BOLDUC
                             (jseb@cs.mcgill.ca)

                        McGill University  (Montréal)
                       ===============================

### ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ###
'''

# Import CellData and CellCoordinate implementations
from CData  import *
from CCoord import *

class SpreadsheetData:
  '''
  Encapsulates a dynamically sized spreadsheet structure containing CellData
  data and indexed by CellCoordinate coordinates.
  THIS VERSION BASED ON PYTHON LISTS
  '''

  ### -------------------------------------------------------------  API -- ###

  def __init__(self):
    ''' ->  -- SpreadsheetData constructor.'''
    # Data stored in private variable __table, a list of lists (a SQUARE
    # array, for this first prototype):
    # i.e., __table[i]     is a list, the array's i-th row;
    #       __table[i][j]  is the j-th element in that row
    #                      (:CellData | None).
    # __table is initialized to an empty list (spreadsheet is empty).
    self.__table = []
    # For better use of memory, the __table indexes (i, j) do not necessarily
    # correspond to the spreadsheet coordinates. To illustrate why, consider a
    # spreadheet with a single entry at coordinate (1000, 1000) -- it is
    # obviously not a good idea to store ~10e6 empty entries in __table. The
    # spreadsheet coordinates corresponding to __table[0][0] are stored in the
    # private variables __headRow and __headCol (both set to None for an empty
    # spreadsheet).
    self.__headRow = self.__headCol = None
    # __table is dynamically resized so that, at all times, it is just large
    # enough to contain all nonempty spreadsheet data: in other words, __table
    # always has
    #       ( getRB().getRow() - getLU().getRow + 1)         rows, and
    #       ( getRB().getColumn() - getLU().getColumn + 1)   columns.
    # This is obviously not the most efficient approach, from an amortized
    # analysis point of view.
    # Checking whether __table needs to be extended upon insertion of a new
    # piece of data is relatively straightforward. Checking whether __table
    # needs to be shrinked after deletion of a piece of data, however, turns
    # out to be much trickier. To help in that task, we introduce two lists
    # that respectively keep track of the number of nonempty entries in each
    # row/column.
    self.__rowEntries = []
    self.__colEntries = []

  def __setitem__(self, coord, data):
    '''coord:CellCoordinate, data:CellData ->

    Update the content of cell indexed by coord with data.
    A KeyError is raised on bad coordinate, and a TypeError is raised on
    bad value. Example use:
          sd[CellCoordinate(3,4)] = CellData(33)
    '''
    # First make sure that coord and data are the right type:
    if not isinstance(coord, CellCoordinate):
      raise KeyError, 'coord must be CellCoordinate object'
    if not isinstance(data, CellData):
      raise TypeError, 'data must be CellData object'

    luCoord = self.getLU()
    if luCoord == None: # This means the spreadsheet is empty
      # update private variables:
      self.__table = [[data]] # (or a copy thereof)
      self.__headRow = coord.getRow()
      self.__headCol = coord.getColumn()
      self.__rowEntries = [1]
      self.__colEntries = [1]
      # stop here
      return None
    rbCoord = self.getRB()

    # Before storing data, check whether coord falls within __table.
    # If not, extend __table:
    delta = luCoord.getRow() - coord.getRow()
    if delta > 0:
      self.__extendTable('N', delta)
    else:
      delta = coord.getRow() - rbCoord.getRow()
      if delta > 0:
        self.__extendTable('S', delta)

    delta = coord.getColumn() - rbCoord.getColumn()
    if delta > 0:
      self.__extendTable('E', delta)
    else:
      delta = luCoord.getColumn() - coord.getColumn()
      if delta > 0:
        self.__extendTable('W', delta)

    # Store the data
    # If __table[i][j] already contained a CellData object, we don't need to
    # explicitely delete that object, thanks to garbage collection.
    i, j = self.__indexFromCoord(coord)
    self.__table[i][j] = data # (or a copy thereof)
    # Don't forget to update following private variables:
    self.__rowEntries[i] = self.__rowEntries[i] + 1
    self.__colEntries[j] = self.__colEntries[j] + 1

  def __getitem__(self, coord):
    '''coord:CellCoordinate -> :CellData | None

    Return the content of a cell indexed by coord (return None if the cell is
    empty).
    A KeyError is raised on bad coordinate. Example use:
          sd[CellCoordinate(3,4)]
    '''
    # Make sure coord is the right type:
    if not isinstance(coord, CellCoordinate):
      raise KeyError, 'coordinate must be CellCoordinate object'

    i, j = self.__indexFromCoord(coord)
    try:
      return self.__table[i][j]
    except TypeError: # One or both indexes are None (coord outside __table)
      return None

  def __delitem__(self, coord):
    '''coord:CellCoordinate ->

    Empty the cell indexed by coord'.
    A KeyError is raised on bad coordinate. Example use:
          del sd[CellCoordinate(3,4)]
    '''
    # Make sure coord is the right type:
    if not isinstance(coord, CellCoordinate):
      raise KeyError, 'coordinate must be CellCoordinate object'

    i, j = self.__indexFromCoord(coord)
    try:
      # Update the following private variables only if __table[i][j] actually
      # contains a CellData object:
      if self.__table[i][j] != None:
        self.__rowEntries[i] = self.__rowEntries[i] - 1
        self.__colEntries[j] = self.__colEntries[j] - 1
    except TypeError: # One or both indexes are None (coord outside __table)
      # stop here
      return None

    # Delete the CellData object (if any)
    # If __table[i][j] actually contained a CellData object (which would
    # usually be the case), we don't need to explicitely delete the object,
    # thanks to garbage collection.
    self.__table[i][j] = None

    if self.__table == [[None]]: # This means the spreadsheet is now empty
      self.__init__() # reinitialize all private variables, and stop here
      return None

    # Shrink __table if necessary:
    # Build a list that contains all k such that __rowEntries[k]>0 (indexes of
    # nonempty rows):
    neRowIndexes = []
    for k in range(len(self.__rowEntries)):
      if self.__rowEntries[k] > 0:
        neRowIndexes.append(k)
    # from this list, find:
    #    minRow -- the lowest index such that __rowEntries[min] != 0
    #    maxRow -- the highest index such that __rowEntries[max] != 0
    minRow = min(neRowIndexes)
    maxRow = max(neRowIndexes)
    if minRow != 0:
      self.__shrinkTable('N', minRow)
    elif maxRow != len(self.__rowEntries) - 1:
      self.__shrinkTable('S', len(self.__rowEntries) - 1 - maxRow)

    # Do the same as above, for columns:
    neColIndexes = []
    for k in range(len(self.__colEntries)):
      if self.__colEntries[k] > 0:
        neColIndexes.append(k)
    minCol = min(neColIndexes)
    maxCol = max(neColIndexes)
    if minCol != 0:
      self.__shrinkTable('W', minCol)
    elif maxRow != len(self.__colEntries) - 1:
      self.__shrinkTable('E', len(self.__colEntries) - 1 - maxRow)

  def getLU(self):
    ''' -> :CellCoordinate | None

    Return a CellCoordinate containing the Left-most non-empty column,
    and Upper-most non-emtpy row.
    Return None in case of an empty spreadsheet
    '''
    # First check whether spreadsheet is empty
    if self.__table == []:
      return None

    C = CellCoordinate()
    C.setRow(self.__headRow)
    C.setColumn(self.__headCol)
    return C

  def getRB(self):
    ''' -> :CellCoordinate | None

    Return a CellCoordinate containing the Right-most non-empty column,
    and Bottom-most non-emtpy row.
    Return None in case of an empty spreadsheet.
    '''
    # First check whether spreadsheet is empty
    if self.__table == []:
      return None

    C = CellCoordinate()
    C.setRow(self.__headRow + len(self.__table) - 1 )
    C.setColumn(self.__headCol + len(self.__table[0]) - 1 )
    return C


  def __str__(self):
    ''' -> :String

    Return the string representation of the SpreadSheet.
    This looks like a table of values with spaces for empty cells.
    The row and column indexes are also shown.
    '''
    # This method prints the smallest rectangular area of the spreadsheet that
    # contains all data. It doesn't do anything special if the width does not
    # fit the display.
    # The formatting is adapted CellData objects containing only integers
    # between -9999 and 9999 and row/column indexes <= 9999
    # (some fine-tuning here).

    S = '' # the string to be returned

    luCoord = self.getLU()
    if luCoord == None: # This means the spreadsheet is empty
      return S
    rbCoord = self.getRB()

    # Build spreadsheet heading (column indexes)
    S = S + " "*6
    for c in range(luCoord.getColumn(), rbCoord.getColumn()+1):
      S = S + "C%-5d" % c
    S = S + "\n"

    for row in range(luCoord.getRow(), rbCoord.getRow()+1):
      # Build row heading (row indexes)
      S = S + "R%-5d" % row
      # display data:
      for col in range(luCoord.getColumn(), rbCoord.getColumn()+1):
        data = self[CellCoordinate(row, col)]
        if data == None:
          S = S + " "*6
        else:
          S = S + "%- 6d" % (data.getValue())
      S = S + "\n"

    return S

  ### -------------------------------------------------  PRIVATE METHODS -- ###

    i, j = self.__indexFromCoord(coord)

  def __indexFromCoord(self, coord):
    ''' coord:CellCoordinate -> (:Integer | None, :Integer | None)

    Return the (i, j) indexes for the private variable __table
    that correspond to a spreadsheet coordinate. if __table is empty or if the
    row/column is outside __table, the corresponding index(es) is None.
    '''
    try:
      i = coord.getRow() - self.__headRow
    except TypeError: # happens if __headRow is None (spreadsheet empty)
      i = -1
    if i < 0 or i > len(self.__table)-1:
      i = None

    try:
      j = coord.getColumn() - self.__headCol
    except TypeError: # happens if __headCol is None (spreadsheet empty)
      j = -1
    if j < 0 or j > len(self.__table[0])-1:
      j = None

    return (i, j)

  def __extendTable(self, direction, size):
    ''' direction:String, size:Integer ->

    Extend __table.
    The direction is a character indicating in which direction to extend
    __table ('N', 'S', 'E', 'W'). size is a positive Integer indicating how
    many rows/columns to add in that direction.
    All private variables might be affected here.
    '''
    # adding ROWS
    if direction in ('N', 'S'):
      row = [None]*len(self.__table[0])
      # Build block of rows
      block = []
      for i in range(size):
        block.append(row[:])

      if direction == 'N': # add block ABOVE
        self.__headRow = self.__headRow - size
        self.__rowEntries = [0]*size + self.__rowEntries
        self.__table = block + self.__table
      elif direction == 'S': # add block BELOW
        self.__rowEntries = self.__rowEntries + [0]*size
        self.__table = self.__table + block

    # adding COLUMNS
    elif direction in ('E', 'W'):
      cols = [None]*size
      if direction == 'E': # add cols to the RIGHT
        self.__colEntries = self.__colEntries + [0]*size
        for row in range(len(self.__table)):
          self.__table[row] = self.__table[row] + cols[:]
      elif direction == 'W': # add cols to the LEFT
        self.__headCol = self.__headCol - size
        self.__colEntries = [0]*size + self.__colEntries
        for row in range(len(self.__table)):
          self.__table[row] =  cols[:] + self.__table[row]

  def __shrinkTable(self, direction, size):
    ''' direction:String, size:Integer ->

    Shrink __table.
    The direction is a character indicating in which direction to shrink
    __table ('N', 'S', 'E', 'W'). size is a positive Integer indicating how
    many rows/columns to delete in that direction.
    All private variables might be affected here.
    '''
    # deleting ROWS
    if direction == 'N': # delete rows ABOVE
      self.__headRow = self.__headRow + size
      del self.__rowEntries[0:size]
      del self.__table[0:size]
    elif direction == 'S': # delete rows BELOW
      del self.__rowEntries[len(self.__rowEntries)-size:]
      del self.__table[len(self.__table)-size:]

    # deleting COLUMNS
    elif direction == 'E': # delete cols from the RIGHT
      del self.__colEntries[len(self.__colEntries)-size:]
      for row in range(len(self.__table)):
        del self.__table[row][len(self.__table[row])-size:]
    elif direction == 'W': # delete cols from the LEFT
      self.__headCol = self.__headCol + size
      del self.__colEntries[0:size]
      for row in range(len(self.__table)):
        del self.__table[row][0:size]