heap-def.h

Go to the documentation of this file.

/*
Copyright (C) 2007-12 Andrea Vedaldi and Brian Fulkerson.
All rights reserved.

This file is part of the VLFeat library and is made available under
the terms of the BSD license (see the COPYING file).
*/

#include "host.h"
#include <assert.h>

#ifndef VL_HEAP_prefix
#error "VL_HEAP_prefix must be defined"
#endif

#ifndef VL_HEAP_array
#ifndef VL_HEAP_type
#error "VL_HEAP_type must be defined if VL_HEAP_array is not"
#endif
#define VL_HEAP_array       VL_HEAP_type*
#define VL_HEAP_array_const VL_HEAP_type const*
#endif

#ifndef VL_HEAP_array_const
#define VL_HEAP_array_const VL_HEAP_array
#endif

#ifdef __DOXYGEN__
#define VL_HEAP_prefix  HeapObject       
#define VL_HEAP_type    HeapType         
#define VL_HEAP_array   HeapType*        
#define VL_HEAP_array   HeapType const*  
#endif

/* ---------------------------------------------------------------- */

#ifndef VL_HEAP_DEF_H
#define VL_HEAP_DEF_H

VL_INLINE vl_uindex
vl_heap_parent (vl_uindex index)
{
  if (index == 0) return 0 ;
  return (index - 1) / 2 ;
}

VL_INLINE vl_uindex
vl_heap_left_child (vl_uindex index)
{
  return 2 * index + 1 ;
}

VL_INLINE vl_uindex
vl_heap_right_child (vl_uindex index)
{
  return vl_heap_left_child (index) + 1 ;
}

/* VL_HEAP_DEF_H */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_cmp) || defined(__DOXYGEN__)
#define VL_HEAP_cmp VL_XCAT(VL_HEAP_prefix, _cmp)

VL_INLINE VL_HEAP_type
VL_HEAP_cmp
(VL_HEAP_array_const array,
 vl_uindex indexA,
 vl_uindex indexB)
{
  return array[indexA] - array[indexB] ;
}

/* VL_HEAP_cmp */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_swap) || defined(__DOXYGEN__)
#define VL_HEAP_swap VL_XCAT(VL_HEAP_prefix, _swap)

VL_INLINE void
VL_HEAP_swap
(VL_HEAP_array array,
 vl_uindex indexA,
 vl_uindex indexB)
{
  VL_HEAP_type t = array [indexA] ;
  array [indexA] = array [indexB] ;
  array [indexB] = t ;
}

/* VL_HEAP_swap */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_up) || defined(__DOXYGEN__)
#define VL_HEAP_up VL_XCAT(VL_HEAP_prefix, _up)

VL_INLINE void
VL_HEAP_up
(VL_HEAP_array array, vl_size heapSize, vl_uindex index)
{
  vl_uindex leftIndex  = vl_heap_left_child (index) ;
  vl_uindex rightIndex = vl_heap_right_child (index) ;

  /* no childer: stop */
  if (leftIndex >= heapSize) return ;

  /* only left childer: easy */
  if (rightIndex >= heapSize) {
    if (VL_HEAP_cmp (array, index, leftIndex) > 0) {
      VL_HEAP_swap (array, index, leftIndex) ;
    }
    return ;
  }

  /* both childern */
  {
    if (VL_HEAP_cmp (array, leftIndex, rightIndex) < 0) {
      /* swap with left */
      if (VL_HEAP_cmp (array, index, leftIndex) > 0) {
        VL_HEAP_swap (array, index, leftIndex) ;
        VL_HEAP_up (array, heapSize, leftIndex) ;
      }
    } else {
      /* swap with right */
      if (VL_HEAP_cmp (array, index, rightIndex) > 0) {
        VL_HEAP_swap (array, index, rightIndex) ;
        VL_HEAP_up (array, heapSize, rightIndex) ;
      }
    }
  }
}

/* VL_HEAP_up */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_down) || defined(__DOXYGEN__)
#define VL_HEAP_down VL_XCAT(VL_HEAP_prefix, _down)

VL_INLINE void
VL_HEAP_down
(VL_HEAP_array array, vl_uindex index)
{
  vl_uindex parentIndex ;

  if (index == 0) return  ;

  parentIndex = vl_heap_parent (index) ;

  if (VL_HEAP_cmp (array, index, parentIndex) < 0) {
    VL_HEAP_swap (array, index, parentIndex) ;
    VL_HEAP_down (array, parentIndex) ;
  }
}

/* VL_HEAP_down */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_push) || defined(__DOXYGEN__)
#define VL_HEAP_push VL_XCAT(VL_HEAP_prefix, _push)

VL_INLINE void
VL_HEAP_push
(VL_HEAP_array array, vl_size *heapSize)
{
  VL_HEAP_down (array, *heapSize) ;
  *heapSize += 1 ;
}

/* VL_HEAP_push */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_pop) || defined(__DOXYGEN__)
#define VL_HEAP_pop VL_XCAT(VL_HEAP_prefix, _pop)

VL_INLINE vl_uindex
VL_HEAP_pop
(VL_HEAP_array array, vl_size *heapSize)
{
  assert (*heapSize) ;

  *heapSize -= 1 ;

  VL_HEAP_swap (array, 0, *heapSize) ;

  if (*heapSize > 1) {
    VL_HEAP_up (array, *heapSize, 0) ;
  }

  return *heapSize ;
}

/* VL_HEAP_pop */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_update) || defined(__DOXYGEN__)
#define VL_HEAP_update VL_XCAT(VL_HEAP_prefix, _update)

VL_INLINE void
VL_HEAP_update
(VL_HEAP_array array,
 vl_size heapSize,
 vl_uindex index)
{
  VL_HEAP_up (array, heapSize, index) ;
  VL_HEAP_down (array, index) ;
}

/* VL_HEAP_update */
#endif

/* ---------------------------------------------------------------- */

#undef VL_HEAP_cmp
#undef VL_HEAP_swap
#undef VL_HEAP_up
#undef VL_HEAP_down
#undef VL_HEAP_push
#undef VL_HEAP_pop
#undef VL_HEAP_update
#undef VL_HEAP_prefix
#undef VL_HEAP_type
#undef VL_HEAP_array
#undef VL_HEAP_array_const