Contents

Einführung

Ziel der Vorlesung

Chapter 1
Frühe und späte Bindungen

1.1  Wiederholung: Das Prinzip der späten Bindung

Beispiel:
Wir sehen zunächst eine Schnittstelle vor. Dieses wäre zur Verdeutlichung der späten Bindung nicht unbedingt notwendig. Objekte, die diese Schnittstelle implementieren, sollen eine Methode getDescription enthalten.

package name.panitz.lateBinding;

public interface Descriptable{
  String getDescription();
}

package name.panitz.lateBinding;

public class Upper implements Descriptable{
  public String getDescription(){return "Upper";} 
}

package name.panitz.lateBinding;

public class Lower extends Upper{
  public String getDescription(){return "Lower";}

  public static void main(String[] _){
    Upper up = new Upper();
    Upper lo = new Lower();
    System.out.println(up.getDescription());
    System.out.println(lo.getDescription());
    Descriptable des = up;
    System.out.println(des.getDescription());
    des = lo;
    System.out.println(des.getDescription());
  }
}

sep@linux:~/fh/prog2/examples> java -classpath classes/ name.panitz.lateBinding.Lower
Upper
Lower
Upper
Lower
sep@linux:~/fh/prog2/examples>

1.2  Keine späte Bindung für Felder

package name.panitz.lateBinding;

class Ente {
  int beine = 2;
  int getBeine(){return beine;}
  int getWirklicheBeine(){return beine;}
}

package name.panitz.lateBinding;

class LahmeEnte extends Ente {
  int beine = 1;
  int getWirklicheBeine(){return beine;}
}

package name.panitz.lateBinding;

class EntenTest {
  public static void main(String [] args){
    Ente ente1 = new Ente(); 
    LahmeEnte ente2 = new LahmeEnte(); 
    Ente ente3 = ente2;

    System.out.println("Ente ente1 = new Ente()");
    System.out.println("beine: "+ente1.beine);
    System.out.println("getBeine(): "+ente1.getBeine());
    System.out.println(
     "getWirklicheBeine(): "+ente1.getWirklicheBeine());

    System.out.println(
     "\nLahmeEnte ente2 = new LahmeEnte()");
    System.out.println("beine: "+ente2.beine);
    System.out.println("getBeine(): "+ente2.getBeine());
    System.out.println(
     "getWirklicheBeine(): "+ente2.getWirklicheBeine());

    System.out.println("\nEnte ente3 = new LahmeEnte()");
    System.out.println("beine: "+ente3.beine);
    System.out.println("getBeine(): "+ente3.getBeine());
    System.out.println(
     "getWirklicheBeine(): "+ente3.getWirklicheBeine());
  }
}

sep@swe10:~/fh/prog2/beispiele> java name.panitz.lateBinding.EntenTest
Ente ente1 = new Ente()
beine: 2
getBeine(): 2
getWirklicheBeine(): 2

LahmeEnte ente2 = new LahmeEnte()
beine: 1
getBeine(): 2
getWirklicheBeine(): 1

Ente ente3 = ente2
beine: 2
getBeine(): 2
getWirklicheBeine(): 1
sep@swe10:~/fh/prog2/beispiele>

package name.panitz.lateBinding;
class EntenTest2 {
  public static void main(String [] args){
    Ente ente = new LahmeEnte(); 
    System.out.println(            ente .beine);
    System.out.println(((LahmeEnte)ente).beine);
  }
}

sep@swe10:~/fh/prog2/beispiele> java name.panitz.lateBinding.EntenTest2
2
1
sep@swe10:~/fh/prog2/beispiele>

1.3  Keine Späte Bindung für überladene Methoden

package name.panitz.overload;
public class Up{}

package name.panitz.overload;
public class Down1 extends Up{}

package name.panitz.overload;
public class Down2 extends Up{}

package name.panitz.overload;
public class  GetDescription {
  public String getDescription(Up _){return "Up";}
  public String getDescription(Down1 _){return "Down1";}
  public String getDescription(Down2 _){return "Down2";}

  public static void main(String [] _){
    GetDescription g = new GetDescription();
    Up up = new Up();
    Down1 down1 = new Down1();
    Down2 down2 = new Down2();
    System.out.println(g.getDescription(up));
    System.out.println(g.getDescription(down1));
    System.out.println(g.getDescription(down2));
    up = down1;
    System.out.println(g.getDescription(up));
    up = down2;
    System.out.println(g.getDescription(up));
    System.out.println(g.getDescription((Down2)up));
  }
}

sep@linux:~/fh/prog2/examples> java -classpath classes/ name.panitz.overload.GetDescription
Up
Down1
Down2
Up
Up
Down2
sep@linux:~/fh/prog2/examples>

Chapter 2
Graphische Benutzeroberflächen und Graphiken

• java.awt: Dieses ist das ältere Paket zur GUI-Programmierung. Es enthält Klassen für viele graphische Objekte (z.B. eine Klasse Button) und Unterpakete, zur Programmierung der Funktionalität der einzelnen Komponenten.
• javax.swing: Dieses neuere Paket ist noch universeller und platformunabhängiger als das java.awt-Paket. Auch hier finden sich Klassen für unterschiedliche GUI-Komponenten. Sie entsprechen den Klassen aus dem Paket java.awt. Die Klassen haben oft den gleichen Klassennamen wie in java.awt jedoch mit einem J vorangestellt. So gib es z.B. eine Klasse JButton.

2.1  Graphische Benutzeroberflächen

• Komponenten
• Ereignisbehandlung
• Layoutstuerung

2.1.1  Graphische Komponenten

• Top-Level Komponenten
• Zwischenkomponenten
• Atomare Komponenten

Top-Level Komponenten

Beispiel:
Das minimalste GUI-Programm ist wahrscheinlich folgendes Programm, das ein Fensterobjekt erzeugt und dieses sichtbar macht.

package name.panitz.simpleGui;
import javax.swing.*;

public class Window1{
  public static void main(String [] _){
    new JFrame("erstes Fenster").setVisible(true);
  }
}

Figure 2.1: Ein erstes Fenster.

Zwischenkomponenten

Atomare Komponenten

Beispiel:
Das folgende Programm erzeugt ein Fenster mit einer Textfläche.

package name.panitz.simpleGui;
import javax.swing.*;

class JT {
  public static void main(String [] _){
    JFrame frame = new JFrame();
    JTextArea textArea = new JTextArea();
    textArea.setText("hallo da draußen");
    frame.getContentPane().add(textArea);
    frame.pack();
    frame.setVisible(true);
  }
}

Figure 2.2: Fenster mit Textfläche

Beispiel:
Die folgende Klasse definiert ein Fenster, das einen Knopf und eine Textfläche enthält. In der Hauptmethode wird das Objekt instanziiert:

package name.panitz.simpleGui;
import javax.swing.*;

class JTB extends JFrame {
  JPanel pane = new JPanel();
  JTextArea textArea = new JTextArea();
  JButton button = new JButton("ein Knopf");

  public JTB(){
    textArea.setText("hallo da draußen");
    pane.add(textArea);
    pane.add(button);
    getContentPane().add(pane);
    pack();
    setVisible(true);
  }

  public static void main(String [] _){
    new JTB();
  }
}

Figure 2.3: Fenster mit Textfläche und Knopf

2.1.2  Ereignisbehandlung

Beispiel:
Als erstes Beispiel für eine Ereignisbehandlung betrachten wir die vielleicht elementarste Art eines Ereignisses: ein Knopf wird gedrückt. Hierzu gibt es die elementare Ereignisbehandlungsschnittstelle: java.awt.event.ActionListener. Diese Schnittstelle enthält nur eine Methode: actionPerformed

package name.panitz.simpleGui;
import java.awt.event.*;
import javax.swing.*;

public class CounterListener implements ActionListener{
  private final JTextArea textArea;
  private int counter = 0;
  public CounterListener(JTextArea ta){textArea=ta;}

  public void actionPerformed(ActionEvent _){
    counter = counter+1;
    textArea.setText(counter+"");
  } 
}

package name.panitz.simpleGui;
import javax.swing.*;

class Counter extends JTB {
  public Counter(){
    super();
    button.addActionListener(new CounterListener(textArea));
  }

  public static void main(String [] _){new Counter();}
}

• einen Knopf zum Erhöhen eines Zählers.
• einen Knopf zum Verringern des Zählers um 1.
• einen Knopf zum Zurücksetzen des Zählers auf 0.

2.1.3  Setzen des Layouts

Flow Layout

Beispiel:
Die folgende Klasse definiert ein Fenster, dessen Layout über ein Objekt der Klasse FlowLayout gesteuert wird. Dem Fenster werden fünf Knöpfe hinzugefügt:

package name.panitz.gui.layoutTest;

import java.awt.*;
import javax.swing.*;

class FlowLayoutTest extends JFrame {

  public FlowLayoutTest(){
    Container pane = getContentPane();
    pane.setLayout(new FlowLayout());
    pane.add(new JButton("eins"));
    pane.add(new JButton("zwei"));
    pane.add(new JButton("drei (ein langer Knopf)"));
    pane.add(new JButton("vier"));
    pane.add(new JButton("fuenf"));
    pack();
    setVisible(true);
  }

  public static void main(String [] _){new FlowLayoutTest();}
}

Border Layout

Beispiel:
In dieser Klasse wird die Klasse BorderLayout zur Steuerung des Layoout benutzt. Die fünf Knöpfe werden an jeweils eine der fünf Positionen hinzugefügt:

package name.panitz.gui.layoutTest;

import java.awt.*;
import javax.swing.*;

class BorderLayoutTest extends JFrame {

  public BorderLayoutTest(){
    Container pane = getContentPane();
    pane.setLayout(new BorderLayout());
    pane.add(new JButton("eins"),BorderLayout.NORTH);
    pane.add(new JButton("zwei"),BorderLayout.SOUTH);
    pane.add(new JButton("drei (ein langer Knopf)")
                                ,BorderLayout.CENTER);
    pane.add(new JButton("vier"),BorderLayout.WEST);
    pane.add(new JButton("fuenf"),BorderLayout.EAST);
    pack();
    setVisible(true);
  }

  public static void main(String [] _){new BorderLayoutTest();}
}

Grid Layout

Beispiel:
Folgende Klasse benutzt ein Grid-Layout mit zwei Zeilen zu je drei Spalten.

package name.panitz.gui.layoutTest;

import java.awt.*;
import javax.swing.*;

class GridLayoutTest extends JFrame {
  public GridLayoutTest(){
    Container pane = getContentPane();
    pane.setLayout(new GridLayout(2,3));
    pane.add(new JButton("eins"));
    pane.add(new JButton("zwei"));
    pane.add(new JButton("drei (ein langer Knopf)"));
    pane.add(new JButton("vier"));
    pane.add(new JButton("fünf"));
    pack();
    setVisible(true);
  }

  public static void main(String [] _){new GridLayoutTest();}
}

2.2  Exkurs: verschachtelte Klassen

2.2.1  Innere Klassen

Beispiel:
Unser erstes GUI mit einer Funktionalität läßt sich jetzt mit Hilfe einer inneren Klasse in einer Datei schreiben. Das Feld counter, das wir in der vorherigen Implementierung als privates Feld der Klass CounterListener definiert hatten, haben wir hier als Feld der GUI-Klasse modelliert. Trotzdem kann die Klasse CounterListener weiterhin darauf zugreifen. Ebenso brauch die Textfläche nicht der Klasse CounterListener im Konstruktor übergeben werden. Als innere Klasse kann in CounterListener auf dieses Feld der äußeren Klasse zugegriffen werden.

package name.panitz.simpleGui;
import javax.swing.*;
import java.awt.event.*;

class InnerCounter extends JTB {
  private int counter = 0;

  class CounterListener implements ActionListener{
    public void actionPerformed(ActionEvent _){
      counter = counter+1;
      textArea.setText(counter+"");
    } 
  }

  public InnerCounter(){
    button.addActionListener(new CounterListener());
  }

  public static void main(String [] _){new InnerCounter();}
}

sep@linux:~/fh/prog2/examples/classes/name/panitz/simpleGui> ll *.class
-rw-r--r--    1 sep      users        1082 2004-03-29 11:36 InnerCounter$CounterListener.class
-rw-r--r--    1 sep      users         892 2004-03-29 11:36 InnerCounter.class

2.2.2  Anonyme Klassen

Beispiel:
Wir schreiben ein drittes Mal die Klasse Counter. Diesmal wird statt der nur einmal instanziierten inneren Klasse eine anonyme Implementierung der Schnittstelle ActionListener Instanziiert.

package name.panitz.simpleGui;
import javax.swing.*;
import java.awt.event.*;

class AnonymousCounter extends JTB {
  private int counter = 0;

  public AnonymousCounter(){
    button.addActionListener(
      new ActionListener(){
        public void actionPerformed(ActionEvent _){
          counter = counter+1;
          textArea.setText(counter+"");
        } 
      });
  }

  public static void main(String [] _){new AnonymousCounter();}
}

sep@linux:~/fh/prog2/examples/classes/name/panitz/simpleGui> ll *.class
-rw-r--r--    1 sep      users        1106 2004-03-29 11:59 AnonymousCounter$1.class
-rw-r--r--    1 sep      users         887 2004-03-29 11:59 AnonymousCounter.class
sep@linux:~/fh/prog2/examples/classes/name/panitz/simpleGui>

2.2.3  Statische verschachtelte Klassen

2.3  Selbstdefinierte graphische Komponenten

2.3.1  Graphics Objekte

public void paintComponent(java.awt.Graphics g)

Beispiel:
Folgende Klasse definiert eine neue graphische Komponente, die zwei Linien, einen Text, ein Rechteck, ein Oval und ein gefülltes Kreissegment enthält.

package name.panitz.gui.graphicsTest;

import javax.swing.JPanel;
import javax.swing.JFrame;
import java.awt.Graphics;

class SimpleGraphics extends JPanel{
  public void paintComponent(Graphics g){
    g.drawLine(0,0,100,200);
    g.drawLine(0,50,100,50);
    g.drawString("hallo",10,20);
    g.drawRect(10, 10, 60,130); 
    g.drawOval( 50,  100, 30, 80); 
    g.fillArc(-20, 150, 80, 80, 0, 50); 
  } 
}

package name.panitz.gui.graphicsTest;
 
import javax.swing.JFrame;

class UseSimpleGraphics {
  public static void main(String [] args){
    JFrame frame = new JFrame();
    frame.getContentPane().add(new SimpleGraphics());

    frame.pack();
    frame.setVisible(true);
  }
}

Figure 2.4: Einfache graphische Komponente.

2.3.2  Dimensionen

  public java.awt.Dimension getPreferredSize() {
    return new java.awt.Dimension(100,200);
  }

public static void main(String [] args) {
  StrichKreis k = new StrichKreis(120);
  JFrame f = new JFrame();
  JPanel p = new JPanel();
  p.add(new StrichKreis(120));
  p.add(new StrichKreis(10));
  p.add(new StrichKreis(60));
  p.add(new StrichKreis(50));
  p.add(new StrichKreis(70));
  f.getContentPane().add(p);

  f.pack();
  f.setVisible(true);
}

2.3.3  Farben

public abstract void setColor(java.awt.Color c)

Beispiel:
Wir können eine kleine Klasse schreiben, in der wir ein wenig mit Farben spielen. Wir setzen die Hintergrundfarbe des Objekts auf einen dunklen Grauwert, zeichnen darin ein dunkelgrünes Rechteck, ein rotes Oval und ein gelbes Oval.

package name.panitz.gui.graphicsTest;

import javax.swing.JPanel;
import javax.swing.JFrame;

public class ColorTest extends JPanel{
  public ColorTest(){
    //Hintergrundfarbe auf einen dunklen Grauton setzen
    setBackground(new java.awt.Color(100,100,100));
  }  

  public void paintComponent(java.awt.Graphics g){
    //Farbe auf einen dunklen Grünton setzen
    g.setColor(new java.awt.Color(22,178,100));
    //Rechteck zeichnen
    g.fillRect(25,50,50,100);
    //Farbe auf rot setzen
    g.setColor(java.awt.Color.RED);
    g.fillOval(25,50,50,100);
    //Farbe auf gelb setzen
    g.setColor(java.awt.Color.YELLOW);
    g.fillOval(37,75,25,50);
  }

  public java.awt.Dimension getPreferredSize() {
    return new java.awt.Dimension(100,200);
  }

  public static void main(String [] _){
    javax.swing.JFrame f = new JFrame("Farben");
    f.getContentPane().add(new ColorTest());
    f.pack();f.setVisible(true);
  }
} 

Figure 2.6: Erste farbige Graphik.

Fraktale

package name.panitz.crempel.tool.apfel;

public class Complex{

  public double re;
  public double im;

 public Complex(double re,double im){
  this.re=re;this.im=im;
}

  public Complex add(Complex other){
    return new Complex(re+other.re,im+other.im);
  }

  public Complex mult(Complex other){
    return new Complex
      (re*other.re-im*other.im,re*other.im+im*other.re);
  }

  public double norm(){return re*re+im*im;}
}

package name.panitz.crempel.tool.apfel;

import java.awt.Graphics;
import java.awt.Color;
import java.awt.Dimension;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Apfelmaennchen extends JPanel {

  final int width = 480;
  final int height = 430;

  double zelle=0.00625;

  final Color colAppleman = new Color(0,129,190);

  double startX = -2;
  double startY = -1.35;

  final int recDepth = 50;
  final int schwellwert = 4;

  //C-Werte checken nach zn+1 = zn*zn + c, 
  public int checkC(Complex c) {        
    Complex zn = new Complex(0,0);

    for (int n=0;n<recDepth;n=n+1) {
      final Complex znp1 = zn.mult(zn).add(c);
      if (znp1.norm() > schwellwert) return n;
      zn=znp1;
    }
    return recDepth;
  }

  public void paint(Graphics g) {
    for (int y=0;y<height;y=y+1) {
      for (int x=0;x<width;x=x+1) {

        final Complex current
          =new Complex(startX+x*zelle,startY+y*zelle);  

        final int iterationenC = checkC(current);

        paintColorPoint(x,y,iterationenC,g);
      }
    }
  }

  private void paintColorPoint
                 (int x,int y,int it,Graphics g){
    final Color col
      = it==recDepth
        ?colAppleman   
        :new Color(255-5*it%1,255-it%5*30,255-it%5* 50);
    g.setColor(col); 
    g.drawLine(x,y,x,y);
  }

  public Dimension getPreferredSize(){
    return new Dimension(width,height);
  }

  public static void main(String [] args){
    JFrame f = new JFrame();
    f.getContentPane().add(new Apfelmaennchen());
    f.pack();
    f.setVisible(true);
  }
}

2.3.4  Fonts und ihre Metrik

Beispiel:
Folgende Kleine Klasse vergrößert nach und nach den Font, und malt in verschiedenen Größen einen Text in ein Fenster.

package name.panitz.gui.graphicsTest;

import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Dimension;
import javax.swing.JPanel;
import javax.swing.JFrame;


class FontTest extends JPanel {

  public Dimension getPreferredSize(){
    return new Dimension(250,650);
  }
  
  public void paintComponent(Graphics g){
    //die y-Koordinate für einen Text
    int where = 0;

    //25 mal
    for (int i=1; i<=25;i=i+1){
      //nimm aktuellen Font und seine Maße
      final Font f = g.getFont();
      final FontMetrics fm = g.getFontMetrics(f);

      //gehe die Höhe des Fonts weiter in Richtung x
      where = where + (f.getSize()) ;

      //male "hallo"
      g.drawString("hallo",0,where);      

      //berechne wo der gerade gemalte String endet
      //und male dort "welt"
      g.drawString
        ("welt!",fm.stringWidth("hallo "),where);      

      //verändere die Fontgröße. Erhöhe sie um 1.
      g.setFont(getFont().deriveFont(f.getSize2D()+1));
    }
  } 

  public static void main(String [] _){
    JFrame f = new JFrame("Fonts");
    f.getContentPane().add(new FontTest());
    f.pack();
    f.setVisible(true); 
  }
}

Figure 2.8: Verschiedene Fontgrößen.

2.3.5  Erzeugen graphischer Dateien

Beispiel:
Wir schreiben eine kleine Klasse mit Methoden, um das Bild einer graphischen Komponente in eine Datei zu speichern.

package name.panitz.gui.graphicsFile;

import name.panitz.crempel.tool.apfel.Apfelmaennchen;
import java.awt.image.BufferedImage;
import java.awt.image.RenderedImage;
import java.awt.Dimension;
import java.awt.Graphics;

import javax.imageio.ImageIO; 
import javax.swing.JComponent; 

import java.io.File;
import java.io.IOException;

public class ComponentToFile {
  public static void main(String [] args){

   try {
     final JComponent component = new Apfelmaennchen();
     final RenderedImage image = createComponentImage(component);
     ImageIO.write(image,"png", new File(args[0]+".png"));
     ImageIO.write(image,"jpg", new File(args[0]+".jpg"));
    }catch (IOException e) {System.out.println(e);}
  }

  static public RenderedImage createComponentImage
                                (JComponent component) {

     Dimension d = component.getPreferredSize();
     BufferedImage bufferedImage 
      = new BufferedImage((int)d.getWidth(),(int)d.getHeight()
                         ,BufferedImage.TYPE_INT_RGB);

    Graphics g = bufferedImage.createGraphics();

   component.paint(g);

    return bufferedImage;
  }
}

2.3.6  Graphics2D

public void paint(Graphics g) {
    Graphics2D g2 = (Graphics2D) g;
    ...
}

Beispiel:
Folgende Klasse benutzt willkürlich ein paar Eigenschaften der Graphics2D-Klasse, um einen Eindruck über die Arbeitsweise dieser Klasse zu geben. Eine systematische Behandlung der graphischen ist nicht Gegenstand dieser Vorlesung.

package name.panitz.gui.g2d;
import javax.swing.JPanel;
import javax.swing.JFrame;

import java.awt.font.*;
import java.awt.*;
import java.awt.geom.*;

public class G2DTest extends JPanel{
  int w = 550;
  int h = 650;

  public Dimension getPreferredSize(){
    return new Dimension(w,h);}

  public void paintComponent(Graphics g){
    Graphics2D g2 = (Graphics2D) g;
    TextLayout textTl 
     = new TextLayout
             ("Kommunismus", new Font("Helvetica", 1, 96)
             , new FontRenderContext(null, false, false));

    AffineTransform textAt = new AffineTransform();
    textAt.translate(0,(float)textTl.getBounds().getHeight());
    Shape shape = textTl.getOutline(textAt);

    AffineTransform at = new AffineTransform();
    at.rotate(Math.toRadians(45));
    at.shear(1.5, 0.0);

    g2.transform(at);

    float dash[] = {10.0f};
    g2.setStroke(
      new BasicStroke
           (3.0f, BasicStroke.CAP_BUTT
           ,BasicStroke.JOIN_MITER, 10.0f, dash, 0.0f)
    );

    g2.setPaint(
      new GradientPaint(0,0,Color.black,w,h
                       ,new Color(255,100,100),false)
    );

    g2.fill(shape);
    g2.setColor(Color.darkGray);
    g2.draw(shape);
  }
  
  public static void main(String [] _){
    JFrame f = new JFrame("G2");
    f.getContentPane().add(new G2DTest());
    f.pack();
    f.setVisible(true);
  }
}

Figure 2.9: Transformationen auf Text in Graphics2D.

2.4  Weitere Komponente und Ereignisse

2.4.1  Mausereignisse

• Mausereignisse, die sich auf das Drücken, Freilassen oder Klicken auf einen der Mausknöpfe bezieht. Hierfür gibt es eine Schnittstelle zur Behandlung solcher Ereignisse: MouseListener.
• Mausereignisse, die sich auf das Bewegen der Maus beziehen. Die Behandlung solcher Ereignisse kann über eine Implementierung der Schnittstelle MouseMotionListener spezifiziert werden.

Beispiel:
Wir erweitern die Klasse Apfelmaennchen um eine Mausbehandlung. Der mit gedrückter Maus markierte Bereich soll vergrößert in dem Fenster dargestellt werden.

package name.panitz.crempel.tool.apfel;

import java.awt.Graphics;
import java.awt.event.*;
import javax.swing.JFrame;

public class ApfelWithMouse extends Apfelmaennchen{
  public ApfelWithMouse(){

    addMouseListener(new MouseAdapter(){
      int mouseStartX=0;
      int mouseStartY=0;

      public void mousePressed(MouseEvent e) {
        mouseStartX=e.getX();
        mouseStartY=e.getY();
      }
	
      public void mouseReleased(MouseEvent e) {
        int endX = e.getX();
        int endY = e.getY();
        startX = startX+(mouseStartX*zelle);
        startY = startY+(mouseStartY*zelle);
        zelle  = zelle*(endX-mouseStartX)/width;
        repaint();
      }
    });
  }

  public static void main(String [] _){
    JFrame f = new JFrame();
    f.getContentPane().add(new ApfelWithMouse());
    f.pack();
    f.setVisible(true);
  }
}

2.4.2  Fensterereignisse

Beispiel:
In den bisher vorgestellten Programmen wird Java nicht beendet, wenn das einzige Fenster der Anwendung geschlossen wurde. Man kann an der Konsole sehen, daß der Javainterpreter weiterhin aktiv ist. Das liegt daran, daß wir bisher noch nicht spezifiziert haben, wie die Fensterkomponenten auf das Ereignis des Schließens des Fensters reagieren sollen. Dieses kann mit einem Objekt, das WindowListener implementiert in der Methode windowClosing spezifiziert werden. Wir schreiben hier eine Version des Apfelmännchenprogramms, in dem das Schließen des Fensters den Abbruch des gesammten Programms bewirkt.

package name.panitz.crempel.tool.apfel;

import javax.swing.JFrame;
import java.awt.event.*;

public class ClosingApfelFrame {
  public static void main(String [] args){
    JFrame f = new JFrame();
    f.getContentPane().add(new ApfelWithMouse());
    f.addWindowListener(new WindowAdapter(){
      public void windowClosing(WindowEvent e) {
        System.exit(0);
      }
    });
    f.pack();
    f.setVisible(true);
  }
}

2.4.3  Weitere Komponenten

package name.panitz.gui.example;

import javax.swing.*;
import java.awt.*;
import java.util.*;

public class ComponentOverview  {
  public ComponentOverview(){

   JComponent [] cs1 =
    {new JButton("knopf")
    ,new JCheckBox("check mich")
    ,new JRadioButton("drück mich")
    ,new JMenuItem("ins Menue mit mir")
    ,new JComboBox(combos)
    ,new JList(combos)
    ,new JSlider(0,350,79)
    ,new JSpinner(new SpinnerNumberModel(18,0.0,42.0,2.0))
    ,new JTextField(12)
    ,new JFormattedTextField("hallo")
    ,new JLabel("einfach nur ein Label")
    ,new JProgressBar(0,42)
    };

   JComponent [] cs2 =
    {new JColorChooser(Color.RED)
    ,new JFileChooser()
    ,new JTable(13,5)
    ,new JTree()
    };

   displayComponents(cs1,3);
   displayComponents(cs2,2);
  }

  String [] combos = {"friends","romans","contrymen"};

  public void displayComponents(JComponent [] cs,int col){

    JFrame f = new JFrame();
    JPanel panel = new JPanel();
    panel.setLayout(
     new GridLayout(cs.length/col+(cs.length%col==0?0:1),col));

    for (JComponent c:cs){
      JPanel p = new JPanel();
      p.add(c);  
      p.setBorder(BorderFactory
                 .createTitledBorder(c.getClass().getName()));  
      panel.add(p);
    }

    f.getContentPane().add(panel);
    f.pack();
    f.setVisible(true);
  }

  public static void main(String [] _){
    new  ComponentOverview();
  }
}

2.5  Swing und Steuerfäden

The first rule of using threads is this: avoid them when you can.

• Bestimmte Operationen können sehr lange dauern und damit das GUI blockieren. Das Laden oder Bearbeiten von Multimediadateien kann unter Umständen sehr lange dauern. Während dieser Zeit, werden Fensterinhalte nicht aktualisiert.
• Für Animationen soll nach bestimmten Zeitintervallen die Graphik eines GUIs verändert und neu gezeichnet werden. Hierzu benötigt man so etwas wie ein sleep der Steuerfäden.

Beispiel:
Wir können uns zunächst davon überzeugen, daß die einzelnen Komponenten in einer Swinganwendung nicht in einzelnen Steuerfäden laufen. Hierzu schreiben wir ein Programm mit zwei Knopfkomponenten, von denen der eine eine Ereignisbehandlung hat, die nicht terminiert.

package name.panitz.swing.threadTest;

import javax.swing.JFrame;
import javax.swing.JButton;
import java.awt.event.*;

public class GuiHangs {
  public static void main(String [] _){
    JFrame f1 = new JFrame("f1");
    JFrame f2 = new JFrame("f2");
    JButton b1 = new JButton("b1");
    JButton b2 = new JButton("b2");

    b1.addActionListener(new ActionListener(){
      public void actionPerformed(ActionEvent _){
        System.out.println("b1 action");
      }
    });

    b2.addActionListener(new ActionListener(){
      public void actionPerformed(ActionEvent _){
        System.out.println("b2 action");
        while (true){}
      }
    });

    f1.getContentPane().add(b1);
    f2.getContentPane().add(b2);
    f1.pack();
    f2.pack();
    f1.setVisible(true);
    f2.setVisible(true);
  }
}

2.5.1  Timer in Swing

Beispiel:
Folgende Klasse implementiert eine simple Uhr. In einem JLabel wird die aktuelle Zeit angegeben. Die Komponente wird einem Timer übergeben, der jede Sekunde eine neues Ereigniserzeugt. Diese Ereignisse sorgen dafür, daß die Zeit im Label aktualisiert wird.

package name.panitz.swing.threads;

import javax.swing.*;
import java.util.Date;
import java.awt.event.*;

public class Uhr extends JPanel implements ActionListener{

  JLabel l = new JLabel(new Date()+"");

  public Uhr (){
    new Timer(1000,this).start();
    add(l);	
  }

  public void actionPerformed(ActionEvent _){
    l.setText(""+new Date());
  }

  public static void main(String [] _){
    JFrame f = new JFrame();
    f.getContentPane().add(new Uhr());
    f.pack();
    f.setVisible(true);
  }
}

Figure 2.12: Eine einfache Digitaluhr.

Animationen mit Timern

package name.panitz.animation;

public interface Animation {
  public void move();
}

package name.panitz.animation;

import javax.swing.JPanel;
import javax.swing.Timer;
import java.awt.event.*;

public abstract class AnimatedJPanel 
  extends JPanel implements Animation {

  Timer t;

  public AnimatedJPanel(){
    super(true);
    t = new Timer(29,new ActionListener(){
      public void actionPerformed(ActionEvent _){
        move();
        repaint();
      }
    });
    t.start();
  }
}

package name.panitz.animation;

import java.awt.Graphics;
import java.awt.Dimension;
import java.awt.Color;
import javax.swing.JFrame;

public class BouncingBall extends AnimatedJPanel {

  final int width = 100;
  final int height = 200;
  final int ballSize = 20;

  int yDir = 4;

  int ballX = width/2-ballSize/2;
  int ballY = 0;

  public void move(){
    if (ballY>height-ballSize || ballY<0) yDir=-yDir;
    ballY=ballY+yDir;
  }

  public void paintComponent(Graphics g){
    g.setColor(Color.RED);
    g.fillRect(0,0,width,height);
    g.setColor(Color.YELLOW);
    g.fillOval(ballX,ballY,ballSize,ballSize); 
  }

  public Dimension getPreferredSize(){
    return new Dimension(width,height);
  }

  public static void main(String [] _){
    JFrame f = new JFrame("");
    f.getContentPane().add(new BouncingBall());
    f.pack();
    f.setVisible(true);
  }
}

2.5.2  SwingWorker für Steuerfäden in der Ereignisbehandlung

public void actionPerformed(ActionEvent e) {
    ...
    //...Code, der sehr lange dauert ...
    ...
}

public void actionPerformed(ActionEvent e) {
    ...
    final SwingWorker worker = new SwingWorker() {
        public Object construct() {
            //...Code, der sehr lange dauert, ist jetzt hier...
            return someValue;
        }
    };
    worker.start();
    ...
}

 

Beispiel:
Jetzt können wir unser Eingangsbeispiel mit der SwingWorker-Klasse so umschreiben, daß es nicht mehr zum Hängen des gesamten Programms kommt.

package name.panitz.swing.threadTest;

import javax.swing.JFrame;
import javax.swing.JButton;
import java.awt.event.*;

public class GuiHangsNoLonger {
  public static void main(String [] _){
    JFrame f1 = new JFrame("f1");
    JFrame f2 = new JFrame("f2");
    JButton b1 = new JButton("b1");
    JButton b2 = new JButton("b2");

    b1.addActionListener(new ActionListener(){
      public void actionPerformed(ActionEvent _){
        System.out.println("b1 action");
      }
    });

    b2.addActionListener(new ActionListener(){
      public void actionPerformed(ActionEvent _){
        final SwingWorker worker = new SwingWorker() {
          public Object construct() {
            System.out.println("b2 action");
            int x = 1; while (true){if (x==0) break;}
            return null;
          }
        };
        worker.start();  
      }
    });

    f1.getContentPane().add(b1);
    f2.getContentPane().add(b2);
    f1.pack();
    f2.pack();
    f1.setVisible(true);
    f2.setVisible(true);
  }
}

SwingWorkerbeispiel

package name.panitz.gui;

import java.io.File;
import java.net.MalformedURLException;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class ImageIcon extends JLabel {
  private int height = 60;
  private int width = 80;
  final Toolkit toolkit = Toolkit.getDefaultToolkit();
  private Image image;

  public ImageIcon(String fileName){this(new File(fileName));}
  public ImageIcon(final File file){
    setImage(file);
  }

  public void setImage(File jpgFile){
    try{
      image=toolkit.getImage(jpgFile.toURL());
      final MediaTracker tracker = new MediaTracker(this);
      tracker.addImage(image, 0,width,height);
      try {tracker.waitForAll();}
      catch (Exception e) {e.printStackTrace();}
      fitImage();
      setIcon(new javax.swing.ImageIcon(image));
    }catch (MalformedURLException e){}
  }

  private void fitImage(){
    final int w = image.getWidth(this); 
    final int h = image.getHeight(this); 
    
    final int w1 = width;        final int h1 = h*width/w;
    final int w2 = w*height/h;   final int h2 = height;
    final int w3 = w1<w2?w1:w2;  final int h3 = h1<h2?h1:h2;

    image=image.getScaledInstance
                  (w3<w?w3:w,h3<h?h3:h,Image.SCALE_FAST); 
  }
}

package name.panitz.gui;

import name.panitz.swing.threads.Uhr;

import java.io.File;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

class UseImageIcon {
  public static void main(String [] args){
    JFrame f= new JFrame();
    final JPanel p = new JPanel();
    f.getContentPane().add(p);
    final int c = 10;
    final int n = args.length;
 
    p.setLayout(new GridLayout(n/c+((n%c)==0?0:1),c));
    for (final String arg:args)p.add(new ImageIcon(arg));

    f.pack();
    f.setVisible(true);

    JFrame f2 = new JFrame();
    f2.getContentPane().add(new Uhr());
    f2.pack();
    f2.setVisible(true);
  }
}

package name.panitz.gui;

import name.panitz.swing.threads.Uhr;
import name.panitz.swing.threadTest.SwingWorker;

import java.io.File;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class BetterUseOfImageIcon{
  public static void main(String [] args){
    final JFrame f= new JFrame();
    final JPanel p = new JPanel();
    f.getContentPane().add(p);
    final int c = 10;
    final int n = args.length;

    p.setLayout(new GridLayout(n/c+((n%c)==0?0:1),c));
    for (final String arg:args){
      ActionListener listen = new ActionListener(){ 
        public void actionPerformed(ActionEvent e) {
         final SwingWorker worker = new SwingWorker() {
           public Object construct() {
              p.add(new ImageIcon(arg)); f.pack();
              f.repaint();
              return null;
           }
         };
         worker.start(); 
        }
      };

      Timer t = new Timer(10,listen);
      t.setRepeats(false);

      t.start();
    }
    f.pack();
    f.setVisible(true);

    JFrame f2 = new JFrame();
    f2.getContentPane().add(new Uhr());
    f2.pack();
    f2.setVisible(true);
  }
}

Chapter 3
Abstrakte Datentypen

3.1  Bäume

• Dateisystem: Ein gängiges Dateisystem, wie es aus Unix, MacOS und Windows bekannt ist, stellt eine Baumstruktur dar. Es gibt einen ausgezeichneten Wurzelordner, von dem aus zu jeder Datei einen Pfad existiert.
• Klassenhierarchie: Die Klassen in Java stellen mit ihrer Ableitungsrelation eine Baumstruktur dar. Die Klasse Object ist die Wurzel dieses Baumes, von der aus alle anderen Klassen über einen Pfad entlang der Ableitungsrelation erreicht werden können.
• XML: Die logische Struktur eines XML-Dokuments ist ein Baum. Die Kinder eines Elements sind jeweils die Elemente, die durch das Element eigeschlossen sind.
• Parserergebnisse: Ein Parser, der gemäß einer Grammatik prüft, ob ein bestimmter Satz zu einer Sprache gehört, erzeugt im Erfolgsfall eine Baumstruktur. Im nächsten Kapitel werden wir dieses im Detail kennenlernen.
• Listen: Auch Listen sind Bäume, allerdings eine besondere Art, in denen jeder Knoten nur maximal ein Kind hat.
• Berechnungsbäume: Zur statischen Analyse von Programmen, stellt man Bäume auf, in denen die Alternativen eines bedingten Ausdrucks Verzweigungen im Baum darstellen.
• Tableaukalkül: Der Tableaukalkül ist ein Verfahren zum Beweis logischer Formeln. Die dabei verwendeten Tableaux sind Bäume.
• Spielbäume: Alle möglichen Spielverläufe eines Spiels können als Baum dargestellt werden. Die Kanten entsprechen dabei einem Spielzug.
• Prozesse: Auch die Prozesse eines Betriebssystems stellen eine Baumstruktur dar. Die Kinder eines Prozesses sind genau die Prozesse, die von ihm gestartet wurden.

3.1.1  Formale Spezifikation

Allgemeine Bäume

• Node: (a,List<Tree<a>>) ®Tree<a>

• theChildren: Tree<a>®List<Tree<a>>
• mark: Tree<a>®a

mark(Node(x,xs)) = x
theChildren(Node(x,xs)) = xs

isLeaf(Node(x,xs)) = isEmpty(xs)

3.1.2  Modellierung

mit einer Klasse

Mit einer Klassenhierarchie

• Wenn zu erwarten ist, daß im Laufe der Softwareentwicklung noch weitere Konstruktoren zum abstrakten Datentyp hinzudefiniert werden, dann ist eine Modellierung als Hierarchie vorteilhaft. Der neue Konstruktor führt zu einer neuen Klasse, in der lokale Version der für die implementierte Schnittstelle benötigten Methoden implementiert werden.
• Wenn zu erwarten ist, daß spezialisierte Versionen des abstrakten Datentyps benötigt werden, so ist eine Modellierung als eine Klasse vorteilhaft, weil dann für dieser einen Klassen eine Unterklasse implementiert werden kann.

3.1.3  Implementierung

• Tree(List children): als Knotenmarkierung wird null genommen.
• Tree(a mark): für die Kinder wird eine leere Liste erzeugt.

package name.panitz.data.tree;

import java.util.List;
import java.util.Iterator;
import java.util.Enumeration;
import java.util.ArrayList;
import javax.swing.tree.TreeNode; 

public class Tree<a>  implements TreeNode{

  private a mrk;  
  private List<Tree<a>> chldrn;

  public Tree(a mark,List<Tree<a>> children){
    this.mrk=mark;
    this.chldrn=children;
  }

  public Tree(List<Tree<a>> children){
    this(null,children);
  }

  public Tree(a mark){
    this(mark,new ArrayList<Tree<a>>());
  }


  public List<Tree<a>> theChildren(){return chldrn;}
  public a mark(){return mrk;}

  public boolean isLeaf(){return theChildren().isEmpty();}

3.2  Algorithmen auf Bäumen

3.2.1  Knotenanzahl

public int count(){
  int result = 1; // Startwert 1 für diesen Knoten

  //für jedes Kind
  for (Tree<a> child: theChildren())
    //addiere die Knotenanzahl des Kindes zum Ergebnis 
    result=result+child.count();

  return result;
}

3.2.2  toString

public String toString(){
  //Nimm erst die Markierung an diesem Knoten
  String result = mark().toString();
  
  //Gibt es keine Kinder, dann bist du fertig
  if (isLeaf()) return result;

  //ansonsten nimm implizit durch Operator + das 
  //toString() der Kinder
  return result+theChildren();
}

3.2.3  Linearisieren

public List<a> flatten(){
  //leere Liste für das Ergebnis
  List<a> result = new ArrayList<a>();

  //füge die Markierung dieses Knotens zur 
  //Ergebnisliste hinzu
  result.add(mark());

  //für jedes Kind
  for (Tree<a> child : theChildren())
    //erzeuge dessen Knotenliste und füge alle deren 
    //Elemente zum Ergebnis hinzu
    result.addAll(child.flatten());

  return result;
}

{\bf \alph{unteraufgabe})} List leaves(): erzeugt eine Liste der Markierungen an den Blättern des Baumes.
{\bf \alph{unteraufgabe})} String show(): erzeugt eine textuelle Darstellung des Baumes. Jeder Knoten soll eine eigene Zeile haben. Kinderknoten sollen gegenüber einem Elternknoten eingerückt sein.
Beispiel:

william
  charles
    elizabeth
    phillip
  diana
    spencer

Tipp: Benutzen Sie eine Hilfsmethode
String showAux(String prefix),
die den String prefix vor den erzeugten Zeichenketten anhängt.
{\bf \alph{unteraufgabe})} boolean contains(a o): ist wahr, wenn eine Knotenmarkierung gleich dem Objekt o ist.
{\bf \alph{unteraufgabe})} int maxDepth(): gibt die Länge des längsten Pfades von der Wurzel zu einem Blatt an.
{\bf \alph{unteraufgabe})} List<a> getPath(a o): gibt die Markierungen auf dem Pfad von der Wurzel zu dem Knoten, der mit dem Objekt o markiert ist, zurück. Ergebnis ist eine leere Liste, wenn ein Objekt gleich o nicht existiert.
{\bf \alph{unteraufgabe})} java.util.Iterator<a> iterator(): erzeugt ein Iterator über alle Knotenmarkierungen des Baumes.
Tipp: Benutzen Sie bei der Umsetzung die Methode flatten.
{\bf \alph{unteraufgabe})} public boolean equals(Object other): soll genau dann wahr sein, wenn other ein Baum ist, der die gleiche Struktur und die gleichen Markierungen hat.
{\bf \alph{unteraufgabe})} <b>boolean sameStructure(Tree<a> other): soll genau dann wahr sein, wenn der Baum other die gleiche Struktur hat. Die Markierungen der Knoten können hingegen unterschiedlich sein.

3.2.4  Eltern und Geschwister

  public Tree<a> parent=null;

  public Tree(a mark,List<Tree<a>> children){
    //setze die entsprechenden Felder des Knotens
    this.mrk=mark;
    this.chldrn=children;

    //es gibt noch keinen Elternknoten
    this.parent=null;

    //setze den neuen Knoten als Elternknoten der Kinder
    respectParents();  
  }

 public void respectParents(){
   //für jedes Kind
   for (Tree<a> child:theChildren()){
    // ist dieser Knoten jetzt der Elternknoten
    child.parent=this;
   }
 }

3.2.5  Modifizierende Methoden

addChild

public void addChild(Tree<a> newChild){
  List<Tree<a>> chs = theChildren();
  newChild.parent=this;
  chs.add(newChild);
}

addLeaf

public void addLeaf(a o){addChild(new Tree<a>(o));}

deleteChild

public void deleteChild(int n){
   theChildren().remove(n);    
}

setMark

public void setMark(a mark){mrk=mark;}

Beispiel: Baumerzeugung mit modifizierenden Methoden

package name.panitz.data.tree.example;

import  name.panitz.data.tree.Tree;
public class SkriptTree{
  public static Tree<String> getSkript(){
    Tree<String> skript = new Tree<String>("Programmieren 2");

    Tree<String> kap1=new Tree<String>("Frühe und späte Bindung");
    Tree<String> kap2   
     = new Tree<String>
        ("Graphische Benutzeroberflächen und Graphiken");
    Tree<String> kap3   
     = new Tree<String>("Abstrakte Datentypen");

    skript.addChild(kap1);
    skript.addChild(kap2);
    skript.addChild(kap3);

    kap1.addLeaf("Wiederholung: Das Prinzip der späten Bindung");
    kap1.addLeaf("Keine späte Bindung für Felder");
    kap1.addLeaf("Keine Späte Bindung für überladene Methoden");

    Tree<String> sec2_1   
     = new Tree<String>("Graphische Benutzeroberflächen");
    Tree<String> sec2_2   
     = new Tree<String>("Exkurs: verschachtelte Klassen");
    Tree<String> sec2_3   
     =new Tree<String>("Selbstdefinierte graphische Komponenten");
    Tree<String> sec2_4   
     = new Tree<String>("Weitere Komponente und Ereignisse");
    Tree<String> sec2_5   
     = new Tree<String>("Swing und Steuerfäden");

    kap2.addChild(sec2_1);kap2.addChild(sec2_2);
    kap2.addChild(sec2_3);kap2.addChild(sec2_4);
    kap2.addChild(sec2_5);

    Tree<String> sec3_1   
     = new Tree<String>("Bäume");
    Tree<String> sec3_2   
     = new Tree<String>("Algorithmen auf Bäumen");
    Tree<String> sec3_3
     = new Tree<String>("Binärbäume");
    Tree<String> sec3_4
     = new Tree<String>("Binäre Suchbäume");
    Tree<String> sec3_5
     = new Tree<String>("XML-Dokumente als Bäume");
    Tree<String> sec3_6
     = new Tree<String>("Keller");

    kap3.addChild(sec3_1);kap3.addChild(sec3_2);
    kap3.addChild(sec3_3);kap3.addChild(sec3_4);
    kap3.addChild(sec3_5);kap3.addChild(sec3_6);

    sec2_1.addLeaf("Graphische Komponenten");
    sec2_1.addLeaf("Ereignisbehandlung");
    sec2_1.addLeaf("Setzen des Layouts");

    sec2_2.addLeaf("Innere Klassen");
    sec2_2.addLeaf("Anonyme Klassen");
    sec2_2.addLeaf("Statisch verschachtelte Klassen");

    sec2_3.addLeaf("Graphics Objekte");
    sec2_3.addLeaf("Dimensionen");
    sec2_3.addLeaf("Farben");
    sec2_3.addLeaf("Fonts und ihre Metrik");
    sec2_3.addLeaf("Erzeugen graphischer Dateien");
    sec2_3.addLeaf("Graphics2D");

    sec2_4.addLeaf("Mausereignisse");
    sec2_4.addLeaf("Fensterereignisse");
    sec2_4.addLeaf("Weitere Komponenten");

    sec2_5.addLeaf("Timer in Swing");
    sec2_5.addLeaf
     ("SwingWorker für Steuerfäden in der Ereignisbehandlung");
    return skript;
  }
}

package javax.swing.tree;
interface TreeNode{
  Enumeration children();
  int getChildCount(); 
  TreeNode getParent(); 
  boolean isLeaf(); 
  TreeNode getChildAt(int childIndex); 

  boolean getAllowsChildren(); 
  int getIndex(TreeNode node);
}

public class Tree<a>implements TreeNode{

  public Enumeration<TreeNode> children() {
    final Iterator<Tree<a>> it = theChildren().iterator();

    return new Enumeration<TreeNode>(){
      public boolean hasMoreElements(){return it.hasNext();} 
      public Tree<a> nextElement() {return it.next();}
    };
  }

  public TreeNode getChildAt(int childIndex) {
    return theChildren().get(childIndex);
  }

  public int getChildCount(){return theChildren().size();}

  public TreeNode getParent(){return parent;}

  public boolean getAllowsChildren(){
    throw new UnsupportedOperationException();
  } 

  public int getIndex(TreeNode node) {
    throw new UnsupportedOperationException();
  }

  public String toString(){return mark().toString();}

Beispiel:
Wir können jetzt ein beliebiges Objekt der Klasse Tree der Klasse JTree übergeben, um es graphisch darzustellen. Der Code hierzu ist denkbar einfach.

package name.panitz.data.tree.example;

import javax.swing.JFrame;
import javax.swing.JTree;

public class JTreeTest {
  public static void main(String [] args){
    JFrame frame = new JFrame("Baumtest Fenster");
    frame.getContentPane()
         .add(new JTree(SkriptTree.getSkript()));

    frame.pack();
    frame.setVisible(true);
  }
}

Figure 3.3: Baumdarstellung mit JTree.

3.2.7  Bäume zeichnen

package name.panitz.data.tree;

import java.util.Enumeration;

import javax.swing.JComponent;
import javax.swing.JPanel;
import javax.swing.tree.TreeNode;

import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Dimension;

public class DisplayTree extends JPanel{

  private TreeNode treeModell;

  static final public int VERTICAL_SPACE = 50;  
  static final public int HORIZONTAL_SPACE = 20;

    private FontMetrics fontMetrics = null;

  private int height=0;
  private int width=0;

  private boolean dimensionCalculated = false;

  public DisplayTree(TreeNode tree){treeModell=tree;}

  public DisplayTree(TreeNode t,FontMetrics fm){
    treeModell=t;fontMetrics=fm;
  }

  private void calculateDimension(){

    if (fontMetrics==null){
      final Font font = getFont();
      fontMetrics = getFontMetrics(font);
    }

    final int x
      = fontMetrics.stringWidth(treeModell.toString());

    final Dimension childrenDim = childrenSize();
    final int childrenX = (int)childrenDim.getWidth();
    final int childrenY = (int)childrenDim.getHeight();

    width=x>childrenX?x:childrenX;

    height
      =  childrenY == 0
        ?fontMetrics.getHeight()
        :VERTICAL_SPACE+childrenY;

    dimensionCalculated = true;
  }

  Dimension childrenSize(){
    int x = 0;
    int y = 0;

    final Enumeration<TreeNode> it=treeModell.children();
    while (it.hasMoreElements()){
      final DisplayTree t
       = new DisplayTree(it.nextElement(),fontMetrics);

      y =  y > t.getHeight()?y:t.getHeight();

      x=x+t.getWidth();

      if (it.hasMoreElements())  x=x+HORIZONTAL_SPACE;
    }
    return new Dimension(x,y);
  }

  public int getHeight(){
    if (!dimensionCalculated) calculateDimension();
    return height;
  }

  public int getWidth(){
    if (!dimensionCalculated) calculateDimension();
    return width;
  }

  public Dimension getSize(){
    if (!dimensionCalculated) calculateDimension();
    return new Dimension(width,height);
  }

  public Dimension getMinimumSize(){
    return getSize();
  }

  public Dimension getPreferredSize(){
    return getSize();
  }

  public void paintComponent(Graphics g){paintAt(g,0,0);}

  public void paintAt(Graphics g,int x,int y){
    fontMetrics = g.getFontMetrics();
    final String marks =treeModell.toString();

    g.drawString
     (marks
     ,x+(getWidth()/2-fontMetrics.stringWidth(marks)/2)
     ,y+10);

    final int startLineX = x+getWidth()/2;
    final int startLineY = y+10;

    final Enumeration it=treeModell.children();

    final int childrenWidth = (int)childrenSize().getWidth();

    //wieviel nach rechts zu rücken ist
    int newX
      = getWidth()>childrenWidth?(getWidth()-childrenWidth)/2:0;

    //die y-Koordinate der Kinder
    final int nextY = y+VERTICAL_SPACE;

    while (it.hasMoreElements()){
      DisplayTree t
       = new DisplayTree((TreeNode)it.nextElement());

      //x-Positionen für das nächste Kind
      final int nextX = x+newX;
 
      //zeichne das Kind
      t.paintAt(g,nextX,nextY);

      //zeichne Kante
      g.drawLine(startLineX,startLineY
                ,nextX+t.getWidth()/2,nextY);

      newX = newX+t.getWidth()+HORIZONTAL_SPACE;
    }
  }
}

package name.panitz.data.tree.example;
import name.panitz.data.tree.DisplayTree;
import javax.swing.JFrame;
import javax.swing.JScrollPane;

class DisplayTreeTest {
  public static void main(String [] args){
    JFrame frame = new JFrame("Baum Fenster");
    frame.getContentPane()
         .add(new JScrollPane(
                new DisplayTree(SkriptTree.getSkript())));

    frame.pack();
    frame.setVisible(true);
  }
}

package name.panitz.data.tree;
import name.panitz.gui.graphicsFile.ComponentToFile;
import static name.panitz.gui.graphicsFile.ComponentToFile.*;

import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO; 
import javax.swing.JComponent;
import java.awt.image.RenderedImage;

public class TreeToFile{
  public static void treeToFile(Tree tree,String fileName){
    try {
     final JComponent component = new DisplayTree(tree);
     final RenderedImage image = createComponentImage(component);
     ImageIO.write(image,"png", new File(fileName+".png"));
     ImageIO.write(image,"jpg", new File(fileName+".jpg"));
    }catch (IOException e) {System.out.println(e);}
  }
}

3.3  Binärbäume

package name.panitz.data.tree; 

import java.util.List;
import java.util.ArrayList;

public class BinTree<a> extends Tree<a>{

  //private Felder für rechtes und linkes Kind
  private BinTree<a> rght;
  private BinTree<a> lft;

  public BinTree(BinTree<a> left,a mark,BinTree<a> right){
    super(mark);lft=left; rght=right;} 

  public BinTree(a mark){this(null,mark,null);}

  public BinTree<a> left(){return lft;}
  public BinTree<a> right(){return rght;}

  public List<Tree<a>> theChildren(){
    List<Tree<a>> result = new ArrayList<Tree<a>>();
    if (left()!=null)  result.add(left());
    if (right()!=null) result.add(right());
    return result;
  }

3.3.1  Probleme der Klasse BinTree

public void addLeaf(a o){
    throw new UnsupportedOperationException();
}

public void deleteChild(int n){
  if (n==0) lft=null;
  else if (n==1) rght=null;
  else throw new IndexOutOfBoundsException ();
}

  void setLeft(BinTree<a> l){ lft=l;}
  void setRight(BinTree<a> r){ rght=r;}

3.3.2  Linearisieren binärer Bäume

Preordnung

Postordnung

Inordnung

public List<a> inorder(){
  //Ergebnisliste
  List<a> result = new ArrayList<a>();
 
  //gibt es ein linkes Kind, füge dessen 
  //Linearisierung hinzu
  if (left()!=null) result.addAll(left().inorder());

  //dann den Knoten selbst
  result.add(mark());

  //und gegebenenfalls dann das recte Kind
  if (right()!=null) result.addAll(right().inorder());

  return result;
}

Militärordnung

public List military(){
  //Ergebnisliste enthält erst diesen Knoten
  List<a> result=new ArrayList<a>();
  result.add(mark());

  //Wir speichern uns die Knoten einer 
  //aktuellen Generation
  List<Tree<a>> currentGeneration = theChildren();

  //Solange es in der aktuellen Generation Knoten gibt
  while (!currentGeneration.isEmpty()){
    //erzeuge die nächste Generation
    List<Tree<a>> nextGeneration=new ArrayList<Tree<a>>();

    for (Tree<a> nextChild:currentGeneration){
      nextGeneration.addAll(nextChild.theChildren());

      //Füge das Elemente der aktuellen Generation 
      //zum Ergebnis
      result.add(nextChild.mark());
    }
    //schalte eine Generation tiefer
    currentGeneration=nextGeneration;
  } 
  return result;
}}

3.4  Binäre Suchbäume

• jede Knotenmarkierung eines linken Teilbaums ist kleiner oder gleich als die Knotenmarkierung.
• jede Knotenmarkierung eines rechten Teilbaums ist größer als die Knotenmarkierung.

package name.panitz.data.tree;

public class SearchTree<a extends Comparable<a>> 
                                  extends BinTree<a>{

  SearchTree(a o){super(o);}

  public void insert(a o){
    if (o.compareTo(mark())<=0){
      //neuer Knoten ist kneiner, also in den 
      //linken Teilbaum
      if (left()==null){
        setLeft(new SearchTree<a>(o));
      }else 
        ((SearchTree<a>)left()).insert(o);
    }else{
      //wenn der neue Knoten also größer, dann dasselbe
      //im rechten Teilbaum
      if (right()==null){
         setRight(new SearchTree<a>(o));
      }else 
        ((SearchTree<a>)right()).insert(o);
    }
  }

private SearchTree
           (SearchTree<a> l,a o,SearchTree<a> r){
  super(l,o,r);
  try {
   if (!(   o.compareTo(l.mark())>=0
         && o.compareTo(r.mark())<=0))
     throw new IllegalArgumentException
     ("ordering violation in search tree construction");
  }catch(NullPointerException _){
  }
}

package name.panitz.data.tree;
import javax.swing.*;

public class TestSearchTree {
  public static void main(String [] args){
    SearchTree<String> t = new SearchTree<String>("otto");
    t.insert("sven");
    t.insert("eric");
    t.insert("lars");
    t.insert("uwe");
    t.insert("theo");
    t.insert("otto");
    t.insert("kai");
    t.insert("henrik");
    t.insert("august");
    t.insert("berthold");
    t.insert("arthur");
    t.insert("arno");
    t.insert("william");
    t.insert("tibor");
    t.insert("hassan");
    t.insert("erwin");
    t.insert("anna");
    System.out.println(t.inorder());

    JFrame frame = new JFrame("Baum Fenster");
    frame.getContentPane().add(new DisplayTree(t));
    frame.pack();
    frame.setVisible(true);
  }
}

sep@swe10:~/fh/prog2/beispiele/Tree> java TestSearchTree
[anna, arno, arthur, august, berthold, eric, erwin, hassan, henrik,
kai, lars, otto, otto, sven, theo, tibor, uwe, william]
sep@swe10:~/fh/prog2/beispiele/Tree>

Beweis der Sortiereigenschaft

• Anfang: Der Induktionsanfang behauptet, die Inordung eines Blattes ist sortiert. Für ein Blatt k gilt: left(k) = null  und right(k) = null. Es folgt, daß die Inordung nur ein Element, nämlich mark(k), enthält. Einelementige Listen sind immer sortiert.
• Schritt: Wir wollen die Aussage beweisen für alle Bäume k  mit: count(k)=n.
Annahme: die Aussage ist wahr für alle Bäume k¢ mit count(k¢) < n.
Die Definition der Inordnung ist:
inorder(k) = (inorder(left(k)),mark(k),inorder(right(k))).
Für endliche Bäume gilt:
count(left(k)) < n und count(right(k)) < n
Nach der Induktionsvoraussetzung gilt damit, daß
inorder(left(k)) und inorder(right(k))
sortierte Listen sind.
Über die Definition der binären Suchbäume gilt:
für alle x Î inorder(left(k)) gilt x £ mark(k)
und für alle x Î inorder(right(k)) gilt x > mark(k)
Damit ist insbesondere die Liste inorder(k) sortiert.

3.4.1  Suchen in Binärbäumen

public boolean contains(a o){
  //bist du es schon selbst
  if (mark().equals(o)) return true;
 
  //links oder rechts suchen:
  final int compRes = mark().compareTo(o);

  if (compRes>0){
    //keine Knoten mehr. Dann ist er nicht enthalten
    if (left()==null) return false;
    //Sonst such weiter unten im Baum
    else return ((SearchTree<a>)left()).contains(o);
  }    

  if (compRes<0){
    if (right()==null) return false;
    else return ((SearchTree<a>)right()).contains(o);
  }    
  return false;
}

3.4.2  Entartete Bäume

Balanzieren von Bäumen

Beispiel:
Betrachten Sie den Baum aus Abbildung 3.6

Figure 3.6: Nicht balanzierter Baum.

Figure 3.7: Baum nach Rotierungsschritt.

Figure 3.8: Baum nach weiteren Rotierungsschritt.

• rotateRight(Node(Node(l2,x2,r2),x1,r1)) = Node(l2,x2,Node(r2,x1,r1))
• rotateLeft(Node(l1,x1,Node(l2,x2,r2))) = Node(Node(l1,x1,l2),x2,r2)

public static <a extends Comparable<a>> SearchTree<a> 
                         rotateRight(SearchTree<a> t){
  try{
    //speichere die einzelnen Teile in die Bezeichner,
    //die wir in der Spezifikation benutzt haben
    final SearchTree<a> l2 = (SearchTree<a>)t.left().left();
    final SearchTree<a> r2 = (SearchTree<a>)t.left().right();
    final SearchTree<a> r1 = (SearchTree<a>)t.right();
    final a x1 = t.mark();
    final a x2 = t.left().mark();

    return new SearchTree<a>
                 (l2,x2,new SearchTree<a>(r2,x1,r1));
  }catch (NullPointerException _){
      return t;
  }
}

void rotateRight(){
  try{
    BinTree<a> l1 = left();
    BinTree<a> l2 = l1.left();
    BinTree<a> r2 = l1.right();
    BinTree<a> r1 = right();
    a  x1 = mark();
    a  x2 = l1.mark();

    setMark(x2);
    setLeft(l2);
    setRight(l1);
    l1.setMark(x1);
    l1.setLeft(r2);
    l1.setRight(r1);
  }catch (NullPointerException _){
  }
}}

{\bf \alph{unteraufgabe})} Schreiben sie entsprechend die Methode:
static public SearchTree rotateLeft(SearchTree t)
{\bf \alph{unteraufgabe})}
Schreiben Sie in der Klasse BinTree die entsprechende modifizierende Methode rotateLeft()
{\bf \alph{unteraufgabe})} Testen Sie die beiden Rotierungsmethoden. Testen Sie, ob die Tiefe der Kinder sich verändert und ob die Inordnung gleich bleibt. Testen Sie insbesondere auch einen Fall, in dem die NullPointerException abgefangen wird.

Chapter 4
Formale Sprachen, Grammatiken, Parser

4.1  formale Sprachen

4.1.1  kontextfreie Grammatik

• einer Menge T von Wörteren, den Terminalsymbole.
• einer Menge N von Nichtterminalsymbolen.
• ein ausgezeichnetes Startsymbol S Î N.
• einer endlichen Menge  von Regeln der Form:
  nt::= t₁... t_n, wobei nt Î N, t_i Î NÈT.

Beispiel:
Wir geben eine Grammatik an, die einfache Sätze über unser Sonnensystem auf Englisch bilden kann:

• T={mars,mercury,deimos,phoebus,orbits,is,a,moon,planet}
• N={start,noun-phrase,verb-phrase,noun,verb,article}
• S=start
• start ::= noun-phrase verb-phrase
noun-phrase ::= noun
noun-phrase ::= article noun
verb-phrase ::= verb noun-phrase
noun ::= planet
noun ::= moon
noun ::= mars
noun ::= deimos
noun ::= phoebus
verb ::= orbits
verb ::= is
article ::= a

Rekursive Grammatiken

Beispiel:
Die folgende Grammatik erlaubt es arithmetische Ausdrücke zu generieren:

• T={0,1,2,3,4,5,6,7,8,9,+,-,*,/}
• N={start,expr,op,integer,digit,}
• S=start
• start ::= expr
expr ::= integer
expr ::= integer op expr
integer ::= digit
integer ::= digit integer
op ::= +
op ::= -
op ::= *
op ::= /
digit ::= 0
digit ::= 1
digit ::= 2
digit ::= 3
digit ::= 4
digit ::= 5
digit ::= 6
digit ::= 7
digit ::= 8
digit ::= 9

Grenzen kontextfreier Grammatiken

{aⁿbⁿcⁿ|n Î IN}.

class SemanticalIncorrect{int i = "1";}

Das leere Wort

t::=

t::=e

Lexikalische Struktur

Andere Grammatiken

Beispiel:
Wir können mit der folgenden nicht-kontextfreien Grammatik die Sprache beschreiben, in der jeder Satz gleich oft die beiden Terminalsymbole, eber in beliebiger Reihenfolge enthält.

• T={a,b}
• N={start,A,B}
• S=start
• start ::= ABstart
  start ::= e
AB ::= BA
BA ::= AB
A ::= a
B ::= b

start
®ABstart
®ABABstart
®ABABABstart
®ABABABABstart
®ABABABABABstart
®ABABABABAB
®AABBABABAB
®AABBBAABAB
®AABBBABAAB
®AABBBABABA
®AABBBABBAA
®AABBBBABAA
®AABBBBBAAA
® aABBBBBAAA
® aaBBBBBAAA
® aabBBBBAAA
® aabbBBBAAA
® aabbbBBAAA
® aabbbbBAAA
® aabbbbbAAA
® aabbbbbaAA
® aabbbbbaaA
® aabbbbbaaa

Beispiel:
Auch die nicht durch eine kontextfreie Grammatik darstellbare Sprache:

{aⁿbⁿcⁿ|n Î IN}.

läßt sich mit einer solchen Grammatik generieren:

S::=abTc
T::=AbTc | e
bA::=Ab
aA::=aa

Eine Ableitung mit dieser Grammatik sieht wie folgt aus:

S
® abTc
® abAbTcc
® abAbAbTccc
® abAbAbAbTcccc
® abAbAbAbAbTccccc
® abAbAbAbAbccccc
® abAAbbAbAbccccc
® abAAbAbbAbccccc
® abAAAbbbAbccccc
® abAAAbbAbbccccc
® abAAAbAbbbccccc
® abAAAAbbbbccccc
® aAbAAAbbbbccccc
® aAAbAAbbbbccccc
® aAAAbAbbbbccccc
® aAAAAbbbbbccccc
® aaAAAbbbbbccccc
® aaaAAbbbbbccccc
® aaaaAbbbbbccccc
® aaaaabbbbbccccc

Grammatiken und Bäume

Beispiel:
Die Ableitungen der Sätze unserer ersten Grammatik haben folgende Baumdarstellung:

Figure 4.1: Ableitungsbaum für a moon orbits mars.

Figure 4.2: Ableitungsbaum für mercury is a planet.

Figure 4.3: Ableitungsbaum für planet orbits a phoebus.

4.1.2  Erweiterte Backus-Naur-Form

Alternativen

Beispiel:
Die Regeln unserer ersten Grammatik können damit wie folgt geschrieben werden:

start ::= noun-phrase verb-phrase

noun-phrase ::= noun | article noun

verb-phrase ::= verb noun-phrase

noun ::= planet | moon | mars | deimos | phoebus

verb ::= orbits | is

article ::= a

Gruppierung

Beispiel:
Die einfache Grammatik für arithmetische Ausdrücke läßt sich damit ohne das Nichtterminalzeichen op schreiben:

start ::= expr

expr ::= integer | integer (+ | - | * | /) expr

integer ::= digit | digit integer

digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Wiederholungen

Beispiel:
Eine Zahl besteht aus einer Folge von n Ziffern (n > 0). Dieses läßt sich durch folgende Regel ausdrücken:

Zahl ::= Ziffer Zahl  |  Ziffer

Beispiel:
Obige Regel für das Nichtterminal Zahl läßt sich mit dieser abkürzenden Schreibweise schreiben als:

Zahl ::= Ziffer+

Beispiel:
Folgende Regel drückt aus, daß ein Ausdruck eine durch Operatoren getrennte Liste von Zahlen ist.

expr ::= Zahl  |   (Op Zahl)*

4.2  Parser

4.2.1  Parsstrategien

Rekursiv absteigend

Beispiel:
Wir suchen mit dieser Strategie die Ableitung des Satzes a moon orbits mars in dem Sonnensystembeispiel. Sackgassen sind durch einen Punkt · markiert.

(0)		start
(1) aus 0	®	noun-phrase verb-phrase
(2a) aus 1	®	noun verb-phrase
(2a3a) aus 2a	®	planet verb-phrase	·
(2a3b) aus 2a	®	moon verb-phrase	·
(2a3c) aus 2a	®	mars verb-phrase	·
(2a3d) aus 2a	®	deimos verb-phrase	·
(2a3e) aus 2a	®	phobus verb-phrase	·
(2b) aus 1	®	article noun verb-phrase
(3) aus 2b	®	a noun verb-phrase
(4a) aus 3	®	a planet verb-phrase	·
(4b) aus 3	®	a moon verb-phrase
(5) aus 4b	®	a moon verb noun-phrase
(6) aus 5	®	a moon orbits noun-phrase
(7) aus 6	®	a moon orbits noun
(8a) aus 7	®	a moon orbits planet	·
(8b) aus 7	®	a moon orbits moon	·
(8c) aus 7	®	a moon orbits mars

Beispiel:
Gegeben sei eine Grammatik mit einer linksrekursiven Regel:

expr::=expr+zahl | zahl

Der Versuch den Satz

zahl+zahl

mit einem links rekursiv absteigenden Parser abzuleiten, führt zu einem nicht terminierenden rekursiven Abstieg. Wir gelangen nie in eine Sackgasse:

S ::= AB | A

Schieben und Reduzieren

Beispiel:
Wir leiten im folgenden unserer allseits bekannten Beispielsatz aus dem Sonnensystem durch Schieben und Reduzieren ab. Als Marker benutzen wir einen Punkt.

4.3  Handgeschriebene Parser

4.3.1  Basisklassen der Parserbibliothek

package name.panitz.parser;
import java.util.List;
public interface Parser<a> {
  ParseResult<a> parse(List<Token> ts);
}

package name.panitz.parser;
public interface Token {}

• dem eigentlichen Ergebnis vom Typ a.
• der Liste der durch den Parsvorgang nicht konsumierten restlichen Token.

package name.panitz.parser;
import java.util.List;
public class ParseResult<a> {
  final private a result;
  final private List<Token> remainingToken;
  public ParseResult(a r,List<Token> toks){
    result=r;remainingToken=toks;
  }
  public a getResult(){return result;}
  public List<Token> getRemainingToken(){return remainingToken;}
  public boolean failed(){return result==null;}
}

Der Epsilon Parser

package name.panitz.parser;
import java.util.List;

public class Epsilon implements Parser<Boolean>{
  public ParseResult<Boolean> parse(List<Token> ts){
     return new ParseResult<Boolean>(true,ts);
  }
}

4.3.2  Parser zum Erkennen von Token

package name.panitz.parser;
import java.util.List;

public class ParseToken<a extends Token> implements Parser<a>{
  final private a t;
  public ParseToken(a _t){t=_t;}
  public ParseResult<a> parse(List<Token> ts){
    if (ts.isEmpty()) return new ParseResult<a>(null,ts);
    if (ts.get(0).equals(t))
      return new ParseResult<a>((a)ts.get(0),ts.subList(1,ts.size()));
    return new ParseResult<a>(null,ts);
  }
}

4.3.3  Parser zum Bilden der Sequenz zweier Parser

• durch die Sequenz mehrer Symbole auf der rechten Seite einer Regel.
• durch mehrere Regelalternativen.

A ::= B  C

package name.panitz.parser;

public class Pair<a,b>{
  final private a e1;
  final private b e2;
  public Pair(a x1,b x2){e1=x1;e2=x2;}
  public a getE1(){return e1;}
  public b getE2(){return e2;}
}

package name.panitz.parser;

import java.util.List;

public class Seq<a,b> implements Parser<Pair<a,b>>{
  final private Parser<a> p1;
  final private Parser<b> p2;
  public Seq(Parser< a> _p1,Parser< b> _p2){p1=_p1;p2=_p2;}

  public ParseResult<Pair<a,b>> parse(List<Token> ts){
    ParseResult<a> r1 = p1.parse(ts);

    if (r1.failed()) return new ParseResult<Pair<a,b>>(null,ts);

    ParseResult<b> r2 = p2.parse(r1.getRemainingToken());

    if (r2.failed()) return new ParseResult<Pair<a,b>>(null,ts);

    return new ParseResult<Pair<a,b>>
                 (new Pair<a,b>(r1.getResult(),r2.getResult())
                 ,r2.getRemainingToken());
  }
}

4.3.4  Parser zum Bilden der Alternative zweier Parser

A ::= B
A ::= C

package name.panitz.parser;

import java.util.List;
import java.util.ArrayList;

public class Alt<a> implements Parser<a>{
  final private Parser<a> p1;
  final private Parser<a> p2;
  public Alt(Parser<a> _p1,Parser<a> _p2){p1=_p1;p2=_p2;}

  public ParseResult<a> parse(List<Token> ts){
    ParseResult<a> r1 = p1.parse(ts);

    if (r1.failed()) return p2.parse(ts);
    return r1;
  }
}

4.3.5  Parser zum Verändern des Ergebnisses

• elementare Parser definieren, die bestimmte Token erkennen
• aus zwei Parsern die Sequenz bilden, die als Ergebnis das Paar der zwei Tailparses hat.
• aus zwei Parsern einen neuen Parser bilden, der einen der beiden Parser anzuwendet.

package name.panitz.parser;
public interface Function<a,b>{
    b apply(a x);
}

package name.panitz.parser;
import java.util.List;
import java.util.ArrayList;

public class Map<a,b> implements Parser<b>{
  final private Parser<a> p1;
  final private Function<a,b> f;
  public Map(Parser<a> _p1,Function<a,b> _f){p1=_p1;f=_f;}

  public ParseResult<b> parse(List<Token> ts){
    ParseResult<a> r1 = p1.parse(ts);

    if (r1.failed()) return new ParseResult<b>(null,ts);
    return new ParseResult<b>
      (f.apply(r1.getResult()),r1.getRemainingToken());
  }
}

4.3.6  Beispiel: arithmetische Ausdrücke

start ::= addExpr
addExpr ::= multExpraddOp addExpr | multExpr
multExpr ::= zahl multOp multExpr | zahl
multOp ::= * | /
addOp ::= + | -

Token

package name.panitz.parser;
public class Zahl implements Token{
  final public int i;
  public Zahl(int _i){i=_i;}
  public boolean equals(Object o){return o instanceof Zahl;} 
}

package name.panitz.parser;
public enum OpToken implements Token{
 add,sub,mult,div;

package name.panitz.parser;

public interface BinFunction<a,b,c>{
  c apply(a x,b y);
}

package name.panitz.parser;

public interface IntOp 
         extends BinFunction<Integer,Integer,Integer>{}

 public IntOp getFunction(){
   switch (this){
     case div : return new IntOp(){
          public Integer apply(Integer x,Integer y){return x/y;}};
     case mult : return new IntOp(){
          public Integer apply(Integer x,Integer y){return x*y;}};
     case add : return new IntOp(){
          public Integer apply(Integer x,Integer y){return x+y;}};
     default : return new  IntOp(){
          public Integer apply(Integer x,Integer y){return x-y;}};
   }
  }
}

AuswertungsParser

package name.panitz.parser;
import java.util.List;

public class ZahlEval implements Parser<Integer>{
  public ParseResult<Integer> parse(List<Token> ts){
    return new Map<Zahl,Integer>
        (new ParseToken<Zahl>(new Zahl(0))
        ,new Function<Zahl,Integer>(){
           public Integer apply(Zahl z){return z.i;}}
        ).parse(ts);
  }
}

package name.panitz.parser;
import java.util.List;

public class GetIntOp implements Function<OpToken,IntOp>{
  public IntOp apply(OpToken t){
    return t.getFunction();
  }
}

package name.panitz.parser;
import java.util.List;

public class MultOpEval implements Parser<IntOp>{
  public ParseResult<IntOp> parse(List<Token> ts){
    return new Map<OpToken,IntOp>
      (new Alt<OpToken>
         (new ParseToken<OpToken>(OpToken.mult)
         ,new ParseToken<OpToken>(OpToken.div))
      ,new GetIntOp()).parse(ts);
  }
}

package name.panitz.parser;
import java.util.List;

public class AddOpEval implements Parser<IntOp>{
  public ParseResult<IntOp> parse(List<Token> ts){
    return new Map<OpToken,IntOp>
      (new Alt<OpToken>
         (new ParseToken<OpToken>(OpToken.add)
         ,new ParseToken<OpToken>(OpToken.sub))
      ,new GetIntOp()).parse(ts);
  }
}

multExpr ::= zahl multOp multExpr | zahl

package name.panitz.parser;

public class DoIntOp
   implements Function<Pair<Integer,Pair<IntOp,Integer>>,Integer>{
  public Integer apply(Pair<Integer,Pair<IntOp,Integer>> x){
    return x.getE2().getE1().apply(x.getE1(),x.getE2().getE2());
  }
}

package name.panitz.parser;
import java.util.List;

public class MultExprEval implements Parser<Integer>{
  public ParseResult<Integer> parse(List<Token> ts){
    return
      new Alt<Integer>
       (new Map<Pair<Integer,Pair<IntOp,Integer>>,Integer>
         (new Seq<Integer,Pair<IntOp,Integer>>
           (new ZahlEval(),new Seq<IntOp,Integer>
                            (new MultOpEval(),new MultExprEval()))
         ,new DoIntOp()
         )
       ,new ZahlEval()
       ).parse(ts);
  }
}

addExpr ::= multExpraddOp addExpr | multExpr

package name.panitz.parser;
import java.util.List;

public class AddExprEval implements Parser<Integer>{
  public ParseResult<Integer> parse(List<Token> ts){
    return
      new Alt<Integer>
       (new Map<Pair<Integer,Pair<IntOp,Integer>>,Integer>
         (new Seq<Integer,Pair<IntOp,Integer>>
           (new MultExprEval(),new Seq<IntOp,Integer>
                            (new AddOpEval(),new AddExprEval()))
         ,new DoIntOp()
         )
       ,new MultExprEval()
       ).parse(ts);
  }
}

package name.panitz.parser;
import java.util.List;

public class EvalArith implements Parser<Integer>{
  Parser<Integer> startExpr = new AddExprEval();

  public ParseResult<Integer> parse(List<Token> ts){
    return startExpr.parse(ts);
  }
}

package name.panitz.parser;
import java.util.List;
import java.util.ArrayList;

public class TestEvalArith {

  public static void main(String[] _){
    List<Token> ts = new ArrayList<Token>();
    ts.add(new Zahl(17));
    ts.add(OpToken.mult);
    ts.add(new Zahl(2));
    ts.add(OpToken.add);
    ts.add(new Zahl(8));

    ParseResult<Integer> res = new EvalArith().parse(ts);
    System.out.println(res.getResult());
    System.out.println(res.getRemainingToken());
  }
}

Aufbau eines Parsbaumes

package name.panitz.parser;
import name.panitz.data.tree.*;
import java.util.List;

public class ZahlTree implements Parser<Tree<String>>{
  public ParseResult<Tree<String>> parse(List<Token> ts){
    return new Map<Zahl,Tree<String>>
        (new ParseToken<Zahl>(new Zahl(0))
        ,new Function<Zahl,Tree<String>>(){
           public Tree<String> apply(Zahl z){
             return new Tree<String>(""+z.i);}}
        ).parse(ts);
  }
}

package name.panitz.parser;
import name.panitz.data.tree.*;

public interface OpTree 
    extends BinFunction<Tree<String>,Tree<String>,Tree<String>>{}

package name.panitz.parser;
import name.panitz.data.tree.*;

import java.util.List;
import java.util.ArrayList;

public class GetOpTree implements Function<OpToken,OpTree>{
  public OpTree apply(final OpToken t){
    return 
      new OpTree(){
        public Tree<String> apply(Tree<String>op1,Tree<String> op2){
          List<Tree<String>> cs = new ArrayList<Tree<String>>();
          cs.add(op1);
          cs.add(op2);
          return new Tree<String>(t.toString(),cs);
        }
      };
  }
}

package name.panitz.parser;
import name.panitz.data.tree.*;

import java.util.List;

public class MultOpTree implements Parser<OpTree>{
  public ParseResult<OpTree> parse(List<Token> ts){
    return new Map<OpToken,OpTree>
      (new Alt<OpToken>
         (new ParseToken<OpToken>(OpToken.mult)
         ,new ParseToken<OpToken>(OpToken.div))
      ,new GetOpTree()).parse(ts);
  }
}

package name.panitz.parser;
import name.panitz.data.tree.*;

import java.util.List;

public class AddOpTree implements Parser<OpTree>{
  public ParseResult<OpTree> parse(List<Token> ts){
    return new Map<OpToken,OpTree>
      (new Alt<OpToken>
         (new ParseToken<OpToken>(OpToken.add)
         ,new ParseToken<OpToken>(OpToken.sub))
      ,new GetOpTree()).parse(ts);
  }
}

package name.panitz.parser;
import name.panitz.data.tree.*;

public class DoOpTree
 implements  Function<Pair<Tree<String>,Pair<OpTree,Tree<String>>>
                     ,Tree<String>> {
  public Tree<String> apply
                   (Pair<Tree<String>,Pair<OpTree,Tree<String>>> x){
    return x.getE2().getE1().apply(x.getE1(),x.getE2().getE2());
  }
}

package name.panitz.parser;
import name.panitz.data.tree.*;

import java.util.List;

public class MultExprTree implements Parser<Tree<String>>{
  public ParseResult<Tree<String>> parse(List<Token> ts){
    return
      new Alt<Tree<String>>
       (new Map<Pair<Tree<String>,Pair<OpTree,Tree<String>>>,Tree<String>>
         (new Seq<Tree<String>,Pair<OpTree,Tree<String>>>
           (new ZahlTree(),new Seq<OpTree,Tree<String>>
                            (new MultOpTree(),new MultExprTree()))
         ,new DoOpTree()
         )
       ,new ZahlTree()
       ).parse(ts);
  }
}

package name.panitz.parser;
import name.panitz.data.tree.*;

import java.util.List;

public class AddExprTree implements Parser<Tree<String>>{
  public ParseResult<Tree<String>> parse(List<Token> ts){
    return
      new Alt<Tree<String>>
       (new Map<Pair<Tree<String>,Pair<OpTree,Tree<String>>>,Tree<String>>
         (new Seq<Tree<String>,Pair<OpTree,Tree<String>>>
           (new MultExprTree(),new Seq<OpTree,Tree<String>>
                            (new AddOpTree(),new AddExprTree()))
         ,new DoOpTree()
         )
       ,new MultExprTree()
       ).parse(ts);
  }
}

package name.panitz.parser;
import java.util.List;
import name.panitz.data.tree.*;

public class TreeArith implements Parser<Tree<String>>{
  Parser<Tree<String>> startExpr = new AddExprTree();

  public ParseResult<Tree<String>> parse(List<Token> ts){
    return startExpr.parse(ts);
  }
}

package name.panitz.parser;
import name.panitz.data.tree.*;
import java.util.List;
import java.util.ArrayList;
import javax.swing.*;

public class TestTreeArith {

  public static void main(String[] _){
    List<Token> ts = new ArrayList<Token>();
    ts.add(new Zahl(17));
    ts.add(OpToken.mult);
    ts.add(new Zahl(2));
    ts.add(OpToken.add);
    ts.add(new Zahl(8));
    ts.add(OpToken.mult);
    ts.add(new Zahl(2));
    ts.add(OpToken.div);
    ts.add(new Zahl(1));
    ts.add(OpToken.add);
    ts.add(new Zahl(1));
    ts.add(OpToken.sub);
    ts.add(new Zahl(1));
    ParseResult<Tree<String>> res = new TreeArith().parse(ts);
    JFrame f = new JFrame();
    f.getContentPane().add(new DisplayTree(res.getResult()));
    f.pack();
    f.setVisible(true);
    System.out.println(res.getRemainingToken());
  }
}

4.3.7  Tokenizer

package name.panitz.parser;
import java.util.List;
import java.util.ArrayList;
import java.io.Reader;
import java.io.StringReader;
import java.io.IOException;

class ArithTokenizer {

  Reader reader; 
  int next=0;
  List<Token> result = new ArrayList<Token>();

  ArithTokenizer(Reader reader){
    this.reader=reader;
    try {
      next= reader.read();
    }catch (IOException _){}
  }

  List<Token> tokenize() throws Exception{
    try {
      while (next>=0){
        char c = (char)next;
        switch (c){

          case '\u0020'  : break;
          case '\n' : break;
          case '\t' : break;

          case '+'  : result.add(OpToken.add) ; break;
          case '-'  : result.add(OpToken.sub) ; break;
          case '*'  : result.add(OpToken.mult); break;
          case '/'  : result.add(OpToken.div) ; break;

          default   : if (Character.isDigit(c)) {
                        result.add(getInt());
                        continue;
                      }else throw new Exception
                            ("unexpected Token found: '"+c+"'");
        }

        next = reader.read();
      }
    }catch (IOException _){}
    return result;
  }

  Token getInt() throws IOException {
    int res=0;
    while (next>=0 && Character.isDigit((char)next)){
      res=res*10+next-48;
        next = reader.read();
    }
      
    return new Zahl(res);
  }

  static List<Token> tokenize(String inp) throws Exception{
    return tokenize(new StringReader(inp));
  }

  static List<Token> tokenize(Reader inp) throws Exception{
      return new ArithTokenizer(inp).tokenize();
  }
}

sep@swe10:~/fh/prog2/examples> java Jugs
     __ __  __  ____   ___      _________________________________________
     || ||  || ||  || ||__      Jugs: the interactive Java interpreter
     || ||__|| ||__||  __||     Copyright (c) 2003 Sven Eric Panitz
     ||         ___||           World Wide Web:
||   ||                                  http://www.tfh-berlin.de/~panitz
\\__//  Version: February 2003  _________________________________________


>ArithTokenizer.tokenize("888+0009   *+-/   9")
[888, add, 9, mult, add, sub, div, 9]
>ArithTokenizer.tokenize("888+0009   *uiu**+- 09")
java.lang.Exception: unexpected Token found: 'u'
>

package name.panitz.parser;
import java.io.*;
import javax.imageio.ImageIO; 
import javax.swing.*; 
import name.panitz.data.tree.Tree;
import name.panitz.data.tree.DisplayTree;
import static name.panitz.data.tree.TreeToFile.treeToFile;

class ArithParsTreeBuilder{
  
  public static void main(String [] args) throws Exception{
    final String fileName = args[0];
    writeParsTreeFile(new FileReader(fileName+".arith"),fileName);    
  }

  static void writeParsTreeFile(Reader reader,String fileName)
                                               throws Exception{
    treeToFile(parsArith(reader),fileName);            
  }

  public static Tree<String> parsArith(Reader reader) 
                                               throws Exception{
    final ParseResult<Tree<String>> res
     = new TreeArith().parse(ArithTokenizer.tokenize(reader));
    return res.getResult();
  }

  public static DisplayTree parseAndShow(String inp) 
                                      throws Exception{
    return new DisplayTree(parsArith(new StringReader(inp)));
  }

  public static void parseAndShowInFrame(String inp)
                                      throws Exception{
    JComponent c = ArithParsTreeBuilder.parseAndShow(inp);
    JFrame f = new JFrame();
    f.getContentPane().add(c);
    f.pack();
    f.setVisible(true);
  }
}

multExpr ::= atomExpr multOp multExpr | atomExpr
atomExpr ::= (addExpr)|zahl

package name.panitz.parser;
public enum Parentheses implements Token{lpar,rpar;}

package name.panitz.parser;

public class DoParentheses
  implements  
    Function<Pair<Parentheses,Pair<Integer,Parentheses>>,Integer>{
  public Integer 
             apply(Pair<Parentheses,Pair<Integer,Parentheses>> x){
    return x.getE2().getE1();
  }
}

{\bf \alph{unteraufgabe})} Schreiben Sie eine Klasse AtomExprEval, die Parser<Integer> implementiert und der Regel für atomExpr entspricht.
{\bf \alph{unteraufgabe})} Ändern Sie die Klasse MultExprEval, so daß sie der geänderten Grammatikregel entspricht.
{\bf \alph{unteraufgabe})} Erweitern Sie die Klasse ArithTokenizer, so daß er auch die beiden Klammersymbole erkennt.

4.4  Parsergeneratoren

4.4.1  javacc

• jjtree: Dieses Programm generiert Klassen, mit denen der Ableitungsbaum eines Parses dargestellt werden kann. Es nimmt als Eingabedatei eine Beschreibung der Grammatik. Diese Datei hat die Endung .jjt. Sie generiert Klassen für die Baumknoten. Zusätzlich generiert es eine Datei mit der Endung .jj. die im nächsten Schritt Eingabe für den eigentlichen Parsergenerator ist.
• javacc: Dieses Programm generiert eine Klasse für den eigentlichen Parser. Seine Eingabe ist eine Beschreibung der Grammatik in einer Datei mit Endung .jj. Sie generiert eine Klasse für den Parser und eine für die Token, die in der Grammatik spezifiziert werden. Zusätzlich werden Klassen zur Fehlerbehandlung generiert.

Beispiel:
Als erstes Beispiel wollen wir für unsere Sprache astronomischer Aussagen einen Parser generieren lassen. Hierzu schreiben wir eine Eingabegrammatikdatei mit den Namen sms.jjt.⁷.

PARSER_BEGIN(SMS)
public class SMS {
}
PARSER_END(SMS)

TOKEN [IGNORE_CASE] :
{ <MOON: "moon">
| <MARS: "mars">
| <MERCURY: "mercury">
| <PHOEBUS: "phoebus">
| <DEIMOS: "deimos">
| <ORBITS: "orbits">
| <IS: "is">
| <A: "a">
}

SKIP :
{ " "
| "\t"
| "\n"
| "\r"
}

void start() : {}
{
  nounPhrase() verbPhrase() 
}

void nounPhrase() : {}
{
  noun()|article() noun()
}

void noun() : {}
{ <MOON>|<MARS>|<MERCURY>|<PHOEBUS>|<DEIMOS>
}

void article() : {}
{<A>}

void verbPhrase() : {}
{
verb() nounPhrase()
}

void verb() : {}
{
 <IS>|<ORBITS>
}

sep@swe10:~/fh/prog2/beispiele/javacc/sms> ls
sms.jjt
sep@swe10:~/fh/prog2/beispiele/javacc/sms> jjtree sms.jjt
Java Compiler Compiler Version 2.1 (Tree Builder)
Copyright (c) 1996-2001 Sun Microsystems, Inc.
Copyright (c) 1997-2001 WebGain, Inc.
(type "jjtree" with no arguments for help)
Reading from file sms.jjt . . .
File "Node.java" does not exist.  Will create one.
File "SimpleNode.java" does not exist.  Will create one.
Annotated grammar generated successfully in sms.jj
sep@swe10:~/fh/prog2/beispiele/javacc/sms> ls
JJTSMSState.java  SMSTreeConstants.java  sms.jj
Node.java         SimpleNode.java        sms.jjt
sep@swe10:~/fh/prog2/beispiele/javacc/sms>

sep@swe10:~/fh/prog2/beispiele/javacc/sms> javacc sms.jj
Java Compiler Compiler Version 2.1 (Parser Generator)
Copyright (c) 1996-2001 Sun Microsystems, Inc.
Copyright (c) 1997-2001 WebGain, Inc.
(type "javacc" with no arguments for help)
Reading from file sms.jj . . .
File "TokenMgrError.java" does not exist.  Will create one.
File "ParseException.java" does not exist.  Will create one.
File "Token.java" does not exist.  Will create one.
File "SimpleCharStream.java" does not exist.  Will create one.
Parser generated successfully.
sep@swe10:~/fh/prog2/beispiele/javacc/sms> ls
JJTSMSState.java     SMSConstants.java      SimpleNode.java     sms.jjt
Node.java            SMSTokenManager.java   Token.java
ParseException.java  SMSTreeConstants.java  TokenMgrError.java
SMS.java             SimpleCharStream.java  sms.jj
sep@swe10:~/fh/prog2/beispiele/javacc/sms>

sep@swe10:~/fh/prog2/beispiele/javacc/sms> javac *.java
sep@swe10:~/fh/prog2/beispiele/javacc/sms> ls
JJTSMSState.class     SMSConstants.class      SimpleNode.class
JJTSMSState.java      SMSConstants.java       SimpleNode.java
Node.class            SMSTokenManager.class   Token.class
Node.java             SMSTokenManager.java    Token.java
ParseException.class  SMSTreeConstants.class  TokenMgrError.class
ParseException.java   SMSTreeConstants.java   TokenMgrError.java
SMS.class             SimpleCharStream.class  sms.jj
SMS.java              SimpleCharStream.java   sms.jjt
sep@swe10:~/fh/prog2/beispiele/javacc/sms>

/* Generated By:JJTree&JavaCC: Do not edit this line. SMS.java */
public class SMS/*bgen(jjtree)*/
implements SMSTreeConstants, SMSConstants {/*bgen(jjtree)*/

  protected static JJTSMSState jjtree = new JJTSMSState();

  static final public void start() throws ParseException {
                /* bgen(jjtree) start */
  SimpleNode jjtn000 = new SimpleNode(JJTSTART);
  boolean jjtc000 = true;
  jjtree.openNodeScope(jjtn000);
    try {
      nounPhrase();
      verbPhrase();
    } catch (Throwable jjte000) {

...



  static final public void nounPhrase() throws ParseException {
                     /* bgen(jjtree) nounPhrase */
  SimpleNode jjtn000 = new SimpleNode(JJTNOUNPHRASE);
  boolean jjtc000 = true;
  jjtree.openNodeScope(jjtn000);
    try {
      switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
      case MOON:
      case MARS:
      case MERCURY:
      case PHOEBUS:
      kcase DEIMOS:


  public SMS(java.io.InputStream stream) {
    if (jj_initialized_once) {


....

public class MainSMS {
  public static void main(String args[]) throws ParseException {
    SMS parser = new SMS(System.in);
    parser.start();
    ((SimpleNode)parser.jjtree.rootNode()).dump("");
  }
}

sep@swe10:~/fh/prog2/beispiele/javacc/sms> javac *.java
sep@swe10:~/fh/prog2/beispiele/javacc/sms> java MainSMS
a moon orbits mars
start
 nounPhrase
  article
  noun
 verbPhrase
  verb
  nounPhrase
   noun
sep@swe10:~/fh/prog2/beispiele/javacc/sms> java MainSMS
mars is a red planet
Exception in thread "main" TokenMgrError: 
Lexical error at line 1, column 11.  Encountered: "r" (114), after : ""
        at SMSTokenManager.getNextToken(SMSTokenManager.java:447)
        at SMS.jj_ntk(SMS.java:298)
        at SMS.noun(SMS.java:84)
        at SMS.nounPhrase(SMS.java:50)
        at SMS.verbPhrase(SMS.java:133)
        at SMS.start(SMS.java:12)
        at MainSMS.main(MainSMS.java:4)
sep@swe10:~/fh/prog2/beispiele/javacc/sms>

options {
   MULTI=true;
   STATIC=false;
}

4.4.2  Parsen und moderne Programmierparadigmen

Appendix A
Lösungen ausgewählter Aufgaben

A.1  Lösung der Punkteaufgabe zu Bäumen

A.1.1  leaves

public List<a> leaves(){
  //leere Liste für das Ergebnis
  List<a> result = new ArrayList<a>();

  //füge die Markierung dieses Knotens zur Ergebnisliste 
  //nur hinzu, wenn es ein Blatt ist
  if (isLeaf()) result.add(mark());

  //für jedes Kind
  for (Tree<a> child:theChildren())
    //erzeuge dessen Knotenliste und füge alle deren Blätter 
    //zum Ergebnis hinzu
    result.addAll(child.leaves());

  return result;
}

Akkumulative Lösung

public List<a> flatten(List<a> result){
  result.add(mark());

  for (Tree<a> child:theChildren())
    child.flatten(result);

  return result;
}

public List<a> flattenAkk(){
  return flatten(new ArrayList<a>());
}

public List<a> leaves(List<a> result){
  if (isLeaf()) result.add(mark());

  for (Tree<a> child:theChildren())
    child.leaves(result);

  return result;
}

public List<a> leavesAkk(){
  return leaves(new ArrayList<a>());
}

Programmierung höherer Ordnung

package name.panitz.data.tree;

interface TreeCondition<a>{
  boolean takeThis(Tree<a> o);
}

public List<a> filter(List<a> result,TreeCondition<a> c){
  //wenn die Bedingung für den Knoten wahr ist, füge
  //ihm dem Ergebnis hinzu
  if (c.takeThis(this)) result.add(mark());

  //für alle Kinder
  for (Tree<a> child:theChildren())
    //rufe den Filter mit gleicher Bedingung auf
    child.filter(result,c);
  
  return result;
}

public List<a> filter(TreeCondition<a> c){
  return filter(new ArrayList<a>(),c);
}

public List leavesFilter(){
  return filter(
     new TreeCondition<a>(){
        public boolean takeThis(Tree<a> t){
          return t.isLeaf();
        }
     });
}

public List<a> flattenFilter(){
  return filter(new TreeCondition<a>(){
                  public boolean takeThis(Tree<a> _){return true;}
                });
}

public List<a> nodesWithTwoChildren(){
  return filter(new TreeCondition<a>(){
                  public boolean takeThis(Tree<a> t){
                    return t.theChildren().size()==2;
                  }
                });
}

public List<a> nodesMarkedWith(final a o){
  return filter(new TreeCondition<a>(){
                  public boolean takeThis(Tree<a> t){
                    return t.mark().equals(o);
                  }
                });
}

public boolean containsFilter(a o){
  return !nodesMarkedWith(o).isEmpty();
}

A.1.2  show

  public String show(String indent){
    //zeige diesen Knoten mit Einrückung
    String result = indent+mark();

    //erhöhe die Einrückung
    indent=indent+"  ";

    //für jedes Kind
    for (Tree<a> child:theChildren())
     //erzeuge neue Zeile und zeige Kind mit neuer Einrückung
      result=result+"\n"+child.show(indent);
    
    return result;
  }

  public String show(){
      return show("");
  }

Akkumulative Lösung

  public StringBuffer show(String indent,StringBuffer result){
    //zeige diesen Knoten mit Einrückung
    result.append(indent);
    result.append(mark().toString());

    //erhöhe die Einrückung
    indent=indent+"  ";

    //für jedes Kind
    for (Tree<a> child:theChildren()){
     //erzeuge neue Zeile und zeige Kind mit neuer Einrückung
      result.append("\n");
      child.show(indent,result);
    }
    return result;
  }

  public String showAkk(){
      return show("",new StringBuffer()).toString();
  }

A.1.3  contains

  public boolean contains(a o){
    //bin ich schon der gesuchte Knoten? Wenn ja ende mit erfolg
    if (mark().equals(o)) return true;

    //für jedes Kind
   for (Tree<a> child:theChildren()){
      //wenn es den Knoten enthält, beende mit erfolg
      if (child.contains(o)) return true;
    }
    //keiner der Knoten enthielt das Objekt
    return false;
  }

A.1.4  maxDepth

  public int maxDepth(){
    //anfangstiefe
    int result = 0;

    //für jedes Kind
   for (Tree<a> child:theChildren()){
      //berechne seine maximale Tiefe
      int n = child.maxDepth();

      //ist sie höher als die bisher gefundene, dann nimm diese
      if (n>result) result=n;
    } 

    //erhöhe Ergebnis um eins für die Wurzel
    return result+1;
  }

A.1.5  getPath

naive Lösung

  public List<a> getPathBad(a o){
    List<a> result = new ArrayList<a>();

  //wenn Du irgendwo das Objekt enthältst, liegst Du auf den Pfad
    if (contains(o)) { result.add(mark());}

    //für jedes Kind
   for (Tree<a> child:theChildren()){
      //füge den Pfad zum fraglichen Objekt hinzu
      result.addAll(child.getPathBad(o));
    }
    return result;
  }

Lösung höherer Ordnung mit Hilfe von filter

public List<a> getPathFilter(final a o){
   return filter(
      new TreeCondition<a>(){
        public boolean takeThis(Tree<a> e){
          return e.contains(o);
        }  
      }
   );
}

performantere Lösung

  public List<a> getPath(a o,List<a> result){
    //bist Du selbst der Knoten, 
    //dann ende mit der einelementigen Liste
    if (mark().equals(o)) { result.add(mark()); return result;}

   for (Tree<a> child:theChildren()){
      //berechne Pfad vom Kind zum Objekt 
      final List<a> path = child.getPath(o,result);

      //Kind hat einen solchen Pfad
      if (!path.isEmpty()){
        //hänge Dich vorne dran
        result.add(0,mark());
        //und fertig
        return result;
      }
    }
    return result;
  }

  public List<a> getPath(a o){
      return getPath(o,new ArrayList<a>());
  }

A.1.6  iterator

  public Iterator<a> iterator(){
      return flatten().iterator();  
  }

A.1.7  sameStructure

  public <b> boolean sameStructure(Tree<b> other){
    //haben beide Bäume gleich viel Kinder. 
    if(this.theChildren().size()!=other.theChildren().size())
        //wenn nein, dann sind sie nicht strukturgleich
        return false;

    //Iteriere über die Kinder beider Bäume
    Iterator<Tree<a>> it1=this.theChildren().iterator();
    Iterator<Tree<b>> it2=other.theChildren().iterator();

    //solange es noch Kinder gibt
    while (it1.hasNext()){
      //hohle das nächste Kind beider Bäume
      final Tree<a> thisChild = it1.next();
      final Tree<b> otherChild =it2.next();

      //sind diese nicht strukturgleich, dann breche ab
      if (!thisChild.sameStructure(otherChild)) return false;
    }
    
    //die Strukturgleichheit wurde nie verletzt
    return true;
  }

A.1.8  equals

if (!this.mark().equals(other.mark())) return false;

  public <b> boolean equals(Tree<b> other){
      if (!this.sameStructure(other)) return false;
      return this.flatten().equals(other.flatten());
  }

  public boolean equals(Object other){
      if (! (other instanceof Tree)) return false;
      Tree<?> o = (Tree<?>) other;
      return this.equals(o);
  }
}//end der Klasse Tree

Appendix B
Hilfklasssen zu Swing

package name.panitz.swing.threadTest;
import javax.swing.SwingUtilities;

/**
 * This is the 3rd version of SwingWorker (also known as
 * SwingWorker 3), an abstract class that you subclass to
 * perform GUI-related work in a dedicated thread.  For
 * instructions on using this class, see:
 * 
 * http://java.sun.com/docs/books/tutorial/uiswing/misc/threads.html
 *
 * Note that the API changed slightly in the 3rd version:
 * You must now invoke start() on the SwingWorker after
 * creating it.
 */
public abstract class SwingWorker {
    private Object value;  // see getValue(), setValue()
    private Thread thread;

    /** 
     * Class to maintain reference to current worker thread
     * under separate synchronization control.
     */
    private static class ThreadVar {
        private Thread thread;
        ThreadVar(Thread t) { thread = t; }
        synchronized Thread get() { return thread; }
        synchronized void clear() { thread = null; }
    }

    private ThreadVar threadVar;

    /** 
     * Get the value produced by the worker thread, or null if it 
     * hasn't been constructed yet.
     */
    protected synchronized Object getValue() { 
        return value; 
    }

    /** 
     * Set the value produced by worker thread 
     */
    private synchronized void setValue(Object x) { 
        value = x; 
    }

    /** 
     * Compute the value to be returned by the <code>get</code> method. 
     */
    public abstract Object construct();

    /**
     * Called on the event dispatching thread (not on the worker thread)
     * after the <code>construct</code> method has returned.
     */
    public void finished() {
    }

    /**
     * A new method that interrupts the worker thread.  Call this method
     * to force the worker to stop what it's doing.
     */
    public void interrupt() {
        Thread t = threadVar.get();
        if (t != null) {
            t.interrupt();
        }
        threadVar.clear();
    }

    /**
     * Return the value created by the <code>construct</code> method.  
     * Returns null if either the constructing thread or the current
     * thread was interrupted before a value was produced.
     * 
     * @return the value created by the <code>construct</code> method
     */
    public Object get() {
        while (true) {  
            Thread t = threadVar.get();
            if (t == null) {
                return getValue();
            }
            try {
                t.join();
            }
            catch (InterruptedException e) {
                Thread.currentThread().interrupt(); // propagate
                return null;
            }
        }
    }


    /**
     * Start a thread that will call the <code>construct</code> method
     * and then exit.
     */
    public SwingWorker() {
        final Runnable doFinished = new Runnable() {
           public void run() { finished(); }
        };

        Runnable doConstruct = new Runnable() { 
            public void run() {
                try {
                    setValue(construct());
                }
                finally {
                    threadVar.clear();
                }

                SwingUtilities.invokeLater(doFinished);
            }
        };

        Thread t = new Thread(doConstruct);
        threadVar = new ThreadVar(t);
    }

    /**
     * Start the worker thread.
     */
    public void start() {
        Thread t = threadVar.get();
        if (t != null) {
            t.start();
        }
    }
}

Appendix C
Beispielaufgaben

Appendix D
Referate

D.1  JNI: Javas Schnittstelle zu C

D.2  Java 2D Grafik

D.3  Java 3D Grafik

D.4  Java und Netzwerk

D.5  Java und Datenbanken

Appendix E
Gesammelte Aufgaben

• einen Knopf zum Erhöhen eines Zählers.
• einen Knopf zum Verringern des Zählers um 1.
• einen Knopf zum Zurücksetzen des Zählers auf 0.

public static void main(String [] args) {
  StrichKreis k = new StrichKreis(120);
  JFrame f = new JFrame();
  JPanel p = new JPanel();
  p.add(new StrichKreis(120));
  p.add(new StrichKreis(10));
  p.add(new StrichKreis(60));
  p.add(new StrichKreis(50));
  p.add(new StrichKreis(70));
  f.getContentPane().add(p);

  f.pack();
  f.setVisible(true);
}

{\bf \alph{unteraufgabe})} List leaves(): erzeugt eine Liste der Markierungen an den Blättern des Baumes.
{\bf \alph{unteraufgabe})} String show(): erzeugt eine textuelle Darstellung des Baumes. Jeder Knoten soll eine eigene Zeile haben. Kinderknoten sollen gegenüber einem Elternknoten eingerückt sein.
Beispiel:

william
  charles
    elizabeth
    phillip
  diana
    spencer

Tipp: Benutzen Sie eine Hilfsmethode
String showAux(String prefix),
die den String prefix vor den erzeugten Zeichenketten anhängt.
{\bf \alph{unteraufgabe})} boolean contains(a o): ist wahr, wenn eine Knotenmarkierung gleich dem Objekt o ist.
{\bf \alph{unteraufgabe})} int maxDepth(): gibt die Länge des längsten Pfades von der Wurzel zu einem Blatt an.
{\bf \alph{unteraufgabe})} List<a> getPath(a o): gibt die Markierungen auf dem Pfad von der Wurzel zu dem Knoten, der mit dem Objekt o markiert ist, zurück. Ergebnis ist eine leere Liste, wenn ein Objekt gleich o nicht existiert.
{\bf \alph{unteraufgabe})} java.util.Iterator<a> iterator(): erzeugt ein Iterator über alle Knotenmarkierungen des Baumes.
Tipp: Benutzen Sie bei der Umsetzung die Methode flatten.
{\bf \alph{unteraufgabe})} public boolean equals(Object other): soll genau dann wahr sein, wenn other ein Baum ist, der die gleiche Struktur und die gleichen Markierungen hat.
{\bf \alph{unteraufgabe})} <b>boolean sameStructure(Tree<a> other): soll genau dann wahr sein, wenn der Baum other die gleiche Struktur hat. Die Markierungen der Knoten können hingegen unterschiedlich sein.

{\bf \alph{unteraufgabe})} Schreiben sie entsprechend die Methode:
static public SearchTree rotateLeft(SearchTree t)
{\bf \alph{unteraufgabe})}
Schreiben Sie in der Klasse BinTree die entsprechende modifizierende Methode rotateLeft()
{\bf \alph{unteraufgabe})} Testen Sie die beiden Rotierungsmethoden. Testen Sie, ob die Tiefe der Kinder sich verändert und ob die Inordnung gleich bleibt. Testen Sie insbesondere auch einen Fall, in dem die NullPointerException abgefangen wird.

multExpr ::= atomExpr multOp multExpr | atomExpr
atomExpr ::= (addExpr)|zahl

package name.panitz.parser;
public enum Parentheses implements Token{lpar,rpar;}

package name.panitz.parser;

public class DoParentheses
  implements  
    Function<Pair<Parentheses,Pair<Integer,Parentheses>>,Integer>{
  public Integer 
             apply(Pair<Parentheses,Pair<Integer,Parentheses>> x){
    return x.getE2().getE1();
  }
}

{\bf \alph{unteraufgabe})} Schreiben Sie eine Klasse AtomExprEval, die Parser<Integer> implementiert und der Regel für atomExpr entspricht.
{\bf \alph{unteraufgabe})} Ändern Sie die Klasse MultExprEval, so daß sie der geänderten Grammatikregel entspricht.
{\bf \alph{unteraufgabe})} Erweitern Sie die Klasse ArithTokenizer, so daß er auch die beiden Klammersymbole erkennt.

options {
   MULTI=true;
   STATIC=false;
}

Index

List of Figures

Bibliography

[ACL02]

César F. Acebal, Raúl Izquierdo Castanedo, and Juan M. Cueva Lovelle. Good design principles in a compiler university course. ACM SIGPLAN Notices, 37(4):62-73, 2002.

[Cho56]

Noam Chomsky. Three models for the description of language. IRE Transactions of Information Theory, 2:113-124, 1956.

[CWH00]

Mary Campione, Kathy Walrath, and Alison Huml. The Java Tutorial Third Edition. Addison-Wesley Publishing Company, 2000.

[FL89]

R. Frost and J. Launchbury. Constructing natural language interpreters in a lazy functional languages. The Computer Journal, 32(2):108-121, 1989.

[GKS01]

Ulrich Grude, Chritsoph Knabe, and Andreas Solymosi. Compilerbau. Skript zur Vorlesung, TFH Berlin, 2001. www.tfh-berlin.de/~grude/SkriptCompilerbau.pdf.

[Gru01]

Ulrich Grude. Einführung in gentle. Skript, TFH Berlin, 2001. www.tfh-berlin.de/~grude/SkriptGentle.pdf.

[Joh75]

Stephen C. Johnson. Yacc: Yet another compiler compiler. Technical Report 39, Bell Laboratories, 1975.

[NB60]

Peter Naur and J. Backus. Report on the algorithmic language ALGOL 60. Communications of the ACM, 3(5):299-314, may 1960.

[Pan03]

Sven Eric Panitz. Programmieren I. Skript zur Vorlesung, 2. revidierte Auflage, 2003. www.panitz.name/prog1/index.html.

[Tur85]

D. A. Turner. Miranda: A non-strict functional language with polymorphic types. In Functional Programming Languages and Computer Architecture, number 201 in Lecture Notes in Computer Science, pages 1-16. Springer, 1985.