text: // @flow
  
  const UnitBezier = require('@mapbox/unitbezier');
  const interpolate = require('../../util/interpolate');
  const { toString, NumberType } = require('../types');
  const { Color } = require('../values');
  
  import type { Expression } from '../expression';
  import type ParsingContext from '../parsing_context';
  import type EvaluationContext from '../evaluation_context';
  import type { Type } from '../types';
  
  export type InterpolationType =
      { name: 'step' } |
      { name: 'linear' } |
      { name: 'exponential', base: number } |
      { name: 'cubic-bezier', controlPoints: [number, number, number, number] };
  
  type Stops = Array<[number, Expression]>;
  
  class Curve implements Expression {
      key: string;
      type: Type;
  
      interpolation: InterpolationType;
      input: Expression;
      labels: Array<number>;
      outputs: Array<Expression>;
  
      constructor(key: string, type: Type, interpolation: InterpolationType, input: Expression, stops: Stops) {
          this.key = key;
          this.type = type;
          this.interpolation = interpolation;
          this.input = input;
  
          this.labels = [];
          this.outputs = [];
          for (const [label, expression] of stops) {
              this.labels.push(label);
              this.outputs.push(expression);
          }
      }
  
      static interpolationFactor(interpolation: InterpolationType, input: number, lower: number, upper: number) {
          let t = 0;
          if (interpolation.name === 'exponential') {
              t = exponentialInterpolation(input, interpolation.base, lower, upper);
          } else if (interpolation.name === 'linear') {
              t = exponentialInterpolation(input, 1, lower, upper);
          } else if (interpolation.name === 'cubic-bezier') {
              const c = interpolation.controlPoints;
              const ub = new UnitBezier(c[0], c[1], c[2], c[3]);
              t = ub.solve(exponentialInterpolation(input, 1, lower, upper));
          }
          return t;
      }
  
      static parse(args: Array<mixed>, context: ParsingContext) {
          let [ , interpolation, input, ...rest] = args;
  
          if (!Array.isArray(interpolation) || interpolation.length === 0) {
              return context.error(`Expected an interpolation type expression.`, 1);
          }
  
          if (interpolation[0] === 'step') {
              interpolation = { name: 'step' };
          } else if (interpolation[0] === 'linear') {
              interpolation = { name: 'linear' };
          } else if (interpolation[0] === 'exponential') {
              const base = interpolation[1];
              if (typeof base !== 'number')
                  return context.error(`Exponential interpolation requires a numeric base.`, 1, 1);
              interpolation = {
                  name: 'exponential',
                  base
              };
          } else if (interpolation[0] === 'cubic-bezier') {
              const controlPoints = interpolation.slice(1);
              if (
                  controlPoints.length !== 4 ||
                  controlPoints.some(t => typeof t !== 'number' || t < 0 || t > 1)
              ) {
                  return context.error('Cubic bezier interpolation requires four numeric arguments with values between 0 and 1.', 1);
              }
  
              interpolation = {
                  name: 'cubic-bezier',
                  controlPoints: (controlPoints: any)
              };
          } else {
              return context.error(`Unknown interpolation type ${String(interpolation[0])}`, 1, 0);
          }
  
          const isStep = interpolation.name === 'step';
  
          const minArgs = isStep ? 5 : 4;
          if (args.length - 1 < minArgs)
              return context.error(`Expected at least ${minArgs} arguments, but found only ${args.length - 1}.`);
  
          const parity = minArgs % 2;
          if ((args.length - 1) % 2 !== parity) {
              return context.error(`Expected an ${parity === 0 ? 'even' : 'odd'} number of arguments.`);
          }
  
          input = context.parse(input, 2, NumberType);
          if (!input) return null;
  
          const stops: Stops = [];
  
          let outputType: Type = (null: any);
          if (context.expectedType && context.expectedType.kind !== 'value') {
              outputType = context.expectedType;
          }
  
          if (isStep) {
              rest.unshift(-Infinity);
          }
  
          for (let i = 0; i < rest.length; i += 2) {
              const label = rest[i];
              const value = rest[i + 1];
  
              const labelKey = isStep ? i + 2 : i + 3;
              const valueKey = isStep ? i + 3 : i + 4;
  
              if (typeof label !== 'number') {
                  return context.error('Input/output pairs for "curve" expressions must be defined using literal numeric values (not computed expressions) for the input values.', labelKey);
              }
  
              if (stops.length && stops[stops.length - 1][0] > label) {
                  return context.error('Input/output pairs for "curve" expressions must be arranged with input values in strictly ascending order.', labelKey);
              }
  
              const parsed = context.parse(value, valueKey, outputType);
              if (!parsed) return null;
              outputType = outputType || parsed.type;
              stops.push([label, parsed]);
          }
  
          if (interpolation.name !== 'step' &&
              outputType.kind !== 'number' &&
              outputType.kind !== 'color' &&
              !(
                  outputType.kind === 'array' &&
                  outputType.itemType.kind === 'number' &&
                  typeof outputType.N === 'number'
              )
          ) {
              return context.error(`Type ${toString(outputType)} is not interpolatable, and thus cannot be used as a ${interpolation.name} curve's output type.`);
          }
  
          return new Curve(context.key, outputType, interpolation, input, stops);
      }
  
      evaluate(ctx: EvaluationContext) {
          const labels = this.labels;
          const outputs = this.outputs;
  
          if (labels.length === 1) {
              return outputs[0].evaluate(ctx);
          }
  
          const value = ((this.input.evaluate(ctx): any): number);
          if (value <= labels[0]) {
              return outputs[0].evaluate(ctx);
          }
  
          const stopCount = labels.length;
          if (value >= labels[stopCount - 1]) {
              return outputs[stopCount - 1].evaluate(ctx);
          }
  
          const index = findStopLessThanOrEqualTo(labels, value);
          if (this.interpolation.name === 'step') {
              return outputs[index].evaluate(ctx);
          }
  
          const lower = labels[index];
          const upper = labels[index + 1];
          const t = Curve.interpolationFactor(this.interpolation, value, lower, upper);
  
          const outputLower = outputs[index].evaluate(ctx);
          const outputUpper = outputs[index + 1].evaluate(ctx);
  
          const type = this.type.kind.toLowerCase();
          if (type === 'color') {
              return new Color(...interpolate.color((outputLower: any).value, (outputUpper: any).value, t));
          }
  
          return interpolate[type](outputLower, outputUpper, t);
      }
  
      eachChild(fn: (Expression) => void) {
          fn(this.input);
          for (const expression of this.outputs) {
              fn(expression);
          }
      }
  }
  
  /**
   * Returns a ratio that can be used to interpolate between exponential function
   * stops.
   * How it works: Two consecutive stop values define a (scaled and shifted) exponential function `f(x) = a * base^x + b`, where `base` is the user-specified base,
   * and `a` and `b` are constants affording sufficient degrees of freedom to fit
   * the function to the given stops.
   *
   * Here's a bit of algebra that lets us compute `f(x)` directly from the stop
   * values without explicitly solving for `a` and `b`:
   *
   * First stop value: `f(x0) = y0 = a * base^x0 + b`
   * Second stop value: `f(x1) = y1 = a * base^x1 + b`
   * => `y1 - y0 = a(base^x1 - base^x0)`
   * => `a = (y1 - y0)/(base^x1 - base^x0)`
   *
   * Desired value: `f(x) = y = a * base^x + b`
   * => `f(x) = y0 + a * (base^x - base^x0)`
   *
   * From the above, we can replace the `a` in `a * (base^x - base^x0)` and do a
   * little algebra:
   * ```
   * a * (base^x - base^x0) = (y1 - y0)/(base^x1 - base^x0) * (base^x - base^x0)
   *                     = (y1 - y0) * (base^x - base^x0) / (base^x1 - base^x0)
   * ```
   *
   * If we let `(base^x - base^x0) / (base^x1 base^x0)`, then we have
   * `f(x) = y0 + (y1 - y0) * ratio`.  In other words, `ratio` may be treated as
   * an interpolation factor between the two stops' output values.
   *
   * (Note: a slightly different form for `ratio`,
   * `(base^(x-x0) - 1) / (base^(x1-x0) - 1) `, is equivalent, but requires fewer
   * expensive `Math.pow()` operations.)
   *
   * @private
  */
  function exponentialInterpolation(input, base, lowerValue, upperValue) {
      const difference = upperValue - lowerValue;
      const progress = input - lowerValue;
  
      if (difference === 0) {
          return 0;
      } else if (base === 1) {
          return progress / difference;
      } else {
          return (Math.pow(base, progress) - 1) / (Math.pow(base, difference) - 1);
      }
  }
  
  module.exports = Curve;
  
  /**
   * Returns the index of the last stop <= input, or 0 if it doesn't exist.
   * @private
   */
  function findStopLessThanOrEqualTo(stops, input) {
      const n = stops.length;
      let lowerIndex = 0;
      let upperIndex = n - 1;
      let currentIndex = 0;
      let currentValue, upperValue;
  
      while (lowerIndex <= upperIndex) {
          currentIndex = Math.floor((lowerIndex + upperIndex) / 2);
          currentValue = stops[currentIndex];
          upperValue = stops[currentIndex + 1];
          if (input === currentValue || input > currentValue && input < upperValue) { // Search complete
              return currentIndex;
          } else if (currentValue < input) {
              lowerIndex = currentIndex + 1;
          } else if (currentValue > input) {
              upperIndex = currentIndex - 1;
          }
      }
  
      return Math.max(currentIndex - 1, 0);
  }
  