Multi-Way Streams & Merge
I thought this was a reasonable although not perfect solution
to the online midterm exam
interface TokenInterface
{
public String type(); // What kind of token it is
public String value(); // What the value of the token is
}
abstract class Token implements TokenInterface {}
// Top of token hierarchy
// The token class can be extended to include any kind of token.
// The examples below create integer and String tokens.
class intToken extends Token
{
private int i; // data for integer token
public intToken(int j) {i=j;}
public String type() {return "integer ";}
public String value() {return Integer.toString(i);}
}
class stringToken extends Token
{
private String s; // data for string token
public stringToken(String str) {s=str;}
public String type() {return "string ";}
public String value() {return s;}
}
/*
Code to implement a singly-linked list of tokens.
This list is used to store the tokens generated for a given
producer. Each monitor object will contain one such list.
*/
class Node
{
public Token t;
public Node next;
public Node(Token a) { t=a; next=null; }
}
class List
{
private Node head;
public List() { head = null; }
public void Add(Token t)
{
if (head == null) { head = new Node(t); return; }
Node a = head;
while(a.next != null) { a = a.next; } //traverse to end of list
a.next = new Node(t); //add to end of list
}
//Returns the x'th token in the list, if it exists
public Token getToken(int tokenNumber)
{
if (head == null) { return null; }
Node a = head;
for (int i=0 ; i != tokenNumber ; i++)
{
if (a.next == null) { return null; }
a = a.next; //go to node number tokenNumber
}
return a.t;
}
}
/*
End of linked list code
*/
/*
The Monitor class acts as a middleman between the producer and
consumer. Whenever the consumer needs a token, it asks the monitor to
provide it. The monitor also stores the tokens that are generated by
the producer so that they are not generated more than once. If the
token that a consumer wants has not been generated yet, the monitor
"kicks" the producer into generating that token.
*/
class Monitor
{
private List tokenList=new List(); //list to hold generated tokens
//Returns the x'th token generated by the producer.
//Gets this token from the list of generated tokens if it has
//been generated already but will force the producer to make
//it if it hasn't. If the token must be generated, we notify() the
//producer and then immediately wait() for the producer to notify()
//when it has finished generating the token
public synchronized Token get(int tokenNumber)
{
Token t = tokenList.getToken(tokenNumber);
if (t != null)
{
return t;
} else {
notify(); // wake up the producer
try
{
wait(); // wait until the producer is done
} catch (InterruptedException e){}
return tokenList.getToken(tokenNumber);
}
}
//puts a generated token onto the list and the waits until another
//token is needed. If this is the last token, don't wait.
public synchronized void put(Token t, String name)
{
tokenList.Add(t);
System.out.println(name + "\t put \t" + t.type() + t.value());
notify(); // notify the consumer(s) that we're done generating
// the token
try
{
wait();
} catch (InterruptedException e){}
}
}
class Consumer extends Thread
{
static int numConsumers=0; // keep track of how many consumers running
private Monitor Mon;
private String name;
private int tokens=10; //number of tokens to consume
public Consumer(Monitor m, String name)
{
Mon = m;
this.name = name;
++numConsumers;
}
public void run()
{
String value;
Token t;
for (int i = 0; i < tokens; i++)
{
System.out.println( name + "\t requests \ttoken number "+i+".");
t = Mon.get(i);
if( t != null)
{
System.out.println( name + "\t got \t"+ t.type() + t.value());
}
try
{
sleep((int)(Math.random() * 100)); //wait for a while
}
catch (InterruptedException e) { }
}
--numConsumers;
if (numConsumers == 0)
{
System.exit(0); //exit when we are done consuming
}
}
}
// Produces increasing numbers
class Producer extends Thread
{
protected Monitor Mon;
protected String name;
public Producer(Monitor m, String name)
{
Mon = m;
this.name = name;
}
public void run()
{
int i=0;
while(true)
{
System.out.println("New Integer Token: "+i);
Mon.put(new intToken(i++), name);
}
}
}
// Produces prime numbers
class PrimesProducer extends Producer
{
private int primes[] = {1,2,3,5,7,11,13,17,19,23};
public PrimesProducer(Monitor m, String name)
{
super(m,name);
}
public void run()
{
int i=0;
while(true)
{
System.out.println("New Prime Token: "+i);
Mon.put(new intToken(primes[i++]),name);
}
}
}
// Produces incrementing characters
class LetterProducer extends Producer
{
public LetterProducer(Monitor m, String name)
{
super(m,name);
}
public void run()
{
char letter[]={'a'};
while(true)
{
System.out.println("New Letter Token: "+letter);
Mon.put(new stringToken(new String(letter)),name);
letter[0]++;
}
}
}
// On even numbers generate a number. On odd numbers generate a char
class MixedProducer extends Producer
{
public MixedProducer(Monitor m, String name)
{
super(m,name);
}
public void run()
{
char letter[]={'a'};
int i=0;
while(true)
{
if (i%2 == 0) // even
{
Mon.put(new intToken(i),name);
} else {
Mon.put(new stringToken(new String(letter)),name);
letter[0]++;
}
i++;
}
}
}
class MergeProducer extends Producer
{
private Monitor source1,source2; // Monitors for two incoming producers
private Token t1, t2;
public MergeProducer(Monitor m1, Monitor m2, Monitor m, String name)
{
super(m,name);
source1 = m1;
source2 = m2;
}
public void run()
{
int s1tokenNum=0;
int s2tokenNum=0;
t1=source1.get(s1tokenNum);
t2=source2.get(s2tokenNum);
int i=0;
while(true)
{
if (Integer.parseInt(t1.value()) < Integer.parseInt(t2.value()))
{
Mon.put(t1,name);
t1=source1.get(++s1tokenNum);
}
else
{
Mon.put(t2,name);
t2=source2.get(++s2tokenNum);
}
}
}
}
/********************************************************************
In my implementation, there is one monitor for every producer. Many
consumers can connect to a monitor. Consumers request tokens by using
the Monitor.get method with a parameter indicating which token the
consumer would like to recieve. If the desired token has already been
made, it is sent to the consumer, If the desired token has not been
generated yet, the monitor wakes up the producer and waits for it to
make the token.
*******************************************************************/
class Midterm
{
public static void main(String[] args)
{
Monitor m = new Monitor();
Monitor m2 = new Monitor();
Monitor m3 = new Monitor();
Monitor m4 = new Monitor();
Monitor m5 = new Monitor();
// a generic producer attached to Monitor m
Producer p1 = new Producer(m, "Prod");
// a prime number producer attached to Monitor m2
PrimesProducer p2 = new PrimesProducer(m2, "PrimesProd");
// a successive character generator attached to Monitor m3
LetterProducer p3 = new LetterProducer(m3, "LetterProd");
// a mixed producer of integers and strings attached to Monitor m4
MixedProducer p4 = new MixedProducer(m4, "MixedProd");
// a producer that merges two integer streams. This one merges
// the natural producer and the primes producer.
MergeProducer p5 = new MergeProducer(m,m2,m5,"MergeProd");
//The number of tokens consumed can be set in the Consumer class
//declaration. The current setting is 10
/* //Basic multiple consumer example
Consumer c1 = new Consumer(m, "Cons1");
Consumer c2 = new Consumer(m, "Cons2");
Consumer c3 = new Consumer(m, "Cons3");
c1.start();
c2.start();
c3.start();
p1.start();
*/
/* //Multiple consumers of a string token producer
Consumer c1 = new Consumer(m3, "Cons1");
Consumer c2 = new Consumer(m3, "Cons2");
c1.start();
c2.start();
p3.start();
*/
/* //Multiple consumers of a mixed-type producer
Consumer c1 = new Consumer(m4, "Cons1");
Consumer c2 = new Consumer(m4, "Cons2");
c1.start();
c2.start();
p4.start();
*/
//PART 2 -- Producer that merges two streams
//for ease of viewing, I only used one consumer
//but others could be easily added.
//The best way to view the results of this is by
//using a grep filter, eg:
//java Midterm|grep MereCons
Consumer c1 = new Consumer(m5, "MergeCons");
c1.start();
p1.start();
p2.start();
p5.start();
}
}