Repository navigation
Expand file tree
/
Copy pathset.h
More file actions
151 lines (133 loc) · 4.59 KB
/
Copy pathset.h
File metadata and controls
151 lines (133 loc) · 4.59 KB
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
#ifndef SET_JL
#define SET_JL
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#include "../HashTableChaining/hashtablechaining.h"
// Define how our (non linear and dynamic) set is structured.
// It's a hash table with chaining where we only use the keys: a value is either in the set or not, never twice.
typedef struct{
HashTable table; // The hash table that stores the values of the set as keys.
} Set;
/********************/
/* FUNCTIONS */
/********************/
// Set Up the Set. We start with an empty hash table.
void initSet(Set *set){
initHashTable(&set->table);
}
// Get the Number of Values in the Set.
int sizeSet(Set *set){
return set->table.size;
}
// Check if the Set is Empty. Returns 1 if it's empty or 0 if it has elements.
int isEmptySet(Set *set){
return isEmptyHashTable(&set->table);
}
// Check if a Value is in the Set. Returns 1 if it is or 0 if it's not.
int containsSet(Set *set, int value){
return containsHashTable(&set->table, value);
}
// Add a Value to the Set. Returns 1 if successful or 0 if the value was already in the set or there's no memory.
int addSet(Set *set, int value){
if(containsSet(set, value)){
return 0;
}
else{
return insertHashTable(&set->table, value, 0);
}
}
// Remove a Value from the Set. Returns 1 if successful or 0 if the value is not in the set.
int removeSet(Set *set, int value){
return deleteHashTable(&set->table, value);
}
// Copy the Values of the Set into an Array, sorted from the smallest to the greatest. Returns the number of values.
int toArraySet(Set *set, int *output){
int count = 0;
for(int i = 0; i < HASHTABLE_SIZE; i++){
for(HashNode* temp = set->table.buckets[i]; temp != NULL; temp = temp->next){
// Insertion sort: we move the greater values one position to the right.
int position = count;
while(position > 0 && output[position-1] > temp->key){
output[position] = output[position-1];
position--;
}
output[position] = temp->key;
count++;
}
}
return count;
}
// Build the Union of Two Sets (the values that are in a or in b). Returns 1 if successful or 0 if there's no memory.
int unionSet(Set *a, Set *b, Set *result){
initSet(result);
Set* sources[2] = {a, b};
for(int s = 0; s < 2; s++){
for(int i = 0; i < HASHTABLE_SIZE; i++){
for(HashNode* temp = sources[s]->table.buckets[i]; temp != NULL; temp = temp->next){
if(!containsSet(result, temp->key) && !addSet(result, temp->key)){
return 0;
}
}
}
}
return 1;
}
// Build the Intersection of Two Sets (the values that are in a and in b). Returns 1 if successful or 0 if there's no memory.
int intersectionSet(Set *a, Set *b, Set *result){
initSet(result);
for(int i = 0; i < HASHTABLE_SIZE; i++){
for(HashNode* temp = a->table.buckets[i]; temp != NULL; temp = temp->next){
if(containsSet(b, temp->key) && !addSet(result, temp->key)){
return 0;
}
}
}
return 1;
}
// Build the Difference of Two Sets (the values that are in a but not in b). Returns 1 if successful or 0 if there's no memory.
int differenceSet(Set *a, Set *b, Set *result){
initSet(result);
for(int i = 0; i < HASHTABLE_SIZE; i++){
for(HashNode* temp = a->table.buckets[i]; temp != NULL; temp = temp->next){
if(!containsSet(b, temp->key) && !addSet(result, temp->key)){
return 0;
}
}
}
return 1;
}
// Check if every Value of a is also in b. Returns 1 if a is a subset of b or 0 if it's not.
int isSubsetSet(Set *a, Set *b){
for(int i = 0; i < HASHTABLE_SIZE; i++){
for(HashNode* temp = a->table.buckets[i]; temp != NULL; temp = temp->next){
if(!containsSet(b, temp->key)){
return 0;
}
}
}
return 1;
}
// Print all Values of the Set. Displays them sorted from the smallest to the greatest: {1, 2, 3}
void printSet(Set *set){
int count = sizeSet(set);
int* values = (int*)malloc((count > 0 ? count : 1) * sizeof(int));
printf("{");
if(values){
toArraySet(set, values);
for(int i = 0; i < count; i++){
printf("%d", values[i]);
if(i < count-1){
printf(", ");
}
}
free(values);
}
printf("}\n");
}
// Free all the Memory of the Set and Reset It.
void freeSet(Set *set){
freeHashTable(&set->table);
}
#endif //SET_JL