include/

2001-08-20  Daniel Berlin  <dan@cgsoftware.com>

	* fibheap.h: New file. Fibonacci heap.

libiberty/
2001-08-20  Daniel Berlin  <dan@cgsoftware.com>

	* fibheap.c: New file. Fibonacci heap.

	* Makefile.in (CFILES): Add fibheap.c.
	(REQUIRED_OFILES): Add fibheap.o.
	(fibheap.o): Add dependencies for fibheap.o.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@45062 138bc75d-0d04-0410-961f-82ee72b054a4

2 files changed, 84 insertions, 0 deletions

diff --git a/include/ChangeLog b/include/ChangeLog
index ed435beb78f..d3fe4a571c6 100644
--- a/include/ChangeLog
+++ b/include/ChangeLog
@@ -1,3 +1,7 @@
+2001-08-20  Daniel Berlin  <dan@cgsoftware.com>
+
+	* fibheap.h: New file. Fibonacci heap.
+
 2001-08-18  Zack Weinberg  <zackw@panix.com>
 
 	* ansidecl.h: Reorganize for readability, remove documentation
diff --git a/include/fibheap.h b/include/fibheap.h
new file mode 100644
index 00000000000..16db65e093d
--- /dev/null
+++ b/include/fibheap.h
@@ -0,0 +1,80 @@
+/* A Fibonacci heap datatype.
+   Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+   Contributed by Daniel Berlin (dan@cgsoftware.com).
+
+This file is part of GNU CC.
+   
+GNU CC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU CC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU CC; see the file COPYING.  If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
+
+/* Fibonacci heaps are somewhat complex, but, there's an
+   article in DDJ on them  that explains them pretty well:
+
+   http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
+
+   Introduction to algorithms by Corman and Rivest also goes over
+   them.
+
+   The original paper that introduced them is "Fibonacci heaps and their
+   uses in improved network optimization algorithms" by Tarjan and
+   Fredman (JACM 34(3), July 1987).
+
+   Amortized and real worst case time for operations:
+
+   ExtractMin: O(lg n) amortized. O(n) worst case.
+   DecreaseKey: O(1) amortized.  O(lg n) worst case. 
+   Insert: O(2) amortized. O(1) actual.  
+   Union: O(1) amortized. O(1) actual.
+
+  
+*/
+
+#ifndef _FIBHEAP_H_
+#define _FIBHEAP_H_
+
+#include <ansidecl.h>
+
+typedef struct fibheap
+{
+  size_t nodes;
+  struct fibnode *min;
+  struct fibnode *root;
+} *fibheap_t;
+typedef long fibheapkey_t;
+typedef struct fibnode
+{
+  struct fibnode *parent;
+  struct fibnode *child;
+  struct fibnode *left;
+  struct fibnode *right;
+  unsigned int degree : sizeof(size_t) * CHAR_BIT - 2;
+  unsigned int mark:1;
+  fibheapkey_t key;
+  void *data;
+} *fibnode_t;
+
+extern fibheap_t fibheap_new PARAMS ((void));
+extern fibnode_t fibheap_insert PARAMS ((fibheap_t, fibheapkey_t, void *));
+extern int fibheap_empty PARAMS ((fibheap_t));
+extern fibheapkey_t fibheap_min_key PARAMS ((fibheap_t));
+extern fibheapkey_t fibheap_replace_key PARAMS ((fibheap_t, fibnode_t, fibheapkey_t));
+extern void *fibheap_replace_key_data PARAMS ((fibheap_t, fibnode_t, fibheapkey_t, void *));
+extern void *fibheap_extract_min PARAMS ((fibheap_t));
+extern void *fibheap_min PARAMS ((fibheap_t));
+extern void *fibheap_replace_data PARAMS ((fibheap_t, fibnode_t, void *));
+extern void *fibheap_delete_node PARAMS ((fibheap_t, fibnode_t));
+extern void fibheap_delete PARAMS ((fibheap_t));
+extern fibheap_t fibheap_union PARAMS ((fibheap_t, fibheap_t));
+#endif /* _FIBHEAP_H_ */