path: root/src/random_heuristic.c

#include <stdlib.h>
#include "random_heuristic.h"
#include "structs.h"
#include "common.h"
#include <stdio.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;
  
  /* 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);

  do {
    
    /* 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--;
      
      if(tree != NULL) {
        /* Select new random node */
        position = rand() % tree_size;
        node = tree;
        for(int i = 0; i < position; i++,node=node->next);
      }

      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);
    
    /* Choose left or right randomly for node */
    if(rand() % 2 == 0) {
      node = left;
    } else {
      node = right;
    }

    /* 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;
}

struct online_return random_heuristic_online(struct data * data, struct front_item * front, struct tree_item * tree) {
  if(front == NULL) {
    front = new_front_item(0, 0, NULL, NULL);
  }
  struct front_item * front_last = front;
  for(;front_last->next != NULL; front_last=front_last->next);
  
  if(tree == NULL) {
    tree = new_tree_item(0, 0, 0, 0, NULL, NULL);
  }
  long int tree_size = 0;
  for(struct tree_item * tree_node = tree; tree_node != NULL; tree_node = tree_node->next, tree_size++);

  /* 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);

  do {
    /* 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;
      
      if(node->prev != NULL) node->prev->next = node->next;
      if(node->next != NULL) node->next->prev = node->prev;
      
      if(tree == node) tree = node->next;
      free(node);

      /* Reduce tree_size */
      tree_size--;

      if(tree != NULL) {
        /* Select new random node */
        position = rand() % tree_size;
        node = tree;
        for(int i = 0; i < position; i++,node=node->next);
      }

      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
    );

    /* 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
    );

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

    if(node->prev != NULL) node->prev->next = left;
    if(node->next != NULL) node->next->prev = right;

    if(tree == node) tree = left;
    free(node);

    /* Choose left or right randomly for node */
    node = rand() % 2 == 0 ? left : right;

    /* Increment tree_size */
    tree_size++;

  } while(tree != NULL);

  struct online_return ret;
  ret.front = front;
  ret.tree = tree;
 
  return ret;
}