lists inside a list :(((

[H Melua]

hello

i need help in working with trees, how to actually do it, or what do i need to do it, im not asking for codes, but ideas... and maybe links that will help me... im doing my own research but ur help is very appretiated

i need to implement a tree.. no GUI, its like having lists inside a list, and inside those lists there shall be another lists (strings)!!! im really struggling to guess how can that be done! i know i will be using collections, but is there a particuler method that helps to add a list inside another? i read the ADT but still didnt do much... ahh

any suggestions?
thank u
Hannah

[Steven Bell]

Generally when you are creating some kind of tree structure you would create a Node class. What the Node class looks like would depend on how your tree is structured.

A simple example node for a binary tree might look like this:

public class Node{
  private Node leftChild;
  private Node rightChild;
  ...
  public boolean isLeaf(){
    return leftChild == null && rightChild == null;
  }
  ...
  public Node getRightChild(){
    return rightChild;
  }
  public void setRightChild(Node rightChild){
    this.rightChild = rightChild;
  }
}

Then you would have some Tree class that would use these nodes to perform operations such as search, pre/post traversal. Some people would make the Node class an inner class of the Tree, I personally don't really like that approach.

Hope that helps.

[H Melua]

thank u so much for replying
but that mean i will only have 2 children attached to each parent, but what i need is a parent node that can have many children all in one level below it, and i should be able to make any of them a parent of another list!

i could use a linkedList to store children of one parent, but the problem is with making the children parents!! which means i need to link the 2 lists

                                    Emma
                             |        |         |
                           Leame      TJ      Laura
                       |     |        |      |   |   |  |
                       S     T        P      P   M   S  N
 

Something that looks like this... any help
Hannah
[ March 25, 2005: Message edited by: H Melua ]

[David Harkness]

Are you allowed to use the Java Collections classes to create your tree? If so, you can simply use any of the List classes (LinkedList, ArrayList) and nest them. The Collection classes will store any Object as their elements, so in any node you can store a String or another List.

Here's a simple example where each tree node has either a value or children, but never both. Supporting both would require creating a TreeNode class to hold a String and a List.

List root = new LinkedList();
List child1 = new LinkedList();
List child2 = new LinkedList();
List child3 = new LinkedList();
root.add(child1);
root.add(child2);
root.add(child3);
child1.add("Hello");
child1.add("There");
child2.add("A");
child2.add("B");
child2.add("C");
child3.add("1");
child3.add("2");
child3.add("3");

When you access an element of a List using get(index), you can test the returned Object to see if it's another List or a value (String) that you're storing in the tree. If you enforce some structure (or in the case above where you already know), you can make assumptions.

((List) root.get(1)).get(2) --> "C"

In a binary search tree, you use the ordering of the elements to determine how to build the structure of the tree. For example, starting with this tree,

    4
   / \
  2   6
 / \
1   3

inserting the value 5 will create a new node as the left child of 6 to hold it.

    4
   / \
  2   6
 / \ /
1  3 5

How will you specify where values should be stored in your tree if each node can have an unlimited number of children?

[H Melua]

aww bless u (david) u honestly made me so happy
yes i can use collections...now i can start imagining how it can be done .. wellllll thats a good question :roll: .... i guess it will be using the name i specify, so i'll do a little search and when i find the specified name i can then add another value to it...

oh my life, iterating through this will be a killer!!
i'll have a go at programming this and i'll c how it goes, i thank u lot so much..

Hannah

[H Melua]

_____________________________________________________________________
im back
ive got a problem with this code,

 public boolean addToHouse(House house1, House house2){
          house1 = new ArrayList(); 
          house1.add(house2); 

this code gives me incompatible type error, and i understand y
if i change it to

 public boolean addToHouse(Object house1, House house2){

then it works, but would it create a problem for me in the future since house1 will always be of type House? is defining house1 as object means house1 can be either a House or any other object?

thank u
hannah

______________________________________________________________________
OK ive solved this problem, but it might be slightly imperfessional! so what do u lot think?
ArrayList house = (ArrayList)house1;
is it actually doing what i want?


[ March 26, 2005: Message edited by: H Melua ]

[David Harkness]

There is one major problem with the code you've posted: you are changing the value of an argument (house1) which will have no effect in the method that calls it. Method arguments in Java are pass by value, meaning they are a copy of the variables/values used when calling the method.

public void addFive(int x) {
    x = x + 5;
}
 
public void addAndPrint(int x) {
    addFive(x);
    System.out.println("x = " + x);
}
 
public void doIt() {
    int x = 10;
    addAndPrint(x);
}

Calling doIt() will print "x = 10". The reason is that the x's in each of the methods are all individual local variables (local to the methods that define them). When addAndPrint() calls addFive(), it passes it a copy of x's current value, 10. Inside addFive(), the value 10 is assigned to a new local variable x (though they have the same name, they are different variables), 5 is added to that local variable, and the method returns.

Since addFive() operated on its local copy, the x inside addAndPrint() is unaffected. Thus, it prints 10.

Having said that, the first thing to address is what House is. I assume you have defined a House class. If so, can you post it? Is House the TreeNode I described above? Does it hold a String and an ArrayList of children? If so, you need to add a method to House called add() that will add a given House as its child.

Your use of a method outside the House class -- addToHouse() -- is what's known as procedural programming. You have a method that lives off on its own that you give arguments on which it does its work. One of the major points of object oriented programming is encapsulation: combining data with the operations (methods) to act upon the data.

Instead of addToHouse(), create an add(House) method in the House class itself. You might also want to start by writing a one or two paragraph description of what a House represents and what it can do. This will serve as a good starting point for creating the methods House will need.

Here's an example using a Person class.

A Person has a name and age. Each Person has two parents (Person), either of which can be null if unknown, and zero or one spouse (Person). A Person also maintains a List of its children (each a Person).

public class Person
{
    private String name;
    private int age;
    
    private Person parent1;
    private Person parent2;
    private Person spouse;
    
    private List children = new ArrayList();
    
    public Person(String name, int age, 
                  Person parent1, Person parent2)
    {
        this.name = name;
        this.age = age;
        
        // setting parents will add this as child of those parents
        setParent1(parent1);
        setParent2(parent2);
    }
    
    public void setParent1(Person parent)
    {
        if ( parent1 != null ) {
            // cannot change birth parents
            throw new IllegalStateException("Already has parent1");
        }
        
        if ( parent != null ) {
            // set reference and add as child of parent
            parent1 = parent;
            parent.addChild(this);
        }
    }
    
    public void setParent2(Person parent)
    {
        if ( parent2 != null ) {
            // cannot change birth parents
            throw new IllegalStateException("Already has parent2");
        }
        
        if ( parent != null ) {
            // set reference and add as child of parent
            parent2 = parent;
            parent.addChild(this);
        }
    }
    
    public int getChildrenCount()
    {
        return children.size();
    }
    
    public void marry(Person p)
    {
        if ( p == null ) {
            throw new IllegalArgumentException("p must be non-null");
        }
        else if ( spouse == p ) {
            // renewing vows; noop
            return;
        }
        else if ( spouse != null || p.spouse != null ) {
            // both must be single
            throw new IllegalStateException("Already married");
        }
        
        spouse = p;
        p.spouse = this;
    }
    
    public Person createChild(String name)
    {
        if ( spouse == null ) {
            throw new IllegalStateException("No spouse to have child");
        }
        
        // create a child with this Person's spouse
        return createChild(name, spouse);
    }
    
    public Person createChild(String name, Person otherParent)
    {
        if ( otherParent == null ) {
            throw new IllegalArgumentException("otherParent must be non-null");
        }
        
        // create and return a newborn (age 0) Person
        // constructor will add as child of both parents
        return new Person(name, 0, this, otherParent);
    }
    
    public void addChild(Person child)
    {
        if ( child == null ) {
            throw new IllegalArgumentException("child must be non-null");
        }
        
        children.add(child);
    }
}

As you can see from the example, it's not always clear where responsibilities lie. A method like marry(Person) could arguably belong to a different helper class since it operates on two people equally (one Person doesn't have all the responsibility since they both marry each other). However, it's generally easier to start this way to enforce encapsulation.

The method more applicable to your code would be getChildrenCount() and addChild(). Notice that the Person class has sole responsibility for managing the List of children.

[H Melua]

hello
and thank u very much david

ok thats what i did so far.. the problem is that im not thinking to the future! and whether it will be possible for me since im not very knowlegdeable in java to do what i want to do!

public interface House extends Comparable
{
    public String getName();
}
//------------------------------------------------
public class TheHouse implements House{
    private String name;
    
    public TheHouse(String name) {
        this.name = name;
    }
 
    public String getName() {
        return name;
    }
 
    public int compareTo(Object house){ //SomeCode}
}
//-----------------------------------------------
import java.util.ArrayList;
 
public interface HouseList
{   
    // this adds a child house to the root
    public boolean add(House house);
    
    // this adds a child to a given child house and so makes it a parent
    public boolean addToHouse(House house1, House house2);
    
    // this adds a child to a given parent house, ive never wrote 2methods of the same name,
    //so tell me if its not a good idea
    public boolean addToHouse(ArrayList house1, House house2);
 
    public java.util.Iterator iterator();
}
//------------------------------------------------
 
import java.util.Collections;
import java.util.Iterator;
import java.util.ArrayList;
 
public class TheHouseList implements HouseList{
 
    private ArrayList houseList;
    
    public TheHouseList() {
        houseList = new ArrayList();
    }
    
    //this method isnt compelete yet bcus im stock i cant find out how to iterate!
    public boolean add(House house) {
        if(houseList.contains(house))
            return false;   
        else return houseList.add(house);
    }
 
    public boolean addToHouse(ArrayList house1, House house2){
        if(house1.contains(house2))
            return false; 
        else return house1.add(house2);
    }
 
    public boolean addToHouse(House house1, House house2){
        ArrayList house = (ArrayList) house1; // i want house to have same name as house1!
        house = new ArrayList(); 
        return house.add(house2); 
    }
 
    public Iterator iterator() {
        //someCode
    }
}

i wish to know, if what im doing is at least abit right? if i solve the problem of iterating will this code be ok? and regarding the find method, is it going to be ok to iterate throught a list of house children and house lists (parents)? :roll:
i honestly dont know if its supposed to hold a string and its list, i asked my lecturer and he said i cant tell u this then i'll be doing most of the work for u!!! hes like that i dont ever ask him cus hes useless!!
im assuming that the name of the list is basically the parent name i need, and so if u look back at my diagram, e.g. laura is going to be a list and the name laura will be name i search for if i want to add any child to it.. if thats possible!
i cant wait till the 12 of june, i'll be done and sleeping at home
Hannah

[H Melua]

emmm i think i can spot something... what im going, making the House creates the children, and the houselist makes them parents and adds some of those children to the parents created, and that is making houselist in charge of 2 major functions!!

would it be better if i have for example a class that creates a child, another class that creates a parent and another class that creates the list of parents? or would keeping mine be ok?!

hannah :/

[David Harkness]

This looks very good so far, but I'm not sure that it matches your original description. I see a House class that has a name, and there's a HouseList class that wraps an ArrayList to hold many Houses. But your two addToHouse() methods seem to be treating the House like it has a list itself. And that matches what I read above (a tree of Houses).

If you clear that up and explain exactly what iteration is supposed to do (iterate the whole tree or just a single House's children?), I can help further.

i honestly dont know if its supposed to hold a string and its list, i asked my lecturer and he said i cant tell u this then i'll be doing most of the work for u!!!

I recall this attitude from professors in beginning classes. They forget that it really isn't that easy when you're starting and focus on one small piece of the design which they feel is 90% of the effort -- making a single decision about the structure of a class!

In any case, the Collections framework has a binary tree implementation, TreeSet, that you could look at for ideas. Make a case for both ways and see which makes more sense to you. Often in school exercises, you can go the simpler route that is less flexible because flexibility isn't the point of the problem -- it's to learn how trees work, for example.

Also, I've got a few pointers if you'd like. It's a good practice to use the Collections interfaces in type declarations when possible, specifying the exact implementation only when creating it. This makes it much easier to change from ArrayList to LinkedList later.

public boolean addToHouse(House house1, House house2);
public boolean addToHouse(ArrayList house1, House house2);

Perhaps name one house "parent" and the other "child" so the caller knows which is which. Also, I'm unclear what the second method does. The comment makes it sound like they're the same method. Does the second one add multiple houses to house2? Or is the ArrayList house1's list of children?

Make sure to override equals(Object) for TheHouse so that houseList.contains(house) will work. I assume two houses are equal if they have the same name. If not, and two houses are equal only when they are the same instance, ignore this paragraph. Object.equals(Object) does the latter for you.

[David Harkness]

Originally posted by H Melua:
making the House creates the children, and the houselist makes them parents and adds some of those children to the parents created, and that is making houselist in charge of 2 major functions!!

A single class will usually have multiple methods that make up one or a few coarse responsibilities. Especially in the beginning, don't over-emphasize cohesion (few responsibilities) or you end up with a whole bunch of entangled classes that are harder to understand than one or two larger classes.

Can you briefly summarize the requirements for the assignment? Given them, what responsibilities must House have?

[H Melua]

basically, we can look it that way, its nothing to do with houses, but thats like a demo..

                        houseAgent                              [Company]
              |              |             |
          MyArea          YourArea       SomeArea               [Area]
     |       |               |         |      |      |
    me    MyParents         You       him    her    them        [House]
              |                                       |
           MySis                                   theirChild   [People]

i can add an area which will hold set of houses, and i can add a house to an area, i can also add to the house a number of people who live there.. and keep on extending it... and to be able to add anything, i'll have to find where to add it (and so search the whole tree) and check if its not there already..

what the 2nd addToHouse(ArrayList...) does, it takes in a list which is little subtree and adds a child to it or can actually be a list itself!!! << in this case i'll need a third method that takes in 2 ArrayLists!

we should be able to add for example, the subtree "someArea" to the subtree "YourArea", and we should be able to add "TheirChild" to the subTree "MyParents", and so on of that..

thats what i need for now.. but its honestly way bigger than that

the problem with treeSet is that it is a set, and i want a list, im allowed to have dublicate values there, so i can have "You" in "YourArea" & "someArea" meaning "you" can have more than1 house!

Haaaannah
[ March 27, 2005: Message edited by: H Melua ]

[H Melua]

loool u'v actually reminded me once ago, when i was yet at school, one of the guys of whom always asks silly questions ("sir can u do this for me", "sir can u help me") and once he said "sir, can u let me go to the toilet" and the lecturer automatically said before the boy says "toilet", "No i cant do everything for u, oh yes u can!" looool i cant remember laughing from my heart like i did that day! and this lecturer is so like him!
not any1 can be a lecturer!

[David Harkness]

I recommended looking at TreeSet because it would give you ideas on how to implement a tree. You could ignore the non-duplicate aspect and take away only the tree ideas. But I just checked and TreeSet actually uses a TreeMap internally, and that class is a little heavier, though not much.

Basically, a generic tree can be constructed with a Tree class for the main operations (add, remove, find, etc) and a TreeNode to represent a single item in a tree along with that item's children. The Tree also has a reference to the root TreeNode. Each node maintains a List of its children.

You can have TreeNode manage its list of children, or the Tree class can do all the work.

Do you really need to model House (and Company, Area, and Person) or can you use a String to represent them? In other words, can you simply store the String "MyParents" in the list as a child of the node that contains the String "MyArea", or do you actually need to be able to grab the item named "MyParents" and check that it's a House?

Basically, it seems to me that your overcomplicating it by adding details not in the original assignment, but I can only guess. Are you supposed to do more than implement a tree class? I see you've implemented Comparable which is useful for sorting; is this related?

[H Melua]

true i undestand what ur saying, iam making it complicated! the company and.... are all the same and of one type which is House, so there is no need for these little bits... but yes i will need to check that "myParent" is a house or a list..

not really i dont need to sort it but he said u can use it if u wish to and sort the list, im not worried about that..

what is confusing me is that, when i do find(), wouldnt it have a problem when it looks throught objects of type House and suddently it finds it mixed with ArrayLists?

i imagin it to be like this

                                                        [ArrayList]
                                         [ArrayList]    [House]
                                                        [House]
TreeStartsHere-->          [ArrayList]   [House]
                                                    
                                         [House]
 

so the name of the arrayList is a group of houses, and if i contact the ArrayList it means it will contact all the once bellow it...

ok can i send u a private letter on this?
[ March 27, 2005: Message edited by: H Melua ]

[David Harkness]

Originally posted by H Melua:
when i do find(), wouldnt it have a problem when it looks throught objects of type House and suddently it finds it mixed with ArrayLists?

This is the reason you must override equals(Object) in the House class. The House "this" is equal to the passed in Object only if

the Object is non-null

the Object is a House

both Houses have the same name (my assumption)

One question, though: How will you locate an ArrayList since they don't have names?

ok can i send u a private letter on this?

I prefer to keep it public so others that search the forums can learn as well, but if you want to send me a private message, that's fine.

[H Melua]

sent it u by the way
hannah