In this lecture, we'll learn how to implement an UnorderedDynamicArray to hold ints.
So, that means that we will grow the array as we need to as we add elements to the array,
but we don't care what order those elements appear in in the array.
We'll start by looking at the parent class for
both the Unordered and Ordered IntDynamicArrays.
So, this is an abstract class
because there are some methods in here that we don't know how to implement.
We'll leave that to our child classes.
We have an ExpandMultiplyFactor.
So, once the underlying array here gets full,
we're going to need to expand it.
And the way we'll expand it is,
we will double its size each time we need to expand it.
And that has been shown historically to be a reasonable approach.
We don't want to just add one to the array size every time because then,
we'll end up having to expand it all the time,
but we don't want to multiply it by a hundred either
because we can end up wasting lots of memory that way.
So, doubling the size each time we need to expand it is reasonable.
Speaking of that underlying array, here it is.
So, it's an integer array called Items,
and we're going to keep track of the Count as well,
because in this array,
some of those items will be valid and some of those items won't be valid.
And so, we need a way to keep track of which ones are valid and which ones aren't,
and Count is the way we're going to do that.
Here's our constructor.
We create a new array with four elements,
and we set Count to zero because at this point,
the array is empty.
The only property we provide for the array is Count.
And here are those methods that we don't know how to implement here in the parent class.
So, we've made all three of them abstract.
So, we're going to be able to add something to our IntDynamicArray,
we're going to be able to remove something from our IntDynamicArray,
and we'll be able to find the IndexOf a particular item in our IntDynamicArray.
And each of the child classes,
both of the child classes,
will implement those three methods in different ways.
Clearing out the array is a very straightforward operation.
All we have to do is set Count to zero which indicates
that there are now no valid elements in the array.
Of course, the elements in the array are holding whatever values they used to hold,
but we don't care.
There's always bits in elements of an array,
and we're indicating that none of those values are valid at this point.
The last public method we have in the parent class is
the ToString method that just converts
the IntDynamicArray to a string of comma-separated values.
We do have one protected method and that protected method expands the array.
So, if in fact the array is full and we want to add an item to it,
we need to make it bigger.
Now, we know that once we've created an array object,
we can't actually increase the size of that array object.
So, here's what we do.
We create a new array called newItems,
and we make the size of the new array the size of
the current array multiplied by that multiply factor.
So now, we have newItems,
an array of twice as many elements as the current array of items.
Now, we copy everything from the items array into the newItems array.
And finally, we change items to refer to newItems.
So, because arrays is a reference site,
we can just change the reference for our items
array to be a reference to that new array that we created.
In the old array, we'll just get garbage collected
whenever the garbage collector decides to collect the garbage.
That's it for the parent class.
Let's look at the child class for an Unordered IntDynamicArray.
As you can see, I've made it to child class of that parent class.
I have a constructor that just calls the constructor for the parent class.
And here are those abstract methods.
So, the first one is adding an item to the Unordered IntDynamicArray.
The first thing we have to check for is whether or not we need to expand the array.
So, if Count, the number of valid values in the array,
is equal to the size of the array,
that means we don't have any room to add another item to the array,
so we need to expand it,
which is what we do here.
Now that we've expanded the array,
we add the item at items count,
and we increment Count,
and you should go do an in-video quiz about this.
Okay, so Count keeps track of the IndexOf the next place we're going to add an item.
So, if you think about this,
if Count is four,
then the indices for the valid elements in the array are zero,
one, two, and three.
So, items count is the next available slot for a valid item when we need to add one.
It's also useful that Count happens to be the number of elements in the array as well.
So, we're using Count for double duty here and that's really handy.
The next method is to remove an element from the array.
So, the first thing we do is look for it,
and we'll talk about the IndexOf method soon,
but if IndexOf returns negative one for the itemLocation,
then the item we were looking for doesn't appear in the array,
so we return false.
Because we haven't removed it,
it wasn't there in the first place.
Otherwise, itemLocation is the location of the element that we're removing,
so we can just copy the element at the very end of
the valid elements in the array into that location instead,
and then we decrement Count and return true.
The last method in the Unordered IntDynamicArray class is IndexOf.
So, we need to look for a particular item.
This is pretty straightforward because this is an Unordered IntDynamicArray.
The only thing we can do is start at the beginning and look for
the item we're looking for until we either find it or we get to the end.
So, this for loop locks that array.
And if in fact the current element we're looking at is the item we're looking for,
then we return i,
the IndexOf that element that we just found.
And if we look through all of the valid elements in the array and we don't find the item,
then we return negative one because we didn't find it in the array.
So, that is
both the parent class IntDynamicArray and the child class Unordered IntDynamicArray
for an Unordered array that can grow as we need it to.
To recap, in this lecture,
we learned how we can implement a parent class for a Dynamic Array of ints,
and we also saw how we could implement the child class for in an UnorderedDynamicArray.