Как слить два интервала Iterable?

Question

[gleendo]

Есть метод interval возвращающий интервал [left, right).

class IteratorUtils {
    public static Iterable<Integer> interval(int left, int right) {
        return new IntervalIterable(left, right);
    }

    public static Iterable<Integer> merge(Iterable<Integer> iter0, Iterable<Integer> iter1) {
        // some code
    }
}

class IntervalIterable implements Iterable<Integer> {
    private final int left;
    private final int right;

    public IntervalIterable(int left, int right) {
        this.left = left;
        this.right = right;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new IntervalIterator(left, right);
    }
}

class IntervalIterator implements Iterator<Integer> {
    private final int max;
    private int current;

    public IntervalIterator(int left, int right) {
        this.max = right;
        this.current = left;
    }

    public boolean hasNext() {
        return current < max;
    }

    public Integer next() {
        return current++;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}

Теперь нужно написать метод merge, который будет сливать 2 интервала.

Использование:

for (int k : merge(interval(10, 12), interval(10, 12))) {
     System.out.print(k + " "); // 10 10 11 11
}

Как теперь реализовать это слияние? Алгоритм слияния двух массивов мне понятен, а вот как написать слияние двух интервалов не могу надумать. Подскажите пожалуйста, как реализовать решение.

Answer 1

[Денис Загаевский]

Всё то же самое - реализуете Iterable, который возвращает Iterator, у которого реализуете next и hasNext. Iterator должен хранить два других итератора, которые будет опрашивать по очереди d next/hasNext.

Comments

[gleendo]

Денис Загаевский Вот это мне понятно, вот я написал сами классы. Но мне не понятен сам алгоритм. Точнее не понятно как организовать проверку на то что еще есть элементы в 2 интервалах. Что делать если один интервал закончится. Как проитерировать другой интервал и завершить вывод? В общем вообще хз как реализовать это.

class MergeIterable implements Iterable<Integer> {
    private final Iterable<Integer> iter0;
    private final Iterable<Integer> iter1;

    public MergeIterable(Iterable<Integer> iter0, Iterable<Integer> iter1) {
        this.iter0 = iter0;
        this.iter1 = iter1;
    }

    public Iterator<Integer> iterator() {
        return new MergeIterator(iter0, iter1);
    }
}

class MergeIterator implements Iterator<Integer> {
    private final Iterable<Integer> iter0;
    private final Iterable<Integer> iter1;

    public MergeIterator(Iterable<Integer> iter0, Iterable<Integer> iter1) {
        this.iter0 = iter0;
        this.iter1 = iter1;
    }

    public boolean hasNext() {

    }

    public Integer next() {

    }
}

[gleendo]

Денис Загаевский И как написать метод hasNext(), в случае чего возвращать false? Вот это мне не понятно

[Денис Загаевский]

evg_: ну вот вы храните Iterabel iter0, iter1, а надо - Iterator.

boolean firstNow = true;
hasNext(){
return firstNow ? iter0.hasNext() : iter1.hasNext();
}

ну и всё в таком духе.

[Денис Загаевский]

evg_: естественно, надо предумотреть случаи, когда в одном итераторе больше элементов, чем в другом - я не знаю, что вам надо тогда делать.