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: Stream Solution

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

// Stream declaration
class Stream {
   public Stream () { isNull = true; }
   public boolean isNull;
   public Object first;
   public Stream rest () { return null; }
}

// Note: this does not detect cycles
class Node extends Stream {
   Vector <Node> depends;  // List of dependent objects
   int ndepends,           // No. of dependent objects
       idx;                // Index into depends array
   String ident;           // Identity of this object
   Stream s;               // Used in Stream *rest().

   public Node (String id) {
      ident = id;          // Save identity
      idx = 0;
      depends = new Vector <Node> ();
      ndepends = 0;
      isNull = false;
   }

   // Set the dependencies
   void requires (Node dependency) {
      depends.add(dependency); ndepends++;
   }

   // 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 Stream rest () {
      if (isNull) return null;
      while (idx < ndepends &&
             (s=depends.get(idx).rest()) == null) idx++;
      if (idx < ndepends) return s;
      isNull = true;
      return this;
   }
}

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.dat");
      combo.addItem("topo.1.dat");
      combo.addItem("topo.0.dat");
      button.addActionListener(this);
   }

   public void actionPerformed (ActionEvent evt) {
      int count = 0;
      Vector  nodes = new Vector  ();
      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 s = t.nextToken();
                     int n = Integer.parseInt(s);
                     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))).rest())
                != 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 sf = new TopoFrame();
      sf.setSize(400,750);
      sf.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. This example is rather deep because the number of procedures through which a token must travel to reach the point of demand could be huge. In additon, the rest() procedure more complex than other stream examples. The red lines on the left show where the output stream is referenced by s. The green lines highlight the Node class.