01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package algs24;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac Multiway.java
 *  Execution:    java Multiway input1.txt input2.txt input3.txt ...
 *  Dependencies: IndexMinPQ.java In.java StdOut.java
 *
 *  Merges together the sorted input stream given as command-line arguments
 *  into a single sorted output stream on standard output.
 *
 *  % more m1.txt
 *  A B C F G I I Z
 *
 *  % more m2.txt
 *  B D H P Q Q
 *
 *  % more m3.txt
 *  A B E F J N
 *
 *  % java Multiway m1.txt m2.txt m3.txt
 *  A A B B B C D E F F G H I I J N P Q Q Z
 *
 *************************************************************************/

public class Multiway {

  public static void merge(In[] streams) {
    int N = streams.length;
    IndexMinPQ<String> pq = new IndexMinPQ<>(N);

    // read the first String from each stream
    for (int i = 0; i < N; i++)
      if (!streams[i].isEmpty())
        pq.insert(i, streams[i].readString());

    // Extract and print min and read next from its stream.
    while (!pq.isEmpty()) {
      StdOut.print(pq.minKey() + " ");
      int i = pq.delMin();
      if (!streams[i].isEmpty())
        pq.insert(i, streams[i].readString());
    }
    StdOut.println();
  }

  public static void main(String[] args) {
    args = new String[] { "data/m1.txt", "data/m2.txt", "data/m3.txt" };
    int N = args.length;
    In[] streams = new In[N];
    for (int i = 0; i < N; i++)
      streams[i] = new In(args[i]);
    merge(streams);
  }
}