package design;

import java.util.*;

/**
 * Created by gouthamvidyapradhan on 16/09/2017.
 *
 * <p>Your task is to design the basic function of Excel and implement the function of sum formula.
 * Specifically, you need to implement the following functions:
 *
 * <p>Excel(int H, char W): This is the constructor. The inputs represents the height and width of
 * the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a
 * character range from 'A' to 'Z'. It represents that the width is the number of characters from
 * 'A' to W. The Excel form content is represented by a height * width 2D integer array C, it should
 * be initialized to zero. You should assume that the first row of C starts from 1, and the first
 * column of C starts from 'A'.
 *
 * <p>
 *
 * <p>void Set(int row, char column, int val): Change the value at C(row, column) to be val.
 *
 * <p>
 *
 * <p>int Get(int row, char column): Return the value at C(row, column).
 *
 * <p>
 *
 * <p>int Sum(int row, char column, List of Strings : numbers): This function calculate and set the
 * value at C(row, column), where the value should be the sum of cells represented by numbers. This
 * function return the sum result at C(row, column). This sum formula should exist until this cell
 * is overlapped by another value or another sum formula.
 *
 * <p>numbers is a list of strings that each string represent a cell or a range of cells. If the
 * string represent a single cell, then it has the following format : ColRow. For example, "F7"
 * represents the cell at (7, F).
 *
 * <p>If the string represent a range of cells, then it has the following format : ColRow1:ColRow2.
 * The range will always be a rectangle, and ColRow1 represent the position of the top-left cell,
 * and ColRow2 represents the position of the bottom-right cell.
 *
 * <p>
 *
 * <p>Example 1: Excel(3,"C"); // construct a 3*3 2D array with all zero. // A B C // 1 0 0 0 // 2 0
 * 0 0 // 3 0 0 0
 *
 * <p>Set(1, "A", 2); // set C(1,"A") to be 2. // A B C // 1 2 0 0 // 2 0 0 0 // 3 0 0 0
 *
 * <p>Sum(3, "C", ["A1", "A1:B2"]); // set C(3,"C") to be the sum of value at C(1,"A") and the
 * values sum of the rectangle range whose top-left cell is C (1,"A") and bottom-right cell is
 * C(2,"B"). Return 4. // A B C // 1 2 0 0 // 2 0 0 0 // 3 0 0 4
 *
 * <p>Set(2, "B", 2); // set C(2,"B") to be 2. Note C(3, "C") should also be changed. // A B C // 1
 * 2 0 0 // 2 0 2 0 // 3 0 0 6 Note: You could assume that there won't be any circular sum
 * reference. For example, A1 = sum(B1) and B1 = sum(A1). The test cases are using double-quotes to
 * represent a character. Please remember to RESET your class variables declared in class Excel, as
 * static/class variables are persisted across multiple test cases.
 *
 * <p>Solution: Build a graph and for each cell keep track of forward and backward links. When a
 * cell is updated with a new value broadcast the new value to all the forward links and remove all
 * the forward links pointing to this particular cell.
 */
public class Excel {

  private Map<String, Set<String>> fwdEdges; // Forward links from cell
  private Map<String, List<String>> backEdge; // All backward links from cell
  private Map<String, Integer> count; // Keep track of number of times the cell is linked
  private int[][] grid; // excel grid

  /**
   * Initialize datastructure
   *
   * @param H row
   * @param W column
   */
  public Excel(int H, char W) {
    grid = new int[H][(Character.toUpperCase(W) - 'A') + 1];
    fwdEdges = new HashMap<>();
    backEdge = new HashMap<>();
    count = new HashMap<>();
  }

  public static void main(String[] args) throws Exception {
    Excel excel = new Excel(26, 'Z');
    excel.set(1, 'A', 1);
    excel.set(1, 'I', 1);
    String[] arr = {"A1:D6", "A1:G3", "A1:C12"};
    String[] arr1 = {"A1:D7", "D1:F10", "D3:I8", "I1:I9"};
    System.out.println(excel.get(1, 'A'));
    System.out.println(excel.sum(7, 'D', arr));
    System.out.println(excel.get(1, 'A'));
    System.out.println(excel.sum(10, 'G', arr1));
    System.out.println(excel.get(1, 'A'));
  }

  /**
   * Set value to the grid
   *
   * @param r row
   * @param c column
   * @param v value
   */
  public void set(int r, char c, int v) {
    setValue(r, c, v);
    removeForwardEdges(String.valueOf(c) + r);
  }

  private void setValue(int r, char c, int v) {
    int curr = grid[r - 1][Character.toUpperCase(c) - 'A'];
    grid[r - 1][Character.toUpperCase(c) - 'A'] = v;
    broadcast(v - curr, String.valueOf(c) + r);
  }

  /**
   * Remove all the links
   *
   * @param node node
   */
  private void removeForwardEdges(String node) {
    List<String> parents = backEdge.get(node);
    if (parents != null) {
      for (String p : parents) {
        Set<String> children = fwdEdges.get(p);
        if (children != null) {
          count.remove(p + ":" + node);
          children.remove(node);
        }
      }
    }
  }

  /**
   * Broadcast to all the links
   *
   * @param v current node
   * @param node node
   */
  private void broadcast(int v, String node) {
    Set<String> children = fwdEdges.get(node);
    if (children != null) {
      for (String c : children) {
        int order = count.get(node + ":" + c);
        grid[Integer.parseInt(c.substring(1)) - 1][c.charAt(0) - 'A'] += (v * order);
        broadcast(v, c);
      }
    }
  }

  public int get(int r, char c) {
    return grid[r - 1][c - 'A'];
  }

  /**
   * Sum range of cells
   *
   * @param r row
   * @param c column
   * @param strs Strings
   * @return integer sum
   */
  public int sum(int r, char c, String[] strs) {
    int sum = 0;
    // Remove all the forward and backward edges or links
    removeForwardEdges(c + String.valueOf(r));
    backEdge.remove(c + String.valueOf(r));
    Set<String> nodes = new HashSet<>();
    for (String s : strs) {
      String[] range = s.split(":");
      if (range.length > 1) {
        int startRow = Integer.parseInt(range[0].substring(1)) - 1;
        int startColumn = range[0].charAt(0) - 'A';

        int endRow = Integer.parseInt(range[1].substring(1)) - 1;
        int endColumn = range[1].charAt(0) - 'A';

        for (int i = startRow; i <= endRow; i++) {
          for (int j = startColumn; j <= endColumn; j++) {
            char newC = (char) ('A' + j);
            nodes.add(newC + String.valueOf(i + 1));
            sum += grid[i][j];
            String key = newC + String.valueOf(i + 1) + ":" + (c + String.valueOf(r));
            if (count.putIfAbsent(key, 1) != null) {
              count.put(key, (count.get(key) + 1));
            }
          }
        }
      } else {
        sum += grid[Integer.parseInt(range[0].substring(1)) - 1][range[0].charAt(0) - 'A'];
        nodes.add(range[0]);
        String key = range[0] + ":" + (c + String.valueOf(r));
        if (count.putIfAbsent(key, 1) != null) {
          count.put(key, count.get(key) + 1);
        }
      }
    }
    // set value
    setValue(r, c, sum);

    // make new forward-edges
    for (String n : nodes) {
      Set<String> children = fwdEdges.get(n);
      if (children == null) {
        children = new HashSet<>();
        fwdEdges.put(n, children);
      }
      children.add(c + String.valueOf(r));
    }

    // make new back-edges
    List<String> backEdges = new ArrayList<>();
    backEdges.addAll(nodes);
    backEdge.put(c + String.valueOf(r), backEdges);
    return sum;
  }
}