blob: 5234b91f0643637b65bbb3e7ec968c3bd768a2e5 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
#include <stdio.h>
#include "config.h"
#include "PLList.h"
PriorityList *PLList::Union(PriorityList * P)
{
if ((P->GetType()) != (((PriorityList *) this)->GetType())) {
return GenericUnion(P);
} else {
CList *x, *y, *t;
PLList *T = ((PLList *) P);
x = &Head;
y = T->Head.Right;
Key += T->Key;
while (x->Right && y) {
if (x->Right->Key > y->Key) {
t = y->Right;
y->Right = x->Right;
y->Left = x;
x->Right->Left = y;
x->Right = y;
y = t;
}
x = x->Right;
}
if (y) {
x->Right = y;
y->Left = x;
}
T->Head.Right = NULL;
}
return this;
}
bool PLList::Lower_Key(Cell x, Key_t NKey)
{
CList *T = ((CList *) x), *t;
if (T->Key < NKey)
return false;
T->Key = NKey;
if (T->Left)
T->Left->Right = T->Right;
if (T->Right)
T->Right->Left = T->Left;
for (t = T->Left; ((t->Left->Left) && (NKey < t->Left->Key));
t = t->Left) ;
T->Left = t->Left;
T->Right = t;
t->Left = T->Left->Right = T;
return true;
}
PLList::PLList(void)
{
type = T_PLLIST;
Key = 0;
Datas = NULL;
};
PLList::~PLList(void)
{
delete Head.Right;
};
Key_t PLList::ReadKey(Cell C)
{
return Head.ReadKey(C);
};
Datas_t PLList::ReadDatas(Cell C)
{
return Head.ReadDatas(C);
};
int PLList::rn(void)
{
int n = 0;
for (CList * x = Head.Right; x; x = x->Right)
n++;
return n;
}
void PLList::Dump(ostream & os)
{
os << _(" * Head cell\n |\n");
for (CList * x = Head.Right; x; x = x->Right)
os << " |__ " << x->Key << endl;
}
bool PLList::IsEmpty(void)
{
return (!(Head.Right));
}
Cell PLList::Min(void)
{
return Head.Right;
}
Cell PLList::Insert(Key_t IKey, Datas_t const &IDatas)
{
Key++;
return Head.Insert(IKey, IDatas);
}
Key_t PLList::Extract_Min(Datas_t & Datas)
{
if (!Key)
exception(4, _("Extract_Min: Priority List is empty."));
Key--;
return Head.Delete(Datas, Head.Right);
}
Key_t PLList::Delete(Datas_t & Datas, Cell x)
{
return Head.Delete(Datas, x);
}
|
