Talk:TADM2E 3.15 - Revision history

Rbresalier: Search after insert failure

2018-11-25T16:41:02Z

Search after insert failure

Azaza: /* There was an error in the deletion */

2015-06-04T05:48:20Z

‎There was an error in the deletion

Azaza: /* There was an error in the deletion */ new section

2015-06-04T05:47:50Z

‎There was an error in the deletion: new section

NullObjectPtr at 01:17, 12 January 2015

2015-01-12T01:17:31Z

NullObjectPtr: Created page with "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..."

2015-01-12T01:12:50Z

Created page with "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..."

New page

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;
}

← Older revision		Revision as of 16:41, 25 November 2018
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];

← Older revision		Revision as of 05:48, 4 June 2015
Line 116:		Line 116:
	== There was an error in the deletion ==		== There was an error in the deletion ==

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

← Older revision		Revision as of 05:47, 4 June 2015
Line 113:		Line 113:
	}		}
	</pre>		</pre>
		+
		+	== There was an error in the deletion ==
		+
		+	I've edited the article DELETE now starts with A[B[k]] = ..., not with A[k] = ...

@@ Line 1: / Line 1: @@
 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
@@ Line 29: / Line 30: @@
 #endif /* defined(__TADMExercises__Ex3_11__) */
 //
 //  Ex3-11.cpp
@@ Line 89: / Line 92: @@
+     }
+}
 //
 //  main.cpp
@@ Line 107: / Line 112: @@
      return 0;
+}