Design an iterator for a collection of collections

Design an iterator for a collection of collections in java. The iterator should hide the nesting, allowing you to iterate all of the elements belonging to all of the collections as if you were working with a single collection

https://stackoverflow.com/questi ... tion-of-collections

sample solution

1. public class MultiIterator <T> implements Iterator<T>{
   
2. 
   
3.     private Iterator<? extends Collection<T>> it;
   
4.     private Iterator<T> innerIt;
   
5.     private T next;
   
6.     private boolean hasNext = true;
   
7. 
   
8.     public MultiIterator(Collection<? extends Collection<T>> collections) {
   
9.         it = collections.iterator();   
   
10.         prepareNext();
    
11.     }
    
12. 
    
13.     private void prepareNext() {
    
14.         do {
    
15.             if (innerIt == null || !innerIt.hasNext()) {
    
16.                 if (!it.hasNext()) {
    
17.                     hasNext = false;
    
18.                     return;
    
19.                 } else
    
20.                     innerIt = it.next().iterator();
    
21.             }
    
22.         } while (!innerIt.hasNext());
    
23. 
    
24.         next = innerIt.next();
    
25.     }
    
26. 
    
27.     @Override
    
28.     public boolean hasNext() {
    
29.         return hasNext;
    
30.     }
    
31. 
    
32.     @Override
    
33.     public T next() {
    
34.         if (!hasNext)
    
35.             throw new NoSuchElementException();
    
36.         T res = next;
    
37.         prepareNext();
    
38.         return res;
    
39.     }
    
40. 
    
41.     @Override
    
42.     public void remove() {
    
43.         //TODO
    
44.     }
    
45. 
    
46. }

复制代码

支持楼主大侠

Tree Iterator

1. /**
   
2. * An iterator that iterates through a tree using in-order tree traversal
   
3. * allowing a sorted sequence.
   
4. *
   
5. */
   
6. public class Iterator {
   
7. 
   
8.     private Stack<Node> stack = new Stack<>();
   
9.     private Node current;
   
10. 
    
11.     private Iterator(Node argRoot) {
    
12.         current = argRoot;
    
13.     }
    
14. 
    
15.     public Node next() {
    
16.         while (current != null) {
    
17.             stack.push(current);
    
18.             current = current.left;
    
19.         }
    
20. 
    
21. 
    
22.         current = stack.pop();
    
23.         Node node = current;
    
24.         current = current.right;
    
25. 
    
26.         return node;
    
27.     }
    
28. 
    
29.     public boolean hasNext() {
    
30.         return (!stack.isEmpty() || current != null);
    
31.     }
    
32. 
    
33.     public static Iterator iterator(Node root) {
    
34.         return new Iterator(root);
    
35.     }
    
36. }

复制代码

Given a list of k sorted iterators. Implement MergingIterator to merge them. If you are not familiar with Iterators check similar questions.

1. public interface Iterator {
   
2.   /**
   
3.    * [url=home.php?mod=space&uid=160137]@return[/url] True if the there is a next element
   
4.    */
   
5.   boolean hasNext();
   
6.   /**
   
7.    * @return next Highest number and removes the items from the stream.
   
8.    */
   
9.   int getNextHighestNumber();
   
10. }
    
11. 
    
12. class MergedIterator {
    
13.     List<Iterator> _listIters;
    
14.     PriorityQueue<Pair<?,?>> maxHeap;
    
15.   /**
    
16.    * Construct MergedIterator.
    
17.    * @param iterators list of iterator
    
18.    */
    
19.   MergedIterator(List<Iterator> iterators) {
    
20.       if (iterators == null || iterators.size() <= 0) throw new Exception("");
    
21.      _listIters = iterators;
    
22.      maxHeap = new PriorityQueue<Pair<Int, Iterator>, >(new MyCompartor());
    
23.      for (Iterator iter: _listIters) {
    
24.           if (iter.hasNext())
    
25.               maxHeap.insert(new Pair(iter.getNextHighestNumber(), iter));
    
26.       }
    
27.   }
    
28. 
    
29.   /**
    
30.    * @return true if there is a next element.
    
31.    */
    
32.   boolean hasNext() {
    
33.     return maxHeap.size() > 0;
    
34. }
    
35. 
    
36.   /**
    
37.    * @return next max element across all the iterators.
    
38.    */
    
39.   int getNextHighestNumber() {
    
40.       if (!hasNext()) throw new Exception("Empty");
    
41.       Pair pair = maxHeap.pop();
    
42.       int num = pair.getFirst();
    
43.       Iterator iter = pair.getSecond();
    
44.       if (iter.hasNext())
    
45.         maxHeap.insert(new Pair(iter.getNextHighestNumber(), iter));
    
46.       return num;
    
47. 
    
48.   }
    
49. 
    
50. }

复制代码

Deep Iterator

1. class DeepIterator implements Iterator<Object> {
   
2.     Stack<Iterator<Object>> itrs;
   
3.     Object curValue;
   
4.     public DeepIterator(ArrayList<Object> inputList) {
   
5.         itrs = new Stack<Iterator<Object>>();
   
6.         itrs.push(inputList.iterator());
   
7.     }
   
8.    
   
9.     @Override
   
10.     public boolean hasNext() {
    
11.        if (itrs.isEmpty()) {
    
12.            return false;
    
13.        }
    
14.        Iterator<Object> curIter = itrs.peek();
    
15.        while (curIter.hasNext()) {
    
16.            Object nextObj = curIter.next();
    
17.            if (obj instanceof ArrayList) {
    
18.                if ((ArrayList(obj)).size() == 0) {
    
19.                    continue;
    
20.                } else {
    
21.                    itrs.push((ArrayList(obj)).iterator());
    
22.                    return hasNext();
    
23.                }
    
24.            } else {
    
25.                curValue = (Object)nextObj;
    
26.                return true;
    
27.            }
    
28.            
    
29.        }
    
30.        itrs.pop();
    
31.        return hasNext();
    
32.     }
    
33. 
    
34.     @Override
    
35.     public Object next() {
    
36.         if (hasNext()) {
    
37.             return curValue;
    
38.         } else {
    
39.             return null;
    
40.         }
    
41.         
    
42.   
    
43.     }
    
44. }

复制代码