blob: 48d294cc0d1b1087b403c1998e03e85bc49db1ce (
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#include <stdio.h>
#include "config.h"
#include "PLList.h"
/*****************************************************\
* *
* File de priorit� bas�e sur une liste cha�n�e tri�e. *
* *
\*****************************************************/
/*
* Cette file de priorit� a une structure non r�cursive. Elle se base sur
* une SList pour fonctionner.
*
*/
/*
* La m�thode "Union" est en fait l'algorithme "Fusion" du tri-fusion.
*/
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;
}
/*
* Cette m�thode va "d�crocher" l'�l�ment de la liste
* et va tenter de trouver sa nouvelle place, en se d�pla�ant
* depuis son ancienne place vers la "gauche".
*/
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;
}
/*
* Toutes les autres m�thodes sont "simples" (c'est � dire une lignes ou deux)
* et parlent d'elles-m�me. Nul besoin de commentaires pour elles. Elles se
* basent en grande partie sur la SList pr�sente dans la structure.
*/
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);
}
|