Java ArrayList Iterator next() not working as intended

Question

I am trying to create an algorithm that determines if one array list (s1) is a sub-sequence of another array list (s2). The elements in the first list all need to be in the second list and must be in the same order. So s1 is a sub-sequence of s2, but s1 is not a sub-sequence of s2. I need to use iterators to go through each list, and I should only go through each list once (since it has to be in the same order). I seem to have an issue with the next() becoming void ?? What would cause this/how can I fix this? The code I currently have seems to work as I would hope with the exception of not going to the next element in the first array list.

import dataStructures.*;

public class Subsequence2
{
    public static void main(String[] args)
   {
       ArrayList<Character> s1 = new ArrayList<Character>();
       s1.add('n');
       s1.add('p');
       s1.add('a');

       ArrayList<Character> s2 = new ArrayList<Character>();
       s2.add('a');
       s2.add('n');
       s2.add('b');
       s2.add('p');
       s2.add('c');
       s2.add('a');

       Subsequence2 one = new Subsequence2();
       System.out.print("S1 is a subsequence of S2 is a ");      
       System.out.print(one.subSequence(s1, s2));
       System.out.print(" statment.");
} //end main

public static <T> boolean subSequence(ArrayList<T> s1, ArrayList<T> s2) 
{
 //if s1 is empty or if s1 and s2 are empty it is a subsequence
    if(s1.isEmpty() || (s1.isEmpty() && s2.isEmpty())) 
    {
        return true;
    }   
  //if s2 is empty and s1 is not is is not a subsequence.
    else if(s2.isEmpty())
    {
       return false;
    }   
    else
    {
        int s1Count = 0; //count items matched
        Iterator<T> itr1 = s1.iterator();
        Iterator<T> itr2 = s2.iterator();
        while(itr1.hasNext())
     //for(Iterator<T> itr1 = s1.iterator(); itr1.hasNext();) //traverse s1
        {
            T c1 = itr1.getCurrent();
            itr1.next(); //go to next element of s1
            while(itr2.hasNext()) //traverse s2
            {
                T c2 = itr2.getCurrent();
//if items are equal check the next item and add 1 to count of items matched
               if(c1.equals(c2))
               {
                  itr2.next();
                  ++s1Count;
                  //used for testing- just want to see what index it is pulling
                  System.out.print("s1 index " + s1.indexOf(c1) + " s2 index " + s2.indexOf(c2) + " \n" + c1 + " "  + c2 + "\n");
               }
    //if it didn't match, check next element            
               else
               {
                   itr2.next();
               }
               if(s1Count == s1.size()) //if match count is == to s1 size, it is a subsequence
               {
                  return true;
               }
            } // end itr2 while
         } //end for itr1
      } //end else not empty
      return false; 
   } //end subSequence method
 }//end class

I think you are using while(itr2.hasNext()) in a wrong way. this loop will go till end without outer loop going to next iteration. — Faisal Ali
– Faisal Ali, Commented Apr 5, 2014 at 17:42
I haven't taken a close look yet, but note that if(s1.isEmpty() || (s1.isEmpty() && s2.isEmpty()) is equivalent to just if(s1.isEmpty()). If s1 is empty, the whole condition short-circuits to true (without the || (s1.isEmpty() & s2.isEmpty()) bit even being evaluated). If s1 is not empty, then that second part will be evaluated, but will always evaluate to false since it's essentially (false && s2.isEmpty()) (since we know that s1.isEmpty() is false). — yshavit
– yshavit, Commented Apr 5, 2014 at 17:45
"So s1 is a sub-sequence of s2, but s1 is not a sub-sequence of s2." ? I do not get this one ... is it me or is it contradicting itself? — Fildor
– Fildor, Commented Apr 5, 2014 at 17:50
@yshavit - why do I need to re-open the s1 iterator to compare from the start? I don't want to go through it more than once — Ken Buliw
– Ken Buliw, Commented Apr 5, 2014 at 18:31
@yshavit - that's absolutely a subsequence. Karen really DOESN'T want to open a new s1 iterator. — Dawood ibn Kareem
– Dawood ibn Kareem, Commented Apr 5, 2014 at 18:41

Dawood ibn Kareem · Accepted Answer · 2014-04-05 18:57:30Z

1

The condition on the inner loop should not just be itr2.hasNext(). You want the inner loop to iterate so long as itr2.hasNext() AND the next item is not the same as the current item of itr1. Once you find (within itr2) the current item of itr1, you want to stop iterating the inner loop, and go back for the next item in itr1.

public static <T> boolean subSequence(ArrayList<T> s1, ArrayList<T> s2) {
    Iterator<T> itr1 = s1.iterator();
    Iterator<T> itr2 = s2.iterator();

    while (itr1.hasNext()) {
        T itemFrom1 = itr1.next();
        T itemFrom2;
        do {
            if( ! itr2.hasNext()){
                return false;
            }
            itemFrom2 = itr2.next();
        } while( ! itemFrom1.equals(itemFrom2));
    }
    return true;    
}

Basically what's happening here is that while we're still iterating itr1, if we run out of elements in itr2, then we've still got things in itr1 left to match, so it's not a subsequence. But so long as we keep finding things in itr2, we keep going. Whenever we find something in itr2 that matches what we're looking for in itr1, then it's time to go to the next step in the outer loop.

edited Apr 5, 2014 at 18:57

answered Apr 5, 2014 at 18:13

Dawood ibn Kareem

80.2k15 gold badges102 silver badges112 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Ken Buliw Over a year ago

That is what I want to do... apparently that is not what I am doing. This is my first time working with iterators and lists, please excuse my ignorance. How do you suggest I could fix it to do that? I've tried putting the while itr2.hasNext() in various places, but it all ends up back to the next() not seeming to work (as I think it should).

Dawood ibn Kareem Over a year ago

OK, I'll add some code to my answer. Give me 20 minutes or so.

Ken Buliw Over a year ago

I feel so dumb right now. After hours of working on this and then coming to you guys I JUST realized the iterator I am working with has next as void- public void next(); That is why anything I was trying the next() is type void.

Ken Buliw Over a year ago

While testing this out using the lists I originally posted, it seems like it starts from the beginning of s2 every time. While it works as one would expect, if you ask it to get the indexOf() c1 and c2 it will say that the matching 'a' from indexOf(c1) is at 2 and the indexOf(c2) is 0 -should be index 6. Interestingly enough if you take out the last 'a' it still says false (as it should). Why does it pull index 0 then?

Dawood ibn Kareem Over a year ago

Sorry, I don't understand what you're asking. You're saying it's doing the right thing but not in the way you're expecting? Presumably you're stepping through this with a debugger to tell you that? And it will actually pull out every element of s2 up until it finds the last character of s2 - it only compares them to s1 at the bottom of the inner loop.

|

Faisal Ali · Accepted Answer · 2014-04-05 18:11:12Z

1

Alternatively you can use Collections.indexOfSubList(List<?> source, List<?> target) Look at the java docs

answered Apr 5, 2014 at 18:11

Faisal Ali

1,13510 silver badges17 bronze badges

2 Comments

Ken Buliw Over a year ago

While that does look a lot more efficient, I can't use a collection. I need to use 2 ArrayLists and iterators.

yshavit Over a year ago

This will look for a substring, not generally a subsequence -- so it's not what the OP is asking for. (I made the same mistake in comments above. :) )

Collectives™ on Stack Overflow

Java ArrayList Iterator next() not working as intended

2 Answers 2

9 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related