The Algorithm Design Manual - Exercise 3-15

Here is the statement of the exercise 3-15 in the Algorithm Design Manual.

[8] 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.


In addition to the original statement, we impose that if an integer already exists in the data structure, it is not allowed to insert it again unless it is deleted.

Following the hint, we will use array B to store the integers and array A to map the integer k to the index of B where it is stored. In other word, B[A[k]] = k.

As we are not allowed to initialize the two arrays, we will use an incremental approach. We keep track of the next available position in array B and update this information every a element is inserted or deleted. Note that we cannot use any space other than array A and array B.

Here is one solution that might work. We can use the array B itself to track the current state of the data structure. We define the following rules:
(1) if B[i] = k > 0, it means that the k is stored in B[i];
(2) if B[i] = j < 0, it means that B[j] is also a available space.
(3) finally, if B[M] = i < 0, it means that the next available position is B[-i]

The code is listed below:

#include<stdio.h>

#define False 0
#define True (!False)

#define N 10
#define M 5

int A[N + 1];
int B[M + 1];

void initialize();
void insert(int k);
int exist(int k);
void delete(int k);
void print_status();



void initialize()
{
 A[1] = 0;
 B[1] = -2; /* the next available position pointed by B[1] is B[2] */
 B[M] = -1; /* initially, the first spot is available. */
 return;
}


void insert(int k)
{
 printf("insert %d\n", k);
 A[k] = -B[M];    /* link A[k] to the next available position. */
 B[M] = B[A[k]];  /* update the next available position. */
 B[A[k]] = k;     /* put k into the current available position. */

 /* test if next available position has a link to the next-next available position */
 if (B[-B[M]] < 0 && B[-B[M]] >= -M &&  ( B[-B[-B[M]]] < 0 || B[-B[-B[M]]] > N || A[B[-B[-B[M]]]] != B[-B[-B[M]]]))
  return;

 /* in this case, the next-next available position is the one right after the -B[M] */
 if (B[M] < 0)
  B[-B[M]] = B[M] - 1;



}

int exist(int k)
{
 printf("query: does %d exist? ", k);
 if (k >= 1 && k <= N && A[k] >= 1 && A[k] <= M && B[A[k]] == k) {
  printf("Yes\n");
  return True;
 } else {
  printf("No\n");
  return False;
 }
}

void delete(int k)
{
 printf("delete %d\n", k);
 if (exist(k)) {

  if (B[M] < 0) {
   /* B is not full.
    * Suppose we have A[k] <-->B[i] and B[M] --> B[j].
    * After the call, we want to have
    * A[k] = 0 and B[M] --> B[i] and B[i] --> B[j]
    */
   B[A[k]] = B[M];
   B[M] = -A[k];
   A[k] = 0;

  } else {    /* B is full*/
   if (A[k] == M) {
    /* k is put in B[M] and we have A[k] <--> B[M].
     * so we remove the link and set next available spot to M,
     *  */
    B[M] = -M;
    A[k] = 0;

   } else {
    /* k is not in B[M].
     * suppose A[k] <--> B[i] and A[s] <-->B[M]
     * what we want to have after this call is
     * A[k] = 0 and A[s] <-->B[i] and B[M] = -M
     */

    A[B[M]] = A[k];
    B[A[k]] = B[M];
    B[M] = -M;
    A[k] = 0;

   }

  }



 } else {
  printf("%d does not exist.", k);
  return;
 }
}

void print_status()
{
 printf("current status:\n");
 printf("A: ");
 for (int i=0; i <= N; ++i) printf("%d ", A[i]);
 printf("\n");

 printf("B: ");
 for (int i=0; i <= M; ++i) printf("%d ", B[i]);
 printf("\n\n");
}


int main()
{

 initialize(); print_status();

 insert(1); print_status();
 insert(2); print_status();
 exist(3);  print_status();
 exist(4);  print_status();
 insert(3); print_status();
 exist(3);  print_status();
 insert(4); print_status();
 delete(2); print_status();
 exist(2);  print_status();
 insert(5); print_status();
 insert(6); print_status();
 delete(5); print_status();
 exist(5);  print_status();
 insert(7); print_status();
 delete(7); print_status();
 insert(8); print_status();
 delete(3); print_status();


}

And the output is listed below:

current status:
A: 0 0 0 0 0 0 0 0 0 0 0
B: 0 -2 0 0 0 -1

insert 1
current status:
A: 0 1 0 0 0 0 0 0 0 0 0
B: 0 1 -3 0 0 -2

insert 2
current status:
A: 0 1 2 0 0 0 0 0 0 0 0
B: 0 1 2 -4 0 -3

query: does 3 exist? No
current status:
A: 0 1 2 0 0 0 0 0 0 0 0
B: 0 1 2 -4 0 -3

query: does 4 exist? No
current status:
A: 0 1 2 0 0 0 0 0 0 0 0
B: 0 1 2 -4 0 -3

insert 3
current status:
A: 0 1 2 3 0 0 0 0 0 0 0
B: 0 1 2 3 -5 -4

query: does 3 exist? Yes
current status:
A: 0 1 2 3 0 0 0 0 0 0 0
B: 0 1 2 3 -5 -4

insert 4
current status:
A: 0 1 2 3 4 0 0 0 0 0 0
B: 0 1 2 3 4 -5

delete 2
query: does 2 exist? Yes
current status:
A: 0 1 0 3 4 0 0 0 0 0 0
B: 0 1 -5 3 4 -2

query: does 2 exist? No
current status:
A: 0 1 0 3 4 0 0 0 0 0 0
B: 0 1 -5 3 4 -2

insert 5
current status:
A: 0 1 0 3 4 2 0 0 0 0 0
B: 0 1 5 3 4 -5

insert 6
current status:
A: 0 1 0 3 4 2 5 0 0 0 0
B: 0 1 5 3 4 6

delete 5
query: does 5 exist? Yes
current status:
A: 0 1 0 3 4 0 2 0 0 0 0
B: 0 1 6 3 4 -5

query: does 5 exist? No
current status:
A: 0 1 0 3 4 0 2 0 0 0 0
B: 0 1 6 3 4 -5

insert 7
current status:
A: 0 1 0 3 4 0 2 5 0 0 0
B: 0 1 6 3 4 7

delete 7
query: does 7 exist? Yes
current status:
A: 0 1 0 3 4 0 2 0 0 0 0
B: 0 1 6 3 4 -5

insert 8
current status:
A: 0 1 0 3 4 0 2 0 5 0 0
B: 0 1 6 3 4 8

delete 3
query: does 3 exist? Yes
current status:
A: 0 1 0 0 4 0 2 0 3 0 0
B: 0 1 6 8 4 -5

--END--