Implementing ArrayList class manually

[Mansukhdeep Thind]

Implemented the ensureCapacity(int) method:

/**
	 * Increases the capacity of this ArrayList instance, if necessary, to ensure that 
	 * it can hold at least the number of elements specified by the minimum capacity argument.
	 * @param minimumCapacity - the minimum number of elements which the list should be able to hold
	 */
	public final void ensureCapacity(int minimumCapacity){
		values = resizeArray(values, minimumCapacity);		
	}

[Mansukhdeep Thind]

I tried my hand at implementing the addAll(Collection <? extends T>) method:

/**
	 * Appends all of the elements in the specified collection to the end of this list, in the order 
	 * that they are returned by the specified collection's Iterator. The behavior is undefined if 
	 * the collection is dynamically changed when it is being appended.
	 * @param collection - collection to be appended to end of the list
	 * @return boolean true if the list changed as a result of this call
	 * @throws NullPointerException if collection is null
	 */
	public boolean addAll(Collection <? extends T> collection) {

		T [] collectionArray = (T[]) new Object[collection.size()];

		
		collectionArray = collection.toArray(collectionArray);

			for(int i = 0; i < collection.size(); i++){
				values[size] = collectionArray[i];
				size++;
			}



			return true;
		

	}

It is functioning properly. One doubt though. The API documentation says that it throws NullPointerException if collection is null. Am I supposed to cater for that in my method too? I ask this because NullPointerException is a Run time type, unchecked exception.

[Winston Gutkowski]

Mansukhdeep Thind wrote:Implemented the ensureCapacity(int) method:

Which doesn't do what you document it to (which is not necessarily wrong; just inconsistent). What if minimumCapacity is less than values.length?

Winston

[Winston Gutkowski]

Mansukhdeep Thind wrote:I tried my hand at implementing the addAll(Collection <? extends T>) method:

Again, you're waaay overthinking this ... and you've still got it wrong.
1. There's absolutely no need to convert the collection to an array.
2. You already have a perfectly good method for adding elements, so why not use it?

It is functioning properly.

Then I'd say your testing isn't up to snuff. Try it with a collection that breaks the array capacity.

One doubt though. The API documentation says that it throws NullPointerException if collection is null. Am I supposed to cater for that in my method too? I ask this because NullPointerException is a Run time type, unchecked exception.

That latter point is irrelevant. Basically, there's nothing that says you have to slavishly follow the superclass method, but if you vary from it you must document the fact. There's also a difference between semantics and intent: changing things like how you do error-checking is probably fine, but you should be very careful not to change the intent of a superclass method; otherwise you may cause clients problems because they've assumed that your method works as documented for the interface. Once again, whatever you decide, DOCUMENT IT.

Winston

[Mansukhdeep Thind]

Winston Gutkowski wrote:

Mansukhdeep Thind wrote:Implemented the ensureCapacity(int) method:

Which doesn't do what you document it to (which is not necessarily wrong; just inconsistent). What if minimumCapacity is less than values.length?

Winston

Why would someone call this method to reduce the capacity? It is meant to facilitate the increase of the list's current capacity. If I say ensureCapacity(100), it shall increase the capacity to 100. I don't understand how is it inconsistent with what I have documented it to do. The documentation clearly says "Increases.....".

[Mansukhdeep Thind]

Winston Gutkowski wrote:

Mansukhdeep Thind wrote:I tried my hand at implementing the addAll(Collection <? extends T>) method:

Again, you're waaay overthinking this ... and you've still got it wrong.
1. There's absolutely no need to convert the collection to an array.
2. You already have a perfectly good method for adding elements, so why not use it?

Yes, I missed the part to grow the array in case size == values.length? Anyways, that is besides the point here. How do I re-use the add(T) method to add the elements of the passed collection to this list? That method only adds a single object of type T to the end of the list. How to get that object from the passed collection reference? The iterator.next() runs into an infinite loop if I try and retrieve elements of the collection one by one. Why is that happening?

EDIT: Here is the rectified addAll(Collection <? extends T>) method Winston:

/**
	 * Appends all of the elements in the specified collection to the end of this list, in the order 
	 * that they are returned by the specified collection's Iterator. The behavior is undefined if 
	 * the collection is dynamically changed when it is being appended.
	 * @param collection - collection to be appended to end of the list
	 * @return boolean true if the list changed as a result of this call
	 * @throws NullPointerException if collection is null
	 */
	public boolean addAll(Collection <? extends T> collection) {

		Iterator<? extends T> iterator = (Iterator<? extends T>) collection.iterator();
		for(int i = 0; i < collection.size(); i++){
			add(iterator.next());
		}
		return true;


	}

No exceptions now. Works like a charm.

[Winston Gutkowski]

Mansukhdeep Thind wrote:The documentation clearly says "Increases.....".

But you haven't enforced it. Right now it's just a "resize" method - which you've already written.

Winston

[Mansukhdeep Thind]

Winston Gutkowski wrote:

Mansukhdeep Thind wrote:The documentation clearly says "Increases.....".

But you haven't enforced it. Right now it's just a "resize" method - which you've already written.

Winston

Right, so does this look better:

/**
	 * Increases the capacity of this ArrayList instance, if necessary, to ensure that 
	 * it can hold at least the number of elements specified by the minimum capacity argument.
	 * @param minimumCapacity - the minimum number of elements which the list should be able to hold
 
	 */
	public final void ensureCapacity(int minimumCapacity){
		if(minimumCapacity > values.length){
			values = resizeArray(values, minimumCapacity);
		}
			

	}

Now it shall only increase the capacity, otherwise the capacity will remain unchanged. Is it correct now Winston?

[Jeff Verdegan]

Mansukhdeep Thind wrote:

		Iterator<? extends T> iterator = (Iterator<? extends T>) collection.iterator();
		for(int i = 0; i < collection.size(); i++){
			add(iterator.next());
		}

Is that how you always use an Iterator? That's kind of messed up.

1. You should be using a foreach loop, rather than an explicit Iterator.

2. Even if you do use an explicit iterator, you shouldn't be counting up to size().

3. Even if you're counting up to size(), there's no need to call size() on every iteration.

[Jeff Verdegan]

Mansukhdeep Thind wrote:
values = resizeArray(values, minimumCapacity);

Why are you passing values as an argument to that method? Do you sometimes pass a different array?

[Winston Gutkowski]

Jeff Verdegan wrote:Why are you passing values as an argument to that method? Do you sometimes pass a different array?

That was my suggestion. Basically, it allows the method to be used for both resizing and initialization.

Winston

[Jeff Verdegan]

Winston Gutkowski wrote:

Jeff Verdegan wrote:Why are you passing values as an argument to that method? Do you sometimes pass a different array?

That was my suggestion. Basically, it allows the method to be used for both resizing and initialization.

Winston

You mean the client can pass in an array to use? That doesn't sound good. Or am I misunderstanding what you mean by initialization?

[Winston Gutkowski]

Mansukhdeep Thind wrote:Right, so does this look better:

Much. When you're writing methods, try to see if you can re-use code.

Winston

[Mansukhdeep Thind]

Jeff Verdegan wrote:

Mansukhdeep Thind wrote:

		Iterator<? extends T> iterator = (Iterator<? extends T>) collection.iterator();
		for(int i = 0; i < collection.size(); i++){
			add(iterator.next());
		}

Is that how you always use an Iterator? That's kind of messed up.

1. You should be using a foreach loop, rather than an explicit Iterator.

2. Even if you do use an explicit iterator, you shouldn't be counting up to size().

3. Even if you're counting up to size(), there's no need to call size() on every iteration.

Yes Jeff, that is indeed messed up. Here you go:

/**
	 * Appends all of the elements in the specified collection to the end of this list, in the order 
	 * that they are returned by the specified collection's Iterator. The behavior is undefined if 
	 * the collection is dynamically changed when it is being appended.
	 * @param collection - collection to be appended to end of the list
	 * @return boolean true if the list changed as a result of this call
	 * @throws NullPointerException if collection is null
	 */
	public boolean addAll(Collection <? extends T> collection) {

		Iterator<? extends T> iterator = (Iterator<? extends T>) collection.iterator();
		while(iterator.hasNext()){
			add(iterator.next());			
		}
		return true;


	}

Better now?

[Winston Gutkowski]

Jeff Verdegan wrote:You mean the client can pass in an array to use? That doesn't sound good. Or am I misunderstanding what you mean by initialization?

You have to go back about 30 posts.

The problem with arrays in a generic class like this is that they have to be cast at least once, and a method that takes a previous array and a size allows it to be used for initialization (if the passed array is null) or resizing if there is a "previous" array; hence, one - and only one - cast, and a consistent method for all forms of allocation. It can also be stuck in a utility class.

Winston

[Jeff Verdegan]

Winston Gutkowski wrote:

Jeff Verdegan wrote:You mean the client can pass in an array to use? That doesn't sound good. Or am I misunderstanding what you mean by initialization?

You have to go back about 30 posts.

No thanks. I'll just trust you on this one.

[Mansukhdeep Thind]

Jeff Verdegan wrote:

Winston Gutkowski wrote:

Jeff Verdegan wrote:You mean the client can pass in an array to use? That doesn't sound good. Or am I misunderstanding what you mean by initialization?

You have to go back about 30 posts.

No thanks. I'll just trust you on this one.

[Mansukhdeep Thind]

The addAll(indexPos, Collection<? extends T>) method :

/**
	 * Appends all of the elements in the specified collection starting with the specified
	 * index position, in the order that they are returned by the specified collection's Iterator. 
	 * Shifts the elements to right by value equal to size of the collection being inserted.
	 * @param index - starting position where the first element will be inserted
	 * @param collection - the collection containing the elements to be inserted 
	 * @return - boolean true if the list changed as a result of this call 
	 * @throws IllegalArgumentException if index passed is negative or more than capacity of list
	 */
	public boolean addAll(int indexPos, Collection <? extends T> collection) throws IllegalArgumentException{

		Iterator<? extends T> iterator = collection.iterator();

		while (iterator.hasNext()){
			add(indexPos, iterator.next());
			indexPos++;
		}

		return true;

	}

Did I miss anything? Any scope for improvement?

[Mansukhdeep Thind]

Are you asking why did I put indexPos++ inside the loop?

EDIT: Why can't I see your post Jeff? I just saw it about a minute ago.

[Jeff Verdegan]

Here's one place where I wouldn't take the simplest approach. If the collection you're adding has M elements, and there are N elements in your existing list at or after indexPos, you'll be doing M * N moves, just moving the same N elements M times. You could just move them once, changing that part of this method from O(M*N) to simply O(N).

[Jeff Verdegan]

Mansukhdeep Thind wrote:Are you asking why did I put indexPos++ inside the loop?

EDIT: Why can't I see your post Jeff? I just saw it about a minute ago.

I removed my post because I didn't pay enough attention to what you were doing, so my comment was irrelevant.

[Mansukhdeep Thind]

Jeff Verdegan wrote:

Mansukhdeep Thind wrote:Are you asking why did I put indexPos++ inside the loop?

EDIT: Why can't I see your post Jeff? I just saw it about a minute ago.

I removed my post because I didn't pay enough attention to what you were doing, so my comment was irrelevant.

Smart move. Caught red handed though.

[Mansukhdeep Thind]

Jeff Verdegan wrote:Here's one place where I wouldn't take the simplest approach. If the collection you're adding has M elements, and there are N elements in your existing list at or after indexPos, you'll be doing M * N moves, just moving the same N elements M times. You could just move them once, changing that part of this method from O(M*N) to simply O(N).

Not sure what you are suggesting here? Do you want me to shift all the elements to the right of the indexPos at once by number of positions equal to size of the collection? And then insert the collection.

[Jeff Verdegan]

Mansukhdeep Thind wrote:

Jeff Verdegan wrote:Here's one place where I wouldn't take the simplest approach. If the collection you're adding has M elements, and there are N elements in your existing list at or after indexPos, you'll be doing M * N moves, just moving the same N elements M times. You could just move them once, changing that part of this method from O(M*N) to simply O(N).

Not sure what you are suggesting here? Do you want me to shift all the elements to the right of the indexPos at once by number of positions equal to size of the collection? And then insert the collection.

Yes. Exactly that.

[Mansukhdeep Thind]

Is this close to what you wanted Jeff:

/**
	 * Appends all of the elements in the specified collection starting with the specified
	 * index position, in the order that they are returned by the specified collection's Iterator. 
	 * Shifts the elements to right by value equal to size of the collection being inserted.
	 * @param index - starting position where the first element will be inserted
	 * @param collection - the collection containing the elements to be inserted 
	 * @return - boolean true if the list changed as a result of this call 
	 * @throws IllegalArgumentException if index passed is negative or more than capacity of list
	 */
	public boolean addAll(int indexPos, Collection <? extends T> collection)
	    throws IllegalArgumentException
	{
		Iterator<? extends T> iterator = collection.iterator();

		size = size + collection.size();

		if( size >= values.length){
			growArray();
		}

		
		for(int i = indexPos; i <= size ; i++){
			values[i+collection.size()] = values[i];			
			values[i] = iterator.hasNext()?iterator.next():values[i+collection.size()];			
		}


		return true;

	}

[Winston Gutkowski]

Mansukhdeep Thind wrote:Is this close to what you wanted Jeff:

Don't think so.

First: what Jeff is suggesting is an efficiency upgrade; so probably only worth thinking about once you have a working method.
And to me by far the simplest method is:

public boolean addAll(int indexPos, Collection <? extends T> collection)
   throws IllegalArgumentException
{
   // any checks you think you need
   for(T value : collection) {
      add(indexPos++, value);
   }
   return true;
}

All he's saying is that you can make it more efficient by simply copying elements once, viz:

public boolean addAll(int indexPos, Collection <? extends T> collection)
   throws IllegalArgumentException
{
   // any checks you think you need
   int cSize = collection.size();
   if (cSize == 0)
      return false;
   int newSize = Math.max(values.length, size + cSize);
   T[] newArray = resizeArray(null, newSize);
   System.arrayCopy(values, 0, newArray, 0, indexPos);
   int element = indexPos;
   for(T value : collection) {
      newArray[element++] = value;
   }
   if (indexPos < size)
      System.arrayCopy(values, indexPos, newArray, element, size - indexPos);
   values = newArray;
   size += cSize;
   return true;
}

As always, it's just one possibility, and it relies on 'collection's size not changing while the method is running, but reuse existing code wherever you can.

Winston

[Winston Gutkowski]

Actually, there's still a possible inefficiency in what I wrote (yet another reason, if any were needed, not to offer solutions ); I'll leave you to work out why - and it's not obvious.

Winston

[Mansukhdeep Thind]

Well , I would stick to my first implementation. An update Winston, I got a job.

[Mansukhdeep Thind]

Winston Gutkowski wrote:Actually, there's still a possible inefficiency in what I wrote (yet another reason, if any were needed, not to offer solutions ); I'll leave you to work out why - and it's not obvious.

Winston

Well, for that I would first need to understand why you wrote what you just did. I think I would rather pass this one and move on to the next method.

[Winston Gutkowski]

Mansukhdeep Thind wrote:Well, for that I would first need to understand why you wrote what you just did. I think I would rather pass this one and move on to the next method.

I wrote it to illustrate Jeff's point. Resizing your array involves copying elements, so if you add many elements using code designed to add one (which is a perfectly reasonable point to start from), you may be copying the same stuff many times (hence O(n²)).

Furthermore, the method above is generally used to insert elements in the middle of your array, so even if you resize first, you still need to copy the "end" portion again. However, this is still far better than doing multiple resizes, so a simplified version might look something like:

public boolean addAll(int indexPos, Collection <? extends T> collection)
   throws IllegalArgumentException
{
   // any checks you think you need
   int cSize = collection.size();
   if (cSize == 0)
      return false;
   ensureCapacity(size + cSize);
   if (indexPos < size)
      System.arrayCopy(values, indexPos, values, indexPos + cSize, size - indexPos);
   for(T value : collection) {
      values[indexPos++] = value;
   }
   size += cSize;
   return true;
}

Winston

[Winston Gutkowski]

Mansukhdeep Thind wrote:I think I would rather pass this one and move on to the next method.

Fine. But don't forget it.

Winston

[Mansukhdeep Thind]

I got really close to what you just wrote. Didn't I Winston?

[Mansukhdeep Thind]

Winston Gutkowski wrote:

Mansukhdeep Thind wrote:I think I would rather pass this one and move on to the next method.

Fine. But don't forget it.

Winston

The only way I would have not forgotten it is if I had thought of it in the first place before you or Jeff. You guys catch me by the ear just when I am about to screw up things. I need to learn to do that to myself.

[Winston Gutkowski]

Mansukhdeep Thind wrote:I got really close to what you just wrote. Didn't I Winston?

Not really, because
(a) growArray() doesn't specify a size to grow to.
(b) You're not reusing methods you've already written.
(c) Your loop logic is incredibly tortured. If you want all the elements of a collection, use for-each. And if you're worried about making your method bomb-proof from updates to collection, just clone it first, viz:
collection = new ArrayList<T>(collection);

Winston

[Jeff Verdegan]

Winston Gutkowski wrote: And if you're worried about making your method bomb-proof from updates to collection, just clone it first, viz:
collection = new ArrayList<T>(collection);

That doesn't really protect against collection changing. It just narrows the window a little. The whole class has no thread-safety in it, so I don't see any point in worrying about it here either. In fact, it's impossible to guarantee that collection won't be structurally modified while during addAll() from within this class. We need cooperation from the caller for that.

[Campbell Ritchie]

Not that there is any thread‑safety to its Sun/Oracle counterpart either.

[Winston Gutkowski]

Jeff Verdegan wrote:That doesn't really protect against collection changing. It just narrows the window a little...

True. However, it'll also cause the method to throw an exception quickly, if it does at all.

Winston

[Mansukhdeep Thind]

Jeff Verdegan wrote:

Winston Gutkowski wrote: And if you're worried about making your method bomb-proof from updates to collection, just clone it first, viz:
collection = new ArrayList<T>(collection);

That doesn't really protect against collection changing. It just narrows the window a little. The whole class has no thread-safety in it, so I don't see any point in worrying about it here either. In fact, it's impossible to guarantee that collection won't be structurally modified while during addAll() from within this class. We need cooperation from the caller for that.

Is there NO WAY AT ALL to make this operation atomic Jeff? Can't we somehow achieve a handle on the collection and lock it down when it is passed as an argument to the addAll() method to ensure that the collection does not change when it is being inserted in the list? Why is it impossible? Is it because Java uses pass by value? Would it have been possible in case of C++?