path: root/src/common.c

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include "structs.h"
#include "common.h"

struct data * input(char fp[]){
  int i,j;
  FILE *f;
  struct data * d = (struct data *)malloc(sizeof(struct data));

  f = fopen(fp,"r");
  j = fscanf(f,"%ld",&(d->N));
  if(j!=1){
    printf("Error reading data\n");
    exit(0);
  }
  d->items = (struct item *)malloc(d->N*sizeof(struct item));
  for(i=0;i<d->N;++i){
    j = fscanf(f,"%lf %lf",&(d->items[i].p),&(d->items[i].w));
    d->allp += d->items[i].p;
    d->allw += d->items[i].w;
  }

  fclose(f);
  return d;
}

int cmp_items_ratio(const void * a, const void * b){
  struct item c = *(struct item *)a;
  struct item d = *(struct item *)b;
  if(c.p / c.w < d.p / d.w){
    return 1;
  }
  return -1;
}

int cmp_items_random(const void *a, const void *b) {
  if(rand() % 2 == 0){
    return 1;
  }
  return -1;
}

void print_data(struct data * d){
  int i;
  printf("### PRINTING DATA - BEGINNING ###\n");
  printf("N:\t%ld\n\n",d->N);
  printf("Profit\tWeight\n");
  for(i=0;i<d->N;++i){
    printf("%.02f\t%.02f\n",d->items[i].p,d->items[i].w);
  }
  printf("### PRINTING DATA - ENDING ###\n");
}

void print_front(struct front_item * b){
  struct front_item * beg = b;

  printf("Profit, Weight, Time\n");
  while(b!=NULL){
    clock_t t = b->time - beg->time;
    printf("%.02f,%.02f,%f\n", b->i.p, b->i.w, ((double)t)/CLOCKS_PER_SEC);
    b = b->next;
  }
}

void free_data(struct data * d){
  free(d->items);
  free(d);
}

void free_front(struct front_item * b){
  struct front_item * tmp;
  for(;b!=NULL;){
    tmp = b;
    b = b->next;
    free(tmp);
  }
}

struct front_item * new_front_item(double p, double w, struct front_item * prev, struct front_item * next){
  struct front_item * f = (struct front_item *)malloc(sizeof(struct front_item));
  f->i.p = p;
  f->i.w = w;
  f->next = next;
  f->prev = prev;
  f->time = clock();

  return f;
}

struct tree_item * new_tree_item(long int depth, long int itemi, double w, double p, struct tree_item * prev, struct tree_item * next) {
  struct tree_item * t = (struct tree_item *)malloc(sizeof(struct tree_item));
  t->depth = depth;
  t->itemi = itemi;
  t->values.w = w;
  t->values.p = p;
  t->prev = prev;
  t->next = next;
  
  return t;
}

double dist_items(struct item * a, struct item * b){
  return sqrt((a->p - b->p)*(a->p - b->p) + (a->w - b->w)*(a->w - b->w));
}

int len_front(struct front_item * f){
  int N;
  for(N=0;f!=NULL;f=f->next,N++);
  return N;
}

/* Shuffle data items starting on a certain index, in place */
void shuffle_items(struct data * d, int start) {
  int i, ind;
  struct item * new_items;

  if (start < 0) return;
  if (start >= d->N) return;

  new_items = (struct item *)malloc(d->N * sizeof(struct item));

  /* These stay the same */
  for(i = 0; i < start; i++) {
    new_items[i].p = d->items[i].p;
    new_items[i].w = d->items[i].w;
  }

  /* Shuffle the rest */
  for(i = start; i < d->N; i++) {
    ind = rand() % (d->N - i);
    new_items[i].p = d->items[i+ind].p;
    new_items[i].w = d->items[i+ind].w;
    d->items[i+ind].p = d->items[i].p;
    d->items[i+ind].w = d->items[i].w;
  }

  /* Replace old array */
  free(d->items);
  d->items = new_items;
}