eg_eheap.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 
 * */
/* ========================================================================= */
/** @defgroup EGeHeap EGeHeap
 *
 * Here we define the basic interface for d-heaps as an embeded structure.
 * In this implementation the heap does not grow on the fly, meaning that it 
 * may fills-up during an add call, to avoid that, the user must call 
 * re-allocate when necesary. the heap start as a heap of size zero. 
 * This implementatioon is a minimum-heap implementatiton. Note also that the
 * internal connector array is shifted one position to the left. This is done 
 * so that the first element is in position 1, this also speed-up the 
 * computation of the parent and childrens of a given position.
 *
 * @version 0.0.1
 * @par History:
 * - 2005-07-14
 *            - Add EGeHeapEmpty to empty the heap (but keep its maximum
 *              size)
 *            - Add EGeHeapIsFull to test wether a heap is full or not.
 * - 2005-07-07
 *            - First Implementation
 * @note 
 * This implementatiton is designed as a template using as base the types of
 * @ref EGlpNum
 * */
/** @file 
 * @ingroup EGeHeap */
/** @addtogroup EGeHeap */
/** @{ */
/** @example eg_eheap.ex.c
 * This is a simple example of the usage of heaps using @ref EGeHeap */
/* ========================================================================= */
#ifndef __EG_EHEAP__
#define __EG_EHEAP__
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <float.h>
#include "eg_macros.h"
#include "eg_lpnum.h"
/* ========================================================================= */
/** @brief Debug level for the heap */
#define EG_EHEAP_DEBUG 1000

/* ========================================================================= */
/** @brief Structure to store the information relevant to an element in the
 * heap. */
typedef struct EGeHeapCn_t
{
  EGlpNum_t val;    /**< Value of this node in the heap */
  unsigned int pos; /**< Position in the heap array for this node, if set to
                         #EG_EHEAP_POISON, then the connector is not in any 
                         heap.*/
}
EGeHeapCn_t;

/* ========================================================================= */
/** @brief Poison position for heap connector not in a heap. */
#define EG_EHEAP_POISON UINT_MAX

/* ========================================================================= */
/** @brief Initialize a heap conector structure. This function will allocate any
 * interal memory not allocated by the user, it should be called only once, or
 * after a clear function call.
 * @param hcn conector to initialize.
 * */
#define EGeHeapCnInit(hcn) ({EGlpNumInitVar((hcn)->val);(hcn)->pos = EG_EHEAP_POISON;})

/* ========================================================================= */
/** @brief Reset a heap conector to the same state as after an init call, this
 * function is provided only for completness.
 * @param hcn conector to reset
 * */
#define EGeHeapCnReset(hcn) ((hcn)->pos = EG_EHEAP_POISON)

/* ========================================================================= */
/** @brief Free all internal memory used by this structured not allocated by the
 * user. This function should be called after an init call, and only once.
 * @param hcn conector to clear.
 * */
#define EGeHeapCnClear(hcn) EGlpNumClearVar((hcn)->val)

/* ========================================================================= */
/** @brief Structure to hold a whole heap structure, this structure is designed
 * so that it can grow on the fly with a low cost */
typedef struct EGeHeap_t
{
  EGeHeapCn_t **cn;
  unsigned int d;
  unsigned int sz;
  unsigned int max_sz;
}
EGeHeap_t;

/* ========================================================================= */
/** @brief Return one if the heap is full, zero otherwise.
 * @param hp heat to check */
#define EGeHeapIsFull(hp) ({EGeHeap_t*const __EGehp = (hp); __EGehp->sz == __EGehp->max_sz;})

/* ========================================================================= */
/** @brief set the number of elements in hte heap to zero.
 * @param hp heap to empty.
 * */
#define EGeHeapEmpty(hp) ((hp)->sz = 0)

/* ========================================================================= */
/** @brief Initialize a heap as an empty heap (with no space for conectors).
 * @param hp heap to initialize.
 * */
#define EGeHeapInit(hp) (*(hp) = (EGeHeap_t){0,0,0,0})

/* ========================================================================= */
/** @brief Reset the given heap as an empty heap (just as returned by the init
 * call.
 * @param hp heap to reset 
 * */
#define EGeHepReset(hp) EGeHeapInit(hp)

/* ========================================================================= */
/** @brief Clear a heap structure, and free any internal memory (not allocated
 * by the user).
 * @param hp heap to clear.
 * */
#define EGeHeapClear(hp)

/* ========================================================================= */
/** @brief get the minimum value in the heap.
 * @param hp heap where we are working.
 * @param number where to store the result
 * @return zero on success, non-zero otherwise.
 * */
#define EGeHeapGetMinVal(hp,number) ({\
  EGeHeap_t*const __EGehp = (hp);\
  __EGehp->sz ? (EGlpNumCopy(number,__EGehp->cn[0]->val),0):1;})

/* ========================================================================= */
/** @brief get the minimum conector in the heap, if the heap is empty, return
 * NULL.
 * @param hp eap where we are working.
 * @return pointer to the minimum element in the heap.
 * */
#define EGeHeapGetMin(hp) ({\
  EGeHeap_t*const __EGehp = (hp);\
  __EGehp->sz ? __EGehp->cn[0] : 0;})

/* ========================================================================= */
/** @brief resize the heap cn array to the given size, if the new size is zero,
 * it is equivalent to free the internal memory, and left the heap as an empty
 * heap with zero space.
 * @param hp heap where we are working.
 * @param new_sz hew size for the  cn array .
 * */
#define EGeHeapResize(hp,new_sz) ({\
  EGeHeap_t*const __EGehp = (hp);\
  const unsigned int __EGehp_nsz = (new_sz);\
  __EGehp->cn = EGrealloc((__EGehp->cn), __EGehp_nsz * sizeof(EGeHeapCn_t*));\
  __EGehp->max_sz = __EGehp_nsz;})

/* ========================================================================= */
/** @brief return the index of the father of the given index.
 * @param d breadth of the heap.
 * @param id position in the array to wich we want to compute it's father.
 * */
#define EGeHeapFatherId(d,id) ((id)?(((id)-1)/(d)):0)

/* ========================================================================= */
/** @brief move an element in the heap up in the heap (position 0 is the top,
 * this kind of move is neded whenever we decrease the value in a heap element).
 * @param hp heap where we are working.
 * @param hcn element in the heap to move.
 * @return zero on success, non-zero otherwise.
 * */
#define EGeHeapSiftUp(hp,hcn) ({\
  EGeHeap_t*const __EGehp = (hp);\
  EGeHeapCn_t*const __EGecn = (hcn);\
  unsigned int __EGcpos = __EGecn->pos;\
  unsigned int __EGfpos = EGeHeapFatherId(__EGehp->d,__EGcpos);\
  EGeHeapCn_t*__EGfcn = __EGehp->cn[__EGfpos];\
  WARNINGL(EG_EHEAP_DEBUG,__EGehp->sz<=__EGcpos,"Heap Conector out of range");\
  while(__EGcpos && \
        EGlpNumIsLess(__EGecn->val,__EGfcn->val))\
  {\
    __EGfcn->pos = __EGcpos;\
    __EGehp->cn[__EGcpos] = __EGfcn;\
    __EGcpos = __EGfpos;\
    __EGfpos = EGeHeapFatherId(__EGehp->d,__EGcpos);\
    __EGfcn = __EGehp->cn[__EGfpos];\
  }\
  __EGecn->pos = __EGcpos;\
  __EGehp->cn[__EGcpos] = __EGecn;\
  0;})

/* ========================================================================= */
/** @brief Add an element to the heap
 * @param hp heap where to add the element.
 * @param hcn element to be added.
 * @return zero on success, non-zero otherwise.
 * */
#define EGeHeapAdd(hp,hcn) ({\
  EGeHeap_t*const __EGlhp = (hp);\
  EGeHeapCn_t*const __EGlcn = (hcn);\
  __EGlhp->sz == __EGlhp->max_sz ? (fprintf(stderr,"Heap "#hp" is full, can't"\
  " add element "#hcn), 1) : (__EGlcn->pos = __EGlhp->sz, \
  __EGlhp->cn[__EGlhp->sz] = __EGlcn, __EGlhp->sz +=1, EGeHeapSiftUp(__EGlhp,__EGlcn), 0);})

/* ========================================================================= */
/** @brief Give the first child for a given position.
 * @param id position that we want to get the first child.
 * @param d breath of the heap. */
#define EGeHeapFirstChildId(d,id) ((d)*(id)+1)

/* ========================================================================= */
/** @brief Move an element down in the heap (position 0 is the
 * top), this kind of operation is needed whenever we increase the value in a
 * heap element.
 * @param hp heap where we are working.
 * @param hcn element in the heap to move.
 * @return zero on success, non-zero otherwise.
 * */
#define EGeHeapSiftDown(hp,hcn) ({\
  EGeHeap_t*const __EGehp = (hp);\
  EGeHeapCn_t*const __EGecn = (hcn);\
  const unsigned int __EGhsz = __EGehp->sz;\
  unsigned int __EGcpos = __EGecn->pos;\
  unsigned int __EGfchd = EGeHeapFirstChildId(__EGehp->d,__EGcpos);\
  unsigned int __EGlchd = __EGfchd + __EGehp->d;\
  EGeHeapCn_t*__EGcchd = 0;\
  register unsigned int __EGehi = 0;\
  EXITL(EG_EHEAP_DEBUG, __EGcpos > __EGhsz , "Element "#hcn" out of range"\
        " in the heap "#hp);\
  while(__EGfchd < __EGhsz)\
  {\
    /* detect the minimum child */\
    __EGcchd = __EGehp->cn[__EGfchd];\
    for(__EGehi = __EGlchd > __EGhsz ? __EGhsz-1 : __EGlchd-1 ;\
      __EGehi > __EGfchd ; __EGehi--)\
      if(EGlpNumIsLess(__EGehp->cn[__EGehi]->val,__EGcchd->val))\
        __EGcchd = __EGehp->cn[__EGehi];\
    /* if the minimum child is less than the current position, move the minimum\
     * child to the position of the current element */\
    if(EGlpNumIsLess(__EGcchd->val,__EGecn->val))\
    {\
      __EGfchd = __EGcchd->pos;\
      __EGcchd->pos = __EGcpos;\
      __EGehp->cn[__EGcpos] = __EGcchd;\
      __EGecn->pos = __EGcpos = __EGfchd;\
      __EGehp->cn[__EGcpos] = __EGecn;\
      __EGfchd = EGeHeapFirstChildId(__EGehp->d,__EGcpos);\
      __EGlchd = __EGfchd + __EGehp->d;\
    }\
    /* else we exit the main loop */\
    else __EGfchd = UINT_MAX;\
  }\
  0;})

/* ========================================================================= */
/** @brief Change the value of an element in the heap.
 * @param hp heap where we are working.
 * @param hcn element in the heap that we are going to change it's value.
 * @param new_val new value for the element.
 * @return zero on success, non-zero otherwise.
 * */
#define EGeHeapChangeVal(hp,hcn,new_val) ({\
  (EGlpNumIsLess(new_val,(hcn)->val)) ? (EGlpNumCopy((hcn)->val,new_val),EGeHeapSiftUp(hp,hcn)) : (EGlpNumCopy((hcn)->val,new_val),EGeHeapSiftDown(hp,hcn));})

/* ========================================================================= */
/** @brief Eliminate an element from the heap, note that the position stored in
 * the eliminated element is reset to zero.
 * @param hp heap where we are working.
 * @param hcn element to eliminate from the heap.
 * @return zero on success, non-zero otherwise.
 * */
#define EGeHeapDel(hp,hcn) ({\
  EGeHeap_t*const __EGlhp = (hp);\
  unsigned int const __EGlcn = (hcn)->pos;\
  (hcn)->pos = EG_EHEAP_POISON;\
  (__EGlhp->sz) -= 1;\
  __EGlhp->cn[__EGlcn] = __EGlhp->cn[__EGlhp->sz];\
  __EGlhp->cn[__EGlcn]->pos = __EGlcn;\
  __EGlhp->cn[__EGlhp->sz] = 0;\
  __EGlhp->sz ? EGeHeapSiftDown(__EGlhp,__EGlhp->cn[__EGlcn]):0;})

/* ========================================================================= */
/** @brief Check the integrity of the given heap.
 * @param hp heap to check.
 * @return zero on success, non-zero otherwise.
 * */
#if EG_EHEAP_DEBUG <= DEBUG
#define EGeHeapCheck(hp) ({\
  EGeHeap_t*const __EGehp = (hp);\
  register unsigned int __EGehi = __EGehp->sz;\
  if(__EGehi)\
    while(--__EGehi)\
      if(__EGehp->cn[__EGehi]->pos != __EGehi || EGlpNumIsLess( __EGehp->cn[\
         __EGehi]->val,__EGehp->cn[EGeHeapFatherId(__EGehp->d,__EGehi)]->val))\
      {\
        MESSAGE(EG_EHEAP_DEBUG,"Element %u is wrong, pos %u val [%lf,%lf]"\
               ,__EGehi, __EGehp->cn[__EGehi]->pos, \
               EGlpNumToLf(__EGehp->cn[__EGehi]->val), \
               EGlpNumToLf(__EGehp->cn[EGeHeapFatherId(__EGehp->d,__EGehi)]->val));\
        break;\
      }\
  __EGehi;})
#else
#define EGeHeapCheck(hp) 0
#endif

/* ========================================================================= */
/** @brief set the breath of the heap, this function must be called only when
 * the heap is empty.
 * @param hp heap to set breath.
 * @param width new with for the heap.
 * @return zero on success, non-zero otherwise.
 * */
#define EGeHeapChangeD(hp,width) ({\
  EGeHeap_t*const __EGehp = (hp);\
  __EGehp->sz ? 1 : (__EGehp->d = (width), 0);})

/* ========================================================================= */
/** @} */
/* end of eg_eheap.h */
#endif

---