xref: /dflybsd-src/contrib/gcc-8.0/include/fibheap.h (revision 38fd149817dfbff97799f62fcb70be98c4e32523)
1*38fd1498Szrj /* A Fibonacci heap datatype.
2*38fd1498Szrj    Copyright (C) 1998-2018 Free Software Foundation, Inc.
3*38fd1498Szrj    Contributed by Daniel Berlin (dan@cgsoftware.com).
4*38fd1498Szrj 
5*38fd1498Szrj This file is part of GCC.
6*38fd1498Szrj 
7*38fd1498Szrj GCC is free software; you can redistribute it and/or modify it
8*38fd1498Szrj under the terms of the GNU General Public License as published by
9*38fd1498Szrj the Free Software Foundation; either version 2, or (at your option)
10*38fd1498Szrj any later version.
11*38fd1498Szrj 
12*38fd1498Szrj GCC is distributed in the hope that it will be useful, but
13*38fd1498Szrj WITHOUT ANY WARRANTY; without even the implied warranty of
14*38fd1498Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15*38fd1498Szrj General Public License for more details.
16*38fd1498Szrj 
17*38fd1498Szrj You should have received a copy of the GNU General Public License
18*38fd1498Szrj along with GCC; see the file COPYING.  If not, write to
19*38fd1498Szrj the Free Software Foundation, 51 Franklin Street - Fifth Floor,
20*38fd1498Szrj Boston, MA 02110-1301, USA.  */
21*38fd1498Szrj 
22*38fd1498Szrj /* Fibonacci heaps are somewhat complex, but, there's an article in
23*38fd1498Szrj    DDJ that explains them pretty well:
24*38fd1498Szrj 
25*38fd1498Szrj    http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
26*38fd1498Szrj 
27*38fd1498Szrj    Introduction to algorithms by Corman and Rivest also goes over them.
28*38fd1498Szrj 
29*38fd1498Szrj    The original paper that introduced them is "Fibonacci heaps and their
30*38fd1498Szrj    uses in improved network optimization algorithms" by Tarjan and
31*38fd1498Szrj    Fredman (JACM 34(3), July 1987).
32*38fd1498Szrj 
33*38fd1498Szrj    Amortized and real worst case time for operations:
34*38fd1498Szrj 
35*38fd1498Szrj    ExtractMin: O(lg n) amortized. O(n) worst case.
36*38fd1498Szrj    DecreaseKey: O(1) amortized.  O(lg n) worst case.
37*38fd1498Szrj    Insert: O(2) amortized. O(1) actual.
38*38fd1498Szrj    Union: O(1) amortized. O(1) actual.  */
39*38fd1498Szrj 
40*38fd1498Szrj #ifndef _FIBHEAP_H_
41*38fd1498Szrj #define _FIBHEAP_H_
42*38fd1498Szrj 
43*38fd1498Szrj #include "ansidecl.h"
44*38fd1498Szrj 
45*38fd1498Szrj #ifdef __cplusplus
46*38fd1498Szrj extern "C" {
47*38fd1498Szrj #endif
48*38fd1498Szrj 
49*38fd1498Szrj typedef long fibheapkey_t;
50*38fd1498Szrj 
51*38fd1498Szrj typedef struct fibheap
52*38fd1498Szrj {
53*38fd1498Szrj   size_t nodes;
54*38fd1498Szrj   struct fibnode *min;
55*38fd1498Szrj   struct fibnode *root;
56*38fd1498Szrj } *fibheap_t;
57*38fd1498Szrj 
58*38fd1498Szrj typedef struct fibnode
59*38fd1498Szrj {
60*38fd1498Szrj   struct fibnode *parent;
61*38fd1498Szrj   struct fibnode *child;
62*38fd1498Szrj   struct fibnode *left;
63*38fd1498Szrj   struct fibnode *right;
64*38fd1498Szrj   fibheapkey_t key;
65*38fd1498Szrj   void *data;
66*38fd1498Szrj #if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4)
67*38fd1498Szrj   __extension__ unsigned long int degree : 31;
68*38fd1498Szrj   __extension__ unsigned long int mark : 1;
69*38fd1498Szrj #else
70*38fd1498Szrj   unsigned int degree : 31;
71*38fd1498Szrj   unsigned int mark : 1;
72*38fd1498Szrj #endif
73*38fd1498Szrj } *fibnode_t;
74*38fd1498Szrj 
75*38fd1498Szrj extern fibheap_t fibheap_new (void);
76*38fd1498Szrj extern fibnode_t fibheap_insert (fibheap_t, fibheapkey_t, void *);
77*38fd1498Szrj extern int fibheap_empty (fibheap_t);
78*38fd1498Szrj extern fibheapkey_t fibheap_min_key (fibheap_t);
79*38fd1498Szrj extern fibheapkey_t fibheap_replace_key (fibheap_t, fibnode_t,
80*38fd1498Szrj                                          fibheapkey_t);
81*38fd1498Szrj extern void *fibheap_replace_key_data (fibheap_t, fibnode_t,
82*38fd1498Szrj                                        fibheapkey_t, void *);
83*38fd1498Szrj extern void *fibheap_extract_min (fibheap_t);
84*38fd1498Szrj extern void *fibheap_min (fibheap_t);
85*38fd1498Szrj extern void *fibheap_replace_data (fibheap_t, fibnode_t, void *);
86*38fd1498Szrj extern void *fibheap_delete_node (fibheap_t, fibnode_t);
87*38fd1498Szrj extern void fibheap_delete (fibheap_t);
88*38fd1498Szrj extern fibheap_t fibheap_union (fibheap_t, fibheap_t);
89*38fd1498Szrj 
90*38fd1498Szrj #ifdef __cplusplus
91*38fd1498Szrj }
92*38fd1498Szrj #endif
93*38fd1498Szrj 
94*38fd1498Szrj #endif /* _FIBHEAP_H_ */
95