1130803Smarcel/* A Fibonacci heap datatype.
2130803Smarcel   Copyright 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
3130803Smarcel   Contributed by Daniel Berlin (dan@cgsoftware.com).
4130803Smarcel
5130803SmarcelThis file is part of GCC.
6130803Smarcel
7130803SmarcelGCC is free software; you can redistribute it and/or modify it
8130803Smarcelunder the terms of the GNU General Public License as published by
9130803Smarcelthe Free Software Foundation; either version 2, or (at your option)
10130803Smarcelany later version.
11130803Smarcel
12130803SmarcelGCC is distributed in the hope that it will be useful, but
13130803SmarcelWITHOUT ANY WARRANTY; without even the implied warranty of
14130803SmarcelMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15130803SmarcelGeneral Public License for more details.
16130803Smarcel
17130803SmarcelYou should have received a copy of the GNU General Public License
18130803Smarcelalong with GCC; see the file COPYING.  If not, write to
19130803Smarcelthe Free Software Foundation, 59 Temple Place - Suite 330,
20130803SmarcelBoston, MA 02111-1307, USA.  */
21130803Smarcel
22130803Smarcel/* Fibonacci heaps are somewhat complex, but, there's an article in
23130803Smarcel   DDJ that explains them pretty well:
24130803Smarcel
25130803Smarcel   http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
26130803Smarcel
27130803Smarcel   Introduction to algorithms by Corman and Rivest also goes over them.
28130803Smarcel
29130803Smarcel   The original paper that introduced them is "Fibonacci heaps and their
30130803Smarcel   uses in improved network optimization algorithms" by Tarjan and
31130803Smarcel   Fredman (JACM 34(3), July 1987).
32130803Smarcel
33130803Smarcel   Amortized and real worst case time for operations:
34130803Smarcel
35130803Smarcel   ExtractMin: O(lg n) amortized. O(n) worst case.
36130803Smarcel   DecreaseKey: O(1) amortized.  O(lg n) worst case.
37130803Smarcel   Insert: O(2) amortized. O(1) actual.
38130803Smarcel   Union: O(1) amortized. O(1) actual.  */
39130803Smarcel
40130803Smarcel#ifndef _FIBHEAP_H_
41130803Smarcel#define _FIBHEAP_H_
42130803Smarcel
43130803Smarcel#include "ansidecl.h"
44130803Smarcel
45130803Smarceltypedef long fibheapkey_t;
46130803Smarcel
47130803Smarceltypedef struct fibheap
48130803Smarcel{
49130803Smarcel  size_t nodes;
50130803Smarcel  struct fibnode *min;
51130803Smarcel  struct fibnode *root;
52130803Smarcel} *fibheap_t;
53130803Smarcel
54130803Smarceltypedef struct fibnode
55130803Smarcel{
56130803Smarcel  struct fibnode *parent;
57130803Smarcel  struct fibnode *child;
58130803Smarcel  struct fibnode *left;
59130803Smarcel  struct fibnode *right;
60130803Smarcel  fibheapkey_t key;
61130803Smarcel  void *data;
62130803Smarcel#ifdef __GNUC__
63130803Smarcel  __extension__ unsigned long int degree : 31;
64130803Smarcel  __extension__ unsigned long int mark : 1;
65130803Smarcel#else
66130803Smarcel  unsigned int degree : 31;
67130803Smarcel  unsigned int mark : 1;
68130803Smarcel#endif
69130803Smarcel} *fibnode_t;
70130803Smarcel
71130803Smarcelextern fibheap_t fibheap_new PARAMS ((void));
72130803Smarcelextern fibnode_t fibheap_insert PARAMS ((fibheap_t, fibheapkey_t, void *));
73130803Smarcelextern int fibheap_empty PARAMS ((fibheap_t));
74130803Smarcelextern fibheapkey_t fibheap_min_key PARAMS ((fibheap_t));
75130803Smarcelextern fibheapkey_t fibheap_replace_key PARAMS ((fibheap_t, fibnode_t,
76130803Smarcel						 fibheapkey_t));
77130803Smarcelextern void *fibheap_replace_key_data PARAMS ((fibheap_t, fibnode_t,
78130803Smarcel					       fibheapkey_t, void *));
79130803Smarcelextern void *fibheap_extract_min PARAMS ((fibheap_t));
80130803Smarcelextern void *fibheap_min PARAMS ((fibheap_t));
81130803Smarcelextern void *fibheap_replace_data PARAMS ((fibheap_t, fibnode_t, void *));
82130803Smarcelextern void *fibheap_delete_node PARAMS ((fibheap_t, fibnode_t));
83130803Smarcelextern void fibheap_delete PARAMS ((fibheap_t));
84130803Smarcelextern fibheap_t fibheap_union PARAMS ((fibheap_t, fibheap_t));
85130803Smarcel
86130803Smarcel#endif /* _FIBHEAP_H_ */
87