Combining lists using iterators

Question

I need to combine two list of strings in java, and I'm not sure if this is the best way to do this. I have to use iterators and compareTo () method. For instance...

Example: L1: A, B, C, D L2: B, D, F, G result: A, B, B, C, D, D, F, G

I can assume that the input lists are already sorted, and I cannot use the contains () method. I have some initial checks, but the while loop is what I'm stuck with.

public static ListADT<String> merge(ListADT<String> L1,ListADT<String> L2) throws BadListException { ListADT<String> L3 = new ArrayList<String>; if(L1 == null || L2 == null) { throw new BadListException(); } Iterator<String> itr1 = new L1.iterator(); Iterator<String> itr2 = new L2.iterator(); if(L1.size() == 0 && L2.size() == 0) { return L3; } if(L1.size() == 0 && L2.size() != 0) { for(int i = 0; i < L2.size(); i++) { return L3.add(L2.get(i)); } } if(L2.size() == 0 && L1.size() != 0) { for(int i = 0; i < L1.size(); i++) { return L3.add(L1.get(i)); } } while(itr1.hasNext() || irt2.hasNext()) { //merge the lists here? } 

}

Any help would be appreciated.

Answer 1

It is quite simple if you just use variables to hold the current value from each iterator. This solution assumes that your lists do not contain null , but it is easy to add null processing because the lists are sorted.

 package com.example; import java.util.ArrayList; import java.util.Arrays; import java.util.Iterator; import java.util.List; public class IteratorMerge { /** * @param args */ public static void main(String[] args) { List<String> list1 = Arrays.asList(new String[]{"A", "B", "C", "D"}); List<String> list2 = Arrays.asList(new String[]{"B", "D", "F", "G"}); System.out.println(merge(list1, list2)); } public static List<String> merge(List<String> L1,List<String> L2) { List<String> L3 = new ArrayList<String>(); Iterator<String> it1 = L1.iterator(); Iterator<String> it2 = L2.iterator(); String s1 = it1.hasNext() ? it1.next() : null; String s2 = it2.hasNext() ? it2.next() : null; while (s1 != null && s2 != null) { if (s1.compareTo(s2) < 0) { // s1 comes before s2 L3.add(s1); s1 = it1.hasNext() ? it1.next() : null; } else { // s1 and s2 are equal, or s2 comes before s1 L3.add(s2); s2 = it2.hasNext() ? it2.next() : null; } } // There is still at least one element from one of the lists which has not been added if (s1 != null) { L3.add(s1); while (it1.hasNext()) { L3.add(it1.next()); } } else if (s2 != null) { L3.add(s2); while (it2.hasNext()) { L3.add(it2.next()); } } return L3; } } 

Answer 2

Here is some pseudo code for the basic algorithm:

 while(itr1 && itr2) { if(itr1 value < it2 value) add itr1 to list increment itr1 else add itr2 to list increment itr2 } check if itr1 or itr2 still have more elements while itr1 or itr2 has more elements, add those elements to the list 

We know that lists are sorted, so at each stage we just grab the smallest element from each list and add it to the combined list. If at the end one of the iterators is exhausted and the other is not, then we can simply iterate over the one that still has elements, adding each element in turn to the combined list.

As you saw, doing it with Iterators in Java is a little painful since next() removes the element. One way around this is to use two Queue s, one for each iterator, that store values ​​from the call to next() . Then you need to compare the head of each queue by adding a minimum to the combined list and then removing it from the corresponding Queue .

Answer 3

As you have already found, it is just a pain to join with iterators. Let me explicitly point out why:

• For each step of the merge, you want to check the first element of both sequences, but you only want to move through one .
• Iterator#next() combines these checks and preliminary operations into one operation, so it is impossible to check the head of both sequences without missing both.

You need a way to look at the first element in Iterator without promoting it. If you had this ability, the merger would look something like this:

 public <T extends Comparable<T>> List<T> merge(Iterator<T> it1, Iterator<T> it2) { PeekableIterator<T> seq1 = new PeekableIterator<T>(it1); PeekableIterator<T> seq2 = new PeekableIterator<T>(it2); List<T> merged = new ArrayList<T>(); while (seq1.hasNext() && seq2.hasNext()) { if (seq1.peekNext().compareTo(seq2.peekNext()) < 0) { merged.add(seq1.next()); } else { merged.add(seq2.next()); } } while (seq1.hasNext()) { merged.add(seq1.next()); } while (seq2.hasNext()) { merged.add(seq2.next()); } return merged; } 

And it turns out that creating this PeekableIterator not difficult! You just need to keep track of whether you currently have a peeked element and what that element is.

 public class PeekableIterator<T> implements Iterator<T> { private final Iterator<T> backing; private boolean havePeek = false; private T peek; public PeekableIterator(Iterator<T> backing) { this.backing = backing; } @Override public boolean hasNext() { return havePeek || backing.hasNext(); } @Override public T next() { if (havePeek) { havePeek = false; return peek; } else { return backing.next(); } } public T peekNext() { if (!havePeek) { peek = backing.next(); havePeek = true; } return peek; } @Override public void remove() { throw new UnsupportedOperationException(); } } 

EDIT

I did not notice the comment above, referring to PeekingIterator in the Google Guava library, which here is more or less similar to PeekableIterator . If you have access to third-party libraries, this would certainly be preferable if you moved your own.

Answer 4

Do not try to manage merging an empty list with a non-empty one as a special case, just loop until at least one of the iterators is valid and does your work right there:

 public static ListADT<String> merge(ListADT<String> L1,ListADT<String> L2) throws BadListException { ListADT<String> L3 = new ArrayList<String>; Iterator<String> itr1 = new L1.iterator(), itr2 = new L2.iterator(); while (itr1.hasNext() || itr2.hasNext()) { if (!itr1.hasNext()) L3.add(itr2.next()); else if (!itr2.hasNext()) L3.add(itr1.next()); else { String s1 = peek from itr1 String s2 = peek from itr2; if (s1.compareTo(s2) < 0) { L3.add(itr1.next()); L3.add(itr2.next()); } else { L3.add(itr2.next()); L3.add(itr1.next()) } } } } 

Answer 5

public class MergeIterator {

 public static void main(String[] args) { List<String> s1 = new ArrayList<String>(); s1.add("a"); s1.add("z"); s1.add("b"); s1.add("k"); s1.add("c"); Collections.sort(s1); List<String> s2 = new ArrayList<String>(); s2.add("p"); s2.add("a"); s2.add("d"); s2.add("n"); s2.add("m"); Collections.sort(s2); Iterator<String> it1 = s1.iterator(); // sortIterator(it1); Iterator<String> it2 = s2.iterator(); System.out.println(); combine(it1, it2); } private static Iterator<String> combine(Iterator<String> it1, Iterator<String> it2) { Iterator<String> it3 = null; List<String> l1 = new ArrayList<>(); String s1 = null, s2 = null; while (it1.hasNext() || it2.hasNext()) { //line 1 s1 = (s1 == null ? (it1.hasNext() ? it1.next() : null) : s1); //line 2 s2 = (s2 == null ? (it2.hasNext() ? it2.next() : null) : s2); // line 3 if (s1 != null && s1.compareTo(s2) < 0) { // line 4 l1.add(s1); s1 = null; } else { l1.add(s2); s2 = null; } } it3 = l1.iterator(); return it3; } 

}