CODEWITHSUNDEEP
java
Adam K
Adam K

Reputation: 21

Nested Data Structure Problem

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.

Upvotes: 2

Views: 332

Answers (3)

bguiz
bguiz

Reputation: 28617

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;
    }
}

Upvotes: 2

Michael Patterson
Michael Patterson

Reputation: 1770

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.

Upvotes: 0

Rasmus Kaj
Rasmus Kaj

Reputation: 4360

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).

Upvotes: 0

Related Questions