/*
 * Fheap.h
 *
 * The author of this software is Alain K\"{a}gi.
 *
 * Copyright (c) 1993 by Alain K\"{a}gi and the University of Wisconsin
 * Board of Trustees.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose without fee is hereby granted, provided that this entire notice
 * is included in all copies of any software which is or includes a copy
 * or modification of this software and in all copies of the supporting
 * documentation for such software.
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHOR NOR THE UNIVERSITY OF
 * WISCONSIN MAKE ANY REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING
 * THE MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR
 * PURPOSE.
 *
 * ------------------------------------------------------------------------
 *
 * This is an implementation of an algorithm described in the paper:
 *
 *   , by Michael L. Fredman and Robert Endre Tarjan, in
 *   Journal of Association for Computing Machinery, Vol. 34, No. 3,
 *   July 1987, Pages 596-615.
 *
 * The algorithm is theirs.  Any discrepancy between the algorithm
 * description which appears in the paper and this implementation is
 * a consequence of my misunderstanding of their intent.
 *   
 * ------------------------------------------------------------------------
 *
 * $Id$
 *
 */

#ifndef _fheap_h
#define _fheap_h

/*
 * The following "item.h" must define
 *   o a structure "Item",
 *   o the definition of NULL_ITEM,
 *   o the definition of "int LessThan(Item *, Item *);",
 *   o the definition of "int Equal(Item *, Item *);",
 *   o the definition of "Item *Subtract(Item *, void *);"
 *     this function must returm an item with its key reduced by a positive
 *     value passed as void *.
 */
#include "item.h"

typedef struct _Heap
{
  Item *     item;

  struct _Heap * parent;
  struct _Heap * child;
  struct _Heap * forward;
  struct _Heap * backward;
  int           rank;
  short         marked;
} HeapP;

#define NULL_HEAP	((void *)0)

/*
 * Initialize the package.  A single call is sufficient even if multiple
 * heaps are alive in the course of a computation.
 *
 * Special external object accessed:
 *   none
 *
 * Arguments:
 *   none
 *
 * Return values:
 *   none
 */
void  InitFHeap();

/*
 * Create a heap structure.
 *
 * Special external object accessed:
 *   none
 *
 * Arguments:
 *   none
 *
 * Return values:
 *   a heap, to be precise an empty, i.e. NULL_HEAP
 */
HeapP * MakeHeap();

/*
 * Find the item with lowest key.
 *
 * Special external object accessed:
 *   none
 *
 * Arguments:
 *   INPUT:	h	the structure to access, possibly NULL_HEAP
 *
 * Return values:
 *   an item if the heap is not empty
 *   NULL_ITEM otherwise
 */
Item * FindMin(HeapP * h);

/*
 * Insert an item in a heap.
 *
 * Special external object accessed:
 *   none
 *
 * Arguments:
 *   IN/OUT:	h	the structure to access, possibly NULL_HEAP
 *   INPUT:	i	the item to insert, must be different than NULL_ITEM
 *
 * Return values:
 *   a handle to the inserted item, useful in connection with Delete()
 *   and DecreaseKey().
 */
HeapP * Insert(HeapP * * h, Item * i);

/*
 * Meld to heaps.
 *
 * Special external object accessed:
 *   none
 *
 * Arguments:
 *   INPUT:	h1, h2	the heaps to meld, possibly NULL_HEAP
 *
 * Return values:
 *   a bigger heap, possibly NULL_HEAP
 */
HeapP * Meld(HeapP * h1, HeapP * h2);

/*
 * Remove the smallest item in a heap
 *
 * Special external object accessed:
 *   none
 *
 * Arguments:
 *   INPUT:	h	the structure to access, possibly NULL_HEAP
 *
 * Return values:
 *   a smaller heap, possibly NULL_HEAP
 */
HeapP * DeleteMin(HeapP * h);

/*
 * Decrease the key of an item in a heap.
 *
 * Special external object accessed:
 *   none
 *
 * Arguments:
 *   INPUT:	h	the structure to access, must be different than
 *			NULL_HEAP
 *   INPUT:	i	the item to change, must different than NULL_HEAP
 *   INPUT:	delta	a "positive" value which will be subtracted from
 *                      the key in i.
 *
 * Return values:
 *   a heap, possibly NULL_HEAP
 */
HeapP * DecreaseKey(HeapP * h, HeapP * i, int delta);

/*
 * Delete an entry in a heap.
 *
 * Special external object accessed:
 *   none
 *
 * Arguments:
 *   INPUT:	h	the structure to access, must be different than
 *			NULL_HEAP
 *   INPUT:	i	the item to delete, must be different than NULL_HEAP
 *
 * Return values:
 *   a smaller heap, possibly NULL_HEAP
 */
HeapP * Delete(HeapP * h, HeapP * i);

/*
 * Search for an item with a particular key in a heap.
 * Beware the fibonacci heaps are not efficient at searching.
 *
 * Special external object accessed:
 *   none
 *
 * Arguments:
 *   INPUT:	h	the structure to access, possibly NULL_HEAP
 *   INPUT:	item	the item to search for in h (only the key in item is
 *                      accessed through Equal() and LessThan())
 *
 * Return values:
 *   an handle to the item, possibly NULL_HEAP
 */
HeapP * Find(HeapP * h, Item * item);

/*
 * Converts a item handle into an item pointer.
 *
 * Special external object accessed:
 *   none
 *
 * Arguments:
 *   INPUT:	h	the item handle, must be different than NULL_HEAP
 *
 * Return values:
 *   an pointer to the item
 */
Item * ItemOf(HeapP * h);

#endif