2

I have the following code:

class A {
    IListB list;

    A( IListB list ) {
        this.list = list;
    }
}

interface IListA {}

class EmptyListA implements IListA {
    EmptyListA() {}
}

class ListA implements IListA {
    A first;
    IListA rest;

    ListA( A first, IListA rest ) {
        this.first = first;
        this.rest = rest;
    }
}

interface IListB {}

class EmptyListB implements IListB {
    EmptyListB() {}
}

class ListB implements IListB {
    B first;
    IListB rest;

    ListB( B first, IListB rest ) {
        this.first = first;
        this.rest = rest;
    }
}

So I have an instance of ListA which contains a few instances of class A. Each class A contains an instance of ListB. I'm attempting to write a method for ListA that would take all of the ListB's contained within it and produce a single ListB (just one level deep, no nested lists). I have literally been trying to do this for the past 4 hours now with absolutely no luck.

Improve this question
2
  • 1
    Why don't you use a Java List? You have there a method addAll() + other functionalities of Collections. Commented Nov 9, 2009 at 6:36
  • 3
    This smells like homework ... Commented Nov 9, 2009 at 6:43

3 Answers 3

Reset to default
2

I recognise this as uni homework. So I'm not attempting to give you the solution, but rather point you in the right directions.

Recursion

If I were to guess, I would say the objective of this assignment is to get you to use recursion, because that's the only alternative to iteration in solving a problem like this.

The clue was in the constructors: 

ListA( A first, IListA rest )

and 

ListB( B first, IListB rest )

Recursion is where a method calls itself directly (or indirectly), and stops doing so when a base case is encountered. Here are some examples.
In this situation, where you have a data structure where X contains another instance of X lends itself quite well to the application of recursion insolving the problem.

Use instanceof

In order to differentiate the two types of IListB's (EmptyListB and ListB), you could use instanceof. Given the variable list is an IListB (but you need to find out which one it implements): 

if (list instanceof ListB)
{
    ListB listB = (ListB)list;
    //do stuff with listB
}
else if (list instanceof EmptyListB)
{
    EmptyListB emptyListB = (EmptyListB)list;
    //do stuff with emptyListB
}

Best practices

You code listing above, while technically correct, doesn't have much by way of good programming practices. You will find your code alot less unwieldy (and easier to work with yourself), by doing the following:

  • Give all your classes and the member variables and methods modifiers such as private, protected and public
  • Create getters (and where needed setters too) for member variables of one class that need to be accessed from (objects of) other classes
  • Adding (just enough) comments

Edit

As per Rasmus' suggestion: Create isEmpty methods as follows, and then you can test whether an object of type IListB is empty or not rather easily.

interface IListB {
    public boolean isEmpty();
}

class EmptyListB implements IListB {
    ...
    public boolean isEmpty()
    {
        return true;
    }
}

class ListB implements IListB {
    ...
    public boolean isEmpty()
    {
        return false;
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Yes, the objective in this situation is to use recursion, and I thought of doing it like this as well, except we're not allowed to use instanceof. Kind of frustrating.
If you can modify IListX to add a virtual isEmpty() method (and implement that to simply return true in EmptyListX and false in ListX) you don't need instanceof.
@Adam what other restriction do you have besides no iteration and no instanceof? @Rasmus +1 Because I reckon that is actually the best way to get around not being able to use instanceof.
0

You have a way to add a B to an IListB? (Yes you have, the constructor to ListB prepends a B to an IListB). Then you can add an entier IListB to another IListB by iterating over one list while prepending to the other. Create a method for this!

Then you just have to iterate over your IListA, prepending the contents of each IListB to the main list (use the method you just created).

Improve this answer

4 Comments

That sounds like a good idea, however I'm not quite sure what you mean by "iterating over one list while prepending to the other". By this do you mean two different instances of IListB?
You have several instances of IListB to begin with (one for each A). And by "the main list" above I mean an accumultad list, that you create (empty) in your merge method, and add all the B's from the other lists to.
Well, I'm not allowed to use iterators or "for" loops. I'm beginning to think this can't be done.
If loops are prohibited, you may use recursion instead. E.g. to add an antire list x to a list y, create a method that adds the first item of x to y, and calls itself to add the rest of x to y.
0

Couldn't you just create a new ListB, and then loop through every instance of class A, and for each one get its listB and keep adding those listB's to your newly created ListB? Are you able to add two lists together directly? If not, then just loop through each list within the A class, and add the individual elements to your new ListB.

Improve this answer

2 Comments

I cannot add two lists together directly. The problem is that I need some way of omitting the EmptyList.
Ok. Sorry, when I first read your question I wasn't aware that you couldn't add the two lists together directly and that loops were prohibited. As others have suggested, I think recursion may be the way to go.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.