#include <malloc.h>
#include <gtk/gtk.h>

static gint repeats = 2;
static gint max_size = 8;

static GOptionEntry entries[] = {
  { "repeats", 'r', 0, G_OPTION_ARG_INT, &repeats, "Average over N repetitions", "N" },
  { "max-size", 'm', 0, G_OPTION_ARG_INT, &max_size, "Test up to 2^M items", "M" },
  { NULL }
};


typedef void (ClearFunc)(GtkTreeModel *model);
typedef void (InsertFunc)(GtkTreeModel *model,
			  gint          items,
			  gint          i);

static void
list_store_append (GtkTreeModel *model,
		   gint          items,
		   gint          i)
{
  GtkListStore *store = GTK_LIST_STORE (model);
  GtkTreeIter iter;
  gchar *text;

  text = g_strdup_printf ("row %d", i);
  gtk_list_store_append (store, &iter);
  gtk_list_store_set (store, &iter, 0, i, 1, text, -1);
  g_free (text);
}

static void
list_store_prepend (GtkTreeModel *model,
		    gint          items,
		    gint          i)
{
  GtkListStore *store = GTK_LIST_STORE (model);
  GtkTreeIter iter;
  gchar *text;

  text = g_strdup_printf ("row %d", i);
  gtk_list_store_prepend (store, &iter);
  gtk_list_store_set (store, &iter, 0, i, 1, text, -1);
  g_free (text);
}

static void
list_store_insert (GtkTreeModel *model,
		   gint          items,
		   gint          i)
{
  GtkListStore *store = GTK_LIST_STORE (model);
  GtkTreeIter iter;
  gchar *text;
  gint n;

  text = g_strdup_printf ("row %d", i);
  n = g_random_int_range (0, i + 1);
  gtk_list_store_insert (store, &iter, n);
  gtk_list_store_set (store, &iter, 0, i, 1, text, -1);
  g_free (text);
}

static gint
compare (GtkTreeModel *model,
	 GtkTreeIter  *a,
	 GtkTreeIter  *b,
	 gpointer      data)
{
  gchar *str_a, *str_b;
  gint result;

  gtk_tree_model_get (model, a, 1, &str_a, -1);
  gtk_tree_model_get (model, b, 1, &str_b, -1);
  
  result = strcmp (str_a, str_b);

  g_free (str_a);
  g_free (str_b);

  return result;
}

static void
tree_store_append (GtkTreeModel *model,
		   gint          items,
		   gint          i)
{
  GtkTreeStore *store = GTK_TREE_STORE (model);
  GtkTreeIter iter;
  gchar *text;

  text = g_strdup_printf ("row %d", i);
  gtk_tree_store_append (store, &iter, NULL);
  gtk_tree_store_set (store, &iter, 0, i, 1, text, -1);
  g_free (text);
}

static void
tree_store_prepend (GtkTreeModel *model,
		    gint          items,
		    gint          i)
{
  GtkTreeStore *store = GTK_TREE_STORE (model);
  GtkTreeIter iter;
  gchar *text;

  text = g_strdup_printf ("row %d", i);
  gtk_tree_store_prepend (store, &iter, NULL);
  gtk_tree_store_set (store, &iter, 0, i, 1, text, -1);
  g_free (text);
}

static void
tree_store_insert_flat (GtkTreeModel *model,
			gint          items,
			gint          i)
{
  GtkTreeStore *store = GTK_TREE_STORE (model);
  GtkTreeIter iter;
  gchar *text;
  gint n;

  text = g_strdup_printf ("row %d", i);
  n = g_random_int_range (0, i + 1);
  gtk_tree_store_insert (store, &iter, NULL, n);
  gtk_tree_store_set (store, &iter, 0, i, 1, text, -1);
  g_free (text);
}

typedef struct {
  gint i;
  gint n;
  gboolean found;
  GtkTreeIter iter;
} FindData;

static gboolean
find_nth (GtkTreeModel *model,
	  GtkTreePath  *path,
	  GtkTreeIter  *iter,
	  gpointer      data)
{
  FindData *fdata = (FindData *)data; 

  if (fdata->i >= fdata->n)
    {
      fdata->iter = *iter;
      fdata->found = TRUE;
      return TRUE;
    }

  fdata->i++;

  return FALSE;
}

static void
tree_store_insert_deep (GtkTreeModel *model,
			gint          items,
			gint          i)
{
  GtkTreeStore *store = GTK_TREE_STORE (model);
  GtkTreeIter iter;
  gchar *text;
  FindData data;
  gint n;

  text = g_strdup_printf ("row %d", i);
  data.n = g_random_int_range (0, items);
  data.i = 0;
  data.found = FALSE;
  if (data.n < i)
    gtk_tree_model_foreach (model, find_nth, &data);
  gtk_tree_store_insert (store, &iter, data.found ? &(data.iter) : NULL, n);
  gtk_tree_store_set (store, &iter, 0, i, 1, text, -1);
  g_free (text);
}


static void
test_run (gchar        *title,
	  GtkTreeModel *store,
	  ClearFunc    *clear,
	  InsertFunc   *insert)
{
  GtkTreeIter iter;
  gint i, k, d, items;
  gchar *text;
  GTimer *timer;
  gdouble elapsed;
  int uordblks_before;

  g_print ("%s (average over %d runs, time in milliseconds)\n"
	   "items \ttime      \ttime/item \tused memory\n", title, repeats);

  timer = g_timer_new ();

  for (k = 0; k < max_size; k++)
    {
      items = 1 << k;
      elapsed = 0.0;
      for (d = 0; d < repeats; d++)
	{
	  (*clear)(store);
	  uordblks_before = mallinfo().uordblks;
	  g_timer_reset (timer);
	  g_timer_start (timer);
	  for (i = 0; i < items; i++)
	    (*insert) (store, items, i);
	  g_timer_stop (timer);
	  elapsed += g_timer_elapsed (timer, NULL);
	}
      
      elapsed = elapsed * 1000 / repeats;
      g_print ("%d \t%lf \t%lf  \t%ldk\n", 
	       items, elapsed, elapsed/items, (mallinfo().uordblks - uordblks_before) / 1024);
    }  
}

int
main (int argc, char *argv[])
{
  GtkTreeModel *model;
  GOptionContext *context;
  
  gtk_init (&argc, &argv);

  context = g_option_context_new ("");
  g_option_context_add_main_entries (context, entries, "");
  g_option_context_parse (context, &argc, &argv, NULL);
  g_option_context_free (context);

  model = GTK_TREE_MODEL (gtk_list_store_new (2, G_TYPE_INT, G_TYPE_STRING));
  
  test_run ("list store append", 
	    model, 
	    (ClearFunc*)gtk_list_store_clear, 
	    (InsertFunc*)list_store_append);

  test_run ("list store prepend", 
	    model, 
	    (ClearFunc*)gtk_list_store_clear, 
	    (InsertFunc*)list_store_prepend);

  test_run ("list store insert", 
	    model, 
	    (ClearFunc*)gtk_list_store_clear, 
	    (InsertFunc*)list_store_insert);

  gtk_tree_sortable_set_default_sort_func (GTK_TREE_SORTABLE (model), 
					   compare, NULL, NULL);
  gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (model), 
					GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID,
					GTK_SORT_ASCENDING);

  test_run ("list store insert (sorted)", 
	    model, 
	    (ClearFunc*)gtk_list_store_clear, 
	    (InsertFunc*)list_store_insert);

  g_object_unref (model);
  
  model = GTK_TREE_MODEL (gtk_tree_store_new (2, G_TYPE_INT, G_TYPE_STRING));

  test_run ("tree store append", 
	    model, 
	    (ClearFunc*)gtk_tree_store_clear, 
	    (InsertFunc*)tree_store_append);

  test_run ("tree store prepend", 
	    model, 
	    (ClearFunc*)gtk_tree_store_clear, 
	    (InsertFunc*)tree_store_prepend);

  test_run ("tree store insert (flat)", 
	    model, 
	    (ClearFunc*)gtk_tree_store_clear, 
	    (InsertFunc*)tree_store_insert_flat);

  test_run ("tree store insert (deep)", 
	    model, 
	    (ClearFunc*)gtk_tree_store_clear, 
	    (InsertFunc*)tree_store_insert_deep);

  gtk_tree_sortable_set_default_sort_func (GTK_TREE_SORTABLE (model), 
					   compare, NULL, NULL);
  gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (model), 
					GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID,
					GTK_SORT_ASCENDING);

  test_run ("tree store insert (flat, sorted)", 
	    model, 
	    (ClearFunc*)gtk_tree_store_clear, 
	    (InsertFunc*)tree_store_insert_flat);

  test_run ("tree store insert (deep, sorted)", 
	    model, 
	    (ClearFunc*)gtk_tree_store_clear, 
	    (InsertFunc*)tree_store_insert_deep);

  return 0;
}