# Difference between revisions of "Talk:TADM2E 3.15"

(→There was an error in the deletion) |
Rbresalier (Talk | contribs) (Search after insert failure) |
||

Line 117: | Line 117: | ||

I've edited the article DELETE. now starts with A[B[k]] = ..., not with A[k] = ... | 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: | ||

+ | |||

+ | <pre> | ||

+ | Insert(3) | ||

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

+ | </pre> | ||

+ | |||

+ | 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]; |

## 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];