20-CS-4003-001 Organization of Programming Languages Fall 2017
Topological Sort

Lambda calculus, Type theory, Formal semantics, Program analysis

All lectures        Code               Code considerations        Demo

Topological Sort: Thread-based Solution

import java.net.*;
import java.util.*;
import java.io.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.applet.*;

// Stream declaration via threads
abstract class Stream implements Runnable {
   Object value;
   Thread runner = null;
   
   public Stream ()  {  }
   
   synchronized public void putIt (Object t) {
      value = t;
      notify();
      try { wait(); } catch (Exception e) {  }
   }

   synchronized public Object next () {
      if (runner != null)  notify();
      else {
         runner = new Thread(this);
         runner.start();
      }

      try { wait(); } catch (Exception e) {  }

      return value;
   }
}

// Note: this does not detect cycles
// Lots of fixes could make this look a bit more 
// elegant but are not worth the trouble here.
class Node extends Stream {
   Vector <Object> depends; // Dependent objects
   int idx;                 // Depends vector index
   String ident;            // Identity of this object
   boolean isNull;          // isNull = true -> finis

   Node (String id) {
      ident = id;
      idx = 0;
      isNull = false;
      depends = new Vector <Object> ();
   }

   // Set the dependencies
   void requires (Object sobject) {  
      depends.add(sobject);  
   }

   // As long as there are tokens in the current
   // Stream, output them.  When the current Stream is
   // closed (rest() returns NULL) switch to the next 
   // Stream, in order.  When all Streams are closed, 
   // send this object into the stream.
   public void run () {
      Object s = null;

      while (true) {
         if (!isNull) {
            while (idx < depends.size() &&
                   (s=((Node)(depends.get(idx))).next())
                    == null) idx++;
            // If some depedency stream is still open, 
            // put object s into stream
            if (idx < depends.size()) putIt(s);
            else {
               // All dependency streams are closed: 
               // put this object into the stream 
               // and set this object to null
               isNull = true;
               putIt(this);
            }
         } else {
            // Object is null, put null into the stream
            putIt(null);
         }
      }
   }
}

class TopoFrame 
   extends JFrame implements ActionListener {
   JTextArea text;
   JButton button;
   JComboBox combo;

   public TopoFrame () {
      setLayout(new FlowLayout());
      add(new JScrollPane(text = new JTextArea(30,20)));
      text.setFont(new Font("TimesRoman",Font.PLAIN,18));
      JPanel p = new JPanel();
      p.setLayout(new GridLayout(1,2));
      p.add(combo = new JComboBox());
      p.add(button = new JButton("Press Me"));
      add(p);
      combo.addItem("topo.0.dat");
      combo.addItem("topo.1.dat");
      button.addActionListener(this);
   }

   public void actionPerformed (ActionEvent evt) {
      int count = 0;
      Vector <Node> nodes = new Vector <Node> ();
      Object s;

      text.setText("");

      // Read data from file
      // Assume format of input file:
      //  name1 name2 name3 ...
      //  name1_depend1 name1_depend2 ... name1_dependk1
      //  name2_depend1 name2_depend2 ... name2_dependk2
      //  ...
      //  namen_depend1 namen_depend2 ... name2n_dependkn
      try {
         String file = (String)combo.getSelectedItem();
         String dir = "http://gauss.ececs.uc.edu/Courses"+
                      "/c4003/java/";
         String line = null;
         
         URL url = 
            new URL(dir+"DataDriven/Topological/"+file);
         InputStream is = (InputStream)url.getContent();
         ViewFrame vf = new ViewFrame(file,this);
         BufferedReader br = 
            new BufferedReader(new InputStreamReader(is));
         try {
            line = br.readLine();
            vf.append(line);
            StringTokenizer t = 
               new StringTokenizer(line," ");
            while (true) {
               String token = t.nextToken();
               nodes.add(new Node(token));
            }
         } catch (Exception e) { }
         
         count = 0;
         try {
            while (true) {
               line  = br.readLine();
               vf.append(line);
               StringTokenizer t = 
                  new StringTokenizer(line," ");
               try {
                  while (true) {
                     String str = t.nextToken();
                     int n = Integer.parseInt(str);
                     Node nd = (Node)nodes.get(count);
                     nd.requires(nodes.get(n));
                  }
               } catch (Exception f) { }
               count++;
            }
         }  catch (Exception e) { }
      } catch (Exception e) { 
         text.append("Error: "+e.toString()+"\n");
      }

      // Done reading data from file.
      // Do the topological sort.
      for (int i=0 ; i < count ; i++) {
         while ((s=((Node)(nodes.get(i))).next()) 
                != null) {
            text.append(((Node)s).ident+"\n");
         }
      }
   }
}

class ViewFrame extends JFrame {
   TopoFrame topo;
   JTextArea text;
   
   public ViewFrame (String file,TopoFrame t) {
      super(file);
      topo = t;
      add(new JScrollPane(text=new JTextArea(80,24)));
      setSize(500,500);
      setVisible(true);
   }
   
   public void append(String str) {
      text.append(str+"\n");
   }
}


public class topo 
   extends Applet implements ActionListener {
   JButton go;

   public void init () {
      setLayout(new BorderLayout());
      setBackground(new Color(255,255,223));
      add("Center", go = new JButton("Applet"));
      go.addActionListener(this);
   }

   public void actionPerformed (ActionEvent evt) {
      TopoFrame topo = new TopoFrame();
      topo.setSize(400,750);
      topo.setVisible(true);
   }
}
 -  The class Node to the left computes a topological sort of a given partial order of elements. Comments are in blue because there are many of them. The definition of Stream allows any object to be a member of a stream. Observe the interplay of notify, wait, and synchronized in the Stream class to support a putIt() method for putting tokens into the stream and a next() method for consuming them. The green lines highlight the Node class. Observe that the Node class subclasses the Stream class and is therefore a stream token producer. The run method of the Node class is where the stream tokens are produced. Objects of the Node class also consume tokens produced by other Node objects. The red lines in the code on the left show where this happens.