Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > what happen in for (x:List) and iterator when adding to List

Reply
Thread Tools

what happen in for (x:List) and iterator when adding to List

 
 
George
Guest
Posts: n/a
 
      09-25-2008
Hi,

I need to do a breadth-first search on a graph. So I need to have a
list for element and iterator over it while keep adding element in the
end of the list. I am currently using ArrayList in java 5. I
remembered vaguely something about the iterator is unpredictable when
the collection changed. Is it true?

Can I use
List<E> list=new ArrayList<E>;
......
for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
{....; list.add(x);
}

or can I use

for (x:list){
.....; list.add(x);
}
 
Reply With Quote
 
 
 
 
Andreas Leitgeb
Guest
Posts: n/a
 
      09-25-2008
George <(E-Mail Removed)> wrote:
> for (x:list){
> ....; list.add(x);
> }

That will not work, but perhaps this will:

ArrayList auxList=new ArrayList();
do {
auxList.clear();
for (Object x:list) { ...; auxList.add(x); }
list.addAll(auxList);
} while (!auxList.empty());

I didn't test it, but hope for lack of typoes and thinkoes.
 
Reply With Quote
 
 
 
 
Andreas Leitgeb
Guest
Posts: n/a
 
      09-25-2008
Lew <(E-Mail Removed)> wrote:
>> for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
>> {....; list.add(x);
>> }

> Where does 'x' come from?


Probably it doesn't matter at all. It's just some element that's
to be added to end of the currently iterated list.
It doesn't work that way, of course. I understood the question not
so much as about the "why", but rather about "how else can I achieve
such an effect".

>> for (x:list){
>> .....; list.add(x);
>> }

> Wouldn't that make the List grow until it hits OutOfMemoryError (OOME)?
> (Isn't that the point of Andreas' response?)


No that wasn't it. I (boldly) assumed, that the ".....;" contained
something like: "if (x.exhausted()) continue; x.exhaustGradually();"

Anyway, I meanwhile noticed, that my code is broken as well, because
I re-iterate also those elements that were originally in list...

 
Reply With Quote
 
Andreas Leitgeb
Guest
Posts: n/a
 
      09-25-2008
Andreas Leitgeb <(E-Mail Removed)> wrote:
> George <(E-Mail Removed)> wrote:
>> for (x:list){
>> ....; list.add(x);
>> }

> That will not work, but perhaps this will:


On review (and after Lew's comment): no it didn't, either.
Follows next attempt:

ArrayList auxList=new ArrayList( list );
do {
ArrayList newList=new ArrayList();
for (Object x:auxList) { ...; newList.add(x); }
list.addAll(newList); auxList=newList;
} while (!auxList.empty());

As long as the inner loop produces new elements, the outer
list will take care of adding them to the original list
(which is not iterated itself, so it's ok) and of preparing
for next run of the inner loop.

> I didn't test it, but hope for lack of typoes and thinkoes.

Same again.

PS: maybe the ArrayDeque would be more appropriate for your task
(and you wouldn't iterate() it, but poll() the first element, and
eventually offer() one to the far end of the queue.)

 
Reply With Quote
 
Tom Anderson
Guest
Posts: n/a
 
      09-25-2008
On Thu, 25 Sep 2008, Andreas Leitgeb wrote:

> PS: maybe the ArrayDeque would be more appropriate for your task
> (and you wouldn't iterate() it, but poll() the first element, and
> eventually offer() one to the far end of the queue.)


Yes, i think what the OP really wants is a queue - certainly, if he's
doing breadth-first search in the normal way, that's exactly what he
needs. It doesn't need to be a deque, but ArrayDeque is the best
all-round implementation of Queue. So:

void breadthFirstVisit(Node root, NodeVisitor visitor) {
Queue<Node> toVisit = new ArrayDeque<Node>() ;
toVisit.add(root) ;
while (!toVisit.isEmpty()) {
Node n = toVisit.remove() ;
for (Node child: n.getChildren()) toVisit.add(child) ;
visitor.visit(n) ;
}
}

tom

--
The revolution is here. Get against the wall, sunshine. -- Mike Froggatt
 
Reply With Quote
 
George
Guest
Posts: n/a
 
      09-25-2008
Thank you all.

Thanks for the remind about javadoc. I should have read about it.

What I am trying to do is the build-up the breadth-first tree
traverse from a node in a graph if you are familiar with data
structure. This can be accomplished by a "link-list" or array in the
traditional data structure sense. I have one node at first. Then I
add all the connected NEW nodes of the current node to the end while
going through the link-list. I just figure it might be quicker and
safer to use something ready in java rather than building my own. But
there seems to be no mechanism in collection framework. The two for
coupling should work, but it would be inefficient because it checks
the connection of those nodes that I have already checked. I am using
java 5. So I cannot use Deque.

Any suggestion?

Sincerely
Zhu, Guojun

On Sep 25, 2:54*am, George <(E-Mail Removed)> wrote:
> Hi,
>
> I need to do a breadth-first search on a graph. *So I need to have a
> list for element and iterator over it while keep adding element in the
> end of the list. * *I am currently using ArrayList in java 5. I
> remembered vaguely something about the iterator is unpredictable when
> the collection changed. *Is it true?
>
> Can I use
> List<E> list=new ArrayList<E>;
> .....
> for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
> {....; list.add(x);
>
> }
>
> or can I use
>
> *for (x:list){
> ....; list.add(x);
>
> }
>
>


 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      09-25-2008
On Sep 25, 12:30*pm, George <(E-Mail Removed)> wrote:
> Thank you all.


Please do not top-post.

> I just figure it might be quicker and
> safer to use something ready in java rather than building my own. *But
> there seems to be no mechanism in collection framework. *The two for
> coupling should work, but it would be inefficient because it checks
> the connection of those nodes that I have already checked. *I am using
> java 5. *So I cannot use Deque.


No, but Queue is available in 1.5, and that's what you need.

<http://java.sun.com/javase/6/docs/api/java/util/Queue.html>
<http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html>

Once again, the Javadocs rescue you. You should've looked up "Queue"
the minute it was mentioned.

--
Lew
 
Reply With Quote
 
Andreas Leitgeb
Guest
Posts: n/a
 
      09-25-2008
George <(E-Mail Removed)> wrote:
> I am using java 5. So I cannot use Deque.
> Any suggestion?


Now that you know the javadocs, hinting you towards
Queue and LinkedList (as a standard class implementing
Queue) should get you further. (these two do exist in 1.5)

 
Reply With Quote
 
George
Guest
Posts: n/a
 
      09-25-2008
Thanks. The queue can do that but seems not very efficient since I do
need the full list instead of the working one. I am end up using a
bare array to implement it. I just make an array with the size of the
graph nodes and use the primitive int i as iterator. Sometimes, one
probably needs to fall back to the basic things.

Sincerely
Zhu, Guojun

On Sep 25, 12:20*pm, Lew <(E-Mail Removed)> wrote:
> On Sep 25, 12:30*pm, George <(E-Mail Removed)> wrote:
>
> > Thank you all.

>
> Please do not top-post.
>
> > I just figure it might be quicker and
> > safer to use something ready in java rather than building my own. *But
> > there seems to be no mechanism in collection framework. *The two for
> > coupling should work, but it would be inefficient because it checks
> > the connection of those nodes that I have already checked. *I am using
> > java 5. *So I cannot use Deque.

>
> No, but Queue is available in 1.5, and that's what you need.
>
> <http://java.sun.com/javase/6/docs/api/java/util/Queue.html>
> <http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html>
>
> Once again, the Javadocs rescue you. *You should've looked up "Queue"
> the minute it was mentioned.
>
> --
> Lew


 
Reply With Quote
 
Patricia Shanahan
Guest
Posts: n/a
 
      09-25-2008
George wrote:
> Thanks. The queue can do that but seems not very efficient since I do
> need the full list instead of the working one. I am end up using a
> bare array to implement it. I just make an array with the size of the
> graph nodes and use the primitive int i as iterator. Sometimes, one
> probably needs to fall back to the basic things.

....

As a matter of curiosity, did you measure the queue based method?

Patricia
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
List iterator assignment fails, assert iterator not dereferencable David Bilsby C++ 5 10-09-2007 02:05 PM
Difference between Java iterator and iterator in Gang of Four Hendrik Maryns Java 18 12-22-2005 05:14 AM
How to convert from std::list<T*>::iterator to std::list<const T*>::iterator? PengYu.UT@gmail.com C++ 6 10-30-2005 03:31 AM
difference between the each iterator and the collect iterator? vasten@gmail.com Ruby 4 10-28-2005 04:42 AM
Iterator doubts, Decision on Iterator usage greg C++ 6 07-17-2003 01:26 PM



Advertisments