#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 <= MAX; i++) {

        node* hashNode = search(i, hashTable);

        if (hashNode != NULL) {
            if (hashNode->value == 0) {

                //cout<< " Key = " << hashNode->key << endl;
                //cout<< " Value =  "<< hashNode->value << endl << endl;

                pop(hashNode->key, hashTable);

            }
        }
    }
}

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;
}