Difference between revisions of "Talk:TADM2E 3.15"

Latest revision as of 16:41, 25 November 2018

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
//

#ifndef __TADMExercises__Ex3_11__
#define __TADMExercises__Ex3_11__

#include <stdio.h>
#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 );
};

#endif /* defined(__TADMExercises__Ex3_11__) */

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

#include <stdlib.h>
#include <iostream>
#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
//

#include <iostream>
#include "Ex3-11.h"

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

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

There was an error in the deletion

I've edited the article DELETE. now starts with A[B[k]] = ..., not with A[k] = ...

Search after insert fails and a fix

With the insertion/deletion as they defined today (Nov 25 2018, change k at start of insert, change k at end of delete), the following test case fails:

Insert(3)
Search(3) <== Returns false instead of true because A[3] == 1, fails A[3] < 1 (k) test

To get this test case to work, I think the place where k is updated needs to be changed to the other side of each operation:

Insert X:

 A[X] = k; 
 B[k] = X;
 k = k+1;    <= Put this at the end of the insert

Delete X:

 k = k-1;
 A[B[k]] = A[X]; 
 B[A[X]] = B[k]; 

Additionally since A[] has random initial values that are not guaranteed to be in the range 0..k-1 which could cause B[A[X]] to index B out of bounds, a check of A[X] >= 0 should be added into Search:

Search X:

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

Finally I think some safeguards also need to be added into Insert/Delete to check the value of k before doing anything:

Insert X:

 if (k < n)
   A[X] = k; 
   B[k] = X;
   k = k+1;    <= Put this at the end of the insert

Delete X:

 if (k > 0)
   k = k-1;
   A[B[k]] = A[X]; 
   B[A[X]] = B[k];