The Algorithm Design Manual (3rd) Exercise Solution 'E3-31'

Table of Contents

Introduction
Repository
Exercise 3-31
- Question
- Solution
  - Outline
  - Code

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-31

Question

Design a data structure that allows one to search, insert, and delete an integer X in O(1) time (i.e., constant time, independent of the total number of integers stored). Assume that $1 ≤ X ≤ n$ and that there are m + n units of space available, where m is the maximum number of integers that can be in the table at any one time. (Hint: use two arrays $A[1..n]$ and $B[1..m]$ .) You are not allowed to initialize either A or B, as that would take $O(m)$ or $O(n)$ operations. This means the arrays are full of random garbage to begin with, so you must be very careful.

Solution

Outline

The number contained in the system is represented as the index number of array A, in the other word, the element of k's index in array A is used for managing whether the system contains the number "k".

The element of k's index in array A contains a index number for array B, and let the number l. In the contrast, the element of l's index in array B contains the index number k when the system contains k. The number k exists in our system if and only if this mutual relation holds.

Code

#include <cassert>
#include <memory>
class Constant_time_dictionary {
   private:
    std::unique_ptr<size_t[]> arr_n;
    std::unique_ptr<size_t[]> arr_m;
    size_t m;
    size_t total_count{0};

   public:
    Constant_time_dictionary(size_t n, size_t _m)
        : m{_m},
          arr_n{std::make_unique<size_t[]>(n)},
          arr_m{std::make_unique<size_t[]>(_m)} {}

    bool search(size_t x) const {
        if (total_count < 1) return false;

        x--;
        auto idx_m_for_x{(arr_n[x] - reinterpret_cast<size_t>(&arr_m[0])) /
                         sizeof(size_t)};
        if (idx_m_for_x < 0 || total_count <= idx_m_for_x) return false;
        if (arr_m[idx_m_for_x] != reinterpret_cast<size_t>(&arr_n[x]))
            return false;
        return true;
    }
    void insert(size_t x) {
        if (total_count == m) return;

        x--;
        arr_m[total_count] = reinterpret_cast<size_t>(&arr_n[x]);
        arr_n[x] = reinterpret_cast<size_t>(&arr_m[total_count]);
        total_count++;
    }
    void delete_num(size_t x) {
        if (total_count < 1) return;

        x--;
        auto idx_m_for_x{(arr_n[x] - reinterpret_cast<size_t>(&arr_m[0])) /
                         sizeof(size_t)};
        if (idx_m_for_x < 0 || total_count <= idx_m_for_x) return;
        if (arr_m[idx_m_for_x] != reinterpret_cast<size_t>(&arr_n[x])) return;

        auto idx_n_for_tobe_replaced{
            (arr_m[total_count - 1] - reinterpret_cast<size_t>(&arr_n[0])) /
            sizeof(size_t)};
        arr_n[idx_n_for_tobe_replaced] =
            reinterpret_cast<size_t>(&arr_m[idx_m_for_x]);
        arr_m[idx_m_for_x] = arr_m[total_count - 1];
        total_count--;
    }
};

int main(int argc, char const *argv[]) {
    Constant_time_dictionary ctd{1, 1};
    assert(!ctd.search(1));
    ctd.insert(1);
    assert(ctd.search(1));
    ctd.delete_num(1);
    assert(!ctd.search(1));

    ctd = {2, 1};
    ctd.insert(1);
    assert(ctd.search(1));
    assert(!ctd.search(2));
    ctd.insert(2);
    assert(ctd.search(1));
    assert(!ctd.search(2));
    ctd.delete_num(2);
    assert(ctd.search(1));
    assert(!ctd.search(2));
    ctd.delete_num(1);
    assert(!ctd.search(1));
    assert(!ctd.search(2));
    ctd.insert(2);
    assert(!ctd.search(1));
    assert(ctd.search(2));

    ctd = {10, 3};
    assert(!ctd.search(1));
    ctd.insert(1);
    assert(ctd.search(1));
    assert(!ctd.search(2));
    ctd.insert(2);
    assert(ctd.search(2));
    assert(!ctd.search(10));
    ctd.insert(10);
    assert(ctd.search(10));

    assert(!ctd.search(5));
    ctd.insert(5);
    assert(!ctd.search(5));

    ctd.delete_num(2);
    assert(!ctd.search(2));
    assert(ctd.search(1));
    assert(ctd.search(10));

    return 0;
}