OOP mit Java: Generische Abstrakte Datentypen

als abstrakte Klasse ohne Implementierungsteil

template <class Element>
class TemplateStack {
 
public:
 
  //--------------------
  // die Attribut-Funktionen
 
  virtual
  int isEmpty() const = 0;
 
  virtual
  Element & top() const = 0;
 
  //--------------------
  // die modifizierenden Funktionen
 
  virtual
  TemplateStack<Element> & push(Element & e) = 0;
 
  virtual
  TemplateStack<Element> & pop() = 0;
 
 
  //--------------------
  // die Vorbedingungen
 
  virtual
  int pre_pop() {
    return
      ! isEmpty();
  }
 
  virtual
  int pre_top() {
    return
      ! isEmpty();
  }
 
  //--------------------
  // der Destruktor
 
  virtual
  ~TemplateStack() {}
};
 

Ein template Stack in C++

mit konkreter Implementierung und Instanziierung

#include "TemplateStack.cc"
 
template <class Element>
class SimpleTemplateStack : public TemplateStack<Element> {
 
 
private:
 
  // die Datenfelder: nicht nach aussen sichtbar
 
  struct StackStruct {
    unsigned top;
    Element  elems[100];
  } * s;
 
 
public:
 
  //--------------------
  // der Konstruktor
 
  SimpleTemplateStack() {
    s = new StackStruct;
    s->top = 0;
  }
 
  //--------------------
  // der Destruktor
 
  ~SimpleTemplateStack() {
    delete s;
  }
 
  //--------------------
  // die Attribut-Funktionen
 
  virtual
  int isEmpty() const {
    return
      s->top == 0;
  }
 
  virtual
  Element & top() const {
    return
      s->elems[s->top-1];
  }
 
  //--------------------
  // die modifizierenden Funktionen
 
  virtual
  TemplateStack<Element> & push(Element & e) {
    s->elems[s->top++] = e;
    return
      *this;
  }
 
  virtual
  TemplateStack<Element> & pop() {
    s->top--;
    return
      *this;
  }
 
  // Vorbedingungen sind schon implementiert
};
 
//--------------------
// ein int Stack
 
typedef SimpleTemplateStack<int> SimpleIntStack;
 
// ein double Stack
 
typedef SimpleTemplateStack<double> SimpleDoubleStack;

Generische ADTs in Java

	Konzept der generischen ADTs gut, aber die Umsetzung in C++ wenig elegant.

bis Java 1.4 nicht vorhanden

erst in Java 1.5 als Erweiterung

Lösung für Java < 1.5:
Eine Klasse für beliebige Objekte

public
abstract
class GenStack {
 
  //--------------------
  // der Konstruktor
 
  public
  GenStack() { }
 
  //--------------------
  // die Attribut-Funktionen
 
  public
  abstract
  boolean isEmpty();
 
  public
  abstract
  Object  top();                   // <-----
 
  //--------------------
  // die modifizierenden Funktionen
 
  public
  abstract
  GenStack push(Object e);         // <-----
 
  public
  abstract
  GenStack pop();
 
  //--------------------
  // die Vorbedingungen
 
  public
  boolean preTop() {
    return
      ! isEmpty();
  }
 
  public
  boolean prePop() {
    return
      ! isEmpty();
  }
}
 

Die Deklaration von

GenStack push(Object e)

erlaubt es, mehrere Operationen zu verketten

s.push(...).push(...).push(...);

Eine Implementierung

class SimpleGenStack extends GenStack{
 
  // die Datenfelder: nicht nach aussen sichtbar
 
  private
  Object [] a;                     // <-----
 
  private
  int i;
 
  //--------------------
  // der Konstruktor
 
  public
  SimpleGenStack() {
    super();                       // redundant
    a = new Object[20];            // <-----
    i = 0;
  }
 
  //--------------------
  // die Attribut-Funktionen
 
  public
  boolean isEmpty() {
    return
      i == 0;
  }
 
  public
  Object top() {                   // <-----
    return
      a[i-1];
  }
 
  //--------------------
  // die modifizierenden Funktionen
 
  public
  GenStack push(Object e) {        // <-----
    a[i++] = e;
    return
      this;
  }
 
  public
  GenStack pop() {
    a[--i] = null;
    return
      this;
  }
 
  // Vorbedingungen sind schon implementiert
}

	einfache Umsetzung: Exemplare von `Object` werden gespeichert
	keine Typüberprüfung zur Übersetzungszeit: Es gibt nur eine Sorte Körbe, in diese passt immer alles, auch Äpfel und Birnen zusammen!!
	Wie speichert man elementare Werte, z.B. ints? Wrapper-Klassen: elementare Werte werden in Klassen eingepackt, z.B. `Integer`.
	upcasts beim Einfügen von Elementen downcasts beim Auslesen von Elementen

Generische ADTs mit Java 1.5

analog zu C++
mit Typüberprüfung zur Übersetzungszeit

public
abstract
class GenericStack <Element> {
 
  //--------------------
  // der Konstruktor
 
  public
  GenericStack() { }
 
  //--------------------
  // die Attribut-Funktionen
 
  public
  abstract
  boolean isEmpty();
 
  public
  abstract
  Element top();
 
  //--------------------
  // die modifizierenden Funktionen
 
  public
  abstract
  GenericStack<Element> push(Element e);
 
  public
  abstract
  GenericStack<Element> pop();
 
  //--------------------
  // die Vorbedingungen
 
  public
  boolean preTop() {
    return
      ! isEmpty();
  }
 
  public
  boolean prePop() {
    return
      ! isEmpty();
  }
}
 
 

Eine konkrete Implementierung nach der gleichen Art wie oben

class SimpleGenericStack<Element>
    extends GenericStack<Element> {
 
  // die Datenfelder: nicht nach aussen sichtbar
 
  private
  Element [] a;                     // <-----
 
  private
  int i;
 
  //--------------------
  // der Konstruktor
 
  public
  SimpleGenericStack() {
 
    // a = new Element[20];            // so leider nicht
 
    a = (Element []) new Object[20];   // aber so: mit downcast
 
    
    /*
    a = (Element [])                   // oder so: mit downcast
        java.lang.reflect.Array.
        newInstance(a.getClass().getComponentType(), 20);
    */
 
    i = 0;
  }
 
  //--------------------
  // die Attribut-Funktionen
 
  public
  boolean isEmpty() {
    return
      i == 0;
  }
 
  public
  Element top() {                   // <-----
    return
      a[i-1];
  }
 
  //--------------------
  // die modifizierenden Funktionen
 
  public
  GenericStack<Element> push(Element e) {        // <-----
    a[i++] = e;
    return
      this;
  }
 
  public
  GenericStack<Element> pop() {
    a[--i] = null;
    return
      this;
  }
 
  // Vorbedingungen sind schon implementiert
}
 

Eine Anwendung

class SimpleGenericTest {
 
    // zwei Stacks mit unterschiedlichen Elementtypen
 
    GenericStack<Integer> intStack;
 
    GenericStack<String> stringStack;
 
    void test() {
        intStack
            .push(new Integer(1))
            .push(new Integer(2))
            .push(new Integer(3));
 
        // autoboxing:
        // die int-Zahlen werden automatisch
        // in Integer-Objekte eingewickelt
 
        intStack.push(1).push(2).push(3);
 
        stringStack.push("abc").push("xyz");
    }
}

ADTs mit Laufzeit-Typüberprüfung

	Syntax sehr ähnlich wie bei C++
	Für Java 1.5 ist die JVM nicht geändert worden: Abwärtskompatibilität
	Typparameter werden in Java vollständig zur Übersetzungszeit ausgewertet und sind im JVM Code nicht mehr vorhanden
	Typparameter können nicht zur Laufzeitbeschleunigung durch Vermeidung von downcasts genutzt werden.
	Primitiven Typen sind nicht als Typparameter zugelassen.
	Namenskonvention: Kurze Namen (häufig ein Großbuchstabe) als Bezeichner für Typparameter

das Stack-Beispiel (für Java > 1.4 weniger von Bedeutung)

Im Stack Objekt wird der Typ der zugelassenen Elemente gespeichert.
Beim Einfügen in den Stack wird der Typ des einzufügenden Elements mit dem im Stack gespeicherten Typ auf Zuweisungskompatibilität geprüft.

Lösung: push muss modifiziert werden

class SimpleTypedStack extends SimpleGenStack { 
 
  // die Typinformation
 
  private
  Class elementType;
 
  //--------------------
  // der Konstruktor
 
  public
  SimpleTypedStack(Class elementType) {
    super();            // redundant
    this.elementType = elementType;
  }
 
  //--------------------
  // push wird reimplementiert
 
  public
  GenStack push(Object e) {
 
    // Laufzeitueberpruefung auf korrekten Typ von e
    if ( ! elementType.isAssignableFrom(e.getClass()) )
      throw
        new IllegalArgumentException
              ("wrong element type: "
               + e.getClass().toString()
               + ", "
               + elementType.toString()
               + " expected");
 
    return
      super.push(e);
  }
}

und ein Testprogramm

public
class SimpleTypedStackTest {
 
  public
  static
  void main(String[] argv) {
    Integer i =
      new Integer(42);
 
    Double d =
      new Double(47.11);
 
    //--------------------
    // ein Integer stack
 
    GenStack intStack =
      new SimpleTypedStack(i.getClass());
 
    // ein stack fuer Double
 
    GenStack doubleStack =
      new SimpleTypedStack(d.getClass());
 
    // ein stack fuer stacks    
 
    GenStack stackStack =
      new SimpleTypedStack(intStack.getClass());
 
    //--------------------
    // o.k.
 
    intStack.push(i);
 
    // Typ Konflikt
 
    try {
      intStack.push(d);
    }
    catch ( IllegalArgumentException e ) {
      System.out.println(e);
    }
  }
}

Ausgabe:

java.lang.IllegalArgumentException:
wrong element type: class java.lang.Double,
class java.lang.Integer expected

Object enthält Methode Class getClass()

Class enthält boolean isAssignableFrom(Class cls)

Generische Abstrakte Datentypen

Begriffe

Ein template Stack in C++

Ein template Stack in C++

Generische ADTs in Java

Generische ADTs mit Java 1.5

ADTs mit Laufzeit-Typüberprüfung