189857Sobrien/* A Fibonacci heap datatype.
2104834Sobrien   Copyright 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
389857Sobrien   Contributed by Daniel Berlin (dan@cgsoftware.com).
489857Sobrien
589857SobrienThis file is part of GCC.
689857Sobrien
789857SobrienGCC is free software; you can redistribute it and/or modify it
889857Sobrienunder the terms of the GNU General Public License as published by
989857Sobrienthe Free Software Foundation; either version 2, or (at your option)
1089857Sobrienany later version.
1189857Sobrien
1289857SobrienGCC is distributed in the hope that it will be useful, but
1389857SobrienWITHOUT ANY WARRANTY; without even the implied warranty of
1489857SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
1589857SobrienGeneral Public License for more details.
1689857Sobrien
1789857SobrienYou should have received a copy of the GNU General Public License
1889857Sobrienalong with GCC; see the file COPYING.  If not, write to
19218822Sdimthe Free Software Foundation, 51 Franklin Street - Fifth Floor,
20218822SdimBoston, MA 02110-1301, USA.  */
2189857Sobrien
2289857Sobrien/* Fibonacci heaps are somewhat complex, but, there's an article in
2389857Sobrien   DDJ that explains them pretty well:
2489857Sobrien
2589857Sobrien   http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
2689857Sobrien
2789857Sobrien   Introduction to algorithms by Corman and Rivest also goes over them.
2889857Sobrien
2989857Sobrien   The original paper that introduced them is "Fibonacci heaps and their
3089857Sobrien   uses in improved network optimization algorithms" by Tarjan and
3189857Sobrien   Fredman (JACM 34(3), July 1987).
3289857Sobrien
3389857Sobrien   Amortized and real worst case time for operations:
3489857Sobrien
3589857Sobrien   ExtractMin: O(lg n) amortized. O(n) worst case.
3689857Sobrien   DecreaseKey: O(1) amortized.  O(lg n) worst case.
3789857Sobrien   Insert: O(2) amortized. O(1) actual.
3889857Sobrien   Union: O(1) amortized. O(1) actual.  */
3989857Sobrien
4089857Sobrien#ifndef _FIBHEAP_H_
4189857Sobrien#define _FIBHEAP_H_
4289857Sobrien
43104834Sobrien#include "ansidecl.h"
4489857Sobrien
4589857Sobrientypedef long fibheapkey_t;
4689857Sobrien
4789857Sobrientypedef struct fibheap
4889857Sobrien{
4989857Sobrien  size_t nodes;
5089857Sobrien  struct fibnode *min;
5189857Sobrien  struct fibnode *root;
5289857Sobrien} *fibheap_t;
5389857Sobrien
5489857Sobrientypedef struct fibnode
5589857Sobrien{
5689857Sobrien  struct fibnode *parent;
5789857Sobrien  struct fibnode *child;
5889857Sobrien  struct fibnode *left;
5989857Sobrien  struct fibnode *right;
6089857Sobrien  fibheapkey_t key;
6189857Sobrien  void *data;
62218822Sdim#if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4)
63130561Sobrien  __extension__ unsigned long int degree : 31;
64130561Sobrien  __extension__ unsigned long int mark : 1;
65130561Sobrien#else
6689857Sobrien  unsigned int degree : 31;
6789857Sobrien  unsigned int mark : 1;
68130561Sobrien#endif
6989857Sobrien} *fibnode_t;
7089857Sobrien
71218822Sdimextern fibheap_t fibheap_new (void);
72218822Sdimextern fibnode_t fibheap_insert (fibheap_t, fibheapkey_t, void *);
73218822Sdimextern int fibheap_empty (fibheap_t);
74218822Sdimextern fibheapkey_t fibheap_min_key (fibheap_t);
75218822Sdimextern fibheapkey_t fibheap_replace_key (fibheap_t, fibnode_t,
76218822Sdim                                         fibheapkey_t);
77218822Sdimextern void *fibheap_replace_key_data (fibheap_t, fibnode_t,
78218822Sdim                                       fibheapkey_t, void *);
79218822Sdimextern void *fibheap_extract_min (fibheap_t);
80218822Sdimextern void *fibheap_min (fibheap_t);
81218822Sdimextern void *fibheap_replace_data (fibheap_t, fibnode_t, void *);
82218822Sdimextern void *fibheap_delete_node (fibheap_t, fibnode_t);
83218822Sdimextern void fibheap_delete (fibheap_t);
84218822Sdimextern fibheap_t fibheap_union (fibheap_t, fibheap_t);
8589857Sobrien
8689857Sobrien#endif /* _FIBHEAP_H_ */
87