root/lang/c/rbtree/branches/bst_inherit_impl/test_bstree.c @ 5251

/* $Id$
 *
 * Copyright (C) 2008 Kenta Murata.
 * 
 * This file is part of rbtree.
 *
 * rbtree is free software: you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * rbtree is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with rbtree.  If not, see
 * <http://www.gnu.org/licenses/>.
 */
/* gcc -g -Wall -DNOT_RUBY -o test_rbtree test_rbtree.c -lcunit */
/* gcc -g -Wall -I/usr/lib/ruby/1.8/i486-linux/ -o test_rbtree
   test_rbtree.c -lcunit -lruby1.8 */

#include "bstree.h"

#include <CUnit/CUnit.h>
#include <CUnit/Basic.h>

#include <stdio.h>
#include <stdlib.h>

#define ALLOC_NODE() \
  (struct bstree_node*)malloc(sizeof(struct bstree_node))

static inline void
print_intnode(struct bstree_node const* node)
{
  printf("<%p:%llu, %s, %p, %p, %p>",
         node, BSTREE_NODE_VALUE(node), BSTREE_NODE_PARENT(node),
         BSTREE_NODE_LEFT(node), BSTREE_NODE_RIGHT(node));
}

static inline void
println_strnode(struct bstree_node const* node)
{
  print_strnode(node);
  putchar('\n');
}

/*                      index---.   ,---value
 *                             ( 5: 5)
 *                ,---------------^---------------.
 *             ( 2: 2)                         ( 9: 9)
 *        ,-------^-------.               ,-------^-------.
 *     ( 1: 1)         ( 3: 2)         ( 7: 7)         (11:11)
 *    ,---^---.       ,---^---.       ,---^---.       ,---^---.
 * ( 0: 0)   (:)     (:)   ( 4: 2) ( 6: 6) ( 8: 8) (10:10)   (:)
 *  ,-^-.                   ,-^-.   ,-^-.   ,-^-.   ,-^-.
 * (:) (:)                 (:) (:) (:) (:) (:) (:) (:) (:)
 *       '---null node
 */

static struct bstree_node* nodes[12] = { 0, };
static struct bstree_node* root = 0;
static int dfs_index[12] = { 5, 2, 1, 0, 3, 4, 9, 7, 6, 8, 11, 10 };
static int bfs_index[12] = { 5, 2, 9, 1, 3, 7, 11, 0, 4, 6, 8, 10 };

static int
suite_rbtree_init(void)
{
  int i;

  for (i = 0; i < 12; ++i) {
    nodes[i] = ALLOC_NODE();
    BSTREE_NODE_PARENT(nodes[i]) = 0;
    BSTREE_NODE_LEFT(nodes[i]) = 0;
    BSTREE_NODE_RIGHT(nodes[i]) = 0;
    BSTREE_NODE_VALUE(nodes[i]) = BSTREE_DATA(i);
  }

  for (i = 2; i < 3; ++i) {
    BSTREE_VALUE(nodes[i]) = 2;
  }

  BSTREE_NODE_PARENT(nodes[0]) = nodes[1];
  BSTREE_NODE_LEFT(nodes[1]) = nodes[0];

  BSTREE_NODE_PARENT(nodes[1]) = nodes[2];
  BSTREE_NODE_LEFT(nodes[2]) = nodes[1];

  BSTREE_NODE_PARENT(nodes[2]) = nodes[5];
  BSTREE_NODE_LEFT(nodes[5]) = nodes[2];

  BSTREE_NODE_PARENT(nodes[3]) = nodes[2];
  BSTREE_NODE_RIGHT(nodes[2]) = nodes[3];

  BSTREE_NODE_PARENT(nodes[4]) = nodes[3];
  BSTREE_NODE_RIGHT(nodes[3]) = nodes[4];

  root = nodes[5];

  BSTREE_NODE_PARENT(nodes[6]) = nodes[7];
  BSTREE_NODE_LEFT(nodes[7]) = nodes[6];

  BSTREE_NODE_PARENT(nodes[7]) = nodes[9];
  BSTREE_NODE_LEFT(nodes[9]) = nodes[7];

  BSTREE_NODE_PARENT(nodes[8]) = nodes[7];
  BSTREE_NODE_RIGHT(nodes[7]) = nodes[8];

  BSTREE_NODE_PARENT(nodes[9]) = nodes[5];
  BSTREE_NODE_RIGHT(nodes[5]) = nodes[9];

  BSTREE_NODE_PARENT(nodes[10]) = nodes[11];
  BSTREE_NODE_RIGHT(nodes[11]) = nodes[10];

  BSTREE_NODE_PARENT(nodes[11]) = nodes[9];
  BSTREE_NODE_RIGHT(nodes[9]) = nodes[11];

  return 0;
}

static int
suite_rbtree_clean(void)
{
  int i;
  for (i = 0; i < 12; ++i) {
    free(nodes[i]);
  }

  return 0;
}

static void
test_lookup_lower_bound(void)
{
  CU_ASSERT_EQUAL(nodes[2],
                  bstree_node_lookup_lower_bound(
                    root, bstree_intcmp, 0, 2));
  CU_ASSERT_EQUAL(nodes[5],
                  bstree_node_lookup_lower_bound(
                    root, bstree_intcmp, 0, 5));
  CU_ASSERT_EQUAL(nodes[10],
                  bstree_node_lookup_lower_bound(
                    root, bstree_intcmp, 0, 10));
}

static void
test_lookup_upper_bound(void)
{
  CU_ASSERT_EQUAL(nodes[4],
                  bstree_node_lookup_upper_bound(
                    root, bstree_intcmp, 0, 2));
  CU_ASSERT_EQUAL(nodes[5],
                  bstree_node_lookup_upper_bound(
                    root, bstree_intcmp, 0, 5));
  CU_ASSERT_EQUAL(nodes[10],
                  bstree_node_lookup_upper_bound(
                    root, bstree_intcmp, 0, 10));
}

static int
callback_test_foreach(struct bstree_node* node, void* callback_data)
{
  int* index = callback_data;
  CU_ASSERT_EQUAL(nodes[*index], node);
  (*index)++;
  return BSTREE_CONTINUE;
}

static void
test_foreach(void)
{
  int index = 0;
  bstree_node_foreach(root, callback_test_foreach, &index);
  CU_ASSERT_EQUAL(12, data.index);
}

struct test_foreach_range_data {
  int index, inf, sup, count;
};

static int
callback_test_foreach(struct bstree_node* node, void* callback_data)
{
  struct test_foreach_range_data* data = callback_data;
  CU_ASSERT_EQUAL(nodes[data->index], node);
  data->index++;
  data->count++;
  return BSTREE_CONTINUE;
}

static void
test_foreach_range(void)
{
  struct test_foreach_range_data data;

  data.index = 2;
  data.inf   = 2;
  data.sup   = 2;
  data.count = 0;
  bstree_node_foreach_range(root, bstree_intcmp, 0,
                            callback_test_foreach_range, &data,
                            data.inf, data.sup);
  CU_ASSERT_EQUAL(3, data.count);

  data.index = 2;
  data.inf   = 2;
  data.sup   = 7;
  data.count = 0;
  bstree_node_foreach_range(root, bstree_intcmp, 0,
                            callback_test_foreach_range, &data,
                            data.inf, data.sup);
  CU_ASSERT_EQUAL(6, data.count);

  data.index = 5;
  data.inf   = 5;
  data.sup   = 5;
  data.count = 0;
  bstree_node_foreach_range(root, bstree_intcmp, 0,
                            callback_test_foreach_range, &data,
                            data.inf, data.sup);
  CU_ASSERT_EQUAL(1, data.count);
}

static int
callback_test_dfs_foreach(struct bstree_node* node, void* callback_data)
{
  int* index = callback_data;
  CU_ASSERT_EQUAL(nodes[dfs_index[*index]], node);
  (*index)++;
  return BSTREE_CONTINUE;
}

static void
test_dfs_foreach(void)
{
  int index = 0;
  bstree_node_dfs_foreach(root, callback_test_dfs_foreach, &index);
  CU_ASSERT_EQUAL(12, data.index);
}

static int
callback_test_bfs_foreach(struct bstree_node* node, void* callback_data)
{
  int* index = callback_data;
  CU_ASSERT_EQUAL(nodes[bsf_index[*index]], node);
  (*index)++;
  return BSTREE_CONTINUE;
}

static void
test_bfs_foreach(void)
{
  int index = 0;
  bstree_node_bfs_foreach(root, callback_test_bfs_foreach, &index);
  CU_ASSERT_EQUAL(12, data.index);
}

static CU_TestInfo tests_bstree[] = {
  { "test_lookup_lower_bound", test_lookup_lower_bound },
  { "test_lookup_upper_bound", test_lookup_upper_bound },
  { "test_foreach", test_foreach },
  { "test_foreach_range", test_foreach_range },
  { "test_dfs_foreach", test_dfs_foreach },
  { "test_bfs_foreach", test_bfs_foreach },
  CU_TEST_INFO_NULL,
};

static CU_SuiteInfo suites[] = {
  { "suite_bstree", suite_bstree_init, suite_bstree_clean, tests_bstree },
  CU_SUITE_INFO_NULL,
};

int
main(int argc, char** argv)
{
  CU_BasicRunMode mode = CU_BRM_VERBOSE;
  CU_ErrorAction error_action = CUEA_IGNORE;

  setvbuf(stdout, NULL, _IONBF, 0);
  if (CU_initialize_registry()) {
    fprintf(stderr, "Initialization of Test Registry failed.\n");
  }
  else {
    if (CU_register_suites(suites) != CUE_SUCCESS) {
      fprintf(stderr, "suite registration failed - %s\n", CU_get_error_msg());
      return EXIT_FAILURE;
    }
    CU_basic_set_mode(mode);
    CU_set_error_action(error_action);
    printf("\nTests completed with return value %d.\n", CU_basic_run_tests());
    CU_cleanup_registry();
  }

  return 0;
}

/*
 * Local Variables:
 * coding: utf-8
 * mode: c
 * c-basic-offset: 2
 * indent-tabs-mode: nil
 * End:
 */