#include <iostream>
#include <stdlib.h>
#include <time.h>

#define N 50
#define S 30
#define MAX 100

using namespace std;

struct node {
    int key;
    int value;
    struct node* next = NULL;
};

void generateHashTable(node * hashTable[]);

void removingHashTable(node * hashTable[] );

int getRandom();

int hash(int key);

void push(int key, node* hashTable[]);

node* search(int key, node* hashTable[]);

void pop(int key, node* hashTable[]);

void print(node* hashTable[]);

int main() {
    srand(time(NULL));

    node* hashTable[S] = { NULL };

    generateHashTable(hashTable);

    cout << "Before removing even elements:" << endl;

    print(hashTable);

    removingHashTable(hashTable);

    cout << "After removing even elements:" << endl;

    print(hashTable);

    return 0;
}

void removingHashTable(node * hashTable[] ) {

//     for (int i = 1; i <= MAX; i++) {
//      node* p = search(i, hashTable);
//      if (p != NULL && p->value == 0) {
//          pop(i, hashTable);
//      }
//  }

    for (int i = 0; i < S; i++) {

        node* hashNode = hashTable[i];
        node* next;

        while (hashNode != NULL) {
            next = hashNode->next;
            if (hashNode->value == 0) {
                pop(hashNode->key, hashTable);
            }
            hashNode = next;
        }
    }
}

void generateHashTable(node * hashTable[]) {

    for (int i = 0; i < N; i++) {
        int value = rand() % MAX + 1;

        push(value, hashTable);
    }
}


int hash_func(int key) {
    return key % S;
}

void push(int key, node* hashTable[]) {
    int hashNumber = hash_func(key);

    node* newHashNode = new node;

    newHashNode->key = key;

    newHashNode->value = key %2;

    newHashNode->next = NULL;

    node* hashNode = hashTable[hashNumber];

    if (hashNode == NULL) {
        hashTable[hashNumber] = newHashNode;
        return;
    } else {
        while (hashNode->next != NULL) {
            hashNode = hashNode->next;
        }

        hashNode->next = newHashNode;
    }
}

node* search(int key, node* hashTable[]) {
    int hashNumber = hash_func(key);

    node* hashNode = hashTable[hashNumber];

    while (hashNode != NULL) {
        if (hashNode->key == key) {
            return hashNode;
        }

        hashNode = hashNode->next;
    }
    return NULL;
}

void pop(int key, node* hashTable[]) {
    int hashNumber = hash_func(key);

    node* hashNode = hashTable[hashNumber];

    while (hashNode != NULL) {
        if (hashNode->key == key) {
            if (hashNode->next == NULL) {
                if (hashTable[hashNumber] == hashNode) {
                    hashTable[hashNumber] = NULL;
                    hashNode = NULL;
                } else {
                    node* tHashNode = hashTable[hashNumber];

                    while (tHashNode->next != hashNode) {
                        tHashNode = tHashNode->next;
                    }
                    (*tHashNode).next = NULL;
                }
                return;
            } else {
                *hashNode = *hashNode->next;
            }
            continue;
        }
        hashNode = hashNode->next;
    }
}

void print(node* hashTable[]) {
    bool isEmpty = true;
    bool emptyQuete = true;

    cout << endl << "##################################\n\t\tHash table" << endl;

    for (int i = 0; i < S; i++) {
        emptyQuete = true;

        node* hashNode = hashTable[i];


        cout << "in Hash table on index [" << i << "]: ";

        while (hashNode != NULL) {
            emptyQuete = false;

            isEmpty = false;

            cout << hashNode->key << " ";

            hashNode = hashNode->next;
        }

        if (emptyQuete) {
            cout << "--";
        }

        cout << endl;
    }

    if (isEmpty) {
        cout << "-Empty-" << endl;
    }

    cout << "##################################\n\t\tEND" << endl << endl;
}