Slicer  4.10
Slicer is a multi-platform, free and open source software package for visualization and medical image computing
FibHeap.h
Go to the documentation of this file.
1 // exclude from VTK wrapping
2 #ifndef __VTK_WRAP__
3 
4 #ifndef FIBHEAP_H
5 #define FIBHEAP_H
6 
7 //***************************************************************************
8 // The Fibonacci heap implementation contained in FIBHEAP.H and FIBHEAP.CPP
9 // is Copyright (c) 1996 by John Boyer
10 //
11 // Once this Fibonacci heap implementation (the software) has been published
12 // by Dr. Dobb's Journal, permission to use and distribute the software is
13 // granted provided that this copyright notice remains in the source and
14 // and the author (John Boyer) is acknowledged in works that use this program.
15 //
16 // Every effort has been made to ensure that this implementation is free of
17 // errors. Nonetheless, the author (John Boyer) assumes no liability regarding
18 // your use of this software.
19 //
20 // The author would also be very glad to hear from anyone who uses the
21 // software or has any feedback about it.
22 // Email: jboyer@gulf.csc.uvic.ca
23 //***************************************************************************
24 
25 
26 #define OK 0
27 #define NOTOK -1
28 
29 #include <cstdio>
30 
31 //======================================================
32 // Fibonacci Heap Node Class
33 //======================================================
34 
35 class FibHeap;
36 
38 {
39  friend class FibHeap;
40  FibHeapNode *Left, *Right, *Parent, *Child;
41  short Degree, Mark, NegInfinityFlag;
42 
43 protected:
44  inline int FHN_Cmp(FibHeapNode& RHS) {
45  if (NegInfinityFlag)
46  return RHS.NegInfinityFlag ? 0 : -1;
47  return RHS.NegInfinityFlag ? 1 : 0;
48  }
49  inline void FHN_Assign(FibHeapNode& RHS) {
50  NegInfinityFlag = RHS.NegInfinityFlag;
51  }
52 
53 public:
54  inline FibHeapNode() {
55  Left = Right = Parent = Child = NULL;
56  Degree = Mark = NegInfinityFlag = 0;
57  }
58  virtual ~FibHeapNode();
59  virtual void operator =(FibHeapNode& RHS);
60  virtual int operator ==(FibHeapNode& RHS);
61  virtual int operator <(FibHeapNode& RHS);
62 
63  virtual void Print();
64 };
65 
66 //========================================================================
67 // Fibonacci Heap Class
68 //========================================================================
69 
70 class FibHeap
71 {
72  FibHeapNode *MinRoot;
73  long NumNodes, NumTrees, NumMarkedNodes;
74  int HeapOwnershipFlag;
75 
76 public:
77  FibHeap();
78  virtual ~FibHeap();
79 
80  // The Standard Heap Operations
81  void Insert(FibHeapNode *NewNode);
82  void Union(FibHeap *OtherHeap);
83  inline FibHeapNode *Minimum() { return MinRoot; }
85  int DecreaseKey(FibHeapNode *theNode, FibHeapNode& NewKey);
86  int Delete(FibHeapNode *theNode);
87  bool IsEmpty() {return (MinRoot == NULL);}
88 
89  // Extra utility functions
90  int GetHeapOwnership() { return HeapOwnershipFlag; };
91  void SetHeapOwnership() { HeapOwnershipFlag = 1; };
92  void ClearHeapOwnership() { HeapOwnershipFlag = 0; };
93  long GetNumNodes() { return NumNodes; };
94  long GetNumTrees() { return NumTrees; };
95  long GetNumMarkedNodes() { return NumMarkedNodes; };
96  void Print(FibHeapNode *Tree = NULL, FibHeapNode *theParent=NULL);
97 
98 private:
99  // Internal functions that help to implement the Standard Operations
100  inline void _Exchange(FibHeapNode* &N1, FibHeapNode* &N2) {
101  FibHeapNode *Temp; Temp = N1; N1 = N2; N2 = Temp;
102  }
103  void _Consolidate();
104  void _Link(FibHeapNode *, FibHeapNode *);
105  void _AddToRootList(FibHeapNode *);
106  void _Cut(FibHeapNode *, FibHeapNode *);
107  void _CascadingCut(FibHeapNode *);
108 };
109 
110 #endif /* FIBHEAP_H */
111 
112 #endif //__VTK_WRAP__
virtual ~FibHeap()
virtual int operator<(FibHeapNode &RHS)
void ClearHeapOwnership()
Definition: FibHeap.h:92
int Delete(FibHeapNode *theNode)
virtual int operator==(FibHeapNode &RHS)
virtual void operator=(FibHeapNode &RHS)
void FHN_Assign(FibHeapNode &RHS)
Definition: FibHeap.h:49
int DecreaseKey(FibHeapNode *theNode, FibHeapNode &NewKey)
void Union(FibHeap *OtherHeap)
FibHeapNode * ExtractMin()
bool IsEmpty()
Definition: FibHeap.h:87
virtual ~FibHeapNode()
long GetNumMarkedNodes()
Definition: FibHeap.h:95
void Insert(FibHeapNode *NewNode)
void Print(FibHeapNode *Tree=NULL, FibHeapNode *theParent=NULL)
virtual void Print()
int GetHeapOwnership()
Definition: FibHeap.h:90
long GetNumTrees()
Definition: FibHeap.h:94
FibHeapNode()
Definition: FibHeap.h:54
int FHN_Cmp(FibHeapNode &RHS)
Definition: FibHeap.h:44
FibHeapNode * Minimum()
Definition: FibHeap.h:83
void SetHeapOwnership()
Definition: FibHeap.h:91
long GetNumNodes()
Definition: FibHeap.h:93