heap.c

Go to the documentation of this file.

#include "heap.h"

#include "error.h"
#include "defines.h"

#include <math.h>

#define HEAP_PARENT(i) ((unsigned int)floor(((i)-1)/2))

#define HEAP_CHILD(i) (2*(i)+1)

void HeapUp(unsigned int i,Theap *heap);

void  HeapDown(unsigned int i,Theap *heap);


void HeapUp(unsigned int i,Theap *heap)
{ 
  unsigned int p,c;
  void *ep,*ec;
  boolean swap;
  unsigned int idC,idP;

  swap=TRUE;
  c=i;
  ec=GetVectorElement(c,&(heap->data));
  while((c>0)&&(swap))
    {
      p=HEAP_PARENT(c);
      ep=GetVectorElement(p,&(heap->data));
      
      if (heap->LessThan(ec,ep,heap->userData))
        {
          if (heap->hasIDs)
            {
              idC=*(unsigned int *)GetVectorElement(c,&(heap->data2id));
              idP=*(unsigned int *)GetVectorElement(p,&(heap->data2id));
              SwapVectorElements(idC,idP,&(heap->id2data));
              SwapVectorElements(c,p,&(heap->data2id));
            }
          SwapVectorElements(c,p,&(heap->data));

          swap=TRUE;
          /*Prepare to continue moving up*/
          c=p;
          ec=GetVectorElement(c,&(heap->data));
        }
      else
        swap=FALSE;
    }
}

void HeapDown(unsigned int i,Theap *heap)
{
  unsigned int p,c,c1,c2;
  void *ep,*ec,*ec1,*ec2;
  boolean swap;
  unsigned int idC,idP;

  swap=TRUE;
  p=i;
  ep=GetVectorElement(p,&(heap->data));
  while((p<heap->last)&&(swap))
    {
      swap=FALSE;
      c1=HEAP_CHILD(p);
      
      if (c1<heap->last)
        {
          ec1=GetVectorElement(c1,&(heap->data));
          c2=c1+1;
          if (c2<heap->last)
            {
              ec2=GetVectorElement(c2,&(heap->data));
              if (heap->LessThan(ec1,ec2,heap->userData))
                {c=c1; ec=ec1;}
              else
                {c=c2; ec=ec2;}
            }
          else
            {c=c1; ec=ec1;}

          if (heap->LessThan(ec,ep,heap->userData))
            {
              if (heap->hasIDs)
                {
                  idC=*(unsigned int *)GetVectorElement(c,&(heap->data2id));
                  idP=*(unsigned int *)GetVectorElement(p,&(heap->data2id));
                  SwapVectorElements(idC,idP,&(heap->id2data));
                  SwapVectorElements(c,p,&(heap->data2id));
                }
              SwapVectorElements(c,p,&(heap->data));
              
              swap=TRUE;
              
              /*Prepare to continue moving down*/
              p=c;
              ep=GetVectorElement(p,&(heap->data));
            }
        }
    }
}

boolean LessThanID(void *a,void *b,void *userData)
{
  return(*((unsigned int *)a)<*((unsigned int *)b));
}

boolean LessThanDouble(void *a,void *b,void *userData)
{
  return(*((double *)a)<*((double *)b));
}

boolean LessThanPtr(void *a,void *b,void *userData)
{
  return(*((void **)a)<*((void **)b));
}


void InitHeap(unsigned int ele_size,
              void (* Copy)(void *,void*),
              void (* Delete)(void *),
              boolean (* LessThan)(void *,void*,void *),
              void *userData,
              boolean hasIDs,
              unsigned int max_ele,Theap *heap)
{
  InitVector(ele_size,Copy,Delete,max_ele,&(heap->data));
  heap->hasIDs=hasIDs;
  if (heap->hasIDs)
    {
      InitVector(sizeof(unsigned int),CopyID,DeleteID,max_ele,&(heap->data2id));
      /*mapping id2data can be larger that max_element but it will be extended
        as necessary*/
      InitVector(sizeof(unsigned int),CopyID,DeleteID,max_ele,&(heap->id2data));
    }
  heap->last=0;
  heap->LessThan=LessThan;
  heap->userData=userData;
}

void CopyHeap(Theap *h_dst,Theap *h_src)
{
  CopyVector(&(h_dst->data),&(h_src->data));
  h_dst->hasIDs=h_src->hasIDs;
  if (h_dst->hasIDs)
    {
      CopyVector(&(h_dst->data2id),&(h_src->data2id));
      CopyVector(&(h_dst->id2data),&(h_src->id2data));
    }
  h_dst->last=h_src->last;
  h_dst->LessThan=h_src->LessThan;
  h_dst->userData=h_src->userData;
}

unsigned int HeapSize(Theap *heap)
{
  return(heap->last);
}

boolean HeapEmpty(Theap *heap)
{
  return(heap->last==0);
}

void AddElement2Heap(unsigned int id,void *e,Theap *heap)
{
  SetVectorElement(heap->last,e,&(heap->data));
  if (heap->hasIDs)
    {
      SetVectorElement(heap->last,&id,&(heap->data2id));
      SetVectorElement(id,&(heap->last),&(heap->id2data));
    }

  heap->last++;
  
  HeapUp(heap->last-1,heap);
}

void UpdateHeapElement(unsigned int id,Theap *heap)
{
  if (heap->hasIDs)
    {
      unsigned int i;
      
      i=GetHeapPosition(id,heap);
      
      /*only one of those take effect*/
      HeapUp(i,heap);
      
      /*if headup did something then the element is not in
        position 'i' any longer but the call to headdown
        is harmless (it tries to move down and element that
        is already in a proper position) */
      HeapDown(i,heap);
    }
  else
    Error("Elements without associated identifier can not be updated");
}

void *GetHeapElement(unsigned int i,Theap *heap)
{
  if (i<heap->last)
    return(GetVectorElement(i,&(heap->data)));
  else
    return(NULL);
}


void *GetHeapElementWithID(unsigned int id,Theap *heap)
{
  if (heap->hasIDs)
    return(GetHeapElement(GetHeapPosition(id,heap),heap));
  else
    return((void *)NULL);
}

unsigned int GetHeapPosition(unsigned int id,Theap *heap)
{
  if (heap->hasIDs)
    return(*(unsigned int *)GetVectorElement(id,&(heap->id2data)));
  else
    return(NO_UINT);
}

void ExtractMinElement(void *e,Theap *heap)
{
  if (heap->last>0)
    {
      unsigned int id;

      if (heap->hasIDs)
        {
          id=*(unsigned int *)GetVectorElement(0,&(heap->data2id));
          RemoveVectorElement(id,&(heap->id2data));

          SwapVectorElements(heap->last-1,0,&(heap->data2id));
          RemoveVectorElement(heap->last-1,&(heap->data2id));
        }

      SwapVectorElements(heap->last-1,0,&(heap->data));
      ExtractVectorElement(heap->last-1,e,&(heap->data));

      heap->last--;
      HeapDown(0,heap);
    }
  else
    Error("Extracting an element from a empty heap");
}


void ResetHeap(Theap *heap)
{
  if (heap->hasIDs)
    {
      ResetVector(&(heap->data2id));
      ResetVector(&(heap->id2data));
    }
  ResetVector(&(heap->data));
  heap->last=0;
}


void DeleteHeap(Theap *heap)
{
  ResetHeap(heap);
  if (heap->hasIDs)
    {
      DeleteVector((void *)&(heap->id2data));
      DeleteVector((void *)&(heap->data2id));
    }
  DeleteVector((void *)&(heap->data));
}