Talk:TADM2E 3.15

I had a hard time wrapping my head around the solution. So I went to implement it in c++. Sorry if I'm mistaken, but the proposed solution does not appear to give the correct behavior. It seems that if you do a delete and then an insert, the new insert will clobber the last written value in the B array, and the corresponding entry for it in A is not updated. I've copied my implementation below with a counterexample.

// // Ex3-11.h // TADMExercises //

1. ifndef __TADMExercises__Ex3_11__
2. define __TADMExercises__Ex3_11__

1. include <stdio.h>
2. include <vector>

class Ex3d11 { private:

   int k;
   int max;
   std::vector<int> A;
   std::vector<int> B;
   

public:

   Ex3d11( int _max ) : max(_max), k(0) {};
   void Init();
   void Run();
   void Insert( int v );
   bool Search( int x ) const;
   void Delete( int v );

};

1. endif /* defined(__TADMExercises__Ex3_11__) */

// // Ex3-11.cpp // TADMExercises //

1. include <stdlib.h>
2. include <iostream>
3. include "Ex3-11.h"

void Ex3d11::Init() {

   // Fill A and B with junk values
   
   for( int i = 0; i < max; i++)
   {
       A.push_back( (rand() % max) + 1 );
       B.push_back( (rand() % max) + 1 );
   }

}

void Ex3d11::Run() {

   std::cout << "running...\n";
   
   Insert( 3 );
   Insert( 9 );
   Insert( 8 );
   
   Delete( 3 );
   
   Insert( 5 );
   
   std::cout << "8 exists? " << ( Search(8) ? "Y" : "N" ) << "\n";

}

void Ex3d11::Insert(int X) {

   if( k < max )
   {
       k = k+1;
       A[X] = k;
       B[k] = X;
   }

}

bool Ex3d11::Search( int X ) const {

   return (A[X] < k) and (B[A[X]] == X);

}

void Ex3d11::Delete( int X ) {

   if( Search(X))
   {
       A[k] = A[X];
       B[A[X]] = B[k];
       k = k-1;
   }

}

// // main.cpp // TADMExercises //

1. include <iostream>
2. include "Ex3-11.h"

int main(int argc, const char * argv[]) {

   Ex3d11 example(10);
   
   example.Init();
   example.Run();
   
   return 0;

}