2024 Project 2

Εκφώνηση: https://k08.chatzi.org/projects/project2/

Προσωπικά στοιχεία

Όνομα: Φοίβος Βλάχος

Α.Μ.: sdi201900313

Ασκήσεις που παραδίδονται

Συμπληρώστε [x] στις ασκήσεις (και τυχόν bonus) που παραδίδετε.

Documentation

Γενικές Πληροφορίες

Αυτό το έργο αφορά την υλοποίηση και δοκιμή γενικών βοηθητικών συναρτήσεων για το Abstract Data Type (ADT) Set. Οι υλοποιήσεις και οι δοκιμές καλύπτουν διάφορες δομές δεδομένων, όπως Binary Search Tree (BST) και BTree.

Περιγραφή των Αρχείων

modules/UsingADTSet/set_utils.c: Περιέχει τις γενικές υλοποιήσεις των βοηθητικών συναρτήσεων για το ADT Set.

Set set_from_vector(Vector vec, CompareFunc compare): Δημιουργεί και επιστρέφει ένα Set που περιέχει όλα τα στοιχεία του Vector vec, με διάταξη compare.
Vector set_to_vector(Set set): Δημιουργεί και επιστρέφει ένα Vector που περιέχει όλα τα στοιχεία του set με τη σειρά διάταξης.
void set_traverse(Set set, TraverseFunc f): Καλεί τη συνάρτηση f(set, value) σε κάθε στοιχείο του set με τη σειρά διάταξης.
Set set_merge(Set set1, Set set2, CompareFunc compare): Δημιουργεί και επιστρέφει ένα set που περιέχει τα στοιχεία και των δύο Sets set1, set2.
Pointer set_find_k_smallest(Set set, int k): Επιστρέφει την k-οστή τιμή του set με τη σειρά διάταξης.

tests/set_utils_test.c: Περιέχει δοκιμές για τις βοηθητικές συναρτήσεις που υλοποιούνται στο set_utils.c.

test_set_from_vector(void): Δοκιμάζει τη συνάρτηση set_from_vector.
test_set_to_vector(void): Δοκιμάζει τη συνάρτηση set_to_vector.
test_set_traverse(void): Δοκιμάζει τη συνάρτηση set_traverse.
test_set_merge(void): Δοκιμάζει τη συνάρτηση set_merge.
test_set_find_k_smallest(void): Δοκιμάζει τη συνάρτηση set_find_k_smallest.

Makefile: Περιέχει οδηγίες για την κατασκευή και εκτέλεση των δοκιμών.

make all: Κατασκευάζει όλα τα εκτελέσιμα αρχεία.
make run: Εκτελεί όλες τις δοκιμές.
make valgrind: Εκτελεί τις δοκιμές χρησιμοποιώντας το Valgrind για έλεγχο διαρροών μνήμης.
make clean: Καθαρίζει τα εκτελέσιμα αρχεία και τα αρχεία αντικειμένων.

Πολυπλοκότητα Λειτουργιών

set_from_vector: Ο(ν log ν), όπου ν είναι το μέγεθος του vector, λόγω της ανάγκης για ταξινόμηση των στοιχείων και εισαγωγής στο set.
set_to_vector: Ο(ν), όπου ν είναι το μέγεθος του set, καθώς κάθε στοιχείο επισκέπτεται και εισάγεται σε vector.
set_traverse: Ο(ν), όπου ν είναι το μέγεθος του set, καθώς κάθε στοιχείο επισκέπτεται μία φορά.
set_merge: Ο(ν1 + ν2), όπου ν1 και ν2 είναι τα μεγέθη των δύο sets, καθώς κάθε στοιχείο και από τα δύο sets πρέπει να επισκέπτεται και να εισάγεται στο νέο set.
set_find_k_smallest: Ο(log ν), όπου ν είναι το μέγεθος του set, καθώς απαιτεί αναζήτηση σε ισορροπημένο δέντρο.

Οδηγίες Εκτέλεσης

Κατασκευή Εκτελέσιμων Αρχείων
```
make all
make run 
make valgrind
make clean
```
Λεπτομέρειες Υλοποίησης

Η υλοποίηση των βοηθητικών συναρτήσεων του ADT Set έγινε με βάση την αρχή της αφαίρεσης, έτσι ώστε να είναι συμβατές με οποιαδήποτε υποκείμενη δομή δεδομένων του ADT Set. Οι βασικές δομές δεδομένων που χρησιμοποιήθηκαν είναι το Binary Search Tree (BST) και το BTree.

Υλοποίηση `set_from_vector`

Η συνάρτηση set_from_vector παίρνει ως είσοδο ένα Vector και δημιουργεί ένα Set με διάταξη σύμφωνα με τη συνάρτηση σύγκρισης compare. Τα βήματα περιλαμβάνουν:

Αντιγραφή των στοιχείων από το Vector σε ένα νέο Vector.
Ταξινόμηση του νέου Vector.
Δημιουργία ενός ισορροπημένου BST από τα ταξινομημένα στοιχεία.

Υλοποίηση `set_to_vector`

Η συνάρτηση set_to_vector μετατρέπει ένα Set σε Vector με τη σειρά διάταξης των στοιχείων. Χρησιμοποιεί μια ενδοδιαταγμένη διάσχιση (in-order traversal) για να εισάγει τα στοιχεία στο Vector.

Υλοποίηση `set_traverse`

Η συνάρτηση set_traverse επισκέπτεται κάθε στοιχείο του Set με τη σειρά διάταξης και καλεί μια συνάρτηση TraverseFunc σε κάθε στοιχείο.

Υλοποίηση `set_merge`

Η συνάρτηση set_merge συνδυάζει δύο Sets σε ένα νέο Set. Τα βήματα περιλαμβάνουν:

Μετατροπή των δύο Sets σε Vectors.
Συγχώνευση των δύο Vectors σε έναν νέο ταξινομημένο Vector.
Δημιουργία ενός νέου Set από τον ταξινομημένο Vector.

Υλοποίηση `set_find_k_smallest`

Η συνάρτηση set_find_k_smallest βρίσκει το k-οστό μικρότερο στοιχείο σε ένα Set χρησιμοποιώντας αναζήτηση σε ισορροπημένο δέντρο.

Οδηγίες Debugging με Χρήση του LLDB στη Δική μας Περίπτωση

Σε αυτό το έγγραφο, θα εξηγήσουμε πώς πραγματοποιήσαμε το debugging του προγράμματός μας χρησιμοποιώντας το εργαλείο LLDB. Ακολουθήσαμε συγκεκριμένα βήματα για να εντοπίσουμε και να διορθώσουμε τα σφάλματα στον κώδικά μας.

Βήματα για το Debugging με LLDB

Μεταγλώττιση του Κώδικα με Δυνατότητες Debugging:

Μεταγλωττίσαμε τον κώδικά μας με τις κατάλληλες σημαίες για debugging. Χρησιμοποιήσαμε την επιλογή -g για να συμπεριλάβουμε πληροφορίες debugging στο εκτελέσιμο αρχείο.

  gcc -g -o UsingADTSet_BTree_set_utils_test UsingADTSet_BTree_set_utils_test.c

Εκκίνηση του LLDB με το Εκτελέσιμο Αρχείο:

Ξεκινήσαμε το LLDB με το εκτελέσιμο αρχείο μας.

  lldb ./UsingADTSet_BTree_set_utils_test

Ορισμός Σημείου Διακοπής στην Κύρια Συνάρτηση:

Ορίσαμε σημείο διακοπής στην κύρια συνάρτηση για να μπορέσουμε να ελέγξουμε την εκτέλεση από την αρχή.

  (lldb) breakpoint set --name main

Εκτέλεση του Προγράμματος:

Ξεκινήσαμε την εκτέλεση του προγράμματος μέσα στο LLDB.

  (lldb) run

Εντοπισμός Σφάλματος Assertion Failed:

Όταν το πρόγραμμα σταμάτησε λόγω ενός assertion failed, το LLDB μας έδειξε τη γραμμή όπου συνέβη το σφάλμα. Συγκεκριμένα, το σφάλμα βρισκόταν στη συνάρτηση vector_set_at.

  (lldb) print vec->size
  (lldb) print pos

Εξέταση της Κατάστασης του Προγράμματος:

Κατά την εξέταση των τιμών των μεταβλητών vec->size και pos, διαπιστώσαμε ότι η μεταβλητή vec->size ήταν μηδενική ενώ προσπαθούσαμε να τοποθετήσουμε στοιχεία σε συγκεκριμένες θέσεις του διανύσματος.

Διόρθωση του Κώδικα:

Αναγνωρίσαμε ότι το πρόβλημα προερχόταν από τη χρήση της vector_set_at αντί για την vector_insert_last. Διορθώσαμε τον κώδικα στη συνάρτηση set_to_vector.

  Vector vec = vector_create(0, NULL); // αντί για vector_create(set_size(set), NULL);
  for (SetNode node = set_first(set); node != SET_EOF; node = set_next(set, node)) {
  vector_insert_last(vec, set_node_value(set, node)); // αντί για vector_set_at(vec, i++, set_node_value(set, node));
  }

Επαναμεταγλώττιση και Επανεκκίνηση των Δοκιμών:

Μετά τις διορθώσεις, επαναμεταγλωττίσαμε τον κώδικα και εκτελέσαμε ξανά τις δοκιμές.

  make run

Αποτέλεσμα

Μετά τις διορθώσεις, όλες οι δοκιμές ολοκληρώθηκαν με επιτυχία, και το πρόγραμμά μας εκτελέστηκε χωρίς σφάλματα.

Συμπεράσματα

Η χρήση του LLDB μας βοήθησε να εντοπίσουμε και να διορθώσουμε τα σφάλματα στον κώδικά μας με αποτελεσματικό τρόπο. Ακολουθώντας τα παραπάνω βήματα, μπορείτε να χρησιμοποιήσετε το LLDB για να κάνετε debugging στα προγράμματά σας και να βελτιώσετε την ποιότητά τους.

kdalampekis/2024_project_2_foivosv21_master