/**************************************************************/
/* ********************************************************** */
/* *                                                        * */
/* *             PARTITION                                  * */
/* *                                                        * */
/* *  $Module:   PARTITION                                  * */ 
/* *                                                        * */
/* *  Copyright (C) 1999, 2001 MPI fuer Informatik          * */
/* *                                                        * */
/* *  This program is free software; you can redistribute   * */
/* *  it and/or modify it under the terms of the GNU        * */
/* *  General Public License as published by the Free       * */
/* *  Software Foundation; either version 2 of the License, * */
/* *  or (at your option) any later version.                * */
/* *                                                        * */
/* *  This program is distributed in the hope that it will  * */
/* *  be useful, but WITHOUT ANY WARRANTY; without even     * */
/* *  the implied warranty of MERCHANTABILITY or FITNESS    * */
/* *  FOR A PARTICULAR PURPOSE.  See the GNU General Public * */
/* *  License for more details.                             * */
/* *                                                        * */
/* *  You should have received a copy of the GNU General    * */
/* *  Public License along with this program; if not, write * */
/* *  to the Free Software Foundation, Inc., 59 Temple      * */
/* *  Place, Suite 330, Boston, MA  02111-1307  USA         * */
/* *                                                        * */
/* *                                                        * */
/* $Revision$                                         * */
/* $State$                                            * */
/* $Date$                             * */
/* $Author$                                       * */
/* *                                                        * */
/* *             Contact:                                   * */
/* *             Christoph Weidenbach                       * */
/* *             MPI fuer Informatik                        * */
/* *             Stuhlsatzenhausweg 85                      * */
/* *             66123 Saarbruecken                         * */
/* *             Email: weidenb@mpi-sb.mpg.de               * */
/* *             Germany                                    * */
/* *                                                        * */
/* ********************************************************** */
/**************************************************************/


/**************************************************************/
/* Include                                                    */
/**************************************************************/

#include "partition.h"


/**************************************************************/
/* Inline functions                                           */
/**************************************************************/

static __inline__ ECLASS part_GetClass(PARTITION p, ELEMENT e)
{
  return p[e];
}


static __inline__ PARTITION part_SetClass(PARTITION p, ELEMENT e, ECLASS c)
{
  p[e] = c;
  return p;
}


static __inline__ int part_GetClassSize(PARTITION p, ELEMENT e)
{
  return p[p[part_CARD] + e];
}


static __inline__ PARTITION part_SetClassSize(PARTITION p, ELEMENT e, int
    classsize)
{
  p[p[part_CARD] + e] = classsize;
  return p;
}


static __inline__ int part_GetStamp(PARTITION p, ELEMENT e)
{
  return p[-part_HEAD - 1 - e];
}


static __inline__ PARTITION part_SetStamp(PARTITION p, ELEMENT e, int stamp)
{
  p[-part_HEAD - 1 - e] = stamp;
  return p;
}


static __inline__ BOOL part_Stamped(PARTITION p, ELEMENT e)
{
  return part_GetStamp(p, e) == p[part_STAMPCOUNTER];
}


static __inline__ ELEMENT part_DelayedInit(PARTITION p, ELEMENT e)
/***************************************************************
  RETURNS: the (now stamped) element
  EFFECT:  establishes the equivalence class {e} in p, thus
	   partially initializing p
***************************************************************/
{
  if (!part_Stamped(p, e)) {
    part_SetClass(p, e, -e - 1);  /* representative e (>= 0) of {e} is coded */
				  /* as -e - 1 (< 0)                         */
    part_SetClassSize(p, e, 1);
    part_SetStamp(p, e, p[part_STAMPCOUNTER]);
  }
  return e;
}


/**************************************************************/
/* Functions                                                  */
/**************************************************************/

PARTITION part_Create(int size)
/****************************************************************
  RETURNS: the initial partition {{0}, {1}, {2}, ..., {size - 1}}
	   of the set {0, 1, 2, ..., size - 1}
****************************************************************/
{
  PARTITION result;

#ifdef CHECK
  if (size < 0) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In part_Create: negative size %d.", size);
    misc_FinishErrorReport();
  }
#endif

  result = (PARTITION) memory_Calloc(size * 3 + part_HEAD, sizeof(int))
             + size + part_HEAD;  /* move pointer to the middle of the array */
				  /* to allow negative indices               */
  result[part_CARD]         = size;
  result[part_ALLOC]        = size * 3 + part_HEAD;
  result[part_STAMPCOUNTER] = 1;
  return result;
}


PARTITION part_Init(PARTITION p, int size)
/****************************************************************
  RETURNS: the initial partition {{0}, {1}, {2}, ..., {size - 1}}
           of the set {0, 1, 2, ..., size - 1}
  EFFECT:  stores the initial partition to p if it's big enough,
           otherwise creates a new partition, therefore
  CAUTION: must be called inside an assignment like:
             p = part_Init(p, ...)
****************************************************************/
{
  int alloc, i;

#ifdef CHECK
  if (size < 0) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In part_Init: negative size %d.", size);
    misc_FinishErrorReport();
  }
#endif

  alloc = (p[part_ALLOC] - part_HEAD) / 3;
  if (size > alloc) {
    part_Free(p);
    p = part_Create(size);
  }
  else {
    p[part_CARD] = size;
    p[part_STAMPCOUNTER]++;

    /* if a stamp overflow occurs, reinit stamps: */
    if (p[part_STAMPCOUNTER] <= 0) {
      for (i = 0; i < alloc; i++)
        part_SetStamp(p, i, 0);
      p[part_STAMPCOUNTER] = 1;
    }

  }
  return p;
}


static ELEMENT part_NF(PARTITION p, ELEMENT e)
/***************************************************************
  RETURNS: the normal form element of the class [e]; this is an 
           element of [e] that sometimes differ from the
           representative
  EFFECT:  makes the normal form to the direct parent of all
	   elements visited on the search path from e to this
	   normal form ("path compression")
***************************************************************/
{
  ELEMENT nf, aux;

#ifdef CHECK
  if (!part_Element(p, e)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In part_NF: %d not in partitioned set.", e);
    misc_FinishErrorReport();
  }
#endif

  nf = e;
  while (part_GetClass(p, part_DelayedInit(p, nf)) >= 0)
    nf = part_GetClass(p, nf);

  /* path compression: */
  while (e != nf) {
    aux = part_GetClass(p, e);
    part_SetClass(p, e, nf);
    e = aux;
  }

  return nf;
}


ECLASS part_Find(PARTITION p, ELEMENT e)
/***************************************************************
  RETURNS: (the representative of) class [e]
***************************************************************/
{

#ifdef CHECK
  if (!part_Element(p, e)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In part_Find: %d not in partitioned set.", e);
    misc_FinishErrorReport();
  }
#endif

  return -part_GetClass(p, part_NF(p, e)) - 1;
    /* representative e is coded as -e - 1 (cf. part_DelayedInit) */
}


PARTITION part_Union(PARTITION p, ECLASS c1, ECLASS c2)
/***************************************************************
  RETURNS: the union of the classes
  EFFECT:  the representative of c1 is the representative of the
           union
***************************************************************/
{
  ELEMENT nf1, nf2, aux;

#ifdef CHECK
  if (!part_Element(p, c1)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In part_Union: first class %d not in partitioned set.",
      c1);
    misc_FinishErrorReport();
  }
  if (!part_Element(p, c2)) {
    misc_StartErrorReport();
    misc_ErrorReport
      ("\n In part_Union: second class %d not in partitioned set.", c2);
    misc_FinishErrorReport();
  }
#endif

  nf1 = part_NF(p, c1);
  nf2 = part_NF(p, c2);
  if (nf1 != nf2) {

    /* make [nf1] the bigger (or at least not smaller) class: */
    if (part_GetClassSize(p, nf1) < part_GetClassSize(p, nf2)) {
      aux = nf1;
      nf1 = nf2;
      nf2 = aux;
      part_SetClass(p, nf1, part_GetClass(p, nf2));
      part_SetClass(p, -part_GetClass(p, nf2) - 1, nf1);
    }

    part_SetClass(p, nf2, nf1);
    part_SetClassSize(p, nf1,
		      part_GetClassSize(p, nf1) + part_GetClassSize(p, nf2));
  }
  return p;
}