/* 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.c                                  **/
/**                                                        **/
/**   AUTHOR     : Francois PELLEGRINI                     **/
/**                                                        **/
/**   FUNCTION   : This module handles Fibonacci trees.    **/
/**                                                        **/
/**   DATES      : # Version 1.0  : from : 01 may 2010     **/
/**                                 to     12 may 2010     **/
/**                                                        **/
/************************************************************/

/*
**  The defines and includes.
*/

#define FIBO

#include <stdlib.h>
#include <memory.h>
#include <stdio.h>
#include "fibo.h"

/* Helper macros which can be redefined at compile time. */

#ifndef INT
#define INT                         int           /* "long long" can be used on 64-bit systems */
#endif /* INT */

#ifndef errorPrint
#define errorPrint(s)               fprintf (stderr, s)
#endif /* errorPrint */

#ifndef memAlloc
#define memAlloc                    malloc
#define memSet                      memset
#define memFree                     free
#endif /* memAlloc */

static FiboNode *fiboTreeConsolidate (FiboTree * const);

/*********************************************/
/*                                           */
/* These routines deal with Fibonacci trees. */
/*                                           */
/*********************************************/

/* This routine initializes a Fibonacci
** tree structure.
** It returns:
** - 0   : in case of success.
** - !0  : on error.
*/

int
tm_fiboTreeInit (
FiboTree * const            treeptr,
int                      (* cmpfptr) (const FiboNode * const, const FiboNode * const))
{
  if ((treeptr->degrtab = (FiboNode **) memAlloc ((sizeof (INT) << 3) * sizeof (FiboNode *))) == NULL) /* As many cells as there are bits in an INT */
    return (1);

  memSet (treeptr->degrtab, 0, (sizeof (INT) << 3) * sizeof (FiboNode *)); /* Make degree array ready for consolidation: all cells set to NULL */

  treeptr->rootdat.linkdat.prevptr =              /* Link root node to itself */
  treeptr->rootdat.linkdat.nextptr = &treeptr->rootdat;
  treeptr->cmpfptr = cmpfptr;

  return (0);
}

/* This routine flushes the contents of
** the given Fibonacci tree.
** It returns:
** - VOID  : in all cases.
*/

void
tm_fiboTreeExit (
FiboTree * const            treeptr)
{
  if (treeptr->degrtab != NULL)
    memFree (treeptr->degrtab);
}

/* This routine flushes the contents of
** the given Fibonacci tree. It does not
** free any of its contents, but instead
** makes the tree structure look empty again.
** It returns:
** - VOID  : in all cases.
*/

void
tm_fiboTreeFree (
FiboTree * const            treeptr)
{
  treeptr->rootdat.linkdat.prevptr =              /* Link root node to itself */
  treeptr->rootdat.linkdat.nextptr = &treeptr->rootdat;
}

/* This routine perform the consolidation
** of roots per degree. It returns the best
** element found because this element is not
** recorded in the data structure itself.
** It returns:
** - !NULL  : pointer to best element found.
** - NULL   : Fibonacci tree is empty.
*/

static FiboNode *
fiboTreeConsolidate (
FiboTree * const            treeptr)
{
  FiboNode ** restrict  degrtab;
  int                   degrmax;
  int                   degrval;
  FiboNode *            rootptr;
  FiboNode *            nextptr;
  FiboNode *            bestptr;

  degrtab = treeptr->degrtab;

  for (rootptr = treeptr->rootdat.linkdat.nextptr, nextptr = rootptr->linkdat.nextptr, degrmax = 0; /* For all roots in root list */
       rootptr != &treeptr->rootdat; ) {
    degrval = rootptr->deflval >> 1;              /* Get degree, getting rid of flag part */
#ifdef FIBO_DEBUG
    if (degrval >= (sizeof (INT) << 3))
      errorPrint ("fiboTreeConsolidate: invalid node degree");
#endif /* FIBO_DEBUG */
    if (degrtab[degrval] == NULL) {               /* If no tree with same degree already found */
      if (degrval > degrmax)                      /* Record highest degree found               */
        degrmax = degrval;

      degrtab[degrval] = rootptr;                 /* Record tree as first tree with this degree      */
      rootptr = nextptr;                          /* Process next root in list during next iteration */
      nextptr = rootptr->linkdat.nextptr;
    }
    else {
      FiboNode *            oldrptr;              /* Root which will no longer be a root */
      FiboNode *            chldptr;

      oldrptr = degrtab[degrval];                 /* Assume old root is worse           */
      if (treeptr->cmpfptr (oldrptr, rootptr) <= 0) { /* If old root is still better    */
        oldrptr = rootptr;                        /* This root will be be linked to it  */
        rootptr = degrtab[degrval];               /* We will go on processing this root */
      }

      degrtab[degrval] = NULL;                    /* Remaining root changes degree so leaves this cell */
      fiboTreeUnlink (oldrptr);                   /* Old root is no longer a root                      */
      oldrptr->deflval &= ~1;                     /* Whatever old root flag was, it is reset to 0      */
      oldrptr->pareptr = rootptr;                 /* Remaining root is now father of old root          */

      chldptr = rootptr->chldptr;                 /* Get first child of remaining root                                    */
      if (chldptr != NULL) {                      /* If remaining root had already some children, link old root with them */
        rootptr->deflval += 2;                    /* Increase degree by 1, that is, by 2 with left shift in deflval       */
        fiboTreeLinkAfter (chldptr, oldrptr);
      }
      else {                                      /* Old root becomes first child of remaining root */
        rootptr->deflval = 2;                     /* Real degree set to 1, and flag set to 0        */
        rootptr->chldptr = oldrptr;
        oldrptr->linkdat.prevptr =                /* Chain old root to oneself as only child */
        oldrptr->linkdat.nextptr = oldrptr;
      }
    }                                             /* Process again remaining root as its degree has changed */
  }

  bestptr = NULL;
  for (degrval = 0; degrval <= degrmax; degrval ++) {
    if (degrtab[degrval] != NULL) {               /* If some tree is found           */
      bestptr = degrtab[degrval];                 /* Record it as potential best     */
      degrtab[degrval] = NULL;                    /* Clean-up used part of array     */
      degrval ++;                                 /* Go on at next cell in next loop */
      break;
    }
  }
  for ( ; degrval <= degrmax; degrval ++) {       /* For remaining roots once a potential best root has been found */
    if (degrtab[degrval] != NULL) {
      if (treeptr->cmpfptr (degrtab[degrval], bestptr) < 0) /* If new root is better */
        bestptr = degrtab[degrval];               /* Record new root as best root    */
      degrtab[degrval] = NULL;                    /* Clean-up used part of array     */
    }
  }

  return (bestptr);
}

/* This routine returns the node of minimum
** key in the given tree. The node is searched
** for each time this routine is called, so this
** information should be recorded if needed.
** This is the non-macro version, for testing
** and setting up breakpoints.
** It returns:
** - !NULL  : pointer to best element found.
** - NULL   : Fibonacci tree is empty.
*/

#ifndef fiboTreeMin

FiboNode *
tm_fiboTreeMin (
FiboTree * const            treeptr)
{
  FiboNode *            bestptr;

  bestptr = fiboTreeMinMacro (treeptr);

#ifdef FIBO_DEBUG
  fiboTreeCheck (treeptr);
#endif /* FIBO_DEBUG */

  return (bestptr);
}

#endif /* fiboTreeMin */

/* This routine adds the given node to the
** given tree. This is the non-macro version,
** for testing and setting up breakpoints.
** It returns:
** - void  : in all cases.
*/

#ifndef fiboTreeAdd

void
fiboTreeAdd (
FiboTree * const            treeptr,
FiboNode * const            nodeptr)
{
  fiboTreeAddMacro (treeptr, nodeptr);

#ifdef FIBO_DEBUG
  fiboTreeCheck (treeptr);
#endif /* FIBO_DEBUG */
}

#endif /* fiboTreeAdd */

/* This routine deletes the given node from
** the given tree, whatever ths node is (root
** or non root). This is the non-macro version,
** for testing and setting up breakpoints.
** It returns:
** - void  : in all cases.
*/

#ifndef fiboTreeDel

void
tm_fiboTreeDel (
FiboTree * const            treeptr,
FiboNode * const            nodeptr)
{
  fiboTreeDelMacro (treeptr, nodeptr);

#ifdef FIBO_DEBUG
  nodeptr->pareptr =
  nodeptr->chldptr =
  nodeptr->linkdat.prevptr =
  nodeptr->linkdat.nextptr = NULL;

  fiboTreeCheck (treeptr);
#endif /* FIBO_DEBUG */
}

#endif /* fiboTreeDel */

/* This routine checks the consistency of the
** given linked list.
** It returns:
** - !NULL  : pointer to the vertex.
** - NULL   : if no such vertex available.
*/

#ifdef FIBO_DEBUG

static
int
fiboTreeCheck2 (
const FiboNode * const      nodeptr)
{
  FiboNode *            chldptr;
  int                   degrval;

  degrval = 0;
  chldptr = nodeptr->chldptr;
  if (chldptr != NULL) {
    do {
      if (chldptr->linkdat.nextptr->linkdat.prevptr != chldptr) {
        errorPrint ("fiboTreeCheck: bad child linked list");
        return     (1);
      }

      if (chldptr->pareptr != nodeptr) {
        errorPrint ("fiboTreeCheck: bad child parent");
        return (1);
      }

      if (fiboTreeCheck2 (chldptr) != 0)
        return (1);

      degrval ++;
      chldptr = chldptr->linkdat.nextptr;
    } while (chldptr != nodeptr->chldptr);
  }

  if (degrval != (nodeptr->deflval >> 1)) {       /* Real node degree is obtained by discarding lowest bit */
    errorPrint ("fiboTreeCheck2: invalid child information");
    return     (1);
  }

  return (0);
}

int
fiboTreeCheck (
const FiboTree * const      treeptr)
{
  FiboNode *            nodeptr;

  for (nodeptr = treeptr->rootdat.linkdat.nextptr;
       nodeptr != &treeptr->rootdat; nodeptr = nodeptr->linkdat.nextptr) {
    if (nodeptr->linkdat.nextptr->linkdat.prevptr != nodeptr) {
      errorPrint ("fiboTreeCheck: bad root linked list");
      return     (1);
    }

    if (nodeptr->pareptr != NULL) {
      errorPrint ("fiboTreeCheck: bad root parent");
      return (1);
    }

    if (fiboTreeCheck2 (nodeptr) != 0)
      return (1);
  }

  return (0);
}

#endif /* FIBO_DEBUG */