Slicer  4.8
Slicer is a multi-platform, free and open source software package for visualization and medical image computing
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
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; }
84  FibHeapNode *ExtractMin();
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 int operator<(FibHeapNode &RHS)
void ClearHeapOwnership()
Definition: FibHeap.h:92
virtual int operator==(FibHeapNode &RHS)
virtual void operator=(FibHeapNode &RHS)
void FHN_Assign(FibHeapNode &RHS)
Definition: FibHeap.h:49
friend class FibHeap
Definition: FibHeap.h:39
bool IsEmpty()
Definition: FibHeap.h:87
virtual ~FibHeapNode()
long GetNumMarkedNodes()
Definition: FibHeap.h:95
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