aspose file tools*
The moose likes Beginning Java and the fly likes Implementing ArrayList class manually Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Implementing ArrayList class manually" Watch "Implementing ArrayList class manually" New topic
Author

Implementing ArrayList class manually

Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

As soon as I wrote extends List<T> and hit return key, it threw a lot of naming clashes with the already implemented methods. It says that return types do not match. How to overcome this duplication issue Jeff? There is a method with the same name that I have implemented, say public final boolean add(T) and implementing List<T> also requires us to implement it. So, do I change the return types of all already the implemented methods which have naming clashes due to distinct return types from those specified in the List<T> interface? What to do?


~ Mansukh
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:As soon as I wrote extends List<T> and hit return key, it threw a lot of naming clashes with the already implemented methods. It says that return types do not match. How to overcome this duplication issue Jeff?


If you're exending class or interface X, then any public or protected methods you have with the same signature as X must have the same return type as X's version, or a subtype. There's no way around that, which is a good thing.

If I declare a variable to be of type List, I might get back a MansukhdeepArrayList and not even know it. All I know and care about is that I have a List, so if List.foo() returns int, then whatever concrete List implementation I get, including MansukhdeepArrayList, better return int from its foo() method, not long or double or boolean or void or JPanel.

So, do I change the return types of all already the implemented methods which have naming clashes due to distinct return types from those specified in the List<T> interface?


If you want to implement or extend List, then yes. Remember implements and extends represent inheritance, which is an IS-A relationship, and if you're going to say, "My class IS-A List," then your class has to behave like List promises to behave.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:As soon as I wrote extends List<T> and hit return key, it threw a lot of naming clashes with the already implemented methods. It says that return types do not match. How to overcome this duplication issue Jeff?


If you're exending class or interface X, then any public or protected methods you have with the same signature as X must have the same return type as X's version, or a subtype. There's no way around that, which is a good thing.

If I declare a variable to be of type List, I might get back a MansukhdeepArrayList and not even know it. All I know and care about is that I have a List, so if List.foo() returns int, then whatever concrete List implementation I get, including MansukhdeepArrayList, better return int from its foo() method, not long or double or boolean or void or JPanel.


OK

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:So, do I change the return types of all already the implemented methods which have naming clashes due to distinct return types from those specified in the List<T> interface?


If you want to implement or extend List, then yes. Remember implements and extends represent inheritance, which is an IS-A relationship, and if you're going to say, "My class IS-A List," then your class has to behave like List promises to behave.


So the only parts of a method I would need to change would be the return types in the declaration and return the respective types from inside the methods. That should do it. Correct?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:So the only parts of a method I would need to change would be the return types in the declaration and return the respective types from inside the methods. That should do it. Correct?


In order to satisfy the compiler, yes, that's all you'll have to change.

However, if you're changing the return type, you're also changing the semantics of the returned value. In order to satisfy the documented behavior, you can't just return any old value of the appropriate type. You'll have to make sure that the value you return matches the documented semantics.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:So the only parts of a method I would need to change would be the return types in the declaration and return the respective types from inside the methods. That should do it. Correct?


In order to satisfy the compiler, yes, that's all you'll have to change.

However, if you're changing the return type, you're also changing the semantics of the returned value. In order to satisfy the documented behavior, you can't just return any old value of the appropriate type. You'll have to make sure that the value you return matches the documented semantics.


OK. So what needs to be changed are :

a) declaration return type

b) return value inside the method, and

c) documentation needs to be in line with what the methods do

Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Yes.

For the documentation, if you put nothing there, then javadoc will provide a link to the parent's docs. Again, judgment call for you.

Of course, if your implementation does anything special that's worth noting--such is it's O(N) when the general case is O(N^2) or vice versa, or anything else that might surprise a user of the method in the general case--then you want to make sure to document that.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7816
    
  21

Jeff Verdegan wrote: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.

No, but the combination of the two can get a bit tricky. Also:
  • It saves duplicating methods for each direction.
  • It allows you to create an Iterator that can change direction. Even with all those darn methods in ListIterator, you can't do that unless you store the "current" direction somewhere. In fact, in order to comply with the requirements of the class, you're pretty much forced to store it anyway.

  • And wouldn't it be nice to have a way of returning the contents of any Collection in reverse sequence, rather than having to define extra methods to do it? To me, an Iterator iterates - why should that mean only forwards?

    To be honest, there's no real reason for DirectionalIterator to have any extra methods at all; you could just plug a Direction into an Iterator. I can also imagine that for a matrix-style dataset like a ResultSet, it could be used to iterate in more than just two directions. Do you want to add extra methods for all of them?

    I think I'm missing some key point somewhere.

    Maybe not, but I've found the concept quite useful myself. Probably just my Machiavellian brain.

    Winston

    Isn't it funny how there's always time and money enough to do it WRONG?
    Articles by Winston can be found here
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Winston Gutkowski wrote:
    Jeff Verdegan wrote: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.

    No, but the combination of the two can get a bit tricky.


    I must be thick, because I don't see how.

    Also:
  • It saves duplicating methods for each direction.


  • Eh? I'm not sure exactly what you're talking about, but among the possibilities I can conceive, I can't imagine that there would be much more or less code duplication in one approach vs. the other.

  • It allows you to create an Iterator that can change direction. Even with all those darn methods in ListIterator, you can't do that unless you store the "current" direction somewhere. In fact, in order to comply with the requirements of the class, you're pretty much forced to store it anyway.



  • So you store a current or you store a direction. Again, I just don't see a benefit. I'm not trying to b ea jerk; I'm honestly trying to figure out what I'm missing.

    And wouldn't it be nice to have a way of returning the contents of any Collection in reverse sequence, rather than having to define extra methods to do it? To me, an Iterator iterates - why should that mean only forwards?


    Not to beat a dead horse, but I still don't see how setting a direction and then using a single next() method ends up with less code than having a separate previous() method. Either way it's about the same amount of work by my reckoning. The only difference is how you arrange it.

    As for iterating backward on any collection, I can see the value in having the base iterator only go one direction. There may be some collections for which it's impossible or impractical or meaningless to iterate backward. Kind of like how we can't rewind just any old InputStream.

    To be honest, there's no real reason for DirectionalIterator to have any extra methods at all; you could just plug a Direction into an Iterator. I can also imagine that for a matrix-style dataset like a ResultSet, it could be used to iterate in more than just two directions. Do you want to add extra methods for all of them?


    Extra methods vs. more code in a single method. I'm still not seeing a clear "simplicity" benefit here.

    Multi-dimensional iteration might start to bring me around, but then again, I don't know that the code for setDir()+next() would be that much shorter or simpler than the code for next() vs. prev() vs. up() vs. down().


    I think I'm missing some key point somewhere.

    Maybe not, but I've found the concept quite useful myself. Probably just my Machiavellian brain.


    Maybe it's one of those things that's hard to understand until you actually need it.
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 7816
        
      21

    Jeff Verdegan wrote:Not to beat a dead horse, but I still don't see how setting a direction and then using a single next() method ends up with less code than having a separate previous() method

    But it's not just next() and previous(), is it? You also have duplicates of hasNext() and nextIndex().

    Maybe it's one of those things that's hard to understand until you actually need it.

    Perhaps. Have you ever had to implement a ListIterator? It's not as simple as it seems, particularly when adds, sets and removes get involved; and quite a bugger to test. I just find that making the changes of direction explicit rather than implicit helps me to rationalize the positioning logic more easily and, like I say, it's a piece of cake to implement a ListIterator on top of a working TwoWayIterator.

    I suspect we're boring the originator of this thread; but thanks for the scepticism - I can see I'm going to have to order my thoughts well before attempting a JSR on the subject.

    Winston
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Jeff Verdegan wrote:Yes.

    For the documentation, if you put nothing there, then javadoc will provide a link to the parent's docs. Again, judgment call for you.

    Of course, if your implementation does anything special that's worth noting--such is it's O(N) when the general case is O(N^2) or vice versa, or anything else that might surprise a user of the method in the general case--then you want to make sure to document that.


    I have incorporated the respective changes for the four methods Jeff- set(int, T) , indexOf(Object obj), lastIndexOf(Object obj) and contains(Object obj). I would be showing them to you one by one. Here is the set(int, T):



    Anything you see that could be bettered?
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    The changed contains(Object obj) method:



    indexOf(Object obj)



    and lastIndexOf(Object obj)



    Please comment if I have changed them correctly as per the List interface contract.
    Paul Clapham
    Bartender

    Joined: Oct 14, 2005
    Posts: 18570
        
        8

    Mansukhdeep Thind wrote:Please comment if I have changed them correctly as per the List interface contract.


    My comment would be that I haven't seen anything about testing in this thread. (Not that I've been following the entire thing.) But today testing is considered an important part of programming -- many would say that you should write the unit tests for your methods before you even write the code for the methods.

    So... think about what the test cases would be for those methods. Remember that testing isn't supposed to demonstrate that your code is correct, it's supposed to demonstrate the presence of bugs if they are there.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Agreed Paul. So how do you reckon I should start writing test cases for this class that I have partially completed as of now? Is there a particular predefined manner in which it is to be done, some template or something? Or are there any good tutorials for the same? I shall do both side by side then, develop as well as test.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38896
        
      23
    And remember you need lots of tests for each method. I have caught you out in the past because you hadn’t used enough tests.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Well, look who's back. Thank you Campbell for coming back. Can you teach me how to write test cases for a method? Any tutorial would be appreciated.
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 7816
        
      21

    Mansukhdeep Thind wrote:Can you teach me how to write test cases for a method? Any tutorial would be appreciated.

    Well, first off would be to get a proper testing module. AFAIK JUnit is probably the most popular one around, and is quite simple to use. It also plugs into most major IDEs quite nicely.

    I suggest you check out the docs on its site (linked above) for tutorials.

    Winston
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Thanks Winston. Shall write some testXXX() methods and get back on this.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    My first attempt at writing a JUnit test case. I have written it for the add(T) method:


    Test case class





    Test Runner Class



    Is this the way one writes test cases? I am confused about one thing. The third test method that checks for IndexOutOfBoundsException should fail if I pass the correct valued for index. Why does it pass then? It should pass if the index passed is -ve or more than size, which, in this case, is not true. Why is the CustomArrayList_TestRunner class returning true then?
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Mansukhdeep Thind wrote:The third test method that checks for IndexOutOfBoundsException should fail if I pass the correct valued for index. Why does it pass then? It should pass if the index passed is -ve or more than size, which, in this case, is not true.


    So what you're saying is that there's a huge, major bug in Java.

    That must be the case, because your code has no errors, and you've already checked all your assumptions, right?

    For instance, when you say that the index you're passing is negative or greater than size, you have used print statements or a debugger to actually observe that this is the case immediately prior to the add() call in question, right? You didn't just make an assumption and then charge of to the forum for help without doing some due diligence first, such as actually testing that assumption, obviously.

    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    It works properly if I make the following change:


    Why do I have to add elements inside every method separately to execute the respective test case? I have created a myList inside the test class. So, if I add an element in the first method, why is it not present in the following methods? When the stack of a method dissolves, the myList again becomes a list of size 0 as if brand new. Why? I have only created one object in this class. So, all the references should alter the same object. It is as if there are 3 separate instances of myList.
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Mansukhdeep Thind wrote:It is as if there are 3 separate instances of myList.


    Maybe there are.

    What do the docs for JUnit say about how many instances of your test class it creates? What do they say about the order in which the test methods will be called? What do they say about preserving the state of your test class between calls?

    Once again, you seem to be making assumptions about how things behave, and then when you see something that doesn't fit your assumptions, rather than investigating and checking your assumptions you're running here for help. People here are happy to help. That's why we come here after all. But by now, I'd expect you to be doing a little more research yourself before posting here. Don't let this site become a crutch, and don't assume every little question or problem that comes up has to be part of the group discussion.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Jeff Verdegan wrote:
    Mansukhdeep Thind wrote:It is as if there are 3 separate instances of myList.


    Maybe there are.

    What do the docs for JUnit say about how many instances of your test class it creates? What do they say about the order in which the test methods will be called? What do they say about preserving the state of your test class between calls?


    I read the execution procedure of JUnit here. Now I have modified my Test Class to prepopulate the custom list inside the @Before annotated method. But I could not find the answer to my previous question. What exactly happens when I run my Test Runner class? What happens when I say:



    I read the API documentation here. But I could not find anything that indicates specifically what is the flow of execution? After it creates an instance of my Test Class CustomArrayList_Test using reflection, what happens then? That is what I want to know.

    Jeff Verdegan wrote:
    Mansukhdeep Thind wrote:Once again, you seem to be making assumptions about how things behave, and then when you see something that doesn't fit your assumptions, rather than investigating and checking your assumptions you're running here for help. People here are happy to help. That's why we come here after all. But by now, I'd expect you to be doing a little more research yourself before posting here. Don't let this site become a crutch, and don't assume every little question or problem that comes up has to be part of the group discussion.


    Apologies if I am being too curious or irritating Jeff.
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Mansukhdeep Thind wrote:
    I read the API documentation here. But I could not find anything that indicates specifically what is the flow of execution? After it creates an instance of my Test Class CustomArrayList_Test using reflection, what happens then? That is what I want to know.


    I have no idea. My point was that you should be researching that. If it doesn't tell you, then it probably means you can't rely on any particular behavior. On the other hand, if you want to see how many times your class is being instantiated, put some println statements in the constructor. You won't necessarily be able to rely on that behavior in all cases, but it might at least give you an idea of why you're seeing what you're seeing now.

    Apologies if I am being too curious or irritating Jeff.


    There's definitely nothing wrong with being curious, and my comments were not about you being irritating. I said that stuff for your benefit, to get you back on track toward your goal. I wanted to make you aware of what I think you can be expected to do on your own at this point, and where you may be falling into a bad habit--that of turning to the forum too quickly. It's an easy trap to get sucked into in an ongoing thread like this. It can feel like a live discussion, and you start to toss out everything that comes to your mind. I'm reminding you that this is your project, nobody else's, and that the whole reason that you're going through all this now is so that you can learn how to do this stuff on your own.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    The implemented int size() and Object[] toArray() methods:





    Any inputs?

    @ Winston : I cautiously reused code this time.

    EDIT: The declaration of the toArray(T[] a) method gives a warning:



    What does this imply? Is it occurring because the Class itself has the same type <T> as its generic declaration parameterized type? What are its implications and what do I need to do to avoid this?
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38896
        
      23
    Why are you passing an array as a parameter to the toArray method?
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Because that is how the method is declared in the List interface Campbell. I need to implement the exact same method to fulfill the List contract. See this
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 7816
        
      21

    Mansukhdeep Thind wrote:@ Winston : I cautiously reused code this time.

    Hey, don't be cautious about. Do it. At least, wherever it makes sense.

    EDIT: The declaration of the toArray(T[] a) method gives a warning:
    The type parameter T is hiding the type T

    That's almost certainly because you've defined your class as MyList<T>. If you notice, List is defined as List<E>.

    You could try:
    public <E> E[] toArray(E[] a) {
    but you may still get a warning or error because you're using a different symbol. If that's the case, simply refactor your class to use <E>.

    Actually, that method signature is not very good. It really should be:
    public <T extends E> T[] toArray(T[] a) {
    which probably doesn't solve your problem; but at least makes it more obvious what's going on. They should probably warn you about it in the docs too.

    Winston
    Mike Simmons
    Ranch Hand

    Joined: Mar 05, 2008
    Posts: 3014
        
      10
    Winston Gutkowski wrote:
    Actually, that method signature is not very good. It really should be:
    public <T extends E> T[] toArray(T[] a) {
    which probably doesn't solve your problem; but at least makes it more obvious what's going on. They should probably warn you about it in the docs too.

    Surely <T super E> would make more sense, no? And be safe for use for any legal T?
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 7816
        
      21

    Mike Simmons wrote:Surely <T super E> would make more sense, no? And be safe for use for any legal T?

    You're absolutely right, my mistake.

    In fact, it should probably simply have been:
    public E[] toArray(E[] a) {
    and saved everybody a lot of grief.

    @Mansukhdeep: This is one of the basic problems with generics: It just doesn't dovetail well with arrays. Even if you do as Mike says, you're still going to have to add an @SuppressWarnings tag, because you'll be forced into an unchecked cast(*), which is precisely what generics were created to avoid.

    Winston

    Edit: (*) Oops. Put 'exception' when I meant 'cast'.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Winston, I got a job in a company. Chances are this class may take longer than expected to finish. Moreover, I see that people earn cows while answering my queries. Its good for them too.

    And yes, I agree with your comment Winston. Arrays have runtime safety too and if you try and store something that is not a component type of the array, you get an ArrayStoreException. Not the same for generics though as it enforces only compile time safety. I think we have to live with that.
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 7816
        
      21

    Mansukhdeep Thind wrote:Winston, I got a job in a company...

    Hey, congratulations man.

    Winston
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
     
    subject: Implementing ArrayList class manually