Iterator

[Asterothe]

Hello everybody, this is my first post
here. I want to code an iterator for a
data structure homework. The instructor told
us that Iterator has to be a sperarate class.
Let's assume we have a doubly linkd list with nodes.

in main

iterator i = l.iterator();

(l is the name of the list)

then we use

for ( ; i.hasNext(); )
 System.out.preintln(i.next());

Now in order to this work shouldnt
iterator be in the list class? How is the iterator
will get the position of the list without being in the
list? We are not passing any parameters to
the iterator. How do we keep track of
the data? The intructor told us that iterator should be
a speratae class and it has to have a List and
a node inside. I am very confused. i know this is
a very easy problem but I can't figure that out.

Thanks in advance..

[ArchAngel added CODE tags]

[ArchAngel]

Just, before I start, take a look at the code you posted:

for ( ; i.hasNext(); )
 System.out.preintln(i.next());

Doesn't something strike you as a little strange here? Use a while loop! You're performing no initialization and you're not performing any constant action each iteration. Therefore there's no point in using a for loop (and you're making it harder to read). I would have written:

while(i.hasNext()) {
  System.out.println(i.next());
}

Note - I use braces even though there's only one line of code in the body of the loop. I recommend this as a good practice to get into - leaving them out will only get you into trouble later on.

Anyway, your question...

I think this will work best with an example, but I don't want to do your homework for you, so I'll produce my own problem:

Task: Create a BackwardsList class which simply holds a list of objects which can be added using the add(Object) method. You should provide a method iterator() which will allow you to iterator through the items added to the list in reverse order.

import java.util.*;

public class BackwardsList {
	private ArrayList contents;

	public BackwardsList() {
		contents = new ArrayList();
	}

	public void add(Object o) {
		contents.add(o);
	}

	public Iterator iterator() {
		Iterator i = new BackwardsIterator(contents);
		return i;
	}

	public static void main(String[] args) {
		BackwardsList bl = new BackwardsList();
		bl.add("First");
		bl.add("Second");
		bl.add("Third");

		Iterator iList = bl.iterator();
		while (iList.hasNext()) {
			System.out.println(iList.next());
		}
	}
}

/**
 * This probably should be an inner class of BackwardsList,
 * but I wasn't sure if you've done inner classes.
 */
class BackwardsIterator implements Iterator {

	private ArrayList list;
	private int currentIndex;

	public BackwardsIterator(ArrayList list) {
		this.list = list;
		currentIndex = list.size() - 1;
	}

	public boolean hasNext() {
		boolean hasNext = true;

		if (currentIndex == -1) {
			hasNext = false;
		}
	
		return hasNext;
	}

	public Object next() {
		Object element = list.get(currentIndex);
		currentIndex--;
		return element;	
	}

	public void remove() {
		list.remove(currentIndex);	
	}
}

[Asterothe]

ArchAngel you are a savior,
thank you very much..

I know that this is the perfect example
to use a while-loop but when the instructor gave
that code I told him why not while and he
said that he wanted to see the whole
precess in one line.. If it were me I'd of course I'd use
while.

We didn't cove rinner classes. How do they work?
And I am not very clear about "this". I suppose
somehow you pass the argument ( the list) to the
iterator by calling bl.iterator() and that's "this"
sections of the constructors that handle it. Am I
correct?? We didnt cover this neither

Thanks a ton again!!!

[ArchAngel]

he said that he wanted to see the whole
precess in one line..

huh? One line? Are you talking about the lack of braces? I think your instructor is talking rubbish. The choice of loop is determined by its use, nothing else. Instructors....sigh...

We didn't cove rinner classes. How do they work?

All it means is that you can put one class inside another and then prevent any other class from creating objects of that inner class. Don't worry about them for the moment.

And I am not very clear about "this".

It's probably best until you cover this in your course, but here's a two-minute tour of "this". OK, I could have written:

public BackwardsIterator(ArrayList theList) {
  list = theList;

Here there would have been no problem, the parameter variable 'theList' is assigned to the instance variable 'list'.

This isn't a problem, but it often gets difficult to think up of new parameter variable names which are different from the instance variable names. They need to different:

public BackwardsIterator(ArrayList list) {
  list = list;

In the above code the parameter variable and the instance variable are named the same thing: 'list'. In Java, variables are resolved as locally as possible meaning that both of the 'list' variables refer to the parameter variable, meaning that the following code is completely pointless:

  list = list;

...since it's assigning itself to itself!

Right, so we need some way of saying that the 'list' on the left-hand side refers to the instance variable 'list' and the 'list' on the right-hand side refers to the parameter variable 'list. This is where 'this' comes in.
'this' refers to the current object. Therefore
'this.variableName' refers to the instance variable on the current object.

Now consider the code that I wrote:

public BackwardsIterator(ArrayList list) {
  this.list = list;

The 'this.list' refers to the instance variable 'list' on the current object and the 'list' on the right refers to the parameter variable.

It's a bit of a long explanation...hope it helps.

[Asterothe]

Thank you again!
It helps a lot. Now I started
learnign about trees and the book
we are using (Goodrich / Tomissa's Data
Sturctures and Algorithms in Java) is skipping
very importnat information. Could you recommend
a reference for that subject? I am having trouble
with

 
   public PositionIterator positions() {
        Position[] positions = new Position[size()];
        inorderPositions(root(), positions, 0);
        return new ArrayPositionIterator(positions);
        
    }

I have a Position Iterator but ArraypositionIterator
is a adapter they say. What should I set for it? An
I also had an

    
public void inorder(BinaryTree t, Position v) {
        if(isInternal(v))
            inorder(t,t.leftChild(v));
        //perform visit
        if(isInternal(v))
            inorder(t, t.rightChild(v));
    }

but in the code above they have 3 arguments so
I have no clue how to process an array with a 0.
Another reference would be greatly appreciated.

Thanks again..

[MillionBacteria]

Ahh good old data structures and algorithms.
I hated that course sooo much....

code above they have 3 arguments

Maybe i am mistaken but the method with 3 arguments is called inorderPosition and the method u posted is called inorder. They are two different methods.

And adapters are just used to enable objects with different interfaces to communicate with each other. What you set for it is really dependent on the implementation but my guess is that the "adaptee", the object it will adapt to, is the positions array.

[Asterothe]

Originally posted by MillionBacteria


Maybe i am mistaken but the method with 3 arguments is called inorderPosition and the method u posted is called inorder. They are two different methods.

And adapters are just used to enable objects with different interfaces to communicate with each other. What you set for it is really dependent on the implementation but my guess is that the "adaptee", the object it will adapt to, is the positions array. [/B]

You are absouletly right. They give an example of
inorder and then they use inorderPosition in the
main code. So I m trying to figure out that one.
Isn't the goal of inorder functions to access all the
nodes(positions) and do stuff with them? I understand
with

 if(isInternal(v))
            inorder(t,t.leftChild(v));

we reach to an external node(with no child and we
are dealing with a binary tree here ) but after
the visit with

        if(isInternal(v))
            inorder(t, t.rightChild(v));

what's the purpose?

in the 3argument example I'm trying to write
an inorderPostions method that gets all the
positions and put them in the array.

 
    public void inorderPositions(Position v, Position[] positions, int i){
        if(isInternal(v))
            inorderPositions(leftChild(v), positions, i);
        positions[i++] = v;
        
        if(isInternal(v))
            inorderPositions(rightChild(v), positions, i);
        
    }

Should the purpose of that method be this? they call
it like

   public PositionIterator positions() {
        Position[] positions = new Position[size()];
        inorderPositions(root(), positions, 0);
        return new ArrayPositionIterator(positions);
        
    }

Of course still I have to code ArrayPositionIterator
accessor.....

[Asterothe]

Ladies and Gents ,

I solved the problem.

    public int inorderPositions(Position v, Position[] positions, int i){     
        if(isInternal(v))
            i = inorderPositions(leftChild(v), positions, i);
       positions[i++] = v;
        
        if(isInternal(v))
           i= inorderPositions(rightChild(v), positions, i);
         return i;
    }

That's more powerful that I though!!!

[MillionBacteria]

Ahhh good stuff. You got it figured out. Learning inorder traversal eh? Inorder traversal is very simple. This is all there is to it really...

void inorder (tree_pointer ptr)
{
    if (ptr)
    {
        inorder(ptr->left);
        print node value
        inorder(ptr->right);
    }
}

I dunno about you but that's what i memorized and it's helped me out a lot in telling the differece between inorder, preorder and postorder traversals. Hope that's somewhat of a help