/*

* Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies).

* All rights reserved.

* This component and the accompanying materials are made available

* under the terms of "Eclipse Public License v1.0"

* which accompanies this distribution, and is available

* at the URL "http://www.eclipse.org/legal/epl-v10.html".

*

* Initial Contributors:

* Nokia Corporation - initial contribution.

*

* Contributors:

*

* Description: 

*

*/

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