/* Portions copyright (c) 2009 Nokia Corporation.  All rights reserved.*/

#include <stdio.h>

#include <glib.h>

#include <stdlib.h>

#ifdef __SYMBIAN32__

#include "mrt2_glib2_test.h"

#endif /*__SYMBIAN32__*/

/* 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

{

  gint                  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);

    }

}

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);

}

//undefs done here as some of these enums are already defined in s60 environ

#ifdef __SYMBIAN32__

#undef NEW 

#undef FREE

#undef GET_LENGTH

#undef FOREACH

#undef FOREACH_RANGE

#undef SORT

#undef SORT_ITER

#endif//__SYMBIAN32__

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,

  /* 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;

  int		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 (g_sequence_get_length (info->sequence) != info->n_items)

    g_print ("%d %d\n",

	     g_sequence_get_length (info->sequence), info->n_items);

  g_assert (info->n_items == g_queue_get_length (info->queue));

  g_assert (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 (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

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_print ("%p  %p    %d\n", list->data, iter, item->number);

      iter = g_sequence_iter_next (iter);

      list = list->next;

    }

#endif

}

/* A version of g_queue_insert_before() that appends if link is NULL */

static void

queue_insert_before (SequenceInfo *seq, GList *link, gpointer data)

{

  if (link)

    g_queue_insert_before (seq->queue, link, data);

  else

    g_queue_push_tail (seq->queue, data);

}

static void

run_random_tests (guint32 seed)

{

#ifndef __SYMBIAN32__

#define N_ITERATIONS 60000

#else

#define N_ITERATIONS 600

#endif//__SYMBIAN32__    

#define N_SEQUENCES 8

#define N_TIMES 24

  SequenceInfo sequences[N_SEQUENCES];

  int k;

  g_print ("    seed: %u\n", seed);

  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_print ("%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) == 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));

		queue_insert_before (seq, 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));

		queue_insert_before (seq2, 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);

		queue_insert_before (dst, 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;

	  /* 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);

	  }