1η ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΗ ΕΡΓΑΣΙΑ 
ΛΕΙΤΟΥΡΓΙΚΑ

Παρακάτω θα γίνει η επεξήγηση της υλοποίησης μου.
Τα αρχεία που περιλαμβάνονται είναι τα εξής:
global.h
hash_table.c
hash_table.h
inverted_list.c
inverted_list.h
Makefile
mvote.c
parsing.c
voter.h

Οδηγίες για την μεταγλώττιση και οδηγίες για την εκτέλεση του προγράμματος:

make

./mvote -f filename -b x -ib y

(ώπου x,y θετικός ακέραιος αριθμός)
(τα flags μπορούν να αλλάξουν θέση πχ πρώτα το -b δεύτερο το -f κλπ)
(το flag -ib είναι δική μου προσθήκη και απευθύνεται στα buckets που θα γίνει αρχικά initialize το hashing table)

Υπόλοιπες λειτουργίες του προγράμματος:

1. l <pin>
προσπέλασε το πίνακα κατακερματισμού για την εκλέκτορα με PIN: <pin>. Εάν η εκλέκτορας βρεθεί, οι
πληροφορίες της εγγραφής παρέχονται στο tty. Διαφορετικά μια ένδειξη λάθους παρέχεται.
2. i <pin> <lname> <fname> <zip>
εισήγαγε τις σχετικές πληροφορίες για ένα συγκεκριμένο εκλέκτορα του οποίου το ID είναι <pin>, το
επίθετο και όνομα του είναι <lname> και <fname> και ο Τ.Κ. της μόνιμης διαμονής του είναι <zip>.
3
 ́Οσοι εκλέκτορες εγγράφονται στην ψηφοφορία έχουν αρχικά την ψηφοφορίας σαν “N”. Εάν το <pin>
ήδη υπάρχει στο πίνακα κατακερματισμού, η εντολή εισαγωγής ακυρώνεται και ένα σχετικό μήνυμα λάθους
τυπώνεται.
3. m <pin>
σημείωσε ότι η συμμετέχουσα με ID <pin> έχει ήδη ψηφίσει και θέσε την τιμή της κατάστασης της σε
“Y”. Αν η κατάσταση στην εν λόγω εγγραφή είναι ήδη “Y”, δεν χρειάζεται να γίνει κάτι παραπάνω και
ένα σχετικό μήνυμα εμφανίζεται στην έξοδο.
4. bv <fileofkeys>
για οσους εκλέκτορες τα κλειδιά των οποίων εμφανίζονται στο αρχείο <fileofkeys> θέσε την κατάσταση
ψηφοφορίας τους σε “Y”. Για κάθε επιχειρούμενη αλλαγή κατάστασης ψηφοφορίας, η ίδια συμπεριφορά
με την εντολή ‘m <pin>’ πρέπει να ακολουθηθεί.
5. v
δώσε τον αριθμό εκλεκτόρων που έχουν ψηφίσει μέχρι στιγμής.
6. perc
παρουσίασε το ποσοστό εκλεκτόρων που έχουν ήδη ψηφίσει σε σχέση με τον αριθμό όλων των εκλεκτόρων.
7. z <zipcode>
παρουσίασε τον αριθμό των συμμετεχόντων στη ψηφοφορία στο Τ.Κ. <zipcode> και τύπωσε τα PINs
τους.
8. o
παρουσίασε όλους τους Τ.Κ. για τους οποίους υπάρχουν ήδη συμμετέχοντες στην ψηφοφορία. Η εν λόγω
έξοδος θα πρέπει να είναι ταξινομημένη σε φθίνουσα σειρά σε σχέση με τον αριθμό των ψηφοφόρων ανά
Τ.Κ. Κάθε γραμμή στην έξοδο αποτελείται από ένα Τ.Κ. και των αριθμό εκλεκτόρων που η κατάσταση
ψηφοφορίας τους είναι “Y”.
9. exit: Το πρόγραμμα τερματίζει αφού αποδεσμεύσει τη μνήμη που δέσμευσε για τη λειτουργία του.

Το πρόγραμμα ξεκινάει κάνοντας parsing τα δεδομένα του χρήστη με την χρήση της συνάρτησης parsing που βρίσκεται στο file parsing.c.
Η συνάρτηση επεξεργάζεται τα δεδομένα του χρήστη και ανάλογα τα flags κάνει τις κατάλληλες αρχικοποιήσεις,filename , bucket entries
και ακόμα αρχικοποιεί την global μεταβλήτη (στο file global.h έχω όλες τις global μεταβλητές) initial_bucket_size,αν κάποιο flag λειπει η δωθεί λαθος input 
ένα μήνυμα λάθους εμφανίζεται και το πρόγραμμα τερματίζει.
Αρχικά το Linear hashing table ,έχει την εξής δομή.
Στο voter.h έιναι η δομή του κάθε voter ,έχοντας ένα όνομα ένα επίθετο ένα PIN,ΤΚ και αν ψήφισε η όχι.
Στο αρχείο hash_table.h βρίσκεται η δομή του Linear hashing table ,το οποίο είναι ένας μονοδιάστατος πίνακας όπου σε κάθε κελί του υπάρχει μια linked list που το κάθε node της έχει έναν array μεγέθους
bucket entries και κάθε κελί του array είναι κελί ενός bucket.Το κάθε κελί περιέχει ενα PIN και έναν pointer σε voter,ενώ το κάθε bucket έχει έναν pointer σε νέο bucket(αυτό για τα overflow buckets).
Το linear hashing table γίνεται initialized με την συνάρτηση initialization που βρίσκεται στο αρχείο hash_table.c
Στην συνέχεια καλείται η συνάρτηση fill_hashing_table για να γίνουν insert όλοι οι voters απο το αρχείο filename στο linear hashing table.
Η συνάρτηση fill_hashing_table που βρίσκεται στο αρχείο hash_table.c αρχικοποιεί για αρχή όλες τις global μεταβλητές που θα χρειαστούν για το hashing,όπως τις συναρτήσεις h0,h1 (που υπολογιζονται με την συνάρτηση h_right_factor)
όπως και την μεταβλητή current_buckets_number η οποία δείχνει το πόσα buckets έχει το hashing table.Η συνάρτηση διαβάζει έναν έναν τους voters από το file και για καθέναν από αυτους καλεί την συνάρτηση hash_table_insert η οποία βρίσκεται
στο ίδιο αρχείο (hash_table.c).Το πρώτο πράγμα που γίνεται στην συνάρτηση είναι να ελέγξει αν ο voter βρίσκεται ήδη στον πίνακα με την συνάρτηση search_by_PIN που χρησιμοποιείται και για τις λειτουργίες της mvote.
Για αρχή χρησιμοποιείται η συνάρτηση h0 για να βρεθεί το hashed key,αν αυτό είναι μικρότερο απο το p τότε χρησιμοποιείται η συνάρτηση h1.Η συνάρτηση χωρίζει το key insertion στις εξής περιπτώσεις:
1η:Στο bucket που είναι να προσθεθεί το key δεν υπάρχει overflow bucket
    1η:Υπάρχει άδειος χώρος σε αυτό το bucket επομένως γίνεται το insertion
    2η:το bucket είναι γεμάτο επομένως πρέπει να δημιουργηθεί ένα νέο overflow bucket με την χρήση της συνάρτησης create_overflow_bucket η οποία κάνει init ένα νεο bucket το οποίο θα είναι κενό.Ο voter μπαίνει στην αρχή αυτού,
        και το προηγούμενο bucket συνδέεται με το bucket αυτό.
2η:Υπάρχει overflow οπότε πάω στο τελευταίο overflow bucket
    1η:Υπάρχει άδειος χώρος σε αυτό το overflow bucket επομένως βάζω το key εκεί
    2η:Δέν υπάρχει χώρος στο overflow bucket επομένως δημιουργώ καινούριο και βάζω τον voter στην αρχή του
Κάποια issues που αντιμετώπιζα και διόρθωσα με τον εξής τρόπο:
1.Κάποιες φορές ενώ είχα κενή θεση στο αρχικό bucket ο voter δέν έμπαινε εκεί και δημουργούσα χωρίς λόγο overflow bucket,διορθώθηκε με την πρόσθεση του LinearHashingArray[bucket_position]->data[bucketentries - 1].PIN != -1
και την προσθήκη του else που βάζω τον voter στον άδειο χώρο και αποτρέπω στο να δημουργηθεί νεο bucket
Έπειτα αφου γίνει το Insertion του voter τεστάρω αν το l>0.75 ,υπολογίζοντας το l με τις συναρτήσεις number of keys και key capacity non overflow που κάνουν το προφανές
Aν το l είναι μεγαλυτερο του 0.75 δημιουργείται νέο bucket δυναμικά και δεσμεύεται χώρος για αυτο και καλείται η συνάρτηση rehash για να γίνει split το συγκεκριμένο bucket που ο pointer p δείχνει(μετά το split αυξάνεται ο pointer και ο αριθμος των buckets)
Ενω αν το l<0.75 απλά επιστρέφεται το table.
Η συνάρτηση rehash κάνει τα εξής.
Για αρχή πηγαίνει στο τελευταίο bucket (στο κελι του array που τα buckets πρεπει να γινουν split) και ανάλογα την περίπτωση κάνει τα απαραίτητα.
Εάν ένα κελί ενος bucket είναι γεμάτο με έναν voter τότε,βρίσκεται το νέο hashed key του key και οι περιπτώσεις είναι οι εξής
1η To hashed key είναι ίσο με τον pointer επομένως ο voter δέν πρέπει να μετακινηθεί,σε αυτην την περίπτωση για αρχή αυξάνεται ο counter voters_not_to_move


2η Το hashed key είναι διαφορετικό απο τον pointer
    1η Στην θέση του table που δείχνει το hashed key έχω άδεια θέση επομένως βαάζω το key στο bucket αυτό
    2η ο bucket είναι γεμάτος
        1η δέν εχω overflow bucket οπότε δημιουργώ εναν νέο και βάζω τον voter εκεί
        2η έχω ήδη overflow bucket,πηγαίνω στον τελευταίο ,έχει άδειο χώρο οπότε βάζω το key εκεί
        3η ο overflow bucket είναι και αυτος γεμάτος επομένως δημιουργώ νέο overflow bucket και βάζω τον voter στην αρχή αυτου του bucket
    

Στην συνέχεια αφου τελείωσε το rehash ,υπάρχει η περίπτωση να έχω αφαιρέση απο έναν bucket έναν voter στην αρχή του και να υπάρχουν voters στα μέσα του bucket,επομένως γίνονται rearange ώστε να μην υπάρχουν κενα
Εάν όλοι οι voters άλλαξαν bucket position και κανένα δεν έμεινε στο ίδιο Bucket τότε επιστρέφω το table,αλλιώς δημιουργείται ένας array με voters ,οι οποιοι voters είναι όσοι δεν εχουν μετακινηθεί,οι voters μπαίνουν στο array και διαγραφονται απο τα buckets τους και τέλος γίνεται ένα rearange αυτών ώστε να μην υπάρχουν διασπαρτοι σε άσκοπα overflow buckets.


Έπειτα έχει δημιουργηθεί το inverted list του οποίου η δομή είναι η εξης.Βρισκεται στο αρχείο inverted_list.h και είναι μια linked list και κάθε node της έχει έναν ΤΚ και έναν pointer σε λίστα από pointers σε voters που έχουν τον ίδιο ΤΚ.
Η λίστα αυτή αρχικοποιείται με την συνάρτηση init_inverted_list η οποία βρίσκεται στο αρχείο inverted_list.c.Μέχρι να δωθεί η εντολή exit καλείται η συνάρτηση mvote,η οποία κάνει parsing για αρχή και διαβάζει τα δεδομένα από τον δημοσκόπο
και ανάλογα την είσοδο κάνει τα εξής.

1.l PIN,με την βοήθεια της συνάρτησης search by PIN που προαναφέρθηκε γίνεται search για να βρεθεί voters στο hash table με το συγκεκριμένο PIN,γίνεται μια προσπέλαση σε όλα τα κελιά του πίνακα και σε όλα τα buckets για να βρεθεί το PIN

    άν δεν βρεθεί ή το input είναι λάθος γίνονται τα ανάλογα print,αλλιώς εκτυπώνεται ο voter
2.m PIN ,με την βοήθεια της συνάρτησης set_to_voted γίνεται μια προσπέλαση του πίνακα ,αν βρεθεί το PIN και δεν εχει ψηφίσει ο voter ,θέτεται η τιμή οτι ψήφισε
    τα αντίστοιχα μηνύματα εκτυπώνονται αν βρεθει,δεν βρεθεί η βρεθεί και ψήφισε
3.i surname name TK,δίνονται τα παρακάτω στοιχεία και με την βοήθεια της συνάρτησης hash_table_insert η οποία εχει προαναφερθεί εισάγεται ο αντίστοιχος voter
    τα αντίστοιχα μηνύματα εκτυπώνονται
4.bv filename,δίνεται ένα αρχείο με PIN και γίνεται η ίδια διαδικασία με το m PIN απλά για όλα τα Pins του αρχείου
    τα αντίστοιχα μηνύματα εκτυώνονται
5.v,με την βοήθεια της συνάρτησης total_votes ,η οποία κάνει προσπέλαση την inverted list επιστρέφει τον συνολικό αριθμό των voters
6.o,με τη βοήθεια της συνάρτησης print_by_TK εκτυπώνονται για όσους voters έχουν ψηφίσει οι TK ταξινομημένοι σε φθίνουσα σειρά (για κάθε ΤΚ υπάρχει ένας array με counters που αναλογεί στο πόσοι εχουν ψηφίσει απο αυτον τον ΤΚ και στο τέλος 
    γίνεται ταξινόμηση σε φθίνουσα σειρά και εκτυπώνονται τα αντίστοιχα ΤΚ
7.perc,καλόντας τις συναρτήσεις total votes και number of keys που έχω ήδη αναφερθεί υπολογίζεται το ποσοστό των voters που έχουν ψηφίσει
8.z TK,με την συνάρτηση print_by_TK εκτυπώνεται ο αριθμός των φηφοφόρων με συγκεκριμένο ΤΚ και ακόμα εκτυπώνονται όλα τα PIN τους
9.exit, η εντολή exit κάνει free όλες τις δομές και το πρόγραμμα τερματίζει
Το complexity για Linear hashing table insertion είναι O(n*buckeentries)
Το worst case complexity για αναζήτηση στο table είναι
O(current_bucket_number * buckeentries)
Ενώ απο την άλλη για το insertion στο inverted list
Ο(n) complexity
Ενω για την αναζήτηση 
O(n*k),n τα nodes της λίστας και k average voters,με μικρο n και k έχω linear complexity