Εργασία 2

Last updated on Mar 4, 2024

Ανακοινώθηκε: 7/5/2023
Προθεσμία παράδοσης: ~~28/5/2023~~ 31/5/2023 23:59
16% του συνολικού βαθμού στο μάθημα
Link εγγραφής: https://classroom.github.com/a/lDihUSgA
Repository: https://github.com/chatziko-k08/2023-project-2-<github-username>

Σημαντικό: διαβάστε τις οδηγίες (κοινές για όλες τις εργασίες). Περιέχουν μεταξύ άλλων και πληροφορίες για τη χρήση του git, η οποία είναι ολόιδια με τα εργαστήρια.

Άσκηση 1 (20%)

Τα δυαδικά δέντρα μπορούν να οριστούν με “αναδρομικό” τρόπο, ως εξής: ένα δέντρο είναι

είτε κενό
είτε περιέχει ένα στοιχείο ως ρίζα, και δύο (υπο)δέντρα (αριστερό και δεξί)

Στο repository της εργασίας υπάρχει ένα module ADTRecTree.h που περιγράφει ένα τέτοιο αφηρημένο δέντρο. Ας σημειωθεί ότι:

Δεν υπάρχει έννοια του “κόμβου”, κάθε δέντρο περιέχει άλλα δέντρα (όχι κόμβους).
Κάθε δέντρο είναι immutable, από τη στιγμή που δημιουργηθεί δεν μπορεί να τροποποιηθεί (ούτε η τιμή του ούτε τα υποδέντρα). Αν θέλουμε να αλλάξουμε κάτι πρέπει να δημιουργήσουμε νέο δέντρο και να καταστρέψουμε το παλιό.
(Τέτοιου είδους τύποι χρησιμοποιούνται συχνά για λόγους βελτιστοποίησης, ώστε δύο ίδια immutable αντικείμενα να μοιράζονται την ίδια μνήμη.)
Καταστρέφοντας ένα δέντρο δεν καταστρέφονται αυτόματα τα υποδέντρα του.

Στο αρχείο modules/UsingLinkedTree/ADTRecTree.c υπάρχει ένα προσχέδιο μιας υλοποίησης του ADTRecTree χρησιμοποιώντας “συνδεδεμένα” δέντρα με pointers (η συνιθισμένη υλοποίηση ενός δέντρου, όπως κάνουμε με τις λίστες). Υλοποιήστε όλες τις συναρτήσεις, η πολυπλοκότητα των οποίων θα πρέπει να είναι $O(1)$.

Στη συνέχεια υλοποιήστε ένα test tests/ADTRecTree.c το οποίο θα πρέπει να ελέγχει όλες τις λειτουργίες του ADTRecTree. Δεν χρειάζεται τεράστιος αριθμός από tests, αλλά φροντίστε να καλύπτονται τα βασικά “edge cases” (κενά δέντρα, κλπ). Προσαρμόστε το Makefile ώστε να δημιουργεί ένα εκτελέσιμο tests/UsingLinkedTree_ADTRecTree_test το οποίο να κάνει link το test με την υλοποίηση που δημιουργήσατε, η οποία θα πρέπει να περνάει όλα τα tests χωρίς leaks.

Άσκηση 2 (20%)

Στην άσκηση αυτή καλούμαστε να φτιάξουμε μια εναλλακτική υλοποίηση του ADTRecTree η οποία θα χρησιμοποιεί τον ADTMap χωρίς να δεσμεύει καθόλου απ'ευθείας μνήμη (απαγορεύεται οποιαδήποτε κλήση στη malloc). Αυτό μπορεί να γίνει ως εξής: ο τύπος RecTree (που είναι pointer σε struct rec_tree) θα είναι μεν pointer, αλλά δε θα δείχνει σε κάποια δεσμευμένη μνήμη, απλά κάθε τιμή του θα αντιπροσωπεύει ένα δέντρο. Η τιμή 0 θα είναι πάντα το κενό δέντρο REC_TREE_EMPTY ενώ κάθε κλήση της rectree_create θα επιστρέφει και μια νέα σειριακή τιμή, 1, 2, 3, κλπ, οι οποίες θα αντιπροσωπεύουν τα διαφορετικά δέντρα. Το 1 εδώ είναι η τιμή του pointer, αλλά δεν αντιστοιχεί σε δεσμευμένη μνήμη (δε θα κάνουμε ποτέ dereference), απλά αναπαριστά το δέντρο που δημιουργήθηκε.

Η αντιστοίχηση κάθε δέντρου στην τιμή και τα υποδέντρα του θα γίνεται μέσω κατάλληλων maps. Πχ μια αντιστοίχηση 4 => 6 μπορεί να υποδηλώνει ότι το δέντρο 6 είναι αριστερό παιδί του δέντρου 4. Τα maps είναι κοινά για όλα τα δέντρα (δεν δημιουργείται νέο map για κάθε δέντρο), θα δημιουργούνται την πρώτη φορά που θα κληθεί η rectree_create και θα αποθηκεύονται σε global μεταβλητές. Για να μην υπάρχουν memory leaks θα πρέπει όταν καταστραφούν όλα τα δέντρα που έχουν δημιουργηθεί να καταστρέφονται και τα maps.

Δημιουργήστε την υλοποίηση αυτή στο αρχείο modules/UsingADTMap/ADTRecTree.c, και τροποποιήστε το tests/Makefile ώστε να δημιουργείται ένα εκτελέσιμο tests/UsingADTMap_ADTRecTree_test το οποίο να κάνει link με το test που υλοποιήσατε στην Άσκηση 1 με τη νέα υλοποίηση. Για τη δημιουργία του εκτελέσιμου θα χρειαστείτε φυσικά και μια υλοποίηση του ADTMap, μπορείτε να χρησιμοποιήσετε όποια θέλετε από το lecture-code. Το test θα πρέπει να είναι κοινό για τις δύο υλοποιήσεις, χωρίς αλλαγές, και θα πρέπει να περνάει χωρίς leaks.

Τέλος στο README.md αναφέρετε την πολυπλοκότητα κάθε λειτουργίας, η οποία εξαρτάται από την υλοποίηση του ADTMap που χρησιμοποιήσατε, και συγκρίνετέ την με αυτήν της υλοποίησης της Άσκησης 1.

Άσκηση 3 (20%)

Δημιουργήστε ένα module ADTRecTree_utils.c με τις παρακάτω λειτουργίες:

// Επιστρέφει το υποδέντρο του tree στη θέση pos. Η αρίθμηση των θέσεων ξεκινάει
// από το 0 (ρίζα) και κινείται κατά επίπεδα, τα παιδιά της ρίζας έχουν θέση 1
// και 2, τα δικά τους παιδιά έχουν θέσεις 3,4,5,6, κλπ. Αν το υποδέντρο δεν
// υπάρχει θα επιστρέφεται REC_TREE_EMPTY. 

RecTree rectree_get_subtree(RecTree tree, int pos);

// Δημιουργεί και επιστρέφει ένα νέο δέντρο, το οποίο προκύπτει αντικαθιστώντας
// το υποδέντρο του tree στη θέση pos με το subtree που δίνεται.  Η θέση pos
// πρέπει να αντιστοιχεί είτε σε υπάρχον κόμβο (που αντικαθίσταται), είτε στο
// κενό παιδί ενός υπάρχοντος κόμβου (οπότε προστίθεται εκεί το subtree).  Αν το
// subtree τοποθετείται στη ρίζα (pos == 0) τότε επιστρέφεται το ίδιο το subtree.
//
// Η συνάρτηση καταστρέφει αυτόματα τόσο το παλιό υποδέντρο που αντικαθίσταται
// (αν υπάρχει), καθώς και όλους τους προγόνους του που μεταβάλλονται (οπότε
// ξαναδημιουργούνται).

RecTree rectree_replace_subtree(RecTree tree, int pos, RecTree subtree);

Προσοχή, στη συνάρτηση rectree_replace_subtree διαγράφονται μόνο τα δέντρα στο μονοπάτι προς τη ρίζα (το πολύ h σε αριθμό), όχι τα υποδέντρα τους. Πχ αν καλέσουμε rectree_replace_subtree(tree, 2) στο παρακάτω δέντρο:

       0
    /      \
   1         2
 /   \     /   \
3     4   5     6

θα διαγραφούν μόνο τα 2 και 0, και θα πάρουμε το παρακάτω δέντρο:

      new 0
    /      \
   1      subtree
 /   \     
3     4

Δηλαδή:

Διαγράφηκε το 2 (μπήκε στη θέση του το subtree).
Διαγράφηκε η παλιά ρίζα (μπήκε στη θέση της νέα ρίζα με την ίδια τιμή 0 και παιδί το subtree).
Το παλιό 1 δεν άλλαξε καθόλου, απλά μπήκε παιδί της νέας ρίζας.
Τα παλιά 5,6 δεν άλλαξαν καθόλου (είναι ευθύνη του χρήστη είτε να τα έχει βάλει μέσα στο subtree, ή να τα διαγράψει).

Οι αλγόριθμοι θα πρέπει να είναι αποδοτικοί (λύσεις $O(n)$ δεν γίνονται δεκτές).

Επίσης δημιουργήστε ένα test tests/ADTRecTree_utils_test που να δοκιμάζει τις λειτουργίες αυτές, ελέγχοντας όλα τα edge cases. Τροποποιήστε το tests/Makefile ώστε να παράγει δύο εκτελέσιμα προγράμματα, κάνοντας link το παραπάνω test με τις δύο υλοποιήσεις του ADTRecTree που δημιουργήσατε. Όλα τα tests θα πρέπει να παρνάνε χωρίς leaks.

Τέλος στο README.md αναφέρετε την πολυπλοκότητα κάθε λειτουργίας.

Άσκηση 4 (20%)

Δημιουργήστε ένα module ADTCompTree.h το οποίο να περιγράφει ένα αφηρημένο complete αναδρομικό δέντρο. Οι λειτουργίες θα είναι οι ίδιες με αυτές του ADTRecTree, αλλάζοντας βέβαια τον τύπο που περιγράφει το δέντρο σε CompTree, και το prefix των συναρτήσεων σε comptree_.

Επίσης το module θα περιλαμβάνει και τις παρακάτω λειτουργίες:

// Δημιουργεί και επιστρέφει ένα νέο δέντρο που προκύπτει από το tree μετά την προσθήκη της
// τιμής value στο "τέλος" του δέντρου (ώστε να παραμείνει complete). Τυχόν υποδέντρα που
// "μεταβάλλονται" κατά την προσθήκη αυτή καταστρέφονται αυτόματα.

CompTree comptree_insert_last(CompTree tree, Pointer value);

// Δημιουργεί και επιστρέφει ένα νέο δέντρο που προκύπτει από το tree μετά την διαγραφή του
// "τελευταίου" υποδέντρου του (ώστε να παραμείνει complete). Το υποδέντρο που αφαιρείται, και
// τυχόν υποδέντρα που "μεταβάλλονται" κατά τη διαγραφή αυτή καταστρέφονται αυτόματα.

CompTree comptree_remove_last(CompTree tree);

Στη συνέχεια δημιουργήστε μια υλοποίηση modules/UsingADTRecTree/ADTCompTree.c του παραπάνω module, χρησιμοποιώντας εσωτερικά τον ADTRecTree. Δημιουργήστε επίσης ένα test tests/ADTCompTree_test.c για το module αυτό (για τις βασικές λειτουργίες μπορείτε φυσικά να επαναχρησιμοποιήσετε τον κώδικα του ADTRecTree_test.c). Το Makefile πρέπει να δημιουργεί δύο εκτελέσιμα, κάνοντας link με τις δύο υλοποιήσεις του ADTRecTree.

Οι συναρτήσεις rectree_get_subtree και rectree_replace_subtree της άσκησης 3 θα σας χρησιμεύσουν στην υλοποίηση, και μπορείτε επίσης να προσθέσετε και αντίστοιχες συναρτήσεις comptree_get_subtree και comptree_replace_subtree, για να τις χρησιμοποιήσετε στην άσκηση 5.

Τέλος στο README.md αναφέρετε την πολυπλοκότητα κάθε λειτουργίας.

Άσκηση 5 (20%)

Δημιουργήστε μια υλοποίηση modules/UsingADTCompTree/ADTPriorityQueue.c του ADTPriorityQueue χρησιμοποιώντας το ADTCompTree για την αναπαράσταση του σωρού. Μπορείτε να χρησιμοποιήσετε τον κώδικα του modules/UsingHeap/ADTPriorityQueue.c σαν βάση, αλλάζοντάς τον κατάλληλα ώστε όλα τα δεδομένα να αποθηκεύονται σε ένα CompTree. Η υλοποίηση της pqueue_create με αρχικά δεδομένα θα πρέπει να χρησιμοποιεί τον γρήγορο $O(n)$ αλγόριθμο που είδαμε στο μάθημα (και όχι τον naive_heapify).

Στη συνέχεια τροποποιήστε το tests/Makefile ώστε να κάνει link το ήδη υπάρχον tests/ADTPriorityQueue_test.c με τη νέα υλοποίηση, δημιουργώντας δύο εκτελέσιμα, ένα για κάθε υλοποίηση του ADTRecTree. Τα tests θα πρέπει να περνάνε χωρίς leaks.

Bonus (5%):

Τροποποιήστε την υλοποίηση του ADTSet μέσω Binary Search Trees από το lecture-code, ώστε να χρησιμοποιεί εσωτερικά το ADTRecTree. Η υλοποίηση θα πρέπει να περνάει το αντίστοιχο test χωρίς leaks.

Bonus (10%):

Τροποποιήστε την υλοποίηση του ADTSet μέσω AVL από το lecture-code, ώστε να χρησιμοποιεί εσωτερικά το ADTRecTree. Η υλοποίηση θα πρέπει να περνάει το αντίστοιχο test χωρίς leaks.