• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Implementing ArrayList class manually

 
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Implemented the ensureCapacity(int) method:

 
Mansukhdeep Thind
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I tried my hand at implementing the addAll(Collection <? extends T>) method:



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.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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:



No exceptions now. Works like a charm.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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:



Now it shall only increase the capacity, otherwise the capacity will remain unchanged. Is it correct now Winston?
 
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mansukhdeep Thind wrote:




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
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeff Verdegan wrote:

Mansukhdeep Thind wrote:




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:



Better now?
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The addAll(indexPos, Collection<? extends T>) method :



Did I miss anything? Any scope for improvement?
 
Mansukhdeep Thind
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Is this close to what you wanted Jeff:

 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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:All he's saying is that you can make it more efficient by simply copying elements once, viz: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
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well , I would stick to my first implementation. An update Winston, I got a job.

 
Mansukhdeep Thind
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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:
Winston
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I got really close to what you just wrote. Didn't I Winston?
 
Mansukhdeep Thind
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Not that there is any thread‑safety to its Sun/Oracle counterpart either.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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++?
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic