Brtdku

Working on an addBefore() method that adds a new element to the beginning of an array of ints and then causes the existing elements to increase their index by one.

This is what is showing in the console when trying to run --
java.lang.RuntimeException: Index 1 should have value 11 but instead has 0
at IntArrayListTest.main(IntArrayListTest.java:67)

Below is the code I have so far.

public class IntArrayList {

private int a; 

private int length;

private int index;

private int count;



public IntArrayList() {

    length = 0; 







    a = new int[4]; 



}



public int get(int i) { 



    if (i < 0 || i >= length) {

        throw new ArrayIndexOutOfBoundsException(i);

    }

    return a[i];

}

public int size() { 



    return length; 

}



public void set(int i, int x) {



    if (i < 0 || i >= a.length) {

        throw new ArrayIndexOutOfBoundsException(i);

    }

    a[i] = x;

}

public void add(int x) {



    if (length >= a.length) {



        int b = new int[a.length * 2];



        for (int i = 0; i < a.length; i++) {

            b[i] = a[i];

        }



        a = b;



        //count += 1;

    }



    a[length] = x;

    count++;



    length = length + 1;

}

public void addBefore(int x) {

    int b = new int[a.length*2];

    for (int i = 0; i < a.length; i++) {

        b[i+a.length] = a[i];

    }

    a = b;

    a[index] = x;

    length ++;

    }   

}

Whether you add first or last, you need to only grow the array size if it is already full.

The count field seems to be exactly the same as length, and index seems unused and meaningless as a field, so remove them both.

To rearrange values in an array, use this method:
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

You two "add" methods should then be:

public class IntArrayList {

    private int a; // Underlying array

    private int length; // Number of added elements in a



    // other code



    public void add(int x) {

        if (length == a.length) {

            int b = new int[a.length * 2];

            System.arraycopy(a, 0, b, 0, length);

            a = b;

        }

        a[length++] = x;

    }



    public void addBefore(int x) {

        if (length < a.length) {

            System.arraycopy(a, 0, a, 1, length);

        } else {

            int b = new int[a.length * 2];

            System.arraycopy(a, 0, b, 1, length);

            a = b;

        }

        a[0] = x;

        length++;

    }

}

If the answer requires you to do the looping yourself then something like this should work fine (one of a few ways to do this, but is O(n)) :

public void addBefore(int x) {

        if(length + 1 >= a.length){

            int b = new int[a.length*2];

            b[0] = x;

            for (int i = 0; i < length; i++) {

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

            }

            a = b;

        } else {

            for (int i = length; i >= 0 ; i--) {

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

            }

            a[0] = x;

        }

        length++;

    }

I noticed this started running a "speed test" - not sure how useful a test like that is, as it would be based on cpu performance, rather than testing complexity of the algorithm ..

you had three problems with your solution:

1. you increased the length of a every time the method was called. this would quickly create an OutOfMemoryException




2. when you copied values from a to b, you did b[i+a.length] = a[i]; which means the values would be copied to the middle of b instead of shift just one place




3. at the end, you put the new value in the end of the array instead of at the beginning.

all this I was able to see because I used a debugger on your code. You need to start using this tool if you want to be able to detect and fix problems in your code.

so fixed solution would do this:

1. check if a is full (just like it is done with add() method) and if so, create b, and copy everything to it and so on)




2. move all values one place ahead. the easiest way to do it is to loop backwards from length to 0




3. assign new value at the beginning of the array

here is a working solution:

public void addBefore(int x) {



    // increase length if a is full

    if (length >= a.length) {

        int b = new int[a.length * 2];

        for (int i = 0; i < a.length; i++) {

            b[i] = a[i];

        }

        a = b;

    }

    // shift all values one cell ahead

    for (int i = length; i > 0; i--) {

        a[i] = a[i-1];

    }



    // add new value as first cell 

    a[0] = x;

    length ++;

    }   

}

You can use the existing Java methods from the Colt library. Here is a small example that uses a Python syntax (to make the example code small I use Jython):

from cern.colt.list import IntArrayList

a=IntArrayList()

a.add(1); a.add(2)    # add two integer numbers

print "size=",a.size(),a

a.beforeInsert(0, 10) # add 10 before index 0 

print "size=",a.size(),a

You can use DataMelt program to run this code. The output of the above code is:

size= 2 [1, 2]

size= 3 [10, 1, 2]

As you can see, 10 is inserted before 1 (and the size is increased)
Feel free to change the codding to Java, i.e. importing this class as

import cern.colt.list.IntArrayList

IntArrayList a= new IntArrayList()

You could use an ArrayList instead and then covert it to an Integer Array which could simplify your code. Here is an example below:
First create the ArrayList:

ArrayList<Integer> myNums = new ArrayList<Integer>();

Next you can add the values that you want to it, but I chose to just add the numbers 2-5, to illustrate that we can make the number 1 the first index and automatically increment each value by one index. That can simplify your addBefore() method to something such as this:

public static void addBefore(ArrayList<Integer> aList) {

    int myInt = 1;

    aList.add(0, myInt);

}

Since your ArrayList has ONE memory location in Java, altering the Array within a method will work (this would also work for a regular Array). We can then add any value to the beginning of the ArrayList. You can pass an Integer to this method as the second argument (int x), if you want, but I simply created the myInt primitive to simplify the code. I know that in your code you had the (int x) parameter, and you can add that to this method. You can use the ArrayList.add() method to add the int to index 0 of the Array which will increment each Array element by 1 position. Next you will need to call the method:

addBefore(myNums);//You can add the int x parameter and pass that as an arg if you want here

Next we can use the ArrayList.toArray() method in order to covert the ArrayList to an Integer Array. Here is an example below:

Integer integerHolder = new Integer[myNums.size()];

Integer numsArray = (Integer)myNums.toArray(integerHolder);

System.out.println(Arrays.toString(numsArray));

First we create an ArrayHolder that will be the same size as your ArrayList, and then we create the Array that will store the elements of the ArrayList. We cast the myNums.toArray() to an Integer Array. The results will be as follows. The number 1 will be at index 0 and the rest of your elements will have incremented by 1 index:

[1, 2, 3, 4, 5]

You could do the entire process within the addBefore() method by converting the Array to an ArrayList within the method and adding (int x) to the 0 index of the ArrayList before converting it back into an Array. Since an ArrayList can only take a wrapper class object you'll simply need to convert the int primitive Array into the type Integer for this to work, but it simplifies your addBefore() method.