Implementing ArrayList class manually

[Jeff Verdegan]

Mansukhdeep Thind wrote:
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

No. You can't "lock down" an arbitrary object. Mutual exclusion in Java only works when all concerned parties cooperate. If someone passes you a Collection, there's nothing you can do inside your method to force them not to modify that collection.

On the other hand, if they're operating in a multithreaded environment, it's their responsibility to know that your method will be reading their collection and to know if something else they're doing could be writing it, and to add their own mutual exclusion logic to handle it. In short, it's not your problem.

Why is it impossible?

Because Java does not provide a way to say "Nobody can call any methods on this object or access any of its members" for an arbitrary object.

[Winston Gutkowski]

Mansukhdeep Thind wrote:Is there NO WAY AT ALL to make this operation atomic Jeff?

Nope, because it depends entirely on what type of collection was passed and what the caller decides to do with it.

In general, cloning the way I suggested will either return some weakly consistent version of collection, or else it'll throw an exception. If you document it as such, at least it's then the client's own stupid fault if they decide to update it while you're cloning. If you don't clone, you run the risk of elements being added while you're filling your array, which could screw up that logic in ways that are trickier to analyse.

Winston

[Campbell Ritchie]

You can put a lock on the add method (etc) which prevents two threads accessing the add method simultaneously. You can make the lock re-entrant and lock all the add methods, remove, etc, so only one of them can be called at any one time. But the Collection you are loading the elements from is probably not thread‑safe, so there is the possibility that it is added to or removed from while your addAll operation is proceeding.

[Mansukhdeep Thind]

Campbell Ritchie wrote:You can put a lock on the add method (etc) which prevents two threads accessing the add method simultaneously. You can make the lock re-entrant and lock all the add methods, remove, etc, so only one of them can be called at any one time. But the Collection you are loading the elements from is probably not thread‑safe, so there is the possibility that it is added to or removed from while your addAll operation is proceeding.

That's what. Atomicity is what I was thinking of. Anyways, let's move on to the next method. Lets clone () the list.

[Campbell Ritchie]

Why clone? An iterator method would be far more interesting.

[Mansukhdeep Thind]

So you want me to implement Iterable interface for my CustomArrayList class?

[Campbell Ritchie]

Why not? You need to work out how to create the Iterator and a ListIterator, and also how to get it to throw the concurrent modification exception. That won’t be easy.

[Winston Gutkowski]

Mansukhdeep Thind wrote:So you want me to implement Iterable interface for my CustomArrayList class?

Assuming that it implements java.util.List, you don't have any choice because a List is an Iterable.

Campbell Ritchie wrote:You need to work out how to create the Iterator and a ListIterator...

Ugh. Now's there's a dog's breakfast of an interface if there ever was one.

Why couldn't they simply have extended Iterator to provide a direction? I have never, in 12 years, needed to do next() followed by previous(); which is, arguably, not "iteration" at all.

Winston

[Mansukhdeep Thind]

Winston Gutkowski wrote:Why couldn't they simply have extended Iterator to provide a direction? I have never, in 12 years, needed to do next() followed by previous(); which is, arguably, not "iteration" at all.

Winston

I did not understand this statement of yours Winston. What do you mean when you say

extended Iterator to provide a direction..

[Mansukhdeep Thind]

Tried my hand at implementing Iterable interface for my custom list:

/**
	 * Returns an iterator over a set of elements of type T.
	 */
	@Override
	public Iterator<T> iterator() {
		CustomIterator myIterator = new CustomIterator(this);
		return myIterator;
	}

	class CustomIterator implements Iterator<T>{
		private T[] iterable;
		private int currentIndex;

		/**
		 * Constructor that returns the iterator on the list
		 * @param list
		 */
		public CustomIterator(CustomArrayList<T> list) {
			iterable = (T[]) list.values;			
		}

		/**
		 * Returns true if the iteration has more elements.
		 * @return true if the iterator has more elements
		 */
		@Override
		public final boolean hasNext() {
			if(iterable[currentIndex]!=null){				
				return true;
			}
			return false;
		}

		/**
		 * Returns the next element in the iteration.
		 * @return the next element in the iteration
		 * @throws NoSuchElementException - if iteration has no more elements
		 */
		@Override
		public final T next() throws NoSuchElementException{
			if(hasNext()){
				T currentObject = iterable[currentIndex];
				currentIndex++;
				return currentObject;
			}
			return null;
		}

[Jeff Verdegan]

Mansukhdeep Thind wrote:
public final boolean hasNext() {
if(iterable[currentIndex]!=null){
return true;
}
return false;
}

So the only way that you ever don't have a next element is if you're currently pointing to null? Really?

[Mansukhdeep Thind]

Then how come the for-each and the while(hasNext()) are returning perfect results. All the elements are being printed correctly in order. If my hasNext() method is flawed as your say, which it is , then why is there no problem with the printing of the list?

[Jeff Verdegan]

Mansukhdeep Thind wrote:Then how come the for-each and the while(hasNext()) are returning perfect results. All the elements are being printed correctly in order. If my hasNext() method is flawed as your say, which it is , then why is there no problem with the printing of the list?

Don't get defensive. Just answer my question: Is the only way that you ever don't have a next element is if you're currently pointing to null?

As for "returning perfect results," that means either your testing is flawed by virtue of not covering the corner case my question is alluding to, I'm making an incorrect assumption. I'm asking the question to try to find out which it is.

[Mansukhdeep Thind]

Jeff Verdegan wrote:

Mansukhdeep Thind wrote:Then how come the for-each and the while(hasNext()) are returning perfect results. All the elements are being printed correctly in order. If my hasNext() method is flawed as your say, which it is , then why is there no problem with the printing of the list?

Don't get defensive. Just answer my question: Is the only way that you ever don't have a next element is if you're currently pointing to null?

No Jeff. The correct logic would be to check successively if the next element is null or not. Am I thinking correct now?

[Jeff Verdegan]

Mansukhdeep Thind wrote:

Jeff Verdegan wrote:

Mansukhdeep Thind wrote:Then how come the for-each and the while(hasNext()) are returning perfect results. All the elements are being printed correctly in order. If my hasNext() method is flawed as your say, which it is , then why is there no problem with the printing of the list?

Don't get defensive. Just answer my question: Is the only way that you ever don't have a next element is if you're currently pointing to null?

No Jeff. The correct logic would be to check successively if the next element is null or not. Am I thinking correct now?

Current vs. next is a separate issue. Either one can work, depending on how you implement it. Given that your testing works so far, you probably have that right, and from your code, it looks like the index is indicating the item that will be returned on the next call to next(), so I don't think you have that off-by-one error, and that's not what I'm getting at.

Here's another hint: Will there always be at least one null element?

[Mansukhdeep Thind]

Jeff Verdegan wrote: Here's another hint: Will there always be at least one null element?

No Jeff. If the list size becomes equal to its capacity, then we will have no null elements at all. But what's the point? I just modified the methods as follows:

/**
		 * Returns true if the iteration has more elements.
		 * @return true if the iterator has more elements
		 */
		@Override
		public final boolean hasNext() {

			return (currentIndex < size && iterable[currentIndex]!=null);				

		}

		/**
		 * Returns the next element in the iteration.
		 * @return the next element in the iteration
		 * @throws NoSuchElementException - if iteration has no more elements
		 */
		@Override
		public final T next() throws NoSuchElementException {
			return iterable[currentIndex++];
		}

These are also working perfectly.

[Jeff Verdegan]

Mansukhdeep Thind wrote:

Jeff Verdegan wrote: Here's another hint: Will there always be at least one null element?

No Jeff. If the list size becomes equal to its capacity, then we will have no null elements at all. But what's the point? I just modified the methods as follows:

The point is exactly the modification you just made. That's what I was getting it. Your earlier approach that only looked for the next (or current) element being null would throw ArrayIndexOutOfBoundsException if your array was full. I was asking because I didn't know if maybe you always resized before you get full, so that there would in fact always be at least one null at the end. (Although i think it would still be good practice to check for cur matching size, so that your hasNext() is less tightly coupled to your backing store implementation.)

There's another, smaller problem though. Your next() claims to throw NoSuchElementException, but it doesn't. It throws ArrayIndexOutOfBoundsException.

Your testing should include testing error conditions, to make sure that exceptions are thrown when expected, and that they're the correct exceptions.

[Mansukhdeep Thind]

Jeff Verdegan wrote:

Mansukhdeep Thind wrote:

Jeff Verdegan wrote: Here's another hint: Will there always be at least one null element?

No Jeff. If the list size becomes equal to its capacity, then we will have no null elements at all. But what's the point? I just modified the methods as follows:

The point is exactly the modification you just made. That's what I was getting it. Your earlier approach that only looked for the next (or current) element being null would throw ArrayIndexOutOfBoundsException if your array was full. I was asking because I didn't know if maybe you always re-sized before you get full, so that there would in fact always be at least one null at the end. (Although i think it would still be good practice to check for cur matching size, so that your hasNext() is less tightly coupled to your backing store implementation.)

Ohhh.. OK NOW! Some new learning from Jeff Verdegan. I just realized the meaning of the last 4 posts. Since the backing array is growing as and when size becomes equal to capacity, there will always be at least 1 null element. Hence, the previous logic worked too. And obviously, this is the correct way it should have been done in the first place, regardless of the fact that whether we are growing the array or not, just to be safe.

Jeff Verdegan wrote:There's another, smaller problem though. Your next() claims to throw NoSuchElementException, but it doesn't. It throws ArrayIndexOutOfBoundsException.

Your testing should include testing error conditions, to make sure that exceptions are thrown when expected, and that they're the correct exceptions.

This is yet another thing on my to do list Jeff. I need to learn how to judge which exceptions will be thrown and when to throw them. Is there a tutorial for this? Or is it sheer experience of working with the language that helps one gauge it?

[Winston Gutkowski]

Mansukhdeep Thind wrote:I did not understand this statement of yours Winston. What do you mean when you say

extended Iterator to provide a direction..

It's simply an opinion, but I think that ListIterator is badly thought out and bloated for 99% of everyday use. It's rare for me to slag off Sun's designers but, in this case, I think they got it wrong.

An Iterator that works backwards? No problem. And, for a List, one that takes a start point I can also understand. But one that works in both directions at once? As I said above: very rare - and it's arguable then whether it even qualifies as an "Iterator".

Somewhere in between you have a DirectionalIterator (unfortunately, not defined by Sun) - ie, an Iterator that has a "direction" - you can can even implement one that allows you to change direction, but it only works in one direction at a time.

Indeed, that's how I generally design a ListIterator (if I need to).

Winston

[Jeff Verdegan]

Mansukhdeep Thind wrote:Since the backing array is growing as and when size becomes equal to capacity, there will always be at least 1 null element.

So, if capacity is 10 (array.length is 10), then when you add the 10th element, so that now all the array slots are filled up, you resize the array before you return from add()? If so, then, yes, I was mistaken and you don't have to check for size == capacity. However, if you return from add() without resizing, then you will not have a null element.

This is yet another thing on my to do list Jeff. I need to learn how to judge which exceptions will be thrown and when to throw them. Is there a tutorial for this? Or is it sheer experience of working with the language that helps one gauge it?

You should throw an exception when something outside the expected "happy path" execution occurs. If something that's required to happen fails to happen, throw an exception (unless you can make things right in the code). The exception name, package, and class hierarchy should match the problem.

In the case of java.util.Collection, calling Iterator.next() when there are no more elements throws NoSuchElementException. That is an exception that was created specifically to mean "there are no more elements here, and you should know that, but you tried to get the next one anyway." It was actually created for Enumeration, but that's just an early form of Iterator. The "and you should know that" part is the reason its an unchecked exception.

In your case, ArrayIndexOutOfBoundsException might not necessarily be wrong, if your ArrayList stands alone, rather than being part of a collection library. In the case of java.util.Collection, however, ArrayIndexOutOfBoundsException doesn't make sense, because not all Collections are backed by arrays. So a general-purpose "this Collection has no more elments" exception was defined, to be thrown when you try to go past the end of any Collection. Like so many other things you've been hit with lately, it's about decoupling interface from implementation.

[Jeff Verdegan]

Winston Gutkowski wrote:you can can even implement one that allows you to change direction, but it only works in one direction at a time.

If I can change direction, how is that any more "one direction at a time" then just calling next(); previous(); next(); previous();? Are you talking about only being allowed to change direction after iterating the entire list?

I don't know that I think the current ListIterator is poorly designed, but, like you, I don't recall the last time I actually used one so I could call previous().

[Winston Gutkowski]

Jeff Verdegan wrote:If I can change direction, how is that any more "one direction at a time" then just calling next(); previous(); next(); previous();? Are you talking about only being allowed to change direction after iterating the entire list?

No, I mean that if you need an Iterator to work in either direction, give it one; don't proliferate methods. Why not just have next()/hasNext() work on the "next" element in whatever direction the Iterator is defined to travel?

Personally, I've always found it the easiest way to implement a ListIterator anyway; and it saves having to remember a load of "implementation-type" specification about how next() and previous() are supposed to work together.

Winston

[Jeff Verdegan]

Winston Gutkowski wrote:

Jeff Verdegan wrote:If I can change direction, how is that any more "one direction at a time" then just calling next(); previous(); next(); previous();? Are you talking about only being allowed to change direction after iterating the entire list?

No, I mean that if you need an Iterator to work in either direction, give it one; don't proliferate methods. Why not just have next()/hasNext() work on the "next" element in whatever direction the Iterator is defined to travel?

So, instead of

next();
previous();
next();

it would be something like

next();
setDirectionReverse();
next();
setDirectionForward();
next():

?

[Mansukhdeep Thind]

Jeff Verdegan wrote:

Mansukhdeep Thind wrote:Since the backing array is growing as and when size becomes equal to capacity, there will always be at least 1 null element.

So, if capacity is 10 (array.length is 10), then when you add the 10th element, so that now all the array slots are filled up, you resize the array before you return from add()? If so, then, yes, I was mistaken and you don't have to check for size == capacity. However, if you return from add() without resizing, then you will not have a null element.

Regardless which one I choose to implement, I learned a new thing. I shall stick to the modified version. Loose coupling, as you said, should be the aim.

Jeff Verdegan wrote:

Mansukhdeep Thind wrote:This is yet another thing on my to do list Jeff. I need to learn how to judge which exceptions will be thrown and when to throw them. Is there a tutorial for this? Or is it sheer experience of working with the language that helps one gauge it?

You should throw an exception when something outside the expected "happy path" execution occurs. If something that's required to happen fails to happen, throw an exception (unless you can make things right in the code). The exception name, package, and class hierarchy should match the problem.

In the case of java.util.Collection, calling Iterator.next() when there are no more elements throws NoSuchElementException. That is an exception that was created specifically to mean "there are no more elements here, and you should know that, but you tried to get the next one anyway." It was actually created for Enumeration, but that's just an early form of Iterator. The "and you should know that" part is the reason its an unchecked exception.

In your case, ArrayIndexOutOfBoundsException might not necessarily be wrong, if your ArrayList stands alone, rather than being part of a collection library. In the case of java.util.Collection, however, ArrayIndexOutOfBoundsException doesn't make sense, because not all Collections are backed by arrays. So a general-purpose "this Collection has no more elments" exception was defined, to be thrown when you try to go past the end of any Collection. Like so many other things you've been hit with lately, it's about decoupling interface from implementation.

So how would I throw the NoSuchElementException then Jeff? Something like this:

/**
		 * Returns the next element in the iteration.
		 * @return the next element in the iteration
		 * @throws NoSuchElementException - if iteration has no more elements
		 */
		@Override
		public final T next() throws NoSuchElementException {
			if(iterable[currentIndex] != null){
				return iterable[currentIndex++];
			}
			else{
				throw new NoSuchElementException("No further elements exist in the list.");
			}
			//return iterable[currentIndex++];
		}

Is this the correct way?

[Jeff Verdegan]

That's one way. But you're forgetting to use your own methods again.

What's the logic of next()? "If the list has a next element, return it, otherwise, throw an exception."

[Winston Gutkowski]

Jeff Verdegan wrote:it would be something like

next();
setDirectionReverse();
next();
setDirectionForward();
next():

?

You've got it. My DirectionalIterator simply adds a nextIndex() method (already defined in ListIterator) to the Iterator spec, and I also have a TwoWayIterator (not wild about the name though) that further adds a Direction enum and get/setDirection() methods.

The idea is that the first one is for iterators that have their direction set at construction time, and the second is a building block for a ListIterator as well as being an Iterator that can simply "change direction". I've considered writing a JSR for it, but I'm not sure of the procedure.

Winston

[Campbell Ritchie]

That might be better design than ListIterator, but the List interface has a listIterator() method which returns a ListIterator, so you are stuck with hasPrevious() and previous().

[Winston Gutkowski]

Campbell Ritchie wrote:That might be better design than ListIterator, but the List interface has a listIterator() method which returns a ListIterator, so you are stuck with hasPrevious() and previous().

True, but what if the listIterator() methods returned a DirectionalIterator instead? If ListIterator was defined as an extension of DirectionalIterator, you wouldn't be breaking any existing code; and whether or not people creating their own ListIterator want it to also extend TwoWayIterator would be entirely up to them.

Like I said, the main reason I use it is to rationalize the business of implementing ListIterator for myself, but I reckon it could also make the business of implementing Lists simpler and more flexible.

Winston

[Mansukhdeep Thind]

Jeff Verdegan wrote:That's one way. But you're forgetting to use your own methods again.

What's the logic of next()? "If the list has a next element, return it, otherwise, throw an exception."

Yeah,already changed it Jeff.

/**
		 * Returns the next element in the iteration.
		 * @return the next element in the iteration
		 * @throws NoSuchElementException - if iteration has no more elements
		 */
		@Override
		public final T next() throws NoSuchElementException {
			if(hasNext()){
				return iterable[currentIndex++];
			}
			else{
				throw new NoSuchElementException("No further elements exist in the list.");
			}
			//return iterable[currentIndex++];
		}

But if I try and write this using the ternary operator in a single statement Jeff, it throws a casting issue. Is this the shortest, most concise form possible, or can it be further reduced?

[Mansukhdeep Thind]

Now, after reading all this fuss created about the ListIterator and Winston's terming it as a dog's breakfast, I am having second second thoughts whether I should go ahead and implement it at all?

[Winston Gutkowski]

Mansukhdeep Thind wrote:Now, after reading all this fuss created about the ListIterator and Winston's terming it as a dog's breakfast, I am having second second thoughts whether I should go ahead and implement it at all?

Like I said: you don't have any choice. My post was simply a rant about ListIterator.

It's possible that, like me, you may find it easier to think of a ListIterator as an extension to an Iterator that has a "direction" and implement it that way - ie, exactly the way Jeff described it:

next() = setDirection(FORWARDS) + getNextElement()

previous() = setDirection(BACKWARDS) + getNextElement()

but it's entirely up to you.

Winston

[Mansukhdeep Thind]

The remove() method has been marked as an optional operation. What does that mean? It says

Removes from the underlying collection the last element returned by the iterator (optional operation).

What is the meaning of optional? Can I get away without implementing it?

[Winston Gutkowski]

Mansukhdeep Thind wrote:What is the meaning of optional? Can I get away without implementing it?

Sure. The usual way is to simply have it throw UnsupportedOperationException.

Winston

[Campbell Ritchie]

As Winston says, you have no choice.

[Jeff Verdegan]

Winston Gutkowski wrote:
You've got it. My DirectionalIterator simply adds a nextIndex() method (already defined in ListIterator) to the Iterator spec, and I also have a TwoWayIterator (not wild about the name though) that further adds a Direction enum and get/setDirection() methods.

The idea is that the first one is for iterators that have their direction set at construction time, and the second is a building block for a ListIterator as well as being an Iterator that can simply "change direction". I've considered writing a JSR for it, but I'm not sure of the procedure.

I gotta admit, I really don't see what the benefit is to this approach. It's not like next() vs. previous() is a complex concept to get one's head around. What's the difference between calling setDirection(REVERSE) ; next(); and just calling previous();? What do we gain by making "current direction" part of the state of the iterator rather than just implied by the method call? I think I'm missing some key point somewhere.

[Mansukhdeep Thind]

Winston Gutkowski wrote:

Mansukhdeep Thind wrote:What is the meaning of optional? Can I get away without implementing it?

Sure. The usual way is to simply have it throw UnsupportedOperationException.

Winston

Like this:

/**
		 * Removes from the underlying collection the last element returned by the iterator (optional operation). 
		 * This method can be called only once per call to next. The behavior of an iterator is unspecified 
		 * if the underlying collection is modified while the iteration is in
		 *  progress in any way other than by calling this method.
		 *  @throws UnsupportedOperationException - if the iterator does not support remove operation 
		 */

		@Override
		public final void remove() {
			throw new UnsupportedOperationException("Operation is not supported.");

		}

Is that it?

[Jeff Verdegan]

Yup.

You might choose to put a bit more detail in the message, such as which class and method.

throw new UnsupportedOperationException("The remove() method is not supported in the Iterator for com.mansukhdeep.ArrayList");

Some may say that's redundant, since the stack trace contains all that. Others may say it's useful to have it self-contained in the exception's message. It's a judgment call, and pretty much comes down to personal preference. I'm just throwing it out there as something for you to keep in mind.

[Mansukhdeep Thind]

Campbell Ritchie wrote:As Winston says, you have no choice.

I just went through the documentation of the ListIterator interface. I don't see any specific thing that I can't do with what I have currently as my public APIs. Why do I need to implement this interface if it does not serve any particular purpose at all? Can you give an example of some use case which can not be tackled by existing APIs and the Iterator functionality already implemented, except for traversal in reverse direction, which I think is more or less useless? Isn't it Campbell?

[Jeff Verdegan]

Mansukhdeep Thind wrote:

Campbell Ritchie wrote:As Winston says, you have no choice.

I just went through the documentation of the ListIterator interface. I don't see any specific thing that I can't do with what I have currently as my public APIs. Why do I need to implement this interface if it does not serve any particular purpose at all? Can you give an example of some use case which can not be tackled by existing APIs and the Iterator functionality already implemented, except for traversal in reverse direction, which I think is more or less useless? Isn't it Campbell?

ListIterator adds backward traversal and the ability to add an element during iteration. I don't know if I've ever used either one of those, but regardless of whether you or I or Campbell or Winston think they're useful, apparently somebody did at one point, and so now, whether we think they're useful or not, if we're implementing java.util.List, we have no choice but to provide implementations for those methods. (Of course, those implementations can throw UnsuppportedOperationException, so it's not required that they actually work, only that they're present.)

[Mansukhdeep Thind]

Jeff Verdegan wrote:Yup.

You might choose to put a bit more detail in the message, such as which class and method.

throw new UnsupportedOperationException("The remove() method is not supported in the Iterator for com.mansukhdeep.ArrayList");

Some may say that's redundant, since the stack trace contains all that. Others may say it's useful to have it self-contained in the exception's message. It's a judgment call, and pretty much comes down to personal preference. I'm just throwing it out there as something for you to keep in mind.

It is good that you bring such things up now and then Jeff. Keeping things organized and following the correct practices does help in the long run.