/*
 * Copyright ©2022 Hannah C. Tang.  All rights reserved.  Permission is
 * hereby granted to students registered for University of Washington
 * CSE 333 for use solely during Spring Quarter 2022 for purposes of
 * the course.  No other use, copying, distribution, or modification
 * is permitted without prior written consent. Copyrights for
 * third-party components of this work must be honored.  Instructors
 * interested in reusing these course materials should contact the
 * author.
 */
#define INITIAL_CAPACITY 10

#include <stdint.h>  // uint64_t
#include <stdlib.h>  // calloc

#include "fib.h"

int64_t *fib_values = NULL;
int fib_size = 0;
int fib_capacity = INITIAL_CAPACITY;

void maybe_resize_to(int n) {
  int old_size = fib_size;
  int64_t *old_fib_values = fib_values;
  int i = 0;

  if (n < fib_capacity - 1) {
    return;
  }

  // First, ensure the array is big enough to hold our newly-calculated.
  // value.  We'll double the array size until it's sufficient.
  while (fib_capacity <= n) {
    fib_capacity *= 2;
  }

  // Copy over our already-calculated values into the new array
  fib_values = (int64_t*)calloc(fib_capacity, sizeof(int64_t));
  for (i = 0; i <= old_size; ++i) {
    fib_values[i] = old_fib_values[i];
  }
  free(old_fib_values);
}

int64_t fib(int16_t n) {
  int i = 0;

  // If this is the first call to fib(), initialize the array and
  // its metadata.
  if (fib_values == NULL) {
    fib_capacity = INITIAL_CAPACITY;

    fib_values = (int64_t*)calloc(fib_capacity, sizeof(int64_t));

    fib_values[0] = 1;
    fib_values[1] = 1;
    fib_values[2] = 2;
    fib_size = 2;
  }

  // Ensure the array is big enough to accomodate the requested
  // Fibonacci number.  May or may not resize the underlying array.  Note
  // that the initially-sized array might be too small; this will ensure
  // it's resized to fit the requested size.
  maybe_resize_to(n);

  // If we haven't calculated-and-cached the currently-requested Fibonacci
  // number yet, do so now.
  if (n > fib_size) {
    for (i = fib_size; i <= n; ++i) {
      fib_values[i+1] = fib_values[i] + fib_values[i-1];
    }
    fib_size = n;
  }

  return fib_values[n];
}