1169695Skan/* A Fibonacci heap datatype.
2169695Skan   Copyright 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
3169695Skan   Contributed by Daniel Berlin (dan@cgsoftware.com).
4169695Skan
5169695SkanThis file is part of GCC.
6169695Skan
7169695SkanGCC is free software; you can redistribute it and/or modify it
8169695Skanunder the terms of the GNU General Public License as published by
9169695Skanthe Free Software Foundation; either version 2, or (at your option)
10169695Skanany later version.
11169695Skan
12169695SkanGCC is distributed in the hope that it will be useful, but
13169695SkanWITHOUT ANY WARRANTY; without even the implied warranty of
14169695SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15169695SkanGeneral Public License for more details.
16169695Skan
17169695SkanYou should have received a copy of the GNU General Public License
18169695Skanalong with GCC; see the file COPYING.  If not, write to
19169695Skanthe Free Software Foundation, 51 Franklin Street - Fifth Floor,
20169695SkanBoston, MA 02110-1301, USA.  */
21169695Skan
22169695Skan/* Fibonacci heaps are somewhat complex, but, there's an article in
23169695Skan   DDJ that explains them pretty well:
24169695Skan
25169695Skan   http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
26169695Skan
27169695Skan   Introduction to algorithms by Corman and Rivest also goes over them.
28169695Skan
29169695Skan   The original paper that introduced them is "Fibonacci heaps and their
30169695Skan   uses in improved network optimization algorithms" by Tarjan and
31169695Skan   Fredman (JACM 34(3), July 1987).
32169695Skan
33169695Skan   Amortized and real worst case time for operations:
34169695Skan
35169695Skan   ExtractMin: O(lg n) amortized. O(n) worst case.
36169695Skan   DecreaseKey: O(1) amortized.  O(lg n) worst case.
37169695Skan   Insert: O(2) amortized. O(1) actual.
38169695Skan   Union: O(1) amortized. O(1) actual.  */
39169695Skan
40169695Skan#ifndef _FIBHEAP_H_
41169695Skan#define _FIBHEAP_H_
42169695Skan
43169695Skan#include "ansidecl.h"
44169695Skan
45169695Skantypedef long fibheapkey_t;
46169695Skan
47169695Skantypedef struct fibheap
48169695Skan{
49169695Skan  size_t nodes;
50169695Skan  struct fibnode *min;
51169695Skan  struct fibnode *root;
52169695Skan} *fibheap_t;
53169695Skan
54169695Skantypedef struct fibnode
55169695Skan{
56169695Skan  struct fibnode *parent;
57169695Skan  struct fibnode *child;
58169695Skan  struct fibnode *left;
59169695Skan  struct fibnode *right;
60169695Skan  fibheapkey_t key;
61169695Skan  void *data;
62169695Skan#if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4)
63169695Skan  __extension__ unsigned long int degree : 31;
64169695Skan  __extension__ unsigned long int mark : 1;
65169695Skan#else
66169695Skan  unsigned int degree : 31;
67169695Skan  unsigned int mark : 1;
68169695Skan#endif
69169695Skan} *fibnode_t;
70169695Skan
71169695Skanextern fibheap_t fibheap_new (void);
72169695Skanextern fibnode_t fibheap_insert (fibheap_t, fibheapkey_t, void *);
73169695Skanextern int fibheap_empty (fibheap_t);
74169695Skanextern fibheapkey_t fibheap_min_key (fibheap_t);
75169695Skanextern fibheapkey_t fibheap_replace_key (fibheap_t, fibnode_t,
76169695Skan                                         fibheapkey_t);
77169695Skanextern void *fibheap_replace_key_data (fibheap_t, fibnode_t,
78169695Skan                                       fibheapkey_t, void *);
79169695Skanextern void *fibheap_extract_min (fibheap_t);
80169695Skanextern void *fibheap_min (fibheap_t);
81169695Skanextern void *fibheap_replace_data (fibheap_t, fibnode_t, void *);
82169695Skanextern void *fibheap_delete_node (fibheap_t, fibnode_t);
83169695Skanextern void fibheap_delete (fibheap_t);
84169695Skanextern fibheap_t fibheap_union (fibheap_t, fibheap_t);
85169695Skan
86169695Skan#endif /* _FIBHEAP_H_ */
87