CODEWITHSUNDEEP
java
Lisa
Lisa

Reputation: 201

Making a Dynamic Array for a class without using Arraylists in Java and have not been properly taught how to do it

So I am taking a Java class with a teacher who is not good at teaching us what we need to do the homework.

This assignment, we are supposed to make a Dynamic Array of Integers class with Constructors, Methods, and required features. Are are not allowed to use ArrayLists I've got some of them written, a couple are not working and I don't know how to do the others.

Here are the requirements:

  1. private int array[] field. You MUST store the data internally in a regular partially-filled array of integers. Please DO NOT USE ArrayList. The size of the allocated array is its capacity and will be discussed below.

  2. private int size field. This variable stores the number of “occupied” elements in the array. Set to 0 in the constructor.

  3. Constructor with parameter. The parameter defines the capacity of initial array. Allocates array of given capacity, sets size field to zero. In case the parameter given to constructor is less than 0, IllegalArgumentException is being thrown.

  4. No-argument constructor. Allocates array of size 10, sets size field to 0.

  5. Copy constructor. The constructor takes an object of type DynamibcArray as a parameter and copies it into the object it creates. The constructor throws IllegalArgumentException if the object that was passed to copy from is null.

  6. int getSize() returns the size – a number of occupied elements in the array.

  7. int [] toArray() accessor returns the array. Make sure you DO NOT return the private array field. Instead, allocate memory for the new array, copy your array field into that new object, and return the new array.

  8. public void push(int num) adds a new element to the end of the array and increments the size field. If the array is full, you need to increase the capacity of the array: a. Create a new array with the size equal to double the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Add the new element to the end of the new array. d. Use new array as an array field.

  9. public int pop() throws RuntimeException removes the last element of the array and returns it. Decrements the size field. If the array is empty a RuntimeException with the message “Array is empty” must be thrown. At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array:

    a. Create a new array with the size equal to half of the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Use new array as an array field.

  10. int get(int index) throws IndexOutOfBoundsException returns element of the array with the requested index. If the index provided is too large or negative, the IndexOutOfBoundsException is thrown with the message “Illegal index”.

  11. int indexOf(int key) returns the index of the first occurrence of the given number. Returns -1 when the number is not found.

  12. void add(int index, int num) throws IndexOutOfBoundsException adds a new element (passed as parameter num) to the location of the array specified by index parameter. If the index is larger than size of the array or less than 0, IndexOutOfBoundsException is thrown. When adding the element into the middle of the array, you’ll have to shift all the elements to the right to make room for the new one. If the array is full and there is no room for a new element, the array must be doubled in size. Please follow the steps listed in the push() method description to double the capacity of the array.

  13. int remove ( int index) throws IndexOutOfBoundsException removes the element at the specified position in this array. When the element is removed from the middle of the array, all the elements must be shifted to close the gap created by removed element. If the index value passed into the method is more or equal to the size or less than 0 the IndexOutOfBoundsException must be thrown. At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array.

Here is the class with the methods that I've made so far.

/**
 *
 * @author Lisa Hergert
 */
public class DynamicArray {
    private int array[];
    private int size;

    /*
    * Constructor
    * @param capacity - integer
    * throws an IllegalArgumentExeception if capacity is less than 0
    */
    public DynamicArray (int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("Size cannot be less than 0.");
        }
    }

    /*
    * no-arg constructor
    */
    public DynamicArray () {
        array = new int [10];
        size = 0;
    }

    /*
    * Copies the array to a new one
    * @param - array [] - integer array
    */
    public DynamicArray (int array[]) {
        int arrayCopy [] = new int [array.length];
        for (int i = 0; i < array.length; i++) {
            arrayCopy[i] = array[i];
        }
    }

    /*
    * getSize returns the size.
    * @return - size
    */
    public int getSize () {
        return size;
    }

    /*
    * @param array[] - integer
    * @return array
    */
    public int [] toArray (int array[]) {
        return array;
    }

    /*
    * @param num - integer
    */
    public void push (int num) {

    }

    /*
    * @return pop - integer
    */
    public int pop() throws RuntimeException { 
        return pop();
    }

    /*
    * @param index - integer
    */
    public int get(int index) throws IndexOutOfBoundsException {
        if (index >= size || index < 0)
            throw new IndexOutOfBoundsException("Illegal Index");
        return array[index];
    }

    public int indexOf(int key) {
        int index = 0;

        return index;
    }

    public void add(int index, int num) throws IndexOutOfBoundsException {
        if (index >= size || index < 0)
            throw new IndexOutOfBoundsException("Illegal Index");
        int oldValue = array[index];
        array[index] = num;
        return oldValue;
    }

    public int remove(int index) throws IndexOutOfBoundsException {

    }
}

I am asking for help or even advice on where I can look up what I need to do. I I am going to go to the tutoring lab on campus and see if they can help me understand what the teacher has not taught properly, but I would like to try and work on it a little on my own before then.

Here is one of a few problems.

/*
* @return pop - integer
*/
public int pop() throws RuntimeException { 
    return pop();
}

I know that is not right. Even if you don't want to show me the code, can you maybe give me a recommendation on a site I can look up what I need to do, the requirements for this one are #9.

Thank you for your help. I wish I had the knowledge to do this without help, but that is not what has occurred, so I have to use outside sources. This site has been very helpful in the past.

Upvotes: 2

Views: 8065

Answers (3)

Seelenvirtuose
Seelenvirtuose

Reputation: 20618

Let's start over again. From the beginning. I will comment each step in this tutorial. (Note that this question is usually far too broad to be answered, but today I am going to do that nevertheless.)

This assignment, we are supposed to make a Dynamic Array of Integers class with Constructors, Methods, and required features.

Let's start with the class itself:

public final class DynamicArray {
}

This is the part, you have already done. Everything that follows now (fields, methods) will be part of that class. One note: I have made that class final to prevent subclassing, which would otherwise introduce some other problems.

private int array[] field. You MUST store the data internally in a regular partially-filled array of integers. Please DO NOT USE ArrayList. The size of the allocated array is its capacity and will be discussed below.

You have also already done this:

private int[] array;

Note, that I usually would mark that field as private. But as some other requirements are too grow and shrink that array, we cannot do that.

private int size field. This variable stores the number of “occupied” elements in the array. Set to 0 in the constructor.

You also have already done this:

private int size;

The requirement to "set to 0 in the constructor" is superfluous, because in Java such fields are initialized to their default value (which is 0 in this case). That means, whenever you create an instance of your DynamicArray class, the field size will automatically have a value of 0. I will therefore not set the size in the following constructors.

Constructor with parameter. The parameter defines the capacity of initial array. Allocates array of given capacity, sets size field to zero. In case the parameter given to constructor is less than 0, IllegalArgumentException is being thrown.

Although you already have shown us the constructor, you forgot to initialize the array. Here we go:

public DynamicArray(int capacity) {
    if (capacity < 0)
        throw new IllegalArgumentException("Capacity cannot be less than 0.");
    array = new int[capacity];
}

I would argue that even a capacity of 0 does not make much sense, but we can deal with that later (when the array shall grow).

No-argument constructor. Allocates array of size 10, sets size field to 0.

You have already shown the constructor, but you should use constructor chaining, because you already have another constructor that handles the initialization.

public DynamicArray() {
    this(10);
}

It is even better to have a constant for that:

private static final int DEFAULT_CAPACITY = 10;

public DynamicArray() {
    this(DEFAULT_CAPACITY);
}

Copy constructor. The constructor takes an object of type DynamibcArray as a parameter and copies it into the object it creates. The constructor throws IllegalArgumentException if the object that was passed to copy from is null.

Unfortunately, you got this one wrong. A copy constructor takes another DynamicArray (not an int[]).

public DynamicArray(DynamicArray source) {
    if (source == null)
        throw new IllegalArgumentException("Source array must not be null.");
    this.array = Arrays.copyOf(source.array, source.array.length);
    this.size = source.size;
}

This uses the helper class java.util.Arrays to create a copy of the internal array.

int getSize() returns the size – a number of occupied elements in the array.

Ok. This one's easy:

public int getSize() {
    return size;
}

int [] toArray() accessor returns the array. Make sure you DO NOT return the private array field. Instead, allocate memory for the new array, copy your array field into that new object, and return the new array.

Although you have this method, you forgot to make a copy of the internal array. You are not allowed to return that. And you should not return that, because any caller then could change your internal array. So we are going to use the same technique as in the copy constructor:

public int[] toArray() {
    return Arrays.copyOf(array, array.length);
}

public void push(int num) adds a new element to the end of the array and increments the size field. If the array is full, you need to increase the capacity of the array.

This method has much to do. So you should use some helper method, e.g. for the growing functionality.

public void push(int num) {
    growIfNecessary();
    array[size] = num;
    size += 1;
}

Some explanation: I am postponing the growing functionality for now (so I extracted it into another method that I will show later). For pushing the given number into the internal array, you must know the exact position. Fortunately the size field tells you exactly that, but you also have to increment that pointer. You could also do it that way:

public void push(int num) {
    growIfNecessary();
    array[size++] = num;
}

public int pop() throws RuntimeException removes the last element of the array and returns it. Decrements the size field. If the array is empty a RuntimeException with the message “Array is empty” must be thrown. At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array.

public int pop() {
    if (size == 0)
        throw new NoSuchElementException();
    int result = array[--size];
    shrinkIfNecessary();
    return result;
}

Hint: I am throwing another exception which is more appropriate for that case. Popping an element is the opposite function of pushing one. We are first decrementing the pointer, then reading and returning the value. Additionally, I extracted the shrinking functionality into another method that I will also show later.

int get(int index) throws IndexOutOfBoundsException returns element of the array with the requested index. If the index provided is too large or negative, the IndexOutOfBoundsException is thrown with the message "Illegal index".

You got this one completely right:

public int get(int index) throws IndexOutOfBoundsException {
    if (index >= size || index < 0)
        throw new IndexOutOfBoundsException("Illegal index");
    return array[index];
}

int indexOf(int key) returns the index of the first occurrence of the given number. Returns -1 when the number is not found.

With this method you shall search for a given number in the array. It needs a loop!

public int indexOf(int key) {
    for (int i = 0; i < size; i++)
        if (array[i] == key)
            return i; // found
    return -1; // not found
}

void add(int index, int num) throws IndexOutOfBoundsException adds a new element (passed as parameter num) to the location of the array specified by index parameter. If the index is larger than size of the array or less than 0, IndexOutOfBoundsException is thrown. When adding the element into the middle of the array, you’ll have to shift all the elements to the right to make room for the new one. If the array is full and there is no room for a new element, the array must be doubled in size. Please follow the steps listed in the push() method description to double the capacity of the array.

This one is somewhat advanced, as it needs shifting the elements, which you did not do in your attempt. So let's go:

public void add(int index, int num) throws IndexOutOfBoundsException {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException("Illegal index");
    growIfNecessary();
    System.arraycopy(array, index, array, index + 1, size - index);
    array[index] = num;
    size += 1;
}

Explanation: The index checking must now check whether the index is greater than the size (not greater or equal), because you also can add an element at the end of the array (at the position that size points to). We then have to grow the array if necessary (like in the push method). Then I use a Java built-in class for shifting all elements one position to the rigth from the given index to the end. The last step is to add the element at the given index, and we must not forget to increment the size.

int remove ( int index) throws IndexOutOfBoundsException removes the element at the specified position in this array. When the element is removed from the middle of the array, all the elements must be shifted to close the gap created by removed element. If the index value passed into the method is more or equal to the size or less than 0 the IndexOutOfBoundsException must be thrown. At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array.

This one is the most difficult method. I will show you directly the whole thing:

public int remove(int index) {
    if (index >= size || index < 0)
        throw new IndexOutOfBoundsException("Illegal Index");
    int result = array[index];
    System.arraycopy(array, index + 1, array, index, size - index - 1);
    size -= 1;
    shrinkIfNecessary();
    return result;
}

We first have to check the index, then we can get the element that later will be returned by this method. Now comes the shifting: We shift all elements from position index + 1 to the end one place to the left. We then decrement the size and shrink the internal array if necessary. That's it.

Now I am going to show you the last two helper methods.

Let's start with the growing method:

a. Create a new array with the size equal to double the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Add the new element to the end of the new array. d. Use new array as an array field.

private void growIfNecessary() {
    if (size == array.length) {
        if (array.length == 0)
            array = new int[1]; // Special case for capacity 0.
        else
            array = Arrays.copyOfRange(array, 0, array.length * 2);
    }
}

The array is full, if the size equals the capacity. Again, I am using the Arrays helper class. The copyOfRange method is able to create a larger array.

Now to the shrinking method:

a. Create a new array with the size equal to half of the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Use new array as an array field.

private void shrinkIfNecessary() {
    if (size * 4 <= array.length)
        array = Arrays.copyOfRange(array, 0, array.length / 2);
}

Here, we do not have any special case. Simply shrink the array, if the capacity is 4 times larger than the size. That's it.

Study the code carefully and try to reproduce the code. The usage of library methods (System.arraycopy and Arrays.copyOf) can easily be replaced by simple for loops using temporary arrays. Try it out.

Upvotes: 1

Ryan Leach
Ryan Leach

Reputation: 4470

public int pop() throws RuntimeException removes the last element of the array and returns it. Decrements the size field. If the array is empty a RuntimeException with the message “Array is empty” must be thrown. At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array:

a. Create a new array with the size equal to half of the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Use new array as an array field.

at the moment, your pop command is just running itself, recursively. This will crash.

Edit: I recommend partially implementing remove before pop, as it will make pop easier.

Lets break this down into a bullet point list and examine each item. (Also I recommend making a new question for each specific piece of advice you need)

  1. public int pop() throws RuntimeException
  2. removes the last element of the array and returns it.
  3. Decrements the size field.
  4. If the array is empty a RuntimeException with the message “Array is empty” must be thrown.
  5. At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array:
  6. a. Create a new array with the size equal to half of the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Use new array as an array field.

Now I've broken this down into sections, to start with I would ignore 3, 4, 5, 6

and just implement a super dumb pop method that just removes the last element from the array.

Once you have that working, concentrate on the edge cases.

3. Decrements the size field This is going to be a cross cutting concern across your class. You will want to do this only in a small reuseable part of your code, as you are going to be messing with the the size field every time an element gets added or removed.

4. If the array is empty a RuntimeException with the message "Array is empty" must be thrown. You will want to tackle this at the very start of your pop method, as it's a guard clause protecting invalid use.

5.At this point check the capacity of the array. If the capacity is 4 times larger than the number of occupied elements (size), it is time to shrink the array: Again, this is probably going to be a recurring cross cutting concern, so defining this as a separate private method that gets reused will be helpful.

6. a. Create a new array with the size equal to half of the capacity of the original one. b. Copy all the elements from the array field to the new array. c. Use new array as an array field. Is providing guidance on how best to implement 5.

you can find more information on array copying and stuff over on the docs of the Arrays static helper class. https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html as well as the arrayCopy method in System https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#arraycopy(java.lang.Object,%20int,%20java.lang.Object,%20int,%20int)

Upvotes: 0

skashyap
skashyap

Reputation: 143

This is a great programming assignment to give students a clear understanding of ArrayList. As you might have already guessed your instructor wants you to implement ArrayList of your own and its a wonderful way to teach Data Structure.

Starting with the requirements one by one

  • Constructor with parameter : The intention is that you can initialize an array of specific length. However, since the array has no element keep its size as 0

    public DynamicArray (int capacity) { if (capacity < 0) { throw new IllegalArgumentException("Size cannot be less than 0."); } this.array = new int[capacity]; this.size = 0 }

  • Constructor with no parameter : Similar as previous just that capacity will be replaced with a constant value of 10. It makes complete sense for the sake of legibility that you assign this constant as

    public static final int DEFAULT_CAPACITY = 10;

    • For shrink/increase of capacity during push or pop, think it this way, if you know your cookie jar would soon run out of space what will you do. You will get a new jar. Now, how do you decide what size of jar you want ? Well here the answer is double if you want to go bigger and 1/4 if you want to go smaller. Getting a new jar is analogous to creating a new integer array object. You then move all your cookies from small to bigger jar and discard the jar. Similarly, copy each item from the old array to new array.

This answer could be rather long and I know it would be cheating if I pass on the source code to you, but as I understand you are really willing to see how it is to be done and hence you can look up the reference implementation of ArrayList : http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/ArrayList.java

This initially might be intimidating but if you carefully look at methods grow(), ensureCapacity(), indexOf(), clone(), add() you will get a better idea of how it is implemented in java

Upvotes: 3

Related Questions