blob: b74d7d342e2c6a0e00968de1202ec1f0c7e7ed18 (
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
|
#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()) != 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)
{
}
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);
}
|
