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

/* Keep this in sync with gsequence.c !!! */
typedef struct _GSequenceNode GSequenceNode;

struct _GSequence
{
  GSequenceNode *       end_node;
  GDestroyNotify        data_destroy_notify;
  gboolean              access_prohibited;
  GSequence *           real_sequence;
};

struct _GSequenceNode
{
  guint                 n_nodes;
  GSequenceNode *       parent;
  GSequenceNode *       left;
  GSequenceNode *       right;
  gpointer              data;
};

static guint
get_priority (GSequenceNode *node)
{
  guint key = GPOINTER_TO_UINT (node);

  key = (key << 15) - key - 1;
  key = key ^ (key >> 12);
  key = key + (key << 2);
  key = key ^ (key >> 4);
  key = key + (key << 3) + (key << 11);
  key = key ^ (key >> 16);

  return key? key : 1;
}

static void
check_node (GSequenceNode *node)
{
  if (node)
    {
      g_assert (node->parent != node);
      if (node->parent)
        g_assert (node->parent->left == node || node->parent->right == node);
      g_assert (node->n_nodes == 1 + (node->left ? node->left->n_nodes : 0) + (node->right ? node->right->n_nodes : 0));
      if (node->left)
          g_assert (get_priority (node) >= get_priority (node->left));
      if (node->right)
          g_assert (get_priority (node) >= get_priority (node->right));
      check_node (node->left);
      check_node (node->right);
    }
}

static void
g_sequence_check (GSequence *seq)
{
  GSequenceNode *node = seq->end_node;

  while (node->parent)
    node = node->parent;

  check_node (node);

  while (node->right)
    node = node->right;

  g_assert (seq->end_node == node);
  g_assert (node->data == seq);

}


enum {
  NEW, FREE, GET_LENGTH, FOREACH, FOREACH_RANGE, SORT, SORT_ITER,

  /* Getting iters */
  GET_BEGIN_ITER, GET_END_ITER, GET_ITER_AT_POS, APPEND, PREPEND,
  INSERT_BEFORE, MOVE, SWAP, INSERT_SORTED, INSERT_SORTED_ITER, SORT_CHANGED,
  SORT_CHANGED_ITER, REMOVE, REMOVE_RANGE, MOVE_RANGE, SEARCH, SEARCH_ITER,
  LOOKUP, LOOKUP_ITER,

  /* dereferencing */
  GET, SET,

  /* operations on GSequenceIter * */
  ITER_IS_BEGIN, ITER_IS_END, ITER_NEXT, ITER_PREV, ITER_GET_POSITION,
  ITER_MOVE, ITER_GET_SEQUENCE,

  /* search */
  ITER_COMPARE, RANGE_GET_MIDPOINT,
  N_OPS
};

typedef struct SequenceInfo
{
  GQueue *      queue;
  GSequence *   sequence;
  guint         n_items;
} SequenceInfo;

typedef struct
{
  SequenceInfo *seq;
  int             number;
} Item;

void g_sequence_check (GSequence *sequence);

static Item *
fix_pointer (gconstpointer data)
{
  return (Item *)((char *)data - 1);
}

static Item *
get_item (GSequenceIter *iter)
{
  return fix_pointer (g_sequence_get (iter));
}

static void
check_integrity (SequenceInfo *info)
{
  GList *list;
  GSequenceIter *iter;
  int i;

  g_sequence_check (info->sequence);

#if 0
  if (g_sequence_get_length (info->sequence) != info->n_items)
    g_printerr ("%d %d\n",
             g_sequence_get_length (info->sequence), info->n_items);
#endif
  g_assert (info->n_items == g_queue_get_length (info->queue));
  g_assert ((guint) g_sequence_get_length (info->sequence) == info->n_items);

  iter = g_sequence_get_begin_iter (info->sequence);
  list = info->queue->head;
  i = 0;
  while (iter != g_sequence_get_end_iter (info->sequence))
    {
      Item *item;
      g_assert (list->data == iter);
      item = get_item (list->data);
      g_assert (item->seq == info);

      iter = g_sequence_iter_next (iter);
      list = list->next;
      i++;
    }

  g_assert (info->n_items == g_queue_get_length (info->queue));
  g_assert ((guint) g_sequence_get_length (info->sequence) == info->n_items);
}

static gpointer
new_item (SequenceInfo *seq)
{
  Item *item = g_new (Item, 1);
  seq->n_items++;
  item->seq = seq;
  item->number = g_random_int ();

  /* There have been bugs in the past where the GSequence would
   * dereference the user pointers. This will make sure such
   * behavior causes crashes
   */
  return ((char *)item + 1);
}

static void
free_item (gpointer data)
{
  Item *item = fix_pointer (data);
  item->seq->n_items--;
  g_free (item);
}

static void
seq_foreach (gpointer data,
             gpointer user_data)
{
  Item *item = fix_pointer (data);
  GList **link = user_data;
  GSequenceIter *iter;

  g_assert (*link != NULL);

  iter = (*link)->data;

  g_assert (get_item (iter) == item);

  item->number = g_random_int();

  *link = (*link)->next;
}

static gint
simple_items_cmp (gconstpointer a,
	          gconstpointer b,
	          gpointer data)
{
  const Item *item_a = fix_pointer (a);
  const Item *item_b = fix_pointer (b);

  if (item_a->number > item_b->number)
    return +1;
  else if (item_a->number < item_b->number)
    return -1;
  else
    return 0;
}

static gint
simple_iters_cmp (gconstpointer a,
	          gconstpointer b,
	          gpointer data)
{
  GSequence *seq = data;
  GSequenceIter *iter_a = (GSequenceIter *)a;
  GSequenceIter *iter_b = (GSequenceIter *)b;
  gpointer item_a = g_sequence_get (iter_a);
  gpointer item_b = g_sequence_get (iter_b);

  if (seq)
    {
      g_assert (g_sequence_iter_get_sequence (iter_a) == seq);
      g_assert (g_sequence_iter_get_sequence (iter_b) == seq);
    }

  return simple_items_cmp (item_a, item_b, data);
}

static gint
compare_items (gconstpointer a,
               gconstpointer b,
               gpointer      data)
{
  const Item *item_a = fix_pointer (a);
  const Item *item_b = fix_pointer (b);

  if (item_a->number < item_b->number)
    {
      return -1;
    }
  else if (item_a->number == item_b->number)
    {
      /* Force an arbitrary order on the items
       * We have to do this, since g_queue_insert_sorted() and
       * g_sequence_insert_sorted() do not agree on the exact
       * position the item is inserted if the new item is
       * equal to an existing one.
       */
      if (item_a < item_b)
        return -1;
      else if (item_a == item_b)
        return 0;
      else
        return 1;
    }
  else
    {
      return 1;
    }
}

static void
check_sorted (SequenceInfo *info)
{
  GList *list;
  int last;
  GSequenceIter *last_iter;

  check_integrity (info);

  last = G_MININT;
  last_iter = NULL;
  for (list = info->queue->head; list != NULL; list = list->next)
    {
      GSequenceIter *iter = list->data;
      Item *item = get_item (iter);

      g_assert (item->number >= last);
      /* Check that the ordering is the same as that of the queue,
       * ie. that the sort is stable
       */
      if (last_iter)
        g_assert (iter == g_sequence_iter_next (last_iter));

      last = item->number;
      last_iter = iter;
    }
}

static gint
compare_iters (gconstpointer a,
               gconstpointer b,
               gpointer      data)
{
  GSequence *seq = data;
  GSequenceIter *iter_a = (GSequenceIter *)a;
  GSequenceIter *iter_b = (GSequenceIter *)b;
  /* compare_items() will fix up the pointers */
  Item *item_a = g_sequence_get (iter_a);
  Item *item_b = g_sequence_get (iter_b);

  if (seq)
    {
      g_assert (g_sequence_iter_get_sequence (iter_a) == seq);
      g_assert (g_sequence_iter_get_sequence (iter_b) == seq);
    }

  return compare_items (item_a, item_b, data);
}

/* A version of g_queue_link_index() that treats NULL as just
 * beyond the queue
 */
static int
queue_link_index (SequenceInfo *seq, GList *link)
{
  if (link)
    return g_queue_link_index (seq->queue, link);
  else
    return g_queue_get_length (seq->queue);
}

static void
get_random_range (SequenceInfo *seq,
                  GSequenceIter **begin_iter,
                  GSequenceIter **end_iter,
                  GList **begin_link,
                  GList **end_link)
{
  int length = g_queue_get_length (seq->queue);
  int b = g_random_int_range (0, length + 1);
  int e = g_random_int_range (b, length + 1);

  g_assert (length == g_sequence_get_length (seq->sequence));

  if (begin_iter)
    *begin_iter = g_sequence_get_iter_at_pos (seq->sequence, b);
  if (end_iter)
    *end_iter = g_sequence_get_iter_at_pos (seq->sequence, e);
  if (begin_link)
    *begin_link = g_queue_peek_nth_link (seq->queue, b);
  if (end_link)
    *end_link = g_queue_peek_nth_link (seq->queue, e);
  if (begin_iter && begin_link)
    {
      g_assert (
                queue_link_index (seq, *begin_link) ==
                g_sequence_iter_get_position (*begin_iter));
    }
  if (end_iter && end_link)
    {
      g_assert (
                queue_link_index (seq, *end_link) ==
                g_sequence_iter_get_position (*end_iter));
    }
}

static gint
get_random_position (SequenceInfo *seq)
{
  int length = g_queue_get_length (seq->queue);

  g_assert (length == g_sequence_get_length (seq->sequence));

  return g_random_int_range (-2, length + 5);
}

static GSequenceIter *
get_random_iter (SequenceInfo  *seq,
                 GList        **link)
{
  GSequenceIter *iter;
  int pos = get_random_position (seq);
  if (link)
    *link = g_queue_peek_nth_link (seq->queue, pos);
  iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
  if (link)
    g_assert (queue_link_index (seq, *link) == g_sequence_iter_get_position (iter));
  return iter;
}

static void
dump_info (SequenceInfo *seq)
{
#if 0
  GSequenceIter *iter;
  GList *list;

  iter = g_sequence_get_begin_iter (seq->sequence);
  list = seq->queue->head;

  while (iter != g_sequence_get_end_iter (seq->sequence))
    {
      Item *item = get_item (iter);
      g_printerr ("%p  %p    %d\n", list->data, iter, item->number);

      iter = g_sequence_iter_next (iter);
      list = list->next;
    }
#endif
}

static void
run_random_tests (gconstpointer d)
{
  guint32 seed = GPOINTER_TO_UINT (d);
#define N_ITERATIONS 60000
#define N_SEQUENCES 8
#define N_TIMES 24

  SequenceInfo sequences[N_SEQUENCES];
  int k;

#if 0
  g_printerr ("    seed: %u\n", seed);
#endif

  g_random_set_seed (seed);

  for (k = 0; k < N_SEQUENCES; ++k)
    {
      sequences[k].queue = g_queue_new ();
      sequences[k].sequence = g_sequence_new (free_item);
      sequences[k].n_items = 0;
    }

#define RANDOM_SEQUENCE() &(sequences[g_random_int_range (0, N_SEQUENCES)])

  for (k = 0; k < N_ITERATIONS; ++k)
    {
      int i;
      SequenceInfo *seq = RANDOM_SEQUENCE();
      int op = g_random_int_range (0, N_OPS);

#if 0
      g_printerr ("%d on %p\n", op, seq);
#endif

      switch (op)
        {
        case NEW:
        case FREE:
          {
            g_queue_free (seq->queue);
            g_sequence_free (seq->sequence);

            g_assert (seq->n_items == 0);

            seq->queue = g_queue_new ();
            seq->sequence = g_sequence_new (free_item);

            check_integrity (seq);
          }
          break;
        case GET_LENGTH:
          {
            int slen = g_sequence_get_length (seq->sequence);
            int qlen = g_queue_get_length (seq->queue);

            g_assert (slen == qlen);
          }
          break;
        case FOREACH:
          {
            GList *link = seq->queue->head;
            g_sequence_foreach (seq->sequence, seq_foreach, &link);
            g_assert (link == NULL);
          }
          break;
        case FOREACH_RANGE:
          {
            GSequenceIter *begin_iter, *end_iter;
            GList *begin_link, *end_link;

            get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);

            check_integrity (seq);

            g_sequence_foreach_range (begin_iter, end_iter, seq_foreach, &begin_link);

            g_assert (begin_link == end_link);
          }
          break;
        case SORT:
          {
            dump_info (seq);

            g_sequence_sort (seq->sequence, compare_items, NULL);
            g_queue_sort (seq->queue, compare_iters, NULL);

            check_sorted (seq);

            dump_info (seq);
          }
          break;
        case SORT_ITER:
          {
            check_integrity (seq);
            g_sequence_sort_iter (seq->sequence,
                                  (GSequenceIterCompareFunc)compare_iters, seq->sequence);
            g_queue_sort (seq->queue, compare_iters, NULL);
            check_sorted (seq);
          }
          break;

          /* Getting iters */
        case GET_END_ITER:
        case GET_BEGIN_ITER:
          {
            GSequenceIter *begin_iter;
            GSequenceIter *end_iter;
            GSequenceIter *penultimate_iter;

            begin_iter = g_sequence_get_begin_iter (seq->sequence);
            check_integrity (seq);

            end_iter = g_sequence_get_end_iter (seq->sequence);
            check_integrity (seq);

            penultimate_iter = g_sequence_iter_prev (end_iter);
            check_integrity (seq);

            if (g_sequence_get_length (seq->sequence) > 0)
              {
                g_assert (seq->queue->head);
                g_assert (seq->queue->head->data == begin_iter);
                g_assert (seq->queue->tail);
                g_assert (seq->queue->tail->data == penultimate_iter);
              }
            else
              {
                g_assert (penultimate_iter == end_iter);
                g_assert (begin_iter == end_iter);
                g_assert (penultimate_iter == begin_iter);
                g_assert (seq->queue->head == NULL);
                g_assert (seq->queue->tail == NULL);
              }
          }
          break;
        case GET_ITER_AT_POS:
          {
            int i;

            g_assert (g_queue_get_length (seq->queue) == (guint) g_sequence_get_length (seq->sequence));

            for (i = 0; i < 10; ++i)
              {
                int pos = get_random_position (seq);
                GSequenceIter *iter = g_sequence_get_iter_at_pos (seq->sequence, pos);
                GList *link = g_queue_peek_nth_link (seq->queue, pos);
                check_integrity (seq);
                if (pos >= g_sequence_get_length (seq->sequence) || pos < 0)
                  {
                    g_assert (iter == g_sequence_get_end_iter (seq->sequence));
                    g_assert (link == NULL);
                  }
                else
                  {
                    g_assert (link);
                    g_assert (link->data == iter);
                  }
              }
          }
          break;
        case APPEND:
          {
            for (i = 0; i < 10; ++i)
              {
                GSequenceIter *iter = g_sequence_append (seq->sequence, new_item (seq));
                g_queue_push_tail (seq->queue, iter);
              }
          }
          break;
        case PREPEND:
          {
            for (i = 0; i < 10; ++i)
              {
                GSequenceIter *iter = g_sequence_prepend (seq->sequence, new_item (seq));
                g_queue_push_head (seq->queue, iter);
              }
          }
          break;
        case INSERT_BEFORE:
          {
            for (i = 0; i < 10; ++i)
              {
                GList *link;
                GSequenceIter *iter = get_random_iter (seq, &link);
                GSequenceIter *new_iter;
                check_integrity (seq);

                new_iter = g_sequence_insert_before (iter, new_item (seq));

                g_queue_insert_before (seq->queue, link, new_iter);
              }
          }
          break;
        case MOVE:
          {
            GList *link1, *link2;
            SequenceInfo *seq1 = RANDOM_SEQUENCE();
            SequenceInfo *seq2 = RANDOM_SEQUENCE();
            GSequenceIter *iter1 = get_random_iter (seq1, &link1);
            GSequenceIter *iter2 = get_random_iter (seq2, &link2);

            if (!g_sequence_iter_is_end (iter1))
              {
                g_sequence_move (iter1, iter2);

                if (!link2)
                  g_assert (g_sequence_iter_is_end (iter2));

                g_queue_insert_before (seq2->queue, link2, link1->data);

                g_queue_delete_link (seq1->queue, link1);

                get_item (iter1)->seq = seq2;

                seq1->n_items--;
                seq2->n_items++;
              }

            check_integrity (seq);

            iter1 = get_random_iter (seq, NULL);

            /* Moving an iter to itself should have no effect */
            if (!g_sequence_iter_is_end (iter1))
              g_sequence_move (iter1, iter1);
          }
          break;
        case SWAP:
          {
            GList *link1, *link2;
            SequenceInfo *seq1 = RANDOM_SEQUENCE();
            SequenceInfo *seq2 = RANDOM_SEQUENCE();
            GSequenceIter *iter1 = get_random_iter (seq1, &link1);
            GSequenceIter *iter2 = get_random_iter (seq2, &link2);

            if (!g_sequence_iter_is_end (iter1) &&
                !g_sequence_iter_is_end (iter2))
              {
                gpointer tmp;

                g_sequence_swap (iter1, iter2);

                get_item (iter1)->seq = seq2;
                get_item (iter2)->seq = seq1;

                tmp = link1->data;
                link1->data = link2->data;
                link2->data = tmp;
              }
          }
          break;
        case INSERT_SORTED:
          {
            int i;
            dump_info (seq);

            g_sequence_sort (seq->sequence, compare_items, NULL);
            g_queue_sort (seq->queue, compare_iters, NULL);

            check_sorted (seq);

            for (i = 0; i < N_TIMES; ++i)
              {
                GSequenceIter *iter =
                  g_sequence_insert_sorted (seq->sequence, new_item(seq), compare_items, NULL);

                g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
              }

            check_sorted (seq);

            dump_info (seq);
          }
          break;
        case INSERT_SORTED_ITER:
          {
            int i;
            dump_info (seq);

            g_sequence_sort (seq->sequence, compare_items, NULL);
            g_queue_sort (seq->queue, compare_iters, NULL);

            check_sorted (seq);

            for (i = 0; i < N_TIMES; ++i)
              {
                GSequenceIter *iter;

                iter = g_sequence_insert_sorted_iter (seq->sequence,
                                                      new_item (seq),
                                                      (GSequenceIterCompareFunc)compare_iters,
                                                      seq->sequence);

                g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
              }

            check_sorted (seq);

            dump_info (seq);
          }
          break;
        case SORT_CHANGED:
          {
            int i;

            g_sequence_sort (seq->sequence, compare_items, NULL);
            g_queue_sort (seq->queue, compare_iters, NULL);

            check_sorted (seq);

            for (i = 0; i < N_TIMES; ++i)
              {
                GList *link;
                GSequenceIter *iter = get_random_iter (seq, &link);

                if (!g_sequence_iter_is_end (iter))
                  {
                    g_sequence_set (iter, new_item (seq));
                    g_sequence_sort_changed (iter, compare_items, NULL);

                    g_queue_delete_link (seq->queue, link);
                    g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
                  }

                check_sorted (seq);
              }
          }
          break;
        case SORT_CHANGED_ITER:
          {
            int i;

            g_sequence_sort (seq->sequence, compare_items, NULL);
            g_queue_sort (seq->queue, compare_iters, NULL);

            check_sorted (seq);

            for (i = 0; i < N_TIMES; ++i)
              {
                GList *link;
                GSequenceIter *iter = get_random_iter (seq, &link);

                if (!g_sequence_iter_is_end (iter))
                  {
                    g_sequence_set (iter, new_item (seq));
                    g_sequence_sort_changed_iter (iter,
                                                  (GSequenceIterCompareFunc)compare_iters, seq->sequence);

                    g_queue_delete_link (seq->queue, link);
                    g_queue_insert_sorted (seq->queue, iter, compare_iters, NULL);
                  }

                check_sorted (seq);
              }
          }
          break;
        case REMOVE:
          {
            int i;

            for (i = 0; i < N_TIMES; ++i)
              {
                GList *link;
                GSequenceIter *iter = get_random_iter (seq, &link);

                if (!g_sequence_iter_is_end (iter))
                  {
                    g_sequence_remove (iter);
                    g_queue_delete_link (seq->queue, link);
                  }
              }
          }
          break;
        case REMOVE_RANGE:
          {
            GSequenceIter *begin_iter, *end_iter;
            GList *begin_link, *end_link;
            GList *list;

            get_random_range (seq, &begin_iter, &end_iter, &begin_link, &end_link);

            g_sequence_remove_range (begin_iter, end_iter);

            list = begin_link;
            while (list != end_link)
              {
                GList *next = list->next;

                g_queue_delete_link (seq->queue, list);

                list = next;
              }
          }
          break;
        case MOVE_RANGE:
          {
            SequenceInfo *src = RANDOM_SEQUENCE();
            SequenceInfo *dst = RANDOM_SEQUENCE();

            GSequenceIter *begin_iter, *end_iter;
            GList *begin_link, *end_link;

            GSequenceIter *dst_iter;
            GList *dst_link;

            GList *list;

            g_assert (src->queue);
            g_assert (dst->queue);

            get_random_range (src, &begin_iter, &end_iter, &begin_link, &end_link);
            dst_iter = get_random_iter (dst, &dst_link);

            g_sequence_move_range (dst_iter, begin_iter, end_iter);

            if (dst_link == begin_link || (src == dst && dst_link == end_link))
              {
                check_integrity (src);
                check_integrity (dst);
                break;
              }

            if (queue_link_index (src, begin_link) >=
                queue_link_index (src, end_link))
              {
                break;
              }

            if (src == dst &&
                queue_link_index (src, dst_link) >= queue_link_index (src, begin_link) &&
                queue_link_index (src, dst_link) <= queue_link_index (src, end_link))
              {
                break;
              }

            list = begin_link;
            while (list != end_link)
              {
                GList *next = list->next;
                Item *item = get_item (list->data);

                g_assert (dst->queue);
                g_queue_insert_before (dst->queue, dst_link, list->data);
                g_queue_delete_link (src->queue, list);

                g_assert (item->seq == src);

                src->n_items--;
                dst->n_items++;
                item->seq = dst;

                list = next;
              }
          }
          break;
        case SEARCH:
          {
            Item *item;
            GSequenceIter *search_iter;
            GSequenceIter *insert_iter;

            g_sequence_sort (seq->sequence, compare_items, NULL);
            g_queue_sort (seq->queue, compare_iters, NULL);

            check_sorted (seq);

            item = new_item (seq);
            search_iter = g_sequence_search (seq->sequence, item, compare_items, NULL);

            insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);

            g_assert (search_iter == g_sequence_iter_next (insert_iter));

            g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
          }
          break;
        case SEARCH_ITER:
          {
            Item *item;
            GSequenceIter *search_iter;
            GSequenceIter *insert_iter;

            g_sequence_sort (seq->sequence, compare_items, NULL);
            g_queue_sort (seq->queue, compare_iters, NULL);

            check_sorted (seq);

            item = new_item (seq);
            search_iter = g_sequence_search_iter (seq->sequence,
                                                  item,
                                                  (GSequenceIterCompareFunc)compare_iters, seq->sequence);

            insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);

            g_assert (search_iter == g_sequence_iter_next (insert_iter));

            g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);
          }
          break;
        case LOOKUP:
          {
            Item *item;
            GSequenceIter *lookup_iter;
            GSequenceIter *insert_iter;

            g_sequence_sort (seq->sequence, compare_items, NULL);
            g_queue_sort (seq->queue, compare_iters, NULL);

            check_sorted (seq);

            item = new_item (seq);
            insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
            g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);

            lookup_iter = g_sequence_lookup (seq->sequence, item, simple_items_cmp, NULL);
            g_assert (simple_iters_cmp (insert_iter, lookup_iter, NULL) == 0);
          }
          break;
        case LOOKUP_ITER:
          {
            Item *item;
            GSequenceIter *lookup_iter;
            GSequenceIter *insert_iter;

            g_sequence_sort (seq->sequence, compare_items, NULL);
            g_queue_sort (seq->queue, compare_iters, NULL);

            check_sorted (seq);

            item = new_item (seq);
            insert_iter = g_sequence_insert_sorted (seq->sequence, item, compare_items, NULL);
            g_queue_insert_sorted (seq->queue, insert_iter, compare_iters, NULL);

            lookup_iter = g_sequence_lookup_iter (seq->sequence, item,
                (GSequenceIterCompareFunc) simple_iters_cmp, NULL);
            g_assert (simple_iters_cmp (insert_iter, lookup_iter, NULL) == 0);
          }
          break;

          /* dereferencing */
        case GET:
        case SET:
          {
            GSequenceIter *iter;
            GList *link;

            iter = get_random_iter (seq, &link);

            if (!g_sequence_iter_is_end (iter))
              {
                Item *item;
                int i;

                check_integrity (seq);

                /* Test basic functionality */
                item = new_item (seq);
                g_sequence_set (iter, item);
                g_assert (g_sequence_get (iter) == item);

                /* Make sure that existing items are freed */
                for (i = 0; i < N_TIMES; ++i)
                  g_sequence_set (iter, new_item (seq));

                check_integrity (seq);

                g_sequence_set (iter, new_item (seq));
              }
          }
          break;

          /* operations on GSequenceIter * */
        case ITER_IS_BEGIN:
          {
            GSequenceIter *iter;

            iter = g_sequence_get_iter_at_pos (seq->sequence, 0);

            g_assert (g_sequence_iter_is_begin (iter));

            check_integrity (seq);

            if (g_sequence_get_length (seq->sequence) > 0)
              {
                g_assert (!g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
              }
            else
              {
                g_assert (g_sequence_iter_is_begin (g_sequence_get_end_iter (seq->sequence)));
              }

            g_assert (g_sequence_iter_is_begin (g_sequence_get_begin_iter (seq->sequence)));
          }
          break;
        case ITER_IS_END:
          {
            GSequenceIter *iter;
            int len = g_sequence_get_length (seq->sequence);

            iter = g_sequence_get_iter_at_pos (seq->sequence, len);

            g_assert (g_sequence_iter_is_end (iter));

            if (len > 0)
              {
                g_assert (!g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
              }
            else
              {
                g_assert (g_sequence_iter_is_end (g_sequence_get_begin_iter (seq->sequence)));
              }

            g_assert (g_sequence_iter_is_end (g_sequence_get_end_iter (seq->sequence)));
          }
          break;
        case ITER_NEXT:
          {
            GSequenceIter *iter1, *iter2, *iter3, *end;

            iter1 = g_sequence_append (seq->sequence, new_item (seq));
            iter2 = g_sequence_append (seq->sequence, new_item (seq));
            iter3 = g_sequence_append (seq->sequence, new_item (seq));

            end = g_sequence_get_end_iter (seq->sequence);

            g_assert (g_sequence_iter_next (iter1) == iter2);
            g_assert (g_sequence_iter_next (iter2) == iter3);
            g_assert (g_sequence_iter_next (iter3) == end);
            g_assert (g_sequence_iter_next (end) == end);

            g_queue_push_tail (seq->queue, iter1);
            g_queue_push_tail (seq->queue, iter2);
            g_queue_push_tail (seq->queue, iter3);
          }
          break;
        case ITER_PREV:
          {
            GSequenceIter *iter1, *iter2, *iter3, *begin;

            iter1 = g_sequence_prepend (seq->sequence, new_item (seq));
            iter2 = g_sequence_prepend (seq->sequence, new_item (seq));
            iter3 = g_sequence_prepend (seq->sequence, new_item (seq));

            begin = g_sequence_get_begin_iter (seq->sequence);

            g_assert (g_sequence_iter_prev (iter1) == iter2);
            g_assert (g_sequence_iter_prev (iter2) == iter3);
            g_assert (iter3 == begin);
            g_assert (g_sequence_iter_prev (iter3) == begin);
            g_assert (g_sequence_iter_prev (begin) == begin);

            g_queue_push_head (seq->queue, iter1);
            g_queue_push_head (seq->queue, iter2);
            g_queue_push_head (seq->queue, iter3);
          }
          break;
        case ITER_GET_POSITION:
          {
            GList *link;
            GSequenceIter *iter = get_random_iter (seq, &link);

            g_assert (g_sequence_iter_get_position (iter) ==
                      queue_link_index (seq, link));
          }
          break;
        case ITER_MOVE:
          {
            int len = g_sequence_get_length (seq->sequence);
            GSequenceIter *iter;
            int pos;

            iter = get_random_iter (seq, NULL);
            pos = g_sequence_iter_get_position (iter);
            iter = g_sequence_iter_move (iter, len - pos);
            g_assert (g_sequence_iter_is_end (iter));


            iter = get_random_iter (seq, NULL);
            pos = g_sequence_iter_get_position (iter);
            while (pos < len)
              {
                g_assert (!g_sequence_iter_is_end (iter));
                pos++;
                iter = g_sequence_iter_move (iter, 1);
              }
            g_assert (g_sequence_iter_is_end (iter));
          }
          break;
        case ITER_GET_SEQUENCE:
          {
            GSequenceIter *iter = get_random_iter (seq, NULL);

            g_assert (g_sequence_iter_get_sequence (iter) == seq->sequence);
          }
          break;

          /* search */
        case ITER_COMPARE:
          {
            GList *link1, *link2;
            GSequenceIter *iter1 = get_random_iter (seq, &link1);
            GSequenceIter *iter2 = get_random_iter (seq, &link2);

            int cmp = g_sequence_iter_compare (iter1, iter2);
            int pos1 = queue_link_index (seq, link1);
            int pos2 = queue_link_index (seq, link2);

            if (cmp == 0)
              {
                g_assert (pos1 == pos2);
              }
            else if (cmp < 0)
              {
                g_assert (pos1 < pos2);
              }
            else
              {
                g_assert (pos1 > pos2);
              }
          }
          break;
        case RANGE_GET_MIDPOINT:
          {
            GSequenceIter *iter1 = get_random_iter (seq, NULL);
            GSequenceIter *iter2 = get_random_iter (seq, NULL);
            GSequenceIter *iter3;
            int cmp;

            cmp = g_sequence_iter_compare (iter1, iter2);

            if (cmp > 0)
              {
                GSequenceIter *tmp;

                tmp = iter1;
                iter1 = iter2;
                iter2 = tmp;
              }

            iter3 = g_sequence_range_get_midpoint (iter1, iter2);

            if (cmp == 0)
              {
                g_assert (iter3 == iter1);
                g_assert (iter3 == iter2);
              }

            g_assert (g_sequence_iter_get_position (iter3) >=
                      g_sequence_iter_get_position (iter1));
            g_assert (g_sequence_iter_get_position (iter2) >=
                      g_sequence_iter_get_position (iter3));
          }
          break;

        }

      check_integrity (seq);
    }

  for (k = 0; k < N_SEQUENCES; ++k)
    {
      g_queue_free (sequences[k].queue);
      g_sequence_free (sequences[k].sequence);
      sequences[k].n_items = 0;
    }
}

/* Random seeds known to have failed at one point
 */
static gulong seeds[] =
  {
    825541564u,
    801678400u,
    1477639090u,
    3369132895u,
    1192944867u,
    770458294u,
    1099575817u,
    590523467u,
    3583571454u,
    579241222u
  };

/* Single, stand-alone tests */

static void
test_out_of_range_jump (void)
{
  GSequence *seq = g_sequence_new (NULL);
  GSequenceIter *iter = g_sequence_get_begin_iter (seq);

  g_sequence_iter_move (iter, 5);

  g_assert (g_sequence_iter_is_begin (iter));
  g_assert (g_sequence_iter_is_end (iter));

  g_sequence_free (seq);
}

static void
test_iter_move (void)
{
  GSequence *seq = g_sequence_new (NULL);
  GSequenceIter *iter;
  gint i;

  for (i = 0; i < 10; ++i)
    g_sequence_append (seq, GINT_TO_POINTER (i));

  iter = g_sequence_get_begin_iter (seq);
  iter = g_sequence_iter_move (iter, 5);
  g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5);

  iter = g_sequence_iter_move (iter, -10);
  g_assert (g_sequence_iter_is_begin (iter));

  iter = g_sequence_get_end_iter (seq);
  iter = g_sequence_iter_move (iter, -5);
  g_assert_cmpint (GPOINTER_TO_INT (g_sequence_get (iter)), ==, 5);

  iter = g_sequence_iter_move (iter, 10);
  g_assert (g_sequence_iter_is_end (iter));

  g_sequence_free (seq);
}

static int
compare (gconstpointer a, gconstpointer b, gpointer userdata)
{
  int ai, bi;

  ai = GPOINTER_TO_INT (a);
  bi = GPOINTER_TO_INT (b);

  if (ai < bi)
    return -1;
  else if (ai > bi)
    return 1;
  else
    return 0;
}

static int
compare_iter (GSequenceIter *a,
              GSequenceIter *b,
              gpointer data)
{
  return compare (g_sequence_get (a),
                  g_sequence_get (b),
                  data);
}

static void
test_insert_sorted_non_pointer (void)
{
  int i;

  for (i = 0; i < 10; i++)
    {
      GSequence *seq = g_sequence_new (NULL);
      int j;

      for (j = 0; j < 10000; j++)
        {
          g_sequence_insert_sorted (seq, GINT_TO_POINTER (g_random_int()),
                                    compare, NULL);

          g_sequence_insert_sorted_iter (seq, GINT_TO_POINTER (g_random_int()),
                                         compare_iter, NULL);
        }

      g_sequence_check (seq);

      g_sequence_free (seq);
    }
}

static void
test_stable_sort (void)
{
  int i;
  GSequence *seq = g_sequence_new (NULL);

#define N_ITEMS 1000

  GSequenceIter *iters[N_ITEMS];
  GSequenceIter *iter;

  for (i = 0; i < N_ITEMS; ++i)
    {
      iters[i] = g_sequence_append (seq, GINT_TO_POINTER (3000));
      g_sequence_check (seq);
      g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
   }

  i = 0;
  iter = g_sequence_get_begin_iter (seq);
  g_assert (g_sequence_iter_get_sequence (iter) == seq);
  g_sequence_check (seq);
  while (!g_sequence_iter_is_end (iter))
    {
      g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
      g_assert (iters[i++] == iter);

      iter = g_sequence_iter_next (iter);
      g_sequence_check (seq);
    }

  g_sequence_sort (seq, compare, NULL);

  i = 0;
  iter = g_sequence_get_begin_iter (seq);
  while (!g_sequence_iter_is_end (iter))
    {
      g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
      g_assert (iters[i] == iter);

      iter = g_sequence_iter_next (iter);
      g_sequence_check (seq);

      i++;
    }

  for (i = N_ITEMS - 1; i >= 0; --i)
    {
      g_sequence_check (seq);
      g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
      g_assert (g_sequence_get_end_iter (seq) != iters[i]);
      g_sequence_sort_changed (iters[i], compare, NULL);
    }

  i = 0;
  iter = g_sequence_get_begin_iter (seq);
  while (!g_sequence_iter_is_end (iter))
    {
      g_assert (iters[i++] == iter);

      iter = g_sequence_iter_next (iter);
      g_sequence_check (seq);
    }

  g_sequence_free (seq);
}

static void
test_empty (void)
{
  GSequence *seq;
  int i;

  seq = g_sequence_new (NULL);
  g_assert_true (g_sequence_is_empty (seq));

  for (i = 0; i < 1000; i++)
    {
      g_sequence_append (seq, GINT_TO_POINTER (i));
      g_assert_false (g_sequence_is_empty (seq));
    }

  for (i = 0; i < 1000; i++)
    {
      GSequenceIter *end = g_sequence_get_end_iter (seq);
      g_assert_false (g_sequence_is_empty (seq));
      g_sequence_remove (g_sequence_iter_prev (end));
    }

  g_assert_true (g_sequence_is_empty (seq));

  g_sequence_free (seq);
}

int
main (int argc,
      char **argv)
{
  gsize i;
  guint32 seed;
  gchar *path;

  g_test_init (&argc, &argv, NULL);

  /* Standalone tests */
  g_test_add_func ("/sequence/out-of-range-jump", test_out_of_range_jump);
  g_test_add_func ("/sequence/iter-move", test_iter_move);
  g_test_add_func ("/sequence/insert-sorted-non-pointer", test_insert_sorted_non_pointer);
  g_test_add_func ("/sequence/stable-sort", test_stable_sort);
  g_test_add_func ("/sequence/is_empty", test_empty);

  /* Regression tests */
  for (i = 0; i < G_N_ELEMENTS (seeds); ++i)
    {
      path = g_strdup_printf ("/sequence/random/seed:%lu", seeds[i]);
      g_test_add_data_func (path, GUINT_TO_POINTER (seeds[i]), run_random_tests);
      g_free (path);
    }

  /* New random seed */
  seed = g_test_rand_int_range (0, G_MAXINT);
  path = g_strdup_printf ("/sequence/random/seed:%u", seed);
  g_test_add_data_func (path, GUINT_TO_POINTER (seed), run_random_tests);
  g_free (path);

  return g_test_run ();
}