Programmieren, Algorithmen und Datenstrukturen 2 (Praktikum 2)

Aufgabe 1: Generalisierung / Vererbung

a) Definieren Sie in Anlehnung an die Vorlesung / Hörsaalübung widget als abstrakte Basisklasse und pro und acc als Klassen, die direkt aus widget abgeleitet sind. Sehen Sie in der abstrakten Basisklasse eine einfach verkettete Liste mit den Objekten aller abgeleiteten Klassen vor. Denken Sie sich pro Klasse mindestens zwei beliebige Attribute (Datenmember, z.B. name und value ) und mindestens drei beliebige Methoden (Memberfunktionen, z.B. set(), increase() ) plus Konstruktoren aus, darunter auf jeden Fall print() zur Ausgabe.

b) Planen Sie, wie Sie Ihren Quellcode systematisch und möglichst umfangreich testen. Überlegen Sie sich, welche Fehler auftreten könnten und entwerfen Sie mindestens 10 Testfälle. Passen Sie Ihre Klassen so an, dass bei kritischen Situationen Ausnahmen geworfen werden – finden Sie mindestens drei Fehlerzustände, die Sie mit einer Ausnahme melden. Dokumentieren Sie alle Tests und erwarteten Ergebnisse.

c) Implementieren Sie einen main() Treiber, um Ihre Klassen gem. Ihrem Testplan aus b) zu überprüfen. Legen Sie u.a. mindestens je 10 Objekte vom Typ pro bzw. acc an und geben Sie diese in einer Schleife über einen widget* wieder aus. Verbessern Sie, bis Ihre Lösung funktioniert.

#include "error.h"
#include "Widget.h"
#include "Acc.h"
#include "Pro.h"

using std::exception;
using std::cerr;

int main() {
    try {
        Acc acc1("Acc1", 1, "a", 11);
        Pro pro1("Pro1", 2, "b", 12);
        Acc acc2("Acc2", 3, "c", 13);
        Acc acc3("Acc3", 4, "d", 14);
        Pro pro2("Pro2", 5, "e", 15);
        Pro pro3("Pro2", 5, "e", 15);
        Pro pro4("Pro2", 5, "e", 15);
        Pro pro5("Pro2", 5, "e", 15);
        Acc acc4("Acc3", 4, "d", 14);
        Acc acc5("Acc3", 4, "d", 14);

        pro2.print_list();
    } catch (exception& e) {
        cerr << e.what();
    } catch (...) {
        cerr << "Unbekannter Fehler führt zum Abbruch des Programms.";
    }
}

#ifndef ACC_H
#define	ACC_H

#include "Widget.h"

class Acc : public Widget {
public:
    //Konstruktoren
    Acc();
    Acc(string, int, string, int);

    // Print-Methode
    const void print() ;

    // Set-Methoden
    void set_accname(string);
    void set_accvalue(int);

    // Get-Methoden
    const string get_accname() ;
    const int get_accvalue() ;

    // Modifikatoren
    void increase_accvalue();
    void decrease_accvalue();

private:
    string saccname;
    int iaccvalue;

};

#endif	/* ACC_H */

#include "Acc.h"
using std::cout;
using std::endl;

Acc::Acc() :
Widget(), saccname(""), iaccvalue(0) {
}

Acc::Acc(string widgetname, int widgetvalue, string accname, int accvalue) :
Widget(widgetname, widgetvalue), saccname(accname), iaccvalue(accvalue) {
}

void Acc::print() const {
    cout << "---Acc---" << endl;
    cout << "Widget-Name:\t" << get_widgetname() << endl;
    cout << "Widget-Wert:\t" << get_widgetvalue() << endl;
    cout << "Account-Name:\t" << saccname  << endl;
    cout << "Account-Wert:\t" << iaccvalue  << endl;
}

void Acc::set_accname(const string sname) {
    saccname = sname;
}

void Acc::set_accvalue(const int ivalue) {
    iaccvalue = ivalue;
}

string Acc::get_accname() const {
    return saccname;
}

int Acc::get_accvalue() const {
    return iaccvalue;
}

void Acc::increase_accvalue() {
    iaccvalue++;
}

void Acc::decrease_accvalue() {
    iaccvalue--;
}

#ifndef PRO_H
#define	PRO_H

#include "Widget.h"

class Pro : public Widget {
public:
    //Konstruktoren
    Pro();
    Pro(string, int, string, int);

    //Print-Methoden
    const void print() ;

    //Set-Methoden
    void set_proname(string);
    void set_provalue(int);

    //Get-Methoden
    const string get_proname() ;
    const int get_provalue() ;

    //Modifikatoren
    void increase_provalue();
    void decrease_provalue();

private:
    string sproname;
    int iprovalue;

};

#endif	/* PRO_H */

#include "Pro.h"
using std::cout;
using std::endl;

Pro::Pro() :
Widget(), sproname(""), iprovalue(0) {
}

Pro::Pro(string widgetname, int widgetvalue, string proname, int provalue) :
Widget(widgetname, widgetvalue), sproname(proname), iprovalue(provalue) {
}

void Pro::print() const {
    cout << "---Pro---" << endl;
    cout << "Widget-Name:\t" << get_widgetname() << endl;
    cout << "Widget-Wert:\t" << get_widgetvalue() << endl;
    cout << "Pro-Name:\t" << sproname  << endl;
    cout << "Pro-Wert:\t" << iprovalue  << endl;
}

void Pro::set_proname(const string sname) {
    sproname = sname;
}

void Pro::set_provalue(const int ivalue) {
    iprovalue = ivalue;
}

string Pro::get_proname() const {
    return sproname;
}

int Pro::get_provalue() const {
    return iprovalue;
}

void Pro::increase_provalue() {
    iprovalue++;
}

void Pro::decrease_provalue() {
    iprovalue--;
}

#ifndef WIDGET_H
#define	WIDGET_H

#include
#include
using std::string;

class Widget {
public:
    //Konstruktoren
    Widget();
    Widget(string, int);

    //Print-Methoden
    const virtual void print()  = 0;
    void print_list();

    //Set-Methoden
    void set_widgetname(string);
    void set_widgetvalue(int);

    //Get-Methoden
    const string get_widgetname() ;
    const int get_widgetvalue() ;

    //Modifikatoren
    void increase_widgetvalue();
    void decrease_widgetvalue();

    Widget* next;

private:
    string swidgetname;
    int iwidgetvalue;
    static Widget* list;
};

#endif	/* WIDGET_H */

#include "Widget.h"
using std::cout;
using std::endl;

Widget* Widget::list = 0;

//Standard-Konstruktor
Widget::Widget()
: next(list) {
    list = this;
}

//Konstruktor
Widget::Widget(string widgetname, int widgetvalue) :
swidgetname(widgetname), iwidgetvalue(widgetvalue), next(list) {
    list = this;
}

//Print-Methode für alle Objekte
void Widget::print_list() {
    for (Widget* w = list; w; w = w->next) {
        w->print();
        cout << endl;
    }
}

//Widgetname setzen
void Widget::set_widgetname(const string sname) {
    swidgetname = sname;
}

//Widgetvalue setzen
void Widget::set_widgetvalue(const int ivalue) {
    iwidgetvalue = ivalue;
}

// Widgetname holen
string Widget::get_widgetname() const {
    return swidgetname;
}

// Widgetvalue holen
int Widget::get_widgetvalue() const {
    return iwidgetvalue;
}

// Widgetvalue um 1 inkrementieren
void Widget::increase_widgetvalue() {
    iwidgetvalue++;
}

// Widgetvalue um 1 dekrementieren
void Widget::decrease_widgetvalue() {
    iwidgetvalue--;
}

#ifndef ERROR_H
#define	ERROR_H

#include
#include

using std::string;
using std::runtime_error;

void error (string s)
{throw runtime_error(s);}

void error (string s1, string s2)
{error(s1+s2);}
#endif	/* ERROR_H */

Aufgabe 2: Bresenham-Algorithmus, char-Plotter

a) Implementieren Sie Ihre eigene Version des Bresenham-Algorithmus auf Basis der in der Vorlesung zu Figurenklassen und Rasterpunkten besprochenen Inhalte. Definieren Sie die Frame Klasse, implementieren Sie den Algorithmus zunächst aber nur „stand-alone“, d.h. als Supportfunktion und nicht als Methode für Objekte von Typen, die vom Typ Shape abgeleitet sind.

b) Planen Sie, wie Sie ihre Supportfunktion zur Ermittlung von Rasterpunkten für gerade Linien und deren Aufgabe auf einen Frame* gründlich über einen geeigneten main() Treiber testen. Dokumentieren Sie Ihren Testplan und die erwarteten Ergebnisse.

c) Implementieren Sie den char-Plotter void Frame::frame_dump() const je einmal mit der formatierten Ausgabe über den << Operator ( cout << ). Führen Sie Ihren Testplan aus b) in einem geeigneten main() Treiber durch.

d) Implementieren Sie für den char-Plotter void Frame::frame_dump() const auch mit der unformatierte Ausgabe per cout.put() . Instrumentieren Sie nun Quellcode mit clock() und messen Sie die Laufzeitunterschiede beim Plotten eines großen Frames. Überlegen Sie sich, wie Sie dabei vorgehen. Dokumentieren Sie alle Tests und Ergebnisse. Welche Schlussfolgerungen ziehen Sie aus Ihren Ergebnissen?

e) Wie könnte man die frame_dump() Implementierung beschleunigen? Machen Sie einen Vorschlag.

f) Optional: implementieren Sie Ihren Vorschlag aus e) und führen Sie weitere Messungen durch.

/*
 * File:   Frame.h
 * Author: maximilian.krieg
 *
 * Created on 20. April 2012, 12:42
 */

#ifndef FRAME_H
#define	FRAME_H

class Frame;
class Coordinate;

const int XMAX = 55; // Zeichen pro Frame-Zeile (55)
const int YMAX = 10000; // Zeilen pro Frame   (34)
void draw_line(Frame*, Coordinate, Coordinate);

class Frame {
public:

    enum color {
	on = ' ', off = '*'
    };

    Frame();

    void put_point(int, int); // Punkt im Frame speichern
    void frame_reset(); // Frame "leeren"
    void frame_dump() const; // Frame auf die Konsole ausgeben
    void frame_dump(bool) const; // Frame auf die Konsole ausgeben
    void frame_dump(int) const; // Frame auf die Konsole ausgeben
    bool on_frame(int, int) const; // "Clipping"

private:
    char frame[XMAX][YMAX];
};
#endif	/* FRAME_H */

/*
 * File:   Frame.cpp
 * Author: maximilian.krieg
 *
 * Created on 20. April 2012, 12:42
 */

#include "Frame.h"
#include "Coordinate.h"
#include
using std::cout;
using std::endl;
using std::string;

// Standardkonstruktor für Frames
Frame::Frame() {
    frame_reset();
}

// Punkt im Frame speichern
void Frame::put_point(int x, int y) {
    if (on_frame(x, y)) {
        frame[x][y] = on;
    }
}

// Frame "leeren"
void Frame::frame_reset() {
    for (int x = 0; x < XMAX; x++) {
        for (int y = 0; y < YMAX; y++) {             frame[x][y] = off;         }     }     frame[0][0] = '*'; } // Frame auf die Konsole ausgeben  void Frame::frame_dump() const {     for (int y = YMAX - 1; y >= 0; --y) {
        for (int x = 0; x < XMAX; x++) {
            cout << frame[x][y];
        }
        cout << endl;
    }
    cout << endl; } // Frame auf die Konsole ausgeben  (Alternative) void Frame::frame_dump(bool b_notused) const {     for (int y = YMAX - 1; y >= 0; --y) {
        for (int x = 0; x < XMAX; x++) {
            cout.put(frame[x][y]);
        }
        cout << endl;
    }
    cout << endl; } // "Clipping" bool Frame::on_frame(int x, int y) const {     if (x >= 0 && x < XMAX && y >= 0 && y < YMAX) {
        return true;
    } else {
        return false;
    }
}

// Tauschen von Variablen
void swap(int& a, int& b) {
    int help = 0;
    help = a;
    a = b;
    b = help;
}

// Bresenham Algorithmus
void draw_line(Frame* pFrame, Coordinate start, Coordinate end) {

    bool bMerker1 = false;
    bool bMerker2 = false;

    int iX_start = start.get_x();
    int iY_start = start.get_y();
    int iX_end = end.get_x();
    int iY_end = end.get_y();

    if (iX_end < iX_start) {

        // Start- und Endpunkt vertauschen
        swap(iX_start, iX_end);
        swap(iY_start, iY_end);
    }

    if (iY_end < iY_start) {
        // Vorzeichen beider Y-Koordinaten umdrehen
        // und dafür einen Merker setzen
        iY_end = -iY_end;
        iY_start = -iY_start;
        bMerker1 = true;
    }

    if ((iX_end - iX_start) < (iY_end - iY_start)) {         swap(iX_start, iY_start); // iX_start mit iY_start vertauschen         swap(iX_end, iY_end); // iX_end mit iY_end vertauschen         bMerker2 = true; // dafür einen weiteren Merker setzen     }     int dx = iX_end - iX_start;     int dy = iY_end - iY_start;     int d = (2 * dy) - dx;     int y = iY_start;     for (int x = iX_start; x put_point(x, y); // Punkt im Frame setzen         }         // flach & fallend         if (bMerker1 == true && bMerker2 == false) {             pFrame->put_point(x, -y); // Punkt im Frame setzen
        }

        // steil & steigend
        if (bMerker1 == false && bMerker2 == true) {
            pFrame->put_point(y, x); // Punkt im Frame setzen
        }

        // steil & fallend
        if (bMerker1 == true && bMerker2 == true) {
            pFrame->put_point(y, -x); // Punkt im Frame setzen
        }

        //error = error + delta; // Fehler aktualisieren
        if (d < 0) {             d = d + 2 * dy; // Fehler anpassen         } else {             y++; // Rechts und hoch gehen             d = d - 2 * (dy - dx);         }     } } 

/*  * File:   Coordinate.h  * Author: maximilian.krieg  *  * Created on 22. April 2012, 17:25  */ #ifndef COORDINATE_H #define	COORDINATE_H class Coordinate { public:     Coordinate();     Coordinate(int, int);     int get_x();     int get_y(); private:     int x;     int y; }; #endif	/* COORDINATE_H */ 

/*  * File:   Coordinate.cpp  * Author: maximilian.krieg  *  * Created on 22. April 2012, 17:25  */ #include "Coordinate.h" Coordinate::Coordinate() { } Coordinate::Coordinate(int cx, int cy):  x(cx),  y(cy){} int Coordinate::get_x() {     return x; } int Coordinate::get_y() {     return y; }

/*  * File:   main.cpp  * Author: maximilian.krieg  *  * Created on 20. April 2012, 12:41  */ #include #include "Coordinate.h" #include "Frame.h" using namespace std; void debug_haus(Frame* pFrame) {     Coordinate start(20, 30); //Oben     Coordinate end1(30, 20); //Rechtsoben     Coordinate end2(10, 20); // Linksoben     Coordinate end3(10, 0); // Linksunten     Coordinate end4(30, 0); // Rechtsunten     draw_line(pFrame, start, end1);     draw_line(pFrame, end1, end2);     draw_line(pFrame, end2, start);     draw_line(pFrame, end2, end3);     draw_line(pFrame, end3, end4);     draw_line(pFrame, end4, end1);     draw_line(pFrame, end3, end1);     draw_line(pFrame, end2, end4); } void debug_stern(Frame* pFrame) {     Coordinate start(10, 10); // Ursprung     Coordinate end1(10, 20); // Norden     Coordinate end2(20, 10); // Osten     Coordinate end3(10, 0); // Süden     Coordinate end4(0, 10); // Westen     Coordinate end5(0, 0); // Südwesten     Coordinate end6(20, 0); // Südosten     Coordinate end7(20, 20); // Nordosten     Coordinate end8(0, 20); // Nordwesten     draw_line(pFrame, start, end1); // Norden     draw_line(pFrame, start, end2); // Osten     draw_line(pFrame, start, end3); // Süden     draw_line(pFrame, start, end4); // Westen     draw_line(pFrame, start, end5); // Südwesten     draw_line(pFrame, start, end6); // Südosten     draw_line(pFrame, start, end7); // Nordosten     draw_line(pFrame, start, end8); // Nordwesten } int main() {     Frame test;     Frame* pFrame = &test;     char c_notused='x';     clock_t start = clock_t(-1);     clock_t end = clock_t(-1);     // Test 1: Stern plotten     debug_stern(pFrame);     start = clock();     pFrame->frame_dump();
    end = clock();
    cout << (double) (end - start) / CLOCKS_PER_SEC << " Sekunden fuer " << endl;     cin >> c_notused;

    start = clock();
    pFrame->frame_dump(true);
    end = clock();
    cout << (double) (end - start) / CLOCKS_PER_SEC << " Sekunden fuer " << endl;               // Test 2: Haus plotten //    pFrame->frame_reset();
//    debug_haus(pFrame);
//
//    start = clock();
//    pFrame->frame_dump();
//    end = clock();
//    cout << (double) (end - start) / CLOCKS_PER_SEC << " Sekunden fuer " << endl; //     //    start = clock(); //    pFrame->frame_dump(true);
//    end = clock();
//    cout << (double) (end - start) / CLOCKS_PER_SEC << " Sekunden fuer " << endl;

    return 0;
}