/* Copyright 2010 IPB, INRIA & CNRS
**
** This file originally comes from the Scotch software package for
** static mapping, graph partitioning and sparse matrix ordering.
**
** This software is governed by the CeCILL-B license under French law
** and abiding by the rules of distribution of free software. You can
** use, modify and/or redistribute the software under the terms of the
** CeCILL-B license as circulated by CEA, CNRS and INRIA at the following
** URL: "http://www.cecill.info".
** 
** As a counterpart to the access to the source code and rights to copy,
** modify and redistribute granted by the license, users are provided
** only with a limited warranty and the software's author, the holder of
** the economic rights, and the successive licensors have only limited
** liability.
** 
** In this respect, the user's attention is drawn to the risks associated
** with loading, using, modifying and/or developing or reproducing the
** software by the user in light of its specific status of free software,
** that may mean that it is complicated to manipulate, and that also
** therefore means that it is reserved for developers and experienced
** professionals having in-depth computer knowledge. Users are therefore
** encouraged to load and test the software's suitability as regards
** their requirements in conditions enabling the security of their
** systems and/or data to be ensured and, more generally, to use and
** operate it in the same conditions as regards security.
** 
** The fact that you are presently reading this means that you have had
** knowledge of the CeCILL-B license and that you accept its terms.
*/
/************************************************************/
/**                                                        **/
/**   NAME       : fibo.h                                  **/
/**                                                        **/
/**   AUTHOR     : Francois PELLEGRINI                     **/
/**                                                        **/
/**   FUNCTION   : This module is a sample test program    **/
/**                for the generic Fibonacci trees module. **/
/**                                                        **/
/**   DATES      : # Version 1.0  : from : 01 may 2010     **/
/**                                 to     12 may 2010     **/
/**                                                        **/
/************************************************************/

/*
**  The defines and includes.
*/

#include <errno.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <stdint.h>

#include "fibo.h"
#include "helper.h"

/*
**  The type and structure definitions.
*/

/* Sample data structure which uses the Fibonacci
   tree module to sort some of its properties.    */
typedef struct Data_ {
  FiboNode	node;                       /* Can be everywhere in the data structure */
  int64_t	data;                       /* Can be everywhere in the data structure */
} Data;

/* The comparison function which is used to sort
** "Data" structures. Since only "FiboNode" pointers
** are passed, pointer offset computations are
** necessary to access the whole "Data" structures,
** with all their fields. Since this Fibonacci tree
** implementation sorts data by ascending order,
** the comparison function must return a negative
** number if "node1" has to be returned before
** "node2" when extracting sorted data from the
** Fibonacci tree structure.
*/

static int cmpFunc (const FiboNode *const node1, const FiboNode *const node2)
{
  const Data *const data1 = fibo_entry(node1, Data, node);
  const Data *const data2 = fibo_entry(node2, Data, node);

/* Any kind of criteria can be used for sorting, provided
 * that the comparison function guarantees a total order
 * on the elements.
 */
  return ((data1->data < data2->data) ? -1 : 1);
}

int main (int argc, char *argv[])
{
  FiboTree            treedat;
  FiboNode *          nodeptr;
  Data *              dataptr;
  long int            i;
  long int            loops;
  long int            deleted = 0;
  uint32_t            randval;
  Data                *tests;

  if (argc != 2) return 1;
  errno = 0;
  loops = strtoul(argv[1], NULL, 10);
  if (errno || loops <= 1 || (loops > (LONG_MAX/sizeof(Data)))) return 1;
  srand(loops);
  tests = malloc(sizeof(Data) * loops);

  fprintf (stderr, "Initializing tree\n");
  if (fiboTreeInit (&treedat, cmpFunc) != 0) {
    fprintf (stderr, "Cannot initialize tree\n");
    return 1;
  }

  for (i = 0; i < loops; i++) {
      randval = rand();
      tests[i].data = INT64_C(0x100000000) + randval;
      if (i > 0 && ((randval & 255) == 0)) {
          fiboTreeDel(&treedat, &tests[i-i].node);
          deleted++;
      }
      fiboTreeAdd(&treedat, &tests[i].node);
  }
  fprintf(stderr, "added %ld and deleted %ld nodes\n", loops, deleted);

#if 1
  nodeptr = fiboTreeMin (&treedat);
  if (nodeptr == NULL) {
      fprintf (stderr, "TREE IS EMPTY\n");
      return 1;
  } else {
      dataptr = fibo_entry(nodeptr, Data, node);
      fprintf (stderr, "first item: %" PRId64 "\n", dataptr->data);
      fiboTreeDel (&treedat, nodeptr);
      //free (dataptr);
  }
#endif

  fiboTreeExit (&treedat);                        /* Necessary to free the internal consolidation array */

  return 0;
}