#include <iostream>
using namespace std;

class LinearProbingHashTable {
private:
    int* table;
    int tableSize;
    int count;
    const int EMPTY = -1;

    int hashFunction(int key) {
        return key % tableSize;
    }

public:
    LinearProbingHashTable(int size) {
        tableSize = size;
        count = 0;
        table = new int[tableSize];

        for (int i = 0; i < tableSize; i++) {
            table[i] = EMPTY;
        }
    }

    ~LinearProbingHashTable() {
        delete[] table;
    }

    bool isFull() {
        return count == tableSize;
    }

    bool insert(int key) {
        if (isFull()) {
            return false;
        }

        int h = hashFunction(key);

        while (table[h] != EMPTY) {
            h = (h + 1) % tableSize;
        }

        table[h] = key;
        count++;
        return true;
    }

    bool search(int key) {
        int h = hashFunction(key);
        int start = h;

        while (true) {
            if (table[h] == EMPTY) {
                return false;
            }

            if (table[h] == key) {
                return true;
            }

            h = (h + 1) % tableSize;

            if (h == start) {
                return false;
            }
        }
    }

    void print() {
        for (int i = 0; i < tableSize; i++) {
            cout << "[" << i << "] ";

            if (table[i] == EMPTY) {
                cout << "EMPTY";
            } else {
                cout << table[i];
            }

            cout << endl;
        }
    }
};

int main() {
    LinearProbingHashTable table(11);

    int keys[] = {55, 35, 66, 76, 59, 48, 84, 70};

    for (int key : keys) {
        table.insert(key);
    }

    table.print();

    cout << endl;

    cout << "Search 48: " << (table.search(48) ? "Found" : "Not Found") << endl;
    cout << "Search 100: " << (table.search(100) ? "Found" : "Not Found") << endl;

    return 0;
}