Difference between revisions of "Talk:TADM2E 3.15"

Revision as of 05:48, 4 June 2015

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] = ...