eg_aequiset.h

Go to the documentation of this file.

/* EGlib "Efficient General Library" provides some basic structures and
 * algorithms commons in many optimization algorithms.
 *
 * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
 * 
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 *
 * This library 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 Lesser General Public 
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
 * */
/* ========================================================================= */
/* This is an implementation of the set's defined at 'Data Structures and
 * Network Algorithms' of Robert Endre Tarjan. This structures allow to work
 * with disjoint sets with a representant (thus an equivalence class) and ask 
 * the basic question of, given an elment, who is the representant in his 
 * class, make a set, link two sets (i.e. union of them) and given a 
 * representant link an element to that class. But this implementation instead 
 * of working with pointers works with arrays and index in such an array, the 
 * main advantage of this implementation is that copying this information is 
 * easier than in the linked-list implementation. the main drawback is that it 
 * is an static structure (in terms of the number of elements).
 *
 * - 2003-12-01
 *          - First Implementation.
 * 
 * */
/* ========================================================================= */
#ifndef __EG_AEQUISET_H__
#define __EG_AEQUISET_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "eg_config.h"
#include "eg_macros.h"
#include "eg_mempool.h"
#ifndef EG_AEQUISET_DLEVEL
#define EG_AEQUISET_DLEVEL 10
#endif

/* ========================================================================= */
/* this structure holds an element of a set */
typedef struct EGaequiSetElem_t
{
  unsigned father;
  unsigned rank;
  void *this;
}
EGaequiSetElem_t;

/* ========================================================================= */
/* this structure holds a universe set. Note that this structure is mainly
 * static. */
typedef struct EGaequiSet_t
{
  unsigned size;
  EGaequiSetElem_t *set;
  EGmemPool_t *mem;
}
EGaequiSet_t;

/* ========================================================================= */
/*  this function copy one aequiset to another new set */
extern inline EGaequiSet_t *EGaequiSetCopyMP (EGaequiSet_t * U,
                                              EGcopyMP_f data_copy,
                                              EGmemPool_t * mem)
{
  /* local variables */
  EGaequiSet_t *orig = (EGaequiSet_t *) U,
   *copy;
  register unsigned i;

  /* create basic copy of the set */
  copy = EGmemPoolSMalloc (orig->mem, EGaequiSet_t, 1);
  copy->mem = orig->mem;
  copy->size = orig->size;
  copy->set = EGmemPoolSMalloc (mem, EGaequiSetElem_t, orig->size);
  memcpy (copy->set, orig->set, sizeof (EGaequiSetElem_t) * orig->size);

  /* if we have a copy function we use it */
  if (data_copy)
    for (i = copy->size; i--;)
      copy->set[i].this = data_copy (orig->set[i].this, mem);

  /* ending */
  return copy;
}

/* ========================================================================= */
/*  this function copy one aequiset to another new set */
extern inline EGaequiSet_t *EGaequiSetCopy (EGaequiSet_t * U,
                                            EGcopy_f data_copy)
{
  /* local variables */
  EGaequiSet_t *orig = (EGaequiSet_t *) U,
   *copy;
  register unsigned i;

  /* create basic copy of the set */
  copy = EGmemPoolSMalloc (orig->mem, EGaequiSet_t, 1);
  copy->mem = orig->mem;
  copy->size = orig->size;
  copy->set = EGmemPoolSMalloc (orig->mem, EGaequiSetElem_t, orig->size);
  memcpy (copy->set, orig->set, sizeof (EGaequiSetElem_t) * orig->size);

  /* if we have a copy function we use it */
  if (data_copy)
    for (i = copy->size; i--;)
      copy->set[i].this = data_copy (orig->set[i].this);

  /* ending */
  return copy;
}

/* ========================================================================= */
/* this procedure make a new set of size 'size' and with all elements as
 * singletons and without internal data. */
extern inline EGaequiSet_t *EGnewAEquiSet (EGmemPool_t * mem,
                                           const unsigned size)
{
  /* local variables */
  EGaequiSet_t *v;
  register unsigned i;
  EGaequiSetElem_t *elem;

  /* basic set-up */
  v = EGmemPoolSMalloc (mem, EGaequiSet_t, 1);
  v->mem = mem;
  v->size = size;
  v->set = EGmemPoolSMalloc (mem, EGaequiSetElem_t, size);
  for (elem = v->set + size, i = size; i--;)
  {
    elem--;
    elem->father = i;
    elem->this = 0;
    elem->rank = 0;
  }

  /* ending */
  return v;
}

/* ========================================================================= */
/* this function find the representant of this element in his equivalence set */
unsigned EGaequiSetFind (EGaequiSet_t * const s,
                         const unsigned elem);

/* ========================================================================= */
/* this functionlink two sets or equivalence clases */
extern inline unsigned EGaequiSetLink (EGaequiSet_t * const U,
                                       const unsigned u,
                                       const unsigned v)
{
  /* local variables */
  EGaequiSetElem_t *w,
   *uptr,
   *vptr;

  /* some tests */
  EXITL (EG_AEQUISET_DLEVEL, u >= U->size,
         "elem (%u) is out of range (size = %u)", u, U->size);
  EXITL (EG_AEQUISET_DLEVEL, v >= U->size,
         "elem (%u) is out of range (size = %u)", v, U->size);
  EXITL (EG_AEQUISET_DLEVEL, v != U->set[v].father,
         "v is not a representant for its class");
  EXITL (EG_AEQUISET_DLEVEL, u != U->set[u].father,
         "u is not a representant for its class");

  /* pick the biggest one */
  uptr = U->set + u;
  vptr = U->set + v;
  if (uptr->rank < vptr->rank)
  {
    w = uptr;
    uptr = vptr;
    vptr = w;
  }

  if (uptr->rank == vptr->rank)
  {
    uptr->rank++;
  }

  /* now we know that rank->u > rank->v */
  vptr->father = uptr - U->set;

  /* ending */
  return vptr->father;
}

/* ========================================================================= */
/* this function reset a Universe set to all singleton-state */
extern inline void EGaequiSetReset (EGaequiSet_t * const U)
{
  unsigned register i;
  EGaequiSetElem_t *elem;
  for (i = U->size, elem = U->set + U->size; i--;)
  {
    elem--;
    elem->father = i;
    elem->this = 0;
    elem->rank = 0;
  }
  return;
}

/* ========================================================================= */
/* destructor for the structure, note that his only eliminate the given element
 * in the set, but no the whole structure */
extern inline void EGfreeAEquiSet (void *U)
{
  EGmemPoolSFree (((EGaequiSet_t *) U)->set,
                  EGaequiSetElem_t,
                  ((EGaequiSet_t *) U)->size, ((EGaequiSet_t *) U)->mem);
  EGmemPoolSFree (((EGaequiSet_t *) U),
                  EGaequiSet_t, 1, ((EGaequiSet_t *) U)->mem);
  return;
}

/* ========================================================================= */

/* end eg_aequiset.h */
#endif

---