/* Test the interval data-structure in itree.c.

Copyright (c) 2017-2022 Free Software Foundation, Inc.

This file is part of GNU Emacs.

GNU Emacs is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.

GNU Emacs 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 General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.  */

#include <config.h>

#include <stdarg.h>
#include <stdlib.h>

#include <check.h>
#include "emacs-compat.h"

#define EMACS_LISP_H            /* lisp.h inclusion guard */
#define ITREE_DEBUG 1
#define ITREE_TESTING
#include "itree.c"

/* Globals.  */

static struct itree_tree tree;
static struct itree_node A, B, C, D, E;
static struct itree_node N_05, N_10, N_15, N_20, N_30, N_40;
static struct itree_node N_50, N_70, N_80, N_90, N_85, N_95;

/* Basic tests of the itree_tree data-structure.  */

/* +===================================================================================+
 * | Insert
 * +===================================================================================+ */

/* The graphs below display the trees after each insertion (as they
   should be).  See the source code for the different cases
   applied.  */

static void
test_insert1_setup (void)
{
  enum { N = 6 };
  const int values[N] = {50, 30, 20, 10, 15, 5};
  struct itree_node *nodes[N] = {&N_50, &N_30, &N_20, &N_10, &N_15, &N_05};
  interval_tree_init (&tree);
  for (int i = 0; i < N; ++i)
    {
      nodes[i]->begin = nodes[i]->end = values[i];
      nodes[i]->otick = tree.otick;
    }
}

START_TEST (test_insert_1)
{
  /*
   *                 [50]
   */

  interval_tree_insert (&tree, &N_50);
  ck_assert (! N_50.red);
  ck_assert_ptr_eq (&N_50, tree.root);
}
END_TEST

START_TEST (test_insert_2)
{
  /*
   *                 [50]
   *                /
   *              (30)
   */

  interval_tree_insert (&tree, &N_50);
  interval_tree_insert (&tree, &N_30);
  ck_assert (! N_50.red);
  ck_assert (N_30.red);
  ck_assert_ptr_eq (&N_50, tree.root);
  ck_assert_ptr_eq (N_30.parent, &N_50);
  ck_assert_ptr_eq (N_50.left, &N_30);
  ck_assert_ptr_null (N_50.right);
  ck_assert_ptr_null (N_30.left);
  ck_assert_ptr_null (N_30.right);
}
END_TEST

START_TEST (test_insert_3)
{
  /* case 3.a
   *                [30]
   *               /    \
   *             (20)   (50)
   */

  interval_tree_insert (&tree, &N_50);
  interval_tree_insert (&tree, &N_30);
  interval_tree_insert (&tree, &N_20);
  ck_assert (N_50.red);
  ck_assert (! N_30.red);
  ck_assert (N_20.red);
  ck_assert_ptr_eq (&N_30, tree.root);
  ck_assert_ptr_eq (N_50.parent, &N_30);
  ck_assert_ptr_eq (N_30.right, &N_50);
  ck_assert_ptr_eq (N_30.left, &N_20);
  ck_assert_ptr_null (N_20.left);
  ck_assert_ptr_null (N_20.right);
  ck_assert_ptr_eq (N_20.parent, &N_30);
}
END_TEST

START_TEST (test_insert_4)
{
  /* 1.a
   *                [30]
   *               /    \
   *             [20]   [50]
   *             /
   *           (10)
   */

  interval_tree_insert (&tree, &N_50);
  interval_tree_insert (&tree, &N_30);
  interval_tree_insert (&tree, &N_20);
  interval_tree_insert (&tree, &N_10);
  ck_assert (! N_50.red);
  ck_assert (! N_30.red);
  ck_assert (! N_20.red);
  ck_assert (N_10.red);
  ck_assert_ptr_eq (&N_30, tree.root);
  ck_assert_ptr_eq (N_50.parent, &N_30);
  ck_assert_ptr_eq (N_30.right, &N_50);
  ck_assert_ptr_eq (N_30.left, &N_20);
  ck_assert_ptr_eq (N_20.left, &N_10);
  ck_assert_ptr_null (N_20.right);
  ck_assert_ptr_eq (N_20.parent, &N_30);
  ck_assert_ptr_eq (N_10.parent, &N_20);
  ck_assert_ptr_eq (N_20.left, &N_10);
  ck_assert_ptr_null (N_10.right);
}
END_TEST

START_TEST (test_insert_5)
{
  /* 2.a
   *                [30]
   *               /    \
   *             [15]   [50]
   *             /  \
   *           (10) (20)
   */

  interval_tree_insert (&tree, &N_50);
  interval_tree_insert (&tree, &N_30);
  interval_tree_insert (&tree, &N_20);
  interval_tree_insert (&tree, &N_10);
  interval_tree_insert (&tree, &N_15);
  ck_assert (! N_50.red);
  ck_assert (! N_30.red);
  ck_assert (N_20.red);
  ck_assert (N_10.red);
  ck_assert (! N_15.red);
  ck_assert_ptr_eq (&N_30, tree.root);
  ck_assert_ptr_eq (N_50.parent, &N_30);
  ck_assert_ptr_eq (N_30.right, &N_50);
  ck_assert_ptr_eq (N_30.left, &N_15);
  ck_assert_ptr_null (N_20.left);
  ck_assert_ptr_null (N_20.right);
  ck_assert_ptr_eq (N_20.parent, &N_15);
  ck_assert_ptr_eq (N_10.parent, &N_15);
  ck_assert_ptr_null (N_20.left);
  ck_assert_ptr_null (N_10.right);
  ck_assert_ptr_eq (N_15.right, &N_20);
  ck_assert_ptr_eq (N_15.left, &N_10);
  ck_assert_ptr_eq (N_15.parent, &N_30);
}
END_TEST

START_TEST (test_insert_6)
{
  /* 1.a
   *                [30]
   *               /    \
   *             (15)   [50]
   *             /  \
   *           [10] [20]
   *           /
   *         (5)
   */

  interval_tree_insert (&tree, &N_50);
  interval_tree_insert (&tree, &N_30);
  interval_tree_insert (&tree, &N_20);
  interval_tree_insert (&tree, &N_10);
  interval_tree_insert (&tree, &N_15);
  interval_tree_insert (&tree, &N_05);
  ck_assert (! N_50.red);
  ck_assert (! N_30.red);
  ck_assert (! N_20.red);
  ck_assert (! N_10.red);
  ck_assert (N_15.red);
  ck_assert (N_05.red);
  ck_assert_ptr_eq (&N_30, tree.root);
  ck_assert_ptr_eq (N_50.parent, &N_30);
  ck_assert_ptr_eq (N_30.right, &N_50);
  ck_assert_ptr_eq (N_30.left, &N_15);
  ck_assert_ptr_null (N_20.left);
  ck_assert_ptr_null (N_20.right);
  ck_assert_ptr_eq (N_20.parent, &N_15);
  ck_assert_ptr_eq (N_10.parent, &N_15);
  ck_assert_ptr_null (N_20.left);
  ck_assert_ptr_null (N_10.right);
  ck_assert_ptr_eq (N_15.right, &N_20);
  ck_assert_ptr_eq (N_15.left, &N_10);
  ck_assert_ptr_eq (N_15.parent, &N_30);
  ck_assert_ptr_eq (N_05.parent, &N_10);
  ck_assert_ptr_eq (N_10.left, &N_05);
  ck_assert_ptr_null (N_05.right);
}
END_TEST



/* These are the mirror cases to the above ones.  */

static void
test_insert2_setup (void)
{
  enum { N = 6 };
  const int values[] = {50, 70, 80, 90, 85, 95};
  struct itree_node *nodes[N] = {&N_50, &N_70, &N_80, &N_90, &N_85, &N_95};
  interval_tree_init (&tree);
  for (int i = 0; i < N; ++i)
    {
      nodes[i]->begin = nodes[i]->end = values[i];
      nodes[i]->otick = tree.otick;
    }
}

START_TEST (test_insert_7)
{
  /*
   *                 [50]
   */

  interval_tree_insert (&tree, &N_50);
  ck_assert (! N_50.red);
  ck_assert_ptr_eq (&N_50, tree.root);
}
END_TEST

START_TEST (test_insert_8)
{
  /*
   *                 [50]
   *                    \
   *                   (70)
   */

  interval_tree_insert (&tree, &N_50);
  interval_tree_insert (&tree, &N_70);
  ck_assert (! N_50.red);
  ck_assert (N_70.red);
  ck_assert_ptr_eq (&N_50, tree.root);
  ck_assert_ptr_eq (N_70.parent, &N_50);
  ck_assert_ptr_eq (N_50.right, &N_70);
  ck_assert_ptr_null (N_50.left);
  ck_assert_ptr_null (N_70.right);
  ck_assert_ptr_null (N_70.left);
}
END_TEST

START_TEST (test_insert_9)
{
  /* 3.a
   *                [70]
   *               /    \
   *             (50)   (80)
   */

  interval_tree_insert (&tree, &N_50);
  interval_tree_insert (&tree, &N_70);
  interval_tree_insert (&tree, &N_80);
  ck_assert (N_50.red);
  ck_assert (! N_70.red);
  ck_assert (N_80.red);
  ck_assert_ptr_eq (&N_70, tree.root);
  ck_assert_ptr_eq (N_50.parent, &N_70);
  ck_assert_ptr_eq (N_70.right, &N_80);
  ck_assert_ptr_eq (N_70.left, &N_50);
  ck_assert_ptr_null (N_80.right);
  ck_assert_ptr_null (N_80.left);
  ck_assert_ptr_eq (N_80.parent, &N_70);
}
END_TEST

START_TEST (test_insert_10)
{
  /* 1.b
   *                [70]
   *               /    \
   *             [50]   [80]
   *                      \
   *                      (90)
   */

  interval_tree_insert (&tree, &N_50);
  interval_tree_insert (&tree, &N_70);
  interval_tree_insert (&tree, &N_80);
  interval_tree_insert (&tree, &N_90);
  ck_assert (! N_50.red);
  ck_assert (! N_70.red);
  ck_assert (! N_80.red);
  ck_assert (N_90.red);
  ck_assert_ptr_eq (&N_70, tree.root);
  ck_assert_ptr_eq (N_50.parent, &N_70);
  ck_assert_ptr_eq (N_70.right, &N_80);
  ck_assert_ptr_eq (N_70.left, &N_50);
  ck_assert_ptr_eq (N_80.right, &N_90);
  ck_assert_ptr_null (N_80.left);
  ck_assert_ptr_eq (N_80.parent, &N_70);
  ck_assert_ptr_eq (N_90.parent, &N_80);
  ck_assert_ptr_eq (N_80.right, &N_90);
  ck_assert_ptr_null (N_90.left);
}
END_TEST

START_TEST (test_insert_11)
{
  /* 2.b
   *                [70]
   *               /    \
   *             [50]   [85]
   *                    /  \
   *                  (80) (90)
   */

  interval_tree_insert (&tree, &N_50);
  interval_tree_insert (&tree, &N_70);
  interval_tree_insert (&tree, &N_80);
  interval_tree_insert (&tree, &N_90);
  interval_tree_insert (&tree, &N_85);
  ck_assert (! N_50.red);
  ck_assert (! N_70.red);
  ck_assert (N_80.red);
  ck_assert (N_90.red);
  ck_assert (! N_85.red);
  ck_assert_ptr_eq (&N_70, tree.root);
  ck_assert_ptr_eq (N_50.parent, &N_70);
  ck_assert_ptr_eq (N_70.right, &N_85);
  ck_assert_ptr_eq (N_70.left, &N_50);
  ck_assert_ptr_null (N_80.right);
  ck_assert_ptr_null (N_80.left);
  ck_assert_ptr_eq (N_80.parent, &N_85);
  ck_assert_ptr_eq (N_90.parent, &N_85);
  ck_assert_ptr_null (N_80.right);
  ck_assert_ptr_null (N_90.left);
  ck_assert_ptr_eq (N_85.right, &N_90);
  ck_assert_ptr_eq (N_85.left, &N_80);
  ck_assert_ptr_eq (N_85.parent, &N_70);

}
END_TEST

START_TEST (test_insert_12)
{
  /* 1.b
   *                [70]
   *               /    \
   *             [50]   (85)
   *                    /  \
   *                  [80] [90]
   *                         \
   *                        (95)
   */

  interval_tree_insert (&tree, &N_50);
  interval_tree_insert (&tree, &N_70);
  interval_tree_insert (&tree, &N_80);
  interval_tree_insert (&tree, &N_90);
  interval_tree_insert (&tree, &N_85);
  interval_tree_insert (&tree, &N_95);
  ck_assert (! N_50.red);
  ck_assert (! N_70.red);
  ck_assert (! N_80.red);
  ck_assert (! N_90.red);
  ck_assert (N_85.red);
  ck_assert (N_95.red);
  ck_assert_ptr_eq (&N_70, tree.root);
  ck_assert_ptr_eq (N_50.parent, &N_70);
  ck_assert_ptr_eq (N_70.right, &N_85);
  ck_assert_ptr_eq (N_70.left, &N_50);
  ck_assert_ptr_null (N_80.right);
  ck_assert_ptr_null (N_80.left);
  ck_assert_ptr_eq (N_80.parent, &N_85);
  ck_assert_ptr_eq (N_90.parent, &N_85);
  ck_assert_ptr_null (N_80.right);
  ck_assert_ptr_null (N_90.left);
  ck_assert_ptr_eq (N_85.right, &N_90);
  ck_assert_ptr_eq (N_85.left, &N_80);
  ck_assert_ptr_eq (N_85.parent, &N_70);
  ck_assert_ptr_eq (N_95.parent, &N_90);
  ck_assert_ptr_eq (N_90.right, &N_95);
  ck_assert_ptr_null (N_95.left);
}
END_TEST

START_TEST (test_insert_13)
{
  enum { N = 4 };
  const int values[N] = {10, 20, 30, 40};
  struct itree_node *nodes[N] = {&N_10, &N_20, &N_30, &N_40};
  interval_tree_init (&tree);
  for (int i = 0; i < N; ++i)
    itree_insert (&tree, nodes[i], values[i], values[i]);

  ck_assert_ptr_eq (tree.root, &N_20);
  ck_assert_ptr_eq (N_20.left, &N_10);
  ck_assert_ptr_eq (N_20.right, &N_30);
  ck_assert_ptr_eq (N_30.right, &N_40);
  ck_assert (! N_10.red);
  ck_assert (! N_20.red);
  ck_assert (! N_30.red);
  ck_assert (N_40.red);
}
END_TEST

START_TEST (test_insert_14)
{
  enum { N = 3 };
  struct itree_node nodes[N];
  interval_tree_init (&tree);

  for (int i = 0; i < N; ++i)
    itree_insert (&tree, &nodes[i], 10, 10);
  for (int i = 0; i < N; ++i)
    ck_assert (interval_tree_contains (&tree, &nodes[i]));
}
END_TEST


/* +===================================================================================+
 * | Remove
 * +===================================================================================+ */

/* Creating proper test trees for the formal tests via insertions is
   way too tedious, so we just fake it and only test the
   fix-routine.  */
static void
test_remove1_setup (void)
{
  interval_tree_init (&tree);
  tree.root = &B;
  A.parent = &B; B.parent = NULL; C.parent = &D; D.parent = &B; E.parent = &D;
  A.left = A.right = C.left = C.right = E.left = E.right = NULL;
  B.left = &A; B.right = &D;
  D.left = &C; D.right = &E;
  A.offset = B.offset = C.offset = D.offset = E.offset = 0;
  A.otick = B.otick = C.otick = D.otick = E.otick = tree.otick;
}

/* 1.a -> 2.a
 *                [B]
 *               /    \
 *             [A]    (D)
 *                    /  \
 *                 [C]   [E]
 */

START_TEST (test_remove_1)
{
  B.red = A.red = C.red = E.red = false;
  D.red = true;
  interval_tree_remove_fix (&tree, &A, &B);

  ck_assert (! A.red);
  ck_assert (! B.red);
  ck_assert (C.red);
  ck_assert (! D.red);
  ck_assert (! E.red);
  ck_assert_ptr_eq (A.parent, &B);
  ck_assert_ptr_eq (B.left, &A);
  ck_assert_ptr_eq (B.right, &C);
  ck_assert_ptr_eq (C.parent, &B);
  ck_assert_ptr_eq (E.parent, &D);
  ck_assert_ptr_eq (D.right, &E);
  ck_assert_ptr_eq (D.left, &B);
  ck_assert_ptr_eq (tree.root, &D);
}
END_TEST

/* 2.a */
START_TEST (test_remove_2)
{
  B.red = D.red = A.red = C.red = E.red = false;
  interval_tree_remove_fix (&tree, &A, &B);

  ck_assert (! A.red);
  ck_assert (! B.red);
  ck_assert (! C.red);
  ck_assert (D.red);
  ck_assert (! E.red);
  ck_assert_ptr_eq (A.parent, &B);
  ck_assert_ptr_eq (B.left, &A);
  ck_assert_ptr_eq (B.right, &D);
  ck_assert_ptr_eq (C.parent, &D);
  ck_assert_ptr_eq (E.parent, &D);
  ck_assert_ptr_eq (tree.root, &B);
}
END_TEST

/* 3.a -> 4.a */
START_TEST (test_remove_3)
{
  D.red = A.red = E.red = false;
  B.red = C.red = true;
  interval_tree_remove_fix (&tree, &A, &B);

  ck_assert (! A.red);
  ck_assert (! B.red);
  ck_assert (! C.red);
  ck_assert (! D.red);
  ck_assert (! E.red);
  ck_assert_ptr_eq (A.parent, &B);
  ck_assert_ptr_eq (B.left, &A);
  ck_assert_ptr_null (B.right);
  ck_assert_ptr_eq (&C, tree.root);
  ck_assert_ptr_eq (C.left, &B);
  ck_assert_ptr_eq (C.right, &D);
  ck_assert_ptr_eq (E.parent, &D);
  ck_assert_ptr_null (D.left);
}
END_TEST

/* 4.a */
START_TEST (test_remove_4)
{
  B.red = C.red = E.red = true;
  A.red = D.red = false;
  interval_tree_remove_fix (&tree, &A, &B);

  ck_assert (! A.red);
  ck_assert (! B.red);
  ck_assert (C.red);
  ck_assert (! D.red);
  ck_assert (! E.red);
  ck_assert_ptr_eq (A.parent, &B);
  ck_assert_ptr_eq (B.left, &A);
  ck_assert_ptr_eq (B.right, &C);
  ck_assert_ptr_eq (C.parent, &B);
  ck_assert_ptr_eq (E.parent, &D);
  ck_assert_ptr_eq (tree.root, &D);
}
END_TEST



/* These are the mirrored cases.  */

static void
test_remove2_setup (void)
{
  interval_tree_init (&tree);
  tree.root = &B;
  A.parent = &B; B.parent = NULL; C.parent = &D; D.parent = &B; E.parent = &D;
  A.right = A.left = C.right = C.left = E.right = E.left = NULL;
  B.right = &A; B.left = &D;
  D.right = &C; D.left = &E;
}

/* 1.b -> 2.b
 *                [B]
 *               /    \
 *             [A]    (D)
 *                    /  \
 *                 [C]   [E]
 */

START_TEST (test_remove_5)
{
  B.red = A.red = C.red = E.red = false;
  D.red = true;
  interval_tree_remove_fix (&tree, &A, &B);

  ck_assert (! A.red);
  ck_assert (! B.red);
  ck_assert (C.red);
  ck_assert (! D.red);
  ck_assert (! E.red);
  ck_assert_ptr_eq (A.parent, &B);
  ck_assert_ptr_eq (B.right, &A);
  ck_assert_ptr_eq (B.left, &C);
  ck_assert_ptr_eq (C.parent, &B);
  ck_assert_ptr_eq (E.parent, &D);
  ck_assert_ptr_eq (D.left, &E);
  ck_assert_ptr_eq (D.right, &B);
  ck_assert_ptr_eq (tree.root, &D);
}
END_TEST

/* 2.b */
START_TEST (test_remove_6)
{
  B.red = D.red = A.red = C.red = E.red = false;
  interval_tree_remove_fix (&tree, &A, &B);

  ck_assert (! A.red);
  ck_assert (! B.red);
  ck_assert (! C.red);
  ck_assert (D.red);
  ck_assert (! E.red);
  ck_assert_ptr_eq (A.parent, &B);
  ck_assert_ptr_eq (B.right, &A);
  ck_assert_ptr_eq (B.left, &D);
  ck_assert_ptr_eq (C.parent, &D);
  ck_assert_ptr_eq (E.parent, &D);
  ck_assert_ptr_eq (tree.root, &B);
}
END_TEST

/* 3.b -> 4.b */
START_TEST (test_remove_7)
{
  D.red = A.red = E.red = false;
  B.red = C.red = true;
  interval_tree_remove_fix (&tree, &A, &B);

  ck_assert (! A.red);
  ck_assert (! B.red);
  ck_assert (! C.red);
  ck_assert (! D.red);
  ck_assert (! E.red);
  ck_assert_ptr_eq (A.parent, &B);
  ck_assert_ptr_eq (B.right, &A);
  ck_assert_ptr_null (B.left);
  ck_assert_ptr_eq (&C, tree.root);
  ck_assert_ptr_eq (C.right, &B);
  ck_assert_ptr_eq (C.left, &D);
  ck_assert_ptr_eq (E.parent, &D);
  ck_assert_ptr_null (D.right);
}
END_TEST

/* 4.b */
START_TEST (test_remove_8)
{
  B.red = C.red = E.red = true;
  A.red = D.red = false;
  interval_tree_remove_fix (&tree, &A, &B);

  ck_assert (! A.red);
  ck_assert (! B.red);
  ck_assert (C.red);
  ck_assert (! D.red);
  ck_assert (! E.red);
  ck_assert_ptr_eq (A.parent, &B);
  ck_assert_ptr_eq (B.right, &A);
  ck_assert_ptr_eq (B.left, &C);
  ck_assert_ptr_eq (C.parent, &B);
  ck_assert_ptr_eq (E.parent, &D);
  ck_assert_ptr_eq (tree.root, &D);
}
END_TEST

START_TEST (test_remove_9)
{
  enum { N = 4 };
  const int values[N] = {10, 20, 30, 40};
  struct itree_node *nodes[N] = {&N_10, &N_20, &N_30, &N_40};
  interval_tree_init (&tree);
  for (int i = 0; i < N; ++i)
    itree_insert (&tree, nodes[i], values[i], values[i]);

  ck_assert (tree.root == &N_20);
  ck_assert (N_20.left == &N_10);
  ck_assert (N_20.right == &N_30);
  ck_assert (N_30.right == &N_40);
  ck_assert (! N_20.red);
  ck_assert (! N_10.red);
  ck_assert (! N_30.red);
  ck_assert (N_40.red);

  itree_remove (&tree, &N_10);

  ck_assert_ptr_eq (tree.root, &N_30);
  ck_assert_ptr_null (N_30.parent);
  ck_assert_ptr_eq (N_30.left, &N_20);
  ck_assert_ptr_eq (N_30.right, &N_40);
  ck_assert (! N_20.red);
  ck_assert (! N_30.red);
  ck_assert (! N_40.red);
}
END_TEST

static void
shuffle (int *index, int n)
{
  for (int i = n - 1; i >= 0; --i)
    {
      int j = random () % (i + 1);
      int h = index[j];
      index[j] = index[i];
      index[i] = h;
    }
}

START_TEST (test_remove_10)
{
  enum { N = 3 };
  int index[N];
  for (int i = 0; i < N; ++i)
    index[i] = i;
  srand (42);
  shuffle (index, N);

  interval_tree_init (&tree);
  struct itree_node nodes[N];
  for (int i = 0; i < N; ++i)
    {
      ptrdiff_t pos = (i + 1) * 10;
      itree_insert (&tree, &nodes[index[i]], pos, pos + 1);
    }

  shuffle (index, N);
  for (int i = 0; i < N; ++i)
    {
      ck_assert (interval_tree_contains (&tree, &nodes[index[i]]));
      itree_remove (&tree, &nodes[index[i]]);
    }
  ck_assert_ptr_null (tree.root);
  ck_assert_int_eq (tree.size, 0);
}
END_TEST


/* +===================================================================================+
 * | Generator
 * +===================================================================================+ */

START_TEST (test_generator_1)
{
  struct itree_node node, *n;
  struct itree_iterator *g;
  interval_tree_init (&tree);

  itree_insert (&tree, &node, 10, 20);
  g = itree_iterator_start (&tree, 0, 30, ITREE_ASCENDING, NULL, 0);
  n = itree_iterator_next (g);
  ck_assert_ptr_eq (n, &node);
  ck_assert_int_eq (n->begin, 10);
  ck_assert_int_eq (n->end, 20);
  ck_assert_ptr_null (itree_iterator_next (g));
  ck_assert_ptr_null (itree_iterator_next (g));
  ck_assert_ptr_null (itree_iterator_next (g));
  itree_iterator_finish (g);

  g = itree_iterator_start (&tree, 30, 50, ITREE_ASCENDING, NULL, 0);
  ck_assert_ptr_null (itree_iterator_next (g));
  ck_assert_ptr_null (itree_iterator_next (g));
  ck_assert_ptr_null (itree_iterator_next (g));
  itree_iterator_finish (g);
}
END_TEST

static void
test_check_generator (struct itree_tree *tree,
                      ptrdiff_t begin, ptrdiff_t end,
                      int n, ...)
{
  va_list ap;
  struct itree_iterator *g =
    itree_iterator_start (tree, begin, end, ITREE_ASCENDING, NULL, 0);

  va_start (ap, n);
  for (int i = 0; i < n; ++i)
    {
      struct itree_node *node = itree_iterator_next (g);
      ck_assert_ptr_nonnull (node);
      ck_assert_int_eq (node->begin, va_arg (ap, ptrdiff_t));
    }
  va_end (ap);
  ck_assert_ptr_null (itree_iterator_next (g));
  ck_assert_ptr_null (itree_iterator_next (g));
  itree_iterator_finish (g);
}

START_TEST (test_generator_2)
{
  interval_tree_init (&tree);
  struct itree_node nodes[3];
  for (int i = 0; i < 3; ++i)
    itree_insert (&tree, &nodes[i], 10 * (i + 1), 10 * (i + 2));

  test_check_generator (&tree, 0, 50, 3,
                        10, 20, 30);
  test_check_generator (&tree, 0, 10, 0);
  test_check_generator (&tree, 40, 50, 0);
  test_check_generator (&tree, 15, 35, 3,
                        10, 20, 30);
  test_check_generator (&tree, -100, -50, 0);
  test_check_generator (&tree, -100, -50, 0);
  test_check_generator (&tree, 100, 50, 0);
  test_check_generator (&tree, 100, 150, 0);
  test_check_generator (&tree, 0, 0, 0);
  test_check_generator (&tree, 40, 40, 0);
  test_check_generator (&tree, 30, 30, 0);
  test_check_generator (&tree, 35, 35, 1,
                        30);
}
END_TEST

static void
test_create_tree (struct itree_node *nodes, int n, bool doshuffle)
{
  int *index = calloc (n, sizeof (int));
  for (int i = 0; i < n; ++i)
    index[i] = i;
  if (doshuffle)
    {
      srand (42);
      shuffle (index, n);
    }

  interval_tree_init (&tree);
  for (int i = 0; i < n; ++i)
    {
      struct itree_node *node = &nodes[index[i]];
      itree_insert (&tree, node, node->begin, node->end);
    }
  free (index);
}

START_TEST (test_generator_3)
{
  enum { N = 3 };
  struct itree_node nodes[N] = {{.begin = 10, .end = 10},
                                {.begin = 10, .end = 10},
                                {.begin = 10, .end = 10}};
  test_create_tree (nodes, N, true);
  test_check_generator (&tree, 0, 10, 0);
  test_check_generator (&tree, 10, 10, 3,
                        10, 10, 10);
  test_check_generator (&tree, 10, 20, 3,
                        10, 10, 10);
}
END_TEST

START_TEST (test_generator_5)
{
  enum { N = 4 };
  struct itree_node nodes[N] = {{.begin = 10, .end = 30},
                                {.begin = 20, .end = 40},
                                {.begin = 30, .end = 50},
                                {.begin = 40, .end = 60}};
  test_create_tree (nodes, N, false);
  struct itree_iterator *g =
    itree_iterator_start (&tree, 0, 100, ITREE_PRE_ORDER, NULL, 0);
  for (int i = 0; i < N; ++i)
    {
      struct itree_node *n = itree_iterator_next (g);
      ck_assert_ptr_nonnull (n);
      switch (i)
        {
        case 0: ck_assert_int_eq (20, n->begin); break;
        case 1: ck_assert_int_eq (10, n->begin); break;
        case 2: ck_assert_int_eq (30, n->begin); break;
        case 3: ck_assert_int_eq (40, n->begin); break;
        }
    }
  itree_iterator_finish (g);
}
END_TEST

START_TEST (test_generator_6)
{
  enum { N = 4 };
  struct itree_node nodes[N] = {{.begin = 10, .end = 30},
                                {.begin = 20, .end = 40},
                                {.begin = 30, .end = 50},
                                {.begin = 40, .end = 60}};
  test_create_tree (nodes, N, true);
  struct itree_iterator *g =
    itree_iterator_start (&tree, 0, 100, ITREE_ASCENDING, NULL, 0);
  for (int i = 0; i < N; ++i)
    {
      struct itree_node *n = itree_iterator_next (g);
      ck_assert_ptr_nonnull (n);
      switch (i)
        {
        case 0: ck_assert_int_eq (10, n->begin); break;
        case 1: ck_assert_int_eq (20, n->begin); break;
        case 2: ck_assert_int_eq (30, n->begin); break;
        case 3: ck_assert_int_eq (40, n->begin); break;
        }
    }
  itree_iterator_finish (g);
}
END_TEST

START_TEST (test_generator_7)
{
  enum { N = 4 };
  struct itree_node nodes[N] = {{.begin = 10, .end = 30},
                                {.begin = 20, .end = 40},
                                {.begin = 30, .end = 50},
                                {.begin = 40, .end = 60}};
  test_create_tree (nodes, N, true);
  struct itree_iterator *g =
    itree_iterator_start (&tree, 0, 100, ITREE_DESCENDING, NULL, 0);
  for (int i = 0; i < N; ++i)
    {
      struct itree_node *n = itree_iterator_next (g);
      ck_assert_ptr_nonnull (n);
      switch (i)
        {
        case 0: ck_assert_int_eq (40, n->begin); break;
        case 1: ck_assert_int_eq (30, n->begin); break;
        case 2: ck_assert_int_eq (20, n->begin); break;
        case 3: ck_assert_int_eq (10, n->begin); break;
        }
    }
  itree_iterator_finish (g);
}
END_TEST

START_TEST (test_generator_8)
{
  enum { N = 2 };
  struct itree_node nodes[N] = {{.begin = 20, .end = 30},
                                {.begin = 40, .end = 50}};
  test_create_tree (nodes, N, false);
  struct itree_iterator *g =
    itree_iterator_start (&tree, 1, 60, ITREE_DESCENDING, NULL, 0);
  struct itree_node *n = itree_iterator_next (g);
  ck_assert_int_eq (n->begin, 40);
  itree_iterator_narrow (g, 50, 60);
  n = itree_iterator_next (g);
  ck_assert_ptr_null (n);
  itree_iterator_finish (g);
}
END_TEST

START_TEST (test_generator_9)
{
  enum { N = 2 };
  struct itree_node nodes[N] = {{.begin = 25, .end = 25},
                                {.begin = 20, .end = 30}};
  test_create_tree (nodes, N, false);
  struct itree_iterator *g =
    itree_iterator_start (&tree, 1, 30, ITREE_DESCENDING, NULL, 0);
  struct itree_node *n = itree_iterator_next (g);
  ck_assert_int_eq (n->begin, 25);
  itree_iterator_narrow (g, 25, 30);
  n = itree_iterator_next (g);
  ck_assert_int_eq (n->begin, 20);
  itree_iterator_finish (g);
}
END_TEST


/* +===================================================================================+
 * | Insert Gap
 * +===================================================================================+ */

static struct itree_tree gap_tree;
static struct itree_node gap_node;

#define N_BEG (itree_node_begin (&gap_tree, &gap_node))
#define N_END (itree_node_end (&gap_tree, &gap_node))

static void
test_setup_gap_node (ptrdiff_t begin, ptrdiff_t end,
                     bool front_advance, bool rear_advance)
{
  interval_tree_init (&gap_tree);
  gap_node.front_advance = front_advance;
  gap_node.rear_advance = rear_advance;
  itree_insert (&gap_tree, &gap_node, begin, end);
}

static void
test_setup_gap_node_noadvance (ptrdiff_t begin, ptrdiff_t end)
{
  test_setup_gap_node (begin, end, false, false);
}

START_TEST (test_gap_insert_1)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_insert_gap (&gap_tree, 100 + 10, 20, false);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 200 + 20);
}
END_TEST

START_TEST (test_gap_insert_2)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_insert_gap (&gap_tree, 300, 10, false);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 200);
}
END_TEST

START_TEST (test_gap_insert_3)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_insert_gap (&gap_tree, 0, 15, false);
  ck_assert_int_eq (N_BEG, 100 + 15);
  ck_assert_int_eq (N_END, 200 + 15);
}
END_TEST

START_TEST (test_gap_insert_4)
{
  test_setup_gap_node (100, 200, true, false);
  itree_insert_gap (&gap_tree, 100, 20, false);
  ck_assert_int_eq (N_BEG, 100 + 20);
  ck_assert_int_eq (N_END, 200 + 20);

}
END_TEST

START_TEST (test_gap_insert_5)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_insert_gap (&gap_tree, 100, 20, false);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 200 + 20);

}
END_TEST

START_TEST (test_gap_insert_6)
{
  test_setup_gap_node (100, 200, false, true);
  itree_insert_gap (&gap_tree, 200, 20, false);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 200 + 20);

}
END_TEST

START_TEST (test_gap_insert_7)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_insert_gap (&gap_tree, 200, 20, false);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 200);

}
END_TEST

START_TEST (test_gap_insert_8)
{
  test_setup_gap_node (100, 100, true, true);
  itree_insert_gap (&gap_tree, 100, 20, false);
  ck_assert_int_eq (N_BEG, 100 + 20);
  ck_assert_int_eq (N_END, 100 + 20);

}
END_TEST

START_TEST (test_gap_insert_9)
{
  test_setup_gap_node (100, 100, false, true);
  itree_insert_gap (&gap_tree, 100, 20, false);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 100 + 20);

}
END_TEST

START_TEST (test_gap_insert_10)
{
  test_setup_gap_node (100, 100, true, false);
  itree_insert_gap (&gap_tree, 100, 20, false);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 100);

}
END_TEST

START_TEST (test_gap_insert_11)
{
  test_setup_gap_node_noadvance (100, 100);
  itree_insert_gap (&gap_tree, 100, 20, false);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 100);

}
END_TEST


/* +===================================================================================+
 * | Delete Gap
 * +===================================================================================+ */

START_TEST (test_gap_delete_1)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_delete_gap (&gap_tree, 100 + 10, 20);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 200 - 20);

}
END_TEST

START_TEST (test_gap_delete_2)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_delete_gap (&gap_tree, 200 + 10, 20);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 200);

}
END_TEST

START_TEST (test_gap_delete_3)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_delete_gap (&gap_tree, 200, 20);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 200);

}
END_TEST

START_TEST (test_gap_delete_4)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_delete_gap (&gap_tree, 100 - 20, 20);
  ck_assert_int_eq (N_BEG, 100 - 20);
  ck_assert_int_eq (N_END, 200 - 20);

}
END_TEST

START_TEST (test_gap_delete_5)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_delete_gap (&gap_tree, 70, 20);
  ck_assert_int_eq (N_BEG, 100 - 20);
  ck_assert_int_eq (N_END, 200 - 20);

}
END_TEST

START_TEST (test_gap_delete_6)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_delete_gap (&gap_tree, 80, 100);
  ck_assert_int_eq (N_BEG, 80);
  ck_assert_int_eq (N_END, 100);
}
END_TEST

START_TEST (test_gap_delete_7)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_delete_gap (&gap_tree, 120, 100);
  ck_assert_int_eq (N_BEG, 100);
  ck_assert_int_eq (N_END, 120);
}
END_TEST

START_TEST (test_gap_delete_8)
{
  test_setup_gap_node_noadvance (100, 200);
  itree_delete_gap (&gap_tree, 100 - 20, 200 + 20);
  ck_assert_int_eq (N_BEG, 100 - 20);
  ck_assert_int_eq (N_END, 100 - 20);

}
END_TEST



static Suite *
basic_suite ()
{
  Suite *s = suite_create ("basic");

  TCase *tc = tcase_create ("insert1");
  tcase_add_checked_fixture (tc, test_insert1_setup, NULL);
  tcase_add_test (tc, test_insert_1);
  tcase_add_test (tc, test_insert_2);
  tcase_add_test (tc, test_insert_3);
  tcase_add_test (tc, test_insert_4);
  tcase_add_test (tc, test_insert_5);
  tcase_add_test (tc, test_insert_6);
  suite_add_tcase (s, tc);

  tc = tcase_create ("insert2");
  tcase_add_checked_fixture (tc, test_insert2_setup, NULL);
  tcase_add_test (tc, test_insert_7);
  tcase_add_test (tc, test_insert_8);
  tcase_add_test (tc, test_insert_9);
  tcase_add_test (tc, test_insert_10);
  tcase_add_test (tc, test_insert_11);
  tcase_add_test (tc, test_insert_12);
  suite_add_tcase (s, tc);

  tc = tcase_create ("insert3");
  tcase_add_test (tc, test_insert_13);
  tcase_add_test (tc, test_insert_14);
  suite_add_tcase (s, tc);

  tc = tcase_create ("remove1");
  tcase_add_checked_fixture (tc, test_remove1_setup, NULL);
  tcase_add_test (tc, test_remove_1);
  tcase_add_test (tc, test_remove_2);
  tcase_add_test (tc, test_remove_3);
  tcase_add_test (tc, test_remove_4);
  suite_add_tcase (s, tc);

  tc = tcase_create ("remove2");
  tcase_add_checked_fixture (tc, test_remove2_setup, NULL);
  tcase_add_test (tc, test_remove_5);
  tcase_add_test (tc, test_remove_6);
  tcase_add_test (tc, test_remove_7);
  tcase_add_test (tc, test_remove_8);
  suite_add_tcase (s, tc);

  tc = tcase_create ("remove3");
  tcase_add_test (tc, test_remove_9);
  tcase_add_test (tc, test_remove_10);
  suite_add_tcase (s, tc);

  tc = tcase_create ("generator");
  tcase_add_test (tc, test_generator_1);
  tcase_add_test (tc, test_generator_2);
  tcase_add_test (tc, test_generator_3);
  tcase_add_test (tc, test_generator_5);
  tcase_add_test (tc, test_generator_6);
  tcase_add_test (tc, test_generator_7);
  tcase_add_test (tc, test_generator_8);
  tcase_add_test (tc, test_generator_9);
  suite_add_tcase (s, tc);

  tc = tcase_create ("insert_gap");
  tcase_add_test (tc, test_gap_insert_1);
  tcase_add_test (tc, test_gap_insert_2);
  tcase_add_test (tc, test_gap_insert_3);
  tcase_add_test (tc, test_gap_insert_4);
  tcase_add_test (tc, test_gap_insert_5);
  tcase_add_test (tc, test_gap_insert_6);
  tcase_add_test (tc, test_gap_insert_7);
  tcase_add_test (tc, test_gap_insert_8);
  tcase_add_test (tc, test_gap_insert_9);
  tcase_add_test (tc, test_gap_insert_10);
  tcase_add_test (tc, test_gap_insert_11);
  suite_add_tcase (s, tc);

  tc = tcase_create ("delete_gap");
  tcase_add_test (tc, test_gap_delete_1);
  tcase_add_test (tc, test_gap_delete_2);
  tcase_add_test (tc, test_gap_delete_3);
  tcase_add_test (tc, test_gap_delete_4);
  tcase_add_test (tc, test_gap_delete_5);
  tcase_add_test (tc, test_gap_delete_6);
  tcase_add_test (tc, test_gap_delete_7);
  tcase_add_test (tc, test_gap_delete_8);
  suite_add_tcase (s, tc);

  return s;
}

int
main (void)
{
  Suite *s = basic_suite ();
  SRunner *sr = srunner_create (s);

  init_itree ();
  srunner_run_all (sr, CK_ENV);
  int nfailed = srunner_ntests_failed (sr);
  srunner_free (sr);
  return (nfailed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
}