Shifting Arrays (one space to right)

[aznballerlee]

How do I shift my arrays .. starting at a position in the middle of the arrays .. to one place to the right?

I tried using a for loop, but it doesn't work.

Here is my task:
int insert(string a[], int n, string s, int pos, int max);
Insert the string s into the array at index pos, moving the n minus pos existing elements starting at pos one place to the right to make room. Return the index of the element inserted. It is legitimate for pos to be 0 or n. Return -1 if inserting the element would cause the array to have more than max elements. For example,
string h[6] = { "peter", "lois", "meg", "chris", "stewie", "brian" };int k = insert(h, 3, "quagmire", 1, 6); // returns 1
// h is now "peter" "quagmire" "lois" "meg" "stewie" "brian"
and my progress so far:

int insert(string a[], int n, string s, int pos, int max);

int n;
int pos;

if (n + 1 > max)
    return -1;

else
    for (pos; pos <= n-pos; pos++)
    {
        a[n-1] = a[n];
    }

    string s = a[pos];
    return pos;

[~s.o.s~]

Hmm... what happens if the capacity of array overflows ?
You state in your problem statement that the function returns -1 if the inserted element causes the array to have more than max elements , but still in your eg. you return 1 ?

Post two or three egs. specifying different cases so that the problem statement is a bit clearer .

BTW does your code even compile ?

[Ancient Dragon]

The loop appears to be about right except you need to save the value of pos so that you can use it after the loop finished. The current code destroys the value of pos.

Also, the else statement is unnecessary because of the previous return.

Remove the semicolon at the end of the function name/parameter list and add some brackets to enlose the function statements.

[~s.o.s~]

The loop appears to be about right except you need to save the value of pos so that you can use it after the loop finished. The current code destroys the value of pos.

Hmm... I think it is more of a compilation error.

It would probably consider int n ; and int pos; as the redeclaration and flag errors.

[aznballerlee]

Okay, here's an updated version of what I edited.

int insert(string a[], int n, string s, int pos, int max)
{

if (n+1>max)
   return -1;

else
    for (n-1; n>pos; n--)
   {       
         a[n] = a[n-1];
         string temp = "";
         a[n] = temp;
   }

       string s = a[pos]
       return pos;

}

[Ancient Dragon]

a[n] = a[n-1];
         string temp = "";
         a[n] = temp;

That won't work -- yes it compiles but right after assigning the nth element the value of n-1 you turn around and assign an empty string to it. Delete the 2nd and 3d lines above, they are not necessary.

>>moving the n minus pos existing elements starting at pos one place to the right
That does not mean you move the entire array, only the (n-pos) number of elements. In the example you posted, n = 3 and pos = 1, so (n-pos) = 2, so you move "lois" and "meg" to the right one position, deleting "chris" in the process. All other string positions remain unchanged.

The loop counter needs to start at (n+pos-1), or 3 and count down (not up) to pos, or 1.

[aznballerlee]

Yes, I get your logic,but the problem is that if I don't create a temporary string, each loop will assign things wrong.

If I went from a[2] = a[3],
and then the next iteration,
get a[1] = a[2], I would insert the new
value of a[2] into a[1]..

unless you think what I did before was fine ..

[Ancient Dragon]

I would use a different loop counter such as i to reduce confusion.

int i;
for( i = (n+pos-1); i > n; i--)
{
   a[i] = a[i-1];
}

[aznballerlee]

Would using the loop work? I thoguht about it,
and ifi you keep looping, each time there might be an unintended error.

say i=2.

a[2] = a[3]

next iteration, i = 1
a[1] = a[2]

my questionable problem is .. would they assign a[1]
just to the position a[2], or since we set a[2] equal to a[3],
they would mistakenly set a[1] also equal to a[3]?

a[i] = a[i+1];

[Ancient Dragon]

a[2] = a[3] <<< NO NO NO

NO! NO! NO! that is backwards. Look at the loop I posted.

a[3] = a[2]  <<First loop iteration
a[2] = a[1] << Second iteration 

a[1] = new string << final result

The loop counter MUST count down for this to work correctly.

[aznballerlee]

Okay, I will try that.

Thoguht about it:

Why would we be going backward in the loop? I want to shift the values to the right.

What I want ..

a[2] = a[3] <<First loop iteration
a[1] = a[2] << Second iteration

[John A]

a[2] = a[3] <<First loop iteration
a[1] = a[2] << Second iteration

That doesn't work!

You've got a value in spot 2. You want to move it one to the right, so into spot 3.

a[3] = a[2];

Your current code is moving the array backwards. Do what Ancient Dragon said.

[Ancient Dragon]

No, that is not what you want. Re-read the requirements and the example in your original post

string h[6] = { "peter", "lois", "meg", "chris", "stewie", "brian" };
int k = insert(h, 3, "quagmire", 1, 6); // returns 1
// h is now "peter" "quagmire" "lois" "meg" "stewie" "brian"

first iteration:
h[3] = h[2]
h is now { "peter", "lois", "meg", "meg", "stewie", "brian" };
Notice that "cris" is lost -- tossed into the bit bucket

second loop iteration
h[2] = h[1]
h is not { "peter", "lois", "lois", "meg", "stewie", "brian" };

now insert the new string
h is not { "peter", "quagmire", "lois", "meg", "stewie", "brian" };

[aznballerlee]

Gotcha! I understand the procedures now. Now let me come up with the code and it would be great if anyone could verify the correctness.

Okay UPDATE: (wouldn't it be i>pos, not i>n?) everything else i agree with you, dragon,

int i;
for( i = (n+pos-1); i > pos; i--)
{
   a[i] = a[i-1];
}

string s = a[pos]
return pos;

[WaltP]

Okay, I will try that.

Thoguht about it:

Why would we be going backward in the loop? I want to shift the values to the right.

What I want ..

a[2] = a[3] <<First loop iteration
a[1] = a[2] << Second iteration

OK, try this. Seriously....

Take a piece of paper. Cut out about 20-30 squares from it.
Now place all but one in one row on a table in front of you.
Now read in a string by writing a sentence, one letter per square, starting from the far left. Don't make the sentence long enough to fill every square. When you end, after the last square you wrote on, write "EOS" to indicate the End of string (\0). That square is part of the sentence and must be there.

Decide where you want to add a space and place that extra piece under that letter (next row).

Here comes the problem. Using only two fingers, moving ONLY one piece of paper at a time in any direction, how would you make room for that blank without destroying the sentence.

When you figure that out, decide what you just did and how to translate that to code.

I've used this technique for complex array and matrix manipulation and it works really well in debugging code, too.

[aznballerlee]

Thanks, I get that logic. I have to start from the end, and start moving to make room, and finally add the new string.

Please, anyone verify this is the correct code?

int i;
for( i = (n+pos-1); i > pos; i--)
{
   a[i] = a[i-1];
}

string s = a[pos]
return pos;

[Ancient Dragon]

>>Please, anyone verify this is the correct code?

compile and run it, then you will verify it for yourself. Debugging programs is 3/4th of the programming efforts.

[aznballerlee]

Alright, I'm trying very hard.

I got one error.
error: Error 1 error C2082: redefinition of formal parameter 's'

which refers to this :

int insert(string a[], int n, string s, int pos, int max);

int insert(string a[], int n, string s, int pos, int max)
{

if (n + 1 > max)
    return -1;

else
    int i;
    for( int i = (n+pos-1); i > pos; i--)
    {
        a[i] = a[i-1];
    }

string s = a[pos];
return pos;

}

Suggestions for fixing this bug?

[aznballerlee]

Awesome, I found out my mistake. I already declared the string, so can;t declare it again.

I hope my other tests work out, or I'd have to post something here.

Thanks everyone for their input!

[Ancient Dragon]

>>string s = a[pos];
should be the opposite
a[pos] = s;

[aznballerlee]

int insert(string a[], int n, string s, int pos, int max);
int insert(string a[], int n, string s, int pos, int max)
{

if (n + 1 > max)
    return -1;

else
    int i;
    for( int i = n; i > pos && i-1 >=0; i--)
    {
        a[i] = a[i-1];
    }

a[pos] = s;
return pos;

}

This is the final code, and I run assert, but I got a problem. It gave me the right return value, but I checked the matching elemnts, and assert crashed.

Can anyone let me know why?

I used these assertions:

string f[6] = { "peter", "lois", "meg", "chris", "stewie", "brian" };

assert(insert(f, 3, "quagmire", 1, 6) == 1
&& a[0] == "peter"
&& a[1] == "quagmire"
&& a[2] == "lois"
&& a[3] == "meg"
&& a[4] == "stewie"
&& a[5] == "brian");

[Ancient Dragon]

I did not get an assert error. I think you got the error because your test data did not compile cleanly -- array f[] should be named a[].