Iterator


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 9 of 9

Thread: Iterator

  1. #1
    Join Date
    Nov 2003
    Posts
    7

    Iterator

    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
    Code:
    iterator i = l.iterator();
    (l is the name of the list)

    then we use
    Code:
    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]

  2. #2
    Join Date
    Mar 2003
    Posts
    834
    Just, before I start, take a look at the code you posted:
    Code:
    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:
    Code:
    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.
    Code:
    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);	
    	}
    }
    ArchAngel.
    O:-)

  3. #3
    Join Date
    Nov 2003
    Posts
    7
    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!!!

  4. #4
    Join Date
    Mar 2003
    Posts
    834
    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:
    Code:
    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:
    Code:
    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:
    Code:
      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:
    Code:
    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.
    ArchAngel.
    O:-)

  5. #5
    Join Date
    Nov 2003
    Posts
    7
    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
    Code:
     
       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
    Code:
        
    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..

  6. #6
    Join Date
    Nov 2003
    Posts
    9

    Wink

    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.

  7. #7
    Join Date
    Nov 2003
    Posts
    7
    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

    Code:
     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

    Code:
            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.
    Code:
     
        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
    Code:
       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.....

  8. #8
    Join Date
    Nov 2003
    Posts
    7
    Ladies and Gents ,

    I solved the problem.
    Code:
        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!!!

  9. #9
    Join Date
    Nov 2003
    Posts
    9
    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...
    Code:
    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center