# -*- coding: utf-8 -*-
# Copyright (c) 2013 The ChromiumOS Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

"""Table generating, analyzing and printing functions.

This defines several classes that are used to generate, analyze and print
tables.

Example usage:

  from cros_utils import tabulator

  data = [["benchmark1", "33", "44"],["benchmark2", "44", "33"]]
  tabulator.GetSimpleTable(data)

You could also use it to generate more complex tables with analysis such as
p-values, custom colors, etc. Tables are generated by TableGenerator and
analyzed/formatted by TableFormatter. TableFormatter can take in a list of
columns with custom result computation and coloring, and will compare values in
each row according to taht scheme. Here is a complex example on printing a
table:

  from cros_utils import tabulator

  runs = [[{"k1": "10", "k2": "12", "k5": "40", "k6": "40",
            "ms_1": "20", "k7": "FAIL", "k8": "PASS", "k9": "PASS",
            "k10": "0"},
           {"k1": "13", "k2": "14", "k3": "15", "ms_1": "10", "k8": "PASS",
            "k9": "FAIL", "k10": "0"}],
          [{"k1": "50", "k2": "51", "k3": "52", "k4": "53", "k5": "35", "k6":
            "45", "ms_1": "200", "ms_2": "20", "k7": "FAIL", "k8": "PASS", "k9":
            "PASS"}]]
  labels = ["vanilla", "modified"]
  tg = TableGenerator(runs, labels, TableGenerator.SORT_BY_VALUES_DESC)
  table = tg.GetTable()
  columns = [Column(LiteralResult(),
                    Format(),
                    "Literal"),
             Column(AmeanResult(),
                    Format()),
             Column(StdResult(),
                    Format()),
             Column(CoeffVarResult(),
                    CoeffVarFormat()),
             Column(NonEmptyCountResult(),
                    Format()),
             Column(AmeanRatioResult(),
                    PercentFormat()),
             Column(AmeanRatioResult(),
                    RatioFormat()),
             Column(GmeanRatioResult(),
                    RatioFormat()),
             Column(PValueResult(),
                    PValueFormat()),
            ]
  tf = TableFormatter(table, columns)
  cell_table = tf.GetCellTable()
  tp = TablePrinter(cell_table, out_to)
  print tp.Print()
"""

from __future__ import division
from __future__ import print_function

import collections
import getpass
import math
import statistics
import sys
# TODO(crbug.com/980719): Drop scipy in the future.
# pylint: disable=import-error
import scipy

from cros_utils.email_sender import EmailSender
from cros_utils import misc


def _AllFloat(values):
  return all([misc.IsFloat(v) for v in values])


def _GetFloats(values):
  return [float(v) for v in values]


def _StripNone(results):
  res = []
  for result in results:
    if result is not None:
      res.append(result)
  return res


def _RemoveMinMax(cell, values):
  if len(values) < 3:
    print('WARNING: Values count is less than 3, not ignoring min/max values')
    print('WARNING: Cell name:', cell.name, 'Values:', values)
    return values

  values.remove(min(values))
  values.remove(max(values))
  return values


class TableGenerator(object):
  """Creates a table from a list of list of dicts.

  The main public function is called GetTable().
  """
  SORT_BY_KEYS = 0
  SORT_BY_KEYS_DESC = 1
  SORT_BY_VALUES = 2
  SORT_BY_VALUES_DESC = 3
  NO_SORT = 4

  MISSING_VALUE = 'x'

  def __init__(self, d, l, sort=NO_SORT, key_name='keys'):
    self._runs = d
    self._labels = l
    self._sort = sort
    self._key_name = key_name

  def _AggregateKeys(self):
    keys = collections.OrderedDict()
    for run_list in self._runs:
      for run in run_list:
        keys.update(dict.fromkeys(run.keys()))
    return list(keys.keys())

  def _GetHighestValue(self, key):
    values = []
    for run_list in self._runs:
      for run in run_list:
        if key in run:
          values.append(run[key])
    values = _StripNone(values)
    if _AllFloat(values):
      values = _GetFloats(values)
    return max(values)

  def _GetLowestValue(self, key):
    values = []
    for run_list in self._runs:
      for run in run_list:
        if key in run:
          values.append(run[key])
    values = _StripNone(values)
    if _AllFloat(values):
      values = _GetFloats(values)
    return min(values)

  def _SortKeys(self, keys):
    if self._sort == self.SORT_BY_KEYS:
      return sorted(keys)
    elif self._sort == self.SORT_BY_VALUES:
      # pylint: disable=unnecessary-lambda
      return sorted(keys, key=lambda x: self._GetLowestValue(x))
    elif self._sort == self.SORT_BY_VALUES_DESC:
      # pylint: disable=unnecessary-lambda
      return sorted(keys, key=lambda x: self._GetHighestValue(x), reverse=True)
    elif self._sort == self.NO_SORT:
      return keys
    else:
      assert 0, 'Unimplemented sort %s' % self._sort

  def _GetKeys(self):
    keys = self._AggregateKeys()
    return self._SortKeys(keys)

  def GetTable(self, number_of_rows=sys.maxsize):
    """Returns a table from a list of list of dicts.

    Examples:
      We have the following runs:
        [[{"k1": "v1", "k2": "v2"}, {"k1": "v3"}],
         [{"k1": "v4", "k4": "v5"}]]
      and the following labels:
        ["vanilla", "modified"]
      it will return:
        [["Key", "vanilla", "modified"]
         ["k1", ["v1", "v3"], ["v4"]]
         ["k2", ["v2"], []]
         ["k4", [], ["v5"]]]
      The returned table can then be processed further by other classes in this
      module.

    The list of list of dicts is passed into the constructor of TableGenerator.
    This method converts that into a canonical list of lists which represents a
    table of values.

    Args:
      number_of_rows: Maximum number of rows to return from the table.

    Returns:
      A list of lists which is the table.
    """
    keys = self._GetKeys()
    header = [self._key_name] + self._labels
    table = [header]
    rows = 0
    for k in keys:
      row = [k]
      unit = None
      for run_list in self._runs:
        v = []
        for run in run_list:
          if k in run:
            if isinstance(run[k], list):
              val = run[k][0]
              unit = run[k][1]
            else:
              val = run[k]
            v.append(val)
          else:
            v.append(None)
        row.append(v)
      # If we got a 'unit' value, append the units name to the key name.
      if unit:
        keyname = row[0] + ' (%s) ' % unit
        row[0] = keyname
      table.append(row)
      rows += 1
      if rows == number_of_rows:
        break
    return table


class SamplesTableGenerator(TableGenerator):
  """Creates a table with only samples from the results

  The main public function is called GetTable().

  Different than TableGenerator, self._runs is now a dict of {benchmark: runs}
  We are expecting there is 'samples' in `runs`.
  """

  def __init__(self, run_keyvals, label_list, iter_counts, weights):
    TableGenerator.__init__(
        self, run_keyvals, label_list, key_name='Benchmarks')
    self._iter_counts = iter_counts
    self._weights = weights

  def _GetKeys(self):
    keys = self._runs.keys()
    return self._SortKeys(keys)

  def GetTable(self, number_of_rows=sys.maxsize):
    """Returns a tuple, which contains three args:

      1) a table from a list of list of dicts.
      2) updated benchmark_results run_keyvals with composite benchmark
      3) updated benchmark_results iter_count with composite benchmark

    The dict of list of list of dicts is passed into the constructor of
    SamplesTableGenerator.
    This method converts that into a canonical list of lists which
    represents a table of values.

    Examples:
      We have the following runs:
        {bench1: [[{"samples": "v1"}, {"samples": "v2"}],
                  [{"samples": "v3"}, {"samples": "v4"}]]
         bench2: [[{"samples": "v21"}, None],
                  [{"samples": "v22"}, {"samples": "v23"}]]}
      and weights of benchmarks:
        {bench1: w1, bench2: w2}
      and the following labels:
        ["vanilla", "modified"]
      it will return:
        [["Benchmark", "Weights", "vanilla", "modified"]
         ["bench1", w1,
            ((2, 0), ["v1*w1", "v2*w1"]), ((2, 0), ["v3*w1", "v4*w1"])]
         ["bench2", w2,
            ((1, 1), ["v21*w2", None]), ((2, 0), ["v22*w2", "v23*w2"])]
         ["Composite Benchmark", N/A,
            ((1, 1), ["v1*w1+v21*w2", None]),
            ((2, 0), ["v3*w1+v22*w2", "v4*w1+ v23*w2"])]]
      The returned table can then be processed further by other classes in this
      module.

    Args:
      number_of_rows: Maximum number of rows to return from the table.

    Returns:
      A list of lists which is the table.
    """
    keys = self._GetKeys()
    header = [self._key_name, 'Weights'] + self._labels
    table = [header]
    rows = 0
    iterations = 0

    for k in keys:
      bench_runs = self._runs[k]
      unit = None
      all_runs_empty = all(not dict for label in bench_runs for dict in label)
      if all_runs_empty:
        cell = Cell()
        cell.string_value = ('Benchmark %s contains no result.'
                             ' Is the benchmark name valid?' % k)
        table.append([cell])
      else:
        row = [k]
        row.append(self._weights[k])
        for run_list in bench_runs:
          run_pass = 0
          run_fail = 0
          v = []
          for run in run_list:
            if 'samples' in run:
              if isinstance(run['samples'], list):
                val = run['samples'][0] * self._weights[k]
                unit = run['samples'][1]
              else:
                val = run['samples'] * self._weights[k]
              v.append(val)
              run_pass += 1
            else:
              v.append(None)
              run_fail += 1
          one_tuple = ((run_pass, run_fail), v)
          if iterations not in (0, run_pass + run_fail):
            raise ValueError('Iterations of each benchmark run ' \
                             'are not the same')
          iterations = run_pass + run_fail
          row.append(one_tuple)
        if unit:
          keyname = row[0] + ' (%s) ' % unit
          row[0] = keyname
        table.append(row)
        rows += 1
        if rows == number_of_rows:
          break

    k = 'Composite Benchmark'
    if k in keys:
      raise RuntimeError('Composite benchmark already exists in results')

    # Create a new composite benchmark row at the bottom of the summary table
    # The new row will be like the format in example:
    # ["Composite Benchmark", N/A,
    #        ((1, 1), ["v1*w1+v21*w2", None]),
    #        ((2, 0), ["v3*w1+v22*w2", "v4*w1+ v23*w2"])]]
    # First we will create a row of [key, weight, [[0] * iterations] * labels]
    row = [None] * len(header)
    row[0] = '%s (samples)' % k
    row[1] = 'N/A'
    for label_index in range(2, len(row)):
      row[label_index] = [0] * iterations

    for cur_row in table[1:]:
      # Iterate through each benchmark
      if len(cur_row) > 1:
        for label_index in range(2, len(cur_row)):
          # Iterate through each run in a single benchmark
          # each result should look like ((pass, fail), [values_list])
          bench_runs = cur_row[label_index][1]
          for index in range(iterations):
            # Accumulate each run result to composite benchmark run
            # If any run fails, then we set this run for composite benchmark
            # to None so that we know it fails.
            if bench_runs[index] and row[label_index][index] is not None:
              row[label_index][index] += bench_runs[index]
            else:
              row[label_index][index] = None
      else:
        # One benchmark totally fails, no valid data will be in final result
        for label_index in range(2, len(row)):
          row[label_index] = [None] * iterations
        break
    # Calculate pass and fail count for composite benchmark
    for label_index in range(2, len(row)):
      run_pass = 0
      run_fail = 0
      for run in row[label_index]:
        if run:
          run_pass += 1
        else:
          run_fail += 1
      row[label_index] = ((run_pass, run_fail), row[label_index])
    table.append(row)

    # Now that we have the table genearted, we want to store this new composite
    # benchmark into the benchmark_result in ResultReport object.
    # This will be used to generate a full table which contains our composite
    # benchmark.
    # We need to create composite benchmark result and add it to keyvals in
    # benchmark_results.
    v = []
    for label in row[2:]:
      # each label's result looks like ((pass, fail), [values])
      benchmark_runs = label[1]
      # List of values of each label
      single_run_list = []
      for run in benchmark_runs:
        # Result of each run under the same label is a dict of keys.
        # Here the only key we will add for composite benchmark is the
        # weighted_samples we added up.
        one_dict = {}
        if run:
          one_dict[u'weighted_samples'] = [run, u'samples']
          one_dict['retval'] = 0
        else:
          one_dict['retval'] = 1
        single_run_list.append(one_dict)
      v.append(single_run_list)

    self._runs[k] = v
    self._iter_counts[k] = iterations

    return (table, self._runs, self._iter_counts)


class Result(object):
  """A class that respresents a single result.

  This single result is obtained by condensing the information from a list of
  runs and a list of baseline runs.
  """

  def __init__(self):
    pass

  def _AllStringsSame(self, values):
    values_set = set(values)
    return len(values_set) == 1

  def NeedsBaseline(self):
    return False

  # pylint: disable=unused-argument
  def _Literal(self, cell, values, baseline_values):
    cell.value = ' '.join([str(v) for v in values])

  def _ComputeFloat(self, cell, values, baseline_values):
    self._Literal(cell, values, baseline_values)

  def _ComputeString(self, cell, values, baseline_values):
    self._Literal(cell, values, baseline_values)

  def _InvertIfLowerIsBetter(self, cell):
    pass

  def _GetGmean(self, values):
    if not values:
      return float('nan')
    if any([v < 0 for v in values]):
      return float('nan')
    if any([v == 0 for v in values]):
      return 0.0
    log_list = [math.log(v) for v in values]
    gmean_log = sum(log_list) / len(log_list)
    return math.exp(gmean_log)

  def Compute(self, cell, values, baseline_values):
    """Compute the result given a list of values and baseline values.

    Args:
      cell: A cell data structure to populate.
      values: List of values.
      baseline_values: List of baseline values. Can be none if this is the
      baseline itself.
    """
    all_floats = True
    values = _StripNone(values)
    if not values:
      cell.value = ''
      return
    if _AllFloat(values):
      float_values = _GetFloats(values)
    else:
      all_floats = False
    if baseline_values:
      baseline_values = _StripNone(baseline_values)
    if baseline_values:
      if _AllFloat(baseline_values):
        float_baseline_values = _GetFloats(baseline_values)
      else:
        all_floats = False
    else:
      if self.NeedsBaseline():
        cell.value = ''
        return
      float_baseline_values = None
    if all_floats:
      self._ComputeFloat(cell, float_values, float_baseline_values)
      self._InvertIfLowerIsBetter(cell)
    else:
      self._ComputeString(cell, values, baseline_values)


class LiteralResult(Result):
  """A literal result."""

  def __init__(self, iteration=0):
    super(LiteralResult, self).__init__()
    self.iteration = iteration

  def Compute(self, cell, values, baseline_values):
    try:
      cell.value = values[self.iteration]
    except IndexError:
      cell.value = '-'


class NonEmptyCountResult(Result):
  """A class that counts the number of non-empty results.

  The number of non-empty values will be stored in the cell.
  """

  def Compute(self, cell, values, baseline_values):
    """Put the number of non-empty values in the cell result.

    Args:
      cell: Put the result in cell.value.
      values: A list of values for the row.
      baseline_values: A list of baseline values for the row.
    """
    cell.value = len(_StripNone(values))
    if not baseline_values:
      return
    base_value = len(_StripNone(baseline_values))
    if cell.value == base_value:
      return
    f = ColorBoxFormat()
    len_values = len(values)
    len_baseline_values = len(baseline_values)
    tmp_cell = Cell()
    tmp_cell.value = 1.0 + (
        float(cell.value - base_value) / (max(len_values, len_baseline_values)))
    f.Compute(tmp_cell)
    cell.bgcolor = tmp_cell.bgcolor


class StringMeanResult(Result):
  """Mean of string values."""

  def _ComputeString(self, cell, values, baseline_values):
    if self._AllStringsSame(values):
      cell.value = str(values[0])
    else:
      cell.value = '?'


class AmeanResult(StringMeanResult):
  """Arithmetic mean."""

  def __init__(self, ignore_min_max=False):
    super(AmeanResult, self).__init__()
    self.ignore_min_max = ignore_min_max

  def _ComputeFloat(self, cell, values, baseline_values):
    if self.ignore_min_max:
      values = _RemoveMinMax(cell, values)
    cell.value = statistics.mean(values)


class RawResult(Result):
  """Raw result."""


class IterationResult(Result):
  """Iteration result."""


class MinResult(Result):
  """Minimum."""

  def _ComputeFloat(self, cell, values, baseline_values):
    cell.value = min(values)

  def _ComputeString(self, cell, values, baseline_values):
    if values:
      cell.value = min(values)
    else:
      cell.value = ''


class MaxResult(Result):
  """Maximum."""

  def _ComputeFloat(self, cell, values, baseline_values):
    cell.value = max(values)

  def _ComputeString(self, cell, values, baseline_values):
    if values:
      cell.value = max(values)
    else:
      cell.value = ''


class NumericalResult(Result):
  """Numerical result."""

  def _ComputeString(self, cell, values, baseline_values):
    cell.value = '?'


class StdResult(NumericalResult):
  """Standard deviation."""

  def __init__(self, ignore_min_max=False):
    super(StdResult, self).__init__()
    self.ignore_min_max = ignore_min_max

  def _ComputeFloat(self, cell, values, baseline_values):
    if self.ignore_min_max:
      values = _RemoveMinMax(cell, values)
    cell.value = statistics.pstdev(values)


class CoeffVarResult(NumericalResult):
  """Standard deviation / Mean"""

  def __init__(self, ignore_min_max=False):
    super(CoeffVarResult, self).__init__()
    self.ignore_min_max = ignore_min_max

  def _ComputeFloat(self, cell, values, baseline_values):
    if self.ignore_min_max:
      values = _RemoveMinMax(cell, values)
    if statistics.mean(values) != 0.0:
      noise = abs(statistics.pstdev(values) / statistics.mean(values))
    else:
      noise = 0.0
    cell.value = noise


class ComparisonResult(Result):
  """Same or Different."""

  def NeedsBaseline(self):
    return True

  def _ComputeString(self, cell, values, baseline_values):
    value = None
    baseline_value = None
    if self._AllStringsSame(values):
      value = values[0]
    if self._AllStringsSame(baseline_values):
      baseline_value = baseline_values[0]
    if value is not None and baseline_value is not None:
      if value == baseline_value:
        cell.value = 'SAME'
      else:
        cell.value = 'DIFFERENT'
    else:
      cell.value = '?'


class PValueResult(ComparisonResult):
  """P-value."""

  def __init__(self, ignore_min_max=False):
    super(PValueResult, self).__init__()
    self.ignore_min_max = ignore_min_max

  def _ComputeFloat(self, cell, values, baseline_values):
    if self.ignore_min_max:
      values = _RemoveMinMax(cell, values)
      baseline_values = _RemoveMinMax(cell, baseline_values)
    if len(values) < 2 or len(baseline_values) < 2:
      cell.value = float('nan')
      return
    _, cell.value = scipy.stats.ttest_ind(values, baseline_values)

  def _ComputeString(self, cell, values, baseline_values):
    return float('nan')


class KeyAwareComparisonResult(ComparisonResult):
  """Automatic key aware comparison."""

  def _IsLowerBetter(self, key):
    # Units in histograms should include directions
    if 'smallerIsBetter' in key:
      return True
    if 'biggerIsBetter' in key:
      return False

    # For units in chartjson:
    # TODO(llozano): Trying to guess direction by looking at the name of the
    # test does not seem like a good idea. Test frameworks should provide this
    # info explicitly. I believe Telemetry has this info. Need to find it out.
    #
    # Below are some test names for which we are not sure what the
    # direction is.
    #
    # For these we dont know what the direction is. But, since we dont
    # specify anything, crosperf will assume higher is better:
    # --percent_impl_scrolled--percent_impl_scrolled--percent
    # --solid_color_tiles_analyzed--solid_color_tiles_analyzed--count
    # --total_image_cache_hit_count--total_image_cache_hit_count--count
    # --total_texture_upload_time_by_url
    #
    # About these we are doubtful but we made a guess:
    # --average_num_missing_tiles_by_url--*--units (low is good)
    # --experimental_mean_frame_time_by_url--*--units (low is good)
    # --experimental_median_frame_time_by_url--*--units (low is good)
    # --texture_upload_count--texture_upload_count--count (high is good)
    # --total_deferred_image_decode_count--count (low is good)
    # --total_tiles_analyzed--total_tiles_analyzed--count (high is good)
    lower_is_better_keys = [
        'milliseconds', 'ms_', 'seconds_', 'KB', 'rdbytes', 'wrbytes',
        'dropped_percent', '(ms)', '(seconds)', '--ms',
        '--average_num_missing_tiles', '--experimental_jank',
        '--experimental_mean_frame', '--experimental_median_frame_time',
        '--total_deferred_image_decode_count', '--seconds', 'samples', 'bytes'
    ]

    return any([l in key for l in lower_is_better_keys])

  def _InvertIfLowerIsBetter(self, cell):
    if self._IsLowerBetter(cell.name):
      if cell.value:
        cell.value = 1.0 / cell.value


class AmeanRatioResult(KeyAwareComparisonResult):
  """Ratio of arithmetic means of values vs. baseline values."""

  def __init__(self, ignore_min_max=False):
    super(AmeanRatioResult, self).__init__()
    self.ignore_min_max = ignore_min_max

  def _ComputeFloat(self, cell, values, baseline_values):
    if self.ignore_min_max:
      values = _RemoveMinMax(cell, values)
      baseline_values = _RemoveMinMax(cell, baseline_values)

    baseline_mean = statistics.mean(baseline_values)
    values_mean = statistics.mean(values)
    if baseline_mean != 0:
      cell.value = values_mean / baseline_mean
    elif values_mean != 0:
      cell.value = 0.00
      # cell.value = 0 means the values and baseline_values have big difference
    else:
      cell.value = 1.00
      # no difference if both values and baseline_values are 0


class GmeanRatioResult(KeyAwareComparisonResult):
  """Ratio of geometric means of values vs. baseline values."""

  def __init__(self, ignore_min_max=False):
    super(GmeanRatioResult, self).__init__()
    self.ignore_min_max = ignore_min_max

  def _ComputeFloat(self, cell, values, baseline_values):
    if self.ignore_min_max:
      values = _RemoveMinMax(cell, values)
      baseline_values = _RemoveMinMax(cell, baseline_values)
    if self._GetGmean(baseline_values) != 0:
      cell.value = self._GetGmean(values) / self._GetGmean(baseline_values)
    elif self._GetGmean(values) != 0:
      cell.value = 0.00
    else:
      cell.value = 1.00


class Color(object):
  """Class that represents color in RGBA format."""

  def __init__(self, r=0, g=0, b=0, a=0):
    self.r = r
    self.g = g
    self.b = b
    self.a = a

  def __str__(self):
    return 'r: %s g: %s: b: %s: a: %s' % (self.r, self.g, self.b, self.a)

  def Round(self):
    """Round RGBA values to the nearest integer."""
    self.r = int(self.r)
    self.g = int(self.g)
    self.b = int(self.b)
    self.a = int(self.a)

  def GetRGB(self):
    """Get a hex representation of the color."""
    return '%02x%02x%02x' % (self.r, self.g, self.b)

  @classmethod
  def Lerp(cls, ratio, a, b):
    """Perform linear interpolation between two colors.

    Args:
      ratio: The ratio to use for linear polation.
      a: The first color object (used when ratio is 0).
      b: The second color object (used when ratio is 1).

    Returns:
      Linearly interpolated color.
    """
    ret = cls()
    ret.r = (b.r - a.r) * ratio + a.r
    ret.g = (b.g - a.g) * ratio + a.g
    ret.b = (b.b - a.b) * ratio + a.b
    ret.a = (b.a - a.a) * ratio + a.a
    return ret


class Format(object):
  """A class that represents the format of a column."""

  def __init__(self):
    pass

  def Compute(self, cell):
    """Computes the attributes of a cell based on its value.

    Attributes typically are color, width, etc.

    Args:
      cell: The cell whose attributes are to be populated.
    """
    if cell.value is None:
      cell.string_value = ''
    if isinstance(cell.value, float):
      self._ComputeFloat(cell)
    else:
      self._ComputeString(cell)

  def _ComputeFloat(self, cell):
    cell.string_value = '{0:.2f}'.format(cell.value)

  def _ComputeString(self, cell):
    cell.string_value = str(cell.value)

  def _GetColor(self, value, low, mid, high, power=6, mid_value=1.0):
    min_value = 0.0
    max_value = 2.0
    if math.isnan(value):
      return mid
    if value > mid_value:
      value = max_value - mid_value / value

    return self._GetColorBetweenRange(value, min_value, mid_value, max_value,
                                      low, mid, high, power)

  def _GetColorBetweenRange(self, value, min_value, mid_value, max_value,
                            low_color, mid_color, high_color, power):
    assert value <= max_value
    assert value >= min_value
    if value > mid_value:
      value = (max_value - value) / (max_value - mid_value)
      value **= power
      ret = Color.Lerp(value, high_color, mid_color)
    else:
      value = (value - min_value) / (mid_value - min_value)
      value **= power
      ret = Color.Lerp(value, low_color, mid_color)
    ret.Round()
    return ret


class PValueFormat(Format):
  """Formatting for p-value."""

  def _ComputeFloat(self, cell):
    cell.string_value = '%0.2f' % float(cell.value)
    if float(cell.value) < 0.05:
      cell.bgcolor = self._GetColor(
          cell.value,
          Color(255, 255, 0, 0),
          Color(255, 255, 255, 0),
          Color(255, 255, 255, 0),
          mid_value=0.05,
          power=1)


class WeightFormat(Format):
  """Formatting for weight in cwp mode."""

  def _ComputeFloat(self, cell):
    cell.string_value = '%0.4f' % float(cell.value)


class StorageFormat(Format):
  """Format the cell as a storage number.

  Examples:
    If the cell contains a value of 1024, the string_value will be 1.0K.
  """

  def _ComputeFloat(self, cell):
    base = 1024
    suffices = ['K', 'M', 'G']
    v = float(cell.value)
    current = 0
    while v >= base**(current + 1) and current < len(suffices):
      current += 1

    if current:
      divisor = base**current
      cell.string_value = '%1.1f%s' % ((v / divisor), suffices[current - 1])
    else:
      cell.string_value = str(cell.value)


class CoeffVarFormat(Format):
  """Format the cell as a percent.

  Examples:
    If the cell contains a value of 1.5, the string_value will be +150%.
  """

  def _ComputeFloat(self, cell):
    cell.string_value = '%1.1f%%' % (float(cell.value) * 100)
    cell.color = self._GetColor(
        cell.value,
        Color(0, 255, 0, 0),
        Color(0, 0, 0, 0),
        Color(255, 0, 0, 0),
        mid_value=0.02,
        power=1)


class PercentFormat(Format):
  """Format the cell as a percent.

  Examples:
    If the cell contains a value of 1.5, the string_value will be +50%.
  """

  def _ComputeFloat(self, cell):
    cell.string_value = '%+1.1f%%' % ((float(cell.value) - 1) * 100)
    cell.color = self._GetColor(cell.value, Color(255, 0, 0, 0),
                                Color(0, 0, 0, 0), Color(0, 255, 0, 0))


class RatioFormat(Format):
  """Format the cell as a ratio.

  Examples:
    If the cell contains a value of 1.5642, the string_value will be 1.56.
  """

  def _ComputeFloat(self, cell):
    cell.string_value = '%+1.1f%%' % ((cell.value - 1) * 100)
    cell.color = self._GetColor(cell.value, Color(255, 0, 0, 0),
                                Color(0, 0, 0, 0), Color(0, 255, 0, 0))


class ColorBoxFormat(Format):
  """Format the cell as a color box.

  Examples:
    If the cell contains a value of 1.5, it will get a green color.
    If the cell contains a value of 0.5, it will get a red color.
    The intensity of the green/red will be determined by how much above or below
    1.0 the value is.
  """

  def _ComputeFloat(self, cell):
    cell.string_value = '--'
    bgcolor = self._GetColor(cell.value, Color(255, 0, 0, 0),
                             Color(255, 255, 255, 0), Color(0, 255, 0, 0))
    cell.bgcolor = bgcolor
    cell.color = bgcolor


class Cell(object):
  """A class to represent a cell in a table.

  Attributes:
    value: The raw value of the cell.
    color: The color of the cell.
    bgcolor: The background color of the cell.
    string_value: The string value of the cell.
    suffix: A string suffix to be attached to the value when displaying.
    prefix: A string prefix to be attached to the value when displaying.
    color_row: Indicates whether the whole row is to inherit this cell's color.
    bgcolor_row: Indicates whether the whole row is to inherit this cell's
    bgcolor.
    width: Optional specifier to make a column narrower than the usual width.
    The usual width of a column is the max of all its cells widths.
    colspan: Set the colspan of the cell in the HTML table, this is used for
    table headers. Default value is 1.
    name: the test name of the cell.
    header: Whether this is a header in html.
  """

  def __init__(self):
    self.value = None
    self.color = None
    self.bgcolor = None
    self.string_value = None
    self.suffix = None
    self.prefix = None
    # Entire row inherits this color.
    self.color_row = False
    self.bgcolor_row = False
    self.width = 0
    self.colspan = 1
    self.name = None
    self.header = False

  def __str__(self):
    l = []
    l.append('value: %s' % self.value)
    l.append('string_value: %s' % self.string_value)
    return ' '.join(l)


class Column(object):
  """Class representing a column in a table.

  Attributes:
    result: an object of the Result class.
    fmt: an object of the Format class.
  """

  def __init__(self, result, fmt, name=''):
    self.result = result
    self.fmt = fmt
    self.name = name


# Takes in:
# ["Key", "Label1", "Label2"]
# ["k", ["v", "v2"], [v3]]
# etc.
# Also takes in a format string.
# Returns a table like:
# ["Key", "Label1", "Label2"]
# ["k", avg("v", "v2"), stddev("v", "v2"), etc.]]
# according to format string
class TableFormatter(object):
  """Class to convert a plain table into a cell-table.

  This class takes in a table generated by TableGenerator and a list of column
  formats to apply to the table and returns a table of cells.
  """

  def __init__(self, table, columns, samples_table=False):
    """The constructor takes in a table and a list of columns.

    Args:
      table: A list of lists of values.
      columns: A list of column containing what to produce and how to format
               it.
      samples_table: A flag to check whether we are generating a table of
                     samples in CWP apporximation mode.
    """
    self._table = table
    self._columns = columns
    self._samples_table = samples_table
    self._table_columns = []
    self._out_table = []

  def GenerateCellTable(self, table_type):
    row_index = 0
    all_failed = False

    for row in self._table[1:]:
      # If we are generating samples_table, the second value will be weight
      # rather than values.
      start_col = 2 if self._samples_table else 1
      # It does not make sense to put retval in the summary table.
      if str(row[0]) == 'retval' and table_type == 'summary':
        # Check to see if any runs passed, and update all_failed.
        all_failed = True
        for values in row[start_col:]:
          if 0 in values:
            all_failed = False
        continue
      key = Cell()
      key.string_value = str(row[0])
      out_row = [key]
      if self._samples_table:
        # Add one column for weight if in samples_table mode
        weight = Cell()
        weight.value = row[1]
        f = WeightFormat()
        f.Compute(weight)
        out_row.append(weight)
      baseline = None
      for results in row[start_col:]:
        column_start = 0
        values = None
        # If generating sample table, we will split a tuple of iterations info
        # from the results
        if isinstance(results, tuple):
          it, values = results
          column_start = 1
          cell = Cell()
          cell.string_value = '[%d: %d]' % (it[0], it[1])
          out_row.append(cell)
          if not row_index:
            self._table_columns.append(self._columns[0])
        else:
          values = results
        # Parse each column
        for column in self._columns[column_start:]:
          cell = Cell()
          cell.name = key.string_value
          if not column.result.NeedsBaseline() or baseline is not None:
            column.result.Compute(cell, values, baseline)
            column.fmt.Compute(cell)
            out_row.append(cell)
            if not row_index:
              self._table_columns.append(column)

        if baseline is None:
          baseline = values
      self._out_table.append(out_row)
      row_index += 1

    # If this is a summary table, and the only row in it is 'retval', and
    # all the test runs failed, we need to a 'Results' row to the output
    # table.
    if table_type == 'summary' and all_failed and len(self._table) == 2:
      labels_row = self._table[0]
      key = Cell()
      key.string_value = 'Results'
      out_row = [key]
      baseline = None
      for _ in labels_row[1:]:
        for column in self._columns:
          cell = Cell()
          cell.name = key.string_value
          column.result.Compute(cell, ['Fail'], baseline)
          column.fmt.Compute(cell)
          out_row.append(cell)
          if not row_index:
            self._table_columns.append(column)
      self._out_table.append(out_row)

  def AddColumnName(self):
    """Generate Column name at the top of table."""
    key = Cell()
    key.header = True
    key.string_value = 'Keys' if not self._samples_table else 'Benchmarks'
    header = [key]
    if self._samples_table:
      weight = Cell()
      weight.header = True
      weight.string_value = 'Weights'
      header.append(weight)
    for column in self._table_columns:
      cell = Cell()
      cell.header = True
      if column.name:
        cell.string_value = column.name
      else:
        result_name = column.result.__class__.__name__
        format_name = column.fmt.__class__.__name__

        cell.string_value = '%s %s' % (
            result_name.replace('Result', ''),
            format_name.replace('Format', ''),
        )

      header.append(cell)

    self._out_table = [header] + self._out_table

  def AddHeader(self, s):
    """Put additional string on the top of the table."""
    cell = Cell()
    cell.header = True
    cell.string_value = str(s)
    header = [cell]
    colspan = max(1, max(len(row) for row in self._table))
    cell.colspan = colspan
    self._out_table = [header] + self._out_table

  def GetPassesAndFails(self, values):
    passes = 0
    fails = 0
    for val in values:
      if val == 0:
        passes = passes + 1
      else:
        fails = fails + 1
    return passes, fails

  def AddLabelName(self):
    """Put label on the top of the table."""
    top_header = []
    base_colspan = len(
        [c for c in self._columns if not c.result.NeedsBaseline()])
    compare_colspan = len(self._columns)
    # Find the row with the key 'retval', if it exists.  This
    # will be used to calculate the number of iterations that passed and
    # failed for each image label.
    retval_row = None
    for row in self._table:
      if row[0] == 'retval':
        retval_row = row
    # The label is organized as follows
    # "keys" label_base, label_comparison1, label_comparison2
    # The first cell has colspan 1, the second is base_colspan
    # The others are compare_colspan
    column_position = 0
    for label in self._table[0]:
      cell = Cell()
      cell.header = True
      # Put the number of pass/fail iterations in the image label header.
      if column_position > 0 and retval_row:
        retval_values = retval_row[column_position]
        if isinstance(retval_values, list):
          passes, fails = self.GetPassesAndFails(retval_values)
          cell.string_value = str(label) + '  (pass:%d fail:%d)' % (passes,
                                                                    fails)
        else:
          cell.string_value = str(label)
      else:
        cell.string_value = str(label)
      if top_header:
        if not self._samples_table or (self._samples_table and
                                       len(top_header) == 2):
          cell.colspan = base_colspan
      if len(top_header) > 1:
        if not self._samples_table or (self._samples_table and
                                       len(top_header) > 2):
          cell.colspan = compare_colspan
      top_header.append(cell)
      column_position = column_position + 1
    self._out_table = [top_header] + self._out_table

  def _PrintOutTable(self):
    o = ''
    for row in self._out_table:
      for cell in row:
        o += str(cell) + ' '
      o += '\n'
    print(o)

  def GetCellTable(self, table_type='full', headers=True):
    """Function to return a table of cells.

    The table (list of lists) is converted into a table of cells by this
    function.

    Args:
      table_type: Can be 'full' or 'summary'
      headers: A boolean saying whether we want default headers

    Returns:
      A table of cells with each cell having the properties and string values as
      requiested by the columns passed in the constructor.
    """
    # Generate the cell table, creating a list of dynamic columns on the fly.
    if not self._out_table:
      self.GenerateCellTable(table_type)
    if headers:
      self.AddColumnName()
      self.AddLabelName()
    return self._out_table


class TablePrinter(object):
  """Class to print a cell table to the console, file or html."""
  PLAIN = 0
  CONSOLE = 1
  HTML = 2
  TSV = 3
  EMAIL = 4

  def __init__(self, table, output_type):
    """Constructor that stores the cell table and output type."""
    self._table = table
    self._output_type = output_type
    self._row_styles = []
    self._column_styles = []

  # Compute whole-table properties like max-size, etc.
  def _ComputeStyle(self):
    self._row_styles = []
    for row in self._table:
      row_style = Cell()
      for cell in row:
        if cell.color_row:
          assert cell.color, 'Cell color not set but color_row set!'
          assert not row_style.color, 'Multiple row_style.colors found!'
          row_style.color = cell.color
        if cell.bgcolor_row:
          assert cell.bgcolor, 'Cell bgcolor not set but bgcolor_row set!'
          assert not row_style.bgcolor, 'Multiple row_style.bgcolors found!'
          row_style.bgcolor = cell.bgcolor
      self._row_styles.append(row_style)

    self._column_styles = []
    if len(self._table) < 2:
      return

    for i in range(max(len(row) for row in self._table)):
      column_style = Cell()
      for row in self._table:
        if not any([cell.colspan != 1 for cell in row]):
          column_style.width = max(column_style.width, len(row[i].string_value))
      self._column_styles.append(column_style)

  def _GetBGColorFix(self, color):
    if self._output_type == self.CONSOLE:
      prefix = misc.rgb2short(color.r, color.g, color.b)
      # pylint: disable=anomalous-backslash-in-string
      prefix = '\033[48;5;%sm' % prefix
      suffix = '\033[0m'
    elif self._output_type in [self.EMAIL, self.HTML]:
      rgb = color.GetRGB()
      prefix = ('<FONT style="BACKGROUND-COLOR:#{0}">'.format(rgb))
      suffix = '</FONT>'
    elif self._output_type in [self.PLAIN, self.TSV]:
      prefix = ''
      suffix = ''
    return prefix, suffix

  def _GetColorFix(self, color):
    if self._output_type == self.CONSOLE:
      prefix = misc.rgb2short(color.r, color.g, color.b)
      # pylint: disable=anomalous-backslash-in-string
      prefix = '\033[38;5;%sm' % prefix
      suffix = '\033[0m'
    elif self._output_type in [self.EMAIL, self.HTML]:
      rgb = color.GetRGB()
      prefix = '<FONT COLOR=#{0}>'.format(rgb)
      suffix = '</FONT>'
    elif self._output_type in [self.PLAIN, self.TSV]:
      prefix = ''
      suffix = ''
    return prefix, suffix

  def Print(self):
    """Print the table to a console, html, etc.

    Returns:
      A string that contains the desired representation of the table.
    """
    self._ComputeStyle()
    return self._GetStringValue()

  def _GetCellValue(self, i, j):
    cell = self._table[i][j]
    out = cell.string_value
    raw_width = len(out)

    if cell.color:
      p, s = self._GetColorFix(cell.color)
      out = '%s%s%s' % (p, out, s)

    if cell.bgcolor:
      p, s = self._GetBGColorFix(cell.bgcolor)
      out = '%s%s%s' % (p, out, s)

    if self._output_type in [self.PLAIN, self.CONSOLE, self.EMAIL]:
      if cell.width:
        width = cell.width
      else:
        if self._column_styles:
          width = self._column_styles[j].width
        else:
          width = len(cell.string_value)
      if cell.colspan > 1:
        width = 0
        start = 0
        for k in range(j):
          start += self._table[i][k].colspan
        for k in range(cell.colspan):
          width += self._column_styles[start + k].width
      if width > raw_width:
        padding = ('%' + str(width - raw_width) + 's') % ''
        out = padding + out

    if self._output_type == self.HTML:
      if cell.header:
        tag = 'th'
      else:
        tag = 'td'
      out = '<{0} colspan = "{2}"> {1} </{0}>'.format(tag, out, cell.colspan)

    return out

  def _GetHorizontalSeparator(self):
    if self._output_type in [self.CONSOLE, self.PLAIN, self.EMAIL]:
      return ' '
    if self._output_type == self.HTML:
      return ''
    if self._output_type == self.TSV:
      return '\t'

  def _GetVerticalSeparator(self):
    if self._output_type in [self.PLAIN, self.CONSOLE, self.TSV, self.EMAIL]:
      return '\n'
    if self._output_type == self.HTML:
      return '</tr>\n<tr>'

  def _GetPrefix(self):
    if self._output_type in [self.PLAIN, self.CONSOLE, self.TSV, self.EMAIL]:
      return ''
    if self._output_type == self.HTML:
      return '<p></p><table id="box-table-a">\n<tr>'

  def _GetSuffix(self):
    if self._output_type in [self.PLAIN, self.CONSOLE, self.TSV, self.EMAIL]:
      return ''
    if self._output_type == self.HTML:
      return '</tr>\n</table>'

  def _GetStringValue(self):
    o = ''
    o += self._GetPrefix()
    for i in range(len(self._table)):
      row = self._table[i]
      # Apply row color and bgcolor.
      p = s = bgp = bgs = ''
      if self._row_styles[i].bgcolor:
        bgp, bgs = self._GetBGColorFix(self._row_styles[i].bgcolor)
      if self._row_styles[i].color:
        p, s = self._GetColorFix(self._row_styles[i].color)
      o += p + bgp
      for j in range(len(row)):
        out = self._GetCellValue(i, j)
        o += out + self._GetHorizontalSeparator()
      o += s + bgs
      o += self._GetVerticalSeparator()
    o += self._GetSuffix()
    return o


# Some common drivers
def GetSimpleTable(table, out_to=TablePrinter.CONSOLE):
  """Prints a simple table.

  This is used by code that has a very simple list-of-lists and wants to
  produce a table with ameans, a percentage ratio of ameans and a colorbox.

  Examples:
    GetSimpleConsoleTable([["binary", "b1", "b2"],["size", "300", "400"]])
    will produce a colored table that can be printed to the console.

  Args:
    table: a list of lists.
    out_to: specify the fomat of output. Currently it supports HTML and CONSOLE.

  Returns:
    A string version of the table that can be printed to the console.
  """
  columns = [
      Column(AmeanResult(), Format()),
      Column(AmeanRatioResult(), PercentFormat()),
      Column(AmeanRatioResult(), ColorBoxFormat()),
  ]
  our_table = [table[0]]
  for row in table[1:]:
    our_row = [row[0]]
    for v in row[1:]:
      our_row.append([v])
    our_table.append(our_row)

  tf = TableFormatter(our_table, columns)
  cell_table = tf.GetCellTable()
  tp = TablePrinter(cell_table, out_to)
  return tp.Print()


# pylint: disable=redefined-outer-name
def GetComplexTable(runs, labels, out_to=TablePrinter.CONSOLE):
  """Prints a complex table.

  This can be used to generate a table with arithmetic mean, standard deviation,
  coefficient of variation, p-values, etc.

  Args:
    runs: A list of lists with data to tabulate.
    labels: A list of labels that correspond to the runs.
    out_to: specifies the format of the table (example CONSOLE or HTML).

  Returns:
    A string table that can be printed to the console or put in an HTML file.
  """
  tg = TableGenerator(runs, labels, TableGenerator.SORT_BY_VALUES_DESC)
  table = tg.GetTable()
  columns = [
      Column(LiteralResult(), Format(), 'Literal'),
      Column(AmeanResult(), Format()),
      Column(StdResult(), Format()),
      Column(CoeffVarResult(), CoeffVarFormat()),
      Column(NonEmptyCountResult(), Format()),
      Column(AmeanRatioResult(), PercentFormat()),
      Column(AmeanRatioResult(), RatioFormat()),
      Column(GmeanRatioResult(), RatioFormat()),
      Column(PValueResult(), PValueFormat())
  ]
  tf = TableFormatter(table, columns)
  cell_table = tf.GetCellTable()
  tp = TablePrinter(cell_table, out_to)
  return tp.Print()


if __name__ == '__main__':
  # Run a few small tests here.
  run1 = {
      'k1': '10',
      'k2': '12',
      'k5': '40',
      'k6': '40',
      'ms_1': '20',
      'k7': 'FAIL',
      'k8': 'PASS',
      'k9': 'PASS',
      'k10': '0'
  }
  run2 = {
      'k1': '13',
      'k2': '14',
      'k3': '15',
      'ms_1': '10',
      'k8': 'PASS',
      'k9': 'FAIL',
      'k10': '0'
  }
  run3 = {
      'k1': '50',
      'k2': '51',
      'k3': '52',
      'k4': '53',
      'k5': '35',
      'k6': '45',
      'ms_1': '200',
      'ms_2': '20',
      'k7': 'FAIL',
      'k8': 'PASS',
      'k9': 'PASS'
  }
  runs = [[run1, run2], [run3]]
  labels = ['vanilla', 'modified']
  t = GetComplexTable(runs, labels, TablePrinter.CONSOLE)
  print(t)
  email = GetComplexTable(runs, labels, TablePrinter.EMAIL)

  runs = [[{
      'k1': '1'
  }, {
      'k1': '1.1'
  }, {
      'k1': '1.2'
  }], [{
      'k1': '5'
  }, {
      'k1': '5.1'
  }, {
      'k1': '5.2'
  }]]
  t = GetComplexTable(runs, labels, TablePrinter.CONSOLE)
  print(t)

  simple_table = [
      ['binary', 'b1', 'b2', 'b3'],
      ['size', 100, 105, 108],
      ['rodata', 100, 80, 70],
      ['data', 100, 100, 100],
      ['debug', 100, 140, 60],
  ]
  t = GetSimpleTable(simple_table)
  print(t)
  email += GetSimpleTable(simple_table, TablePrinter.HTML)
  email_to = [getpass.getuser()]
  email = "<pre style='font-size: 13px'>%s</pre>" % email
  EmailSender().SendEmail(email_to, 'SimpleTableTest', email, msg_type='html')