~ubuntu-branches/ubuntu/lucid/igraph/lucid

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2007  Gabor Csardi <csardi@rmki.kfki.hu>
   MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
   
   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.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include "memory.h"
#include "random.h"
#include "error.h"
#include "config.h"

#include <assert.h>
#include <string.h> 		/* memcpy & co. */
#include <stdlib.h>

#define PARENT(x)     (((x)+1)/2-1)
#define LEFTCHILD(x)  (((x)+1)*2-1)
#define RIGHTCHILD(x) (((x)+1)*2)
  
/**
 * \ingroup heap
 * \function igraph_heap_init
 * \brief Initializes an empty heap object.
 *
 * Creates an empty heap, but allocates size for some elements.
 * \param h Pointer to an uninitialized heap object.
 * \param alloc_size Number of elements to allocate memory for.
 * \return Error code.
 * 
 * Time complexity: O(\p alloc_size), assuming memory allocation is a
 * linear operation.
 */

int FUNCTION(igraph_heap,init)(TYPE(igraph_heap)* h, long int alloc_size) {
  if (alloc_size <= 0 ) { alloc_size=1; }
  h->stor_begin=igraph_Calloc(alloc_size, BASE);
  if (h->stor_begin==0) {
    IGRAPH_ERROR("heap init failed", IGRAPH_ENOMEM);
  }
  h->stor_end=h->stor_begin + alloc_size;
  h->end=h->stor_begin;
  h->destroy=1;
  
  return 0;  
}

/**
 * \ingroup heap
 * \function igraph_heap_init_array
 * \brief Build a heap from an array.
 * 
 * Initializes a heap object from an array, the heap is also
 * built of course (constructor).
 * \param h Pointer to an uninitialized heap object.
 * \param data Pointer to an array of base data type.
 * \param len The length of the array at \p data.
 * \return Error code.
 * 
 * Time complexity: O(n), the number of elements in the heap.
 */

int FUNCTION(igraph_heap,init_array)(TYPE(igraph_heap) *h, BASE* data, long int len) {
  h->stor_begin=igraph_Calloc(len, BASE);
  if (h->stor_begin==0) {
    IGRAPH_ERROR("heap init from array failed", IGRAPH_ENOMEM);
  }
  h->stor_end=h->stor_begin+len;
  h->end=h->stor_end;
  h->destroy=1;

  memcpy(h->stor_begin, data, len*sizeof(igraph_real_t));

  FUNCTION(igraph_heap,i_build) (h->stor_begin, h->end-h->stor_begin, 0);
  
  return 0;
}

/**
 * \ingroup heap
 * \function igraph_heap_destroy
 * \brief Destroys an initialized heap object.
 * 
 * \param h The heap object.
 * 
 * Time complexity: O(1).
 */

void FUNCTION(igraph_heap,destroy)(TYPE(igraph_heap)* h) {  
  if (h->destroy) {
    if (h->stor_begin != 0) {
      igraph_Free(h->stor_begin);
      h->stor_begin=0;
    }
  }
}

/**
 * \ingroup heap
 * \function igraph_heap_empty
 * \brief Decides whether a heap object is empty.
 * 
 * \param h The heap object.
 * \return \c TRUE if the heap is empty, \c FALSE otherwise.
 * 
 * TIme complexity: O(1).
 */

igraph_bool_t FUNCTION(igraph_heap,empty)(TYPE(igraph_heap)* h) {
  assert(h != NULL);
  assert(h->stor_begin != NULL);
  return h->stor_begin == h->end;
}

/**
 * \ingroup heap
 * \function igraph_heap_push
 * \brief Add an element.
 * 
 * Adds an element to the heap.
 * \param h The heap object.
 * \param elem The element to add.
 * \return Error code.
 * 
 * Time complexity: O(log n), n is the number of elements in the
 * heap if no reallocation is needed, O(n) otherwise. It is ensured
 * that n push operations are performed in O(n log n) time.
 */

int FUNCTION(igraph_heap,push)(TYPE(igraph_heap)* h, BASE elem) {
  assert(h != NULL);
  assert(h->stor_begin != NULL);
	
  /* full, allocate more storage */
  if (h->stor_end == h->end) {
    long int new_size = FUNCTION(igraph_heap,size)(h) * 2;
    if (new_size == 0) { new_size = 1; }
    IGRAPH_CHECK(FUNCTION(igraph_heap,reserve)(h, new_size));
  }
	
  *(h->end) = elem;
  h->end += 1;

  /* maintain heap */
  FUNCTION(igraph_heap,i_shift_up)(h->stor_begin, FUNCTION(igraph_heap,size)(h),
				   FUNCTION(igraph_heap,size)(h)-1);
  
  return 0;
}

/**
 * \ingroup heap
 * \function igraph_heap_top
 * \brief Top element.
 * 
 * For maximum heaps this is the largest, for minimum heaps the
 * smallest element of the heap.
 * \param h The heap object.
 * \return The top element.
 *
 * Time complexity: O(1).
 */

BASE FUNCTION(igraph_heap,top)(TYPE(igraph_heap)* h) {
  assert(h != NULL);
  assert(h->stor_begin != NULL);
  assert(h->stor_begin != h->end);
  
  return h->stor_begin[0];
}

/**
 * \ingroup heap
 * \function igraph_heap_delete_top
 * \brief Return and removes the top element
 * 
 * Removes and returns the top element of the heap. For maximum heaps
 * this is the largest, for minimum heaps the smallest element.
 * \param h The heap object.
 * \return The top element.
 * 
 * Time complexity: O(log n), n is the number of elements in the
 * heap.
 */

BASE FUNCTION(igraph_heap,delete_top)(TYPE(igraph_heap)* h) {
  BASE tmp;

  assert(h != NULL);
  assert(h->stor_begin != NULL);

  tmp=h->stor_begin[0];
  FUNCTION(igraph_heap,i_switch)(h->stor_begin, 0, FUNCTION(igraph_heap,size)(h)-1);
  h->end -= 1;
  FUNCTION(igraph_heap,i_sink)(h->stor_begin, h->end-h->stor_begin, 0);
  
  return tmp;
}

/**
 * \ingroup heap
 * \function igraph_heap_size
 * \brief Number of elements
 * 
 * Gives the number of elements in a heap.
 * \param h The heap object.
 * \return The number of elements in the heap.
 * 
 * Time complexity: O(1).
 */

long int FUNCTION(igraph_heap,size)(TYPE(igraph_heap)* h) {
  assert(h != NULL);
  assert(h->stor_begin != NULL);
  return h->end - h->stor_begin;
}

/**
 * \ingroup heap
 * \function igraph_heap_reserve
 * \brief Allocate more memory
 *
 * Allocates memory for future use. The size of the heap is
 * unchanged. If the heap is larger than the \p size parameter then
 * nothing happens.
 * \param h The heap object.
 * \param size The number of elements to allocate memory for.
 * \return Error code.
 * 
 * Time complexity: O(\p size) if \p size is larger than the current
 * number of elements. O(1) otherwise.
 */

int FUNCTION(igraph_heap,reserve)(TYPE(igraph_heap)* h, long int size) {
  long int actual_size=FUNCTION(igraph_heap,size)(h);
  BASE *tmp;
  assert(h != NULL);
  assert(h->stor_begin != NULL);
  
  if (size <= actual_size) { return 0; }
  
  tmp=igraph_Realloc(h->stor_begin, size, BASE);
  if (tmp==0) {
    IGRAPH_ERROR("heap reserve failed", IGRAPH_ENOMEM);
  }
  h->stor_begin=tmp;
  h->stor_end=h->stor_begin + size;
  h->end=h->stor_begin+actual_size;
  
  return 0;
}

/**
 * \ingroup heap
 * \brief Build a heap, this should not be called directly.
 */

void FUNCTION(igraph_heap,i_build)(BASE* arr, 
				   long int size, long int head) {

  if (RIGHTCHILD(head) < size) { 
    /* both subtrees */
    FUNCTION(igraph_heap,i_build)(arr, size, LEFTCHILD(head) );
    FUNCTION(igraph_heap,i_build)(arr, size, RIGHTCHILD(head));
    FUNCTION(igraph_heap,i_sink)(arr, size, head);
  } else if (LEFTCHILD(head) < size) {
    /* only left */
    FUNCTION(igraph_heap,i_build)(arr, size, LEFTCHILD(head));
    FUNCTION(igraph_heap,i_sink)(arr, size, head);
  } else {
    /* none */
  }
}

/**
 * \ingroup heap
 * \brief Shift an element upwards in a heap, this should not be
 * called directly.
 */

void FUNCTION(igraph_heap,i_shift_up)(BASE* arr, long int size, long int elem) {
  
  if (elem==0 || arr[elem] HEAPLESS arr[PARENT(elem)]) { 
    /* at the top */
  } else {
    FUNCTION(igraph_heap,i_switch)(arr, elem, PARENT(elem));
    FUNCTION(igraph_heap,i_shift_up)(arr, size, PARENT(elem));
  }
}

/**
 * \ingroup heap
 * \brief Moves an element down in a heap, this function should not be
 * called directly.
 */

void FUNCTION(igraph_heap,i_sink)(BASE* arr, long int size, long int head) {

  if (LEFTCHILD(head) >= size) { 
    /* no subtrees */
  } else if (RIGHTCHILD(head) == size ||
	     arr[LEFTCHILD(head)] HEAPMOREEQ arr[RIGHTCHILD(head)]) {
    /* sink to the left if needed */
    if (arr[head] HEAPLESS arr[LEFTCHILD(head)]) {
      FUNCTION(igraph_heap,i_switch)(arr, head, LEFTCHILD(head));
      FUNCTION(igraph_heap,i_sink)(arr, size, LEFTCHILD(head));
    }
  } else {
    /* sink to the right */
    if (arr[head] HEAPLESS arr[RIGHTCHILD(head)]) {
      FUNCTION(igraph_heap,i_switch)(arr, head, RIGHTCHILD(head));
      FUNCTION(igraph_heap,i_sink)(arr, size, RIGHTCHILD(head));
    }
  }
}

/**
 * \ingroup heap
 * \brief Switches two elements in a heap, this function should not be
 * called directly.
 */

void FUNCTION(igraph_heap,i_switch)(BASE* arr, long int e1, long int e2) {
  if (e1!=e2) {
    BASE tmp=arr[e1];
    arr[e1]=arr[e2];
    arr[e2]=tmp;
  }
}