//************************************
//  and.c
//************************************

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ruby.h>
#include "figure_set.h"

static void middel_intersection_branch_node(root_node, branch_node, branch_node, branch_node);
static void last_intersection_branch_node(root_node, branch_node, branch_node, branch_node);

static branch_node
init_and_intersection_branch_node(root_node result_set, branch_node base, branch_node other)
{
  branch_node branch;

  branch = (branch_node)init_branch_node();

  if (base->children_type == CT_LEAF) {
    last_intersection_branch_node(result_set, branch, base, other);
  } else {
    middel_intersection_branch_node(result_set, branch, base, other);
  }

  if (branch->children_size) {
    branch->children_type = base->children_type;
    return branch;
  } else {
    destroy_branch(branch);
    return (branch_node)NULL;
  }
}

static leaf_node
init_and_intersection_leaf_node(root_node result_set, leaf_node base, leaf_node other)
{
  unsigned long data;
  leaf_node leaf;

  data = base->data & other->data;

  if (!data) return (leaf_node)NULL;

  leaf = (leaf_node)init_leaf_node(base->offset);
  leaf->data = data;
  result_set->size += BIT_COUNT(leaf->data);

  return leaf;
}

static void
middel_intersection_branch_node(root_node result_set, branch_node branch, branch_node base, branch_node other)
{
  unsigned int i, count;
  branch_node middle_branch;

  for (i = 0, count = 0; i < MAX_CHILDREN_SIZE_OF_BRANCH || count < base->children_size; i++) {
    if (base->index[i]) {
      count++;
      if (other->index[i]) {
        middle_branch = (branch_node)init_and_intersection_branch_node(result_set, (branch_node)base->index[i], (branch_node)other->index[i]);
        if (middle_branch) {
          branch->index[i] = (void*)middle_branch;
          branch->children_size++;
        }
      }
    }
  }
}

static void
last_intersection_branch_node(root_node result_set, branch_node branch, branch_node base, branch_node other)
{
  unsigned int i, count;
  leaf_node leaf;

  for (i = 0, count = 0; i < MAX_CHILDREN_SIZE_OF_BRANCH || count < base->children_size; i++) {
    if (base->index[i]) {
      count++;
      if (other->index[i]) {
        leaf = (leaf_node)init_and_intersection_leaf_node(result_set, (leaf_node)base->index[i], (leaf_node)other->index[i]);
        if (leaf) {
          branch->index[i] = (void*)leaf;
          branch->children_size++;
        }
      }
    }
  }
}

//
// intersection
//
void
intersection(root_node result_set, root_node set0, root_node set1)
{
  unsigned int i, count;
  root_node base, other;
  branch_node branch;

  if (set0->size == 0 || set1->size == 0) {
    return;
  } else if (set0->size > set1->size) {
    base = set1;
    other = set0;
  } else {
    base = set0;
    other = set1;
  }

  for (i = 0, count = 0; i < MAX_CHILDREN_SIZE_OF_ROOT_NODE || count < base->children_size; i++) {
    if (base->index[i]) {
      count++;
      if (other->index[i]) {
        branch = (branch_node)init_and_intersection_branch_node(result_set, (branch_node)base->index[i], (branch_node)other->index[i]);
        if (branch) {
          result_set->index[i] = (void*)branch;
          result_set->children_size++;
        }
      }
    }
  }
}