jcsp.plugNplay.ints
Class MergeInt

java.lang.Object
  |
  +--jcsp.plugNplay.ints.MergeInt

All Implemented Interfaces:

CSProcess

public final class MergeInt

extends Object

implements CSProcess

Merges an array of strictly increasing int input streams into one strictly increasing output stream.

Process Diagram

     in[0] +----------+
    ------>|          |
       :   |          | out
       :   | MergeInt |----->
   in[n-1] |          |
    ------>|          |
           +----------+
 

Description

MergeInt is a process whose output stream is the ordered merging of the integers on its input streams. It assumes that each input stream is strictly increasing (i.e. with no repeats) sequence of integers. It generates a strictly increasing output stream containing all -- and only -- the numbers from its input streams (eliminating any duplicates).

Warning: this process assumes that its input channel array has at least two elements.

Channel Protocols

Input Channels
in[]	int	Assume: in.length >= 2.
Output Channels
out	int	All channels in this package carry integers.

Example

The following example shows how to use MergeInt in a small program. The program also uses some of the other plugNplay processes. The program prints, in ascending order (up to Integer.MAX_VALUE), all integers whose prime factors consist only of 2, 3 and 5. Curious readers may like to reason why the infinitely buffered channels are needed.

 import jcsp.lang.*;
 import jcsp.util.ints.*;
 
 public final class MergeIntExample {
 
   public static void main (String[] argv) {
 
     final One2OneChannelInt[] a = One2OneChannelInt.create (4);
     final One2OneChannelInt[] b = One2OneChannelInt.create (3,
                                     new InfiniteBufferInt ());
     final One2OneChannelInt c = new One2OneChannelInt ();
     final One2OneChannelInt d = new One2OneChannelInt ();
 
     new Parallel (
       new CSProcess[] {
         new MultInt (2, a[0], b[0]),
         new MultInt (3, a[1], b[1]),
         new MultInt (5, a[2], b[2]),
         new MergeInt (b, c),
         new PrefixInt (1, c, d),
         new DeltaInt (d, a),
         new PrinterInt (a[3], "--> ", "\n")
       }
     ).run ();
 
   }
 
 }
 

Implementation Note

The implementation sets up a balanced binary tree of parallel Merge2Int processes to fan-in the merge from its external input channels to its external output. It's a nice example of recursion and parallelism -- here's the run method:

   public void run () {
     final int n = in.length;  // deduce: n >= 2
     switch (n) {
       case 2:
         new Merge2Int (in[0], in[1], out).run ();
       break;
       case 3:
         final One2OneChannelInt c = new One2OneChannelInt ();
         new Parallel (
           new CSProcess[] {
             new Merge2Int (in[0], in[1], c),
             new Merge2Int (c, in[2], out)
           }
         ).run ();
       break;
       default:  // deduce: n >= 4
         final int n2 = n/2;
         ChannelInputInt[] bottom = new ChannelInputInt[n2];
         ChannelInputInt[] top = new ChannelInputInt[n - n2];
         for (int i = 0; i < n2; i++) {
           bottom[i] = in[i];
         }
         for (int i = n2; i < n; i++) {
           top[i - n2] = in[i];
         }
         final One2OneChannelInt[] d = One2OneChannelInt.create (2);
         new Parallel (
           new CSProcess[] {
             new MergeInt (bottom, d[0]),
             new MergeInt (top, d[1]),
             new Merge2Int (d[0], d[1], out)
           }
         ).run ();
       break;
     }
   }
 

Author:

P.H.Welch

See Also:

Merge2Int

Constructor Summary

MergeInt(ChannelInputInt[] in, ChannelOutputInt out)
Construct a new Merge2Int process with the input channels inand the output channel out.

Method Summary

void	run() The main body of this process.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MergeInt

public MergeInt(ChannelInputInt[] in,
                ChannelOutputInt out)

Construct a new Merge2Int process with the input channels inand the output channel out. The ordering of the input channels makes no difference to the behaviour of this process.

Parameters:

in - the input channels

out - the output channel

Method Detail

run

public void run()

The main body of this process.

Specified by:

run in interface CSProcess