path: root/src/random_heuristic.c

#include <stdlib.h>
#include "random_heuristic.h"
#include "structs.h"
#include "common.h"

struct front_item * random_heuristic(struct data * data) {
  struct front_item * front = new_front_item(0, 0, NULL, NULL);
  struct front_item * front_last = front;
  struct tree_item * tree = new_tree_item(0, 0, 0, 0, NULL, NULL);
  long int tree_size = 1;

  do {
    /* Choose tree node randomly */
    long int position = rand() % tree_size;
    struct tree_item * node = tree;
    for(int i = 0; i < position; i++,node=node->next);
    
    /* Check if node is leaf */
    if(node->depth == data->N) {
      front_last->next = new_front_item(node->values.p, node->values.w, front_last, NULL);
      front_last = front_last->next;
      
      struct tree_item * old = node;
      if(tree == old) {
        tree = node->next;
      }

      if(node->next != NULL) {
        node->next->prev = node->prev;
      }
      if(node->prev != NULL) {
        node->prev->next = node->next;
      }
      free(old);
      /* Reduce tree_size */
      tree_size--;

      continue;
    }
    
    /* Make left node (select item) */
    struct tree_item * left = new_tree_item(
      node->depth + 1,
      node->itemi + 1,
      node->values.w + data->items[node->itemi].w,
      node->values.p + data->items[node->itemi].p,
      node->prev,
      node
    );
    if(node->prev != NULL){
      node->prev->next = left;
    }

    /* Make right node (do not select item) */
    struct tree_item * right = new_tree_item(
      node->depth + 1,
      node->itemi + 1,
      node->values.w,
      node->values.p,
      left,
      node->next
    );
    if(node->next != NULL) {
      node->next->prev = right;
    }

    /* Adjust left->next to right */
    left->next = right;

    struct tree_item * old = node;
    if(node == tree) {
      tree = left;
    }
    free(old);

    /* Increment tree_size */
    tree_size++;
  } while(tree != NULL);
 
  /* Remove first item from front (only a placeholder) */
  front=front->next;
  free(front->prev);
  front->prev = NULL;

  return front;
  return NULL;
}