#include <iostream>
#include <cstring>

using namespace std;

struct elt {
    int key; // to hold a unique key for each element
    int data;  // the data for each element
    elt * next; // next element in the bucket list
};

typedef elt * Eltp; // elt pointer


class HashTableOne {
    int size= 0;
    Eltp * table; // array of buckets
    
    int hash(int k){ // hash function, k= key value
        int i;
        for (i= 0; k; i += k++);
        return i % size;
    }
    
public:
    HashTableOne(int n); // constructor, n= size of hash table array    
    void add(int k, int d); // function adds element to hash table, k= key value, d= data to be added (an int)
    int find(int k); // function that returns data (an int) for "k" key value input (returns -1 if no key exists)
    void print(); // function that prints the contents of the hash table
};


    
// HashTable3 class declaration:
class HashTable3 {
    HashTableOne_p * table; // array of pointers to buckets
public:
    HashTable3(int n1, int n2); // constructor, n1= size of main hash table, n2= size for bucket hash tables
    void add(int k, int d); // adds element, k= key, d= data (an int)
    int find(int key); // returns d (data) associated with key (returns -1 if key does not exist)
    void print(); // prints contents of hash table, printing bucket hash tables
};


// HashTableOne constructor:
HashTableOne::HashTableOne(int n) {
        size = n;
        table = new Eltp [size];
        for(int i=0; i < size; i++){
            table[i] = NULL;
        }
    }
    
    
// HashTableOne add function:
void HashTableOne::add(int k, int d) {
        int index = hash(k);
        if(table[index] == NULL){
            table[index] = new elt;
            table[index]->data = d;
            table[index]->key = k;
            table[index]->next = NULL;
        } else{
            // search for the key, if found update the data
            elt * p = table[index];
            while(p != NULL) {
                if(p->key == k){ // found one
                    p->data = d;
                    return;
                }
                p = p->next;
            }// end while
            
            // did not find it in the bucket
            p = table[index];
            table[index] = new elt;
            table[index]->data = d;
            table[index]->key = k;
            table[index]->next = p;
        }
    }
    
// HashTableOne find function:
int HashTableOne::find(int k) {
        int index = hash(k);
        elt * p = table[index];
        while(p != NULL) {
            if(p->key == k){ // found one
                return p;
            }
            p = p->next;
        }// end while
            
        // did not find it 
        return -1;
    }
    
    

// HashTable3 constructor:
HashTable3::HashTable3(int n1, int n2) {
    typedef HashTableOne * HashTableOne_p; // a pointer to HashTableOne class
    
    table= new HashTableOne_p[n1];
    for (int i= 0; i < n1; i++){
        table[i]= new HashTableOne(n2);
    }
    
}

// HashTable3 add function:
void HashTable3::add(int k, int d) {
        int index = hash(k);
        if(table[index] == NULL){
            table[index] = new elt;
            table[index]->data = d;
            table[index]->key = k;
            table[index]->next = NULL;
        } else{
            // search for the key, if found update the data
            elt * p = table[index];
            while(p != NULL) {
                if(p->key == k){ // found one
                    p->data = d;
                    return;
                }
                p = p->next;
            }// end while
            
            // did not find it in the bucket
            p = table[index];
            table[index] = new elt;
            table[index]->data = d;
            table[index]->key = k;
            table[index]->next = p;
        }
    }
    
// HashTable3 find function:
int HashTable3::find(int k) {
        int index = hash(k);
        elt * p = table[index];
        while(p != NULL) {
            if(p->key == k){ // found one
                return p;
            }
            p = p->next;
        }// end while
            
        // did not find it 
        return -1;
    }



int main() {
    
    // test cases go here
    
    HashTable3 H1(3, 2); // New hash table with 3 elements in main hash table and 2 bucket hash tables, populate with add() method randomly
                         // Print the contents of the table after each operation using print()
                         
    H1.find("key"); // finds an element with "key" value and returns data value (or -1 if key does not exist)
    
    
    return 0;
}