001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 */ 019package org.apache.reef.io.storage; 020 021import org.apache.reef.io.Tuple; 022import org.apache.reef.io.storage.util.TupleKeyComparator; 023 024import java.util.Comparator; 025import java.util.Iterator; 026import java.util.PriorityQueue; 027 028public class MergingIterator<T> implements Iterator<T> { 029 private final PriorityQueue<Tuple<T, Iterator<T>>> heap; 030 031 public MergingIterator(final Comparator<T> c, final Iterator<T>[] its) { 032 this.heap = new PriorityQueue<>(11, new TupleKeyComparator<T, Iterator<T>>(c)); 033 034 for (final Iterator<T> it : its) { 035 final T b = it.hasNext() ? it.next() : null; 036 if (b != null) { 037 heap.add(new Tuple<>(b, it)); 038 } 039 } 040 } 041 042 @Override 043 public boolean hasNext() { 044 return heap.size() != 0; 045 } 046 047 @Override 048 public T next() { 049 final Tuple<T, Iterator<T>> ret = heap.remove(); 050 if (ret.getValue().hasNext()) { 051 heap.add(new Tuple<>(ret.getValue().next(), ret.getValue())); 052 } 053 return ret.getKey(); 054 } 055 056 @Override 057 public void remove() { 058 throw new UnsupportedOperationException( 059 "Cannot remove entires from MergingIterator!"); 060 } 061}