Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / September 2006

Tip: Looking for answers? Try searching our database.

store or clone the Iterator

Thread view: 
p7371464@yahoo.com.tw - 04 Sep 2006 15:16 GMT
I have a LinkedList which stores some integer key.
For each key, I can use a computing function f() to get the
corresponding value.
In order to founding the key which has smallest value, I must work
through all key in the list.
Once found the key, I will remove the key from the list.
So I wrote the code as follow:

...
LinkedList<Integer> list = new LinkedList<Integer>();
...
...add some integer key to the list
....

ListIterator<Integer> it = list.listIterator();
ListIterator<Integer> it_save;
Integer min=Integer.MAX_VALUE;

//walk through all key in the list to found the key have minimum value
while(it.hasNext()){
   int key = it.next();
   int value = f(i);

   if(value < min){
       it.previous();
       It_save = it;
       it.next();
   }
}

//remove the key which has smallest value
it_save.remove();
....

But the above code can not work correctly, have any method to store the
ListIterator variable while
scan the list ?

Thanks in advance.
Thomas Hawtin - 04 Sep 2006 15:38 GMT
> I have a LinkedList which stores some integer key.
> For each key, I can use a computing function f() to get the
[quoted text clipped - 3 lines]
> Once found the key, I will remove the key from the list.
> So I wrote the code as follow:

Using ListIterator.previousIndex is the obvious solution. If the extra
iteration through the list is a performance problem, you've probably
started with the wrong data structure anyway (LinkedList is almost
always the wrong choice).

Tom Hawtin
Signature

Unemployed English Java programmer
http://jroller.com/page/tackline/

ricky.clarkson@gmail.com - 04 Sep 2006 20:45 GMT
I would do this by looping through, and storing a minimum value..

int min=Integer.MAX_VALUE;

for (final Integer key: list)
{
   int value=f(key);

   if (value<min)
       min=value;
}

return min;

Of course, this gives you a stupidly high number if there are no
elements in the list, and I'll leave solving that as an exercise for
the OP. ;)

This can be nicely generalised into a method that takes a function as
an argument, which is also fun.  See fpeas.util.Collections.min in
Functional Peas:

http://functionalpeas.googlecode.com/svn/trunk/src/fpeas/util/Collections.java

> I have a LinkedList which stores some integer key.
> For each key, I can use a computing function f() to get the
[quoted text clipped - 35 lines]
>
> Thanks in advance.
Piotr Kobzda - 04 Sep 2006 22:50 GMT
[...]

> But the above code can not work correctly, have any method to store the
> ListIterator variable while
> scan the list ?

No.

But your goal can be achieved without of it, using only two independent
iterators.  See implementation:

    public static <T> T removeFirstMin(
            LinkedList<T> list, Comparator<? super T> c) {
        int left = list.size();
        ListIterator<T> fit = list.listIterator();
        ListIterator<T> bit = list.listIterator(left);
        T f = fit.next();
        T b = bit.previous();
        for (; left > 1; --left) {
            if (c.compare(f, b) <= 0) {
                b = bit.previous();
            } else {
                f = fit.next();
            }
        }
        fit.remove();
        return f;
    }

Which can be applied into your scenario this way:

    removeFirstMin(list, new Comparator<Integer>() {

        public int compare(Integer k1, Integer k2) {
            int v1 = f(k1);
            int v2 = f(k2);
            return (v1<v2 ? -1 : (v1==v2 ? 0 : 1));
        }

    });

HTH,
piotr


Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.