diff options
Diffstat (limited to 'lib/BHeap.cc')
| -rw-r--r-- | lib/BHeap.cc | 278 |
1 files changed, 278 insertions, 0 deletions
diff --git a/lib/BHeap.cc b/lib/BHeap.cc new file mode 100644 index 0000000..4d7cc9e --- /dev/null +++ b/lib/BHeap.cc @@ -0,0 +1,278 @@ +#include <stdio.h> +#include "config.h" +#include "BHeap.h" +#include "CList.h" + +static int d, Depths[65536]; + +void BHeap::Dump(ostream & os) +{ + int i; + + if (Degree == -1) { + os << _(" * Head cell.\n |\n"); + for (i = 0; i < 65535; i++) + Depths[i] = 1; + d = 1; + } else { + for (i = 1; i <= d; i++) + os << (Depths[i] ? " |" : " "); + os << (Child ? "_ " : "__ ") << Key << endl; + } + if (Child) { + Depths[d] = (Brother != NULL); + d++; + Child->Dump(os); + d--; + } + if (Brother) { + Brother->Dump(os); + } +} + +int BHeap::rn(void) +{ + int n = 0; + + if (Degree != -1) { + n++; + } + if (Child) { + n += Child->rn(); + } + if (Brother) { + n += Brother->rn(); + } + return n; +} + +void BHeap::Link(BHeap * z) +{ + Father = z; + Brother = z->Child; + z->Child = this; + z->Degree = z->Degree + 1; +} + +void BHeap::Merge(BHeap * H) +{ + BHeap *P1, *P2, *T1, *T2; + + Key += H->Key; + H->Key = 0; + + for (P1 = this, P2 = H->Brother; P1->Brother && P2;) { + if (P1->Brother->Degree < P2->Degree) { // P1 < P2, jump over P1. + P1 = P1->Brother; + } else { // P1 >= P2. We will insert P2 after P1. + T1 = P1->Brother; + T2 = P2->Brother; + P1->Brother = P2; + P2->Brother = T1; + P1 = P2; + P2 = T2; + } + } + if (!(P1->Brother)) + P1->Brother = P2; + H->Brother = NULL; +} + +BHeap::BHeap(void):Degree(-1), Father(NULL), Child(NULL), Brother(NULL), +FP(new CList) +{ + type = T_BHEAP; +} + +BHeap::BHeap(Key_t IKey, Datas_t const &IDatas):PriorityList(IKey, IDatas), +Degree(0), Father(NULL), Child(NULL), Brother(NULL) +{ + type = T_BHEAP; +#ifdef DEBUG + nc++; +#endif +} + +BHeap::~BHeap(void) +{ + if (Degree == -1) + delete FP; + + if (Child) { + delete Child; + } + if (Brother) { + delete Brother; + } +#ifdef DEBUG + nd++; +#endif +} + +Cell BHeap::Min(void) +{ + BHeap *x = this, *y = NULL; + int min = P_INFINITY; + + for (; x; x = x->Brother) { + if ((x->Key < min)) { + min = x->Key; + y = x; + } + } + + return y->FP; +} + +Cell BHeap::Insert(BHeap * E) +{ + BHeap *H; + + if (Degree != -1) + exception(2, _("Insert: not over Head.")); + if (!(H = new BHeap)) + exception(5, _("Insert: No more memory.")); + H->Brother = E; + Union(H); + delete H; + + return ((E->FP = ((CList *) (FP->Insert(Key, E))))); +} + +Cell BHeap::Insert(Key_t IKey, Datas_t const &IDatas) +{ + BHeap *P; + + Key++; + + if (!(P = new BHeap(IKey, IDatas))) + exception(5, _("Insert: No more memory.")); + return (Insert(P)); +} + +Key_t BHeap::Extract_Min(Datas_t & Datas) +{ + BHeap *x, *y = NULL, *P, *P2, *P3, *Before; + Key_t k; + int min = P_INFINITY; + + P = Before = this; + + if (!Brother) + exception(4, _("Extract_Min: Priority List is empty.")); + + Key--; + + for (x = Brother; x; x = x->Brother) { + if ((x->Key < min)) { + min = x->Key; + y = x; + Before = P; + } + P = x; + } + + Before->Brother = y->Brother; + + Before = new BHeap; + + for (P = y->Child; P;) { + P2 = Before->Brother; + P3 = P->Brother; + Before->Brother = P; + P->Brother = P2; + P = P3; + } + + Before->Key = 0; + Union(Before); + + k = y->Key; + y->Brother = y->Child = NULL; + FP->Delete(Datas, ((Cell) y->FP)); + Datas = y->Datas; + delete y; + + return k; +} + +PriorityList *BHeap::Union(PriorityList * P) +{ + BHeap *x, *Before, *After; + + if ((P->GetType()) != (((PriorityList *) this)->GetType())) + return GenericUnion(P); + + Merge((BHeap *) P); + if (!(Brother)) { + return this; + } + Before = this; + x = Brother; + After = x->Brother; + while (After) { + if ((x->Degree != After->Degree) + || ((After->Brother) + && (After->Brother->Degree == x->Degree))) { + Before = x; + x = After; + } else { + if (x->Key <= After->Key) { + x->Brother = After->Brother; + After->Link(x); + } else { + Before->Brother = After; + x->Link(After); + x = After; + } + } + After = x->Brother; + } + return this; +} + +bool BHeap::Lower_Key(Cell x, Key_t NKey) +{ + BHeap *y, *z, *tx = ((BHeap *) ((CList *) x)->Datas); + + if (NKey > tx->Key) + return false; + tx->Key = NKey; + + for (y = tx, z = tx->Father; z && (y->Key < z->Key); + y = z, z = y->Father) { + SWAP(y->Datas, z->Datas); + SWAP(y->Key, z->Key); + SWAP(y->FP, z->FP); + SWAP(((CList *) (y->FP))->Datas, ((CList *) (z->FP))->Datas); + } + + return true; +} + +Key_t BHeap::Delete(Datas_t & Datas, Cell x) +{ + Key_t K; + + K = ReadKey(x); + + Lower_Key(x, M_INFINITY); + Extract_Min(Datas); + + return K; +} + +bool BHeap::IsEmpty(void) +{ + return (!(Brother)); +} + +Key_t BHeap::ReadKey(Cell C) +{ + return ((BHeap *) ((CList *) C)->Datas)->Key; +} + +Datas_t BHeap::ReadDatas(Cell C) +{ + return ((BHeap *) ((CList *) C)->Datas)->Datas; +} |