#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#include <unistd.h>

typedef struct {
   unsigned short int fuelAmt, flightNum;
} aircraft_t;

typedef struct {
   unsigned int arraysize, heapsize;
   aircraft_t *array;
} deap_t;

aircraft_t get_min(deap_t deap) {
   return deap.array[2];
}

aircraft_t get_max(deap_t deap) {
   if (deap.heapsize > 2)
      return deap.array[3];
   else
      return get_min(deap);
}

int row_starts(int i) {
   return pow(2, (int) log2(i));
}

int swap(deap_t *flights, int from, int to) {
   /* Use the empty 0 spot for temporary storage */
   flights->array[0] = flights->array[to];
   flights->array[to] = flights->array[from];
   flights->array[from] = flights->array[0];

   return to;
}

int cousin(deap_t deap, int i, bool try_parent) {
   int midpoint = row_starts(i) * 1.5;
   int cousin;

   if (i < midpoint)
      cousin = i - row_starts(i) + midpoint;
   else
      cousin = i + row_starts(i) - midpoint;

   if (try_parent && cousin > deap.heapsize)
      cousin /= 2; /* If there's no node there, use the parent */

   if (cousin == 1)
      cousin = 2; /* Special-case for when we accidentally choose 1 */

   return cousin;
}

void trickle_up(deap_t *deap, int from_index) {
   if (from_index/2 < 2)
      return;
   if (cousin(*deap, from_index, false) > from_index) {
      /* this is the min-heap side */
      if (deap->array[from_index].fuelAmt < deap->array[from_index/2].fuelAmt)
         trickle_up(deap, swap(deap, from_index, from_index/2));
   }
   else {
      /* max-heap side of the deap */
      if (deap->array[from_index].fuelAmt > deap->array[from_index/2].fuelAmt)
         trickle_up(deap, swap(deap, from_index, from_index/2));
   }
}

int trickle_down(deap_t *deap, int from_index) {
   aircraft_t leftchild, rightchild;
   leftchild = deap->array[from_index*2];
   rightchild = deap->array[from_index*2 + 1];

   if (from_index*2 > deap->heapsize)
      return from_index;
   if (cousin(*deap, from_index, false) > from_index) {
      /* this is the min-heap side */
      if (leftchild.fuelAmt < rightchild.fuelAmt) {
         if (deap->array[from_index].fuelAmt > leftchild.fuelAmt)
            return trickle_down(deap, swap(deap, from_index, from_index*2));
      }
      else if (deap->array[from_index].fuelAmt > rightchild.fuelAmt)
         return trickle_down(deap, swap(deap, from_index, from_index*2 + 1));
   }
   else {
      /* max-heap side of the deap */
      if (leftchild.fuelAmt > rightchild.fuelAmt) {
         if (deap->array[from_index].fuelAmt < leftchild.fuelAmt)
            return trickle_down(deap, swap(deap, from_index, from_index*2));
      }
      else if (deap->array[from_index].fuelAmt < rightchild.fuelAmt)
         return trickle_down(deap, swap(deap, from_index, from_index*2 + 1));
   }
   return from_index;
}

bool on_correct_side(deap_t deap, int thisi) {
   int cousini = cousin(deap, thisi, false);
   int cousinp = cousin(deap, thisi, true);
   int cousinv = deap.array[cousinp].fuelAmt;
   int thisv = deap.array[thisi].fuelAmt;

   if (cousini > thisi && cousinv >= thisv)
      return true;
   else if (cousini < thisi && cousinv <= thisv)
      return true;
   else
      return false;
}

void insert(deap_t *flights, aircraft_t new) {
   printf("Inserting %d\n", new.fuelAmt);
   flights->array[++(flights->heapsize)] = new;
   if (!on_correct_side(*flights, flights->heapsize))
      swap(flights, flights->heapsize, cousin(*flights, flights->heapsize, true));

   trickle_up(flights, cousin(*flights, flights->heapsize, true));
}

aircraft_t pop_min(deap_t *deap) {
   /* I think it's possible this solved the issues with < 5 elements and problems
      shown in class, but I'm not sure. I forget how they happened. */
   int newindex;

   deap->array[1] = deap->array[2]; /* save for later. */
   deap->heapsize--; /* The last spot on the deep was just dropped */

   /* Trickle down the "empty" spot, pretend it's worth infinity, go bottom */

   deap->array[2].fuelAmt = -1; /* unsigned, we just overflowed to max. */
   newindex = trickle_down(deap, 2);

   /* Now we go and replace that element with our dropped one from earlier */
   deap->array[newindex] = deap->array[deap->heapsize + 1];
   trickle_up(deap, newindex);

   return deap->array[1];
}

aircraft_t pop_max(deap_t *deap) {
   /* Just like min. I could probably combine these functions. */
   int newindex;

   deap->array[1] = deap->array[3]; /* save for later. 0 and 1 unused. */
   deap->heapsize--; /* The last spot on the deep was just dropped */

   /* Trickle down the "empty" spot, pretend it's worth nothing, goes bottom */

   deap->array[3].fuelAmt = 0;
   newindex = trickle_down(deap, 3);

   /* Now we go and replace that element with our dropped one from earlier */
   deap->array[newindex] = deap->array[deap->heapsize + 1];
   trickle_up(deap, newindex);

   return deap->array[1];
}


void printheap(deap_t flights) {
   unsigned short int i;
   for (i = 2; i <= flights.heapsize; i++) {
      if ((i & (i - 1)) == 0) /* Check if power of two. */
         puts("\n");

      printf("%3d ", flights.array[i].fuelAmt);
   }
}

void init_deap(deap_t *empty, int size) {
   empty->array = calloc(size, sizeof(aircraft_t));
   empty->arraysize = size;
   empty->heapsize = 1;
}

int main(int argc, char *argv[]) {
   FILE *input;
   bool verbose = false;
   char *datafile = "DEAPdataFileSmall";
   short int c;

   char opcode;
   aircraft_t newplane;
   deap_t flights;

   /* getopt is a nice helper to parse cli parameters. */
   while ((c = getopt(argc, argv, "vi:")) != -1) {
      switch (c) {
         case 'v':
            verbose = true;
            break;
         case 'i':
            datafile = optarg;
            break;
         default:
            puts("usage: [-v] [-i INPUTFILE]");
            exit(1);
      }
   }

   init_deap(&flights, 5000);

   input = fopen(datafile, "r");
   assert(input != NULL);

   while (opcode != EOF) {
      switch(opcode = getc(input)) {
         case 'i':
            fscanf(input, " %hu %hu", &newplane.fuelAmt, &newplane.flightNum);
            insert(&flights, newplane);
            printheap(flights);
            puts("\n-----");
            break;

         case 'L':
            printf("Popped min. %hu\n", pop_min(&flights).fuelAmt);
            printheap(flights);
            break;

         case 'D':
            printf("Popped max. %hu\n", pop_max(&flights).fuelAmt);
            printheap(flights);
            break;
      }
   }

   fclose(input);

   free(flights.array);
   return 1;
}