/*
 * Copyright 2012 ZXing authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#import "ZXIntArray.h"
#import "ZXModulusGF.h"
#import "ZXModulusPoly.h"

@interface ZXModulusPoly ()

@property (nonatomic, strong, readonly) ZXIntArray *coefficients;
@property (nonatomic, weak, readonly) ZXModulusGF *field;

@end

@implementation ZXModulusPoly

- (id)initWithField:(ZXModulusGF *)field coefficients:(ZXIntArray *)coefficients {
  if (self = [super init]) {
    if (coefficients.length == 0) {
      @throw [NSException exceptionWithName:@"IllegalArgumentException"
                                     reason:@"coefficients must have at least one element"
                                   userInfo:nil];
    }
    _field = field;
    int coefficientsLength = coefficients.length;
    if (coefficientsLength > 1 && coefficients.array[0] == 0) {
      // Leading term must be non-zero for anything except the constant polynomial "0"
      int firstNonZero = 1;
      while (firstNonZero < coefficientsLength && coefficients.array[firstNonZero] == 0) {
        firstNonZero++;
      }
      if (firstNonZero == coefficientsLength) {
        _coefficients = [[ZXIntArray alloc] initWithLength:1];
      } else {
        _coefficients = [[ZXIntArray alloc] initWithLength:coefficientsLength - firstNonZero];
        for (int i = 0; i < _coefficients.length; i++) {
          _coefficients.array[i] = coefficients.array[firstNonZero + i];
        }
      }
    } else {
      _coefficients = coefficients;
    }
  }

  return self;
}

/**
 * @return degree of this polynomial
 */
- (int)degree {
  return self.coefficients.length - 1;
}

/**
 * @return true iff this polynomial is the monomial "0"
 */
- (BOOL)zero {
  return self.coefficients.array[0] == 0;
}

/**
 * @return coefficient of x^degree term in this polynomial
 */
- (int)coefficient:(int)degree {
  return self.coefficients.array[self.coefficients.length - 1 - degree];
}

/**
 * @return evaluation of this polynomial at a given point
 */
- (int)evaluateAt:(int)a {
  if (a == 0) {
    return [self coefficient:0];
  }
  int size = self.coefficients.length;
  if (a == 1) {
    // Just the sum of the coefficients
    int result = 0;
    for (int i = 0; i < size; i++) {
      result = [self.field add:result b:self.coefficients.array[i]];
    }
    return result;
  }
  int result = self.coefficients.array[0];
  for (int i = 1; i < size; i++) {
    result = [self.field add:[self.field multiply:a b:result] b:self.coefficients.array[i]];
  }
  return result;
}

- (ZXModulusPoly *)add:(ZXModulusPoly *)other {
  if (![self.field isEqual:other.field]) {
    [NSException raise:NSInvalidArgumentException format:@"ZXModulusPolys do not have same ZXModulusGF field"];
  }
  if (self.zero) {
    return other;
  }
  if (other.zero) {
    return self;
  }

  ZXIntArray *smallerCoefficients = self.coefficients;
  ZXIntArray *largerCoefficients = other.coefficients;
  if (smallerCoefficients.length > largerCoefficients.length) {
    ZXIntArray *temp = smallerCoefficients;
    smallerCoefficients = largerCoefficients;
    largerCoefficients = temp;
  }
  ZXIntArray *sumDiff = [[ZXIntArray alloc] initWithLength:largerCoefficients.length];
  int lengthDiff = largerCoefficients.length - smallerCoefficients.length;
  // Copy high-order terms only found in higher-degree polynomial's coefficients
  memcpy(sumDiff.array, largerCoefficients.array, lengthDiff * sizeof(int32_t));

  for (int i = lengthDiff; i < largerCoefficients.length; i++) {
    sumDiff.array[i] = [self.field add:smallerCoefficients.array[i - lengthDiff] b:largerCoefficients.array[i]];
  }

  return [[ZXModulusPoly alloc] initWithField:self.field coefficients:sumDiff];
}

- (ZXModulusPoly *)subtract:(ZXModulusPoly *)other {
  if (![self.field isEqual:other.field]) {
    [NSException raise:NSInvalidArgumentException format:@"ZXModulusPolys do not have same ZXModulusGF field"];
  }
  if (self.zero) {
    return self;
  }
  return [self add:[other negative]];
}

- (ZXModulusPoly *)multiply:(ZXModulusPoly *)other {
  if (![self.field isEqual:other.field]) {
    [NSException raise:NSInvalidArgumentException format:@"ZXModulusPolys do not have same ZXModulusGF field"];
  }
  if (self.zero || other.zero) {
    return self.field.zero;
  }
  ZXIntArray *aCoefficients = self.coefficients;
  int aLength = aCoefficients.length;
  ZXIntArray *bCoefficients = other.coefficients;
  int bLength = bCoefficients.length;
  ZXIntArray *product = [[ZXIntArray alloc] initWithLength:aLength + bLength - 1];
  for (int i = 0; i < aLength; i++) {
    int aCoeff = aCoefficients.array[i];
    for (int j = 0; j < bLength; j++) {
      product.array[i + j] = [self.field add:product.array[i + j]
                                     b:[self.field multiply:aCoeff b:bCoefficients.array[j]]];
    }
  }
  return [[ZXModulusPoly alloc] initWithField:self.field coefficients:product];
}

- (ZXModulusPoly *)negative {
  int size = self.coefficients.length;
  ZXIntArray *negativeCoefficients = [[ZXIntArray alloc] initWithLength:size];
  for (int i = 0; i < size; i++) {
    negativeCoefficients.array[i] = [self.field subtract:0 b:self.coefficients.array[i]];
  }
  return [[ZXModulusPoly alloc] initWithField:self.field coefficients:negativeCoefficients];
}

- (ZXModulusPoly *)multiplyScalar:(int)scalar {
  if (scalar == 0) {
    return self.field.zero;
  }
  if (scalar == 1) {
    return self;
  }
  int size = self.coefficients.length;
  ZXIntArray *product = [[ZXIntArray alloc] initWithLength:size];
  for (int i = 0; i < size; i++) {
    product.array[i] = [self.field multiply:self.coefficients.array[i] b:scalar];
  }
  return [[ZXModulusPoly alloc] initWithField:self.field coefficients:product];
}

- (ZXModulusPoly *)multiplyByMonomial:(int)degree coefficient:(int)coefficient {
  if (degree < 0) {
    [NSException raise:NSInvalidArgumentException format:@"Degree must be greater than 0."];
  }
  if (coefficient == 0) {
    return self.field.zero;
  }
  int size = self.coefficients.length;
  ZXIntArray *product = [[ZXIntArray alloc] initWithLength:size + degree];
  for (int i = 0; i < size; i++) {
    product.array[i] = [self.field multiply:self.coefficients.array[i] b:coefficient];
  }

  return [[ZXModulusPoly alloc] initWithField:self.field coefficients:product];
}

- (NSArray *)divide:(ZXModulusPoly *)other {
  if (![self.field isEqual:other.field]) {
    [NSException raise:NSInvalidArgumentException format:@"ZXModulusPolys do not have same ZXModulusGF field"];
  }
  if (other.zero) {
    [NSException raise:NSInvalidArgumentException format:@"Divide by 0"];
  }

  ZXModulusPoly *quotient = self.field.zero;
  ZXModulusPoly *remainder = self;

  int denominatorLeadingTerm = [other coefficient:other.degree];
  int inverseDenominatorLeadingTerm = [self.field inverse:denominatorLeadingTerm];

  while ([remainder degree] >= other.degree && !remainder.zero) {
    int degreeDifference = remainder.degree - other.degree;
    int scale = [self.field multiply:[remainder coefficient:remainder.degree] b:inverseDenominatorLeadingTerm];
    ZXModulusPoly *term = [other multiplyByMonomial:degreeDifference coefficient:scale];
    ZXModulusPoly *iterationQuotient = [self.field buildMonomial:degreeDifference coefficient:scale];
    quotient = [quotient add:iterationQuotient];
    remainder = [remainder subtract:term];
  }

  return @[quotient, remainder];
}

- (NSString *)description {
  NSMutableString *result = [NSMutableString stringWithCapacity:8 * [self degree]];
  for (int degree = [self degree]; degree >= 0; degree--) {
    int coefficient = [self coefficient:degree];
    if (coefficient != 0) {
      if (coefficient < 0) {
        [result appendString:@" - "];
        coefficient = -coefficient;
      } else {
        if ([result length] > 0) {
          [result appendString:@" + "];
        }
      }
      if (degree == 0 || coefficient != 1) {
        [result appendFormat:@"%d", coefficient];
      }
      if (degree != 0) {
        if (degree == 1) {
          [result appendString:@"x"];
        } else {
          [result appendString:@"x^"];
          [result appendFormat:@"%d", degree];
        }
      }
    }
  }

  return result;
}

@end