Interview: Concevoir un itérateur pour une collection de collections

Question

Concevoir un itérateur pour une collection de collections dans Java. L'itérateur doit masquer l'imbrication, vous permettant d'itérer tous les éléments appartenant à toutes les collections comme si vous travailliez avec une seule collection.

Answer 1

Voici une implémentation possible. Notez que je suis parti supprimer() non implémenté:

public class MultiIterator <T> implements Iterator<T>{ 

    private Iterator<? extends Collection<T>> it; 
    private Iterator<T> innerIt; 
    private T next; 
    private boolean hasNext = true; 

    public MultiIterator(Collection<? extends Collection<T>> collections) { 
     it = collections.iterator();  
     prepareNext(); 
    } 

    private void prepareNext() { 
     do { 
      if (innerIt == null || !innerIt.hasNext()) { 
       if (!it.hasNext()) { 
        hasNext = false; 
        return; 
       } else 
        innerIt = it.next().iterator(); 
      } 
     } while (!innerIt.hasNext()); 

     next = innerIt.next(); 
    } 

    @Override 
    public boolean hasNext() { 
     return hasNext; 
    } 

    @Override 
    public T next() { 
     if (!hasNext) 
      throw new NoSuchElementException(); 
     T res = next; 
     prepareNext(); 
     return res; 
    } 

    @Override 
    public void remove() { 
     //TODO 
    } 

} 

Answer 2

D'abord, jetez un oeil à l'implémentation de l'itérateur dans java.util. LinkedList

http://www.docjar.com/html/api/java/util/LinkedList.java.html

de là, votre tâche est facile de mettre en œuvre un seul itérateur qui tient compte du fait qu'il est itérez collections.

Cordialement.

Answer 3

si tout ce que vous devez travailler avec est le iterator java: qui vient de faire hasNext(), à côté() et remove(), je me suis dit que vous devez faire le tour il.

Procédez comme si vous traitez un tableau 2D, c'est-à-dire avec une boucle externe et une boucle interne, car elles ont le même "arrangement" mais un type de données différent. Au fur et à mesure que vous traitez, vous les transférez dans une nouvelle collection.

alors peut-être une méthode privée:

private void convertToSingleCollection() 
    { 


     while("column") 
     { 
      //convert the "column" to an arra 


      for("Row") 
      { 
      //add to newCollection here 
      } 

      //remove the processed column from CollectionOFcollection 
     } 
    } 
    //call the above method in your constructor 


    public iterator<T> Iterator() 
    { 
     newCollection.iterator(); 
    } 

    public boolean hasNext() 
    { 
     return Iterator().hasNext() 
    } 

    public T next() 
    { 
     if(!hasNext()) 
     { 
     //exception message or message 
     } 
     else 
      //return "next" 
    } 

fin

J'espère que cela aide. Il devrait y avoir d'autres façons de le résoudre, je suppose.

Answer 4

En this post vous pouvez voir deux implémentations, la seule différence (mineure) est qu'il prend un itérateur d'itérateurs au lieu d'une collection de collections. Cette différence combinée à l'exigence d'itérer les éléments de façon circulaire (exigence non demandée par l'OP dans cette question) ajoute le surcoût de la copie des itérateurs dans une liste.

La première approche est paresseux: il itérer un élément que lorsque cet élément est demandé, le « prix » que nous devons payer est que le code est plus complexe car il doit gérer des carres cas:

import java.util.Iterator; 
import java.util.LinkedList; 
import java.util.List; 
import java.util.NoSuchElementException;  

public class MultiIterator<E> implements Iterator { 

    List<Iterator<E>> iterators = new LinkedList<>(); 
    Iterator<E> current = null; 

    public MultiIterator(Iterator<Iterator<E>> iterator) { 
     // copy the iterators into a list 
     while (iterator.hasNext()) { 
      iterators.add(iterator.next()); 
     } 
    } 

    @Override 
    public boolean hasNext() { 
     boolean result = false; 
     if (iterators.isEmpty() && (current == null || !current.hasNext())) { 
      return false; 
     } 

     if (current == null) { 
      current = iterators.remove(0); 
     } 

     while (!current.hasNext() && !iterators.isEmpty()) { 
      current = iterators.remove(0); 
     } 

     if (current.hasNext()) { 
      result = true; 
     } 
     return result; 
    } 

    @Override 
    public E next() { 
     if (current == null) { 
      try { 
       current = iterators.remove(0); 
      } catch (IndexOutOfBoundsException e) { 
       throw new NoSuchElementException(); 
      } 
     } 
     E result = current.next(); // if this method was called without checking 'hasNext' this line might raise NoSuchElementException which is fine 
     iterators.add(current); 
     current = iterators.remove(0); 
     return result; 
    } 

    // test 
    public static void main(String[] args) { 
     List<Integer> a = new LinkedList<>(); 
     a.add(1); 
     a.add(7); 
     a.add(13); 
     a.add(17); 
     List<Integer> b = new LinkedList<>(); 
     b.add(2); 
     b.add(8); 
     b.add(14); 
     b.add(18); 
     List<Integer> c = new LinkedList<>(); 
     c.add(3); 
     c.add(9); 
     List<Integer> d = new LinkedList<>(); 
     d.add(4); 
     d.add(10); 
     d.add(15); 
     List<Integer> e = new LinkedList<>(); 
     e.add(5); 
     e.add(11); 
     List<Integer> f = new LinkedList<>(); 
     f.add(6); 
     f.add(12); 
     f.add(16); 
     f.add(19); 
     List<Iterator<Integer>> iterators = new LinkedList<>(); 
     iterators.add(a.iterator()); 
     iterators.add(b.iterator()); 
     iterators.add(c.iterator()); 
     iterators.add(d.iterator()); 
     iterators.add(e.iterator()); 
     iterators.add(f.iterator()); 
     MultiIterator<Integer> it = new MultiIterator<>(iterators.iterator()); 
     while (it.hasNext()) { 
      System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19, 
     } 
    } 
} 

et le second (« gourmand » copie de tous les éléments de tous les itérateurs dans l'ordre demandé dans une liste et retourner un itérateur à cette liste):

import java.util.Iterator; 
import java.util.LinkedList; 
import java.util.List; 

public class MultiIterator<E> { 

    Iterator<Iterator<E>> iterator = null; 
    List<E> elements = new LinkedList<>(); 

    private MultiIterator(Iterator<Iterator<E>> iterator) { 
     this.iterator = iterator; 
    } 

    private void copyElementsInOrder() { 
     List<Iterator<E>> iterators = new LinkedList<>(); 
     // copy the iterators into a list 
     while (iterator.hasNext()) { 
      iterators.add(iterator.next()); 
     } 
     // go over the list, round-robin, and grab one 
     // element from each sub-iterator and add it to *elements* 
     // empty sub-iterators will get dropped off the list 
     while (!iterators.isEmpty()) { 
      Iterator<E> subIterator = iterators.remove(0); 
      if (subIterator.hasNext()) { 
       elements.add(subIterator.next()); 
       iterators.add(subIterator); 
      } 
     } 
    } 

    public static <E> Iterator<E> iterator(Iterator<Iterator<E>> iterator) { 
     MultiIterator<E> instance = new MultiIterator<>(iterator); 
     instance.copyElementsInOrder(); 
     return instance.elements.iterator(); 
    } 

    // test 
    public static void main(String[] args) { 
     List<Integer> a = new LinkedList<>(); 
     a.add(1); 
     a.add(7); 
     a.add(13); 
     a.add(17); 
     List<Integer> b = new LinkedList<>(); 
     b.add(2); 
     b.add(8); 
     b.add(14); 
     b.add(18); 
     List<Integer> c = new LinkedList<>(); 
     c.add(3); 
     c.add(9); 
     List<Integer> d = new LinkedList<>(); 
     d.add(4); 
     d.add(10); 
     d.add(15); 
     List<Integer> e = new LinkedList<>(); 
     e.add(5); 
     e.add(11); 
     List<Integer> f = new LinkedList<>(); 
     f.add(6); 
     f.add(12); 
     f.add(16); 
     f.add(19); 
     List<Iterator<Integer>> iterators = new LinkedList<>(); 
     iterators.add(a.iterator()); 
     iterators.add(b.iterator()); 
     iterators.add(c.iterator()); 
     iterators.add(d.iterator()); 
     iterators.add(e.iterator()); 
     iterators.add(f.iterator()); 
     Iterator<Integer> it = MultiIterator.<Integer>iterator(iterators.iterator()); 
     while (it.hasNext()) { 
      System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19, 
     } 
    } 
} 

I inclus un « test » simple, code afin de montrer la façon d'utiliser le MultiIterator, ce n'est pas toujours trivial (en raison de l'utilisation de génériques) comme vous pouvez le voir sur la ligne:

Iterator<Integer> it = MultiIterator.<Integer>iterator(iterators.iterator());