eg_equiset.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 setswith a representant (thus an equivalence class) and ask the
 * basic question of, given an elment, who is the representant if his class,
 * make a set, link two sets (i.e. union if them) and given a representant link
 * an element to that class.
 *
 * - 2003-06-24
 *          - First Implementation.
 * 
 * */
/* ========================================================================= */
#ifndef __EG_EQUISET_H__
#define __EG_EQUISET_H__
#include <stdio.h>
#include <stdlib.h>
#include "eg_config.h"
#include "eg_macros.h"
#include "eg_mempool.h"
#ifndef EG_EQUISET_DLEVEL
#define EG_EQUISET_DLEVEL 10
#endif

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

/* ========================================================================= */
/* this procedure make a new set */
extern inline EGequiSetElem_t *EGnewEquiSet (EGmemPool_t * mem,
                                             void *this)
{
  /* local variables */
  EGequiSetElem_t *v;

  /* basic set-up */
  v = (EGequiSetElem_t *) EGmemPoolMalloc (mem, sizeof (EGequiSetElem_t));
  v->rank = 0;
  v->father = v;
  v->this = this;

  /* ending */
  return v;
}

/* ========================================================================= */
/* this function find the representant of this element in his equivalence set */
EGequiSetElem_t *EGequiSetFind (EGequiSetElem_t * w);

/* ========================================================================= */
/* this functionlink two sets or equivalence clases */
extern inline EGequiSetElem_t *EGequiSetLink (EGequiSetElem_t * u,
                                              EGequiSetElem_t * v)
{
  /* local variables */
  EGequiSetElem_t *w;

  /* some tests */
  EXITL (EG_EQUISET_DLEVEL, v != v->father,
         "v is not a representant for its class");
  EXITL (EG_EQUISET_DLEVEL, u != u->father,
         "u is not a representant for its class");

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

  if (u->rank == v->rank)
  {
    u->rank++;
  }

  /* now we know that rank->u > rank->v */
  v->father = u;

  /* ending */
  return u;
}

/* ========================================================================= */
/* this function reset a set element to a singleton with the new parameter */
extern inline void EGequiSetReset (EGequiSetElem_t * u,
                                   void *elem)
{
  u->father = u;
  u->rank = 0;
  u->this = elem;
  return;
}

/* ========================================================================= */
/* destructor for the structure, note that his only eliminate the given element
 * in the set, but no the whole structure */
extern inline void EGfreeEquiSetElem (void *elem,
                                      EGmemPool_t * mem)
{
  EGmemPoolFree (elem, sizeof (EGequiSetElem_t), mem);
}

/* ========================================================================= */
/* this is an example */

/* end eg_equiset.h */
#endif

---