-
Notifications
You must be signed in to change notification settings - Fork 0
/
list.c
484 lines (434 loc) · 26.3 KB
/
list.c
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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
/*
|----------------------------------------------------------|
| This file contains the functions |
| used on the lists |
|----------------------------------------------------------|
*/
// -------------------------- Includes --------------------------
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
#include "timer.h"
#include <math.h>
// -------------------------- Functions --------------------------
p_list createEmptylistCell(int x) { // This function creates an empty list
p_list new_list = (p_list) malloc(sizeof(t_list)); // Allocation of memory for the new list
new_list->max_levels = x; // Initialization of the level of the list (Warning we define the level as the id of the last level -> mean level 6 = 7 levels)
p_cell* levels_tab = (p_cell*) malloc ((new_list->max_levels)*sizeof(p_cell)); // Initialization of the tab stocking all level of the list with (level + 1) value because of the level 0
for (int i = 0 ; i<x ; i++) {
levels_tab[i] = NULL;
}
new_list->levels = levels_tab;
return new_list; // Return the new list
}
void uniform_display_list (p_list list) {
p_cell level0cur; // Create a cursor to compare to higher value (because the first level will be the most complete, we have to check if we have to fill higher level or not)
p_cell tmp_h; // Create a cursor pointer to go through each level
for (int i = 0 ; i<list->max_levels ; i++){ // Loop which stop when all level including the last one are printed
printf("[list head_%d @-]",i); // Special printing for the head of the list
tmp_h = list->levels[i]; // Set the pointer to the head of the current level
level0cur = list->levels[0]; // Reset the level 0 cursor to the first cell of the level 0
while (level0cur!=NULL) { // Loop to go through all cell of the first level each level (and see if cell are there or not)
if (tmp_h!=level0cur || tmp_h==NULL) { // If the level cursor is not equal to the level 0 cursor it mean the cell aren't on the same level / or if the level cursor is NULL but there are still cell on the first level
for (int j = 0; j < cellLength(level0cur)+3; j++) { // Case where cell is not on the level, then we print "-" for the length of the corresponding cell at level 0 to keep it align
printf("-");
}
} else { // Case where we have to print the cell
printf("-->[ %d|@-]", tmp_h->value); // Special print for the cell
tmp_h = tmp_h->levels[i]; // If we have printed the cell on the level we can move to the next one to continue the checking for missing cell in between
}
level0cur = level0cur->levels[0]; // Move the checking cursor on the level 0 to the next value
}
printf("-->NULL\n"); // Special print to indicate the end of the level list
}
}
void display_list (p_list list) {
for (int i = 0 ; i<list->max_levels ; i++) { // Loop which stop when all level are printed (<=)
printf("[list head_%d @-]",i); // Special printing for the head of the list
p_cell tmp_h = list->levels[i]; // Set the moving pointer to the head of the level
while (tmp_h!=NULL){
printf("-->[ %d|@-]", tmp_h->value); // Special print for the cell
tmp_h = tmp_h->levels[i]; // Incrementing the moving pointer
}
printf("-->NULL\n"); // Special print to indicate the end of the level list
}
}
void show_level(p_list list, int level) {
p_cell tmp_h; // Set a moving pointer which will go through the levels
tmp_h = list->levels[level]; // Set the moving pointer to the head of the current level
printf("[list head_%d @-]",level); // Special printing for the head of the list
while (tmp_h!=NULL) { // Loop to print all elements from a level
printf("-->[ %d|@-]", tmp_h->value); // Special print for the cell
tmp_h=tmp_h->levels[level]; // Incrementing the level cursor
}
printf("-->NULL\n"); // Special print to indicate the end of the level list
}
int checkListCompatibility(p_list list, int level) {
if (level>list->max_levels || level<0) { // Check if the level is superior than the max level of the list
return 0;
} else {
return 1;
}
}
int std_search(p_list list, int value) {
startTimer();
int operation = 0; // Set a variable to count the number of operation
p_cell tmp = list->levels[0]; // Set the level cursor to the first cell of the level 0
while (tmp!=NULL) { // Loop to go through every element
operation++; // Increment the number of operations
if (tmp->value==value) { // If we find the value we return 1
printf("%d operations effectued\n", operation);
stopTimer();
displayTime();
return 1;
}
tmp=tmp->levels[0]; // Incrementing the level cursor
}
printf("%d operations effectued\n", operation);
stopTimer();
displayTime();
return 0; // If we haven't found anything at the end of the loop we return 0
}
int counter_std_search(p_list list, int value) {
int operation = 0; // Set a variable to count the number of operation
p_cell tmp = list->levels[0]; // Set the level cursor to the first cell of the level 0
while (tmp!=NULL) { // Loop to go through every element
operation++; // Increment the number of operations
if (tmp->value==value) { // If we find the value we return 1
return operation;
}
tmp=tmp->levels[0]; // Incrementing the level cursor
}
return operation; // If we haven't found anything at the end of the loop we return 0
}
int dtc_search(p_list list, int value) {
startTimer();
int operation = 0; // Initialize a counter for the differents operations
int current_level = list->max_levels-1; // Set a variable to decrement the current level
p_cell tmp = list->levels[current_level]; // Set the cursor to the head of the last level
while (tmp==NULL) { // Loop to downgrade every empty level
current_level--; // Decrement the current level variable
operation++; // Count an operation
tmp = list->levels[current_level]; // Move the cursor to the inferior level
}
while (tmp->value > value && current_level > 0) { // Loop to downgrade the level why the first value is superior than what we're searching
current_level--; // Decrement the current level variable
operation++; // Increment the operation counter
tmp = list->levels[current_level]; // Move the cursor to the inferior level
}
if (tmp->value == value) { // As we won't check the current value everytime, then we check is the first value is the one searched for
printf("%d operations effectued\n", operation);
stopTimer();
displayTime();
return 1;
}
if (current_level==0) { // If every value at every level were superior, it means the searched value is not in the tab
printf("%d operations effectued\n", operation);
stopTimer();
displayTime();
return 0;
}
while (current_level!=0 || tmp!=NULL) { // Loop to go through in the worst case to the level 0 and last value
if (tmp->levels[current_level] != NULL) { // We check if the next level is not NULL to avoid crash because we've tried to compare it
if (tmp->levels[current_level]->value == value) { // If the next value is the searched value we return 1
printf("%d operations effectued\n", operation);
stopTimer();
displayTime();
return 1;
} else if (tmp->levels[current_level]->value > value){ // If the next value is not the one searched for
if (current_level==0) { // Case where the next value is superior but the level is 0, we can't go lower so the value is not in the tab
printf("%d operations effectued\n", operation);
stopTimer();
displayTime();
return 0;
} else { // Case where we can go lower, so we try to see if the value in on lower level
current_level--; // So we decrement the current level
operation++; // And we increment the number of operation
}
} else { // Case where the next value is not NULL and inferior to what we're searching
tmp = tmp->levels[current_level]; // Move of the cursor to the next value on the level
operation++; // We increment the operation
}
} else if (value > tmp->value && current_level==0) { // Value is superior than the last value at last level of the list
printf("%d operations effectued\n", operation);
stopTimer();
displayTime();
return 0;
} else { // Case where there is no next value on higher level and we need to drop down till level 0 or level with next value
current_level--; // We decrement the current level variable
operation++; // We increment the operation counter
}
} // Case already treated in the previous if to optimize condition, should never be used
stopTimer();
displayTime();
return 0;
}
int counter_dtc_search(p_list list, int value) {
int operation = 0; // Initialize a counter for the differents operations
int current_level = list->max_levels-1; // Set a variable to decrement the current level
p_cell tmp = list->levels[current_level]; // Set the cursor to the head of the last level
while (tmp==NULL) { // Loop to downgrade every empty level
current_level--; // Decrement the current level variable
operation++; // Count an operation
tmp = list->levels[current_level]; // Move the cursor to the inferior level
}
while (tmp->value > value && current_level>0) { // Loop to downgrade the level why the first value is superior than what we're searching
current_level--; // Decrement the current level variable
operation++; // Increment the operation counter
tmp = list->levels[current_level]; // Move the cursor to the inferior level
}
if (current_level==0) { // If every value at every level were superior, it means the searched value is not in the tab
return operation;
}
if (tmp->value == value) { // As we won't check the current value everytime, then we check is the first value is the one searched for
return operation;
}
while (current_level!=0 || tmp!=NULL) { // Loop to go through in the worst case to the level 0 and last value
if (tmp->levels[current_level] != NULL) { // We check if the next level is not NULL to avoid crash because we've tried to compare it
if (tmp->levels[current_level]->value == value) { // If the next value is the searched value we return 1
return operation;
} else if (tmp->levels[current_level]->value > value){ // If the next value is not the one searched for
if (current_level==0) { // Case where the next value is superior but the level is 0, we can't go lower so the value is not in the tab
return operation;
} else { // Case where we can go lower, so we try to see if the value in on lower level
current_level--; // So we decrement the current level
operation++; // And we increment the number of operation
}
} else { // Case where the next value is not NULL and inferior to what we're searching
tmp = tmp->levels[current_level]; // Move of the cursor to the next value on the level
operation++; // We increment the operation
}
} else if (value > tmp->value && current_level==0) { // Value is superior than the last value at last level of the list
return operation;
} else { // Case where there is no next value on higher level and we need to drop down till level 0 or level with next value
current_level--; // We decrement the current level variable
operation++; // We increment the operation counter
}
} // Case already treated in the previous if to optimize condition, should never be used
return operation;
}
int print_space(int a, int b) {
int countA = 0;
int countB = 0;
while (a>10) {
countA++;
a/=10;
}
while (b>10) {
countB++;
b/=10;
}
return countA-countB-1;
}
void compareSearchMethod(int seed) {
srand(seed);
p_list testlist = createListPart2(15);
int** results = (int**) malloc (100*sizeof(int*));
results[0] = (int*) malloc (3*sizeof(int));
results[0][0]=rand()%250;
for (int i = 1 ; i<100 ; i++) {
results[i] = (int*) malloc (3*sizeof(int));
results[i][0] = results[i-1][0] + (rand()%3500);
}
for (int i = 0 ; i<100 ; i++) {
results[i][1] = counter_std_search(testlist, results[i][0]);
results[i][2] = counter_dtc_search(testlist, results[i][0]);
}
printf("tirage : ");
for (int i = 0 ; i<100 ; i++) {
printf ("%d\t", results[i][0]);
}
printf("\nstandard : ");
for (int i = 0 ; i<100 ; i++) {
printf ("%d\t", results[i][1]);
}
printf("\ndichotomous : ");
for (int i = 0 ; i<100 ; i++) {
for (int space = 0 ; space< print_space(results[i][1], results[i][3]) ; space++) {
printf(" ");
}
printf ("%d\t", results[i][2]);
}
printf("\n\n");
}
void compareSearchMethod2 (p_list testlist, int searchnumber) {
srand(searchnumber);
int random;
startTimer();
for (int i = 0 ; i<searchnumber ; i++) {
random = rand();
random %= 135000;
counter_std_search(testlist, random);
}
stopTimer();
displayTime();
srand(searchnumber);
startTimer();
for (int i = 0 ; i<searchnumber ; i++) {
random = rand();
random %= 135000;
counter_dtc_search(testlist, random);
}
stopTimer();
displayTime();
return;
}
// -------------------------- Tests Lists Functions --------------------------
p_list createTestList() {
p_list liste = createEmptylistCell(5);
p_cell cell1 = createEmptyCell(4, 4);
p_cell cell2 = createEmptyCell(3, 2);
p_cell cell3 = createEmptyCell(2, 3);
p_cell cell4 = createEmptyCell(1, 3);
p_cell cell5 = createEmptyCell(11, 1);
insertCell(cell1, liste, 4);
insertCell(cell2, liste, 2);
insertCell(cell3, liste, 3);
insertCell(cell4,liste, 3);
insertCell(cell5, liste, 1);
return liste;
}
p_list createOrderedList() {
p_list liste = createEmptylistCell(5);
p_cell cell1 = createEmptyCell(0, 1);
p_cell cell2 = createEmptyCell(10, 2);
p_cell cell3 = createEmptyCell(9, 3);
p_cell cell4 = createEmptyCell(8, 5);
p_cell cell5 = createEmptyCell(5, 4);
p_cell cell6 = createEmptyCell(2, 2);
p_cell cell7 = createEmptyCell(4, 2);
p_cell cell8 = createEmptyCell(3, 1);
p_cell cell9 = createEmptyCell(6, 1);
p_cell cell10 = createEmptyCell(1, 3);
insertCell(cell1, liste, 1);
insertCell(cell2, liste, 2);
insertCell(cell3, liste, 3);
insertCell(cell4, liste, 5);
insertCell(cell5, liste, 4);
insertCell(cell6, liste, 2);
insertCell(cell7, liste, 2);
insertCell(cell8, liste, 1);
insertCell(cell9, liste, 1);
insertCell(cell10, liste, 3);
return liste;
}
p_list createChaoticValueList() {
p_list liste = createEmptylistCell(5);
p_cell cell1 = createEmptyCell(-2, 1);
p_cell cell2 = createEmptyCell(-9, 2);
p_cell cell3 = createEmptyCell(100, 1);
p_cell cell4 = createEmptyCell(3004, 5);
p_cell cell5 = createEmptyCell(9, 4);
p_cell cell6 = createEmptyCell(10, 2);
p_cell cell7 = createEmptyCell(-23, 2);
p_cell cell8 = createEmptyCell(7, 1);
p_cell cell9 = createEmptyCell(5, 1);
p_cell cell10 = createEmptyCell(102, 3);
insertCell(cell1, liste, 1);
insertCell(cell2, liste, 2);
insertCell(cell3, liste, 1);
insertCell(cell4, liste, 5);
insertCell(cell5, liste, 4);
insertCell(cell6, liste, 2);
insertCell(cell7, liste, 2);
insertCell(cell8, liste, 1);
insertCell(cell9, liste, 1);
insertCell(cell10, liste, 3);
return liste;
}
p_list createWaveFormList() {
p_list liste = createEmptylistCell(5);
p_cell cell1 = createEmptyCell(2, 1);
p_cell cell2 = createEmptyCell(4, 1);
p_cell cell3 = createEmptyCell(6, 2);
p_cell cell4 = createEmptyCell(8, 3);
p_cell cell5 = createEmptyCell(10, 4);
p_cell cell6 = createEmptyCell(12, 5);
p_cell cell7 = createEmptyCell(14, 4);
p_cell cell8 = createEmptyCell(16, 3);
p_cell cell9 = createEmptyCell(18, 2);
p_cell cell10 = createEmptyCell(20, 1);
insertCell(cell1, liste, 1);
insertCell(cell2, liste,1);
insertCell(cell3, liste, 2);
insertCell(cell4, liste, 3);
insertCell(cell5, liste, 4);
insertCell(cell6, liste, 5);
insertCell(cell7, liste, 4);
insertCell(cell8, liste, 3);
insertCell(cell9, liste, 2);
insertCell(cell10, liste, 1);
return liste;
}
p_list createWaveFormList2() {
p_list liste = createEmptylistCell(5);
p_cell cell1 = createEmptyCell(-2, 3);
p_cell cell2 = createEmptyCell(4, 3);
p_cell cell3 = createEmptyCell(-6, 2);
p_cell cell4 = createEmptyCell(8, 4);
p_cell cell5 = createEmptyCell(-10, 4);
p_cell cell6 = createEmptyCell(12, 2);
p_cell cell7 = createEmptyCell(-14, 1);
p_cell cell8 = createEmptyCell(16, 5);
p_cell cell9 = createEmptyCell(-18, 5);
p_cell cell10 = createEmptyCell(20, 1);
insertCell(cell1, liste, 3);
insertCell(cell2, liste,3);
insertCell(cell3, liste, 2);
insertCell(cell4, liste, 4);
insertCell(cell5, liste, 4);
insertCell(cell6, liste, 2);
insertCell(cell7, liste, 1);
insertCell(cell8, liste, 5);
insertCell(cell9, liste, 5);
insertCell(cell10, liste, 1);
return liste;
}
void insertCell(p_cell cell, p_list list, int level) {
p_cell tmp_h; // Moving variable to move in the different levels
p_cell prev; // Set a previous cursor variable
for (int i = 0 ; i<level ; i++) { // Loop to go through all level of the new cell, <= because we count the last level
tmp_h = list->levels[i]; // We set the cursor pointer to the first cell of the level
if (tmp_h==NULL) { // If the level is empty create the new head of the level
list->levels[i] = cell;
} else {
if (tmp_h->value >= cell->value) { // If the new cell has to be inserted at the head of the list
cell->levels[i] = list->levels[i];
list->levels[i] = cell;
} else {
while (tmp_h->value <= cell->value && tmp_h->levels[i]!=NULL) { // Loop to move the cursor just after the emplacement to insert or at the end (as this two idea are not the same emplacmeent condition, this mays be optimizable)
prev = tmp_h;
tmp_h=tmp_h->levels[i];
}
if (tmp_h->value < cell->value) { // Case where we need to insert the new cell between the temporary cursor and it's next cell
cell->levels[i] = tmp_h->levels[i]; // The "next" of the new cell is attributed to the "next" of the temporary pointer
tmp_h->levels[i] = cell; // The "next" of the temporary pointer is set to the new cell
} else { // Case where we have to insert the new cell at the "next" of the prev cursor because the temporary one is equal to NULL
prev->levels[i]=cell; // Set the "next" of the prev to the new cell
cell->levels[i]=tmp_h; // Set the "next" of the new cell to NULL / the temporary cursor
}
}
}
}
}
void insertCellHead(p_cell cell, p_list list, int level) {
for (int i = 0 ; i<level ; i++) { // Loop to go through all level of the new cell, <= because we count the last level
if (list->levels[i]==NULL) { // If the level is empty create the new head of the level
list->levels[i] = cell;
} else { // Else insert correctly the cell at the head of thge level without losing the head of the level
cell->levels[i] = list->levels[i];
list->levels[i] = cell;
}
}
}
p_list createListPart2(int n) {
p_list new = createEmptylistCell(n);
int size = (int) pow(2,n)-1;
for (int i = 1 ; i<n+1 ; i++) {
for (int j = (int) pow(2,i-1); j<size+1; j+= (int) pow(2,i)) {
p_cell new_cell = createEmptyCell(j, i);
insertCell(new_cell, new, i);
}
}
return new;
}