path: root/src/dfs.c

#include <stdlib.h>
#include <stdio.h>
#include "dfs.h"
#include "structs.h"
#include "common.h"

struct front_item * dfs(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);

  /* Iterative dfs */
  do {
    /* Check if tree is leaf. If true: 
     *   Add item to front_item;
     *   Update tree to tree->next;
     *   Free leaf;
     *   Continue;
     */
    if(tree->depth == data->N) {
      front_last->next = new_front_item(tree->values.p, tree->values.w, front_last, NULL);
      front_last = front_last->next;
      
      struct tree_item * old = tree;
      tree = tree->next;
      if(tree != NULL) {
        tree->prev = old->prev;
      }
      free(old);

      continue;
    }

    /* Make left node (select item) */
    struct tree_item * left = new_tree_item(
      tree->depth + 1,
      tree->itemi + 1,
      tree->values.w + data->items[tree->itemi].w,
      tree->values.p + data->items[tree->itemi].p,
      tree->prev,
      tree
    );
    /* Make right node (do not select item) */
    struct tree_item * right = new_tree_item(
      tree->depth + 1,
      tree->itemi + 1,
      tree->values.w,
      tree->values.p,
      left,
      tree->next
    );
    /* Update left next */
    left->next = right;

    /* Update tree to left node and free old node */
    struct tree_item * old = tree;
    tree = left;
    free(old);
  } 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 dfs_online(struct data * data, struct front_item * front, struct tree_item * tree, long int change_at){
  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 change=0;

  /* Iterative dfs */
  do {
    /* Check if tree is leaf. If true: 
     *   Add item to front_item;
     *   Update tree to tree->next;
     *   Free leaf;
     *   Continue;
     */
    change++;

    if(tree->depth == data->N) {
      front_last->next = new_front_item(tree->values.p, tree->values.w, front_last, NULL);
      front_last = front_last->next;
      
      /* Adjust prev and next */
      if(tree->prev != NULL) tree->prev->next = tree->next;
      if(tree->next != NULL) tree->next->prev = tree->prev;
      
      struct tree_item * old = tree;
      tree = tree->next;
      free(old);

      continue;
    }

    /* Make left node (select item) */
    struct tree_item * left = new_tree_item(
      tree->depth + 1,
      tree->itemi + 1,
      tree->values.w + data->items[tree->itemi].w,
      tree->values.p + data->items[tree->itemi].p,
      tree->prev,
      tree
    );
    /* Make right node (do not select item) */
    struct tree_item * right = new_tree_item(
      tree->depth + 1,
      tree->itemi + 1,
      tree->values.w,
      tree->values.p,
      left,
      tree->next
    );
    /* Update left next */
    left->next = right;

    /* Adjust prev and next */
    if(tree->prev != NULL) tree->prev->next = left;
    if(tree->next != NULL) tree->next->prev = right;

    /* Update tree to left node and free old node */
    struct tree_item * old = tree;
    tree = left;
    free(old);
  } while(tree != NULL && change < change_at);

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

  return ret;
}